A New Meta-Heuristic Approach for Optimization of Probabilistic Coverage Rate in Wireless Sensor Networks

Year 2017, Volume: 10 Issue: 4, 461 - 473, 30.10.2017

Recep Özdağ

https://doi.org/10.17671/gazibtd.318158

Abstract

The optimization of the coverage rate of the entire field of interest in terms of active surveillance of critical regions in military and civil environments determines the efficiency of the Wireless Sensor Networks (WSN) in the area. The coverage problem in WSNs is one of the critical factors that have determined the effective coverage of the area by the sensor nodes. The purpose in coverage problem, which is classified as area coverage and target coverage in the literature, is to ensure that the entire area or deterministically-specified targets in the area are effectively covered by the distributed nodes. In accordance with this purpose, an optimum solution can be found for the coverage problem in WSNs by performing the optimum dynamic deployments of sensor nodes in the field of interest.

In this study, an attempt to optimize the coverage rate of the network was made according to the Probabilistic Deployment Model using heterogeneous nodes consisting of mobile and static nodes by taking into account the area coverage problem. For this purpose, a new dynamic distribution algorithm approach was developed for WSNs based on Electromagnetism-Like (EM) algorithm which is meta-heuristic. The developed approach was compared with the OSDA-EM in the literature, and the performance and effectiveness of this method were measured. Simulation results indicated that the developed method produced optimum results in terms coverage rate and convergence rate of the nodes in the solution of the probabilistic coverage problem of the entire area and that it could be proposed.

Keywords

Wireless Sensor Networks, Area Coverage Problem, Dynamic Distribution, Probabilistic Distribution Model, Electromagnetism-Like Algorithm

Kablosuz Algılayıcı Ağlarda Olasılıksal Kapsama Oranının Optimizasyonu için Yeni Bir Meta-Sezgisel Yaklaşım

Abstract

Askeri ve sivil ortamlardaki kritik bölgelerin aktif olarak gözetlenmesi bakımından ilgili alanın tümünün kapsanma oranının optimizasyonu Kablosuz Algılayıcı Ağ (KAA)’ların alandaki etkinliğini belirler. KAA‘lardaki kapsama problemi alanın algılayıcı düğümler tarafından etkin olarak kapsanmasını belirleyen kritik faktörlerden biridir. Literatürde alan kapsama ve hedef kapsama olarak sınıflandırılan kapsama problemindeki amaç; tüm alanın veya alanda deterministik olarak belirlenen hedeflerin dağıtılan düğümler tarafından etkin olarak kapsanmasını sağlamaktır. Bu amaç doğrultusunda ilgili alanda algılayıcı düğümlerin optimum dinamik dağıtımları yapılarak KAA’lardaki kapsanma problemine optimum bir çözüm bulunabilir.

Bu çalışmada, alan kapsama problemi dikkate alınıp mobil ve statik düğümlerden oluşan heterojen düğümler kullanılarak Olasılıksal Dağıtım Modeline göre ağın kapsanma oranı optimize edilmeye çalışılmıştır. Bu amaçla; meta-sezgisel olan Elektromagnetizma-Benzer (EM) algoritması esas alınarak KAA’lar için yeni bir dinamik dağıtım algoritma yaklaşımı geliştirilmiştir. Geliştirilen yaklaşım literatürdeki OSDA-EM ile karşılaştırılması yapılarak bu yöntemin performansı ve etkinliği ölçülmüştür. Simülasyon sonuçları; geliştirilen yöntemin tüm alanın olasılıksal kapsama probleminin çözümünde hem kapsanma oranı hem de düğümlerin yakınsama hızı açısından optimum sonuçlar verdiğini ve önerilebileceğini göstermiştir.

Keywords

Kablosuz Algılayıcı Ağlar, Alan Kapsama Problemi, Dinamik Dağıtım, Olasılıksal Tarama Modeli, Elektomagnetizma-Benzer Algoritması

References

