2015/07/18 by Abhishek Sinha, Georgios S. Paschos, Sinha, Abhishek +5
Computer Science · Engineering · #Advanced Wireless Network Optimization #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1507.05240
openalex publication_date 2015/07/18 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We study the problem of efficiently broadcasting packets in multi-hop\nwireless networks. At each time slot the network controller activates a set of\nnon-interfering links and forwards selected copies of packets on each activated\nlink. A packet is considered jointly received only when all nodes in the\nnetwork have obtained a copy of it. The maximum rate of jointly received\npackets is referred to as the broadcast capacity of the network. Existing\npolicies achieve the broadcast capacity by balancing traffic over a set of\nspanning trees, which are difficult to maintain in a large and time-varying\nwireless network. We propose a new dynamic algorithm that achieves the\nbroadcast capacity when the underlying network topology is a directed acyclic\ngraph (DAG). This algorithm is decentralized, utilizes local queue-length\ninformation only and does not require the use of global topological structures\nsuch as spanning trees. The principal technical challenge inherent in the\nproblem is the absence of work-conservation principle due to the duplication of\npackets, which renders traditional queuing modelling inapplicable. We overcome\nthis difficulty by studying relative packet deficits and imposing in-order\ndelivery constraints to every node in the network. Although in-order packet\ndelivery, in general, leads to degraded throughput in graphs with cycles, we\nshow that it is throughput optimal in DAGs and can be exploited to simplify the\ndesign and analysis of optimal algorithms. Our characterization leads to a\npolynomial time algorithm for computing the broadcast capacity of any wireless\nDAG under the primary interference constraints. Additionally, we propose an\nextension of our algorithm which can be effectively used for broadcasting in\nany network with arbitrary topology.\n