فصل اول:کلیات تحقیق
۱-1. شرح مساله………………………………………………………………………………………………………….5
1-1-1. تشریح ابعاد………………………………………………………………………………………………………………………..5
1-1-2. حدود مساله………………………………………………………………………………………………………………………..5
1-1-3. معرفی دقیق مسأله………………………………………………………………………………………………………………..5
1-1-4. بیان جنبههای مجهول و مبهم و متغیرهای مربوط به پرسشهای تحقیق……………………………………………..6
1-1-5. منظور تحقیق………………………………………………………………………………………………………………………7
۱-2. اهداف………………………………………………………………………………………………………………8
۱-3. سوالات تحقیق……………………………………………………………………………………………………8
۱-4. جنبه نوآوری و جدید بودن تحقیق…………………………………………………………………………..8
۱-5. روش کار…………………………………………………………………………………………………………..9
1-6. فرضیات…………………………………………………………………………………………………………..11
1-7. ساختار پایان نامه………………………………………………………………………………………………..11
فصل دوم:ادبیات تحقیق
2-1. معرفی شبکه های حسگر بیسیم……………………………………………………………………………..13
2-2. تاریخچه شبکه های حسگر…………………………………………………………………………………..14
2-3. ساختار هر گره حسگر…………………………………………………………………………………………16
2-3-1. اجزاء درونی یک گره حسگر………………………………………………………………………………………………17
2-3-2. محدودیت های سخت افزاری یک گره حسگر………………………………………………………………………..18
2-4. پشته پروتکلی……………………………………………………………………………………………………20
2-5. مزایای شبکه های حسگر بیسیم……………………………………………………………………………..21
2-6. کاربردهای شبکه های حسگر بیسیم……………………………………………………………………….22
2-7. طراحی شبکه های حسگر بی سیم………………………………………………………………………….26
2-8 . طبقه بندی تکنیک های خوشه بندی………………………………………………………………………30
2-8-1. مدل شبکه………………………………………………………………………………………………………………………..30
2-8-2. اهداف خوشه بندی……………………………………………………………………………………………………………34
2-8-3. طبقه بندی علمی ویژگی های خوشه بندی………………………………………………………………………………37
2-9. الگوریتم ژنتیک………………………………………………………………………………………………..41
2-9-1. پیش زمینه ی بیولوژیکی ژن ها و کروموزوم ها………………………………………………………………………..41
2-9-2. تولید سلول های جدید………………………………………………………………………………………………………..42
2-9- 3. توضیحات پایه………………………………………………………………………………………………………………….42
2-9-4 . فضای جستجو………………………………………………………………………………………………………………….43
2-9-5 . عملگر های الگوریتم ژنتیک……………………………………………………………………………………………….43
2-9-5-1.کددهی………………………………………………………………………………………………………………………..44
2-9-5-2 . بررسی نحوه اعمال عملگرها در انواع کددهی……………………………………………………………………..46
2-10.کلونی مورچگان………………………………………………………………………………………………48
فصل سوم:پیشینه ی تحقیق
3-1. الگوریتم های خوشه بندی برای شبکه ی گیرنده ی بیسیم…………………………………………52
3-1-1. الگوریتم های زمان همگرایی متغیر………………………………………………………………………………………52
3-1-2. الگوریتم های زمان همگرایی ثابت……………………………………………………………………………………….63
3-1-3 . خوشه بندی با GA……………………………………………………………………………………………………………78
3-1-3-1. نمایش مسئله………………………………………………………………………………………………………………78
3-1-3-2. ارزیابی سازگاری………………………………………………………………………………………………………..79
3-1-3-3 . پنجره ی مقیاس گذاری……………………………………………………………………………………………….80
3-2. نتیجه گیری………………………………………………………………………………………………………81
فصل چهارم: روش کار و شرح روش پیشنهادی
4-1.صورت مساله…………………………………………………………………………………………………….83
4-2.فرضیات……………………………………………………………………………………………………………83
4-3. انتخاب سر خوشه با الگوریتم ژنتیک………………………………………………………………………87
4-4.خوشه بندی با ACO……………………………………………………………………………………………89
4-4-1. شبه کد ACO………………………………………………………………………………………………….90
4-4-2. عمل ACO…………………………………………………………………………………………………….91
فصل پنجم: شبیه سازی و نتایج
5-1.مقدار دهی اولیه………………………………………………………………………………………………….94
5-2.ماتریس ها…………………………………………………………………………………………………………94
5-3.شکل دهی کروموزوم ها……………………………………………………………………………………..97
5-4.عملیات Crossover و Mutation………………………………………………………………………….98
5-5.خروجی اولیه CH ها و اعمال ACO برای خوشه بندی………………………………………………..99
5-6.مقایسه خروجی LEACH و روش پیشنهادی…………………………………………………………..100
5-7.مقایسه مصرف انرژی و عمر شبکه LEACH و روش پیشنهادی…………………………………..104
فصل ششم: نتیجه گیری و کارهای آتی
6-1.نتیجه گیری……………………………………………………………………………………………………..107
6-2.کارهای آتی……………………………………………………………………………………………………108
6-3.محدودیت ها…………………………………………………………………………………………………..109
منابع…………………………………………………………………………………………………………………..110
چکیده انگلیسی………………………………………………………………………………………………………113
فهرست جدول ها
عنوان صفحه
3-1. الگوریتم های خوشه بندی……………………………………………………………………………………76
3-2. طبقه بندی ویژگی های الگوریتم های خوشه بندی……………………………………………………77
فهرست شکل ها
عنوان صفحه
2-1. معماری ارتباطات شبکه های حسگر بیسیم……………………………………………………………….13
2-2. اجزاء درونی یک گره حسگر……………………………………………………………………………….18
2-3. پشته پروتکلی شبکههای حسگر…………………………………………………………………………….20
2-4. نمونه کاربردهای شبکههای حسگر بیسیم………………………………………………………………26
2-5.فضای حل کروموزوم ها………………………………………………………………………………………44
2-6.کددهی جایگشتی………………………………………………………………………………………………45
2-7.کددهی ارزشی………………………………………………………………………………………………….45
2-8.کددهی درختی………………………………………………………………………………………………….46
2-9.ترکیب و جهش در کددهی دودویی……………………………………………………………………..46
2-10.ترکیب دو نقطه ای……………………………………………………………………………………………47
2-11.ترکیب یکنواخت……………………………………………………………………………………………..47
2-12.ترکیب حسابی…………………………………………………………………………………………………47
2-13.ترکیب…………………………………………………………………………………………………………..48
2-14. کلونی مورچگان……………………………………………………………………………………………..49
3-1. شکل نهایی خوشه بندی………………………………………………………………………………………57
3-2. مفهوم سلسله مراتب خوشه ها……………………………………………………………………………….58
3-3. ساختار شش گوشه سلولی مجازی…………………………………………………………………………60
3-4. الگوریتم FLOC……………………………………………………………………………………………….65
3-5. پیشرفت الگوریتم ACE را بعد از 3 تکرار……………………………………………………………….68
3-6. ساختار موقعیت درون خوشه ای……………………………………………………………………………72
3-7. ترسیم دوباره از نمونه ای از سلسله مراتب ویژگی………………………………………………………75
3-8. نمونه ای از خوشه بندی……………………………………………………………………………………….78
3-9. توزیع نسبی قبل و بعد از سنجش GA……………………………………………………………………..81
4-1.روند کلی روش پیشنهادی…………………………………………………………………………………….86
4-2. مراحل Genetic………………………………………………………………………………………………..89
4-3. کلونی مورچگان……………………………………………………………………………………………….90
4-4. یک شبه کد برای ACO……………………………………………………………………………………..91
5-1. عمل Crossover با سیاست Bitmask……………………………………………………………………98
5-2. انتخاب CH ها توسط Genetic…………………………………………………………………………….99
5-3. نتایج پیاده سازی LEACH………………………………………………………………………………..101
5-4. نتایج پیاده سازی Genetic – ACO…………………………………………………………………….101
5-5. زمان مرگ اولین گره………………………………………………………………………………………..102
5-6. مقایسه زمان مرگ گره ها………………………………………………………………………………….103
5-7. زمان از کار افتادن شبکه…………………………………………………………………………………….103
5-8. مقایسه مصرف انرژی………………………………………………………………………………………..104
5-9. مقایسه ماندگاری SN ها و طول عمر شبکه…………………………………………………………….105
چکیده
این تحقیق به بهبود بهینه سازی طول عمر و مصرف انرژی در شبکه های حسگر بی سیم می پردازد و در نهایت ایجاد خوشه های مناسب در محیط های با تعداد حسگر زیاد. این دو هدف تأثیر عمیق بر روی صلاحیت خدمات شبکه و شکل گیری خوشه ها که یک راه حل مناسب برای دستیابی به آنها است می گذارد. برای حل مسائل بهینه سازی شبکه ی سنسوری، روشی کارآمد مبتنی بر الگوریتم های ژنتیک و کلونی مورچگان را ارائه می دهیم. ما از الگوریتم ژنتیک برای ایجاد سرخوشه هایی با هدف بهبود انرژی در خوشه بندی شبکه های حسگر بیسیم استفاده می کنیم. کلونی مورچگان نیز خوشه های با هدف نزدیکترین فواصل در محیط های پر جمعیت ارائه می کند. هدف اصلی انتقال داده های جمع آوری شده به ایستگاه پایه و ایجاد گره های منطقی به نام سرخوشه می باشد. این مطالعه به بررسی الگوریتم ژنتیک و کلونی مورچگان به عنوان یک روش پویا برای پیدا کردن موقعیت های مطلوب حسگر ها و خوشه ها است. ابزار شبیه سازی در این پایان نامه نرم افزار JAVA می باشد. در نهایت، اجرای الگوریتم پیشنهادی نشان می دهدکه بهره وری این الگوریتم در مقایسه با دیگر آثار شبیه سازی شده بهتر است.
مقدمه
فنآوری اطلاعات خیلی سریع به عنوان یک وسیله ضروری در جامعه مطرح شد. با رشد هر چه بیشتر این فن آوری ضرورت به کارگیری کامپیوتر، برای رفع نیازها، در جامعه روز به روز بیشتر احساس میشود. پیشرفتهای اخیر در کاهش هزینهها و کوچک کردن وسایل محاسباتی، همچنین استفاده از تکنولوژیهای ارتباطی بیسیم و سنسورها، زندگی روزمره بشر را ساده کرده است. شبکههای سنسور یکی از تکنولوژیهای کلیدی در آینده خواهند بود. در سال 1999 مجله تجارت هفتگی این شبکهها را یکی از مهمترین تکنولوژیهای قرن بیست و یکم معرفی کرد[2]. دستگاههای ارزان و هوشمند با چندین سنسور داخل خود که به صورت بیسیم شبکه شدهاند، امکانات بینظیری برای اندازهگیری و کنترل در صنعت، کشاورزی، شهرها و محیط زیست فراهم کردهاند. شبکه های سنسور این تکنولوژی را برای استفاده در طیف وسیعی از سیستمهای دفاعی، شناسایی و نظارت ارائه کردهاند.
شبکههای حسگر بیسیم[1] جهت جمع آوری اطلاعات در مناطقی که کاربر نمیتواند حضورداشته باشد مورد استفاده قرار می گیرند. در یک شبکه حسگر ، حسگرها به صورت جداگانه مقادیر محلی را نمونه برداری (اندازه گیری) می کنند و این اطلاعات را درصورت لزوم برای حسگرهای دیگر و در نهایت برای مشاهده گر اصلی ارسال می نمایند. عملکرد شبکه این است که گزارش پدیده هایی را که اتفاق میافتد به مشاهده گری بدهد که لازم نیست از ساختار شبکه و حسگرها به صورت جداگانه و ارتباط آنها چیزی بداند. این شبکه ها مستقل و خودگردان بوده وبدون دخالت انسان کار میکنند. معمولا تمامی گرهها همسان میباشند و عملاً با همکاری با یکدیگر، هدف کلی شبکه را برآورده میسازند. هدف اصلی در شبکههای حسگر بیسیم نظارت و کنترل شرایط و تغییرات جوی، فیزیکی و یا شیمیائی در محیطی با محدوده معین میباشد. پیشرفتهای اخیر در طراحی و ساخت تراشههای تجاری این امکان را به وجود آورده است که عمل پردازش سیگنال و حسکنندگی در یک تراشه انجام گردد که به این قطعات حسگرهای شبکه بیسیم گفته میشود که شامل سیستمهای میکروالکترومکانیکی مانند حسگرها، محرکها و قطعات رادیویی میباشد.
در شبکههای بیسیم حسگر فقط یک یا دو ایستگاه پایه وجود دارد و تعداد زیادی نودهای حسگر در محیط پخش گردیدهاند. به علت محدودیت برد این حسگرها و انرژی باتری خیلی از نودها قادر به ارتباط مستقیم با ایستگاه پایه نمی باشند. اما سریعاً با تکیه بر نودهای نظیر خود و نودهای حسگر دیگر، به ارتباط با ایستگاه پایه می پردازد.
شبکه های حسگر بیسیم، نوع خاصی از شبکه های کامپیوتری هستند که برای انجام کارهای نظارتی تعبیه شده اند. این شبکه ها از تعداد زیادی (حتی هزاران) گره کوچک با قابلیت و قدرت پایین و همچنین ارزان قیمت تشکیل شده اند. این گره ها که هر کدام سنسور نامیده می شوند، می توانند اطلاعاتی را از محیط اطراف خود دریافت کرده و با انجام یکسری عملیات، اطلاعات را برای همسایگان خود ارسال کنند.
فصل اول
کلیات تحقیق
1-1.شرح مساله
1-1-1 .تشریح ابعاد : شبکه های حسگر بیسیم، نوع خاصی از شبکه های کامپیوتری هستند که برای انجام کارهای نظارتی تعبیه شده اند. این شبکه ها از تعداد زیادی (حتی هزاران) گره کوچک با قابلیت و قدرت پایین و همچنین ارزان قیمت تشکیل شده اند. این گره ها که هر کدام سنسور نامیده می شوند، می توانند اطلاعاتی را از محیط اطراف
[جمعه 1398-07-05] [ 08:40:00 ب.ظ ]
|