TY - GEN
T1 - Interference-aware gossiping scheduling in uncoordinated duty-cycled multi-hop wireless networks
AU - Jiao, Xianlong
AU - Lou, Wei
AU - Wang, Xiaodong
AU - Ma, Junchao
AU - Cao, Jiannong
AU - Zhou, Xingming
PY - 2010/10/29
Y1 - 2010/10/29
N2 - 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.
AB - 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.
KW - duty cycle
KW - Gossiping scheduling
KW - interference
KW - multi-hop wireless networks
UR - http://www.scopus.com/inward/record.url?scp=77958468465&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-14654-1_24
DO - 10.1007/978-3-642-14654-1_24
M3 - Conference article published in proceeding or book
SN - 3642146538
SN - 9783642146534
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 192
EP - 202
BT - Wireless Algorithms, Systems, and Applications - 5th International Conference, WASA 2010, Proceedings
T2 - 5th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2010
Y2 - 15 August 2010 through 17 August 2010
ER -