Minimizing sensor movement in target coverage problem: A hybrid approach using Voronoi partition and swarm intelligence

• Autorzy: Jagtap A. M.

Identyfikatory

DOI

10.1515/bpasts-2017-0030

• Języki publikacji: EN

Abstrakty

EN

This paper addresses the major challenges that reside on target coverage problem, which is one among the two primary sub-problems of node deployment problem. In order to accomplish a cost-efficient target coverage, a Voronoi partition-based, velocity added artificial bee colony algorithm (V-VABC) is introduced. The V-VABC is an advancement over the traditional, target-based Voronoi greedy algorithm (TVgreedy). Moreover, the VABC component of V-VABC is a hybrid, heuristic search algorithm developed from the context of ABC and particle swarm optimization (PSO). The V-VABC is an attempt to solve the network, which has an equal number of both sensors and targets, which is a special case of TCOV. Simulation results show that V-VABC performs better than TV-greedy and the classical and base algorithms of V-VABC such as ABC and PSO.

Słowa kluczowe

EN

sensor; target; Voronoi; heuristic; ABC; PSO; VABC

PL

czujnik; cel; Voronoi; heurystyka; ABC; PSO; VABC

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2017
• Tom: Vol. 65, nr 2
• Strony: 263--272
• Opis fizyczny: Bibliogr. 35 poz., rys., wykr.

Twórcy

autor

Jagtap A. M.

• VEL-TECH Dr. RR & Dr. SR Technical University, Chennai 600 062, India

Bibliografia

