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 -