رقم المقالة : A-10-2343-1 زيارة : 8505 الصفحة: 201 - 212

نوع المخطوط: المحکّمة

بهبود الگوریتم رقابت استعماری برای حل مسئله جایگذاری نودها در شبکه¬های حسگر بی¬سیم گرید سه¬بعدی

الموضوعات :

سید وفا بارخدا ¹ , همت شیخی ² , سودابه محمدی ³

1 - دانشگاه صنعتی کرمانشاه
2 - هیئت علمی
3 - عضو هیات علمی

تاريخ الإرسال : 19 الإثنين , جمادى الثانية, 1442 تاريخ التأكيد : 28 الثلاثاء , شعبان, 1441 تاريخ الإصدار : 28 الثلاثاء , شعبان, 1441

الکلمات المفتاحية: شبکه حسگر بی¬سیم, شبکه گرید سه¬بعدی, الگوریتم رقابت استعماری, مهاجرت, جایگذاری نود.,

ملخص المقالة :

یکی از زمینه های تحقیقاتی اساسی و مهم در شبکه های حسگر بی سیم نحوه جایگذاری نودهای حسگر است به گونه ای که با کمترین تعداد نود تمامی نقاط هدف پوشش داده شوند و اتصال میان تمام نودها و نود چاهک برقرار باشد. در این مقاله از یک روش جدید که بر اساس الگوریتم رقابت استعماری است برای حل مسئله ذکر شده استفاده شده است. در روش پیشنهاد شده امکان مهاجرت مستعمره ها از امپراطوری های ضعیف به امپراطوری های قوی تر به الگوریتم رقابت استعماری اضافه شده است. ایده مهاجرت از جوامع انسانی الهام گرفته شده است که انسان-ها در برخی شرایط تصمیم به مهاجرت از یک کشور به کشور دیگر می کنند. شبکه حسگر بی سیم به صورت سه بعدی و گرید در نظر گرفته شده است و نودهای حسگر فقط می توانند در نقاط تقاطع گرید قرار بگیرند. این در حالیست که نقاط هدف ممکن است در هر مکانی از فضای سه بعدی پراکنده باشند. نتایج شبیه سازی نشان می دهد که الگوریتم پیشنهادی نسبت به الگوریتم های مشابه از تعداد نود حسگر کمتری برای حل مسئله استفاده می کند و همچنین دارای زمان اجرای بسیار کمتری است.

المصادر:

