Paper Info
Title
Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks
Abstract
The paper studies the problem of computing a minimal energy cost range assignment in a ad-hoe wireless network which allows a station s to perform a broadcast operation in at most h hops. The general version of the problem (i.e., when transmission costs are arbitrary) is known to be log-APX hard even for h = 2. The current paper considers the well-studied real case in which n stations are located on the plane and the cost to transmit from station i to station j is proportional to the alpha-th power of the distance between station i and j, where alpha is any positive constant. A polynomial-time algorithm is presented for finding an optimal range assignment to perform a 2-hop broadcast from a given source station. The algorithm relies on dynamic programming and operates in (worst-case) time O(n(7)). Then, a polynomial-time approximation scheme (PTAS) is provided for the above problem for any fixed h greater than or equal to 1. For fixed h greater than or equal to 1 and epsilon > 0, the PTAS has time complexity O(n(mu)) where mu = O((alpha2(alpha)h(alpha)/epsilon)(alphah)).
Year
DOI
Venue
2004
10.1007/978-3-540-24749-4_37
Lecture Notes in Computer Science
Keywords
Field
DocType
ad hoc wireless network,time complexity,polynomial time approximation scheme
Discrete mathematics,Broadcasting,Wireless network,Dynamic programming,Combinatorics,Low energy,Algorithm,Wireless ad hoc network,Hop (networking),Time complexity,Mathematics,Bounded function
Conference
Volume
ISSN
Citations 
2996
0302-9743
17
PageRank 
References 
Authors
0.74
9
8
Name
Order
Citations
PageRank
Christoph Ambühl135718.50
Andrea E. F. Clementi2116885.30
Miriam di Ianni314417.27
Nissan Lev-Tov41377.91
Angelo Monti567146.93
David Peleg66662824.19
Gianluca Rossi723521.60
Riccardo Silvestri8132490.84