Delay Efficient Data Gathering Scheduling in Multi-Channel Duty-Cycled WSNs
Xiaodong Wang, Xianlong Jiao and Xingming Zhou
Delay efficient data gathering scheduling (DEG) focuses on devising a data gathering scheduling with minimum delay. DEG problem has been widely investigated in wireless sensor networks (WSNs). Nevertheless, prior solutions to DEG problem either exploit one single channel, or assume that nodes do not sleep. Multi-channel technology can mitigate the influence caused by signal interference, and duty-cycled mechanisms can help to conserve the sensor nodes’ limited energy. Thus we study the DEG problem in multi-channel duty-cycled WSNs in this paper, and call this problem as DEGCD problem. First, we prove that DEGCD problem is NP-hard. To solve DEGCD problem, we then propose a novel data gathering algorithm called NDG. We utilize two new concepts of Optional Active Conflict Graph (OACG) and Designated Active Conflict Graph (DACG) to depict the conflict relationship among the data gathering links. We also present two coloring methods to color the nodes in DACG. Based on the colors of these two coloring methods, we will schedule interfering links at different time or on different channels. Theoretical analysis shows that, our proposed NDG algorithm can achieve provable performance guarantee. Simulation results indicate that NDG algorithm can significantly improve the data gathering delay.
Keywords: Data gathering scheduling, duty cycle, approximation algorithm, multiple channels, wireless sensor networks.