[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

$E:\E Drive\logo\iicta Logo0.JPG$

بهبود الگوریتم رقابت استعماری برای حل مسئله جایگذاری نودها در شبکههای حسگر بیسیم گرید سهبعدی

سیدوفا بارخدا* همت شیخی* سودابه محمدی*

*عضو هیئت علمی گروه کامپیوتر، دانشکده فناوری اطلاعات، دانشگاه صنعتی کرمانشاه

تاریخ دریافت: 30/03/1399 تاریخ پذیرش: 05/10/1399

نوع مقاله: پژوهشی

چکیده

یکی از زمینههای تحقیقاتی اساسی و مهم در شبکههای حسگر بیسیم نحوه جایگذاری نودهای حسگر است بهگونهای که با کمترین تعداد نود تمامی نقاط هدف پوشش داده شوند و اتصال میان تمام نودها و نود چاهک برقرار باشد. در این مقاله از یک روش جدید که بر اساس الگوریتم رقابت استعماری است برای حل مسئله ذکر شده استفاده شده است. در روش پیشنهاد شده امکان مهاجرت مستعمرهها از امپراطوریهای ضعیف به امپراطوریهای قویتر به الگوریتم رقابت استعماری اضافه شده است. ایده مهاجرت از جوامع انسانی الهام گرفته شده است که انسانها در برخی شرایط تصمیم به مهاجرت از یک کشور به کشور دیگر میکنند. شبکه حسگر بیسیم بهصورت سهبعدی و گرید در نظر گرفته شده است و نودهای حسگر فقط میتوانند در نقاط تقاطع گرید قرار بگیرند. این در حالیست که نقاط هدف ممکن است در هر مکانی از فضای سهبعدی پراکنده باشند. نتایج شبیهسازی نشان میدهد که الگوریتم پیشنهادی نسبت به الگوریتمهای مشابه از تعداد نود حسگر کمتری برای حل مسئله استفاده میکند و همچنین دارای زمان اجرای بسیار کمتری است.

واژگان کلیدی: شبکه حسگر بیسیم، شبکه گرید سهبعدی، الگوریتم رقابت استعماری، مهاجرت، جایگذاری نود.

1. مقدمه

امروزه یکی از حوزههای مورد توجه محققان کامپیوتر، نحوه ایجاد شبکههای حسگر بیسیم است و پژوهشهای زیادی بر روی جنبههای مختلف طراحی و پیادهسازی این شبکهها در حال انجام هستند. از جمله مزیتهای این نوع از شبکهها نسبت به شبکههای کامپیوتری سنتی میتوان به مقیاسپذیری، انعطافپذیری و تنوع فراوان کاربردهای آنها از قبیل پیگیری نقاط هدف، نظارت بر محیطهای

نویسنده مسئول: همت شیخی h.sheikhi@kut.ac.ir

غیرقابل دسترس و غیره اشاره نمود [1]. همچنین بسیاری از تحقیقات در حال تجمیع شبکههای حسگر بیسیم با اینترنت اشیا هستند، بهنحوی که نودهای حسگر بتوانند به راحتی به اینترنت متصل شده و وظایف خود را انجام دهند [2].

با توجه به نوع کاربرد، محیط عملیاتی برای قرارگیری حسگرها را میتوان به صورت دو بعدی و یا سه بعدی در نظر گرفت؛ لازم به ذکر است که در بیشترتحقیقات انجام شده بر روی شبکههای حسگر در سالیان گذشته، آنها را به صورتی فرض کردهاند که حسگرها در یک محیط مسطح زمینی قرار میگیرند. اما در سالهای اخیر کاربردهای فراوانی برای این شبکهها پیشنهاد شده است که نیازمند قرار گیری نودها در ارتفاع هستند[2].

به عنوان مثال در شبکههای حسگر بیسیم زیرآبی، گرهها در یک محیط سه بعدی قرار دارند و از سیگنالهای صوتی برای برقراری ارتباط استفاده میکنند. در سالهای اخیر این شبکهها بسیار مورد توجه قرار گرفتهاند و از آنها برای نظارت و اکتشاف در اقیانوسها استفاده شده است. کاربردهایی از قبیل هشدار سونامی، کمک به ناوبری و جمع آوری اطلاعات اقیانوسشناسی از جمله کاربردهای شبکههای حسگر زیرآبی است [3] [4]. همچنین میتوان به گرههایی که بر روی درختان یک جنگل قرار میگیرند و یک ویژگی خاص مانند نحوه رشد برگها را نظارت میکنند اشاره نمود. با توجه به این کاربردها و همچنین این نکته که محیطهای دوبعدی اساسا زیرمجموعه محیطهای سهبعدی هستند، در این مقاله محیط عملیاتی بهصورت سهبعدی در نظر گرفته شده است. به علاوه، نحوه قرارگیری نودهای حسگر از استراتژی گرید تبعیت میکند که در آن شبکه سه بعدی به سلولهای مکعبی تقسیم شده و هر نود حسگر میتواند در رئوس این سلولها قرار بگیرد.

یکی از چالشهای اساسی در شبکههای حسگر بیسیم این است که نودهای حسگر باید طوری در محیط عملیاتی جایگذاری شوند که بتوانند کل محیط یا نقاط و بخشهای مورد نیاز را پوشش دهند و رخدادهای اتفاق افتاده در آن مناطق را مانیتور کنند [5]. بدین منظور هر نود دارای یک شعاع حسی است و قادر است تمام رویدادهای اتفاق افتاده در این شعاع را مانیتور کند. پوشش یک محیط عملیاتی به سه روش پوشش کلی، پوشش نقطهای و پوشش حصاری قابل انجام است که در این میان پوشش نقطهای کاربردهای واقعی بیشتری دارند [6][7]. در این نوع پوشش، تنها باید مکانهای خاصی از شبکه پوشش داده شوند؛ به عنوان مثال در یک جنگل به جای پوشش کل فضا، فقط مکانهای نزدیک و روی درختان پوشش داده میشود. اینکار باعث میشود که از جایگذاری نودهای اضافی در شبکه اجتناب شود و هزینه ایجاد شبکه، کاهش چشمگیری داشته باشد. ازاینرو یکی از مسائلی که در این مقاله مورد بررسی قرار میگیرد، مسئله پوشش نقطهای در شبکههای حسگر است.

در جایگذاری نودها علاوه بر مسئله پوشش باید ویژگی متصل بودن شبکه نیز در نظر گرفته شود. در شبکههای حسگر بیسیم فراهم کردن پوشش بدون برقراری اتصال باعث کاهش کیفیت شبکه میشود زیرا تضمینی وجود ندارد که رخدادهای کشف شده در محیط عملیاتی، بهدرستی به نود چاهک گزارش شوند [8]. برای متصل کردن نودهای حسگر به چاهک، ممکن است نیاز به جایگذاری نودهای اضافی باشد که هیچ رخدادی را مانیتور نمیکنند و فقط دادههای سایر نودها را دریافت و ارسال میکنند.

موضوع بررسی شده در این مقاله بدین شرح است که نود چاهک به همراه تعدادی هدف نقطهای با موقعیت تصادفی در فضای یک شبکه حسگر سهبعدی قرار دارند. مساله انتخاب رئوسی در سلولها برای جایگذاری نودهای حسگر است که علاوه بر اینکه تمامی نقاط هدف پوشش داده شوند، ارتباط تمامی نودهای حسگر با چاهک نیز برقرار شود. بدیهی است که بهمنظور کاهش هزینه، اینکار باید با کمترین تعداد ممکن نود انجام شود. در [9] حل مسائل پوشش و اتصال برای شبکههای حسگر بیسیم به عنوان مسئلهای NP-کامل اثبات شده و از این رو برای حل این مسائل، عموما از روشهای اکتشافی و یا متا اکتشافی استفاده میشود [10].

با توجه به ماهیت بهینهسازی در حل مسئله جایگذاری حسگر در شبکههای حسگر بیسیم، استفاده از روشهای تکاملی بسیار مورد استقبال بوده و نتایج قابل توجهی به دست آمده است. در این میان به ویژه استفاده از الگوریتمهای ژنتیک، کلونی مورچگان و کلونی زنبورها مورد توجه بوده است که درهمه آنها به نوعی از طبیعت الهام گرفته شده است [11][12]. یکی از روشهای تکاملی جدیدتر که از جوامع انسانی الهام گرفته و علیرغم داشتن پتانسیل زیاد برای حل این مسئله، تا کنون به صورت جدی مورد توجه قرار نگرفته است، الگوریتم رقابت استعماری میباشد.

این الگوریتم همانند دیگر الگوریتمهای تکاملی، نیازی به دانستن اطلاعات گرادیان مرتبط با تابع هدف نداشته و بنابراین به سادگی میتواند در مسائلی که تعیین اطلاعات گرادیان سخت و یا غیر ممکن است، مورد استفاده قرار گیرد. الگوریتم رقابت استعماری مزیتهای قابل توجهی نسبت به سایر الگوریتمهای تکاملی دارد و بنابراین در این مقاله به عنوان الگوریتم پایه در روش پیشنهادی در نظر گرفته شده است. زمان اجرای این الگوریتم به صورت قابل ملاحظهای کمتر از سایر الگوریتمها میباشد. همچنین از این الگوریتم میتوان در فضاهای مسئله ناپیوسته و یا با تغییرات بسیار شدید استفاده کرد. بعلاوه، به جای اینکه در پایان فقط یک جواب برای مسئله ارائه دهد، مجموعهای از راهحلهای بهینه در اختیار طراح قرار میدهد [13].

الگوریتم رقابت استعماری، کاملا مقیاسپذیر بوده و مؤلفههای جدید را میتوان به آن اضافه کرد. بنابراین، در این مقاله ایده مهاجرت به عنوان یک مؤلفه پیشنهادی مورد مطالعه قرار گرفته و با اصلاح و افزودن آن به الگوریتم رقابت استعماری، از یک روش بهبود یافته برای حل مساله پوشش و اتصال در شبکههای حسگر بیسیم گرید سهبعدی استفاده شده است.

نوآوریهای انجام شده در این مقاله بدین شرح است:

· برای اولین بار از الگوریتم رقابت استعماری به عنوان پایه برای حل مسائل پوشش و اتصال در شبکههای حسگر سه بعدی بر مبنای نقاط هدف استفاده شده است.

· ایده مهاجرت برای اولین بار ارائه شده و به عنوان یک مولفه اصلی به الگوریتم رقابت استعماری اضافه شده است.

· فرمولبندی ریاضی هم برای مولفه مهاجرت و هم برای جایگذاری گرهها، ارائه شده است.

در ادامه این مقاله، ابتدا کارهای قبلی انجام گرفته در بخش 2 مورد بررسی قرار خواهند گرفت. در بخش 3 پیشزمینهای از الگوریتم رقابت استعماری شرح داده خواهد شد. سپس در بخش 4 روش پیشنهادی شامل بهبود الگوریتم رقابت استعماری و همچنین فرمولبندی مسئله بیان شده و در قسمت 5 نتایج شبیهسازی و مقایسه کارایی آن با الگوریتمهای دیگر بررسی خواهد شد. نهایتا جمعبندی و نتیجهگیری در بخش 6 ارائه خواهد شد.

2. مرور کارهای انجام گرفته

تا کنون، مسئله شبکه حسگر بیسیم در پژوهشهای زیادی مورد بررسی قرار گرفته است. با توجه به اینکه هر حسگر هزینهای را به سیستم تحمیل میکند، به صورت خاص مهمترین نکته جایگذاری حسگرها در داخل شبکه به گونهای است که با استفاده از کمترین تعداد حسگر، کل نقاط مورد نظر در داخل شبکه پوشش داده شوند. علاوه بر شرط پوشش، مسئله اتصال هم در بیشتر موارد مورد توجه بوده است. در هر پژوهش فرضیات خاصی برای نوع شبکه، ساختار نودها و نحوه ارتباط در نظر گرفته شده است. به عنوان مثال نودها میتوانند همگن یا غیرهمگن باشند و یا اینکه هر نود حسگری میتواند دادههای دیگر نودها را منتقل کند یا نه. بحث تحملپذیری در برابر خرابی و از کار افتادن نودها هم در برخی تحقیقات مورد توجه قرار گرفته شده است.

در [14] همه حسگرها دارای شعاع پوشش همسان در نظر گرفته شده و همچنین مسئله به صورت 1-پوشش و 1-متصل حل شده است؛ بدین معنا که هر نقطه هدف لزوما باید توسط حداقل یک حسگر پوشش داده شده و همچنین هر حسگر حداقل دارای یک مسیر به نود چاهک باشد. همه این شرایط در [9] در نظر گرفته شده است با این تفاوت که در آن چند نود چاهک موجود بوده و حسگرها میتوانند به هر کدام از این چاهکها متصل باشند. در برخی دیگر از پژوهشها شرط پوشش بررسی نشده و صرفا اتصال نودهایی که حسگر در آنها قرار دارد مد نظر بوده است[15][16].

در [17][18] مسئله به صورت k-پوشش و m-متصل حل شده است و همه حسگرها هنوز دارای شعاع پوشش یکسان میباشند در حالیکه در [19] مسئله m- متصل به صورت غیرهمگن حل شده است. نکته شایان توجه این است که همه الگوریتمهای ذکر شده فضای مسئله را به صورت دو بعدی در نظر گرفتهاند. در[14] با استفاده از الگوریتم کلونی مورچگان مسئله جایگذاری حسگرها در یک شبکه حسگر بیسیم سه بعدی حل شده است.

الگوریتمهای تکاملی، دستهای از الگوریتمها هستند که عموما از طبیعت و سیستمهای بیولوژیکی طبیعی الهام گرفتهاند. برخی از این الگوریتمها همچون الگوریتم کلونی زنبورعسل [20] و PSO [21] برای حل مسئله WSN مورد استفاده قرار گرفتهاند. یکی از الگوریتمهای تکاملی جالب توجه که بیشتر برای حل این مسئله به کار گمارده شده است، الگوریتم کلونی مورچگان است. در [22] با استفاده از این الگوریتم، روشی با عنوان EasiDesign برای حل مسائل مربوط به شبکههای گرید ارائه شده است. این رویه در [23] با استفاده از افزایش تعداد مورچگان بهبود یافته و در [24] هم یک روش حریصانه بر مبنای همین الگوریتم برای بهبود کارایی ارائه شده است.

هنگامی که مسئله k-پوشش مورد بررسی قرار میگیرد تلاش داریم تا همه نقاط هدف در شعاع پوشش k حسگر قرار گیرند. اما ممکن است در برخی از قسمتهای شبکه، تعدادی از نقاط هدف توسط بیش از k حسگر پوشش داده شوند. در واقع در این بخشها تعدادی حسگر قرار داده شدهاند که در صورت حذف مشکلی در صحت و کلیت جواب پیش نخواهد آمد. این حسگرها که حسگرهای افزوده نامیده میشوند، موجب تحمیل هزینه غیرضروری و اضافی به سیستم شده و تشخیص و حذف آنها موجب افزایش کارایی الگوریتم خواهد شد. همین مشکل در مورد اتصال حسگرها هم وجود دارد. در [25] راهکاری برای تشخیص و حذف حسگرهای افزوده با استفاده از الگوریتم کلونی مورچگان ارائه شده است.

تا کنون تحقیقات زیادی برای استفاده از روش رقابت استعماری برای حل مسائل پوشش و اتصال در شبکههای حسگر بیسیم انجام نشده است. در [26] با استفاده از الگوریتم رقابت استعماری، یک الگوریتم به نام ICABC برای مسئله 1-پوشش حصارها و 1-متصل نودها در هر حصار پیشنهاد شده است. در [27] نیز با استفاده از همین الگوریتم، رویهای با نام MOICA برای 1-پوشش تمام محیط پیشنهاد شده است. هر دوی این متدها مسائل را در فضای دو بعدی مدلسازی کردهاند. در این مقاله با افزودن ایده مهاجرت به الگوریتم رقابت استعماری و بهبود آن، یک روش جدید برای حل مسئله جایگذاری حسگرها در شبکه حسگر بیسیم سه بعدی ارائه خواهد شد.

3. پیشزمینه: الگوریتم رقابت استعماری

الگوریتم رقابت استعماری [28] یکی از الگوریتمهای تکاملی بوده که از جوامع بشری الهام گرفته و برای حل بسیاری از مسائل بهینهسازی قابل استفاده است. این الگوریتم همانند دیگر الگوریتمهای تکاملی با تعدادی جمعیت اولیه تصادفی، که هر کدام از آنها یک کشور نامیده میشوند، شروع میشود. این کشورها در واقع جوابهای ممکن مسئله میباشند. تعدادی از بهترین عناصر جمعیت به عنوان استعمارگر و باقیمانده جمعیت به عنوان مستعمره در نظر گرفته میشود. مستعمرات با توجه به میزان قدرت استعمارگران، میان آنها تقسیم شده و تشکیل امپراطوریها را میدهند. سپس رقابت استعماری میان امپراطوریها شروع میشود.

هر امپراطوری که نتواند در رقابت استعماری، موفق عمل کرده و بر قدرت خود بیفزاید به تدریج از صحنه رقابت حذف خواهد شد. بنابراین بقای یک امپراطوری وابسته به قدرت آن در جذب مستعمرات امپراطوریهای رقیب و به سیطره در آوردن آنها خواهد بود. در نتیجه در جریان رقابتهای استعماری به تدریج بر قدرت امپراطوریهای بزرگتر افزوده شده و امپراطوریهای ضعیفتر حذف خواهند شد. استعمارگران برای افزایش قدرت مجبور خواهند شد تا مستعمرات خود را نیز پیشرفت دهند. با گذشت زمان مستعمرات از لحاظ قدرت به استعمارگرها نزدیکتر شده و شاهد یک نوع همگرایی خواهیم بود. حد نهایی رقابت استعماری زمانی است که یک امپراطوری واحد با مستعمراتی که از لحاظ موقعیت به خود کشور استعمارگر خیلی نزدیک هستند، باقی بماند.

یکی از مهمترین مراحل رقابت استعماری، حرکت مستعمرهها به سمت استعمارگر است. در واقع سیاست همگونسازی (جذب) با هدف تحلیل فرهنگ و ساختار اجتماعی مستعمرات در فرهنگ حکومت مرکزی انجام میگیرد. کشورهای استعمارگر برای افزایش نفوذ خود، شروع به ایجاد تغییرات در کشورهای مستعمره خود میکنند. با در نظر گرفتن شیوه نمایش یک کشور در حل مسئله بهینهسازی، در حقیقت حکومت مرکزی با اعمال سیاست جذب سعی دارد تا کشور مستعمره را در راستای ابعاد مختلف اجتماعی-سیاسی به خود نزدیک کند. همچنین در طی مراحل رقابت استعماری، هر کدام از کشورهای مستعمره ممکن است دچار انقلاب شوند. انقلاب یک تغییر بنیادی در قدرت یا سازماندهی یک کشور است که در یک بازه کوتاه زمانی اتفاق میافتد. این تغییرات جدای از تغییرات مرحله همگونسازی بوده که توسط استعمارگر اعمال میشوند و به صورت تغییرات تصادفی در موقعیت یک کشور در راستای محورهای سیاسی- اجتماعی مدل میشود. این فرایند قدرت جستجوی الگوریتم را توسعه داده و از همگرا شدن به کمینههای محلی جلوگیری مینماید [29].

سیاست جذب در عین نابودی ساختارهای اجتماعی-سیاسی کشور مستعمره، در بعضی موارد نتایج مثبتی را نیز برای آنها در پی دارد. بدین صورت که در حین حرکت مستعمرات به سمت کشور استعمارگر، ممکن است بعضی از این مستعمرات به موقعیتی بهتر از استعمارگر برسند؛ این اتفاق در طی فرایند انقلاب هم ممکن است رخ دهد. در این حالت، کشور استعمارگر و کشور مستعمره، جای خود را با هم عوض کرده و الگوریتم با کشور استعمارگر در موقعیت جدید ادامه یافته و این بار این کشور استعمارگر جدید است که شروع به اعمال سیاست همگونسازی بر مستعمرات خود میکند.

در حین جابجایی استعمارگران و مستعمراتشان به سمت کمینه سراسری، ممکن است برخی استعمارگران به نقاط مشابهی برسند. اگر فاصله دو استعمارگر از یک حد آستانه کمتر شود، آنگاه با همدیگر ادغام شده و یک امپراطوری جدید را شکل میدهند. همچنین همه مستعمرات دو استعمارگر هم در این امپراطوری جدید حضور خواهند داشت.

هر امپراطوري كه نتواند بر قدرت خود بيفزايد و قدرت رقابت خود را از دست بدهد درجريان رقابتهاي استعماری حذف خواهد شد. اين حذف شدن به صورت تدريجي صورت گرفته بدين معني كه به مرور زمان امپراطوريهای ضعيف مستعمرات خود را از دست داده و امپراطوريهاي قويتر آنها راتصاحب میکنند. در واقع در هر تکرار از الگوریتم، ضعیفترین مستعمره از ضعیفترین امپراطوری توسط سایر امپراطوریها تصرف میشود. استعمارگری که همه مستعمرات خود را از دست بدهد حذف شده و به عنوان مستعمره به بقیه استعمارگران اختصاص مییابد. نهایتا پس از تعداد مناسب تکرار، همه امپراطوريها سقوط كرده و تنها يك امپراطوري باقی میماند. در چنين موقعيتي رقابت استعماری به پايان رسيده واستعمارگر باقیمانده به عنوان جواب نهایی مسئله ارائه میگردد.

4. ایده پیشنهادی

در این مقاله با استفاده از الگوریتم رقابت استعماری، مسئله جایگذاری حسگرها در شبکه حسگر بیسیم سه بعدی با شرایط 1-پوشش و 1-متصل حل شده است. برای رسیدن به نتایج بهتر، بهبودهایی در الگوریتم رقابت استعماری انجام گرفته است. بدین منظور ایده مهاجرت مدلسازی شده و به این الگوریتم اضافه شده است. مهاجرت باعث ایجاد تنوع بیشتر در امپراطوریها شده و از همگرا شدن آنها به بهینه محلی جلوگیری میکند. در ادامه، ابتدا این ایده بررسی شده و سپس فرمولبندی مسئله و الگوریتم پیشنهادی ارائه میشود.

1.4 مهاجرت: بهبود الگوریتم رقابت استعماری

همانطور که قبلا ذکر شد، الگوریتم رقابت استعماری از جوامع انسانی الهام گرفته شده است. از این رو رویدادهایی که در دنیای واقعی در این جوامع رخ میدهد را میتوان به این الگوریتم اضافه نمود و نتایج آن را تحلیل و بررسی نمود. در کارهای انجام شده قبلی اتفاقاتی نظیر انقلاب در یک مستعمره، اتحاد امپراطوریها و سقوط یک امپراطوری بررسی شده است. بدیهی است که هر رویداد میتواند نتایج مثبت و منفی را برای کشورها، تمدنها و دیگر عوامل تاثیرگذار در جوامع انسانی داشته باشد. بنابراین انجام شدن یک رویداد باید تحت شرایط خاص و به صورت حساب شده صورت پذیرد تا اثرات منفی آن کمتر و اثرات مثبت بیشتر شود.

یکی از اتفافاتی که در جوامع بشری بهوفور رخ میدهد اما در الگوریتم رقابت استعماری در نظر گرفته نشده است، مساله مهاجرت از یک سرزمین به سرزمین دیگر است. از نظر تاریخی تاکنون مهاجرتهای زیادی صورت گرفته که بسیاری از آنها مبدا پیدایش تمدنهای بزرگ بشری بودهاند، هر چند که در برخی موارد نتایج منفی به همراه داشته است. در این مقاله رویداد مهاجرت به الگوریتم رقابت استعماری اضافه شده است و نتایج آن در حل مسائل پوشش و اتصال در شبکههای حسگر بیسیم مورد بررسی قرار گرفته شده است.

میدانیم که در الگوریتم رقابت استعماری هر مستعمره در هر لحظه فقط عضو یک امپراطوری است و یا به عبارتی مستعمره یک استعمارگر است. در فاز اولیه امپراطوریها تشکیل میشوند و سپس رقابت بین امپراطوریها برای کسب قدرت بیشتر و تصرف مستعمرات سایر امپراطوریها آغاز میشود. این رقابت به صورت تکراری است که با تعداد دورهای مشخص انجام میگیرد. هر مستعمره در انتهای هر دور، با یک احتمال، میتواند از امپراطوری خود مهاجرت کرده و به یک امپراطوری جدید وارد شود. این احتمال که یک عدد در بازه [0 , 1] است باید در هر دور و برای تمام مستعمرات محاسبه شود. هر مقدار که شرایط یک مستعمره در دورهای قبلی وخیمتر باشد احتمال مهاجرت آن مستعمره افزایش مییابد. در جدول 1 نمادها و تعاریف مورد نیاز برای فرمولبندی و انجام محاسبات نشان داده شده است.

هر کشور یکی از جوابهای مسئله است که با توجه به قدرتش میتواند در یک امپراطوری به عنوان استعمارگر و یا مستعمره حضور داشته باشد. بنابراین هر کشور در هر لحظه میتواند در یکی از این دو وضعیت قرار داشته باشد که این موضوع در رابطه 1 مشخص شده است.

(1)

جدول 1. نمادهای مورد نیاز برای فرمولبندی مهاجرت

نماد	تعریف
Ee	امپراطوری شماره e شامل تعدادی کشور
PiEe	قدرت امپراطوری شماره e در تکرار i
PiniEe	قدرت امپراطوری شماره e در مرحله اولیه تشکیل امپراطوریها
NiEe	تعداد کشورها در امپراطوری شماره e در تکرار i
GiEe	میزان رشدامپراطوری شماره e در تکرار i
CcEe	کشور شماره c درامپراطوری شماره e
PiCcEe	قدرت کشور شماره c درامپراطوری شماره e در تکرار i
PiniCcEe	قدرت کشور شماره c درامپراطوری شماره e در مرحله اولیه تشکیل امپراطوریها
SiCcEe	وضعیت کشور شمارهc درامپراطوری شماره e در تکرار i
NiCcEe	تعداد نودهای حسگر در کشور شمارهc درامپراطوری شماره e در تکرار i
GiCcEe	میزان رشد کشور شماره c درامپراطوری شماره e در تکرار i
HiCcEe	امید به مهاجرت کشور شماره c ازامپراطوری شماره e در تکرار i
IiCcEe	احتمال مهاجرت کشور شماره c ازامپراطوری شماره e در تکرار i

همه کشورها از تعدادی نود حسگر که در محلهای تقاطع شبکه گرید سه بعدی جایگذاری شدهاند، تشکیل یافتهاند. هر اندازه که تعداد این نودهای حسگر در یک کشور کمتر باشد از دیدگاه بهینهسازی آن کشور قدرتمندتر است. از اینرو قدرت هر کشور در تکرار i ام الگوریتم توسط رابطه 2 محاسبه میشود که همواره یک عدد در بازه [0 , 1] است. همچنین قدرت کلی یک امپراطوری از مجموع قدرت تمامی کشورهای تشکیل دهنده آن بهدست میآید که این موضوع برای تکرار i ام الگوریتم در رابطه 3 نشان داده شده است.

(2)

در انتهای هر دور به ترتیب میزان رشد تمام مستعمرات و تمام امپراطوریها بر اساس روابط 4 و 5 محاسبه میشود. این مقدار برابر اختلاف قدرت یک مستعمره یا امپراطوری در تکرار i نسبت به تکرار i-1 است که میتواند یک عدد مثبت، منفی و یا صفر باشد.

(4)

(5)

در ادامه امید به مهاجرت یک مستعمره از یک امپراطوری بر اساس رابطه 6 محاسبه میشود. در این معادله رشد یک امپراطوری با وزن 1- از قدر مطلق رشد یک مستعمره با وزن کم شده و امید به مهاجرت مستعمره بهدست میآید. اگر رشد مستعمره و امپراطوری اعداد منفی شود، امید به مهاجرت برای مستعمره بیشتر میشود و اگر مثبت شود این امید کاهش مییابد. سپس بر اساس رابطه 7 امید به مهاجرت برای تمام مستعمرات هر امپراطوری نرمالیزه میشود.

(6)

(3)

در پایان احتمال مهاجرت هر مستعمره به یک امپراطوری جدید برای دور بعدی بر اساس رابطه 8 محاسبه میشود که برابر میانگین وزنی امید به مهاجرت مستعمره در تکرار جاری و احتمال مهاجرت در تکرارهای قبلی است.

(7)

2.4 مدل شبکه

در این مقاله محیط عملیاتی به صورت سه بعدی و گرید در نظر گرفته شده که تعدادی هدف به صورت تصادفی در تمام فضای محیط پخش میشوند. نودهای حسگر را فقط میتوان در نقاط تقاطع گریدها جایگذاری کرد. هر نقطه هدف باید در شعاع حسی حداقل یک نود حسگر قرار داشته باشد و به عبارتی توسط آن حسگر پوشش داده شود. نودهای حسگر به صورت همگن در نظر گرفته شدهاند، به این صورت که هم شعاع حسی همه نودها و هم شعاع انتشار آنها با هم یکسان است هر چند که این دو شعاع لزوما با هم برابر نیستند.

در شبکه یک چاهک وجود دارد که داده تمام حسگرها، برای آن ارسال میشود. بین هر نود حسگر و چاهک باید حداقل یک مسیر وجود داشته باشد. نقاط تقاطع گریدها به عنوان مکانهای بالقوه برای قرارگیری نودهای حسگر و چاهک معرفی میشوند. هدف تعیین کمترین تعداد نودهای حسگر و مکان آنها در شبکه است به نحوی که هر نقطه هدف حداقل توسط یک نود حسگر پوشش داده شود و هر نود حسگر حداقل با یک مسیر به چاهک متصل باشد. جدولهای 2 و 3 نمادهای استفاده شده در مورد شبکه و همچنین نمادهای مربوط به الگوریتم رقابت استعماری را نشان میدهند.

جدول 2. نمادهای استفاده شده برای فرمولبندی شبکه

(8)

جدول 3. نمادهای استفاده شده برای فرمولبندی ICA

نماد	تعریف
TP	مجموعه نقاط هدف
PP	مجموعه نقاط بالقوه برای جایگذاری نودهای حسگر
tr	شعاع انتشار نودها
sr	شعاع حسی نودها
Cov(TPi)	مجموعه نودهایی که نقطه هدف TPi را پوشش میدهند
	وضعیت پوشش TPi
\|\|x\|\|	تعداد عناصر مجموعهای به نام x
Con(Si)	مجموعه نودهایی که در شعاع انتشار نود بوده و به چاهک نزدیکتر هستند
	وضعیت اتصال نود

نماد	تعریف
E	مجموعه امپراطوریها
CEe	مجموعه کشورهای امپراطوری Ee
COLW	ضعیف ترین مستعمره از ضعیفترین امپراطوری
Run	تعداد نسل در الگوریتم رقابت استعماری
Emp	تعداد امپراطوریها
prev	احتمال انقلاب
IMP-BEST	کشور استعمارگر در قویترین امپراطوری

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)

