دانلود پایان نامه خوشه بندی در شبکه های ویژه سیار با الگوریتم رقابت استعماری

دانلود پایان نامه خوشه بندی در شبکه های ویژه سیار با الگوریتم رقابت استعماری

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

<<قابل ویرایش>>

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

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

چکیده: 

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

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

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

در فصل پنجم الگوریتم پیشنهادی برای خوشه ­بندی ارائه می­شود. این الگوریتم خوشه­ بندی را با استفاده از الگوریتم رقابت استعماری انجام می­دهد. 

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

در فصل ششم پایان­ نامه، نتیجه­ گیری ارائه شده است.

قابل ویرایش

فرمت : doc و PDF

زبان : فارسی

تعداد صفحه : 75

<< پس از ثبت ایمیل در محل مشخص شده پایین مطلب

و ادامه عملیات خرید لینک دانلود نمایش داده شده

و به ایمیل شما نیز ارسال می شود >> 

پایان نامه ارشد ساختار شبکه تاخیری آگاه با همجوشی درون شبکه ای در شبکه های حسگر بی سیم

چکیده

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

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

فرضیه ها

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

هدف از انجام پژوهش

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

تعداد صفحات 89 word

فهرست مطالب

فصل اول مقدمه. 1

1-1 مقدمه. 2

1-2 تعریف مسئله و بیان سوال های اصلی تحقیق.. 5

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

1-4 فرضیه ها 7

1-5 هدف از انجام پژوهش... 7

1-6 کاربردهای پژوهش... 7

1-7 روش تحقیق.. 8

1-8 نوآوری پژوهش... 8

1-9 ساختار پایان نامه. 10

فصل دوم مروری بر خوشه بندی در شبکه های حسگر بی سیم. 11

2-1 مقدمه. 12

2-2 اهداف اصلی و چالش های طراحی خوشه بندی در شبکه های حسگر بی سیم. 14

2-3 پارامترهای خوشه بندی.. 15

2-4 دسته بندی الگوریتم های خوشه بندی.. 18

2-4-1 الگوریتم های خوشه بندی وزن دار. 20

2-4-2 الگوریتم های خوشه بندی سلسله مراتبی.. 20

2-4-2-1 الگوریتم LEACH.. 20

2-4-2-2 الگوریتمTB-LEACH.. 21

2-4-2-3 الگوریتم خوشه بندی انرژی موثر (EECS) 21

2-4-2-4 الگوریتم خوشه بندی اکتشاف گره های مجاور (NND) 21

2-4-2-5 الگوریتم خوشه بندی بر اساس انرژی باقی مانده (ECHE) 22

2-4-2-6 الگوریتم بهینه برای متعادل سازی خوشه ها (OABC) 22

2-4-2-7 الگوریتم خوشه بندی با توزیع انرژی موثر (MEPA) 23

2-4-3 الگوریتم های خوشه بندی ناهمگن.. 23

2-4-3-1 الگوریتم خوشه بندی ناهمگن با انرژی موثر (EEHC) 23

2-4-3-2 در الگوریتم خوشه بندی ناهمگن با توزیع انرژی متعادل (DEBC) 23

2-4-3-3 الگوریتم خوشه بندی با توزیع انرژی متعادل و تصادفی (SBDEEC) 24

2-4-3-4 الگوریتم خوشه بندی ناهمگن بر مبنای انرژی (EDUC) 24

2-4-3-5 الگوریتم خوشه بندی ناهمگن با انتخاب بیشترین وزن (WEP) 24

2-4-3-6 الگوریتم خوشه بندی ناهمگن با توزیع انرژی موثر (DEEC) 25

2-4-3-7 الگوریتم بهبود یافته خوشه بندی سلسله مراتبی مطابق با کمترین میزان انرژی (IB- LEACH) 25

2-4-3-8 الگوریتم خوشه بندی ناهمگن بر اساس پایداری (SEP) 26

