General Capacity Region for the Fully Connected Three-Node Packet Erasure Network
Jaemin Han, Chih-Chun Wang · IEEE Transactions on Information Theory · 2016
This paper studies the capacity region when three nodes {1, 2,3} communicate with each other by sending packets through unreliable wireless medium. For each time slot, with some probabilities a packet sent by node i may be received by both of the other nodes j and k; received only by node j (or node k); or received by neither node. Interference is avoided by enforcing that at most one node can transmit in each time slot. We assume that node i can always reach node j, possibly with the help of the third node k, for any i ≠ j pairs (thus the term fully connected). One notable example of this model is any CSMA-based Wi-Fi network with three nodes within the hearing range of each other. We consider the most general traffic demands possible in this setting. Namely, there are six private-information flows with rates (R1→2, R1→3, R2→1, R2→3, R3→1, R3→2), respectively, and three common-information flows with rates (R1→23, R2→31, R3→12), respectively. We characterize the 9-dimensional Shannon capacity region within a gap that is inversely proportional to the packet size (bits). The gap can be attributed to exchanging reception status (ACK/NACK) and can be further reduced to zero if we allow such feedbacks to be transmitted via a separate control channel. For normal-sized packets, say 12000 bits, our results effectively characterize the capacity region for many important scenarios, e.g., wireless access-point networks with client-to-client cooperative communications, and wireless two-way relay networks with packet-level coding and processing. Technical contributions of this paper include a new converse for many-to-many network communications and a new capacity-approaching scheme based on simple linear network coding operations.