title   
  

Distributed algorithms for delay bounded minimum energy wireless broadcasting

Çiftlikli, Serkan and Öztoprak, Figen and Erçetin, Özgür and Bülbül, Kerem (2009) Distributed algorithms for delay bounded minimum energy wireless broadcasting. International Journal of Interdisciplinary Telecommunications and Networking, 1 (2). pp. 46-65. ISSN 1941-8663 (print) 1941-8671 (electronic)

This is the latest version of this item.

[img]PDF (This is a RoMEO white publisher -- author cannot archive pre-print (ie pre-refereeing) and post-print (ie final draft post-refereeing)) - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
347Kb

Official URL: http://www.igi-global.com/bookstore/Article.aspx?TitleId=4044

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
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering
Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:15230
Deposited By:Özgür Erçetin
Deposited On:22 Nov 2010 11:59
Last Modified:22 Nov 2010 12:04

Available Versions of this Item

Repository Staff Only: item control page