بهبود الگوریتم رقابت استعماری برای حل مسئله جایگذاری نودها در شبکه¬های حسگر بی¬سیم گرید سه¬بعدی
محورهای موضوعی :
سید وفا بارخدا
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.
دو فصلنامه علمي فناوري اطلاعات و ارتباطات ایران | سال دوازدهم، شمارههاي 45 و 46، پاییز و زمستان1399 صص:201_212 |
|
بهبود الگوریتم رقابت استعماری برای حل مسئله جایگذاری نودها در شبکههای حسگر بیسیم گرید سهبعدی
سیدوفا بارخدا* همت شیخی* سودابه محمدی*
*عضو هیئت علمی گروه کامپیوتر، دانشکده فناوری اطلاعات، دانشگاه صنعتی کرمانشاه
تاریخ دریافت: 30/03/1399 تاریخ پذیرش: 05/10/1399
نوع مقاله: پژوهشی
چکیده
یکی از زمینههای تحقیقاتی اساسی و مهم در شبکههای حسگر بیسیم نحوه جایگذاری نودهای حسگر است بهگونهای که با کمترین تعداد نود تمامی نقاط هدف پوشش داده شوند و اتصال میان تمام نودها و نود چاهک برقرار باشد. در این مقاله از یک روش جدید که بر اساس الگوریتم رقابت استعماری است برای حل مسئله ذکر شده استفاده شده است. در روش پیشنهاد شده امکان مهاجرت مستعمرهها از امپراطوریهای ضعیف به امپراطوریهای قویتر به الگوریتم رقابت استعماری اضافه شده است. ایده مهاجرت از جوامع انسانی الهام گرفته شده است که انسانها در برخی شرایط تصمیم به مهاجرت از یک کشور به کشور دیگر میکنند. شبکه حسگر بیسیم بهصورت سهبعدی و گرید در نظر گرفته شده است و نودهای حسگر فقط میتوانند در نقاط تقاطع گرید قرار بگیرند. این در حالیست که نقاط هدف ممکن است در هر مکانی از فضای سهبعدی پراکنده باشند. نتایج شبیهسازی نشان میدهد که الگوریتم پیشنهادی نسبت به الگوریتمهای مشابه از تعداد نود حسگر کمتری برای حل مسئله استفاده میکند و همچنین دارای زمان اجرای بسیار کمتری است.
واژگان کلیدی: شبکه حسگر بیسیم، شبکه گرید سهبعدی، الگوریتم رقابت استعماری، مهاجرت، جایگذاری نود.
3.4 فرمولبندی مسئله
تعریف 1: اگر یک نقطه هدف توسط حداقل یک نود حسگر پوشش داده شود، آن هدف را پوشش داده شده مینامیم.
تعریف 2: اگر در یک شبکه حسگر بیسیم تمام نقاط هدف پوشش داده شده باشند، آن شبکه را یک شبکه حسگرپوشش داده شده مینامیم.
در معادله 10 مجموعه Cov(TPi) نشاندهنده نودهایی است که نقطه هدف TPi را پوشش میدهند و در معادله 11، وضعیت یک نقطه هدف را از نظر پوشش نشان میدهد.
همچنین رابطه 12 شرط پوشش داده شدن کل یک شبکه را نشان میدهد.
(9)
(10)
|
Cov(TPi)= {Sj | distance(Sj , TPi) <= sr, |
(11)
|
|
تعریف 3: اگر بین هر نود حسگر و چاهک حداقل یک مسیر وجود داشته باشد، آن نود حسگر را متصل شده مینامیم.
تعریف 4: اگر در یک شبکه حسگر بیسیم، تمامی نودهای حسگر متصل شده باشند، آن شبکه را متصل مینامیم.
در یک شبکه حسگر بیسیم اگر در شعاع انتشار هر نود حسگر مانند Si حداقل یک نود دیگر مانند Sj وجود داشته باشد که به چاهک نزدیکتر است آنگاه Si میتواند از طریق Sj دادههایش را برای چاهک ارسال کند. به همین ترتیب Sj از طریق یک نود دیگر در شعاع انتشار خود مانند Sk که به چاهک نزدیکتر است میتواند دادههایش را برای چاهک ارسال کند. بنابراین اگر تمامی نودها حداقل یک نود نزدیکتر به چاهک در شعاع انتشار خود داشته باشند آنگاه کل شبکه متصل است. بدیهی است که نودهای همسایه چاهک بهصورت مستقیم با چاهک ارتباط دارند و نیازی به نود واسطه ندارند. رابطه 13 برای یک نود دلخواه Si شرایط قرارگیری نودهای دیگر در مجموعه Con(Si) را نشان میدهد و رابطه 14 وضعیت یک نود را از نظر متصل بودن به چاهک بیان میکند.
(12)
|
|
حقوق این وبسایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1404-1396
(13) |
بنابراین شرط متصل بودن کل شبکه به صورت معادله 15 خواهد بود.
4.4 الگوریتم پیشنهادی در این بخش الگوریتم 1 برای حل مسائل پوشش و اتصال در شبکه حسگر بیسیم سهبعدی گرید پیشنهاد شده است. مبنای الگوریتم بر اساس الگوریتم رقابت استعماری است که امکان مهاجرت کشورها در انتهای هر دور به آن اضافه شده است. ورودیهای الگوریتم عبارتند از: مجموعه نقاط هدف (TP)، مجموعه نقاط بالقوه برای قرارگیری حسگرها (PP)، نود چاهک و تعداد اولیه امپراطوریها (emp). همچنین الگوریتم در انتها کشور استعمارگر مربوط به قویترین امپراطوری را به عنوان جواب نهایی مسئله (IMP-BEST) معرفی میکند.
5. شبیهسازی و ارزیابی کارایی الگوریتم پیشنهادی در محیط نرمافزار MATLAB به صورت کامل پیادهسازی شده و در این بخش کارایی آن با جدیدترین رهیافتهای موجود به نامهای ACO-MCC3D [14] و NDSBA [30] مقایسه و بررسی میشود. در هر دو روش مورد مقایسه برای حل مسئله پوشش و اتصال در شبکه حسگر بیسیم از الگوریتم کلونی مورچهها در دو مرحله کلی استفاده شده است. در فاز اول نودهای مورد نیاز برای حل مسئله تعیین شده و سپس در مرحله دوم سعی میشود نودهای حسگر افزوده تشخیص و حذف شوند. دو معیار اساسی برای مقایسه عبارت است از زمان اجرای الگوریتم و تعداد نودهای سنسور مورد نیاز برای پوشش تمام نقاط هدف و اتصال تمام سنسورها به گره چاهک. بدیهی است الگوریتمی که در زمان کمتری اجرا میشود و از تعداد نود کمتری استفاده کند دارای کارایی بالاتری است. تمامی شبیهسازیها بر روی یک سیستم با پردازنده Intel i3 processor, 3.3 GHz، حافظه 4 GB وسیستمعاملWindows 7 اجرا شده است. محیط سهبعدی شبکه300×300×300 متر مکعب است که به صورت گرید تقسیمبندی شده است. نودهای حسگر فقط میتوانند در نقاط تقاطع گرید قرار بگیرند در حالیکه نقاط هدف و نود چاهک به صورت تصادفی در تمام فضای سهبعدی پخش میشوند. پارامترهای شبیهسازی در جدول 4 نمایش داده شده و نتایج از میانگین 50 بار اجرای شبیهسازیها بهدست آمده است. 1.5 تعداد نودهای مورد نیاز در اولین آزمایش تعداد نقاط هدف پوشش برابر 20، 100 و 200 در نظر گرفته شده و تعداد نودهای حسگر برای پوشش آنها بررسی شده است. جدول 5 این تعداد حسگر را بر مبنای اندازه شبکه نشان میدهد. همانگونه که قابل انتظار است با افزایش ابعاد شبکه، به جهت افزایش پیچیدگی تعداد نودهای حسگر استفاده شده اندکی افزایش یافته است. نتایج ارائه شده، مربوط به میانگین 50 بار اجرای الگوریتم هستند. جدول 4. لیست پارامترهای شبیهسازی
جدول 5. تعداد نودهای حسگر برای پوشش نقاط هدف در شبکهها با ابعاد متفاوت
در آزمایشی دیگر به جهت مقایسهپذیری با دو الگوریتم دیگر، تعداد نقاط گرید بهصورت متغیر در نظر گرفته شده بهصورتی که برای هر تعداد نقاط گرید، تعداد نقاط هدف مشخصی در شبکه وجود دارد. به عنوان مثال زمانیکه تعداد نقاط گرید 10×10×10 است، تعداد نقاط هدف 20 عدد و زمانیکه تعداد نقاط گرید 20×20×20 است، 40 نقطه هدف در نظر گرفته شده است. برای هر حالت تعداد نود حسگر مورد نیاز برای حل مسائل پوشش و اتصال در هر سه الگوریتم محاسبه شده و در شکلهای 1 و 2 نمایش داده شده است. شکل 1 مربوط به نتایج الگوریتمها بعد از 20 تکرار و شکل 2 مربوط به 40 تکرار است. همانطور که در شکل مشخص است روش پیشنهادی همواره نسبت به دو روش دیگر از تعداد نود کمتری استفاده میکند. دلیل این نتایج به استراتژی کلی الگوریتمها مربوط است. دو الگوریتم ACO-MCC3D و NDSBA تلاش میکنند تا در مرحله اول یک جواب نسبتا قابل قبول یافته و آنگاه در مرحله دوم آن را بهینه نمایند؛ اما بعد از مرحله دوم همچنان تعدادی نود افزوده باقی میمانند. در صورتی که الگوریتم پیشنهادی از همان ابتدا تلاش میکند بهترین جواب ممکن را بدون نود حسگر افزودهای بیابد.
شکل 1. مقایسه الگوریتم پیشنهادی با سایر الگوریتمها در تکرار 20
شکل 2. مقایسه الگوریتم پیشنهادی با سایر الگوریتمها در تکرار 40 همانگونه که از شکلهای 1 و 2 پیداست دو الگوریتم پیشنهادی و ACO-MCC3D در تکرار 20 ام به نتیجه نهایی خود نزدیک شده و بنابراین نتایج آنها برای تکرارهای 20 و 40 تقریبا مشابه میباشد؛ این در حالی است که الگوریتم NDSBA همچنان نیازمند تکرارهای بیشتری میباشد تا به بهترین نتیجه خود برسد.
2.5 زمان اجرا مقایسه زمان اجرای سه الگوریتم در جدول 6 بر حسب ثانیه نشان داده شده است. زمان اجرا برای دو حالت محاسبه شده است: شبکه گرید 20×20×20 با 40 نقطه هدف و شبکه گرید 100×100×100 با 200 نقطه هدف. با توجه به جدول مشخص است که الگوریتم پیشنهادی در زمان بسیار کمتری نسبت به دو الگوریتم دیگر اجرا میشود. هر دو روش ACO-MCC3D و NDSBA الگوریتم کلونی مورچگان را در دو فاز به کار میگیرند. در فاز اول هدف اصلی انتخاب موقعیتهایی در محیط برای جایگذاری گرههای حسگر است به گونهای که دو شرط پوشش و اتصال با نود چاهک برآورده شود. بدیهی است با توجه به عدم اعمال محدودیت روی شناسایی موقعیتها در این مرحله، تعداد زیادی موقعیت اضافی پیشنهاد میشود که آنها را موقعیتهای افزونه مینامند. برای رسیدن به نتیجه بهتر نیاز است که این موقعیتها شناسایی و حذف شوند. به همین علت هر دو روش ACO-MCC3D و NDSBA شامل یک فاز اضافی هستند که در آن مجددا با اجرای الگوریتم کلونی مورچگان حتی المقدور سعی میشود که موقعیتهای افزونه حذف شده و به جواب بهینه نزدیکتر شوند. در واقع در این روشها دو بار الگوریتم کلونی مورچگان اجرا میشود و همین امر سبب افزایش زمان اجرای این دو روش است. از آنجا که الگوریتم پیشنهادی تنها در یک مرحله انجام میگیرد زمان اجرای آن به صورت قابل ملاحظهای کمتر است.
جدول 6. مقایسه زمان اجرای الگوریتم پیشنهادی با سایر الگوریتمها
6. جمعبندی و نتیجهگیری در این مقاله مساله جایگذاری نودها در شبکههای حسگر بیسیم گرید و سهبعدی مورد مطالعه قرار گرفت. در این نوع شبکهها، حسگرها تنها میتوانند در نقاط تقاطع گریدها قرار داده شوند؛ این در حالی است که نقاط هدف به صورت تصادفی در سرتاسر شبکه توزیع میشوند. هر نقطه هدف باید در شعاع پوششی حداقل یک حسگر قرار گیرد تا پوشش یافته نامیده شود. اگر همه نقاط هدف پوشش یافته باشند آنگاه کل شبکه پوشش یافته است. همچنین هر حسگر باید حداقل یک مسیر تا رسیدن به نود چاهک در اختیار داشته باشد تا شبکه را متصل بنامیم. الگوریتم پیشنهادی هر دو شرط پوشش و اتصال را برآورده کرده است. لازم به ذکر است که نود چاهک به صورت تصادفی در شبکه قرار داده شده است. برای حل این مسئله، الگوریتم رقابت استعماری بهبود یافته پیشنهاد شده است. الگوریتم ICA یکی از الگوریتمهای تکاملی است که از جوامع بشری الهام گرفته است. در این مقاله برای افزایش تنوع و جلوگیری از همگرا شدن به بهینههای محلی، ایده مهاجرت پیشنهاد شده است. بدین منظور در هر مرحله برای تمامی کشورهای مستعمره امید به مهاجرت و احتمال مهاجرت محاسبه میشود که در واقع نمایانگر میزان رشد کشور در طی مراحل تکامل الگوریتم است.با توجه به احتمال مهاجرت، هر کشور میتواند از یک امپراطوری به امپراطوری دیگر برود. نتایج شبیهسازی کارایی بالای الگوریتم پیشنهادی را نسبت به بهترین الگوریتمهای موجود نشان میدهد. با توجه به این واقعیت که الگوریتم پیشنهادی در یک مرحله بهترین نتایج را به دست میآورد، زمان اجرای کمتری نسبت به سایر الگوریتمها دارد که معمولا در دو مرحله نتایج را یافته و سپس سعی میکنند تا آنها را بهبود ببخشند. همچنین تعداد نودهای انتخاب شده برای برآورده کردن پوشش و اتصال در الگوریتم پیشنهادی به صورت قابل ملاحظهای کمتر از الگوریتمهای دیگر است.
مراجع [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.
Improving imperialist competitive algorithm for solving the nodes placement problem in three-dimensional grid wireless sensor networks Abstract 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. Keywords: Wireless sensor networks, Three-dimensional grid network, Imperialist competitive algorithm, Immigration, Node placement
|