چکیدهکاربرد روز افزون شبکههای حسگر بیسیم در زندگی انسان گویای اهمیت زیاد این تکنولوژی است. محدودیت انرژی در عناصر تشکیل دهندهی شبکههای حسگر بیسیم که گرهحسگرها میباشند همواره به عنوان مهمترین چالش پیش روی این تکنولوژی مطرح بوده است و به همین دلیل بخش اعظم تحقیقات انجام شده در حیطهی شبکههای حسگر بیسیم به موضوع انرژی اختصاص یافته است. با توجه به اینکه نحوهی انتخاب مسیرها برای ارسال اطلاعات در شبکههای حسگر بیسیم تأثیر قابل توجهی بر میزان مصرف انرژی شبکه دارد، در این پژوهش سعی بر ارایهی راهکاری در زمینهی مسیریابی با هدف افزایش طول عمر شبکه شده است. در این روش با در نظر گرفتن تاریخچهی مصرف انرژی گرههای حسگر، تعداد همسایگان حسگر ارسال کنندهی داده، و فاصله مبدأ تا مقصد ارسال داده(تک گام)، راهکاری ارایه شده است که میتواند تأثیر بسیاری بر افزایش عمر شکه داشته باشد. شبیهسازی و مقایسه با روشهای معروف و موفق مسیریابی در شبکههای حسگر بیسیم گویای شایستگی روش پیشنهادی میباشد. کلمات کلیدی: شبکههای حسگر بیسیم، مسیریابی، الگوریتم PSO، عمر شبکه، محدودیت انرژی فهرست مطالب1 مقدمه. 21-1 ضرورت مسئله و چالشهای پروتکل مسیریابی. 31-1-1 ظرفیت محدود انرژی. 41-1-2مختصات مکان گرهها. 41-1-3محدودیت منابع سختافزاری. 41-1-4تعداد زیاد گره و قرار گرفتن تصادفی در محیط. 41-1-5 ویژگیهای شبکه و عدم اطمینان محیط فیزیکی. 41-1-6 افزونگی داده. 51-1-7 تنوع کاربرد شبکههای حسگر بیسیم. 51-2 ویژگیهای شبکههای حسگر بیسیم. 51-3 ساختار گره حسگر. 71-4 قالب پیام. 8چکیده فصل اول. 92 کارهای مرتبط. 122-1 مقدمه. 122-2 انواع پروتکلهای مسیریابی. 122-2-1 پروتکلهای مبتنی بر مکان. 132-2-2 پروتکلهای دادهمحور. 142-2-3پروتکلهای سلسله مراتبی. 152-2-4 پروتکلهای مبتنی بر حرکت. 172-2-5پروتکلهای مبتنی بر چند مسیر. 182-2-6پروتکلهای مربوط به شبکههای ناهمگن. 182-2-7 پروتکلهای مبتنی بر کیفیت سرویس. 192-3 مسیریابی متمرکز و توزیع شده. 192-3-1 الگوریتمهای مرکزی. 192-3-2 الگوریتم های توزیع شده. 202-4 محیط سه بعدی. 20چکیدهی فصل دوم. 213 الگوریتم پیشنهادی. 233-1 انواع روشهای مسیریابی. 233-2 مفروضات در نظر گرفته شده درشبیهسازی. 243-3الگوریتم PSO.. 263-4 مراحل الگوریتم پیشنهادی. 28چکیدهی فصل سوم. 354 شبیهسازی و اجرای اگوریتم پیشنهادی. 374-1نرمافزارهای شبیهسازی شبکههای حسگر بیسیم. 374-2شبه کد الگوریتم PSO.. 394-3 طراحی شبیه ساز شبکههای حسگر بیسیم. 414-4 بستهی دادهای. 434-5 شبهکد الگوریتم پیشنهادی. 44خلاصهی فصل چهارم. 465نتایج شبیهسازی. 485-1 مقایسهی عمر شبکه. 495-2 مقایسهی نرخ دریافت اطلاعات. 53چکیدهی فصل 5. 556 نتیجهگیری و پیشنهادات. 576-1خلاصهی بحث. 576-2 خلاصهی نتایج. 576-3 پیشنهادات وکارهای آتی. 58مراجع. 60 فهرست اشکال شکل 1-1. الگوی انتقال چند به یک در شبکههای حسگربیسیم7شکل1-2. ساختارگرهیحسگر.............................. 8شکل 2-1. خوشهوسرخوشهدرروشهایسلسلهمراتبی....... 15شکل2-2. خوشههاوسرخوشههادرروشECHERP.............. 16شکل 3-1.نحوهیحرکتذراتدرالگوریتمPSO.............. 27شکل3-2. مراحلالگوریتمPSO.......................... 28.شکل 3-3. ساختارلایهبندیحسگرهایدردسترسایستگاهاصلی31شکل4-1. فلوچارتالگوریتمPSO........................ 40شکل4-2. شبهکدالگوریتمپیشنهادی.................... 41شکل4-3. منویاصلیشبیهسازطراحیشده................. 42شکل4-4. منویاصلیشبیهسازدرلحظهیازبینرفتناولینحسگر 43شکل4-5. شبهکدالگوریتمپیشنهادی................... 45شکل5-1. مقایسهالگوریتمپیشنهادیباالگوریتمهایAODVوLEACH50شکل5-2. مقایسهیالگوریتمپیشنهادی،HEED,APTEEN,PEGASIS51شکل5-3. مقایسهیالگوریتمپیشنهادیوEDOCR........... 52شکل5-4. مقایسهیالگوریتمپیشنهادیو SEEM........... 53شکل5-5. مقایسهیالگوریتمپیشنهادیبراساسنحوهیاستفادهازوزنهایرابطه (5).................................... 55شکل6-1. شبکهیحسگربیسیم............................ 59 فهرست جداول جدول 1-1. تعدادی ازگرهحسگرهای رایج وکاربردآنها....... 3جدول2-1. انواع پروتکلهای مسیریابی درشبکههای حسگر بیسیم13جدول2-2. مقایسهی الگوریتمهای مسیریابی سلسله مراتبی.. 17جدول4-1. مقایسهی شبیهسازهای شبکههای حسگربیسیم....... 38جدول5-1. ضرایب ثابت رابطهی (5) درشرایط مختلف شبکه... 48جدول5-2. مقایسهی نرخ دریافت داده توسط ایستگاه اصلی درالگوریتمهای مسیریابی............................................ 54فصل اول مقدمه 1 مقدمهشبکههای حسگر بیسیم از تعدادی گرهحسگر تشکیل شده است و به طور معمول اندازهی این گرهها کوچک است و ارزان قیمت هستند. تمامی این گرهها قابلیت دریافت اطلاعات از محیط اطراف خود را دارند، همچنین میتوانند دادههای دریافت شده از محیط را به سمت گرهحسگری که در همسایگی آنها قرار دارد بفرستند و یا از آنها دریافت کنند. در این نوع شبکهها شعاع انتقال دادهها محدود است، همچنین گرهها از نظر پردازشی و ذخیرهی اطلاعات نیز محدودیت دارند. با توجه به محدود بودن انرژی گرهها، بیشتر روشهای مسیریابی در این نوع شبکهها با هدف افزایش طول عمر شبکه مطرح شدهاند. در این پژوهش یک الگوریتم مسیریابی جدید معرفی میشود که مهمترین هدف آن افزایش عمر شبکه است.در بیشتر کاربردهای شبکههای حسگر بیسیم، نحوهی قرار گرفتن گرهها در محیط فیزیکی به صورت تصادفی است ونقشهی خاص و از پیش تعیین شدهای ندارد. گرهها پس از قرار گرفتن در محیط به طور خودکار ساختار شبکه را تشکیل میدهند و برای مدت محدودی به دریافت اطلاعات از محیط اطراف و انتقال آن به ایستگاه اصلی میپردازند. انرژی لازم برای دریافت اطلاعات از محیط و فرستادن اطلاعات به دیگر حسگرها توسط باتریهای تعبیه شده در حسگرها تأمین میشود. بنابراین انرژی این گرهها محدود است و در اکثر کاربردها پس از اتمام انرژی باتری، شارژ مجدد ویا تعویض آن بسیار دشوار و بهطور معمول غیرممکن است. کاربردهای مختلف شبکههای حسگر منجر به تولید گرهحسگرهای زیادی شده است که از نظر معماری، اندازه، مصرف انرژی و شعاع پوشش گره بسیار متفاوت هستند. جدول 1-1 تعدادی از این گرهحسگرها و کاربردی را که دارند نشان میدهد]1[. جدول 1-1. تعدادی از گرهحسگرهای رایج و کاربرد آنهاشکل گرهویژگینامیکی از جدیدترین تکنولوژیهای گرهحسگر است. میتواند فیلم و عکس را رمز کرده و ارسال کند.از پروتکلهایHSPA وWCDMAبرای انتقال داده استفاده میکند. 3Gwaspmoteمصرف انرژی کمی دارد. میتواند از انرژی خورشیدی استفاده کند. زمان راه اندازی شبکهی این نوع گره بسیار کوتاه است.قابل برنامهریزی [1]OTAPرا دارا می باشد. Waspmote Plug&Senseقابلیت اندازهگیری همزمان دما، نور و رطوبت را دارد. شعاع پوشش این گره نسبت به گرههای دیگر کم است. ساختمان سادهای دارد. زمان راهاندازی آن کوتاه است. SquidBee 1-1 ضرورت مسئله و چالشهای پروتکل مسیریابیمحدودیت انرژی همواره مهمترین چالش پیشروی شبکههای حسگر بیسیم بوده است. با توجه به اینکه بخش زیادی از انرژی شبکه صرف ارسال اطلاعات به دست آمده از محیط به سمت ایستگاه اصلی میشود، استفاده از یک روش مسیریابی مناسب میتواند تا حد زیادی طول عمر شبکه را افزایش دهد. ارایهی یک پروتکل مسیریابی برای شبکههای حسگر بیسیم با چالشهایی روبهروست که از محدودیتهای این شبکهها ناشی میشود. همچنین این شبکهها در بسیاری از منابع شبکه نیز محدودیت دارند. برای مثال: پهنای باند ارتباطی[2]، واحد پردازشگر، واحد ذخیرهسازی و انرژی ]2،3[. مهمترین چالشهای پیش روی طراحی پروتکلهای مسیریابی عبارتند از]4،5،6[:با توجه به اینکه گرههای حسگر انرژی لازم را از باتریها میگیرند، بنابراین ظرفیت محدودی دارند. هنگامی که انرژی گره از یک مقدار آستانه کمتر شود، آن گره قادر به ادامه فعالیت خود نخواهد بود و این امر تاثیر منفی زیادی روی شبکه میگذارد. از اینرو محدودیت انرژی بزرگترین چالش برای ارایه یک پروتکل مسیر یابی است .چالش دیگری که در امر ارایه یک پروتکل مسیریابی است مدیریت مکان گره است. تعداد زیادی از پروتکلهای مسیریابی فرض میکنند که هرحسگر مجهز به سیستم مکانیابی جهانی است[3] و یا از الگوریتمهای مکانیابی برای یافتن مکان گره استفاده میکنند]5[.گرههای حسگر علاوه بر انرژی، از لحاظ ذخیرهسازی و پردازش نیز محدود هستند. گرهی حسگر نمیتوانند محاسبات پیچیده و طولانی را انجام دهد و این امر چالشی برای پیشرفت نرم افزاری در شبکههای حسگر بیسیم است. بنابراین برای ارایه یک الگوریتم مسیریابی علاوه بر انرژی باید محدودیت سخت افزاری را نیز در نظر داشت. [1]. Over The Air Programming[2]. Bandwidth[3]. Global Positioning System
ارایهی یک روش مسیریابی برای شبکههای حسگر بیسیم با هدف افزایش طول عمر شبکهWORD
چکیدهکاربرد روز افزون شبکههای حسگر بیسیم در زندگی انسان گویای اهمیت زیاد این تکنولوژی است. محدودیت انرژی در عناصر تشکیل دهندهی شبکههای حسگر بیسیم که گرهحسگرها میباشند همواره به عنوان مهمترین چالش پیش روی این تکنولوژی مطرح بوده است و به همین دلیل بخش اعظم تحقیقات انجام شده در حیطهی شبکههای حسگر بیسیم به موضوع انرژی اختصاص یافته است. با توجه به اینکه نحوهی انتخاب مسیرها برای ارسال اطلاعات در شبکههای حسگر بیسیم تأثیر قابل توجهی بر میزان مصرف انرژی شبکه دارد، در این پژوهش سعی بر ارایهی راهکاری در زمینهی مسیریابی با هدف افزایش طول عمر شبکه شده است. در این روش با در نظر گرفتن تاریخچهی مصرف انرژی گرههای حسگر، تعداد همسایگان حسگر ارسال کنندهی داده، و فاصله مبدأ تا مقصد ارسال داده(تک گام)، راهکاری ارایه شده است که میتواند تأثیر بسیاری بر افزایش عمر شکه داشته باشد. شبیهسازی و مقایسه با روشهای معروف و موفق مسیریابی در شبکههای حسگر بیسیم گویای شایستگی روش پیشنهادی میباشد. کلمات کلیدی: شبکههای حسگر بیسیم، مسیریابی، الگوریتم PSO، عمر شبکه، محدودیت انرژی فهرست مطالب1 مقدمه. 21-1 ضرورت مسئله و چالشهای پروتکل مسیریابی. 31-1-1 ظرفیت محدود انرژی. 41-1-2مختصات مکان گرهها. 41-1-3محدودیت منابع سختافزاری. 41-1-4تعداد زیاد گره و قرار گرفتن تصادفی در محیط. 41-1-5 ویژگیهای شبکه و عدم اطمینان محیط فیزیکی. 41-1-6 افزونگی داده. 51-1-7 تنوع کاربرد شبکههای حسگر بیسیم. 51-2 ویژگیهای شبکههای حسگر بیسیم. 51-3 ساختار گره حسگر. 71-4 قالب پیام. 8چکیده فصل اول. 92 کارهای مرتبط. 122-1 مقدمه. 122-2 انواع پروتکلهای مسیریابی. 122-2-1 پروتکلهای مبتنی بر مکان. 132-2-2 پروتکلهای دادهمحور. 142-2-3پروتکلهای سلسله مراتبی. 152-2-4 پروتکلهای مبتنی بر حرکت. 172-2-5پروتکلهای مبتنی بر چند مسیر. 182-2-6پروتکلهای مربوط به شبکههای ناهمگن. 182-2-7 پروتکلهای مبتنی بر کیفیت سرویس. 192-3 مسیریابی متمرکز و توزیع شده. 192-3-1 الگوریتمهای مرکزی. 192-3-2 الگوریتم های توزیع شده. 202-4 محیط سه بعدی. 20چکیدهی فصل دوم. 213 الگوریتم پیشنهادی. 233-1 انواع روشهای مسیریابی. 233-2 مفروضات در نظر گرفته شده درشبیهسازی. 243-3الگوریتم PSO.. 263-4 مراحل الگوریتم پیشنهادی. 28چکیدهی فصل سوم. 354 شبیهسازی و اجرای اگوریتم پیشنهادی. 374-1نرمافزارهای شبیهسازی شبکههای حسگر بیسیم. 374-2شبه کد الگوریتم PSO.. 394-3 طراحی شبیه ساز شبکههای حسگر بیسیم. 414-4 بستهی دادهای. 434-5 شبهکد الگوریتم پیشنهادی. 44خلاصهی فصل چهارم. 465نتایج شبیهسازی. 485-1 مقایسهی عمر شبکه. 495-2 مقایسهی نرخ دریافت اطلاعات. 53چکیدهی فصل 5. 556 نتیجهگیری و پیشنهادات. 576-1خلاصهی بحث. 576-2 خلاصهی نتایج. 576-3 پیشنهادات وکارهای آتی. 58مراجع. 60 فهرست اشکال شکل 1-1. الگوی انتقال چند به یک در شبکههای حسگربیسیم7شکل1-2. ساختارگرهیحسگر.............................. 8شکل 2-1. خوشهوسرخوشهدرروشهایسلسلهمراتبی....... 15شکل2-2. خوشههاوسرخوشههادرروشECHERP.............. 16شکل 3-1.نحوهیحرکتذراتدرالگوریتمPSO.............. 27شکل3-2. مراحلالگوریتمPSO.......................... 28.شکل 3-3. ساختارلایهبندیحسگرهایدردسترسایستگاهاصلی31شکل4-1. فلوچارتالگوریتمPSO........................ 40شکل4-2. شبهکدالگوریتمپیشنهادی.................... 41شکل4-3. منویاصلیشبیهسازطراحیشده................. 42شکل4-4. منویاصلیشبیهسازدرلحظهیازبینرفتناولینحسگر 43شکل4-5. شبهکدالگوریتمپیشنهادی................... 45شکل5-1. مقایسهالگوریتمپیشنهادیباالگوریتمهایAODVوLEACH50شکل5-2. مقایسهیالگوریتمپیشنهادی،HEED,APTEEN,PEGASIS51شکل5-3. مقایسهیالگوریتمپیشنهادیوEDOCR........... 52شکل5-4. مقایسهیالگوریتمپیشنهادیو SEEM........... 53شکل5-5. مقایسهیالگوریتمپیشنهادیبراساسنحوهیاستفادهازوزنهایرابطه (5).................................... 55شکل6-1. شبکهیحسگربیسیم............................ 59 فهرست جداول جدول 1-1. تعدادی ازگرهحسگرهای رایج وکاربردآنها....... 3جدول2-1. انواع پروتکلهای مسیریابی درشبکههای حسگر بیسیم13جدول2-2. مقایسهی الگوریتمهای مسیریابی سلسله مراتبی.. 17جدول4-1. مقایسهی شبیهسازهای شبکههای حسگربیسیم....... 38جدول5-1. ضرایب ثابت رابطهی (5) درشرایط مختلف شبکه... 48جدول5-2. مقایسهی نرخ دریافت داده توسط ایستگاه اصلی درالگوریتمهای مسیریابی............................................ 54فصل اول مقدمه 1 مقدمهشبکههای حسگر بیسیم از تعدادی گرهحسگر تشکیل شده است و به طور معمول اندازهی این گرهها کوچک است و ارزان قیمت هستند. تمامی این گرهها قابلیت دریافت اطلاعات از محیط اطراف خود را دارند، همچنین میتوانند دادههای دریافت شده از محیط را به سمت گرهحسگری که در همسایگی آنها قرار دارد بفرستند و یا از آنها دریافت کنند. در این نوع شبکهها شعاع انتقال دادهها محدود است، همچنین گرهها از نظر پردازشی و ذخیرهی اطلاعات نیز محدودیت دارند. با توجه به محدود بودن انرژی گرهها، بیشتر روشهای مسیریابی در این نوع شبکهها با هدف افزایش طول عمر شبکه مطرح شدهاند. در این پژوهش یک الگوریتم مسیریابی جدید معرفی میشود که مهمترین هدف آن افزایش عمر شبکه است.در بیشتر کاربردهای شبکههای حسگر بیسیم، نحوهی قرار گرفتن گرهها در محیط فیزیکی به صورت تصادفی است ونقشهی خاص و از پیش تعیین شدهای ندارد. گرهها پس از قرار گرفتن در محیط به طور خودکار ساختار شبکه را تشکیل میدهند و برای مدت محدودی به دریافت اطلاعات از محیط اطراف و انتقال آن به ایستگاه اصلی میپردازند. انرژی لازم برای دریافت اطلاعات از محیط و فرستادن اطلاعات به دیگر حسگرها توسط باتریهای تعبیه شده در حسگرها تأمین میشود. بنابراین انرژی این گرهها محدود است و در اکثر کاربردها پس از اتمام انرژی باتری، شارژ مجدد ویا تعویض آن بسیار دشوار و بهطور معمول غیرممکن است. کاربردهای مختلف شبکههای حسگر منجر به تولید گرهحسگرهای زیادی شده است که از نظر معماری، اندازه، مصرف انرژی و شعاع پوشش گره بسیار متفاوت هستند. جدول 1-1 تعدادی از این گرهحسگرها و کاربردی را که دارند نشان میدهد]1[. جدول 1-1. تعدادی از گرهحسگرهای رایج و کاربرد آنهاشکل گرهویژگینامیکی از جدیدترین تکنولوژیهای گرهحسگر است. میتواند فیلم و عکس را رمز کرده و ارسال کند.از پروتکلهایHSPA وWCDMAبرای انتقال داده استفاده میکند. 3Gwaspmoteمصرف انرژی کمی دارد. میتواند از انرژی خورشیدی استفاده کند. زمان راه اندازی شبکهی این نوع گره بسیار کوتاه است.قابل برنامهریزی [1]OTAPرا دارا می باشد. Waspmote Plug&Senseقابلیت اندازهگیری همزمان دما، نور و رطوبت را دارد. شعاع پوشش این گره نسبت به گرههای دیگر کم است. ساختمان سادهای دارد. زمان راهاندازی آن کوتاه است. SquidBee 1-1 ضرورت مسئله و چالشهای پروتکل مسیریابیمحدودیت انرژی همواره مهمترین چالش پیشروی شبکههای حسگر بیسیم بوده است. با توجه به اینکه بخش زیادی از انرژی شبکه صرف ارسال اطلاعات به دست آمده از محیط به سمت ایستگاه اصلی میشود، استفاده از یک روش مسیریابی مناسب میتواند تا حد زیادی طول عمر شبکه را افزایش دهد. ارایهی یک پروتکل مسیریابی برای شبکههای حسگر بیسیم با چالشهایی روبهروست که از محدودیتهای این شبکهها ناشی میشود. همچنین این شبکهها در بسیاری از منابع شبکه نیز محدودیت دارند. برای مثال: پهنای باند ارتباطی[2]، واحد پردازشگر، واحد ذخیرهسازی و انرژی ]2،3[. مهمترین چالشهای پیش روی طراحی پروتکلهای مسیریابی عبارتند از]4،5،6[:با توجه به اینکه گرههای حسگر انرژی لازم را از باتریها میگیرند، بنابراین ظرفیت محدودی دارند. هنگامی که انرژی گره از یک مقدار آستانه کمتر شود، آن گره قادر به ادامه فعالیت خود نخواهد بود و این امر تاثیر منفی زیادی روی شبکه میگذارد. از اینرو محدودیت انرژی بزرگترین چالش برای ارایه یک پروتکل مسیر یابی است .چالش دیگری که در امر ارایه یک پروتکل مسیریابی است مدیریت مکان گره است. تعداد زیادی از پروتکلهای مسیریابی فرض میکنند که هرحسگر مجهز به سیستم مکانیابی جهانی است[3] و یا از الگوریتمهای مکانیابی برای یافتن مکان گره استفاده میکنند]5[.گرههای حسگر علاوه بر انرژی، از لحاظ ذخیرهسازی و پردازش نیز محدود هستند. گرهی حسگر نمیتوانند محاسبات پیچیده و طولانی را انجام دهد و این امر چالشی برای پیشرفت نرم افزاری در شبکههای حسگر بیسیم است. بنابراین برای ارایه یک الگوریتم مسیریابی علاوه بر انرژی باید محدودیت سخت افزاری را نیز در نظر داشت. [1]. Over The Air Programming[2]. Bandwidth[3]. Global Positioning System