Distributed algorithms for delay bounded minimum energy wireless broadcasting

Çiftlikli, Serkan and Öztoprak, Figen and Erçetin, Özgür and Bülbül, Kerem (2008) Distributed algorithms for delay bounded minimum energy wireless broadcasting. (Accepted/In Press)

Warning
There is a more recent version of this item available.
[thumbnail of main.pdf] PDF
main.pdf
Restricted to Registered users only

Download (253kB) | Request a copy

Abstract

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: Article
Additional Information: SU_FENS_2007/0006
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering
Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Telecommunications
Faculty of Engineering and Natural Sciences
Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Depositing User: Özgür Erçetin
Date Deposited: 06 Nov 2008 10:56
Last Modified: 22 May 2019 12:16
URI: https://research.sabanciuniv.edu/id/eprint/9982

Available Versions of this Item

Actions (login required)

View Item
View Item