رایمگ

يقوم نظام رایمگ بتنفيذ جميع عمليات الاستلام والتقييم والحكم والتحرير وتخطيط الصفحة والنشر الإلكتروني للمجلات العلمية.

الروابط

المراكز ذات الصلة

دعامة

الصفحات الرسمية

حقوق هذا الموقع الإلكتروني مملوكة لنظام Rimag Press Management. © 1438-1446

(13)

(14)

بنابراین شرط متصل بودن کل شبکه به صورت معادله 15 خواهد بود.

4.4 الگوریتم پیشنهادی

در این بخش الگوریتم 1 برای حل مسائل پوشش و اتصال در شبکه حسگر بیسیم سهبعدی گرید پیشنهاد شده است. مبنای الگوریتم بر اساس الگوریتم رقابت استعماری است که امکان مهاجرت کشورها در انتهای هر دور به آن اضافه شده است. ورودیهای الگوریتم عبارتند از: مجموعه نقاط هدف (TP)، مجموعه نقاط بالقوه برای قرارگیری حسگرها (PP)، نود چاهک و تعداد اولیه امپراطوریها (emp). همچنین الگوریتم در انتها کشور استعمارگر مربوط به قویترین امپراطوری را به عنوان جواب نهایی مسئله (IMP-BEST) معرفی میکند.

