Large scale sensor networks can be efficiently managed by dividing them into several clusters. With the help of cluster heads, each cluster communicates using some routing schedule. It is essential to rotate the role of cluster heads in a cluster to distribute energy consumption if we do not have dedicated high energy cluster heads. Usually routing and cluster head selection for such networks have been separately solved. If cluster heads are selected with the consideration of routing and routing schedule is prepared with the consideration of selected cluster heads, it can help each other. We have proposed an integrated approach of cluster head selection and routing in two tier wireless sensor network (WSN) using Genetic Algorithm based cluster head selection with A-Star algorithm based routing method to extend life of WSN. This approach can lead to significant improvements in the network lifetime over other techniques. 1. Introduction Wireless Sensor Networks are composed of a large number of sensor nodes with limited resources in terms of energy, memory, and computation. They are operated by a small battery attached to it. This battery has some initial energy, and in every communication it dissipates a fraction of the energy. Many such communications take place during the network lifetime, and every time sensor node consumes some energy which makes battery exhaust eventually. When nodes are deployed in hostile environment or in a kind of environments where it is hard to reach, in most of the cases there is no way to recharge these batteries. Sensor nodes are used for monitoring physical phenomena like temperature, humidity, acoustic, seismic, video, and so on [1]. For large scale wireless sensor networks, applications exist in a variety of fields, including medical monitoring [2–4], environmental monitoring [5, 6], surveillance, home security, military operations, and industrial machine monitoring [7]. To fulfill the requirements of these applications, sensor network should have a lifetime long enough to cater for several months. How to prolong the network lifetime to such a long time is the vital question to design and manage sensor network systems. Randomly deployed sensor nodes in the field collect required data and send towards the base station after processing them. If the optimal path (in terms of energy consumption or quality of service) is chosen for each round of communications, nodes of that particular path may get drained of energy, and network can get partitioned soon. We consider the end of network life as soon as the network gets
References
[1]
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks, vol. 38, no. 4, pp. 393–422, 2002.
[2]
C. Kidd, O. Robert, and D. Gredgory, “The Aware Home: a living laboratory for ubiquitous computing research,” in Proceedings of the 2nd International Workshop on Cooperative Buildings (CoBuild '99), 1999.
[3]
S. S. Intille, “Designing a home of the future,” IEEE Pervasive Computing, vol. 1, no. 2, pp. 76–82, 2002.
[4]
L. Schwiebert, S. K. S. Gupta, and J. Weinmann, “Research challenges in wireless networks of biomedical sensors,” in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, pp. 151–165, July 2001.
[5]
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.
[6]
D. C. Steere, A. Baptista, D. McNamee, C. Pu, and J. Walpole, “Research challenges in environmental observation and forecasting systems,” in Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM '00), pp. 292–299, August 2000.
[7]
M. Perillo and W. Heinzelman, “Wireless sensor network protocols,” in Fundamental Algorithms and Protocols for Wireless and Mobile Networks, CRC Press, Boca Raton, Fla, USA, 2005.
[8]
D. M. Blough and P. Santi, “Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad hoc networks,” in Proceedings of The 8th Annual International Conference on Mobile Computing and Networking, pp. 183–192, September 2002.
[9]
K. Akkaya and M. Younis, “A survey on routing protocols for wireless sensor networks,” Ad Hoc Networks, vol. 3, no. 3, pp. 325–349, 2005.
[10]
J. N. Al-Karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: a survey,” IEEE Wireless Communications, vol. 11, no. 6, pp. 6–27, 2004.
[11]
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.
[12]
W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks,” in Proceedings of the 33rd Annual Hawaii International Conference on System Siences (HICSS-33, '00), pp. 3005–3014, Maui, Hawaii, USA, January 2000.
[13]
O. Younis and S. Fahmy, “HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks,” IEEE Transactions on Mobile Computing, vol. 3, no. 4, pp. 366–379, 2004.
[14]
Y.-Y. Liu, H. Ji, and G.-X. Yue, “Routing protocol with optimal location of aggregation point in wireless sensor networks,” Journal of China Universities of Posts and Telecommunications, vol. 13, no. 1, pp. 1–5, 2006.
[15]
L. Li, D. Shu-Song, and W. Xiang-Ming, “An energy efficient clustering routing algorithm for wireless sensor networks,” Journal of China Universities of Posts and Telecommunications, vol. 13, no. 8, pp. 71–75, 2006.
[16]
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.
[17]
G. Gupta and M. Younis, “Load-balanced clustering of wireless sensor networks,” in Proceedings of the International Conference on Communications (ICC '03), pp. 1848–1852, May 2003.
[18]
E. Falck, P. Floren, P. Kaski, J. Kohonen, and P. Orponen, “Balanced data gathering in energy-constrained sensor networks,” in Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS '04), S. Nikoletseas and J. D. P. Rolim, Eds., vol. 3121 of Lecture Notes in Computer Science, pp. 59–70, Springer, Berlin, Germany, 2004.
[19]
Y. T. Hou, Y. Shi, J. Pan, and S. F. Midkiff, “Lifetime-optimal data routing in wireless sensor networks without flow splitting,” in Proceedings of the Workshop on Broadband Advanced Sensor Networks, San Jose, Calif, USA, 2004.
[20]
Y. T. Hou, Y. Shi, H. D. Sherali, and S. F. Midkiff, “Onenergy provisioning andrelay node placement for wireless sensor networks,” in Proceedings of the 2nd Annual IEEE Communications Society Conference on Sensor and AdHoc Communications and Networks (SECON '05), vol. 32, September 2005.
[21]
K. Kalpakis, K. Dasgupta, and P. Namjoshi, “Maximum lifetime data gathering and aggregation in wireless sensor networks,” in Proceedings of the IEEE International Conference on Networking, pp. 685–696, 2002.
[22]
J. Tang, B. Hao, and A. Sen, “Relay node placement in large scale wireless sensor networks,” Computer Communications, vol. 29, no. 4, pp. 490–501, 2006.
[23]
A. Bari, S. Wazed, A. Jaekel, and S. Bandyopadhyay, “A genetic algorithm based approach for energy efficient routing in two-tiered sensor networks,” Ad Hoc Networks, vol. 7, no. 4, pp. 665–676, 2009.
[24]
K. Rana and M. Zaveri, “A-Star algorithm for energy efficient routing in wireless sensor network,” in Trends in Network and Communications, D. C. Wyld, M. Wozniak, N. Chaki, N. Meghanathan, and D. Nagamalai, Eds., vol. 197 of Communications in Computer and Information Science, pp. 232–241, Springer, Berlin, Germany, 2011.
[25]
G. Gupta and M. Younis, “Performance evaluation of load-balanced clustering of wireless sensor networks,” in Proceedings of the 10th International Conference on Telecommunications, vol. 2, pp. 1577–1583, 2003.
[26]
M. Zhang and C. Gong, “Energy-efficient dynamic clustering algorithm in wireless sensor networks,” in Proceedings of the International Symposium on Computer Science and Computational Technology (ISCSCT '08), pp. 303–306, December 2008.
[27]
J. Nie, D. Li, Y. Han, and S. Xie, “The optimized method of cluster-head deployment based on GA-WCA in Wireless Sensor Networks,” in Proceedings of the International Conference on Computer Application and System Modeling (ICCASM '10), pp. 449–452, October 2010.
[28]
H.-S. Seo, S.-J. Oh, and C.-W. Lee, “Evolutionary genetic algorithm for efficient clustering of wireless sensor networks,” in Proceedings of the 6th IEEE Consumer Communications and Networking Conference (CCNC '09), pp. 1–5, January 2009.
[29]
M. Younis, M. Youssef, and K. Arisha, “Energy-aware routing in cluster-based sensor networks,” in Proceedings of the 10th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS '02), Fort Worth, Tex, USA, October 2002.
[30]
K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie, “Protocols for self-organization of a wireless sensor network,” IEEE Personal Communications, vol. 7, no. 5, pp. 16–27, 2000.
[31]
W. Ye, J. Heidemann, and D. Estrin, “An energy-efficient MAC protocol for wireless sensor networks,” in Proceedings of the IEEE Infocom, pp. 1567–1576, June 2002.
[32]
S. Basagni, “Distributed clustering algorithm for ad-hoc networks,” in Proceedings of the International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN '99), 1999.
[33]
M. Chatterjee, S. K. Das, and D. Turgut, “WCA: a weighted clustering algorithm for mobile ad hoc networks,” in Cluster Computing, pp. 193–204, 2002.
[34]
A. Boukerche, A. Martirosyan, and R. Pazzi, “An inter-cluster communication based energy aware and fault tolerant protocol for wireless sensor networks,” ACM Transaction on Mobile Network Application, vol. 13, no. 6, pp. 614–626, 2008.
[35]
X. Hao, Y. Kang, and Y. Wang, “Geographical-based multihop clustering algorithm for distributed wireless sensor network,” in Proceedings of the 7th World Congress on Intelligent Control and Automation (WCICA '08), pp. 3230–3235, June 2008.
[36]
D. Xia and N. Vlajic, “Near-optimal node clustering in wireless sensor networks for environment monitoring,” in Proceedings of the 21st International Conference on Advanced Information Networking and Applications (AINA '07), pp. 632–641, May 2007.
[37]
H. Chan and A. Perrig, “ACE: an emergent algorithm for highly uniform cluster formation,” in Proceedings of the 1st European Workshop Sensor Networks (EWSN '04), January 2004.
[38]
A. Bari, A. Jaekel, and S. Bandyopadhyay, “Maximizing the lifetime of two-tiered sensor networks,” in Proceedings of the IEEE International Conference on Electro Information Technology, pp. 222–226, May 2006.
[39]
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley, Reading, Mass, USA, 1989.
[40]
K. Sastry, D. Goldberg, and G. Kendall, “Genetic Algorithms,” in Introductory Tutorials in Optimization and Decision Support Techniques, E. Burke and G. Kendall, Eds., pp. 97–125, Kluwer, 2005.
[41]
M.-T. Chen and S.-S. Tseng, “A genetic algorithm for multicast routing under delay constraint in WDM network with different light splitting,” Journal of Information Science and Engineering, vol. 21, no. 1, pp. 85–108, 2005.
[42]
P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.
[43]
S. Russell and P. Norving, Artificial Intelligence: A Modern Approach, 2/E, Pearson Prentice Hall.
[44]
G. Gupta and M. Younis, “Fault-tolerant clustering of wireless sensor networks,” in Proceedings of IEEE WCNC, pp. 1579–1584, IEEE Computer Society Press, Los Alamitos, Calif, USA, 2003.
[45]
K. M. Rana and M. A. Zaveri, “Genetic algorithm based routing technique to extend lifetime of wireless sensor network,” International Journal of Advanced Research in Computer Science, vol. 1, no. 2, pp. 126–132, 2010.
[46]
J. Pan, Y. T. Hou, L. Cai, Y. Shi, and S. X. Shen, “Topology Control for Wireless Sensor Networks,” in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom '03), pp. 286–299, September 2003.
[47]
W. C. Y. Lee, Mobile Cellular Telecommunications, McGraw-Hill, 1995.
[48]
B. Chang and X. Zhang, “An energy-efficient routing algorithm for data gathering in wireless sensor networks,” in Proceedings of the Cross Strait Quad-Regional Radio Science and Wireless Technology Conference (CSQRWC '12), pp. 137–141, 2012.
[49]
N. Ababneh, A. Viglas, H. Labiod, and N. Boukhatem, “ECTC: energy efficient topology control algorithm for wireless sensor networks,” in Proceedings of the IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks and Workshops (WOWMOM '09), pp. 1–9, June 2009.
[50]
H. Yang, F. Ye, and B. Sikdar, “A swarm-intelligence-based protocol for data acquisition in networks with mobile sinks,” IEEE Transactions on Mobile Computing, vol. 7, no. 8, pp. 931–945, 2008.
[51]
W.-Y. Zhang, Z.-Z. Liang, Z.-G. Hou, and M. Tan, “A power efficient routing protocol for wireless sensor network,” in Proceedings of the IEEE International Conference on Networking, Sensing and Control (ICNSC '07), pp. 20–25, April 2007.
[52]
S. Wazed, A. Bari, A. Jaekel, and S. Bandyopadhyay, “Genetic algorithm based approach for extending the lifetime of two-tiered sensor networks,” in Proceedings of the 2nd International Symposium on Wireless Pervasive Computing, pp. 83–87, February 2007.
