Hop constrained energy-efficient broadcasting: insights from massively dense ad hoc networks

Bülbül, Kerem and Erçetin, Özgür and Ünlüyurt, Tonguç (2009) Hop constrained energy-efficient broadcasting: insights from massively dense ad hoc networks. IEEE Transactions on Mobile Computing, 8 (2). pp. 188-202. ISSN 1536-1233

This is the latest version of this item.

[thumbnail of DCMPB_v1_2.pdf] PDF
DCMPB_v1_2.pdf
Restricted to Registered users only

Download (332kB) | Request a copy

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
Uncontrolled Keywords: Quality of service; multicasting; sensor networks; end-to-end delay; network optimization
Subjects: 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: Kerem Bülbül
Date Deposited: 20 Feb 2009 09:17
Last Modified: 22 May 2019 12:21
URI: https://research.sabanciuniv.edu/id/eprint/11325

Available Versions of this Item

Actions (login required)

View Item
View Item