• [1] C.-Y. Chong and S. Kumar, “Sensor networks: Evolution, opportunities, and challenges”, Proc. of the IEEE 91 (8), 1247-1256 (2003).
• [2] M. Lu, J. Wu, M. Cardei, and M. Li, “Energy-efficient connected coverage of discrete targets in wireless sensor networks”, Networking and Mobile Computing 3619, 43-52 (2005).
• [3] B. Liu, O. Dousse, P. Nain, and D. Towsley, “Dynamic coverage of mobile sensor networks”, IEEE Transactions on Parallel and Distributed Systems 24 (2), 301-311 (2013).
• [4] R.C. Luo and O. Chen, “Mobile sensor node deployment and asynchronous power management for wireless sensor networks”, IEEE Transactions on Industrial Electronics 59 (5), 2377-2385 (2012).
• [5] S. Temel, N. Unaldi, and O. Kaynak, “On deployment of wireless sensors on 3-D terrains to maximize sensing coverage by utilizing cat swarm optimization with wavelet transform”, IEEE Transactions on Systems, Man, and Cybernetics: Systems 44 (1), 111-120 (2014).
• [6] S. Mini, S.K. Udgata, and S.L. Sabat, “Sensor deployment and scheduling for target coverage problem in wireless sensor network”, IEEE Sensors Journal 14 (3), 636-644 (2014).
• [7] Y. Gu, H. Liu, and B. Zhao, “Target coverage with QoS requirements in wireless sensor networks”, Proc. Intell. Pervas. Comput., 35-38 (2007).
• [8] M. Chaudhary and A.K. Pujari, “Q-coverage problem in wireless sensor networks”, Proc. Int. Conf. Distrib. Comput. Netw., 325-330 (2009).
• [9] Z. Liao, J. Wang, S. Zhang, J. Cao, and G. Min, “Minimizing movement for target coverage and network connectivity in mobile sensor networks”, IEEE Transactions on Parallel and Distributed Systems 26 (7), 1971-1983 (2015).
• [10] M.A. Zahhad, S.M. Ahmed, N. Sabor, and S. Sasaki, “Utilisation of multi-objective immune deployment algorithm for coverage area maximisation with limit mobility in wireless sensors networks”, IET Wireless Sensor Systems 5 (5), 250-261 (2015).
• [11] W.C. Ke, B.H. Liu, and M.J. Tsai, “Constructing a wireless sensor network to fully cover critical grids by deploying minimum sensors on grid points is NP-Complete”, IEEE Trans. Computers 56 (5), 710-715 (2007).
• [12] X. Liu, “Sensor deployment of wireless sensor networks based on ant colony optimization with three classes of ant transitions”, IEEE Communications Letters 16 (10), 1604-1607 (2012).
• [13] M. Dorigo and T. Stutzle, Ant Colony Optimization, MIT Press, 2004.
• [14] C. Liu, K. Wu, and V. King, “Randomized coverage-preserving scheduling schemes for wireless sensor networks”, Proc. NETWORKING 2005, 956-967 (2005).
• [15] L.-H. Yen and Y.-M. Cheng, “Range-based sleep scheduling (RBSS) for wireless sensor networks”, Wireless Pers. Commun. 48 (3), 411-423 (2009).
• [16] A. Keshavarzian, H. Lee, and L. Venkatraman, “Wakeup scheduling in wireless sensor networks”, Proc. 7th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 322-333 (2006).
• [17] A. Makhoul and C. Pham, “Dynamic scheduling of cover-sets in randomly deployed wireless video sensor networks for surveillance applications”, Proc. 2nd IFIP Conf. Wireless Days, 73-78 (2009).
• [18] C.-Y. Chang and H.-R. Chang, “Energy-aware node placement, topology control and MAC scheduling for wireless sensor networks”, Computer Networks 52 (11), 2189-2204 (2008).
• [19] S. Dhillon, K. Chakrabarty, and S.S. Ivengar, “Sensor placement for grid coverage under imprecise detections”, Proc. 2002 International Conference on Information Fusion, 1581-1587 (2002).
• [20] S.S. Dhillon and K. Chakrabarty, “Sensor placement for effective coverage and surveillance in distributed sensor networks”, Proc. 2003 IEEE Conference on Wireless Communications and Networking, 1609-1614 (2003).
• [21] X. Bai, S. Kumar, D. Xuan, Z. Yun, and T.H. Lai, “Deploying wireless sensors to achieve both coverage and connectivity”, Proc. 7th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 131-142 (2006).
• [22] R. Tan, G. Xing, J. Wang, and H.C. So, “Exploiting reactive mobility for collaborative target detection in wireless sensor networks”, IEEE Trans. Mobile Comput. 9 (3), 317-332 (2010).
• [23] J. Kennedy, R.C. Eberhart, and Y. Shi, Swarm Intelligence, Morgan Kaufmann Publishers, San Francisco, 2001.
• [24] K.E. Parsopoulos and M.N. Vrahatis, “Recent approaches to global optimization problems through particle swarm optimization”, Natural Computing: An International Journal 1 (2-3), 235-306 (2002).
• [25] M. Clerc and J. Kennedy, “The particle swarm - explosion, stability, and convergence in a multidimensional complex space”, IEEE Trans. Evolutionary Computation 6 (1), 58-73 (2002).
• [26] D. Karaboga and B. Basturk, “A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm”, Journal of Global Optimization 39 (3), 459-171 (2007).
• [27] D. Karaboga and B. Basturk, “On the performance of artificial bee colony (ABC) algorithm”, Applied Soft Computing 8 (1), 687-697 (2008).
• [28] M. Sonmez, “Artificial bee colony algorithm for optimization of truss structures”, Applied Soft Computing 11 (2), 2406-2418 (2011).
• [29] S.N. Omkar, J. Senthilnath, R. Khandelwal, G.N. Naik, and S. Gopalakrishnan, “Artificial bee colony (ABC) for multi-objective design optimization of composite structures”, Applied Soft Computing 11 (1), 489-499 (2011).
• [30] A.R. Yildiz, “A new hybrid artificial bee colony algorithm for robust optimal design and manufacturing”, Applied Soft Computing 13 (5), 2906-2912 (2013).
• [31] A.R. Yildiz, “Optimization of cutting parameters in multi-pass turning using artificial bee colony-based approach”, Information Sciences 220, 399-407 (2013).
• [32] B. Akay, “A study on particle swarm optimization and artificial bee colony algorithms for multilevel thresholding”, Applied Soft Computing 13 (6), 3066-3091 (2013).
• [33] I. Develi, Y. Kabalci, and A. Basturk, “Artificial bee colony optimization for modelling of indoor PLC channels: A case study from Turkey”, Electric Power Systems Research 127, 73-79 (2015).
• [34] C. Ozturk, D. Karaboga, and B. Gorkemli, “Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm”, Sensors 11 (6), 6056-6065 (2011).
• [35] N. Imanian, M.E. Shiri, P. Moradi, “Velocity based artificial bee colony algorithm for high dimensional continuous optimization problems”, Engineering Applications of Artificial Intelligence 36, 148-163 (2014).

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).