(15)

Algorithm 1: Proposed approach based on improved ICA

Input: TP, PP, sink, emp.

Output: IMP-BEST;

1: generate initial countries which satisfy coverage and connectivity conditions based on Equations 12 and

15 respectively;

2: create emp empires and put them in E;

3: calculate the power of all countries;

4: put emp most powerful countries as imperialists of empires E1 to Eemp;

5: distribute the remaining countries as colonies among E1 to Eemp using Roulette Wheel;

6: for i = 1 to run

7: imperialists converge their colonies with themselves;

8: similar empires are united together;

9: for each colony do

10: revolution with probability prev;

11: end for each

12: for each colony do

13: if the power of the colony is higher than its relevant imperialist then

14: exchange positions of the colony and the imperialist;

15: end if

16: end for each

17: calculate the power of all empires in E, all imperialists and colonies;

18: determine the colony with minimum power from the empire with minimum power as the COLw;

19: recapture COLw and assign it to another empire according to the power of the imperialists using

Roulette Wheel;

//immigration module

20: for e=1 to emp

21: calculate PiEe using Equation 3;

22: calculate GiEe using Equation 5;

23: for c=1 to ||CEe||

24: if SiCcEe = 0 then

25: calculate PiCcEe using Equation 2;

26: calculate GiCcEe using Equation 4;

