1-1 مقدمه……………………………………………………………………………………………………4

1-2بیان مساله………………………………………………………………………………………………..11

1-3اهمیت و ضرورت تحقیق…………………………………………………………………………..14

1-4سؤالات تحقیق:…………………………………………………………………………………….16

1-5 فرضیه‏ های تحقیق……………………………………………………………………………..16

فصل دوم: مروری بر ادبیات تحقیق

2-1 WSn ‌ها با یک چاهک ثابت…………………………………………………………………….19

2-1-1 مشکل اتمام انرژی در گره‌های اطراف چاهک……………………………………………19

2-1-2 بهبود حالت چاهک ثابت ……………………………………………………………………..20

2-2 WSN با یک چاهک متحرك……………………………………………………………………..21

2-2-1 مزایای چاهک متحرک …………………………………………………………………….22

2-2-2 عیب استفاده از چاهک متحرک………………………………………………………………23

2-2-3 انواع حرکت چاهک متحرک …………………………………………………………………23

2-2-3-1 جابجایی تصادفی ……………………………………………………………………….23

2-2-3-2 شبكه های موبایل ثابت ………………………………………………………………24

2-2-3-3 جابجایی كنترل موبایلیتی ……………………………………………………………….25

2-3 ارسال داده های حساس به تاخیر ……………………………………………………….29

2-4 استفاده از چاهک ثابت و متحرک به صورت همزمان…………………………………..29

2-5 روش ارائه شده در EEQR ……………………………………………………………………

2-5-1 معرفی مشکل نقاط کور…………………………………………………………………..33

2-6 مسیریابی در شبکه‌های حسگر بیسیم…………………………………………………..33

2-6-1 اهداف مسیریابی…………………………………………………………………………33

2-6-2 معیارهای تعیین مسیر بهینه ……………………………………………………………..34

2-6-3 مسیریابی در شبکه‌های بیسیم ……………………………………………………….34

2-6-3-1 مسیریابی بردار فاصله ……………………………………………………………..35

2-6-3-2 مسیریابی حالت اتصال …………………………………………………………….36

2-6-3-3 مسیریابی مبدا ………………………………………………………………………36

2-7 روش های انتشار اطلاعات ………………………………………………………………36

2-7-1 روش همه پخشی (Flooding)…………………………………………………….

2-7-2 روش شایعه پراكنی (gossiping)………………………………………………

2-7-3 روش SPIN…………………………………………………………………………….

2-7-4 پیغام های SPIN …………………………………………………………………..

2-7-5 SPIN-1 یک روش دست تكانی سه مرحله ای ………………………………….41

2-7-6 خلاصه سازی فرصت طلبانه (opportunistic data aggregation)……….

2-7-7 خلاصه سازی حریصانه(greed data aggregation) …………………………

2-7-8 پرسش تو رد تو(nested query) ………………………………………………..

2-8 الگوریتم خوشه بندی …………………………………………………………………….44

2-8-1 معیارمطلوبیت خوشه ها ……………………………………………………………45

2-8-2 ویژگی‌های یک الگوریتم خوشه بندی مناسب …………………………………46

2-8-3 معایب روش خوشه بندی ………………………………………………………46

2-8-4 انواع خوشه بندی …………………………………………………………………46

2-8-5 الگوریتم kmeans …………………………………………………………………

2-8-5-1 مراحل كار ………………………………………………………………………..47

2-8-6 پیش پردازش داده ها …………………………………………………………….48

2-8-7 انواع ویژگی ها در خوشه‌بندی ………………………………………………..48

2-8-8 دلایل اصلی پیش پردازش داده‌ها …………………………………………..48

2-8-9 عملیات اصلی پیش پردازش داده ها …………………………………….49

2-8-10 آلودگی‌ها در خوشه بندی …………………………………………………..49

2-8-11 روش های مورد استفاده در پیش پردازش …………………………………….50

2-8-12 روش (Low-Energy Adaptive Clustering Hierarchy)…………………

2-8-12-1 جزئیات الگوریتم LEACH ………………………………………………………

2-8-12-2 فاز تبلیغات………………………………………………………………………..52

2-8-12-3 فاز تشكیل دسته‌ ها…………………………………………………………….53

 

 

2-8-12-4 فاز تشكیل برنامه…………………………………………………………….53

2-8-12-5 فاز انتقال داده‌ها…………………………………………………………………54

فصل سوم :روش تحقیق

3-1 مقدمه …………………………………………………………………………………..56

3-2 فاز اول: استقرار اولیه …………………………………………………………….58

3-2-1 توسعه اولیه …………………………………………………………………….58

3-2-2خوشه‌بندی ………………………………………………………………………..58

3-2-2-1 استفاده از روش BSK-Means برای خوشه بندی گره ‌ها ………………61

3-2-3 مسیریابی……………………………………………………………………………63

3-2-3-1 مسیریابی جهت اتصال به گره سرخوشه………………………………..64

3-2-3-2 مسیریابی سرخوشه به سمت فوق گره…………………………………64

3-2-3-3 مسیریابی به سمت چاهک متحرک …………………………………..65

3-2-3-4 مسیریابی وایجاد کانال خصوصی بین فوق‌گره‌ها…………………..65

3-3 فاز دوم : حیات و ادامه زندگی شبکه……………………………………….66

3-3-1 اولویت بندی اطلاعات………………………………………………………66

3-3-2 تصمیم گیری برای ارسال داده‌ها ………………………………………67

3-3-3 تصمیم‌گیری در مورد جهش حرکت چاهک متحرک…………………68

3-3-4 نحوه آگاهی فوق‌گره متصل به چاهک متحرک، به سایر فوق‌گره ها و نرک ایستگاه….70

3-3-5 ارسال غیر مستقیم اطلاعات چاهک متحرک………………………70

3-4 مقایسه روش های ارائه شده………………………………………………….71

3-4-1 روش چاهک ثابت………………………………………………………….71

3-4-2 روش چاهک متحرک……………………………………………………….72

3-4-3 استفاده از چاهک ثابت و متحرک به صورت همزمان(DualSink)…..

3-4-4 روش ارائه شده ………………………………………………………………..74

3-5 طرح و نقشه …………………………………………………………………….75

3-6 مزایای استفاده از این روش نسبت به سایر روش‌ها…………………..76

فصل چهارم :تجزیه و تحلیل داده ها و ارزیابی کارایی

4-1 ارزیابی کارایی …………………………………………………………………78

4-1-1 جزییات شبیه سازی ………………………………………………………..78

4-1-2 مدل انرژی مصرفی گره‌ها ……………………………………………….80

4-1-3 مقایسه انرژی مصرف شده در روش ارائه شده ……………………80

4-1-4 تاثیر روش ارائه شده ،بر نرخ گم شدن بسته‌ها …………………..82

4-1-5 متوسط تعداد گام طی نموده برای رسیدن به چاهک ……………..83

فصل پنجم: نتیجه گیری و پیشنهادهای تحقیق

5-1نتایج………………………………………………………………………………….86

5-2 پیشنهادهای تحقیق……………………………………………………………87

چکیده:

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

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