YDYanyan Dong

Yanyan Dong

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Yanyan Dong has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • On Optimal Finite-Length Block Codes of Size Four for Binary Symmetric Channels

    by Yanyan Dong, Shenghao Yang

    An $(n,M)$ code refers to a binary code with blocklength n and codebook size M. Such codes are studied in the context of memoryless binary symmetric channels (BSCs) with maximum likelihood (ML) decoding. Previous research has characterized some optimal codes among the linear $(n,4)$ codes for any $n \geq 2$ . However, it was unknown whether these optimal codes among linear codes were better than all nonlinear codes. In this paper, we first demonstrate that for any $n \geq 2$ , there exists an optimal code among all $(n,4)$ codes that is either linear or belongs to a subset of nonlinear codes called Class-I codes. We identify all the optimal codes among the linear $(n,4)$ codes for each blocklength $n \geq 2$ and discover some that were not previously reported in the literature. For any n from 2 to 8, all the optimal $(n,4)$ codes are identified. Except for $n=3$ , all the optimal $(n,4)$ codes are equivalent to linear codes. There exist optimal $(3,4)$ codes that are not equivalent to linear codes. Furthermore, we introduce a subset of nonlinear codes called Class-II codes and show that for any $n \gt 3$ , the set composed of linear, Class-I, and Class-II codes and their equivalent codes contains all the optimal $(n,4)$ codes. Both Class-I and Class-II codes are close to linear codes in the sense that they involve only one type of column that is not included in linear codes. We derive a sufficient condition such that all the optimal $(n,4)$ codes are equivalent to linear codes, which can be evaluated by computer with a computation cost $O(n^{6})$ .


  • Open Access

    Throughput and Latency Analysis for Line Networks With Outage Links

    by Yanyan Dong, Shenghao Yang, Jie Wang, Fan Cheng

    Wireless communication links suffer from outage events caused by fading and interference. To facilitate a tractable analysis of network communication throughput and latency, we propose an outage link model to represent a communication link in the slow fading phenomenon. For a line-topology network with outage links, we study three types of intermediate network node schemes: random linear network coding, store-and-forward, and hop-by-hop retransmission. We provide the analytical formulas for the maximum throughputs and the end-to-end latency for each scheme. To gain a more explicit understanding, we perform a scalability analysis of the throughput and latency as the network length increases. We observe that the same order of throughput/latency holds across a wide range of outage functions for each scheme. We illustrate how our exact formulae and scalability results can be applied to compare different schemes.


  • Adversarial Combinatorial Bandits With Switching Costs

    by Yanyan Dong, Vincent Y. F. Tan

    We study the problem of adversarial combinatorial bandit with a switching cost λ for a switch of each selected arm in each round, considering both the bandit feedback and semi-bandit feedback settings. In the oblivious adversarial case with K base arms and time horizon T , we derive lower bounds for the minimax regret and design algorithms to approach them. To prove these lower bounds, we design stochastic loss sequences for both feedback settings, building on an idea from previous work in Dekel et al. (2014). The lower bound for bandit feedback is Ω((λ K ) 1/3 ( TI ) 2/3 ) while that for semi-bandit feedback is Ω ( (λ KI ) 1/3 T 2/3 where I is the number of base arms in the combinatorial arm played in each round. To approach these lower bounds, we design algorithms that operate in batches by dividing the time horizon into batches to restrict the number of switches between actions. For the bandit feedback setting, where only the total loss of the combinatorial arm is observed, we introduce the BATCHED-EXP2 algorithm which achieves a regret upper bound of Õ ( (λ K ) 1/3 T 2/3 I 4/3 as T tends to infinity. In the semi-bandit feedback setting, where all losses for the combinatorial arm are observed, we propose the BATCHED-BROAD algorithm which achieves a regret upper bound of Õ ( (λ K ) 1/3 ( TI ) 2/3 ).


  • On Achievable Rates of Line Networks With Generalized Batched Network Coding

    by Jie Wang, Shenghao Yang, Yanyan Dong, Yiheng Zhang

    To better understand the wireless network design with a large number of hops, we investigate a line network formed by general discrete memoryless channels (DMCs), which may not be identical. Our focus lies on Generalized Batched Network Coding (GBNC) that encompasses most existing schemes as special cases and achieves the min-cut upper bounds as the parameters batch size and inner block length tend to infinity. The inner blocklength of GBNC provides upper bounds on the required latency and buffer size at intermediate network nodes. By employing a “bottleneck status” technique, we derive new upper bounds on the achievable rates of GBNC. These bounds surpass the min-cut bound for large network lengths when the inner blocklength and batch size are small. For line networks of canonical channels, certain upper bounds hold even with relaxed inner blocklength constraints. Additionally, we employ a “channel reduction” technique to generalize the existing achievability results for line networks with identical DMCs to networks with non-identical DMCs. For line networks with packet erasure channels, we make refinement in both the upper bound and the coding scheme, and showcase their proximity through numerical evaluations.


  • Open Access

    Design and Analysis of Systematic Batched Network Codes

    by Licheng Mao, Shenghao Yang, Xuan Huang, Yanyan Dong

    Systematic codes are of important practical interest for communications. Network coding, however, seems to conflict with systematic codes: although the source node can transmit message packets, network coding at the intermediate network nodes may significantly reduce the number of message packets received by the destination node. Is it possible to obtain the benefit of network coding while preserving some properties of the systematic codes? In this paper, we study the systematic design of batched network coding, which is a general network coding framework that includes random linear network coding as a special case. A batched network code has an outer code and an inner code, where the latter is formed by linear network coding. A systematic batched network code must take both the outer code and the inner code into consideration. Based on the outer code of a BATS code, which is a matrix-generalized fountain code, we propose a general systematic outer code construction that achieves a low encoding/decoding computation cost. To further reduce the number of random trials required to search a code with a close-to-optimal coding overhead, a triangular embedding approach is proposed for the construction of the systematic batches. We introduce new inner codes that provide protection for the systematic batches during transmission and show that it is possible to significantly increase the expected number of message packets in a received batch at the destination node, without harm to the expected rank of the batch transfer matrix generated by network coding.


  • Open Access

    On Optimal Finite-length Block Codes of Size Four for Binary Symmetric Channels

    by Yanyan Dong, Shenghao Yang

    A binary code of blocklength $n$ and codebook size $M$ is called an $(n,M)$ code, which is studied for memoryless binary symmetric channels (BSCs) with the maximum likelihood (ML) decoding. For any $n \geq 2$, some optimal codes among the linear $(n,4)$ codes have been explicitly characterized in the previous study, but whether the optimal codes among the linear codes are better than all the nonlinear codes or not is unknown. In this paper, we first show that for any $n\geq 2$, there exists an optimal code (among all the $(n,4)$ codes) that is either linear or in a subset of nonlinear codes, called Class-I codes. We identified all the optimal codes among the linear $(n,4)$ codes for each blocklength $n\geq 2$, and found ones that were not given in literature. For any $n$ from $2$ to $300$, all the optimal $(n,4)$ codes are identified, where except for $n=3$, all the optimal $(n,4)$ codes are equivalent to linear codes. There exist optimal $(3,4)$ codes that are not equivalent to linear codes. Furthermore, we derive a subset of nonlinear codes called Class-II codes and justify that for any $n >300$, the set composed of linear, Class-I and Class-II codes and their equivalent codes contains all the optimal $(n,4)$ codes. Both Class-I and Class-II codes are close to linear codes in the sense that they involve only one type of columns that are not included in linear codes. Our results are obtained using a new technique to compare the ML decoding performance of two codes, featured by a partition of the entire range of the channel output.

  • Utility Maximization for Multihop Wireless Networks Employing BATS Codes

    by Yanyan Dong, Sheng Jin, Yanzuo Chen, Shenghao Yang, Hoover H. F. Yin

    BATS (BATched Sparse) codes are a class of efficient random linear network coding variation that has been studied for multihop wireless networks mostly in scenarios of a single communication flow. Towards sophisticated multi-flow network communications, we formulate a network utility maximization (NUM) problem that jointly optimizes the BATS code parameters of all the flows and network scheduling. The NUM problem adopts a batch-wise packet loss model that can be obtained from the network local statistics without any constraints on packet loss patterns. Moreover, the NUM problem allows a different number of recoded packets to be transmitted for different batches in a flow, which is called adaptive recoding. Due to both the probably nonconcave objective and the BATS code-related variables, the algorithms developed for the existing flow optimization problems cannot be applied directly to solve our NUM problem. We introduce a two-step algorithm to solve our NUM problem, where the first step solves the problem with nonadaptive recoding schemes, and the second step optimizes adaptive recoding hop-by-hop from upstream to downstream in each flow. We perform various numerical evaluations and simulations to verify the effectiveness and efficiency of the algorithm.


  • On the Capacity Scalability of Line Networks with Buffer Size Constraints

    by Shenghao Yang, Jie Wang, Yanyan Dong, Yiheng Zhang

    The communication capacity of a network of line topology is studied, where only two adjacent nodes are connected by communication channels, and the intermediate network nodes have a buffer size constraint. Let L be the number of hops from the source node to the destination node. For general channels, we provide schemes to achieve Ω(1/ ln L) rates using a buffer of size B 1 + B 2 bits, where B 1 does not change with L and B 2 = O(ln ln L). In particular, B 1 bits of the buffer are used to store the data generated from the communication messages, and the other B 2 bits of the buffer are used to store the status of counters with the maximum value O(ln L).