We investigate the problem of uneven energy consumption in large-scale many-to-one sensor networks (modeled as concentric coronas) with constant data reporting, which is known as an energy hole around the sink. We conclude that lifetime maximization and the energy hole problem can be solved by searching optimal transmission range for the sensors in each corona and then prove this is an NP-hard optimization problem. In view of the effectiveness of ant colony algorithms in solving combinatorial optimization problems, we propose an ant-based heuristic algorithm (ASTRL) to address the optimal transmission range assignment for the goal of achieving life maximization of sensor networks. Experimentation shows that the performance of ASTRL is very close to the optimal results obtained from exhaustive search method. Furthermore, extensive simulations have also been performed to evaluate the performance of ASTRL using various simulation parameters. The simulation results reveal that, with low communication cost, ASTRL can significantly mitigate the energy hole problem in wireless sensor networks with either uniform or nonuniform node distribution. 1. Introduction Rapid technological advances in microelectromechanical systems (MEMS) and low-power wireless communications have enabled the deployment of large scale wireless sensor networks (WSNs). The potential applications of sensor networks are highly varied, such as environmental monitoring, target tracking, and battlefield surveillance [1, 2]. Due to limited and nonrechargeable energy provision, the energy resource of sensor networks should be managed wisely to extend the lifetime of sensors [3–7]. The sink node in a WSN receives the data from the sensor nodes and forwards these data to the applications over the WSN. Usually, the sensor nodes closest to the sink tend to deplete their energy budget more rapidly than others [8–10] because such nodes need to transmit more data than other nodes. This causes the problem of energy hole around the sink. A WSN suffering from the energy hole problem cannot deliver more data, and consequently the network lifetime has been greatly shortened, although most of the sensor nodes can still work properly. Recently, there have been a number of studies done on the energy hole problem for improving the network lifetime. Generally, these studies aiming to mitigate or solve the energy hole problem can be divided into 3 categories: (i) assistant approaches, such as deployment assistance, traffic compression, and aggregation in [11]; (ii) node distribution strategies. Lian et al. in [9]
References
[1]
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.
[2]
A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson, “Wireless sensor networks for habitat monitoring,” in Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, pp. 88–97, September 2002.
[3]
G. Chen, C. Li, M. Ye, and J. Wu, “An unequal cluster-based routing protocol in wireless sensor networks,” Wireless Networks, vol. 15, no. 2, pp. 193–207, 2009.
[4]
J. Jia, X. Wu, J. Chen, and X. Wang, “Exploiting sensor redistribution for eliminating the energy hole problem in mobile sensor networks,” EURASIP Journal on Wireless Communications and Networking, vol. 2012, article 68, 2012.
[5]
N. Bartolini, T. Calamoneri, A. Massini, and S. Silvestri, “On adaptive density deployment to mitigate the sink-hole problem in mobile sensor networks,” Mobile Networks and Applications, vol. 16, no. 1, pp. 134–145, 2011.
[6]
C. Song, M. Liu, J. Cao, Y. Zheng, H. Gong, and G. Chen, “Maximizing network lifetime based on transmission range adjustment in wireless sensor networks,” Computer Communications, vol. 32, no. 11, pp. 1316–1325, 2009.
[7]
D. Kandris, P. Tsioumas, A. Tzes, G. Nikolakopoulos, and D. D. Vergados, “Power conservation through energy efficient routing in wireless sensor networks,” Sensors, vol. 9, no. 9, pp. 7320–7342, 2009.
[8]
S. Olariu and I. Stojmenovi？, “Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting,” in Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM '06), April 2006.
[9]
J. Lian, K. Naik, and G. B. Agnew, “Data capacity improvement of wireless sensor networks using non-uniform sensor distribution,” International Journal of Distributed Sensor Networks, vol. 2, no. 2, pp. 121–145, 2006.
[10]
A. Wadaa, S. Olariu, L. Wilson, K. Jones, and M. Eltoweissy, “Training a sensor networks,” in Proceedings of the MONET, January 2005.
[11]
V. Mhatre and C. Rosenberg, “Design guidelines for wireless sensor networks: communication, clustering and aggregation,” Ad Hoc Networks, vol. 2, no. 1, pp. 45–63, 2004.
[12]
A. Jarry, P. Leone, O. Powell, and J. Rolim, “An optimal data propagation algorithm for maximizing the lifespan of sensor networks,” in Proceeding of the 2nd IEEE International Conference on distributed Computing in Sensor Systems (DCOSS '06), pp. 405–421, San Francisco, Calif, USA, 2006.
[13]
G. Nico and M. Tesauro, “On the connectivity of ad hoc networks: the role of the power level distribution,” in Proceedings of the 15th International Conference on Software, Telecommunications and Computer Networks (SoftCOM '07), pp. 160–164, September 2007.
[14]
F. Dressler, “Benefits of bio-inspired technologies for networked embedded systems: an overview,” in Proceedings of the Dagstuhl Seminar 06031 on Organic Computing-Controlled Emergence, Schloss Dagstuhl, Wadern, Germany, January 2006.
[15]
F. Dressler, “Efficient and scalable communication in autonomous networking using bio-inspired mechanisms—an overview,” Informatica, vol. 29, no. 2, pp. 183–188, 2005.
[16]
I. Wokoma, L. Sacks, and I. Marshall, “Biologically inspired models for sensor network,” http://www.cs.kent.ac.uk/pubs/2002/1883, 2002.
[17]
J. Li and P. Mohapatra, “Analytical modeling and mitigation techniques for the energy hole problem in sensor networks,” Pervasive and Mobile Computing, vol. 3, no. 3, pp. 233–254, 2007.
[18]
X. Wu, G. Chen, and S. K. Das, “Avoiding energy holes in wireless sensor networks with nonuniform node distribution,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 5, pp. 710–720, 2008.
[19]
G. Di Caro and M. Dorigo, “AntNet: Distributed stigmergetic control for communications networks,” Journal of Artificial Intelligence Research, vol. 9, pp. 317–365, 1998.
[20]
R. G. Aghaei, M. A. Rahman, W. Gueaieb, and A. El Saddik, “Ant colony-based reinforcement learning algorithm for routing in wireless sensor networks,” in Proceedings of the 2007 IEEE Instrumentation and Measurement Technology on Synergy of Science and Technology in Instrumentation and Measurement (IMTC '07), May 2007.
[21]
S. Okdem and D. Karaboga, “Routing in wireless sensor networks using ant colony optimization,” in Proceedings of the 1st NASA/ESA Conference on Adaptive Hardware and Systems (AHS '06), pp. 401–404, June 2006.
[22]
W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660–670, 2002.
[23]
F. Ingelrest, D. Simplot-Ryl, and I. Stojmenovi？, “Target transmission radius over LMST for energy-efficient broadcast protocol in ad hoc networks,” in Proceedings of the IEEE International Conference on Communications (ICC '04), pp. 4044–4049, Paris, france, June 2004.
