On Minimizing Interference-Free Broadcast Latency in Duty-Cycled Wireless Sensor Networks
Xianlong Jiao, Xiaodong Wang, Wei Lou, Jiannong Cao, Xiao Xia, Xingming Zhou and Geming Xia
Broadcast is a crucial operation for routing discovery, data collection and code update in wireless sensor networks, and has attracted plenty of researches recently. In duty-cycled wireless sensor networks, nodes periodically switch between the active and sleep states, which differs from the assumption of most existing broadcast algorithms and thus makes these algorithms unsuitable. In this paper, we focus on the problem of minimizing the broadcast latency in duty-cycled wireless sensor networks while ensuring the transmissions are interference-free. We show that this problem is NP-hard, and propose a novel approximation algorithm with provable performance guarantee. We also prove that the overhead of our proposed algorithm in terms of the number of transmissions is within constant times of the optimum overhead. Extensive simulations are conducted to evaluate the performance of our proposed algorithm and the simulation results confirm the efficiency of our proposed algorithm.
Keywords: broadcast scheduling, duty cycle, approximation algorithm, maximal independent set, wireless sensor networks, protocol interference model.