پایان نامه بهینه سازی مصرف انرژی در شبکه های حسگر بی سیم توسط الگوریتم کلونی مورچگان

پایان نامه کارشناسی ارشد رشته مهندسی کامپیوتر

گرایش:  نرم افزار

چکیده

ﺍﻣﺮﻭﺯﻩ ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯﺷﺒﮑﻪ­ های ﺳﻨسور ﺑﻲ­ﺳﻴﻢ (Wireless Sensor Network) ﺑﻪ ﺷﮑﻞﮔﺴﺘﺮﺩﻩ­ﺍی  ﺭﻭ ﺑﻪ ااست. ﺑﻪ ﻋﻠﺖ ﺍﺳﺘﻔﺎﺩﻩ ﻏﺎﻟﺐ ﺍﺯ ﺑﺎﻃﺮی ﺑﺮﺍی ﺗﺎﻣﻴﻦ ﺍﻧﺮﮊی ﻣﺼﺮﻓﻲ ﺍﻳﻦ ﺳﻨﺴﻮﺭﻫﺎ ﻭ ﻫﻤﭽﻨﻴﻦ ﻋﺪﻡ ﺩﺳﺘﺮﺳﻲ ﺁﺳﺎﻥ ﺑﻪ ﺳﻨﺴﻮﺭﻫﺎ ﺩﺭ ﺑﺴﻴﺎﺭی ﺍﺯ ﺍﻳﻦ ﮐﺎﺭﺑﺮﺩﻫﺎ، ﻣﻬﻨﺪﺳﺎﻥ ﻭ ﻣﺤﻘﻘﺎﻥ ﺑﻪ ﺳﻤﺖ ﻃﺮﺍﺣﻲ پروتکل­ ﻫﺎی  ﻣﺴﻴﺮﻳﺎﺑﻲ ﺑﺎ خصوصیات انرژی مصرفی کم و افزایش طول عمر شبکه ترغیب شده­اند. ﺍﻳﻦ تحقیق، ﻳﮏ ﭘﺮﻭﺗﮑﻞ ﻣﺴﻴﺮﻳﺎﺑﻲ ﺗﻮﺯﻳﻊ­ﺷﺪﻩ ﺭﺍ ﺑﺮ ﺍﺳﺎﺱ ﺭﻭﺵ الگوریتم کلونی ﻣﻮﺭﭼﻪ­ﻫﺎ ﺩﺭ ﺟﻬﺖ ﺑﻬﺒﻮﺩ ﭘﺎﺭﺍﻣﺘﺮﻫﺎی ﻣﺬﮐﻮﺭ ﺍﺭﺍﺋﻪ می­دﻫﺪ. الگوریتم کلونی مورچگان یک الگوریتم متاهیوریستیک می­باشد که توسط دوریگو و همکارانش برای حل برخی مشکلات ترکیبی بهینه سازی مانندمسئله فروشنده دوره گرد معرفی شد. الگوریتم کلونی مورچگان یکسری ویژگی­هایی از جمله محاسبه توزیعی ، خودسازماندهی و بازخورد مثبت دارد که برای جست­و­جوی مسیر در شبکه­ های ارتباطی کاربرد دارد. 

در نهایت پروژه خود را با زبان قدرتمند متلب پیاده­سازی کرده و شبیه ­سازی­ های خود را ارائه نمودیم. ﻧﺘﺎﻳﺞ ﺁﺯﻣﺎﻳﺸﺎﺕ ﮐﺎﻫﺶﻧﺰﺩﻳﮏ به %۴۰ ﻣﺼﺮﻑ ﺍﻧﺮﮊی ﻭ ﺍﻓﺰﺍﻳﺶ 3ﺑﺮﺍﺑﺮ ﻃﻮﻝ ﻋﻤﺮ ﺷﺒﮑﻪ را نسبت به حالت عادی نشان می­دهد.

کلمات­کلیدی ­:­ شبکه­های­حسگر بیسیم،­الگوریتم کلونی مورچگان، مصرف انرژی ­

فصل اول

کلیات

1مقدمه

