Distributed algorithms for delay bounded minimum energy wireless broadcasting
Çiftlikli, Serkan and Öztoprak, Figen and Erçetin, Özgür and Bülbül, Kerem (2007) Distributed algorithms for delay bounded minimum energy wireless broadcasting. [Working Paper / Technical Report] Sabanci University ID:SU_FENS_2007/0006 AbstractIn 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 realtime traffic are also required to provide certain quality of service (QoS) guarantees in terms of the endtoend 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 endtoend 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. Available Versions of this Item Distributed algorithms for delay bounded minimum energy wireless broadcasting. (deposited 05 Oct 2007 16:24) [Currently Displayed]
Repository Staff Only: item control page
