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

WarningThere is a more recent version of this item available.

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


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.

Item Type:Working Paper / Technical Report
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering
Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:5246
Deposited By:Özgür Erçetin
Deposited On:05 Oct 2007 16:24
Last Modified:06 Nov 2008 10:56

Available Versions of this Item

Repository Staff Only: item control page