2-4-4 الگوریتم خوشه بندی حریصانه. 26

2-5 جمع بندی.. 27

فصل سوم همجوشی داده ها در شبکه های حسگر بی سیم. 29

3-1 مقدمه. 30

3-2 تعریف همجوشی داده 30

3-3 واژگان فنی همجوشی.. 32

3-4 فرآیند همجوشی داده 34

3-5 چرا همجوشی داده 34

3-6 کاربردهای همجوشی اطلاعات... 35

3-6-1 کاربردهای نظامی.. 36

3-6-2 کاربردهای غیر نظامی.. 36

3-7 تکنیک ها، الگوریتم ها و روش های همجوشی اطلاعات... 38

3-7-1 دسته بندی همجوشی داده 38

3-7-1-1 دسته بندی براساس رابطه بین منابع (دیویدهال و جیمزلیناس، 2002)، (ناکامورا و همکارانش،2007): 38

3-7-1-2 دسته بندی برحسب سطح انتزاع. 39

3-7-1-3 دسته بندی برحسب داده های ورودی و خروجی.. 42

3-7-2 مدل همجوشی.. 43

3-7-3 الگوریتم ها، تکنیک ها و روش ها 45

3-7-3-1 الگوریتم LEACH.. 47

3-7-3-2 الگوریتم DADCNS. 49

3-8 جمع بندی.. 52

فصل چهارم الگوریتم پیشنهادی.. 54

4-1 مقدمه. 55

4-2 فرضیات الگوریتم. 55

4-3 مرحله ی خوشه بندی.. 56

4-3-1 مرحله ی انتخاب سرخوشه. 59

4-4 معرفی تابع انرژی.. 61

4-5 معرفی تابع تاخیر. 61

4-6 مرحله ی انتقال داده 62

4-7 جمع بندی.. 65

فصل پنجم نتایج شبیه سازی و تحلیل آن ها 67

5-1 مقدمه. 68

5-2 پارامترهای شبیه سازی.. 68

5-3 نتایج شبیه سازی.. 69

5-4 جمع بندی.. 74

فصل ششم جمع بندی و پیشنهادها 75

6-1 مقدمه. 76

6-2 پیشنهادها 77

منابع و مراجع. 78

فهرست اشکال

شکل 2-1: طبقه بندی الگوریتم های خوشه بندی (رضایی،ناجی، 1391) 27

شکل 3-1: رابطه ی میان اصطلاحات قوی همجوشی (عبدالجواد وبایومی،2012)، (ناکامورا و همکارانش،2007) 34

شکل 3-2: شمایی از افزونگی و مکمل داده (ناکامورا و همکارانش، 2007) 39

شکل 3-3: تلفیق مستقیم داده های سنسوری( دیویدهال و جیمزلیناس، 2002)، (داس، 2008) 40

شکل 3-4: نمایش داده های سنسورها در قالب بردارهای ویژگی ها و سپس تلفیق این بردارها (دیویدهال و جیمزلیناس، 2002)، (داس، 2008) 41

شکل 3-5: پردازش هر سنسور برای به دست آوردن استنتاج سطح بالا از آن به تنهایی و نهایتا تلفیق این استنتاج ها با یکدیگر (دیویدهال و جیمزلیناس، 2002)، (داس، 2008) 42

شکل 3-6: دسته بندی بر اساس ورودی و خروجی.. 43

شکل 3-1: الگوریتم DADCNS با N=16 گره (چنگ و همکارانش،2011) 50

شکل 4-1: ساختار مبتنی بر درخت برای N=15 (چنگ و همکارانش، 2013) 58

شکل 4-2: نحوه ی تشکیل خوشه ها در Leach (Hinzelman,2002) 60

شکل 4-3: نحوه ی تشکیل خوشه ها در الگوریتم پیشنهادی.. 60

شکل 4-3: فلوچارت مرحله ی خوشه بندی الگوریتم DASNDF. 64

