EDAL: an Energy-efficient, Delay-aware, and Lifetime-balancing Data Collection Protocol for Wireless Sensor Networks

In many wireless sensor network (WSN) applications, a subset of nodes (source nodes) are selected to sense the environment, generate data, and transmit them back to the sink over multiple hops. Many previous research efforts have tried to achieve trade-offs in terms of delay, energy cost, and load balancing for such data collection tasks. Our work in this paper stems from the insight that, recent research efforts on open vehicle routing (OVR) problems, an active area in operations research, are based on similar assumptions and constraints compared to sensor networks. This insight motivates us to adapt these techniques so that we can solve or prove certain challenging problems in WSN applications. To demonstrate that this approach is feasible, we develop one data collection protocol called EDAL, which stands for Energy-efficient Delay-aware Lifetime-balancing data collection. The algorithm design of EDAL borrows one research result from OVR to prove that its problem formulation is inherently NP-hard. We then proposed both a centralized heuristic to reduce its computational overhead, and a distributed heuristic to make the algorithm scalable for large scale network operations. We also develop EDAL to be closely integrated with compressive sensing, an emerging technique that promises considerable reduction in total traffic cost for collecting sensor readings under loose delay bounds. Finally, we systematically evaluate EDAL to demonstrate its performance superiority compared to related protocols.