Iterated Local Optimization for Minimum Energy Broadcast

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 2005
Accession Number
ADA459079

Entities

People

  • Intae Kang
  • Radha Poovendran

Organizations

  • University of Washington

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Ad Hoc Networks
  • Algorithms
  • Computer Networks
  • Computer Science
  • Computers
  • Electrical Engineering
  • Integer Programming
  • Mesh Networks
  • Network Computing
  • Network Protocols
  • Networks
  • Operations Research
  • Optimization
  • Sensor Networks
  • Simulations
  • Wireless Communications
  • Wireless Networks

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Operations Research