title   
  

Delay Constrained Energy-Efficient Broadcasting: Insights From Massively Dense Ad Hoc Networks

Bülbül, Kerem and Erçetin, Özgür and Ünlüyurt, Tonguç (2007) Delay Constrained Energy-Efficient Broadcasting: Insights From Massively Dense Ad Hoc Networks. (Submitted)

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
314Kb

Abstract

We consider source-initiated broadcast session traffic in an ad hoc wireless network operating under a hard constraint on the end-to-end delay between the source and any node in the network. Our objective in this paper is to construct an energy-efficient broadcast tree that has a maximum depth D, where D represents the end-to-end delay constraint in the network. We characterize the optimal solution to a closely related problem in massively dense networks using a dynamic programming formulation. We prove that the optimal solution can be obtained by an algorithm of polynomial time complexity O(D^2). The solution to the dynamic program indicates that there is a single optimal policy applicable to all massively dense networks. Elaborating on the insights provided by the structure of the problem in massively dense networks, we design an algorithm for finding a solution to the delay constrained minimum power broadcasting problem in general networks. By extensive simulations, we demonstrate that our proposed optimization-based algorithm generates broadcast trees within 20% of optimality for general dense networks.

Item Type:Article
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:5390
Deposited By:Kerem Bülbül
Deposited On:30 Oct 2007 16:17
Last Modified:06 Nov 2008 10:30

Repository Staff Only: item control page