بهبود الگوریتم رقابت استعماری برای حل مسئله جایگذاری نودها در شبکه¬های حسگر بی¬سیم گرید سه¬بعدی
محورهای موضوعی :
سید وفا بارخدا
1
,
همت شیخی
2
*
,
سودابه محمدی
3
1 - دانشگاه صنعتی کرمانشاه
2 - هیئت علمی
3 - عضو هیات علمی
کلید واژه: شبکه حسگر بی¬سیم, شبکه گرید سه¬بعدی, الگوریتم رقابت استعماری, مهاجرت, جایگذاری نود.,
چکیده مقاله :
یکی از زمینه های تحقیقاتی اساسی و مهم در شبکه های حسگر بی سیم نحوه جایگذاری نودهای حسگر است به گونه ای که با کمترین تعداد نود تمامی نقاط هدف پوشش داده شوند و اتصال میان تمام نودها و نود چاهک برقرار باشد. در این مقاله از یک روش جدید که بر اساس الگوریتم رقابت استعماری است برای حل مسئله ذکر شده استفاده شده است. در روش پیشنهاد شده امکان مهاجرت مستعمره ها از امپراطوری های ضعیف به امپراطوری های قوی تر به الگوریتم رقابت استعماری اضافه شده است. ایده مهاجرت از جوامع انسانی الهام گرفته شده است که انسان-ها در برخی شرایط تصمیم به مهاجرت از یک کشور به کشور دیگر می کنند. شبکه حسگر بی سیم به صورت سه بعدی و گرید در نظر گرفته شده است و نودهای حسگر فقط می توانند در نقاط تقاطع گرید قرار بگیرند. این در حالیست که نقاط هدف ممکن است در هر مکانی از فضای سه بعدی پراکنده باشند. نتایج شبیه سازی نشان می دهد که الگوریتم پیشنهادی نسبت به الگوریتم های مشابه از تعداد نود حسگر کمتری برای حل مسئله استفاده می کند و همچنین دارای زمان اجرای بسیار کمتری است.
One of the basic and important research fields in wireless sensor networks is how to place sensor nodes where by using minimum number of sensor nodes all target points are covered and all sensor nodes are connected to the sink. In this paper, a novel method based on imperialist competitive algorithm is used for solving the mentioned problem. In the proposed method, a colony can immigrate from a weak empire to more powerful empire. The idea of immigration is inspired from human society in which a human can emigrate from a country to another country. The network is supposed to be a three-dimensional grid network and the sensor nodes can be only placed at cross-points of the grids while the target points can be deployed at each point of three-dimensional space. The simulation results show that the proposed method uses fewer number of sensor nodes than other similar algorithms and has the less running time.
[1] L. Sathyapriya and A. Jawahar, “Clustering Algorithms for Wireless Sensor Networks Survey,” Sensor Letters, vol. 18, no. 2, pp. 143-149, 2020.
[2] K. Laubhan et al., “A low-power IoT framework: from sensors to the cloud,” IEEE International Conference on Electro Information Technology (EIT), Grand Forks, ND, USA, 2016.
[3] X. Su et al., “A Review of Underwater Localization Techniques, Algorithms, and Challenges,” Journal of Sensors, vol. 2020, pp. 1-24, 2020.
[4] S. Fattah et al., “A Survey on Underwater Wireless Sensor Networks: Requirements, Taxonomy, Recent Advances, and Open Research Challenges,” Sensors, vol. 20, no. 18, pp. 1-30, 2020.
[5] F. Delavernhe et al., “Robust scheduling for target tracking using wireless sensor networks,” Computers & Operations Research, vol. 116, pp. 1-14, 2020.
[6] A. Sangwan and R. P. Singh, “Survey on coverage problems in wireless sensor networks,” Wireless Personal Communications, vol. 80, no. 4, pp. 1475-1500, 2015.
[7] A. Tripathi et al., “Coverage and connectivity in WSNs: a survey, research issues and challenges,” IEEE Access, vol. 6, pp. 26971-26992, 2018.
[8] I. Khoufi, P. Minet, A. Laouiti, S. Mahfoudh, “Survey of deployment algorithms in wireless sensor networks: coverage and connectivity issues and challenges,” International Journal of Autonomous and Adaptive Communications Systems, vol. 10, no. 14, pp. 341-390, 2017.
[9] Y. Wang et al., “Coverage problem with uncertain properties in wireless sensor networks: A survey,” Computer Networks, vol. 123, pp. 200-232, 2017.
[10] B. Wang, “Coverage problems in sensor networks: a survey,” ACM Computing Surveys (CSUR), vol. 43, no. 4, p. 32, 2011.
[11] B. Peng and L. Li, “An improved localization algorithm based on genetic algorithm in wireless sensor networks,” Cognitive Neurodynamics, ISSN 1871-4080, vol. 9, Issue 2, pp. 249–256, 2015.
[12] G. Gajalakshmi and G. U. Srikanth, “A survey on the utilization of Ant Colony Optimization (ACO) algorithm in WSN,” International Conference on Information Communication and Embedded Systems (ICICES), 2016.
[13] H. Sheikhi and W. Barkhoda, “Solving the k-Coverage and m-Connected Problem in Wireless Sensor Networks through the Imperialist Competitive Algorithm,” Journal of Interconnection Networks, vol. 20, no. 1, pp. 1-18, 2020.
[14] T. Qasim et al., “An ant colony optimization based approach for minimum cost coverage on 3-D grid in wireless sensor networks,” IEEE Communications Letters, vol. 22, no. 6, pp. 1140-1143, 2018.
[15] A. Chelli et al., “One-Step approach for two-tiered constrained relay node placement in wireless sensor networks,” IEEE Wireless Communications Letters, vol. 5, no. 4, pp. 448-451, 2016.
[16] M. Bagaa et al., “Optimal placement of relay nodes over limited positions in wireless sensor networks,” IEEE Transactions on Wireless Communications, vol. 16, no. 4, pp. 2205-2219, 2017.
[17] S. K. Gupta, P. Kuila, and P. K. Jana, “Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks,” Computers & Electrical engineering, vol. 56, pp. 544-556, 2016.
[18] G. P. Gupta and S. Jha, “Biogeography-based optimization scheme for solving the coverage and connected node placement problem for wireless sensor networks,” Wireless Networks, vol. 25, no. 6, pp. 3167-3177, 2019.
[19] X. Han, X. Cao, E. L. Lioyd, C. C. Shen, “Fault-Tolerant relay node placement in heterogeneous wireless sensor networks,” IEEE TRANSACTIONS ON MOBILE COMPUTING, vol. 9, no. 5, pp. 643-656, 2009.
[20] R. Jena, “Artificial bee colony algorithm based multi-objective node placement for wireless sensor network,” International Journal of Information Technology and Computer Science, vol. 6, no. 6, 2014.
[21] H. Huang, J. Zhang, R. Wang, and Y. Qian, “Sensor node deployment in wireless sensor networks based on ionic bond-directed particle swarm optimization,” Appl. Math, vol. 8, no. 2, pp. 597–605, 2014.
[22] D. Li et al., “EasiDesign: an improved ant colony algorithm for sensor deployment in real sensor network system,” in IEEE Global Telecommunications Conference (GLOBECOM), pp. 1–5, 2010.
[23] X. Liu, “Sensor deployment of wireless sensor networks based on ant colony optimization with three classes of ant transitions,” IEEE Communications Letters, vol. 16, no. 10, pp. 1604–1607, 2012.
[24] X. Liu and D. He, “Ant colony optimization with greedy migration mechanism for node deployment in wireless sensor networks,” Journal of Network and Computer Applications, vol. 39, pp. 310–318, 2014.
[25] T. Qasim et al., “ACO-Discreet: An efficient node deployment approach in wireless sensor networks,” in Information Technology-New Generations Springer, pp. 43–48, 2018.
[26] H. Mostafaei, M. Shojafar, B. Zaher, M. Singhal, “Barrier coverage of WSNs with the imperialist competitive algorithm,” the Journal of Supercomputing, vol. 73, no. 11, pp. 4957-4980, 2017.
[27] R. Enayatifar, M. Yousefi, A. H. Abdullah, A. N. Darus, “A novel sensor deployment approach using multi-objective imperialist competitive algorithm in wireless sensor networks,” Arabian Journal for Science and Engineering, vol. 39, no. 6, pp. 4637-4650, 2014.
[28] E. A. Gargari and C. Lucas, “Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition,” IEEE Congress on Evolutionary Computation, Singapore, pp. 25-27, 2007.
[29] S. N. Shirkouhi et al., “Solving the integrated product mix-outsourcing problem using the Imperialist Competitive Algorithm,” Expert System With Applications, vol. 37, no. 12, pp. 7615-7626, 2010.
[30] G. Huang, D. Chen, and X. Liu, “A node deployment strategy for blindness avoiding in wireless sensor networks,” IEEE Communications Letters, vol. 19, no. 6, pp. 1005–1008, 2015.