This work investigates the maximum broadcast throughput and its achievability in multi-hop wireless networks with half-duplex node constraint. We allow the use of physical-layer network coding (PNC). Although the use of PNC for unicast has been extensively studied, there has been little prior work on PNC for broadcast. Our specific results are as follows: 1) For single-source broadcast, the theoretical throughput upper bound is n (n+1), where n is the "min vertex-cut" size of the network. 2) In general, the throughput upper bound is not always achievable. 3) For grid and many other networks, the throughput upper bound n (n+1) is achievable. Our work can be considered as an attempt to understand the relationship between max-flow and min-cut in half-duplex broadcast networks with cycles (there has been prior work on networks with cycles, but not half-duplex broadcast networks).
From the reviews: "Bla Bollob's introductory course on graph theory deserves to be considered as a watershed in the development of this theory as a serious academic subject...The book has chapters on electrical networks, flows, connectivity and matchings, extremal problems, colouring, Ramsey theory, random graphs, and graphs and groups. Each chapter starts at a measured and gentle pace. Classical results are proved and new insight is provided, with the examples at the end of each chapter fully supplementing the text...Even so this allows an introduction not only to some of the deeper results but, more vitally, provides outlines of, and firm insights into, their proofs. Thus in an elementary text book, we gain an overall understanding of well-known standard results, and yet at the same time constant hints of, and guidelines into, the higher levels of the subject. It is this aspect of the book which should guarantee it a permanent place in the literature." Physical layer (PHY) network coding (PLNC), which performs the operation of network coding at physical layer, is an attractive means to improve throughput of wireless multi-hop networks. The PLNC requires multiple nodes to transmit their packets with accurate synchronization at symbol-level. Therefore, in many works of literature, centralized scheduling with perfect synchronization has been assumed to be employed on top of PLNC. Another common assumption is perfect channel state information (CSI) availability for end-nodes to decode their desired packets. However, these assumptions are challenged when we attempt to apply PLNC to large-scale and distributed networks. Therefore, in this paper, we propose a distributed medium access control (MAC) protocol for wireless multi-hop networks employing PLNC. The proposed MAC protocol is a random access protocol, which solves the PHY-specific problems, such as synchronization and CSI, jointly with distributed scheduling at MAC layer. We evaluate throughput of PLNC employing the proposed MAC protocol by computer simulation, and compare it with that of conventional relaying. With numerical results, we investigate the effectiveness of PLNC in distributed wireless multi-hop networks.  A main distinguishing feature of a wireless network compared with a wired network is its broadcast nature, in which the signal transmitted by a node may reach several other nodes, and a node may receive signals from several other nodes simultaneously. Rather than a blessing, this feature is treated more as an interference-inducing nuisance in most wireless networks today (e.g., IEEE 802.11). The goal of this paper is to show how the concept of network coding can be applied at the physical layer to turn the broadcast property into a capacity-boosting advantage in wireless ad hoc networks. Specifically, we propose a physical-layer network coding (PNC) scheme to coordinate transmissions among nodes. In contrast to "straightforward" network coding which performs coding arithmetic on digital bit streams after they have been received, PNC makes use of the additive nature of simultaneously arriving electromagnetic (EM) waves for equivalent coding operation. PNC can yield higher capacity than straight-forward network coding when applied to wireless networks. We believe this is a first paper that ventures into EM-wave-based network coding at the physical layer and demonstrates its potential for boosting network capacity. PNC opens up a whole new research area because of its implications and new design requirements for the physical, MAC, and network layers of ad hoc wireless stations. The resolution of the many outstanding but interesting issues in PNC may lead to a revolutionary new paradigm for wireless ad hoc networking. Early simulation experience with wireless ad hoc networks suggests that their capacity can be surprisingly low, due to the requirement that nodes forward each others' packets. The achievable capacity depends on network size, traffic patterns, and detailed local radio interactions. This paper examines these factors alone and in combination, using simulation and analysis from first principles. Our results include both specific constants and general scaling relationships helpful in understanding the limitations of wireless ad hoc networks. We examine interactions of the 802.11 MAC and ad hoc forwarding and the effect on capacity for several simple configurations and traffic patterns. While 802.11 discovers reasonably good schedules, we nonetheless observe capacities markedly less than optimal for very simple chain and lattice networks with very regular traffic patterns. We validate some simulation results with experiments. We also show that the traffic pattern determines whether an ad hoc network's per node capacity will scale to large networks. In particular, we show that for total capacity to scale up with network size the average distance between source and destination nodes must remain small as the network grows. Non-local traffic-patterns in which this average distance grows with the network size result in a rapid decrease of per node capacity. Thus the question “Are large ad hoc networks feasible?” reduces to a question about the likely locality of communication in such networks.  Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.   We take a new look at the issue of network capacity. It is shown that network coding is an essential ingredient in achieving the capacity of a network. Building on recent work by (see Proc. 2001 IEEE Int. Symp. Information Theory, p.102), who examined the network capacity of multicast networks, we extend the network coding framework to arbitrary networks and robust networking. For networks which are restricted to using linear network codes, we find necessary and sufficient conditions for the feasibility of any given set of connections over a given network. We also consider the problem of network recovery for nonergodic link failures. For the multicast setup we prove that there exist coding strategies that provide maximally robust networks and that do not require adaptation of the network interior to the failure pattern in question. The results are derived for both delay-free networks and networks with delays.