Improved routing for load balancing in wireless sensor networks on the Internet of things, based on multiple ant colony algorithm
Subject Areas :
Farhang Padidaran Moghaddam
1
(Esfarayen University of Technology)
Hamid Maghsoudi
2
(Eshragh Institute of Higher Education)
Keywords: Routing, load balancing, Internet of things and ant colony algorithm,
Abstract :
An important issue in dynamic computer networks such as Internet networks, where the cost of connections varies continuously, is to create a traffic load balancing and increase the transmission speed of packets in the network, so that data packets are using paths with minimal congestion, as a result, one of the main approaches to solve routing problems and load balancing algorithms is based on ant - based algorithms using a novel approach based on optimization of multiple ant colony optimization, the purpose of this research is to present an appropriate routing algorithm in order to shorten and improve the path due to end - to - end delay parameters, packet loss rate, bandwidth and energy consumption rate, to reach a sense of data on the Internet systems. this method has been implemented in MATLAB software and shows the results of the improvement experiments in the mentioned parameters.
[1] صادق سبزی، روش جدید مسیریابی با استفاده از الگوریتم بهینه‌سازی ذرات در شبکههای حسگر بی‌سیم، اولین همایش داخلی مهندسی کامپیوتر و فناوری اطلاعات، بروجن، دانشگاه آزاد اسلامی واحد بروجن، ۱۳۹۳.
[2] میثم پناهی, و علی یاراحمدی، شبکه‌ی حسگر به یسیم در اینترنت اشیاء و عصر رایانش ابری، سومین همایش ملی مهندسی رایانه و مدیریت فناوری اطلاعات، تهران، شرکت علم و طلوع فرزین، ۱۳۹۵.
[3] N. Kushalnagar, G. Montenegro, & C. Schumacher, IPv6 over low-power wireless personal area networks (6LoWPANs): overview, assumptions, problem statement, and goals, 2007.
[4] J. V. Sobral, J. J. Rodrigues, R. A. Rabêlo, J. Al-Muhtadi, & V. Korotaev, Routing protocols for low power and lossy networks in internet of things applications. Sensors, 19(9), 2144, 2019.
[5] O. Said, Analysis, design and simulation of Internet of Things routing algorithm based on ant colony optimization. International Journal of Communication Systems, 30(8), e3174, 2017.
[6] سید مهدی دادگر ، علی برومند نیا و سمیه فرهنگ ادیب، چالش های موجود در اینترنت اشیاء و راه‌های مقابله با آن دررسیدن به یک شهر هوشمند، کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات، بابل، موسسه علمی تحقیقاتی کومه علم آوران دانش، ۱۳۹۵.
[7] S. Randhawa, & S. Jain, Data aggregation in wireless sensor networks: Previous research, current status and future directions. Wireless Personal Communications, 97(3), 3355-3425, 2017.
[8] T. Baker, M. Asim, H. Tawfik, B. Aldawsari, & R. Buyya, An energy-aware service composition algorithm for multiple cloud-based IoT applications. Journal of Network and Computer Applications, 89, 96-108, 2017.
[9] S. B. Shah, Z. Chen, F. Yin, I. U. Khan, & N. Ahmad, Energy and interoperable aware routing for throughput optimization in clustered IoT-wireless sensor networks. Future Generation Computer Systems, 81, 372-381, 2018.
[10] F. Al-Turjman, Cognitive routing protocol for disaster-inspired internet of things. Future Generation Computer Systems, 92, 1103-1115, 2019.
[11] O. Gaddour, & A. Koubâa, RPL in a nutshell: A survey. Computer Networks, 56(14), 3163-3178, 2012.
[12] H. S. Kim, H. Kim, J. Paek, & S. Bahk, Load balancing under heavy traffic in RPL routing protocol for low power and lossy networks. IEEE Transactions on Mobile Computing, 16(4), 964-979, 2016.
[13] S. Hamrioui, C. A. M. Hamrioui, J. Lioret, P. & Lorenz, Smart and self-organised routing algorithm for efficient IoT communications in smart cities. IET Wireless Sensor Systems, 8(6), 305-312, 2018.
[14] S. Banerjee , D. Wu , X. Lin , X. Zhang , T. Abdelzaher , S. Avestimehr , V. Bahl, S. Basagni , D. Blough , R.B. R , M. Buddhikot , Final report from the NSF Work- shop on Future Directions in Wireless Networking, pp. 1025-1037, 2014.
[15] D. Thomas, O. Deblecker, & C. S. Ioakimidis, Optimal operation of an energy management system for a grid-connected smart building considering photovoltaics’ uncertainty and stochastic electric vehicles’ driving schedule. Applied Energy, 210, 1188-1206, 2018.
[16] V. C. Gungor, D. Sahin, T. Kocak, S. Ergut, C. Buccella, C. Cecati, & G. P. Hancke, G. P. A survey on smart grid potential applications and communication requirements. IEEE Transactions on industrial informatics, 9(1), 28-42, 2012.
دو فصلنامه علمي فناوري اطلاعات و ارتباطات ایران | سال چهاردهم، شمارههای 51 و 52 ، بهار و تابستان 1401 صص: 255_270 |
|
مسیریابی بهبودیافته برای توازن بار در شبکه حسگر بی‌سیم در بستر اینترنت اشیا بر پایه الگوریتم کلونی مورچگان چندگانه
فرهنگ پدیداران مقدم* حمید مقصودی**
*استادیار گروه کامپیوتر ، مجتمع فنی مهندسی اسفراین
**دانش آموخته کارشناسی ارشد، موسسه آموزش عالی اشراق
تاریخ دریافت: 03/04/1400 تاریخ پذیرش: 14/06/1400
نوع مقاله: پژوهشی
چکیده
یکی از مسائل مهم در شبکههای کامپیوتری پویا از قبیل شبکههای اینترنت اشیاء که در آن هزینه اتصالات به‌طور پی‌درپی تغییر میکند، ایجاد توازن بار ترافیکی و افزایش سرعت انتقال بستهها در شبکه است. بطوریکه بسته‌های داده از مسیرهایی با حداقل تراکم به مقصد برسند؛ درنتیجه یکی از روشهای اصلی برای حل مسائل مسیریابی و توازن بار استفاده از الگوریتمهای مبتنی بر مورچه است.با استفاده از روشی جدید مبتنی بر بهینه‌سازی کلونی مورچه چندگانه 1 ، هدف این پژوهش ارائه یک الگوریتم مسیریابی مناسب در جهت کوتاه کردن و بهبود بخشیدن مسیر با توجه به پارامترهای تأخیر انتها به انتها2، نرخ اتلاف بسته3،پهنای باند4 و نرخ مصرف انرژی است تا دادهی حس شده در سیستمهای اینترنت اشیاء به مقصد برسد. این روش در نرمافزار متلب پیاده‌سازی شده است . نتایج حاصل از آزمایش‌ها، بهبود در پارامترهای مذکور را نشان میدهد.
واژگان کلیدی: مسیریابی، توازن بار، اینترنت اشيا و الگوریتم کلونی مورچه چندگانه
[1] Multiple Ant Colony Optimization
[2] End to End delay
[3] Packet lost
[4] Bandwidth
1. مقدمه
با ظهور اینترنت انسانها توانایی ایجاد برقراری ارتباط در سراسر مرزهای جغرافیایی را پیداکرده است. اینترنت اشیاء فناوری نوظهوری است که در آن حس‌گرها و دستگاه‌های کوچک تعبیه‌شده در اشیاء
نویسنده مسئول: فرهنگ پدیداران مقدم padidaran@esfarayen.ac.ir
قرار میگیرند و باعث ایجاد ارتباط اشیاء با یکدیگر و انسان میشود
اشیاء قادر به دریافت و تبدیل اطلاعات از محیط اطراف خود هستند. پیشرفت در سنجش، محاسبات و ارتباطات بهبود قابل‌توجهی در ارتباط بلادرنگ و تصمیمگیری به ارمغان آورده است. ازاین‌رو اینترنت اشیاء قصد دارد تا اینترنت را در همه‌جا حاضر و فراگیر کند.
در طول دهه اخیر شبکه حسگر بی‌سیم در بستر اینترنت اشیا به‌عنوان یک‌راه حل مناسب برای مجموعه گسترده‌ای از برنامه‌های کاربردی اعم از نظارت بر محیط‌زیست، اتوماسیون منزل و امنیت شبکه هوشمند به‌کاررفته است]1[. ازآنجاکه تهدیدهای امنیتی زیادی بر روی شبکه حسگر بی‌سیم وجود دارد، تحقیقات و اقدامات متقابل مختلفی بر روی مسئله امنیت انجام‌شده است]2[.
یکی از مسائل مهم در شبکههای کامپیوتری پویا از قبیل شبکههای اینترنت اشیاء که در آن هزینه اتصالات به‌طور پی‌درپی تغییر میکند، ایجاد توازن بار ترافیکی و سرعت زیاد انتقال بستهها در شبکه است، بطوریکه بسته‌های داده از مسیرهایی با حداقل تراکم به مقصد برسند، با توجه به مطالعات انجام شده، یکی از روشهای اصلی برای حل مسائل مسیریابی و توازن بار استفاده از الگوریتمهای مبتنی بر مورچه است. با استفاده از روش جدیدی مبتنی بر بهینه‌سازی کلونی مورچگان چندگانه ، میتوان قابیلت متعادل کردن بار ترافیک به‌طور کارآمد را در شبکه ایجاد نمود، بطوریکه ترافیک داده‌ها در هر گام زمانی مسیر بهبودیافته را برای رسیدن به مقصد در نظر بگیرند. در ادامه، نتایج شبیه سازی موید این مهم خواهد بود.
در سیستم های مبتنی اینترنت اشیاء جهت بهبود درروند مسیریابی اخیراً از الگوریتم بهبود مسیر کلونی مورچگان]4 و3[ استفاده شده است تا کوتاهترین و بهترین مسیر را حتی در نواحی همپوشانی بیابد]5[ ارتباط این مورچهها با یکدیگر از طریق ماده شیمیایی فرومون است. زمانی که مورچه از یک مسیر حرکت میکند بر روی زمین فرومون ترشح میکند و باعث میشود که مورچههای بعدی به دنبال او حرکت کنند. فرومون ها دارای غلظت هستند که طی واحد زمان تبخیر میشوند، پس هر چه غلظت فرومون بیشتر باشد مورچه می‌فهمد که این مسیر جدیدتر است. در الگوریتم کلونی مورچگان ایجاد مسیرها توسط مجموعه‌ای از مورچههای مصنوعی انجام میگردد. درواقع هدف یکپارچگی در سیستم های اینترنت اشیاء ارتباط چندین شئ با یکدیگر تحت نظارت یک سیستم خودمختار واحد است. این سیستم شامل مانیتورینگ و پایش از راه دور، نگهداری و عملیات مدیریتی نیز هست که داده‌ها را جمع‌آوری کرده و از طریق شبکه ارسال کند. درنتیجه چالش مسیریابی در این نوع از شبکه‌ها مشهود است و محققان همواره در تلاش هستند که مسیر انتقال دیتا را بهبود بخشیده و بیان کنند که چگونه ویژگی‌های سیستم های مختلف ممکن است مانع انتقال دیتا مابین نودها گردد.
هدف اوليه مسیریابی کلونی مورچگان بهبود مسیر با توجه به پارامترهای سرویس است که دیتا را تحت چندين مسیر از شبكه توزيع کرده و در حقيقت ترافيك را يكنواخت مینماید. يكنواخت كردن بار ترافيك شبكه باعث میشود كه كل پهناي باند موردنیاز از كل ظرفيت شبكه تجاوز نكند و درواقع هدف، مسیریابی بسته‌هاي داده است، بطوريكه تابع هزينه را حداقل كند. انتخاب مناسبترین الگوریتم کلونی مورچگان عملی بسیار سخت و پیچیده‌ای است، لذا در این مقاله الگوریتمی ارائه خواهد شد که میزان استفاده از الگوریتم کلونی مورچگان را کنترل کرده و راه‌حلی را مابین نواحی همپوشانی تعیین نماید. در کلونی مورچگان چندگانه ، بسته‌هاي داده با حداقل تأخير و کیفیت سرویس بالاتر در شبكه انتقال پیداکرده و ميانگين زمان تأخير براي اندازه‌گیری كارايي الگوريتم به كار گرفته میشود.
1. پیشینه پژوهش
در سیستمهای مبتنی بر اینترنت اشیاء جهت انتقال داده بین وسایل ناهمگن، به پروتکل مسیریابی نیاز است که دیتای حس شده از دستگاه‌ها را با کوتاهترین مسیر و حداقل مصرف انرژی به مقصد برساند. در ]2[ ، جهت بهبود درروند مسیریابی، از پروتکل مسیریابی برای شبکه های با انرژی محدود و نویزآلود (RPL1) (مانند شبکه متشکل از اشیاء متصل به هم در IoT) استفاده‌شده است که ازنظر پارامترهای مختلف کیفیت سرویس از قبیل تأخیر، مصرف انرژی، کاهش بیت‌های سرآیند و پهنای باند مورد تست و بررسی قرارگرفته و با تحلیل نتایج شبیهسازی ثابت نموده است که الگوریتم پیشنهادی کیفیت سرویس را بهبود داده است. در ]6[ یک پروتکل مسیریابی تحت عنوان تحلیل و شبیهسازی الگوریتم مسیریابی بر پایه کلونی مورچگان جهت بهبود کیفیت سرویس‌ها و مسیریابی معرفی شده است و در آن انواع پارامترهای کیفیت سرویس اعم از تأخیر انتها به انتها، نرخ اتلاف بسته، پهنای باند، کاهش بیت‌های سرآیند بسته، مصرف انرژی و توان عملیاتی را مورد تحلیل و ارزیابی قرارگرفته است. پس از شبیهسازی بر روی آن و کسب نتایج حاصل از شبیهسازی، کلیه مؤلفه‌ها را با الگوریتمهای پیشین مقایسه کرده و در تحلیل یافته ها به این نتیجه رسیدند که در عملکرد کلیه مؤلفه‌های کیفیت سرویس کارایی بهتری صورت گرفته است و الگوریتم پیشنهادی توانسته است به هدف ارائه روندی در جهت بهبود در فرایند مسیریابی در محیط پویا و داینامیک اینترنت اشیاء نائل گردد. در ]7[ یک پروتکل مسیریابی برای مسافت‌های طولانی در راستای بهبود کارایی الگوریتم مسیریابی ارائه شده است که در این طرح پیشنهادی مسیر مورد نظر به دو بخش فعال داخلی با مسافت زیاد و بخش واکنش‌پذیر داخلی با مسافت کوتاه، تقسیم میگردد. در این روش از پروتکل AODV2 بهره گرفته شده است که پروتکل مسیریابی در مسیرهای داخلی است و از خرابی و شکست بسته ها جلوگیری میکند. محیط تست این پروتکل، محدود بوده و قادر به تولید نتایج صحیح نبوده است. همچنین این پروتکل مسیریابی، مشکلاتی با سیستمهای داینامیک و پویا و ناهمگون از قبیل سیستمهای اینترنت اشیاء دارد. یکي از ضعفهاي پروتکل مسیریابي AODV این است که در فرایند کشف مسیر تعداد زیادي پیامهاي کنترلي در شبکه همهپخشي ميشود و این فرایند باعث ميشود مسیرهاي غیرقابل استفاده بسیاري بین گره منبع و مقصد پیدا شود؛ همچنین باعث افزایش سربار عملیاتی و پهناي باند مصرفي ميشود.
در ]8[ الگوریتمی در رابطه با عوامل چندگانه3 از قبیل عامل سراسری4، عامل محلی5، عامل مانیتورینگ و پایش و عامل دوجانبه6 باهدف بهبود در الگوریتمهای مسیریابی با استفاده از کلونی مورچگان در نواحی همپوشانی معرفی شده است. در این الگوریتم ناحیه تحت پوشش اینترنت اشیاء، بسته به نوع شبکه، به نواحی مختلفی تقسیم‌بندی گردید و هر زیر شبکه الگوریتم کلونی مربوط به خود را اجرا می نماید. در ]9[ الگوریتمی با محوریت توپولوژی بی‌قاعده اینترنت اشیاء باهدف کاهش سیگنال‌های طوفان فرا پخشی7 و درنهایت بهبود درروند مسیریابی با روش RPL و جستجوی مسیر و کاهش تعداد نودها در شبکه تحت کنترل ارائه شده است. در این روش با ویژگی‌های ارسال تصادفی و کوتاه بودن چرخه حیات بر مشکل تعداد زیاد نودهای شبکه غلبه کرده است. نتایج شبیهسازی نشان میدهد که زمان ایجاد مسیر با افزایش نودها در مسیر جستجو به طرز قابل‌توجهی کاهش پیدا کرده است. در ]10[ متدی با عنوان الگوریتم جستجوی بر اساس مدلRPL معرفی شده است. این تکنیک جهت تعیین مسیر بهبودیافته در سیستمهای اینترنت اشیاء و مدل تصمیمگیری مسیریابی جهت ارزیابی نودهای اینترنت اشیاء، از توازن پارامترهای چندگانه استفاده میکند. سیستمهای اینترنت اشیاء از شبکههای مختلف تشکیل‌شده است که میتوان برای مسیریابی در آنها از RPL استفاده نمود. از طرفی تفکیک نودها، بسته های بیشتری را در شبکه ایجاد میکند که باعث سربار در شبکه میشود. Gaddour و همكاران در ]11[، از الگوريتم مورچگان براي انتقال داده بين پردازنده‌های مختلف در سیستم اینترنت اشیا استفاده شده است. كارها توسط مورچهها بين گره‌هاي يك گراف كه پردازنده‌های سيستم میباشند جابه‌جا میشوند. قاعدهی اين جابجايي بر مبناي این الگوريتم است: ابتدا هر مورچه متوسط بار خود را محاسبه كرده و سپس خطاي محلي را نيز بر اساس متوسط بار خود و مورچههای قبلي تعيين میکند. با استفاده از فاكتور تحمل‌پذیری خطا و ميزان ردپاهاي به جاگذاشته شده توسط ساير مورچهها، احتمال ماندن يا ترك نمودن آن پردازنده را به دست آورده و اقدام به مهاجرت میکند. در جدول 1 الگوریتمهای توازن بار با یکدیگر مقایسه شده‌اند. با توجه به مطالعات انجام شده تاکنون روش هایی برای مدیریت تحرک گره ها ارائه شده است اما به لحاظ گم شدن بسته ها، نرخ خوبی ندارند. لذا در این پژوهش روشی برای مدیریت مناسب تر تحرک گره ها از نظر پارامترهای قابلیت اطمینان، زمان پاسخ، تاخیر ، توان عملیاتی و دسترسی پذیری با الگوریتم کلونی مورچه چندگانه ارایه شده است.
[1] Routing Protocol for Low-Power and Lossy Networks
[2] Ad hoc on Demand Distance Vector
[3] Multi Agent
[4] Global Agent
[5] Local Agent
[6] Dual Agent
[7] Broadcast Storm
جدول 1. مقایسه الگوریتمهای توازن بار
معایب | مزایا | روش کار | نام الگوریتم | ردیف |
برای منابع محدود کارایی ندارد | با افزایش منابع ناهمگون کارایی وتوان عملیاتی بالا می‌رود | بر اساس گروه‌بندی گره‌های شبيه به هم | الگوریتم توازن بار خوشه‌بندی فعال | 1 |
بار یک منبع درنظرگرفته نمی‌شود. | برآورده کردن معيار بهره‌برداری از منابع، سربار، توان عملياتی، زمان پاسخ و کارایی | بر اساس زمان اتمام حداقل براي تمام وظایف | الگوریتم توازن بار Min-Min | 2 |
کارهای کوچک برای مدت طولانی منتظر میمانند. | کاهش زمان اجرای کلی برنامه | بر اساس min-minکارمی‌کند با این تفاوت که کارهای با مدت‌زمان اجرای طولانی انتخاب میشوند | الگوریتم توازن بار Min-Max | 3 |
برای یک کار پیچیده نیاز به انجام محاسبات فراوان است | افزایش استفاده موثر از منابع و بهره وری منابع | بر پایه تقسیم وظایف به زیر وظایف و تخصیص زیر وظایف | الگوریتم توازن بار دومرحله‌ای OLB + LBMM | 4 |
برای منابع ناهمگون کارنمی‌کند | کاهش مدت‌زمان اجرای وظایف در ابر، افزایش کارایی استفاده از منابع | بر پایه تقسیم وظایف | توازن باربر پایه الگوریتم زمان‌بندی ترکیبیDCBT | 5 |
زمان کلی را کاهش نمیدهد | توازن بار بدون سربار اضافی و کم | تخصیص کارها به منبعی که بار آن کم است صورت میگیرد | الگوریتم توازن بار VM-assign | 6 |
مصرف زیاد انرژی | به‌طور مؤثر بار سيستم را کاهش میدهد، هيچ سربار ارتباطی هنگام ورود کارها رخ نمیدهد و زمان پاسخ واقعی را افزایش نمیدهد. | تخصیص کارها به پردازنده‌های بیکار برای کاهش طول صف | الگوریتم توازن بار Queue-Idle-Join | 7 |
در برخی شرایط، زمان پاسخ طولانی است | برای حل مسائل بهینه‌سازی ترکیبی استفاده میشود | استفاده از رد و پای مورچه برای انتقال وظایف بین پردازنده‌ها | الگوریتم کلونی مورچهها | 8 |
اولویت کاربر را در نظر نمی گیرد | توازن بار را با کاهش مدت‌زمان اجرا انجام میدهد | انتخاب حریصانه وظایف و زمان‌بندی و توازن آنها بر روی منابع | الگوریتم توازن بار(ژنتیک) JLGA | 9 |
اولویت کاربر را در نظر نمی گیرد | توازن بار و کاهش مدت‌زمان اجرای کارها | انتخاب کارها بر پایه شایستگی | توازن باربر پایه الگوریتم ژنتیک | 11 |
تحمل‌پذیری خطا را در نظر نمی گیرد | کارایی و زمان پاسخ، توان عملياتی و بهره‌برداری از منابع | توازن باربر پایه جدول اطلاعات ماشین‌های مجازی | توازن بار مرکزي اینترنت اشیا | 12
|
2. مراحل انجام طرح پیشنهادی
در طرح پیشنهادی از الگوریتم کلونی مورچگان چندگانه برای یافتن مناسبترین مسیر در درخت شبکه اینترنت اشیا استفاده میشود. هدف از این پروژه، کاهش نرخ اتلاف بسته و تأخیر و بهبود قابلیت اطمینان و توازن بار در سیستمهای اینترنت اشیا است. همانطور که در شکل 1 نشان داده شده است، ابتدا نحوه استقرار گره ها در شبکه اینترنت اشیا، موقعیت آنها و تنظیم پارامترهای اولیه الگوریتم پیشنهادی مانند تعداد تکرار، تعداد گره ها و... انجام می شود]12[. سپس توزیع اطلاعات و داده ها بین گره ها در شبکه اینترنت اشیا صورت می گیرد. در ادامه، اطلاعات توسط گره متقاضی در شبکه اینترنت اشیا درخواست می شود و درخت بر اساس گره ها تشکیل می شود.
شکل1 . فلوچارت گام‌های طرح پیشنهادی |
انتقال دیتا برای ارتباطات در تعامل انسان با انسان، انسان با ماشین و یا ماشین با ماشین و همینطور زمان که نقش بسیار مهمی را در انتقال دیتا ایفا می کند، حایز اهمیت است ، لذا دیتای مورد نظر می بایست بگونه ای مسیر یابی گردد که کمترین و یا کوتاهترین مسیر را برای رسیدن به مقصد داشته باشد. از اینرو پروتکلهای مسیر یابی مختلفی جهت انتقال دیتا به کار گماشته شده اند.
در الگوریتم کلونی مورچگان ایجاد مسیرها توسط مجموعه ای از مورچه های مصنوعی انجام می گردد. در واقع هدف یکپارچگی در سیستم های اینترنت اشیاء، ارتباط چندین شئ با یکدیگر تحت نظارت یک سیستم خود مختار واحد است. این سیستمها شامل مانیتورینگ و پایش از راه دور، نگهداری و عملیات مدیریتی نیز میباشند که داده ها را جمع آوری کرده و از طریق شبکه ارسال مینماید.
در این مقاله از الگوریتم کلونی مورچگان چندگانه برای یافتن مناسبترین مسیر در درخت بر اساس توابع تعریف شده استفاده میشود ]13[ و درنهایت، بهترین مسیر(راه حل یافته شده توسط الگوریتم کلونی مورچگان چندگانه) برای ارسال اطلاعات در بستر اینترنت اشیا به عنوان جواب بهینه نمایش داده می شود.
1_3 استقرار و تولید جمعیت
شکل 2 جستجوي محلی مورچهها و نحوه حرکت آنها را نشان میدهد. درروش پیشنهادی، ساختار محاسبه مقادیر اطلاعات اکتشافی به‌صورت شکل 2-ب در نظر گرفته‌شده است. در روشهای مرسوم مانند شکل 2-الف، جستجو در چهار جهت برای گرهای که مورچه در آن قرار دارد انجام میپذیرد . در روش پیشنهادی، در هشت جهت (افقی ، عمودی و قطری) براي گرهی حاوی مورچه محاسبه میگردد. گسترش محدوده جستجو باعث کشف بیشترین نوسان ظرفیت مابین گره‌هاي در سیستم اینترنت اشیا میگردد و جزو نوآوری های تحقیق است که تاکنون اجرا نشده است.
(الف)
(ب)
شکل 2. حرکت مورچه (الف) ساختار الگوریتمهای قبلی (ب) ساختار پیشنهادی در این تحقیق
اطلاعات مربوط به جستجو در مورد گره (i,j) توسط رابطه (1) محاسبه می شود ]13[
(1) |
|
(2) |
|
(3) |
|
(4) |
|
در معادلهی (4) pijk احتمالی است که مورچهی k حرکت از گرهی i به گرهی j را انتخاب کند و ما آن را مصالحه ای بین قابلیت دید (که میگوید گره‌ها با LET بیشتر باید انتخاب شوند) و شدت دنبالهی واقعی (که میگوید اگر بر روی اتصال (Vi,Vj) مورچههای زیادی عبور کنند آنگاه این اتصال برای استفاده شدن بسیار مناسبتر است) است.
τij(t)میزان دنبالهی فرومون یال (Vi,Vj) و LETij تابع قابلیت دید گره ی Vi به Vj است. این تابع گره‌هایی با LET بیشتر را انتخاب مینماید.
α و β پارامترهایی هستند که نسبت اهمیت دنباله در برابر قابلیت دید را کنترل میکنند. Ni مجموعهی همسایگان گره ی Vi در درخت تشکیل‌شده است که گره در گام بعدی میتواند توسط k مورچه انتخاب شود.
ü اطلاعات مسیر توسط مورچههای عبوری جمع‌آوری میشود و گره ریشه بعد از رسیدن مورچهی k ام شروع به تحلیل داده میکند. اطلاعات جمع‌آوری‌شده توسط مورچهها این‌گونه تعریف میشوند[12].
که V0 گره ی ریشه و Sk گره ی مقصد است. دنبالهی گسستهی گره‌ها {V0,V1,V2,…,Vk} مسیر را تشکیل میدهند. ضمناً برای ارزیابی مسیر که در بالا اشاره شد، مقدار RET را به شکل زیر تعریف میکنیم:
پس از محاسبه LET، میتوان از روش مدت‌زمان پایداری مسیر (RET) برای یافتن بیشترین طول عمر نسبت به مسیرهای دیگر با بالاترین قابلیت اطمینان در انتقال داده استفاده کرد. مدت‌زمان پایداری مسیر (RET) بر اساس حداقل LET، بیان میشود[16].
(5) | RET=min{LET1,LET2,LET3,……….,LETn} |
برای محاسبه RET، نیازمند ثبت اطلاعاتی از قبیل سرعت و جهت در پیام پاسخ مسیر هستیم. در فاز کشف مسیر پیام درخواست مسیر، به همسایگان ارسال میشود. پیام توسط همسایگان که در نقش اشیای واسط هستند، گام‌به‌گام ارسال‌شده تا اینکه به نظیر منبع موردنظر تحویل داده شود. پس از یافتن نظیر منبع، پیام (پاسخ مسیر) به نظیر مقصد از مسیر تحویلی (برعکس) ارسال میگردد. موقعیت و جهت در پیام پاسخ اضافه‌شده تا بتوان به محاسبه مدت‌زمان پایداری پیوند بین دو نظیر پرداخته شود. در ابتدا مقدار (LET=0) است؛ و هر نظیر بر اساس اطلاعات موقعیت و جهت ثبت‌شده در پیام، به محاسبه LET با نظیر بعدی (همسایه) میپردازد و مقدار LET را ثبت میگردد؛ و در ثبت مقدارLET، کمترین مقدار در هر گام در نظر گرفته میشود و این امر باعث به‌روز شدن مقدار LET میگردد.
باید توجه داشت که در هر گام اطلاعات LET در جدول مسیریابی هر نظیر ثبت میشود. این امر باعث میگردد تا اگر نظیر منبع (مشابه) در آینده جستجو گردد اشیای واسط، پیام پاسخ و اطلاعات LET را از جدول مسیریابی خود تولید کنند. سرانجام این فرآیند تا زمانی ادامه دارد تا پیام پاسخ که حاوی حداقل LET محاسبه‌شده از کل مسیر است به نظیر مقصد برسد؛ و درنهایت مسیری را با بیشترین مقدار RET، انتخاب گردد.
ü مطابق با تابع ارزیابی، بهترین مسیر از بین تمام مورچهها در تکرار اول توسط ایستگاه پایه به دست میآید. سپس ایستگاه پایه پیامی را برای اطلاع گره‌ها در بهترین مسیر جهت به‌روزرسانی فرومون مطابق با معادلات زیر پخش میکند[16].
(6) |
|
مقدار | پارامتر |
1000 × 1000 m | ابعاد شبکه |
60 | حداکثر تعداد بستهها |
20-40-60-80-100 | تعداد گره‌ها |
802.11bit | استاندارد IEEE |
10000bit | حجم ترافیک شبکه |
250 m | دامنه رادیویی انتقال بستهها |
20 m/s | حداکثر سرعت سرویس‌گیرنده شبکه |
0.4% | فاکتور هموار کردن بستهها |
500s | مدت‌زمان شبیهسازی |
پارامترها و مقادیر آنها به‌شدت به همگرایی بهتر بستگی دارند. پارامترهای الگوریتم کلونی مورچه بهبودیافته در جدول (3) نشان داده‌شده است. این پارامترها اساسا بر طبق ]14[ در نظر گرفته شده اند.
جدول 3. پارامتر الگوریتم کلونی مورچهها
پارامتر | مقدار | ||
تعداد مورچه | 31 | ||
| 1 | ||
| 2 | ||
| 1/0 | ||
حداکثر تکرار | 200 |
(7) |
|
(8) |
|
(9) |
|
(10) |
|
روش | n = 5 | n = 10 | n = 20 |
PSO | 98562/10 | 6752/1 | 28952/0 |
TSM | 2234/13 | 5968/3 | 36961/0 |
روش پیشنهادی | 68594/15 | 89854/4 | 42658/0 |
همچنین در شکل (10) میزان بسته‌های ازدست‌رفته در سه پروتکل PSO، TSM و روش پیشنهادی با افزایش تعداد گره‌ها از 10 گره به 50 گره مقایسه شده است.
شکل 10. مقایسه میزان بسته‌های ازدست‌رفته در اثر افزایش تعداد گره‌ها
4. نتیجه گیری
در این مقاله یک چارچوب جدید براي مسیریابی در اینترنت اشیاء با آگاهی از کیفیت در شبکههای تنیده3 ارائه شده است. تلاش روش پیشنهادي بر این بود تا یک ترکیب مسیر بهینه را پیدا کند که از میزان شایستگی خوبی برخوردار باشد.. استفاده از الگوریتم کلونی مورچه چندگانه زمان لازم براي مسیریابی در اینترنت اشیاء را کاهش میدهد. با مقایسه الگوریتمهای هم‌راستا ، به این نتیجه رسیدیم که زمان پاسخ الگوریتم کلونی مورچه چندگانه در مقایسه با الگوریتمهای ازدحام ذرات و جستجوی ممنوعه کمتر است. همچنین با توجه به نمودارهاي همگرایی، براي الگوریتم کلونی مورچگان چندگانه به ازای تعداد مختلف مسیرها ، آزمایش جواب واحدي به دست داده است. بنابراین همگرایی الگوریتم کلونی مورچگان چندگانه خوب بوده و میتوان نتیجه گرفت که جواب به‌دست‌آمده از الگوریتم پیشنهادی، نزدیک جواب بهینه میتواند باشد.
مراجع
[1] صادق سبزی، روش جدید مسیریابی با استفاده از الگوریتم بهینه‌سازی ذرات در شبکههای حسگر بی‌سیم، اولین همایش داخلی مهندسی کامپیوتر و فناوری اطلاعات، بروجن، دانشگاه آزاد اسلامی واحد بروجن، ۱۳۹۳.
[2] میثم پناهی, و علی یاراحمدی، شبکه‌ی حسگر به یسیم در اینترنت اشیاء و عصر رایانش ابری، سومین همایش ملی مهندسی رایانه و مدیریت فناوری اطلاعات، تهران، شرکت علم و طلوع فرزین، ۱۳۹۵.
[3] N. Kushalnagar, G. Montenegro, & C. Schumacher, IPv6 over low-power wireless personal area networks (6LoWPANs): overview, assumptions, problem statement, and goals, 2007.
[4] J. V. Sobral, J. J. Rodrigues, R. A. Rabêlo, J. Al-Muhtadi, & V. Korotaev, Routing protocols for low power and lossy networks in internet of things applications. Sensors, 19(9), 2144, 2019.
[5] O. Said, Analysis, design and simulation of Internet of Things routing algorithm based on ant colony optimization. International Journal of Communication Systems, 30(8), e3174, 2017.
[6] سید مهدی دادگر ، علی برومند نیا و سمیه فرهنگ ادیب، چالش های موجود در اینترنت اشیاء و راه‌های مقابله با آن دررسیدن به یک شهر هوشمند، کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات، بابل، موسسه علمی تحقیقاتی کومه علم آوران دانش، ۱۳۹۵.
[1] S. Randhawa, & S. Jain, Data aggregation in wireless sensor networks: Previous research, current status and future directions. Wireless Personal Communications, 97(3), 3355-3425, 2017.
[2] T. Baker, M. Asim, H. Tawfik, B. Aldawsari, & R. Buyya, An energy-aware service composition algorithm for multiple cloud-based IoT applications. Journal of Network and Computer Applications, 89, 96-108, 2017.
[3] S. B. Shah, Z. Chen, F. Yin, I. U. Khan, & N. Ahmad, Energy and interoperable aware routing for throughput optimization in clustered IoT-wireless sensor networks. Future Generation Computer Systems, 81, 372-381, 2018.
[4] F. Al-Turjman, Cognitive routing protocol for disaster-inspired internet of things. Future Generation Computer Systems, 92, 1103-1115, 2019.
[5] O. Gaddour, & A. Koubâa, RPL in a nutshell: A survey. Computer Networks, 56(14), 3163-3178, 2012.
[6] H. S. Kim, H. Kim, J. Paek, & S. Bahk, Load balancing under heavy traffic in RPL routing protocol for low power and lossy networks. IEEE Transactions on Mobile Computing, 16(4), 964-979, 2016.
[7] S. Hamrioui, C. A. M. Hamrioui, J. Lioret, P. & Lorenz, Smart and self-organised routing algorithm for efficient IoT communications in smart cities. IET Wireless Sensor Systems, 8(6), 305-312, 2018.
[8] S. Banerjee , D. Wu , X. Lin , X. Zhang , T. Abdelzaher , S. Avestimehr , V. Bahl, S. Basagni , D. Blough , R.B. R , M. Buddhikot , Final report from the NSF Work- shop on Future Directions in Wireless Networking, pp. 1025-1037, 2014.
[9] D. Thomas, O. Deblecker, & C. S. Ioakimidis, Optimal operation of an energy management system for a grid-connected smart building considering photovoltaics’ uncertainty and stochastic electric vehicles’ driving schedule. Applied Energy, 210, 1188-1206, 2018.
[10] V. C. Gungor, D. Sahin, T. Kocak, S. Ergut, C. Buccella, C. Cecati, & G. P. Hancke, G. P. A survey on smart grid potential applications and communication requirements. IEEE Transactions on industrial informatics, 9(1), 28-42, 2012.
[1] Particle Swarm Optimization
[2] Tabu Searching -Memetic-based Algorithm
[3] Mesh Network
Improved routing for load balancing in wireless sensor networks on the Internet of things, based on multiple ant colony algorithm
Abstract:
An important issue in dynamic computer networks such as Internet networks, where the cost of connections varies continuously, is to create a traffic load balancing and increase the transmission speed of packets in the network, so that data packets are using paths with minimal congestion, as a result, one of the main approaches to solve routing problems and load balancing algorithms is based on ant - based algorithms using a novel approach based on optimization of multiple ant colony optimization, the purpose of this research is to present an appropriate routing algorithm in order to shorten and improve the path due to end - to - end delay parameters, packet loss rate, bandwidth and energy consumption rate, to reach a sense of data on the Internet systems. this method has been implemented in MATLAB software and shows the results of the improvement experiments in the mentioned parameters.
Keywords: Routing, load balancing, Internet of things and ant colony algorithm
Rimag
Links
Related Centers
Technical Support
Official pages
The rights to this website are owned by the Raimag Press Management System.
Copyright © 2017-2024