Edge-based beaconing schedule in duty-cycled multihop wireless networks

Beaconing is a fundamental networking service where each node broadcasts a packet to all its neighbors locally. Unfortunately, the problem Minimum Latency Beaconing Schedule (MLBS) in duty-cycled scenarios is not well studied. Existing works always have rigid assumption that each node is only active once per working cycle. Aiming at making the work more practical and general, MLBS problem in duty-cycled network where each node is allowed to active multiple times in each working cycle (MLBSDCA for short) is investigated in this paper. Firstly, a modified first-fit coloring based algorithm is proposed for MLBSDCA under protocol interference model. After that, a (ρ + 1)² ∗ W-approximation algorithm is proposed to further reduce the beaconing latency, where ρ denotes the interference radius, and W is the maximum number of active time slots per working cycle. When ρ and W is equal to 1, the approximation ratio is only 4, which is better than the one (i.e., 10) in existing works. Furthermore, two approximation algorithms for MLBSDCA under physical interference model are also investigated. The theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms in term of latency.