On minimizing interference-free broadcast latency in duty-cycled wireless sensor networks

Xianlong Jiao, Xiaodong Wang, Wei Lou, Jiannong Cao, Xiao Xia, Xingming Zhou, Geming Xia

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

Broadcast is a crucial operation for routing discovery, data collection and code update in wireless sensor networks, and has attracted plenty of researches recently. In duty-cycled wireless sensor networks, nodes periodically switch between the active and sleep states, which differs from the assumption of most existing broadcast algorithms and thus makes these algorithms unsuitable. In this paper, we focus on the problem of minimizing the broadcast latency in duty-cycled wireless sensor networks while ensuring the transmissions are interference-free.We showthat this problem is NP-hard, and propose a novel approximation algorithm with provable performance guarantee. We also prove that the overhead of our proposed algorithm in terms of the number of transmissions is within constant times of the optimum overhead. Extensive simulations are conducted to evaluate the performance of our proposed algorithm and the simulation results confirm the efficiency of our proposed algorithm.
Original languageEnglish
Pages (from-to)293-309
Number of pages17
JournalAd-Hoc and Sensor Wireless Networks
Volume18
Issue number3-4
Publication statusPublished - 1 May 2013

Keywords

  • Approximation algorithm
  • Broadcast scheduling
  • Duty cycle
  • Maximal independent set
  • Protocol interference model
  • Wireless sensor networks

ASJC Scopus subject areas

  • Computer Science(all)
  • Instrumentation
  • Electrical and Electronic Engineering

Cite this