Interference-aware gossiping scheduling in uncoordinated duty-cycled multi-hop wireless networks

Xianlong Jiao, Wei Lou, Xiaodong Wang, Junchao Ma, Jiannong Cao, Xingming Zhou

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

4 Citations (Scopus)


Gossiping is to broadcast the message of every node to all the other nodes in multi-hop wireless networks (MWNs). This operation plays an important role and is widely used in MWNs. Interference-aware gossiping scheduling (IAGS) aims to provide an interference-free scheduling for gossiping with the minimum latency. Previous work on IAGS mostly assumes that nodes are always active, and thus is not suitable for duty-cycled scenarios. In this paper, we investigate the IAGS problem in uncoordinated duty-cycled multi-hop wireless networks (IAGS-UDC problem) under protocol interference model and unbounded-size message model. We prove that the IAGS-UDC problem is NP-hard. We propose a novel approximation algorithm called MILD for this problem. The MILD algorithm achieves an approximation ratio of 3β2(Δ+6)|T|, where β is , α denotes the ratio of the interference radius to the transmission radius, Δ denotes the maximum node degree of the network, and |T| denotes the number of time-slots in a scheduling period. Moreover, the number of transmissions scheduled by the MILD algorithm is at most 3 times as large as the minimum number of transmissions.
Original languageEnglish
Title of host publicationWireless Algorithms, Systems, and Applications - 5th International Conference, WASA 2010, Proceedings
Number of pages11
Publication statusPublished - 29 Oct 2010
Event5th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2010 - Beijing, China
Duration: 15 Aug 201017 Aug 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6221 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2010


  • duty cycle
  • Gossiping scheduling
  • interference
  • multi-hop wireless networks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this