امروزه بحث سیستم­های کنترل و نظارت از راه دور یکی از مباحث پر چالش در زمینه علوم الکترونیک کامپیوتر می­باشد، لذا تحقیقات در هر زمانی به دنبال راه حلی می­باشد تا شرایط خاص و­انتظارات مدنظر را پاسخ دهد؛ در شرایط وکیفیت کاری یکسان هر چه نسبت هزینه به کارائی پائینتر باشد، همان قدرمحبوبیت آن شیوه بالاتر خواهد رفت. برای اگاهی از تغییرات محیط اطراف و یا وضعیت هر مجموعه نیازمند یکسری تجهیزاتی هستیم که بعنوان حسگر شناخته می­شوند و اینها تغییرات مدنظر )تغییرات فیزیکی یا شیمیائی) را در قالب یک پاسخ، به منظور اندازه­گیری میزان تغییرات و یا وجود آن، ارائه می­دهند. پس از جمع آوری اطلاعات مورد نیاز می­توان سایر عملیات را بر اساس پاسخ ارائه شده انجام داد. پیشرفت­های اخیر در زمینه الکترونیک و مخابرات بی­ سیم باعث شده بتوانیم گره های حسگر چند کاره، با توان مصرفی پائین و هزینه کم داشته باشیم که از نظر اندازه خیلی کوچک هستند و برا ی مسافت­های کوتاه می­توانند با هم ارتباط برقرارکنند. این گره­های حسگر کوچک طبق نظریه شبکه­های حسگر، دارای تجهیزات حس کردن، پردازش داده­ها و مخابره آنها و همچنین منابع انرژی وداده­محور می باشند. تفاوت اصلی شبکه ­های حسگر با سایر شبکه­ها در ماهیت داده –محور پردازشی بسیار محدود در آنهاست که موجب شده تا روش­های مطرح شده جهت انتقال داده­ها در سایر شبکه­ها و حتی شبکه­هایی که تا حد زیادی ساختاری مشابه شبکه­های حسگر دارند (مانند شبکه­های موردی) ، در این شبکه­ها قابل استفاده نباشند. روند توسعه این شبکه­ها در حدی است که مطمئنا این شبکه­ها در آینده نزدیک، نقش مهمی را در زندگی روزمره ما ایفا خواهند کرد. از کاربرد هایی که در حال حاضر برای شبکه حسگر مطرح می­شود و روز به روز بر تعدادشان افزوده می­شود، می­توان به کاربرد­هایی نظیر عمل ردیابی در محیط­های گسترده جغرافیایی، سیستم­های امنیتی، نظارت بر سازه­های بزرگ، نظارت بر بیماران دارای وضعیت حساس، نظارت بر پارامترهای محیطی در مناطقی که حضور انسان در آنها خطرناک است و بسیاری کاربردهای دیگر اشاره کرد. شبکه­های حسگر در واقع تجمع تعداد زیادی از گره­های حسگرمی­باشند که در محیط پراکنده شده­اند و هر کدام به طور خودمختار و با همکاری سایر گره­ها هدف خاصی را دنبال می­کنند. گره­ها به هم نزدیک هستند و هر گره­ای با گره دیگری می­تواند ارتباط برقرار کند و اطلاعات خود را در اختیار گره دیگری قرار دهد و در نهایت وضعیت محیط تحت نظر، به یک گره مرکزی گزارش می­شود .تکنیک­ها و شیوه­های مورد استفاده در چنین شبکه­های وابستگی شدیدی به ماهیت کاربرد شبکه دارد و ساختارتوپولوژی شبکه، شرایط جوی و محیطی، محدودیتها و ... عوامل موثری در پارامترهای کارایی و هزینه شبکه می­باشند. لذا امروزه در سرتاسر دانشگاه­های معتبر و مراکز تحقیقاتی کامپیوتری، الکترونیکی و بخصوص مخابراتی، شبکه­های حسگربیسیم، یک زمینه تحقیقاتی بسیار جذاب و پرطرفدار محسوب می­شود. تحقیقات و پیشنهادات زیادی در مباحث مختلف ارائه شده است و همچنان حجم تحقیقات در این زمینه سیر صعودی دارد .هدف اصلی تمامی این تلاش­ها و ارائه راهکارها، داشتن سیستمی با شیوه­های کنترلی ساده، آسان و با هزینه پائین می­باشد که در نهایت با پاسخگویی به نیازمندیهای ما بتواند درمقابل محدودیتها (پهنای باند، انرژی، دخالت­های محیطی، فیدینگ و...) ایستادگی کند و شرایط کلی را طبق خواسته­ها و تمایلات ما (انتقال حجم زیاد اطلاعات پر محتوا، بقاء­پذیری و طول عمر بالا، هزینه پائین را فراهم سازد. لذا محققین جنبه­های مختلف را تحلیل و بررسی می­نمایند و سعی می­کنند ایده­های بهینه و کارا را استخراج کنند. این ایده­ها می­توانند از محیط وحش اطرافمان الهام گرفته شده باشد و با استفاده از قوانین ریاضی و نظریات تئوری و آماری می­توان آنها را تحلیل نمود. به دلایل ذکر شده در بالا، بحث شبکه­ های حسگر در حال حاضر یکی از مباحث داغ در محافل علمی است و روز به روز بر نیز در IEEE تعداد مقاله­هایی که در این مورد منتشر می­شوند افزوده می­گردد. در سالهای اخیر نیز چند کنفرانس معتبر در همین زمینه برگزار شده است. یکی از چالش­های مطرح در زمینه شبکه­های حسگر، نحوه مسیریابی و انتقال اطلاعات جمع­آوری شده، در گره­های این شبکه­هاست. از آنجایی که این شبکه­ها از لحاظ میزان انرژی قابل دسترسی و منابع پردازشی موجود، محدودیت دارند، نمی­توان از روش­های مطرح شده برای سایر شبکه­ها، در شبکه­های حسگر استفاده کرد.

الگوریتم کلونی مورچگان یک الگوریتم متاهیوریستیک می­باشد که توسط دوریگو و همکارانش برای حل برخی مشکلات ترکیبی بهینه­سازی مانند مسئله فروشنده دوره­گرد معرفی شد. الگوریتم کلونی مورچگان یکسری ویژگی­هایی از جمله محاسبه توزیعی، خودسازماندهی و بازخورد مثبت دارد که برای جست­و­جوی مسیر در شبکه­های ارتباطی کاربرد دارد.]6[

1-2 بیان موضوع

شبکه­های حسگر بیسیم از مجموعه­ای از گره­های حسگر کوچک می­باشند که توانایی نظارت و حس­کردن محیط پیرامون خود و ارسال داده­های حس شده را به یک ایستگاه اصلی (چاهک) دارند [3].

همانطور که در[4]  گفته شده، پروتکل­های مسیریابی در شبکه­های حسگر بیسیم می­توانند از دید ساختار شبکه به سه دسته مسیریابی تخت، سلسه مراتبی و مبتنی بر مکان تقسیم شوند. در مدل تخت همه­ی گره­ها نقش یا کار مساوی دارند، اما در مدل سلسله مراتبی گره­ها نقش­های مختلفی را در شبکه بازی می­کنند. در مدل مبتنی بر مکان نیز از موقعیت گره­های سنسور برای مسیردهی داده در شبکه استفاده می­شود. پروتکل هایSPIN [1]، سیل آسا، شایعه پراکنی، مستقیم و همگی در دسته­ی مسیریابی تخت قرار دارند. پروتکل های LEACH [2]در دسته­ی سلسله مراتبی و پروتکل­های  [3]GEARو [4]GAFنیز در دسته­ی مبتنی بر مکان قرار می­گیرند.

در[5] بیان شده که حسگر­ها با منابع محدود انرژی از جمله باتری­ها به تامین انرژی خود می­پردازند که به پردازش، برقراری ارتباط و ذخیره­ی اطلاعات منجر می­شود. با توجه به شرایط محیطی استقرار این شبکه­ها،

تعویض باتری­های گره های حسگر غیرممکن و بسیار پرهزینه است. چالش اصلی [5] WSNمحدودیت انرژی موجود در گره­ها می­باشد که بقای شبکه را تحت تاثیر خود قرار داده و مانع پیشرفت آن شده است.

در [6] زندگی کلونی شامل توده­ای از موجودات که با هم زندگی می­کنند؛ می­باشد. تعداد زیادی عنصر یا موجود زنده با هم زندگی می­کنند و کلیه­ی رفتارهای آن­ها منظم و در جهت بقای کلونی است. روش کلونی مورچگان برگرفته از رفتار واقعی مورچگان است. مورچه­ها حشراتی اجتماعی هستند که در کلونی­ها زندگی می­کنند و رفتار آن­ها بیشتر در جهت حفظ و بقای کلونی است. مورچه­ها برای یافتن غذا و

مسیریابی خود از ترشح ماده­ای به نام فرومون استفاده می­کنند و مسیر درست و برگشت خود را از طریق شاخک­ها که قادر به تشخیص فرومون به جامانده می­باشد، انتخاب می­کنند.

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

فاکتور انرژی در WSN مسئله­ ی مهمی است که مقالات گوناگون با بررسی جنبه­های گوناگون در زمینه­هایی چون، الگوریتم استعماری[2]، مسئله­ی کوله پشتی [3]، الگوریتم درخت پوشا[10] و مانند آن به بهینه­سازی آن پرداخته­اند. از آنجایی که یکی از مهم­ترین کاربردهای الگوریتم کلونی مورچگان پیدا کردن کوتاه­ترین و بهینه­ترین مسیر است، لذا تحقیق حاضر با استفاده از آن به شناسایی روشی موثر برای کاهش مصرف انرژی در WSN می­پردازد.

1-3 سابقه و ضرورت انجام تحقیق

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

در [2] از روش خوشه­ بندی با استفاده از الگوریتم استعماری استفاده شده است. در چند مرحله گره­های سر خوشه را براساس پارامترهایی نظیر میزان انرژی و پراکندگی گره­ها شناسایی می­نماید. خوشه­هایی متوازن با سر خوشه­هایی با انرژی بالاتر نسبت به گره­های معمولی و در نتیجه طول عمر و کارایی بیشتر ایجاد می­شود.

در [7] از الگوریتم کلونی مورچگان بر پایه­ی مسئله­ی کوله­پشتی برای گسترش حسگر­ها استفاده شده است. گسترش حسگر­ها یکی از مهم­ترین مسایل در WSNمی­باشد، زیرا یک طرح گسترش بهینه می­تواند هزینه­ها را کم کند، توانایی مسیریابی WSN، کیفیت مشاهده و نظارت در WSN را با افزایش مناطق تحت پوشش بالا ببرد. در طرح ارایه شده عمر شبکه طولانی می­شود .

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

در[9] از الگوریتم کلونی مورچگان تجمع داده DAACA (data aggregation ant colony algorithms) برای تجمیع داده­ها استفاده شده است. این الگوریتم شامل سه فاز، مقداردهی اولیه، انتفال بسته­ها و شامل عملیاتی روی فرومون می­باشد. در فاز انتفال، انرژی باقی مانده هر گره و مقدار فرومون همسایه تخمین زده می­شود تا از طریق آن بتوان هاپ بعدی را انتحاب کرد. مرحله­ی بعدی تنظیم فرومون می­باشد که شامل مزایایی در زمان تبخیر آن است. این مرحله شامل 4 استراتژی می­باشد که طول عمر شبکه را بالا می­برد. تحقیقات انجام شده روی تعداد زیادی از گر­ها، DAACA ، کارایی و طول عمر بیشتر، پیچیدگی محاسبه کمتر و نرخ انتقال موفق­تری در یک هاپ، نسبت به سایر الگوریتم­ها دارد.

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

1-4 خلاصه فصل

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

 Energy Efficiency in Wireless Sensor Networks With Ant colony Algorithm

Abstract

 Nowadays The use of wireless sensor (Wireless Sensor Network) is increasing.for the reason of using battery for energy consumption  and  in some applications, sensors are not reachable,researchers  think to design routing protocol with low energy consumption and increseing duration life of network.

 In this paper, a distributed routing protocol based on ant colony algorithm to improve the above parameters is offerded.

Ant colony optimization algorithms, is a methaheuristic algorithm,which is introduced  by Dorigo and colleagues to solve some combinatorial optimization problems like salesman . Ant colony optimization algorithms has some attributes like to calculate the number of features including a distributed calculation, self-organizing and positive feedback that use to search path in communication networks.

Finally, we implement our project with powerful language, MATLAB. Results show,decrease in energy consumption up to 40%  and increase the lifetime of the network.

Keywords: wireless sensor networks, Ant colony optimization algorithms, energy efficiency