• T. He, S. Krishnamurthy, J. A. Stankovic, T. Abdelzaher, L. Luo, R. Stoleru, T. Yan, L. Gu, J. Hui, B. Krogh, “Energy-Efficient Surveillance System Using Wireless Sensor Networks”, 2nd International Conference on Mobile systems, applications and services, Boston, MA, USA, 270-283, 06 - 09 Haziran 2004.
• A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, J. Anderson, “Wireless Sensor Networks for Habitat Monitoring”, 1st ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, Georgia, USA, 88-97, 28 Eylül 2002.
• I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, “Wireless sensor networks: a survey”, Computer Networks, 38 (4), 393-422, 2002.
• M. Hefeeda, H. Ahmadi, “A Probabilistic Coverage Protocol for Wireless Sensor Networks”, IEEE International Conference on Network Protocols, Beijing, China, ISSN: 1092-1648, 16-19 Ekim 2007.
• B. Tavli, Protocol Architectures for Energy Efficient Real-Time Data Communications in Mobile Ad Hoc Networks, Doktora Tezi, University of Rochester, The College School of Engineering and Applied Sciences, 2005.
• J. Zhang, T. Yan, S. H. Son, “Deployment Strategies for Differentiated Detection in Wireless Sensor Networks”, 3th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad-Hoc Communications and Networks, Reston, VA, USA, ISBN: 1-4244-0626-9, 28 Sept. 2006.
• B. Wang, “Coverage problems in sensor networks: A Survey”, ACM Computing Surveys, , 43 (4), 53 pages, 2011.
• K. Chakrabarty, S. S. Iyengar, H. Qi, E. Cho, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks”, IEEE Transactions on Computers, 51 (12), 1448–1453, 2002.
• R. Özdağ, A. Karcı, “Sensor Node Deployment Based on Electromagnetism-Like Algorithm in Mobile Wireless Sensor Networks”, International Journal of Distributed Sensor Networks, 11 (2), 15 pages, 2015.
• N. Ahmed, S. S. Kanhere, S. Jha, “Probabilistic Coverage in Wireless Sensor Networks”, IEEE 30th Anniversary Conference on Local Computer Networks, Sydney, NSW, Australia, ISSN: 0742-1303, 17 Nov. 2005.
• R. Özdağ, A. Karcı, “Probabilistic Dynamic Distribution of Wireless Sensor Networks with Improved Distribution Method based on Electromagnetism-Like Algorithm”, Measurement, 79, 66-76, 2016.
• V. Isler, S. Kannan, K. Daniilidis, “Sampling Based Sensor Network Deployment”, EEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan, 1780-1785, 28 Eylül - 2 Ekim 2004.
• K. Kar and S. Banerjee, “Node placement for connected coverage in sensor networks”, Workshop on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Sophia Antipolis, France, 2 pages, Mart 2003.
• S. Shakkottai, S. Srikant, N. Shroff, “Unreliable Sensor Grids: Coverage, Connectivity and Diameter”, Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, CA, USA, 1073-1083, 30 Mart-3 Nisan 2003.
• Y. Zou, K. Chakrabarty, “Sensor deployment and target localization based on virtual forces”, Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, CA, USA, 1293-1303, 30 Mart-3 Nisan 2003.
• M. Garetto, M. Gribaudo, C. F. Chiasserini, E. Leonardi, “A distributed sensor relocation scheme for environmental control”, IEEE International Conference on Mobile Adhoc and Sensor Systems, Pisa, Italy, ISBN: 978-1-4244-1454-3, 8-11 Ekim 2007.
• S. Li, C. Xu, W. Pan, Y. Pan, “Sensor deployment optimization for detecting manoeuvring targets”, 7th International Conference on Information Fusion, Philadelphia, PA, USA, 1629-1635, 25-28 Temmuz 2005.
• N. Kukunuru, B. R. Thella, R. L. Davuluri, “Sensor deployment using particle swarm optimization”, International Journal of Engineering Science and Technology, 2 (10), 5395-5401, 2010.
• X. Yu, N. Liu, X. Qian, T. Zhang, “A Deployment Method Based on Spring Force in Wireless Robot Sensor Networks”, International Journal of Advanced Robotic Systems, 11 (5), 2014.
• X. Wang, S. Wang, J. Ma, “Dynamic Deployment Optimization in Wireless Sensor Networks”, Lecture Notes in Control and Information Sciences, 344, 182-187, 2006.
• Z. Li, L. Lei, “Sensor Node Deployment in Wireless Sensor Networks Based on Improved Particle Swarm Optimization”, IEEE International Conference on Applied Superconductivity and Electromagnetic Devices, Chengdu, China, 215-217, 25-27 Eylül 2009.
• C. Ozturk, D. Karaboga, B. Gorkemli, “Artificial bee colony algorithm for dynamic deployment of wireless sensor networks”, Turk J Elec Eng & Comp Sci, 20 (2), 255-262, 2012.
• C. Ozturk, D. Karaboga, B. Gorkemli, “Probabilistic Dynamic Deployment of Wireless Sensor Networks by Artificial Bee Colony Algorithm”, sensors, 11 (6), 6056–6065, 2011.
• S. I. Birbil, S. C. Fang, “An Electromagnetism-like Mechanism for Global Optimization”, Journal of Global Optimization, 25 (3), 263-282, 2003.
• R. Özdağ, “Kablosuz Algılayıcı Ağlarda Alan Kapsama için Dinamik Düğüm Dağıtımı ile Yeni bir Meta-sezgisel Yaklaşım”, 4th International Symposium On Innovative Technologies in Engineering and Science, Alanya, Antalya, Turkey, 1513-1522, 3-5 Kasım 2016.
• M. Canayaz, A. Karcı, “Cricket behaviour-based evolutionary computation technique in solving engineering optimization problems”, Applied Intelligence, 44 (2), 362-376, 2016.
• M. Demir, A. Karcı, “Data Clustering on Breast Cancer Data Using Firefly Algorithm with Golden Ratio Method”, Advances in Electrical and Computer Engineering, 15 (2), 75-84, 2015.
• J. Kratica, “An Electromagnetism-Like Approach for Solving the Low Autocorrelation Binary Sequence Problem”, Int J Comput Commun, 7(4), 688-695, 2012.
• P. Wu, W.H. Yang, N.C. Wei, “An Electromagnetism Algorithm of Neural Network Analysis -An Application to Textile Retail Operation”, Journal of the Chinese Institute of Industrial Engineers, 21 (1), 59-67, 2004.