Delay Minimum Data Collection in the low-duty-cycle wireless sensor networks

In low-duty-cycle wireless sensor networks, wireless nodes usually have two states: active state and dormant state. The necessary condition for a successful wireless transmission is that both the sender and the receiver are awake. In this paper, we study the problem: How fast can raw data be collected from all source nodes to a sink in low-duty-cycle WSNs? To address this, we define the Minimum Data Collection Delay (MDCD) problem, and give both the lower and upper tight bounds on the minimum delay for data collection when interfering links are eliminated. Furthermore, a novel concept, Virtual Grid Network (VGN) is introduced to successfully convert the MDCD problem into max-flow problem, and present a MDCD algorithm enlightened by the Ford-fulkerson max-flow method, which is able to find an optimal solution in polynomial time and achieves the lower bound. Extensive simulations are conducted and the results show that the proposed MDCD algorithm significantly outperforms the Shortest Path Routing algorithm (up to 32%) and achieves the lower bound.