|
Published Articles >> Table of Contents >> Abstract
Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'05)
pp. 332-341
Iterated Local Optimization for Minimum Energy Broadcast
Intae Kang, University of Washington
Radha Poovendran, University of Washington
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/WIOPT.2005.24
Send link to a friend
| Abstract |
|
In our prior work, we presented a highly effective local
search based heuristic algorithm called the Largest
Expanding Sweep Search (LESS) to solve the minimum
energy broadcast (MEB) problem over wireless ad hoc
or sensor networks. In this paper, the performance is
further strengthened by using iterated local optimization
(ILO) techniques at the cost of additional computational
complexity. To the best of our knowledge, this
implementation constitutes currently the best performing
algorithm among the known heuristics for MEB. We
support this claim through extensive simulation study,
comparing with globally optimal solutions obtained by
an integer programming (IP) solver. For small network
size up to 20 nodes, which is imposed by practical
limitation of the IP solver, the ILO based algorithm
produces globally optimal solutions with very high frequency
(>70%), and average performance is within
1.12% of the optimal solution.
|
 Additional Information
|
Citation:
Intae Kang, Radha Poovendran,
"Iterated Local Optimization for Minimum Energy Broadcast,"
wiopt,
pp. 332-341,
Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'05),
2005
|
|
