Towards energy-fairness for broadcast scheduling with minimum delay in low-duty-cycle sensor networks

• We are the first to investigate the load-balanced minimum end-to-end delay broadcast scheduling problem (LB-MEBS) for low-duty-cycle WSNs.
• We prove that LB-MEBS problem is NP-hard.
• We propose an approximation algorithm to address LB-MEBS problem.
• We also propose an efficient distributed solution to address LB-MEBS problem.
• Extensive simulation are conducted to validate the effectiveness of our proposed solutions.

Broadcast scheduling for low-duty-cycle wireless sensor networks (WSNs) has been extensively studied recently. However, existing solutions mainly focused on optimizing delay and (or) total energy consumption without considering load distribution among nodes. Due to limited energy supply for sensor nodes, heavily loaded sensors often run out of energy quickly, reducing the lifetime of the whole network. In this paper, we target at minimizing the maximum transmission load of a broadcast schedule for low-duty-cycle WSNs, subject to the constraint that each node should have the minimum end-to-end delay under the broadcast schedule. We prove that it is NP-hard to find the optimal schedule. Then, we devise a Load-Balanced Parents Assignment Algorithm (LBPA-A) that achieves λ-approximation ratio, where λ denotes the maximum number of neighbors that are scheduled to wake up at the same time and is typically a small number in low-duty-cycle WSNs. Further, we introduce how to solve this problem in a distributed manner. Our simulation results reveal that compared with the traditional solutions, our proposed LBPA-A and distributed solution both exhibit much better average performance in terms of energy-fairness, total energy consumption and delivery ratio.