شکل 4-4: فلوجارت مرحله ی انتقال داده الگوریتم DASNDF. 65

شکل 5-1: مدت زمان جمع آوری دده ها با ساختارهای شبکه های مختلف (r=1) 70

شکل 5-2:کل مصرف انرژی در یک فرآِند جمع آوری داده ها برای شبکه ها با ساختارهای متفاوت r=1. 71

شکل 5-3: مدت زمان جمع آوری داده ها برای شبکه ها با ساختاری متفاوت و r=0.75. 72

شکل 5-4: کل مصرف انرژی در یک فرآیند جمع آوری برای شبکه ها با ساختارهای متفاوت و r=0.75. 72

شکل 5-5: مدت زمان جمع آوری داده ها برای شبکه ها با ساختارهای متفاوت و r=0. 5. 73

شکل 5-6: کل مصرف انرژی در یک فرآیند جمع آوری برای شبکه ها با ساختارهای متفاوت و r=0. 5. 73

فهرست جداول

جدول 2-1: مقایسه پارامترهای مختلف برای الگوریتم های خوشه بندی موجود (سادیپ میسترا و همکارانش، 2009) 18

جدول 5-1: پارامترهای شبیه سازی.. 69

جدول 5-2: مقایسه پروتکل های LEACH، DADCNS, و DASNDF, 74

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

عنوان تحقیق: الگوریتم های خوشه بندی در شبکه های حسگر بی سیم

فرمت فایل: word

تعداد صفحات: 133

شرح مختصر:

شبکه های حسگر بی سیم شامل تعدا زیادی از سنسورهای کوچک است که که می توانند یک ابزار قوی برای جمع آوری داده در انواع محیط های داده ای متنوع باشند. داده های جمع آوری شده توسط هر حسگر به ایستگاه اصلی منتقل می شود تا به کاربر نهایی ارائه می شود. یکی از عمده ترین چالشها در این نوع شبکه ها، محدودیت مصرف انرژی است که مستقیما طول عمر شبکه حسگر را تحت تأثیر قرار میدهد ، خوشه بندی بعنوان یکی از روشهای شناخته شده ای است که بطور گسترده برای مواجه شدن با این چالش مورد استفاده قرار میگیرد.

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

فهرست مطالب

چکیده1

مقدمه. 2

فصل اول :شبکه ی حسگر بی سیم. 3

مقدمه. 4

بررسی اجمالی مسائل کلیدی.. 6

انواع شبکه حسگر بی سیم. 11

ساختارهای شبکه حسگر بی سیم. 14

ویژگی‌های سخت‌افزاری:17

کاربردهای شبکه ی حسگر بی سیم. 20

عوامل موثر بر شبکه ی حسگر بی سیم. 26

پشته پروتکلی.. 33

نتیجه گیری بخش... 38

فصل دوم :انواع الگوریتم های خوشه بندی.. 39

مقدمه. 40

بررسی کلی خوشه بندی.. 40

الگوریتم های خوشه بندی سلسله مراتبی.. 40

الگوریتم های خوشه بندی طیفی.. 41

الگوریتم های خوشه بندی مبتنی بر شبکه ی گرید. 42

الگوریتم خوشه بندی مبتنی بر تراکم. 43

الگوریتم های خوشه بندی پارتیشن بندی.. 43

الگوریتم خوشه بندی ژنتیک k-means برای ترکیب مجموعه داده های عددی و قاطعانه. 44

الگوریتم مقیاس.......45

الگوریتم k-means هماهنگ.. 46

مقداردهی k-means با استفاده از الگوریتم ژنتیک.. 47

رویکرد مجموع خوشه ها برای داده های ترکیبی............48

الگوریتم تکاملی ترکیبی.......49

اصلاح جهانی الگوریتم k-means 50

الگوریتم ژنتیک k-means سریع. 50

نتیجه گیری بخش... 52

