Skip to main content
placeholder image

Approximation algorithms for broadcasting in duty cycled wireless sensor networks

Journal Article


Abstract


  • Broadcast is a fundamental operation in wireless sensor networks (WSNs). Given a source node with a packet to broadcast, the aim is to propagate the packet to all nodes in a collision free manner whilst incurring minimum latency. This problem, called minimum latency broadcast scheduling (MLBS), has been studied extensively in wireless ad-hoc networks whereby nodes remain on all the time, and has been shown to be NP-hard. However, only a few studies have addressed this problem in the context of duty-cycled WSNs. In these WSNs, nodes do not wake-up simultaneously, and hence, not all neighbors of a transmitting node will receive a broadcast packet at the same time. Unfortunately, the problem remains NP-hard and multiple transmissions may be necessary due to different wake-up times. Henceforth, this paper considers MLBS in duty cycled WSNs and presents two approximation algorithms, BS-1 and BS-2, that produce a maximum latency of at most (Delta- 1) TH and 13TH respectively. Here, Delta is the maximum degree of nodes, T denotes the number of time slots in a scheduling period, and H is the broadcast latency lower bound obtained from the shortest path algorithm. We evaluated our algorithms under different network configurations and confirmed that the latencies achieved by our algorithms are much lower than existing schemes. In particular, compared to OTAB, the best broadcast scheduling algorithm to date, the broadcast latency and transmission times achieved by BS-1 is at least 1/17 and 2/5 that of OTAB respectively.

Publication Date


  • 2014

Citation


  • D. Zhao, K. Chin & R. Raad, "Approximation algorithms for broadcasting in duty cycled wireless sensor networks," Wireless Networks: the journal of mobile communication, computation and information, vol. 20, (8) pp. 2219-2236, 2014.

Scopus Eid


  • 2-s2.0-84910147203

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/3324

Has Global Citation Frequency


Number Of Pages


  • 17

Start Page


  • 2219

End Page


  • 2236

Volume


  • 20

Issue


  • 8

Place Of Publication


  • Netherlands

Abstract


  • Broadcast is a fundamental operation in wireless sensor networks (WSNs). Given a source node with a packet to broadcast, the aim is to propagate the packet to all nodes in a collision free manner whilst incurring minimum latency. This problem, called minimum latency broadcast scheduling (MLBS), has been studied extensively in wireless ad-hoc networks whereby nodes remain on all the time, and has been shown to be NP-hard. However, only a few studies have addressed this problem in the context of duty-cycled WSNs. In these WSNs, nodes do not wake-up simultaneously, and hence, not all neighbors of a transmitting node will receive a broadcast packet at the same time. Unfortunately, the problem remains NP-hard and multiple transmissions may be necessary due to different wake-up times. Henceforth, this paper considers MLBS in duty cycled WSNs and presents two approximation algorithms, BS-1 and BS-2, that produce a maximum latency of at most (Delta- 1) TH and 13TH respectively. Here, Delta is the maximum degree of nodes, T denotes the number of time slots in a scheduling period, and H is the broadcast latency lower bound obtained from the shortest path algorithm. We evaluated our algorithms under different network configurations and confirmed that the latencies achieved by our algorithms are much lower than existing schemes. In particular, compared to OTAB, the best broadcast scheduling algorithm to date, the broadcast latency and transmission times achieved by BS-1 is at least 1/17 and 2/5 that of OTAB respectively.

Publication Date


  • 2014

Citation


  • D. Zhao, K. Chin & R. Raad, "Approximation algorithms for broadcasting in duty cycled wireless sensor networks," Wireless Networks: the journal of mobile communication, computation and information, vol. 20, (8) pp. 2219-2236, 2014.

Scopus Eid


  • 2-s2.0-84910147203

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/3324

Has Global Citation Frequency


Number Of Pages


  • 17

Start Page


  • 2219

End Page


  • 2236

Volume


  • 20

Issue


  • 8

Place Of Publication


  • Netherlands