Approximation algorithm for data broadcasting in duty cycled multi-hop wireless networks
Dianbo Zhao, Kwan‐Wu Chin · EURASIP Journal on Wireless Communications and Networking · 2013
Broadcast is a fundamental operation in wireless networks. To this end, many past studies have studied the NP-hard, broadcast problem for always-on multi-hop networks. However, in wireless sensor networks, nodes are powered by batteries, meaning, they have finite energy. Consequently, nodes are required to have a low duty cycle, whereby they switch between active and sleep state periodically. This means that a transmission from a node may not reach all of its neighbors simultaneously. Consequently, any developed broadcast protocols must consider collisions and the wake-up times of neighboring nodes. Henceforth, this paper studies the minimum latency broadcast scheduling problem in duty cycled multi-hop wireless networks (MLBSDC), which remains NP hard. The MLBSDC problem aims to find a collision-free schedule that minimizes the time in which the last node receives a broadcast message. We propose a novel algorithm called CFBS that allows nodes in different layers of the broadcast tree to transmit simultaneously. We prove that CFBS produces a latency of at most . Here, T denotes the number of time slots in a scheduling period, and H is the optimal broadcast latency obtained from the shortest path tree algorithm assuming no collision. We also show that the total number of transmissions is at most 4(T+2) times larger than the optimal value. The results from extensive simulation show that CFBS has a better performance than OTAB, the best broadcast scheduling algorithm to date. In particular, the broadcast latency achieved by CFBS is up to that of OTAB.