Paper Info
Title
Label Coloring Based Beaconing Schedule in Duty-Cycled Multihop Wireless Networks
Abstract
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(\rho +1)^2*|\mathcal {W}|$</tex-math><alternatives><mml:math><mml:mrow><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>ρ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>*</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mi mathvariant="script">W</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq1-2907956.gif"/></alternatives></inline-formula> -approximation algorithm is proposed to further reduce the beaconing latency, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\rho$</tex-math><alternatives><mml:math><mml:mi>ρ</mml:mi></mml:math><inline-graphic xlink:href="li-ieq2-2907956.gif"/></alternatives></inline-formula> denotes the interference radius, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$|\mathcal {W}|$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>|</mml:mo><mml:mi mathvariant="script">W</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq3-2907956.gif"/></alternatives></inline-formula> is the maximum number of active time slots per working cycle. When <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\rho$</tex-math><alternatives><mml:math><mml:mi>ρ</mml:mi></mml:math><inline-graphic xlink:href="li-ieq4-2907956.gif"/></alternatives></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$|\mathcal {W}|$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>|</mml:mo><mml:mi mathvariant="script">W</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq5-2907956.gif"/></alternatives></inline-formula> 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.
Year
DOI
Venue
2020
10.1109/TMC.2019.2907956
IEEE Transactions on Mobile Computing
Keywords
DocType
Volume
Interference,Approximation algorithms,Schedules,Protocols,Scheduling algorithms,Wireless sensor networks,Scheduling
Journal
19
Issue
ISSN
Citations 
5
1536-1233
2
PageRank 
References 
Authors
0.36
0
4
Name
Order
Citations
PageRank
Quan Chen1517.05
Hong Gao21086120.07
Lianglun Cheng35129.51
Yingshu Li467153.71