فایل بهینه سازی مصرف انرژی در شبکه های حسگر بیسیم توسط الگوریتم کلونی مورچگان
دسته بندي :
کالاهای دیجیتال »
رشته کامپیوتر و IT (آموزش_و_پژوهش)
این پایان نامه در قالب فرمت word قابل ویرایش ، آماده پرینت و ارائه به عنوان پروژه پایانی میباشد.
فهرست مطالب
مقدمه 1
کلیات 2
1-1مقدمه 2
1-2 بیان موضوع 4
1-3 سابقه و ضرورت انجام تحقیق 6
1-4 خلاصه فصل 7
فصل دوم 8
مباحث عمومی شبکههای حسگر بیسیم و الگوریتم کلونی مورچگان 8
1-2معرفی شبکههای حسگر بیسیم 8
2-2 معماری حسگر 9
2-3 کاربرد 9
2-4 اجزای سختافزاری شبکههای حسگر 11
2-5 روشهای انتشار اطلاعات در شبكههای حسگر بیسیم 12
2-5-1 روش همه پخشی 12
2-5-2 روش شایعه پراكنی 12
2-5-3 روش SPIN1 13
2-5-4 روش پخش مستقیم 13
2-5-5 روش مسیریابی جغرافیایی 13
2-5-6 روش انتشار بیرون دهنده 14
2-5-7 روش انتشار جذب یك مرحلهای 14
2-5-8 روش LEACH 14
2-5-9 روش EDDD 14
2-6 محدودیتهای سختافزاری شبکههای حسگر بیسیم 15
2-7 انرژی مصرفی در شبکههای حسگر بیسیم 15
2-8 الگوریتم کلونی مورچگان 16
2-9 ویژگیهای الگوریتم کلونی مورچگان 17
2-10 کاربردهای الگوریتم کلونی مورچگان 18
2-11-1 مسیریابی شبکههای کامپیوتری با استفاده از ACO 18
2-12 فلوچارت کلونی مورچگان 19
2-13 خلاصه فصل 20
فصل سوم 21
مروری بر کارهای گذشته 21
3-1 بهینهسازی مصرف انرژی در شبکههای حسگر بیسیم با استفاده از الگوریتم ژنتیک 21
3-2 بهینهسازی انرژی با روشی مبتنی بر بازی اقلیت و اتوماتای یادگیری سلول 21
3-3 بهینهسازی انرژی در ارتباطات در شبکههای حسگر بیسیم 21
3-4 بهینهسازی انرژی با تحویل چند داده 22
3-5 بهینهسازی انرژی با جلوگیری از چاههای انرژی و توزیع غیر یکنواخت گرهها 22
3-6 الگوریتم مسیریابی برای شبکههای حسگر بیسیم 22
3-7 مسیریابی قابل اعتماد و کارآمد در شبکههای حسگر بیسیم 23
3-8 بیوگرافی از مسیریابی ترکیبی الهام گرفته از الگوریتم بهینهسازی باکتری 23
3-9 بهینهسازی انرژی با استفاده از تکنیک تجمیع دادهها 23
3-10 مصرف قدرت و افزایش طول عمر شبکه در حین ارتباط گرههای حسگر در wsn 24
3-11 اعتبار و کیفیت سرویس با استفاده از الگوریتم کلونی مورچگان 24
3-12 بهینهسازی انرژی بر اساس تاریخچهای از پروتکل کنترل پنجره 24
3-13 برای به دست آوردن بهترین ارتباط در شبکههای حسگر بیسیم با استفاده از الگوریتم ژنتیک و مقایسه و تجزیه و تحلیل 25
3-14 بهینهسازی انرژی بر اساس مکانیزم مسیریابی برمبنای اتصال و مکان 25
3-15 بهینهسازی انرژی با استفاده از سیستم فازی 26
3-16 بهینهسازی انرژی با استفاده از شمای حفظ مکان مبدا 26
3-17 خلاصه فصل 26
فصل چهارم 27
آزمايشها و ارزيابي نتايج 27
4-2اطلاعات مربوط به شبکه 27
4-3 شرايط الگوريتم 28
4-4پروتکل پيشنهادي 28
4-4-1ارسال مجدد antها به درون شبکه 29
4-4-2انتخابPROXY براي نودهاي ايزوله 29
4-5متوسط مصرف انرژي 30
4-6متوسط تعداد نودهاي زنده 30
4-7طول عمر شبکه 31
4-8مجموعه آزمايشي و محيط پياده سازي و اجرا 32
4-9خلاصه فصل 32
بحث و نتیجهگیری 33
6-1 نتیجهگیری 33
6-2 پیشنهادات 34
منابع 35
فهرست جدول
جدول 4-1پارامترهاي پياده-سازي................................................................................................................................39
فهرست شکل
شکل 2-2 روش همه پخشی 12
شکل 2-3روش شایعه پراکنی 13
شکل 2-4 حرکت مورچگان در انتخاب کوتاهترین مسیر 17
شکل 2-6 فلوچارت کلونی مورچگان 20
شکل 4-1 نودهاي وکيل 30
فهرست نمودار
نمودار 4-1 درصد متوسط انرژی مصرف هر نود 30
نمودار 4-2 متوسط نودهاي زنده 31
نمودار 4-3متوسط طول عمر شبکه 31
چکیده
ﺍﻣــﺮﻭﺯﻩ ﺍﺳــﺘﻔﺎﺩﻩ ﺍﺯﺷــﺒﮑﻪ¬های ﺳﻨسور ﺑــﻲ¬ﺳــﻴﻢ (Wireless Sensor Network) ﺑﻪ ﺷﮑﻞﮔﺴﺘﺮﺩﻩ¬ﺍی ﺭﻭ ﺑﻪ ااست. ﺑﻪ ﻋﻠﺖ ﺍﺳﺘﻔﺎﺩﻩ ﻏﺎﻟﺐ ﺍﺯ ﺑﺎﻃﺮی ﺑﺮﺍی ﺗﺎﻣﻴﻦ ﺍﻧﺮﮊی ﻣﺼﺮﻓﻲ ﺍﻳﻦ ﺳﻨﺴﻮﺭﻫﺎ ﻭ ﻫﻤﭽﻨــﻴﻦ ﻋــﺪﻡ ﺩﺳﺘﺮﺳــﻲ ﺁﺳــﺎﻥ ﺑــﻪ ﺳﻨﺴــﻮﺭﻫﺎ ﺩﺭ ﺑﺴــﻴﺎﺭی ﺍﺯ ﺍﻳــﻦ ﮐﺎﺭﺑﺮﺩﻫﺎ، ﻣﻬﻨﺪﺳﺎﻥ ﻭ ﻣﺤﻘﻘﺎﻥ ﺑﻪ ﺳﻤﺖ ﻃﺮﺍﺣﻲ پروتکل¬ﻫﺎی ﻣﺴـﻴﺮﻳﺎﺑﻲ ﺑﺎ خصوصیات انرژی مصرفی کم و افزایش طول عمر شبکه ترغیب شده¬اند. ﺍﻳﻦ تحقیق، ﻳﮏ ﭘﺮﻭﺗﮑـﻞ ﻣﺴـﻴﺮﻳﺎﺑﻲ ﺗﻮﺯﻳـﻊ¬ﺷـﺪﻩ ﺭﺍ ﺑـﺮ ﺍﺳﺎﺱ ﺭﻭﺵ الگوریتم کلونی ﻣﻮﺭﭼﻪ¬ﻫﺎ ﺩﺭ ﺟﻬﺖ ﺑﻬﺒﻮﺩ ﭘﺎﺭﺍﻣﺘﺮﻫﺎی ﻣﺬﮐﻮﺭ ﺍﺭﺍﺋﻪ می¬دﻫﺪ. الگوریتم کلونی مورچگان یک الگوریتم متاهیوریستیک می¬باشد که توسط دوریگو و همکارانش برای حل برخی مشکلات ترکیبی بهینه سازی مانندمسئله فروشنده دوره گرد معرفی شد. الگوریتم کلونی مورچگان یکسری ویژگی¬هایی از جمله محاسبه توزیعی ، خودسازماندهی و بازخورد مثبت دارد که برای جست¬و-جوی مسیر در شبکه¬های ارتباطی کاربرد دارد.
در نهایت پروژه خود را با زبان قدرتمند متلب پیاده¬سازی کرده و شبیه¬سازی¬های خود را ارائه نمودیم. ﻧﺘﺎﻳﺞ ﺁﺯﻣﺎﻳﺸﺎﺕ ﮐﺎﻫﺶﻧﺰﺩﻳﮏ به %۴۰ ﻣﺼﺮﻑ ﺍﻧﺮﮊی ﻭ ﺍﻓﺰﺍﻳﺶ 3ﺑﺮﺍﺑﺮ ﻃﻮﻝ ﻋﻤﺮ ﺷﺒﮑﻪ را نسبت به حالت عادی نشان می¬دهد.
کلمات¬کلیدی ¬:¬ شبکه¬های¬حسگر بیسیم،¬الگوریتم کلونی مورچگان، مصرف انرژی ¬
فصل اول
کلیات
1-1مقدمه
امروزه بحث سيستم¬هاي كنترل و نظارت از راه دور يكي از مباحث پر چالش در زمينه علوم الكترونيك كامپيوتر می¬باشد، لذا تحقيقات در هر زماني به دنبال راه حلي می¬باشد تا شرايط خاص و¬انتظارات مدنظر را پاسخ دهد؛ در شرايط وكيفيت كاري يكسان هر چه نسبت هزينه به كارائي پائينتر باشد، همان قدرمحبوبيت آن شيوه بالاتر خواهد رفت. براي اگاهي از تغييرات محيط اطراف و يا وضعيت هر مجموعه نيازمند يكسري تجهيزاتي هستيم كه بعنوان حسگر شناخته می¬شوند و اينها تغييرات مدنظر )تغييرات فيزيكي يا شيميائي) را در قالب يك پاسخ، به منظور اندازه¬گيري ميزان تغييرات و يا وجود آن، ارائه مي¬دهند. پس از جمع آوري اطلاعات مورد نياز مي¬توان ساير عمليات را بر اساس پاسخ ارائه شده انجام داد. پيشرفت¬هاي اخير در زمينه الكترونيك و مخابرات بی¬ سيم باعث شده بتوانيم گره هاي حسگر چند كاره، با توان مصرفي پائين و هزينه كم داشته باشيم كه از نظر اندازه خيلي كوچك هستند و برا ي مسافت¬هاي كوتاه می¬توانند با هم ارتباط برقراركنند. اين گره¬هاي حسگر كوچك طبق نظريه شبكه¬هاي حسگر، داراي تجهيزات حس كردن، پردازش داده¬ها و مخابره آنها و همچنين منابع انرژي وداده¬محور مي باشند. تفاوت اصلي شبکه¬هاي حسگر با ساير شبكه¬ها در ماهيت داده –محور پردازشي بسيار محدود در آنهاست كه موجب شده تا روش¬هاي مطرح شده جهت انتقال داده¬ها در ساير شبكه¬ها و حتي شبكه-هايي كه تا حد زيادي ساختاري مشابه شبكه¬هاي حسگر دارند (مانند شبكه¬هاي موردي) ، در اين شبكه¬ها قابل استفاده نباشند. روند توسعه اين شبكه¬ها در حدي است كه مطمئنا اين شبكه¬ها در آينده نزديك، نقش مهمي را در زندگي روزمره ما ايفا خواهند كرد. از كاربرد هايي كه در حال حاضر براي شبكه حسگر مطرح مي¬شود و روز به روز بر تعدادشان افزوده می¬شود، مي¬توان به كاربرد¬هايي نظير عمل رديابي در محيط¬هاي گسترده جغرافيايي، سيستم¬هاي امنيتي، نظارت بر سازه¬هاي بزرگ، نظارت بر بيماران داراي وضعيت حساس، نظارت بر پارامترهاي محيطي در مناطقي كه حضور انسان در آنها خطرناك است و بسياري كاربردهاي ديگر اشاره كرد. شبكه¬هاي حسگر در واقع تجمع تعداد زيادي از گره¬هاي حسگرمی¬باشند كه در محيط پراكنده شده¬اند و هر كدام به طور خودمختار و با همكاري ساير گره¬ها هدف خاصي را دنبال مي¬كنند. گره¬ها به هم نزديك هستند و هر گره¬اي با گره ديگري می¬تواند ارتباط برقرار كند و اطلاعات خود را در اختيار گره ديگري قرار دهد و در نهايت وضعيت محيط تحت نظر، به يك گره مركزي گزارش می¬شود .تكنيک-ها و شيوه¬هاي مورد استفاده در چنين شبكه¬هاي وابستگي شديدي به ماهيت كاربرد شبكه دارد و ساختارتوپولوژي شبكه، شرايط جوي و محيطی، محدوديتها و ... عوامل موثري در پارامترهاي كارايي و هزينه شبكه مي¬باشند. لذا امروزه در سرتاسر دانشگاه¬هاي معتبر و مراكز تحقيقاتي كامپيوتري، الكترونيكي و بخصوص مخابراتي، شبكه¬هاي حسگربيسيم، يك زمينه تحقيقاتي بسيار جذاب و پرطرفدار محسوب مي¬شود. تحقيقات و پيشنهادات زيادي در مباحث مختلف ارائه شده است و همچنان حجم تحقيقات در اين زمينه سير صعودي دارد .هدف اصلي تمامي اين تلاش¬ها و ارائه راهكارها، داشتن سيستمي با شيوه¬هاي كنترلي ساده، آسان و با هزينه پائين مي¬باشد كه در نهايت با پاسخگويي به نيازمنديهاي ما بتواند درمقابل محدوديتها (پهناي باند، انرژي، دخالت¬هاي محيطي، فيدينگ و...) ايستادگي كند و شرايط كلي را طبق خواسته¬ها و تمايلات ما (انتقال حجم زياد اطلاعات پر محتوا، بقاء¬پذيري و طول عمر بالا، هزينه پائين را فراهم سازد. لذا محققين جنبه¬های مختلف را تحليل و بررسي مي¬نمايند و سعي مي¬كنند ايده¬هاي بهينه و كارا را استخراج كنند. اين ايده¬ها مي¬توانند از محيط وحش اطرافمان الهام گرفته شده باشد و با استفاده از قوانين رياضي و نظريات تئوري و آماري مي¬توان آنها را تحليل نمود. به دلايل ذكر شده در بالا، بحث شبکه¬هاي حسگر در حال حاضر يكي از مباحث داغ در محافل علمي است و روز به روز بر نيز در IEEE تعداد مقاله¬هايي كه در اين مورد منتشر مي¬شوند افزوده مي-گردد. در سالهاي اخير نيز چند كنفرانس معتبر در همين زمينه برگزار شده است. يكي از چالش¬هاي مطرح در زمينه شبكه¬هاي حسگر، نحوه مسيريابي و انتقال اطلاعات جمع¬آوري شده، در گره¬هاي اين شبكه¬هاست. از آنجايي كه اين شبكه¬ها از لحاظ ميزان انرژي قابل دسترسي و منابع پردازشي موجود، محدوديت دارند، نمي¬توان از روش¬هاي مطرح شده براي ساير شبكه¬ها، در شبكه¬هاي حسگر استفاده كرد.
الگوریتم کلونی مورچگان یک الگوریتم متاهیوریستیک می¬باشد که توسط دوریگو و همکارانش برای حل برخی مشکلات ترکیبی بهینه¬سازی مانند مسئله فروشنده دوره¬گرد معرفی شد. الگوریتم کلونی مورچگان یکسری ویژگی¬هایی از جمله محاسبه توزیعی، خودسازماندهی و بازخورد مثبت دارد که برای جست¬و-جوی مسیر در شبکه¬های ارتباطی کاربرد دارد.]6[
1-2 بیان موضوع
شبکه¬هاي حسگر بيسيم از مجموعه¬اي از گره¬هاي حسگر کوچک مي-باشند که توانايي نظارت و حس¬کردن محيط پيرامون خود و ارسال داده¬هاي حس شده را به يک ايستگاه اصلي (چاهک) دارند [3].
همانطور که در[4] گفته شده، پروتکل¬های مسیریابی در شبکه-های حسگر بیسیم می¬توانند از دید ساختار شبکه به سه دسته مسیریابی تخت، سلسه مراتبی و مبتنی بر مکان تقسیم شوند. در مدل تخت همه¬ی گره¬ها نقش یا کار مساوی دارند، اما در مدل سلسله مراتبی گره¬ها نقش¬های مختلفی را در شبکه بازی می¬کنند. در مدل مبتنی بر مکان نیز از موقعیت گره¬های سنسور برای مسیردهی داده در شبکه استفاده می¬شود. پروتکل هایSPIN ، سیل آسا، شایعه پراکنی، مستقیم و همگی در دسته¬ی مسیریابی تخت قرار دارند. پروتکل های LEACH در دسته¬ی سلسله مراتبی و پروتکل¬های GEARو GAFنیز در دسته¬ی مبتنی بر مکان قرار می¬گیرند.
در[5] بیان شده که حسگر¬ها با منابع محدود انرژي از جمله باتري¬ها به تامين انرژي خود مي¬پردازند که به پردازش، برقراري ارتباط و ذخيره¬ي اطلاعات منجر مي¬شود. با توجه به شرايط محيطي استقرار اين شبکه¬ها،
تعويض باتري¬هاي گره¬هاي حسگر غيرممکن و بسيار پرهزینه است. چالش اصلي WSNمحدوديت انرژي موجود در گره¬ها مي¬باشد که بقاي شبکه را تحت تاثير خود قرار داده و مانع پيشرفت آن شده است.