چکیده

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

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