TY - GEN
T1 - Delay efficient data aggregation scheduling in multi-channel duty-cycled WSNs
AU - Jiao, Xianlong
AU - Lou, Wei
AU - Feng, Xinxi
AU - Wang, Xiaodong
AU - Yang, Libin
AU - Chen, Guirong
PY - 2018/12/6
Y1 - 2018/12/6
N2 - Data aggregation scheduling is a critical issue in wireless sensor networks (WSNs). This paper studies the Delay efficient Data Aggregation scheduling problem in multi-Channel Duty-cycled WSNs (DDACD problem), which aims to accomplish data aggregation with minimum delay. Existing researches, nevertheless, either focus on non-sleeping scenarios, or assume that nodes communicate on one single channel, and thus have poor performance in multi-channel duty-cycled scenarios. In this paper, we first show that DDACD problem is NP-hard. We then propose two new concepts of Candidate Active Conflict Graphs (CACG) and Feasible Active Conflict Graphs (FACG) to depict the relationship of the data aggregation links, and present two coloring methods to well separate the links at different time-slots or on different channels. Based on these two new concepts and two coloring methods, we propose an Efficient Data Aggregation Scheduling algorithm called EDAS, which exploits the fewest-children-first rule to choose the forwarding nodes to benefit the link scheduling. We theoretically prove that our proposed EDAS algorithm can achieve provable performance guarantee. The results of extensive simulations confirm the efficiency of our algorithm.
AB - Data aggregation scheduling is a critical issue in wireless sensor networks (WSNs). This paper studies the Delay efficient Data Aggregation scheduling problem in multi-Channel Duty-cycled WSNs (DDACD problem), which aims to accomplish data aggregation with minimum delay. Existing researches, nevertheless, either focus on non-sleeping scenarios, or assume that nodes communicate on one single channel, and thus have poor performance in multi-channel duty-cycled scenarios. In this paper, we first show that DDACD problem is NP-hard. We then propose two new concepts of Candidate Active Conflict Graphs (CACG) and Feasible Active Conflict Graphs (FACG) to depict the relationship of the data aggregation links, and present two coloring methods to well separate the links at different time-slots or on different channels. Based on these two new concepts and two coloring methods, we propose an Efficient Data Aggregation Scheduling algorithm called EDAS, which exploits the fewest-children-first rule to choose the forwarding nodes to benefit the link scheduling. We theoretically prove that our proposed EDAS algorithm can achieve provable performance guarantee. The results of extensive simulations confirm the efficiency of our algorithm.
UR - http://www.scopus.com/inward/record.url?scp=85060247946&partnerID=8YFLogxK
U2 - 10.1109/MASS.2018.00055
DO - 10.1109/MASS.2018.00055
M3 - Conference article published in proceeding or book
AN - SCOPUS:85060247946
T3 - Proceedings - 15th IEEE International Conference on Mobile Ad Hoc and Sensor Systems, MASS 2018
SP - 326
EP - 334
BT - Proceedings - 15th IEEE International Conference on Mobile Ad Hoc and Sensor Systems, MASS 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 15th IEEE International Conference on Mobile Ad Hoc and Sensor Systems, MASS 2018
Y2 - 9 October 2018 through 12 October 2018
ER -