Paper Info
Title
On interference-aware gossiping in uncoordinated duty-cycled multi-hop wireless networks
Abstract
Gossiping, which broadcasts the message of every node to all the other nodes, is an important operation in multi-hop wireless networks. Interference-aware gossiping scheduling (IAGS) aims to find 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 two novel algorithms, called MILD and MILD-R, for this problem with an approximation ratio of at most 3@b^2(@D+6)|T|, where @b is 23(@a+2), @a denotes the ratio of the interference radius to the transmission radius, @D denotes the maximum node degree of the network, and |T| denotes the number of time slots in a scheduling period. The total numbers of transmissions scheduled by both two algorithms are at most three times as large as the minimum total number of transmissions. Extensive simulations are conducted to evaluate the performance of our algorithms.
Year
DOI
Venue
2013
10.1016/j.adhoc.2011.01.002
Ad Hoc Networks
Keywords
Field
DocType
Gossiping scheduling,Duty cycle,Multi-hop wireless networks
Wireless network,Scheduling (computing),Latency (engineering),Duty cycle,Computer science,Computer network,Gossip,Interference (wave propagation),Hop (networking),Distributed computing
Journal
Volume
Issue
ISSN
11
4
Ad Hoc Networks
Citations 
PageRank 
References 
4
0.38
22
Authors
6
Name
Order
Citations
PageRank
Xianlong Jiao1516.19
Wei Lou2104565.01
Xiaodong Wang316419.32
Junchao Ma41467.86
Jiannong Cao55226425.12
Xingming Zhou630638.61