فصل سوم :الگوریتم های خوشه بندی در شبکه ی حسگر بی سیم. 53

مقدمه. 54

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

فرآیند خوشه بندی.. 58

پروتکل های خوشه بندی موجود. 59

الگوریتم های ابداعی......59

طرح های وزنی.......60

طرح های شبکه ی گرید. 62

طرح های سلسله مراتبی و دیگر طرح ها......64

الگوریتم های خوشه بندی در شبکه های حسگر بی سیم ناهمگون. 73

مدل ناهمگون برای شبکه های حسگر بی سیم......73

طبقه بندی ویژگی های خوشه بندی در شبکه های حسگر بی سیم ناهمگون......75

الگوریتم خوشه بندی برای شبکه های حسگر بی سیم ناهمگون......77

نتیجه گیری بخش... 92

 فصل چهارم:بررسی دو الگوریتم خوشه بندی EECS و A-LEACH.. 93

مقدمه. 94

EECS.. 95

نمای کلی مشکلات.. 95

جزئیات EECS. 97

تحلیل EECS. 103

شبیه سازی.. 107

رویکردهای آینده112

A-LEACH.. 113

آثار مربوطه. 113

تجزیه و تحلیل انرژی پروتکل ها115

A-LEACH.. 115

شبیه سازی.. 118

رویکردهای آینده و نتیجه گیری 122

نتیجه گیری.. 123

 فهرست اشکال

شکل .1 . طبقه بندی موضوعات مختلف در شبکه ی حسگر بی سیم. 8

شکل .2. ساختار کلی شبکه ی حسگر بی سیم. 16

شکل. 3. ساختار خودکار16

شکل. 4. ساختار نیمه خودکار17

شکل. 5.ساختار داخلی گره ی حسگر. 18

شکل 6. پشته ی پروتکلی.. 34

شکل 7 . نمونه ای از الگوریتم GROUP. 63

شکل .8 . الف )ساختار شبکه ب)شبکه بعد از چند دور78

شکل 9. الف) ساختار شبکه ب) خوشه بندی EDFCM.. 85

شکل 10. سلسله مراتب خوشه در زمینه ی سنجش... 87

شکل 11. دیاگرام شماتیک از مناطق در اندازه های مختلف.. 89

شکل .12. تاثیر هزینه ی سرخوشه ی موردنظر. 102

شکل. 13. پدیده ی شیب در شبکه. 105

شکل.14. الف : توزیع غیر یکنواخت ب : توزیع یکنواخت.. 107

شکل. 15. الف: صحنه ی معمولی ب: صحنه ی بزرگ 108

شکل .16. الف : صحنه ی معمولی ب: صحنه ی بزرگ 109

شکل. 17. الف : صحنه ی معمولی ب: صحنه ی بزرگ.. 110

شکل.18. تعداد خوشه ها در هر دور در EECSو LEACH(صحنه ی 1)111

شکل. 19.الف : صحنه ی معمولی ب : صحنه ی بزرگ.. 112

شکل .20. مدل شبکه ای A-LEACH.. 118

شکل 21. شبکه ی حسگر بی سیم با مدل A-LEACH.. 119

شکل .22. طول منطقه ی ثبات برای مقادیر مختلف ناهمگونی.. 120

شکل 23. تعداد گره های زنده نسبت با دور با m=0.1 و a=1. 120

شکل .24. تعداد گره های زنده نسبت به دور با m=0.3 و a=1. 121

شکل. 25. تعداد گره های زنده نسبت به دور با m=0.5 وa=1. 121

 فهرست جداول

جدول 1 .مقایسه ی الگوریتم های خوشه بندی طرح سلسله مراتبی.. 72

جدول.2. مقایسه ی الگوریتم های خوشه بندی.. 91

جدول.3. مفهوم نمادها98

جدول .4 . توصیف حالات یا پیغام ها98

جدول 5 . پارامترهای شبیه سازی.. 107