27: calculate HiCcEe using Equation 6;

28: normalize HiCcEe using Equation 7 as Hi-normCcEe;

29: calculate IiCcEe using Equation 8;

30: remove CC from Ee with probability IiCcEe and add to another empire using Roulette

Wheel;

31: end if

32: end for

33: end for

34: destroy empires with no colony;

35: end for

36: return the imperialist of the most powerful empire as 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. لیست پارامترهای شبیهسازی

پارامتر	مقدار
ابعاد محیط	300 متر در 300 متر
مکان چاهک	تصادفی
تعداد نقاط هدف	200 – 20
تعداد نقاط بالقوه	1000000 – 1000
شعاع ارتباطی نودها	20 متر
شعاع حسی نودها	20 متر
تعداد جمعیت اولیه در روش رقابت استعماری	100

جدول 5. تعداد نودهای حسگر برای پوشش نقاط هدف در شبکهها با ابعاد متفاوت

50×50×50	40×40×40	30×30×30	20×20×20	10×10×10	PP TP
1/19	8/15	7/11	6/9	1/8	20
2/23	4/21	6/15	2/12	4/10	100
4/28	6/25	5/19	1/16	7/13	200

در آزمایشی دیگر به جهت مقایسهپذیری با دو الگوریتم دیگر، تعداد نقاط گرید بهصورت متغیر در نظر گرفته شده بهصورتی که برای هر تعداد نقاط گرید، تعداد نقاط هدف مشخصی در شبکه وجود دارد. به عنوان مثال زمانیکه تعداد نقاط گرید 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. مقایسه زمان اجرای الگوریتم پیشنهادی با سایر الگوریتمها

الگوریتم

NDSBA

ACO-MCC3D

روش پیشنهادی

20×20×20

4897

5011

100×100×100

200

11481

11485

955

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

شارک