Distributed algorithms for delay bounded minimum energy wireless broadcasting

Official URL: http://www.igi-global.com/journals/details.asp?id=7969

In many network applications, broadcasting is an important part of the operation where data generated by a source is disseminated to all users in the network. Judicious use of limited energy resources in wireless networks typically requires routing packets along the branches of a tree spanning the source and the destination nodes. In addition, networks that support real-time traffic are also required to provide certain quality of service (QoS) guarantees in terms of the end-to-end delay along the individual paths from the source to each of the destination nodes. Therefore, in this paper we focus on constructing a minimum power broadcast tree with a maximum depth D which corresponds to the maximum tolerable end-to-end delay in the network. We investigate two different distributed algorithms for this purpose: Distributed Tree Expansion (DTE) and Distributed Link Substitution (DLS). DTE is based on an implementation of a distributed minimum spanning tree algorithm in which the tree grows at each iteration by adding a node that can cover the maximum number of currently uncovered nodes in the network with minimum incremental transmission power and without violating the delay constraint. In DLS, we begin with a feasible broadcast tree, and then improve that solution by replacing expensive transmissions by transmissions at lower power levels while preserving the feasibility of the tree with respect to the delay bound. Hence, DTE is constructive in nature while DLS is an improvement algorithm. Although DTE increases the message complexity to O(n^3) from O(n^2) in a network of size n, it provides up to 50% improvement in total expended power compared to DLS.