Throughput-Optimal Broadcast in Wireless Networks with Dynamic Topology
We consider the problem of throughput-optimal broadcasting in a time-varying wireless network with an underlying Directed Acyclic (DAG) topology. Known broadcast algorithms route packets along pre-computed spanning trees. In large wireless networks with time-varying connectivity’s, the optimal trees are difficult to compute and maintain. In this paper we propose a new online throughput-optimal broadcast algorithm, which takes packet-by-packet scheduling and routing decisions, obviating the need for any global topological structures, such as spanning trees. Our algorithm utilizes certain queue-like system-state information for making transmission decisions and hence, may be thought of as a generalization of the well-known back-pressure policy, which makes point-to-point unicast transmission decisions based on the local queue-length information. Technically, the back-pressure algorithm is derived by greedily stabilizing the queues. However, because of packet-duplications, the work-conservation principle is violated, and an analogous queueing process is non-trivial to define in the broadcast setting. To address this fundamental issue, we identify certain state variables whose dynamics behave like virtual queues. By stochastically stabilizing these virtual queues, we devise a throughput-optimal broadcast policy. We also derive new characterizations of the broadcast capacity of time-varying wireless DAGs and propose efficient algorithms to compute the capacity either exactly or approximately under various assumptions.
Index Terms—Broadcasting, Network Control, Queueing Theory.
The problem of efficiently disseminating packets from a source node to a subset of nodes in a network is known as the Multicast problem. In the special case when the incoming packets are to be distributed among all nodes in the network, the corresponding problem is referred to as the problem. Multicasting and broadcasting are considered to be fundamental network functionalities, which enjoy numerous practical applications ranging from military communications, disaster management with mobile ad mhoc networks (MANET) , to streaming services for live web television. There exists a substantial body of literature addressing different aspects of this problem in various networking settings. An extensive survey of various multicast routing protocols for MANET is provided in. The authors of consider the problem of minimum latency broadcast of a finite set of messages in MANET, where this problem is shown to be NP-hard. To address this issue, several approximation algorithms have been proposed in, all of which rely on the construction of certain network-wide broadcast trees. Cross-layer solutions for multi-hop multicasting in the wireless network are given in and. These algorithms involve network coding, which introduces additional complexity and exacerbates end-to-end delay. The authors of propose a multicast scheduling and routing protocol which balances the load among a set of pre-computed spanning trees. However, these trees are difficult to compute and maintain in a large time-varying network. The authors of propose a local control algorithm for broadcasting in a wireless network in the so-called scheduling-free model, where an oracle is assumed to make interference-free scheduling decisions. This assumption, as noted by the authors themselves,
is not practical.
We define and characterize the broadcast capacity for wireless networks with time-varying connectivity. We show that the broadcast capacity of time-varying wireless directed acyclic networks can be computed efficiently in some settings. We then derive tight upper and lower bounds on broadcast capacity and utilize it to propose an efficient approximation algorithm to estimate the capacity in a general setting. We propose a throughput-optimal dynamic routing and scheduling policy for broadcasting in a wireless DAG with time-varying connectivity. This algorithm is of Max-Weight type and uses the idea of in-order packet delivery. To the best of our knowledge, this is the first throughput-optimal dynamic algorithm for broadcasting in time-varying wireless networks. We extend our policy to the practical scenario when the nodes have access only to delayed state information. We show that the throughput-optimality of the policy is retained even when the rate of inter-node communication is made arbitrarily small. We consider the effect of piggybacking the control information with the data packets in the absence of dedicated control channels. We illustrate our theoretical findings with extensive numerical simulations.
In this paper, we studied the problem of throughput optimal broadcasting in wireless directed acyclic networks with point-to-point links and time-varying connectivity. We characterized the broadcast capacity and derived efficient algorithms for computing the same. Next, we proposed a throughput-optimal broadcast policy. This policy does not need to maintain any spanning tree and operates based on locally available information, which is updated sporadically. The algorithm is robust and does not require statistics of the arrival or the connectivity process, thus making it useful for mobile wireless networks. The theoretical results are supplemented with illustrative simulations. A possible future direction of research would be to remove the constraint of a cyclic topology. It would also be interesting to theoretically investigate the effect of piggybacked control information exchange, which was studied empirically in this paper.
 J.P. Macker, J.E. Klinker, and M.S. Corson. Reliable multicast data delivery for military networking. In Military Communications Conference, 1996. MILCOM ’96, Conference Proceedings, IEEE, volume 2, pages 399–403 vol.2, Oct 1996.
 Min Ge, Srikanth V Krishnamurthy, and Michalis Faloutsos. Overlay multicasting for ad hoc networks. In Proceedings of Third Annual Mediterranean Ad Hoc Networking Workshop, 2004.
 D.E. Smith. IP TV Bandwidth Demand: Multicast and channel surfing. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pages 2546–2550, May 2007.
 Luo Junhai, Ye Danxia, Xue Liu, and Fan Mingyu. A survey of multicast routing protocols for mobile Ad-Hoc networks. Communications Surveys Tutorials, IEEE, 11(1):78–91, First 2009.
 Rajiv Gandhi, Srinivasan Parthasarathy, and Arunesh Mishra. Minimizing broadcast latency and redundancy in ad hoc networks. In Proceedings of the 4th ACM international symposium on
Mobile ad hoc networking & computing, pages 222–232. ACM, 2003.
 Scott CH Huang, Peng-Jun Wan, Xiaohua Jia, Hongwei Du, and Weiping Shang. Minimum-latency broadcast scheduling in wireless ad hoc networks. In 26th IEEE INFOCOM 2007.
 Jun Yuan, Zongpeng Li, Wei Yu, and Baochun Li. A cross-layer optimization framework for multihop multicast in wireless mesh networks. Selected Areas in Communications, IEEE Journal on, 24(11),
 Tracey Ho and Harish Viswanathan. Dynamic algorithms for
multicast with intra-session network coding. In Proc. 43rd Annual Allerton Conference on Communication, Control, and Computing, 2005.
 Saswati Sarkar and Leandros Tassiulas. A framework for routing
and congestion control for multicast information flows. Information Theory, IEEE Transactions on, 48(10):2690–2708, 2002.
 Don Towsley and Andrew Twigg. Rate-optimal decentralized
broadcasting: the wireless case, 2008.
 A. Sinha, G. Paschos, C. P. Li, and E. Modiano. Throughputoptimal
multihop broadcast on directed acyclic wireless networks.
IEEE/ACM Transactions on Networking, 25(1):377–391, Feb 2017.