Label Coloring 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. First, a novel kind of coloring problem, named as label coloring problem, is identified and analyzed. Second, an edge-based scheduling framework is designed and the MLBSDCA under protocol interference model is transformed to such coloring problem. Based on label coloring, a group first-fit scheduling algorithm is designed for MLBSDCA under protocol interference model. After that, a or (rho + 1)(2) * vertical bar W vertical bar-approximation algorithm is proposed to further reduce the beaconing latency, where r denotes the interference radius, and vertical bar W vertical bar is the maximum number of active time slots per working cycle. When rho and vertical bar W vertical bar 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.