Sleeping schedule-aware minimum latency broadcast in wireless ad hoc networks

Jue Hong, Jiannong Cao, Wenzhong Li, Sanglu Lu, Daoxu Chen

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

32 Citations (Scopus)


Broadcast is a fundamental operation of wireless ad hoc networks (WANET) and has been widely studied in the last decade. However, very few existing broadcasting strategies has considered the scenarios with sleeping schedule, which is a prevalent power-saving method in wireless networks. In this paper we study the sleeping schedule-aware minimum latency broadcast (MLB-SA) problem in WANETs and prove its NP-hardness. By constructing a Shortest Path Tree (SPT) defined with the latency function on the network, we derive a lower bound on the broadcast latency theoretically. Following the top-down layered approach and using the D2-coloring solution, we proposed two progressively improved algorithms: the Simple LAyered Coloring algorithm (SLAC) and the Enhanced LAyered Coloring algorithm (ELAC) for the MLB-SA problem. The SLAC has an approximation ratio of O(Δ2 + 1) where Δ is maximum degree of the network, while the ELAC has constant approximation ratio of 24|T|+1 where |T| is the number of time-slots in a scheduling period. The two algorithms have O(n2) and O(n3) time complexities respectively. The performance of the proposed algorithms are evaluated by simulations.
Original languageEnglish
Title of host publicationProceedings - 2009 IEEE International Conference on Communications, ICC 2009
Publication statusPublished - 19 Nov 2009
Event2009 IEEE International Conference on Communications, ICC 2009 - Dresden, Germany
Duration: 14 Jun 200918 Jun 2009


Conference2009 IEEE International Conference on Communications, ICC 2009

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Cite this