LABS: Latency aware broadcast scheduling in uncoordinated Duty-Cycled Wireless Sensor Networks

摘要

Broadcast is a fundamental operation in Wireless Sensor Networks (WSNs) and plays an important role in a communication protocol design. In duty-cycled scenarios, a sensor node can receive a message only in its active time slot, which makes it more difficult to design collision-free scheduling for broadcast operations. Recent studies in this area have focused on minimizing broadcast latency and guaranteeing that all nodes receive a broadcast message. This paper investigates the problem of Minimum Latency Broadcast Scheduling in Duty-Cycled (MLBSDC) WSNs. By using special geometric properties of independent sets of a broadcast tree, we reduce the number of transmissions, consequently reducing the possibility of collision. Allowing multiple transmissions in one working period, our proposed Latency Aware Broadcast Scheduling (LABS) scheme provides a latency-efficient broadcast schedule. Theoretical analysis proves that the scheme has the same approximation ratio and complexity as the previous best algorithm for the MLBSDC problem. Moreover, simulation shows that the new scheme achieves up to 34%, 37%, and 21% performance improvement over previous schemes, in terms of latency, number of transmissions, and energy consumption, respectively.