مهندسی کامپیوتر- نرم افزار

 

عنوان:

بهبود خوشه بندی شبکه های حسگر بیسیم با بهره گیری از ترکیب الگوریتم ژنتیک و کلونی مورچگان

 

استاد راهنما: دکتر مؤتمنی

استاد مشاور: دکتر رمضانی

93-1392

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی گردد

(در فایل دانلودی نام نویسنده موجود می باشد)

تکه هایی از متن پایان نامه به عنوان نمونه :

فهرست مطالب

عنوان                                                                                                             صفحه

 

چکیده……………………………………………………………………………………………………………………..1

مقدمه……………………………………………………………………………………………………………………….2

فصل اول:کلیات پژوهش

۱-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 .تشریح ابعاد  : شبکه های حسگر بیسیم، نوع خاصی از شبکه های کامپیوتری هستند که برای انجام کارهای نظارتی تعبیه شده اند. این شبکه ها از تعداد زیادی (حتی هزاران) گره کوچک با قابلیت و قدرت پایین و همچنین ارزان قیمت تشکیل شده اند. این گره ها که هر کدام سنسور نامیده می شوند، می توانند اطلاعاتی را از محیط اطراف خود دریافت کرده و با انجام یکسری عملیات، اطلاعات را برای همسایگان خود ارسال کنند. در شبکه های حسگر بیسیم پروتکل های بسیاری به موضوع مسیریابی پرداخته اند. این پروتکل ها می توانند از دید ساختار شبکه به دسته مسیریابی تخت، سلسله مراتبی و مبتنی بر مکان تقسیم شوند. در مدل تخت همه گره ها تأثیر یا کار مساوی دارند اما در سلسله مراتبی گره ها تأثیر مختلفی بازی می کنند و در مدل مبتنی بر مکان نیز از موقعیت گره های سنسور برای مسیردهی داده در شبکه بهره گیری           می گردد. انواع مختلف این پروتکل ها در اینجا مورد مطالعه قرار گرفته و در مورد هایی با پارامترهایی با هم مقایسه شده اند.

 

1-1-2 .حدود مساله : در شبکه­ های حسگر بی­سیم، تعداد زیادی گره با امکانات مخابره، پردازش، حس­کردن محیط و غیره در محیطی با چهارچوب معین پراکنده شده­اند. رویداد اتفاق افتاده و یا سوالات پرسیده شده از سوی گره مرکزی و ماموریت محوله بر هر گره موجب می­گردد، ارتباطاتی بین گره­ها مستقر گردد. اطلاعات رد و بدل شده می‌تواند گزارشی از وضیعت محدوده که زیر نظر گره­های حسگر می­باشد به گره مرکزی و یا درخواستی از سمت گره مرکزی به سمت گره­های حسگر باشد. گره مرکزی به عنوان درگاه ارتباطی شبکه حسگر با سایر سیستم­ها و شبکه­های مخابراتی، در واقع گیرنده نهایی گزارش از گره­های حسگر می­باشد و بعد از انجام یکسری پردازش­ها، اطلاعات پردازش شده را به کاربر ارسال می­کند (با بهره گیری از یک رسانه ارتباطاتی مانند اینترنت، ماهواره و غیره). از سوی دیگر، درخواست­های کاربر نیز توسط این گره به شبکه انتقال می­یابد.

 

تبیین این ایده را به چند قسمت تقسیم کرده و بخش های هر قسمت را تشریح می کنیم. جستجو در سایت :   

 

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

1-1-4 .اظهار جنبه‌های مجهول و مبهم و متغیرهای مربوط به پرسش‌های پژوهش :  عواملی زیرا اقتصادی بودن سیستم، توانایی­های مورد انتظار، تعداد انبوه گره­ها و عملی شدن ایده­ها در محیط واقعی، موجب گشته هر گره با بعضی محدودیت­های سخت­افزاری مواجه باشد . این محدودیت‌ها عبارتند از:

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

حجم کوچک: گره­ها به نسبت محدوده­ای که زیر نظر دارند بخشی را به حجم خود اختصاص می­دهند. هر چه این نسبت (حجم گره به محدوده زیر نظر) کمتر باشد، عملکرد شبکه بهتر می­باشد و از طرفی در اکثر موردها برای اینکه گره­ها جلب توجه نکنند و یا بتوانند در بعضی مکان­ها قرار بگیرند لازم می باشد که حجم بسیار کوچکی داشته باشند.

انرژی مصرفی پائین: منبع تغذیه گره­ها محدود می­باشد و در اقدام معمولاً امکان تعویض یا شارژ مجدد غیرممکن می­باشد. پس بایستی از انرژی موجود به بهترین نحو ممکن بهره گیری گردد.

نرخ بیت پائین: به خاطر وجود بعضی محدودیت­ها (انرژی و غیره)، عملا اندازه نرخ انتقال و پردازش اطلاعات در یک گره حسگر پائین می باشد.

خودمختار بودن: هر گره بایستی از سایر گره­ها مستقل باشد و بتواند عملکرد خود را طبق تشخیص و شرایط خود انجام دهد.

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

(ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل می باشد)

تعداد صفحه : 131

قیمت : چهارده هزار تومان دانلود متن کامل در سایت sabzfile.com

بلافاصله پس از پرداخت لینک دانلود فایل در اختیار شما قرار می گیرد

و در ضمن فایل خریداری شده به ایمیل شما ارسال می گردد.

پشتیبانی سایت :               serderehi@gmail.com

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

***  *** ***