To plan the data collecting path for the mobile collector in wireless sensor network (WSN), an efficient energy-aware distributed intelligent data gathering algorithm (DIDGA) is proposed, which includes cluster formation and path formation phases. In cluster formation phase, an energy-efficient distributed clustering scheme is proposed to form a coverage-efficient WSN, which constructs a minimum connected dominating set (MCDS) based on maximal independent sets (MISs) in distributed and localized manner, and the node with more power is selected to be the cluster head in turn to prolong the network lifetime. In path formation phase, a path formation optimized algorithm (PFOA) is proposed to resolve the path formation NP problem with dynamic requirements. Then DIDGA uses the cluster head relay mechanism for planning the data gathering path. Compared with existed algorithms, detailed simulation results show that the proposed DIDGA can reduce average hop counts, average data gathering time, energy consumption, increase the efficiency of event detection ratio and prolong the network lifetime. 1. Introduction Recent advances in wireless communications and electronics have enabled the development of low-cost, low-power, multifunctional sensor nodes [1], which consist of sensed and data processing, and communicating components, leverage the idea of wireless sensor networks (WSNs) [1, 2]. Typical applications of WSNs are the unmanned environmental monitoring, military surveillance, unmanned health monitoring, target tracking, inventory management, multimedia transmitting, and so on [3, 4]. Considering that battery is the main source of energy for the sensor nodes, how to reduce the high-energy expenditure in multihop routing and extend WSN's lifetime is a major challenge [2, 4]. One important task of WSNs is to collect useful information from the sensory field [5]. For a large-scale, data centric sensor network, it is inefficient to use a single, static data sink to gather data from all sensors [6, 7]. In some applications, sensors are deployed to monitor separate areas. In each area, sensors are densely deployed and connected, while sensors that belong to different areas may be disconnected. Unlike fully connected networks, some sensors cannot forward data to the data sink via wireless links [8, 9]. In some complex terrain environment, especially in noise interference and mobile case, how to effectively gather data is a challenge task with limited power. In general, most data-gathering schemes aim to prolong lifetime of WSNs by saving power consumption and
C. Y. Chong and S. P. Kumar, “Sensor networks: evolution, opportunities, and challenges,” Proceedings of the IEEE, vol. 91, no. 8, pp. 1247–1256, 2003.
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102–114, 2002.
K. Kalpakis, “Everywhere sparse approximately optimal minimum energy data gathering and aggregation in sensor networks,” ACM Transactions on Sensor Networks, vol. 7, no. 1, 2010.
L. Shu, Y. Zhang, Z. Zhou, M. Hauswirth, Z. Yu, and G. Hynes, “Transmitting and gathering streaming data in wireless multimedia sensor networks within expected network lifetime,” Mobile Networks and Applications, vol. 13, no. 3-4, pp. 306–322, 2008.
F. Wang, J. Liu, and L. Sun, “Ambient data collection with wireless sensor networks,” Eurasip Journal on Wireless Communications and Networking, vol. 2010, 2010.
J. Wang, Y. Liu, and S. K. Das, “Energy-efficient data gathering in wireless sensor networks with asynchronous sampling,” ACM Transactions on Sensor Networks, vol. 6, no. 3, article 22, 2010.
P. Santi, “On the data gathering capacity and latency in wireless sensor networks,” IEEE Journal on Selected Areas in Communications, vol. 28, no. 7, pp. 1211–1221, 2010.
S.-H. Hong and B.-K. Kim, “An efficient data gathering routing protocol in sensor networks using the integrated gateway node,” IEEE Transactions on Consumer Electronics, vol. 56, no. 2, pp. 627–632, 2010.
H. Zhang and H. Shen, “Balancing energy consumption to maximize network lifetime in data-gathering sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 10, pp. 1526–1539, 2009.
X. Chen, X. Hu, and J. Zhu, “Data gathering schedule for minimal aggregation time in wireless sensor networks,” International Journal of Distributed Sensor Networks, vol. 5, no. 4, pp. 321–337, 2009.
K. Yuen, B. Liang, and B. Li, “A distributed framework for correlated data gathering in sensor networks,” IEEE Transactions on Vehicular Technology, vol. 57, no. 1, pp. 578–593, 2008.
Y. Yu, B. Krishnamachari, and V. K. Prasanna, “Data gathering with tunable compression in sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 2, pp. 276–287, 2008.
H.-C. Lin, F.-J. Li, and K.-Y. Wang, “Constructing maximum-lifetime data gathering trees in sensor networks with data aggregation,” in Proceedings of the IEEE International Conference on Communications (ICC '10), 2010.
J. C. Dagher, M. W. Marcellin, and M. A. Neifeld, “A theory for maximizing the lifetime of sensor networks,” IEEE Transactions on Communications, vol. 55, no. 2, pp. 323–332, 2007.
M. Zhao and Y. Yang, “An optimization based distributed algorithm for mobile data gathering in wireless sensor networks,” in Proceedings of the IEEE Conference on Computer Communications (INFOCOM '10), March 2010.
F. J. Wu, C. F. Huang, and Y. C. Tseng, “Data gathering by mobile mules in a spatially separated wireless sensor network,” in Proceedings of the 10th International Conference on Mobile Data Management: Systems, Services and Middleware (MDM '09), pp. 293–298, May 2009.
C. L. Hwang and N. W. Chang, “Fuzzy decentralized sliding-mode control of a car-like mobile robot in distributed sensor-network spaces,” IEEE Transactions on Fuzzy Systems, vol. 16, no. 1, pp. 97–109, 2008.
F. El-Moukaddem, E. Torng, and G. Xing, “Maximizing data gathering capacity of wireless sensor networks using mobile relays,” in Proceedings of the IEEE 7th International Conference on Mobile Adhoc and Sensor Systems (MASS '10), pp. 312–321, 2010.
S. Jain, R. C. Shah, and W. Brunette, “Exploiting mobility for energy efficient data collection in wireless sensor networks,” in Proceedings of the IEEE Workshop on Modeling and Optimization in Mobile Ad hoc and Wireless Networks, 2004.
S. Susca, F. Bullo, and S. Martinez, “Monitoring environmental boundaries with a robotic sensor network,” IEEE Transactions on Control Systems Technology, vol. 16, no. 2, pp. 288–296, 2008.
J. Culpepper, L. Dung, and M. Moh, “Hybrid indirect transmissions (HIT) for data gathering in wireless micro sensor networks with biomedical applications,” in Proceedings of the IEEE Annual Workshop on Computer Communications, pp. 124–133, 2003.
D. Mandala, X. Du, F. Dai, and C. You, “Load balance and energy efficient data gathering in wireless sensor networks,” Wireless Communications and Mobile Computing, vol. 8, no. 5, pp. 645–659, 2008.
J. P. Sheu, P. K. Sahoo, C. H. Su, and W. K. Hu, “Efficient path planning and data gathering protocols for the wireless sensor network,” Computer Communications, vol. 33, no. 3, pp. 398–408, 2010.
D. Jea, A. A. Somasundara, and M. B. Srivastava, “Multiple controlled mobile elements (data mules) for data collection in Sensor Networks,” in International Conference on Distributed Computing in Sensor Systems (DCOSS '05), June 2005.
Y. Wu, S. Fahmy, and N. B. Shroff, “On the construction of a maximum-lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm,” in Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM '08), pp. 1013–1021, April 2008.
Y. Kishino, Y. Sakurai, K. Kamei, Y. Yanagisawa, T. Maekawa, and T. Okadome, “Data gathering in high-density wireless sensor networks using hierarchical clustering,” in Proceedings of the IEEE International Symposium on Wireless Communication Systems (ISWCS '08), pp. 547–551, October 2008.
Y. Revah and M. Segal, “Improved algorithms for data-gathering time in sensor networks II: Ring, Tree, and Grid topologies,” International Journal of Distributed Sensor Networks, vol. 5, no. 5, pp. 463–479, 2009.
C. Luo, F. Wu, J. Sun, and C. W. Chen, “Compressive data gathering for large-scale wireless sensor networks,” in Proceedings of the 15th Annual ACM International Conference on Mobile Computing and Networking (MobiCom '09), pp. 145–156, September 2009.
M. Ma and Y. Yang, “Data gathering in wireless sensor networks with mobile collectors,” in Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS '08), April 2008.
A. Boukerche and X. Fei, “Adaptive data-gathering protocols with mobile collectors for vehicular ad-hoc and sensor networks,” in Proceedings of the 4th IEEE International Conference on Wireless and Mobile Computing, Networking and Communication (WiMob '08), pp. 7–12, 2008.
E. M. Saad, M. H. Awadalla, and R. R. Darwish, “A data gathering algorithm for a mobile sink in large-scale sensor networks,” in Proceedings of the 4th International Conference on Wireless and Mobile Communications (ICWMC '08), pp. 207–213, August 2008.
G. F. Zaki, H. M. Elsayed, H. H. Amer, and M. S. El-Soudani, “Energy balanced model for data gathering in wireless sensor networks with fixed and mobile sinks,” in Proceedings of the 18th International Conference on Computer Communications and Networks (ICCCN '09), August 2009.
