دانشگاه زنجان
دانشکده مهندسي
پايان‌نامه براي دريافت درجه کارشناسي ارشد در رشته کامپيوتر
گرايش نرمافزار
عنوان:
ارايه‌ي يک روش مسيريابي براي شبکه‌هاي حسگر بي‌سيم با هدف افزايش طول عمر شبکه
تحقيق و نگارش
عباس کريمي
استاد راهنما
دکتر مجيد مقدادي
شهريور 1393
تعهدنامه‌ي اصالت اثر
اينجانب عباس کريمي متعهد مي‌شوم مطالب مندرج در اين پايان‌نامه با عنوان “ارايه‌ي يک روش مسيريابي براي شبکه‌هاي حسگر بي‌سيم با هدف افزايش طول عمر شبکه” حاصل کار پژوهشي اينجانب است و به دستاوردهاي پژوهشي ديگران که در اين پژوهش از آنها استفاده شده است، مطابق مقررات ارجاع و در فهرست منابع و مآخذ ذکر گرديده است. اين پايان‎‌نامه قبلاً براي براي دريافت هيچ مدرک همسطح و يا بالاتر ارائه نشده است. در صورت اثبات تخلف در (در هر زمان) مدرک تحصيلي صادر شده از طرف دانشگاه از اعتبار ساقط خواهد شد. کليه‌ي حقوق مادي و معنوي اين اثر متعلق به دانشگاه زنجان مي‌باشد.
نام و نام خانوادگي دانشجو:
عباس کريمي
امضا:
چکيده
کاربرد روز افزون شبکه‌هاي حسگر بي‌سيم در زندگي انسان گوياي اهميت زياد اين تکنولوژي است. محدوديت انرژي در عناصر تشکيل دهنده‎ي شبکه‌هاي حسگر بي‌سيم که گره‌حسگرها مي‌باشند همواره به عنوان مهمترين چالش پيش روي اين تکنولوژي مطرح بوده است و به همين دليل بخش اعظم تحقيقات انجام شده در حيطه‌ي شبکه‌هاي حسگر بي‌سيم به موضوع انرژي اختصاص يافته است. با توجه به اينکه نحوه‌ي انتخاب مسيرها براي ارسال اطلاعات در شبکه‌هاي حسگر بي‌سيم تأثير قابل توجهي بر ميزان مصرف انرژي شبکه دارد، در اين پژوهش سعي بر ارايه‎‌ي راهکاري در زمينه‌ي مسيريابي با هدف افزايش طول عمر شبکه شده است. در اين روش با در نظر گرفتن تاريخچه‌ي مصرف انرژي گره‌هاي ‌حسگر، تعداد همسايگان حسگر ارسال کننده‌ي داده، و فاصله مبدأ تا مقصد ارسال داده(تک گام)، راهکاري ارايه شده است که مي‌تواند تأثير بسياري بر افزايش عمر شکه داشته باشد. شبيه‌سازي و مقايسه با روش‌هاي معروف و موفق مسيريابي در شبکه‌هاي حسگر بي‌سيم گوياي شايستگي روش پيشنهادي مي‌باشد.
کلمات کليدي: شبکه‌هاي حسگر بي‌سيم، مسيريابي، الگوريتم PSO، عمر شبکه، محدوديت انرژي
فهرست مطالب
1 مقدمه2
1-1 ضرورت مسئله و چالش‌هاي پروتکل مسيريابي3
1-1-1 ظرفيت محدود انرژي4
1-1-2 مختصات مکان گره‌ها4
1-1-3 محدوديت منابع سخت‌افزاري4
1-1-4 تعداد زياد گره و قرار گرفتن تصادفي در محيط4
1-1-5 ويژگي‌هاي شبکه و عدم اطمينان محيط فيزيکي4
1-1-6 افزونگي داده5
1-1-7 تنوع کاربرد شبکه‌هاي حسگر بي‌سيم5
1-2 ويژگي‌هاي شبکه‌هاي حسگر بي‌سيم5
1-3 ساختار گره‌ حسگر7
1-4 قالب پيام8
چکيده فصل اول9
2 کارهاي مرتبط12
2-1 مقدمه12
2-2 انواع پروتکل‌هاي مسيريابي12
2-2-1 پروتکلهاي مبتني بر مکان13
2-2-2 پروتکلهاي داده‌محور14
2-2-3 پروتکلهاي سلسله مراتبي15
2-2-4 پروتکلهاي مبتني بر حرکت17
2-2-5 پروتکلهاي مبتني بر چند مسير18
2-2-6 پروتکلهاي مربوط به شبکه‌هاي ناهمگن18
2-2-7 پروتکلهاي مبتني بر کيفيت سرويس19
2-3 مسيريابي متمرکز و توزيع شده19
2-3-1 الگوريتمهاي مرکزي19
2-3-2 الگوريتم هاي توزيع شده20
2-4 محيط سه بعدي20
چکيده‌ي فصل دوم21
3 الگوريتم پيشنهادي23
3-1 انواع روش‌هاي مسيريابي23
3-2 مفروضات در نظر گرفته شده درشبيه‌سازي24
3-3 الگوريتم PSO26
3-4 مراحل الگوريتم پيشنهادي28
چکيده‌ي فصل سوم35
4 شبيه‌سازي و اجراي اگوريتم پيشنهادي37
4-1نرم‌افزارهاي شبيه‌سازي شبکه‌هاي حسگر بي‌سيم37
4-2 شبه کد الگوريتم PSO39
4-3 طراحي شبيه ساز شبکه‌هاي حسگر بي‌سيم41
4-4 بسته‌ي داده‌اي43
4-5 شبه‌کد الگوريتم پيشنهادي44
خلاصه‌ي فصل چهارم46
5 نتايج شبيه‌سازي48
5-1 مقايسه‌ي عمر شبکه49
5-2 مقايسه‌ي نرخ دريافت اطلاعات53
چکيده‌ي فصل 555
6 نتيجه‌گيري و پيشنهادات57
6-1خلاصه‌ي بحث57
6-2 خلاصه‌ي نتايج57
6-3 پيشنهادات وکارهاي آتي58
مراجع60

فهرست اشکال
شکل 1-1. الگوي انتقال چند به يک در شبکه‌هاي حسگر بي‌سيم7
شکل1-2. ساختارگره‌ي حسگر8
شکل 2-1. خوشه و سرخوشه در روشهاي سلسله مراتبي15
شکل2-2. خوشه‌ها وسر خوشه‌ها در روشECHERP16
شکل 3-1.نحوه‌ي حرکت ذرات در الگوريتمPSO27
شکل3-2. مراحل الگوريتم PSO28
.شکل 3-3. ساختار لايه‌بندي حسگرهاي در دسترس ايستگاه اصلي31
شکل4-1. فلوچارت الگوريتم PSO40
شکل4-2. شبه کد الگوريتم پيشنهادي41
شکل4-3. منوي اصلي شبيه‌ساز طراحي شده42
شکل4-4. منوي اصلي شبيه‌ساز در لحظه‌ي از بين رفتن اولين حسگر43
شکل4-5. شبه کد الگوريتم پيشنهادي45
شکل5-1. مقايسه الگوريتم پيشنهادي با الگوريتم‌هاي AODV و LEACH50
شکل5-2. مقايسه‌ي الگوريتم پيشنهادي، HEED,APTEEN,PEGASIS51
شکل5-3. مقايسه‌ي الگوريتم پيشنهادي و EDOCR52
شکل5-4. مقايسه‌ي الگوريتم پيشنهادي و SEEM53
شکل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مصرف انرژي کمي دارد. مي‌تواند از انرژي خورشيدي استفاده کند. زمان راه اندازي شبکه‌ي اين نوع گره بسيار کوتاه است. قابل برنامه‌ريزي 1OTAP را دارا مي باشد.
Waspmote Plug&Senseقابليت اندازه‌گيري همزمان دما، نور و رطوبت را دارد. شعاع پوشش اين گره نسبت به گره‌هاي ديگر کم است. ساختمان ساده‌اي دارد. زمان راه‌اندازي آن کوتاه است.
SquidBee
1-1 ضرورت مسئله و چالش‌هاي پروتکل مسيريابي
محدوديت انرژي همواره مهمترين چالش پيش‌روي شبکه‌هاي حسگر بي‌سيم بوده است. با توجه به اينکه بخش زيادي از انرژي شبکه صرف ارسال اطلاعات به دست آمده از محيط به سمت ايستگاه اصلي مي‌شود، استفاده از يک روش مسيريابي مناسب مي‌تواند تا حد زيادي طول عمر شبکه را افزايش دهد. ارايه‌ي يک پروتکل مسيريابي براي شبکه‌هاي حسگر بي‌سيم با چالش‌هايي روبه‌روست که از محدوديت‌هاي اين شبکه‌ها ناشي مي‌شود. همچنين اين شبکه‌ها در بسياري از منابع شبکه نيز محدوديت دارند. براي مثال: پهناي باند ارتباطي2، واحد پردازشگر، واحد ذخيره‌سازي و انرژي ]2،3[. مهمترين چالش‌هاي پيش روي طراحي پروتکل‌هاي مسيريابي عبارتند از]4،5،6[:
1-1-1 ظرفيت محدود انرژي
با توجه به اينکه گره‌هاي حسگر انرژي لازم را از باتري‌ها مي‌گيرند، بنابراين ظرفيت محدودي دارند. هنگامي که انرژي گره از يک مقدار آستانه کمتر شود، آن گره قادر به ادامه فعاليت خود نخواهد بود و اين امر تاثير منفي زيادي روي شبکه مي‌گذارد. از اينرو محدوديت انرژي بزرگترين چالش براي ارايه يک پروتکل مسير يابي است .
1-1-2 مختصات مکان گره‌ها
چالش ديگري که در امر ارايه يک پروتکل مسيريابي است مديريت مکان گره است. تعداد زيادي از پروتکل‌‌هاي مسيريابي فرض مي‌کنند که هرحسگر مجهز به سيستم مکان‌يابي جهاني است3 و يا از الگوريتم‌هاي مکان‌يابي براي يافتن مکان گره استفاده مي‌کنند]5[.
1-1-3 محدوديت منابع سخت‌افزاري
گره‌هاي حسگر علاوه بر انرژي، از لحاظ ذخيره‌سازي و پردازش نيز محدود هستند. گره‌ي حسگر نمي‌توانند محاسبات پيچيده و طولاني را انجام دهد و اين امر چالشي براي پيشرفت نرم افزاري در شبکه‌هاي حسگر بي‌سيم است. بنابراين براي ارايه يک الگوريتم مسيريابي علاوه بر انرژي بايد محدوديت سخت ‌افزاري را نيز در نظر داشت.

1-1-4 تعداد زياد گره و قرار گرفتن تصادفي در محيط
شبکه‌هاي حسگر بي‌سيم به طور کامل وابسته به کاربرد شبکه هستند. در بيشتر کاربردها تعداد زيادي گره به طور تصادفي در محيط فيزيکي قرار داده ميشوند که اين امر تاثير قابل توجهي بر روي کارايي الگوريتم‌هاي مسيريابي دارد.
1-1-5 ويژگي‌هاي شبکه ( عدم اطمينان محيط فيزيکي)
در شبکه‌هاي حسگر بي‌سيم، گره حسگرها در محيطي پويا و غير قابل اطمينان قرار مي‌گيرند. توپولوژي شبکه مدام در حال تغيير است و اين تغييرات از عواملي چون به پايان رسيدن انرژي گره، آسيب فيزيکي گره و يا قطع ارتباط بين گره‌ها ناشي مي‌شود. يک پروتکل مسيريابي مناسب بايد با تغييرات توپولوژي به طور مناسبي همسو باشد.
1-1-6 افزونگي داده
چون در شبکه‌هاي حسگر بي‌سيم افزونگي داده‌ي بالايي وجود دارد و ممکن است اطلاعات يکساني از گره‌هاي مختلف به‌دست آيد، بنابراين در برخي از گره‌ها مي‌توان از تکنيک‌هاي اجماع داده استفاده کرد. اجماع داده‌ها ميتواند تا حد زيادي تعداد بستههاي اطلاعاتي که در شبکه به سمت ايستگاه اصلي منتقل مي‌شوند را کاهش دهد و از اينرو تاثير مثبتي بر طول عمر شبکه دارد.
1-1-7 تنوع کاربرد شبکههاي حسگر بيسيم
با توجه به اينکه اين شبکهها کاربردهاي مختلفي دارند، بنابراين نميتوان ادعا کرد که يک پروتکل مسيريابي براي تمام کاربردها بهينه است. برخي از کاربردها مانند پردازش‌هاي صنعتي و يا صنايع نظامي نياز به پاسخ سريع و تاخير کم دارند. کاربردهاي ديگر مانند اندازه‌گيري دما و نور حساسيت کمتري دارند و در آن‌ها طول عمر شبکه اولويت بيشتري دارد. با توجه به اينکه در بيشتر کاربردها، پياده‌‌سازي يک شبکه‌ي حسگر بي‌سيم واقعي به منظور آزمايش کردن کارايي يک پروتکل مسيريابي مقرون به صرفه نيست، به همين دليل از نرم‌افزارهاي شبيه‌سازي استفاده مي‌شود. در اين شبيه‌سازها مي‌توان شبکه والگوريتم‌هاي مسيريابي را مطابق با کاربرد آن در محيط واقعي شبيه‌سازي کرد. در فصل پنجم تعدادي از نرم‌افزارهاي شبيه‌سازي شبکه‌هاي حسگر بي‌سيم بررسي شده است.
1-2 ويژگي‌هاي شبکه‌هاي حسگر بي‌سيم
محدوديت انرژي باعث ميشود که بيشتر پروتکلهاي مسيريابي ارايه شده در ساير شبکه‌هاي بي‌سيم براي شبکه‌هاي حسگر بي‌سيم مناسب نباشد. براي مثال انتقال سيل‌آسا که در شبکههاي کامپيوتري استفاده مي‌شود براي شبکههاي حسگر بيسيم هزينهي زيادي داشته و طول عمر شبکه را به طور قابل توجهي کاهش ميدهد]7[. البته براي پياده سازي انتقال سيل‌آسا در شبکههاي حسگر بيسيم از يک روش جايگزين استفاده ميشود که به روش شايعه‌پراکني معروف است]8[. در اين روش وقتي گره‌اي مي‌خواهد دادهاي را به سمت گره‌ي ديگر بفرستد به صورت تصادفي تعداد کمي از همسايگان خود را انتخاب ميکند، اما در روش سيل‌آسا تمام همسايگان انتخاب ميشوند. شبکههاي حسگر بيسيم ويژگي‌هايي دارند که آنها را از ديگر شبکه‌ها مانند MANET4 و سيستم‌هاي تلفن همراه5 متمايز ميکند. تعدادي از اين ويژگي‌ها که در انجام اين تحقيق مد نظر قرار گرفته‌است عبارتند از:
تراکم زيادگره‌ها در محيط: بهطور معمول شبکههاي حسگر بي‌سيم نسبت به ديگر شبکهها چگالي بيشتري داشته و از اين‌رو امواج مغناطيسي در محيط اين نوع شبکهها بيشتر است.
محدوديت باتريهاي تامين کننده انرژي: انرژي لازم براي انتقال اطلاعات در شبکه و پردازش دادهها توسط باتري‌هايي فراهم ميشود که از لحاظ ميزان انرژي محدودند ودر بيشتر کاربرد‌ها پس از اتمام انرژي قابل شارژ و يا تعويض کردن نيستند.
محدوديت ميزان ذخيره سازي، پردازش و انتقال داده: گره‌هاي حسگر نسبت به شبکههاي ديگر فضاي ذخيره‌سازي اندکي دارند و از نظر حجم محاسبات و همچنين طول مسافتي که داده را مي‌فرستند بسيار محدودند.
شکل‌گيري خودکار شبکه: در اين نوع شبکهها وقتي گره‌اي در محيط قرار ميگيرد به صورت خودکار با محيط اطراف و ديگر گره‌هاي همسايه خود ارتباط برقرار ميکند.
عدم قابليت اطمينان: با توجه به اينکه گره‌ها در محيط فيزيکي در مکانهايي قرار ميگيرند که به طور معمول دسترسي به آنها غير ممکن است، قابل اطمينان نيستند و ممکن است دچار آسيب فيزيکي شوند و يا مورد نفوذ بيگانه قرار گيرند.
افزونگي زياد دادهها: چون اين نوع شبکهها در نقاط مختلف تراکم زيادي دارند، ممکن است يک مکان خاص توسط چندين گره پوشش داده شود، بنابراين اطلاعاتي که هر يک از اين گره‌ها از آن نقطهي خاص به دست ميآورند يکسان است.
متناسب با کاربرد شبکه: شبکههاي حسگر بي‌سيم با توجه به کاربردي که دارند با يکديگر متفاوت هستند و متناسب با کاربرد طراحي ميشوند.
الگوي انتقال چند به يک: در بيشتر شبکههاي حسگر بي‌سيم، اطلاعات به دست آمده از محيط از سوي حسگرها به سمت يک ايستگاه اصلي انتقال مييابند. در شکل 1-1 اين الگو نشان داده شده است.
شکل 1-1. الگوي انتقال چند به يک در شبکه‌هاي حسگربي‌سيم
توپولوژي متغير شبکه: توپولوژي شبکههاي حسگر بيسيم مدام در حال تغيير است و اين تغيير از مواردي چون آسيب ديدن گره‌ها، اضافه شدن گره‌هاي جديد و يا اتمام انرژي گره‌ها ناشي مي‌شود.
مقياس پذيري: پروتکلهاي مسيريابي بايد با اندازهي شبکه تطابق داشته باشند. همچنين ممکن است تمام گرهها تواناييهاي يکساني نداشته باشند و يا ارتباطات بين گرهها متقارن نباشد. يک پروتکل مسيريابي کارآمد بايد اين ناسازگاري‌هاي شبکه حسگر بي‌سيم را مديريت کند.
1-3 ساختار گره‌ حسگر
در بيشتر موارد تعدادي از مراحل الگوريتم‌هاي مسيريابي در حسگرها اجرا مي‌شوند، بنابراين يک گره‌ حسگر بايد مقداري هوشمندي داشته باشد. البته اين هوشمندي به دليل محدوديت‌ انرژي و همچنين محدوديت سخت افزاري بسيار محدود است. به‌طور معمول معماري يک گره‌ حسگر هوشمند به صورتي که در شکل 1-2 نشان داده شده است]28[، در نظر گرفته مي‌شود.
شکل1-2. ساختارگره‌ي حسگر
1-4 قالب پيام
در شبکههاي حسگر بيسيم داده‌هاي دريافت شده از محيط فيزيکي در قالب بستههايي قرار مي‌گيرند و به گره‌هاي همسايه و يا ايستگاه اصلي ارسال مي‌شوند. با توجه به نوع کاربرد شبکه، اندازه و قالب اين بستهها متفاوت است. در اکثر کاربردها، اندازهي اين بستهها در يک شبکه‌ي حسگر بي‌سيم يکسان و ثابت است. همچنين اندازه اين بستهها ميتواند به صورت پويا تغيير کند، به نحوي که در يک شبکه بسته‌هاي حاوي داده‌ها، اندازه‌هاي گوناگوني داشته باشند. شکل 1-3 يکي از اين قالب‌هاي پيام را نشان مي‌دهد که در بيشتر پروتکل‌هاي سلسله مراتبي استفاده مي‌شود ]9[.
شکل 1-3. نمونه قالب پيام در شبکه‌هاي حسگر بي‌سيم

در ادامه، ساختار اين مقاله به اين صورت است که در فصل دوم کارهاي مرتبط با مسيريابي در شبکه‌هاي حسگر بي‌سيم مطرح گرديده است، فصل سوم الگوريتم مسيريابي ارايه شده‌ي اين مقاله را شرح مي‌دهد، در فصل چهارم نحوه‌ي شبيه‌سازي شبکه‌ي حسگر بي‌سيم و الگوريتم مسيريابي پيشنهادي بررسي شده، در فصل پنجم نتايج حاصل از شبيه‌سازي و مقايسه با ديگر پروتکل‌هاي مسيريابي نمايش داده شده است و در پايان نتيجه‌گيري و کارهاي آتي بيان شده است.
چکيده فصل اول
در اين فصل ويژگيهاي شبکههاي حسگر بيسيم و ضرورت مسئله‌ي مسيريابي در اين شبکه‌ها مطرح شد. همچنين چالش‌هايي که در مقابل ارايه‌ي يک پروتکل مسيريابي است بررسي شدند. تفاوت بين اين نوع شبکهها با ساير شبکههاي بي‌سيم بيان شد. در اين فصل دريافتيم که شبکههاي حسگر هم ازنظر سخت‌افزاري و هم از نظر نرم افزاري تفاوت زيادي دارند، بنابراين هريک از انواع اين شبکه‌ها به پروتکل‌هاي خاص خود نياز دارند و بايد منطبق با کاربرد شبکه طراحي شوند. محدوديت انرژي به عنوان مهمترين چالش شبکه‌هاي حسگر بي‌سيم مطرح شد که در ارايهي يک پروتکل مسيريابي بهينه بايد به خوبي کنترل شود.
فصل دوم
بررسي کارهاي
مرتبط
2 کارهاي مرتبط
2-1 مقدمه
محدوديت انرژي در شبکه‌هاي حسگر به‌عنوان مهمترين چالش پيش‌روي پروتکل‌هاي مسيريابي براي بي‌سيم تحقيقات بسياري براي ارايه‎‌ي يک روش مناسب مسيريابي با هدف افزايش طول عمر شبکه صورت گرفته است. با توجه به ويژگي‌هاي پروتکل‌هاي مسيريابي و همچنين ويژگي‌هاي شبکه‌ي حسگر بي‌سيم، پروتکل‌هاي مسيريابي به چند دسته تقسيم مي‌شوند. در ادامه انواع پروتکل‌هاي مسيريابي و تعدادي از کارهاي انجام شده در زمينه‌ي مسيريابي در شبکه‌هاي حسگر بي‌سيم بررسي شده است.
2-2 انواع پروتکل‌هاي مسيريابي
همانطور که در فصل اول اشاره شد يکي از محدوديت‌هاي شبکه‌هاي حسگر اين است که گره‌هاي حسگر داراي انرژي محدودي هستند. انرژي لازم براي انتقال اطلاعات در يک شبکهي حسگر بيسيم توسط باتريهاي تعبيه شده در گره تامين مي‌شود. هنگامي که اين انرژي پايان يافت تعويض اين باتريها بسيار دشوار و در بيشتر موارد غير ممکن است. بنابراين بسياري از روش‌ها و پروتکل‌هاي شبکه‌هاي غير بي‌سيم براي استفاده در شبکههاي حسگر ناکارآمد است. در زمينهي مسيريابي، روشها و پروتکل‌هاي بسياري ارائه شده است که هدف بيشتر اين روشها افزايش طول‌عمر شبکه است. در اين فصل تعدادي از اين روشها به همراه چند ديدگاه براي دسته‌بندي آنها ذکر خواهد گرديد. از يک ديدگاه]10[ ميتوان روش‌هاي مسيريابي را به هفت گروه تقسيم کرد که در جدول 2-1 نشان داده شده است:
در اين بخش به طور خلاصه ويژگيهاي مهم اين گروه‌ها بيان شده و مناسب‌ترين پروتکل از نظر نتايج شبيه‌سازي ويا مهمترين پروتکل از نظر ميزان کاربرد در هرگروه معرفي خواهند شد.
جدول2-1. انواع پروتکل‌هاي مسيريابي در شبکه‌هاي حسگر بي‌سيم]10[
پروتکلهانوع پروتکلMECN, SMECN, GAF, GEAR, Span, TBF, BVGF, GeRaFمبتني بر مکان6SPIN, Directed Diffusion, Rumor Routing, COUGAR,
ACQUIRE, EAD, Information-Directed Routing, Gradient-
Based Routing, Energy-aware Routing, Information-Directed Routing
دادهمحور7LEACH, PEGASIS, HEED, TEEN, APTEENسلسله مراتبي8SEAD, TTDD, Joint Mobility and Routing, Data MULES,
Dynamic Proxy Tree-Base Data Disseminationمبتني بر حرکت9Sensor-Disjoint Multipath, Braided Multipath, N-to-1 Multipath Discoveryمبتني بر مسيرهاي چندگانه10IDSQ, CADR, CHR مبتني بر شبکههاي ناهمگن11SAR, SPEED, Energy-aware routingمبتني بر کيفيت سرويس12
2-2-1 پروتکلهاي مبتني بر مکان
در اين گروه‌، حسگرها در شبکه‌ي بيسيم بر اساس مختصات مکاني خود حسگر آدرس‌دهي مي‌گردند. بنابراين با دانستن مختصات هر حسگر ميتوان ميزان انرژي لازم براي انتقال اطلاعات بين حسگرها را تخمين زد.
PELCR-TP ]11[ يکي از روشهايي است که در اين گروه قرار ميگيرد و توسطY.Cheng و همکاران در سال 2013 معرفي شد و در مقايسه با روشهاي قبل از خود نتايج بهتري ارايه کرده است. در اين روش دو گره که در دو سوي يک ارتباط قرار مي‌گيرند اطلاعات مربوط به ديگر ارتباطات خود را به گره‌ي ديگر اطلاع ميدهند. به عبارت ديگر تاريخچهاي از گذشته يک ارتباط تعيين کننده مسير بعدي براي انتقال داده است. همچنين اين روش از 13BAS استفاده ميکند تا گره‌هاي با عملکرد نامناسب را شناسايي واز انتقال اطلاعات به اين گره‌ها اجتناب مي‌کند. نتايج ارايه شده در مقاله نشان ميدهد که اين روش نسبت به ديگر پروتکل‌هاي قبل از خود مانندGAF14 ]12[ و MECN15 ]13[ براي افزايش طول عمر شبکه موفقتر بوده است.
2-2-2 پروتکلهاي دادهمحور
در اين دسته از پروتکلهاي مسيريابي هنگامي که يک گره‌ دادهاي را به سوي ايستگاه اصلي ارسال مي‌نمايد گره‌‌هاي مياني مي‌توانند روشهاي مربوط به اجماع‌داده16را روي اطلاعات در حال انتقال اعمال نمايند. اين نوع مسيريابي موجب ذخيره بيشتر انرژي در شبکه ميشود چون از تعداد بستههاي در حال انتقال در شبکه ميکاهد. L.villa،R.Araujo وA.Loureio ]14[ درآوريل 2013 روش DRINA17 را معرفي کردند. اين روش نسبت به روشهاي ديگر نتايج قابل قبول‌تري ارايه کرده است. شيوهي کار اين الگوريتم بدين صورت است که براي ساخت درخت‌ِ مسير تعداد بسيار کمي داده بين حسگرها انتقال مييابد. همچنين تعداد مسيرهاي به روي هم افتاده را بيشينه ميکند و در نهايت از يک اجماع داده قابل اطمينان با نرخ بسيار بالا استفاده ميکند. رعايت اين نکات در ساخت درخت مسير باعث افزايش طول عمر شبکه در اين روش شده است.
SPIN18 ]15[ يکي ديگر از اولين پروتکلهايي است که براي اصلاح روش انتقال سيل آسا19 در يک شبکه حسگر مطرح گرديد‌. در اين پروتکل هر حسگر اين قابليت را دارد که ميزان انرژي لازم براي فرستادن، دريافت و يا محاسبه کردن را تخمين بزند. بنابراين گره حسگرها ميتوانند به صورت بهينه از منابع خود استفاده نمايند. دو مکانيزم اصلي SPIN قابليت مذاکره‌ي گره حسگرها با يکديگر و همسو شدن با ميزان منابع در دسترس است. مذاکره قبل از ارسال اطلاعات صورت ميگيرد، بنابراين از انتقال دادههاي غير مفيد و يا افزونه جلوگيري ميکند. در اين روش از فراداده20 براي توصيف دادهها استفاده ميشود که اندازهي اين فراداده بر اساس کاربرد شبکه بسيار کوچکتر از خود داده است. با توجه به فرادادههايي که هرگره از همسايگان خود بهدست مي‌آورد ميتواند از افزونگي و روي هم افتادن مسيرها جلوگيري کند. همچنين هرگره داراي قسمتي به عنوان مدير منابع است که توسط آن ميتواند منابع خود را نظارت کند و با آن همسو شود.
2-2-3 پروتکلهاي سلسله مراتبي
پروتکلهايي که در اين دسته قرار ميگيرند از مفهوم خوشهبندي استفاده ميکنند. درهرخوشه تعدادي گره قرارگرفته است و يکي از اين گره‌ها به عنوان سرخوشه تعيين مي‌گردد. جمع‌آوري اطلاعات ازاعضاي خوشه توسط سرخوشه صورت مي‌گيرد وسپس به طور مستقيم (تک گامي) و يا از طريق سرخوشه‌هاي ديگر(چندگامي) به ايستگاه اصلي منتقل ميگردند. عمدهي روشهاي مسيريابي که ازمفهوم خوشه‌بندي ‌استفاده مي‌کنند با هدف افزايش طول عمر شبکه به وجود آمده‌اند. درشکل2-1مفهوم خوشه‌بندي نشان داده شده است.
شکل 2-1. خوشه و سرخوشه در روشهاي سلسله مراتبي
Nikolidakis و همکاران ]16[ در سال 2013 روشي را براي خوشه‌بندي مطرح کردند که ECHERP21 نام گرفت و به معناي تساوي در انتخاب سرخوشههاست. اين روش، شبکه‌ي حسگر بيسيم را به صورت يک سيستم خطي مدل ميکند و از الگوريتم انتخاب گوس22استفاده مي‌کند و در نهايت ترکيبي از حسگرها را به عنوان يک خوشه در نظر ميگيرد. در اين روش پس از انتخاب خوشه‌ها به صورت پويا، در هر خوشه گره‌ حسگري به عنوان سرخوشه انتخاب ميگردد که مجموع انرژي مصرفي خوشه کمينه شود. همانطور که در بالا نيز ذکر شد با نگاشت هر خوشه به يک سيستم خطي ميتوان از الگوريتم گوس براي انتخاب سرخوشه استفاده کرد. شکل 2-2 نوع شبکه و خوشهبندي اين روش را نشان ميدهد.
شکل2-2. خوشه‌ها وسر خوشه‌ها در روشECHERP
جدول 2-2 مقايسه‌ي بين تعدادي از الگوريتم‌هاي سلسله مراتبي را بر اساس پارامترهاي مختلف نشان مي‌دهد]17[.

جدول2-2. مقايسه‌ي الگوريتم‌هاي مسيريابي سلسله مراتبي
تاثيردر مصرف انرژي
پيچيدگي روش
توازن بار
مقياس‌‌پذيري
تأخير دريافت
ثبات خوشه
نام پروتکلبسيار ضعيفپايينمتوسطبسيار پايينبسيار کممتوسطLEACHخوببالاخوبپايينکمبالاTEENمتوسطبسياربالامتوسطپايينکمبسيار پايينAPTEENمتوسطمتوسطمتوسطبالاخيلي کممتوسطGAFخوببالامتوسطبسيار پايينمتوسطمتوسطCSPEAبسيار خوببالامتوسطبسيار پايينبسيار زيادپايينPEGASISمتوسطبسيار پايينمتوسطمتوسطبسيار کممتوسطSEPضعيفپايينضعيفبسيار بالامتوسطبالاHGMRبالابسيار پايينخوببالابسيار کمبالاDEECبسيار خوبمتوسطخيلي خوبمتوسطمتوسطبالاDWEHCبسيار خوبمتوسطخيلي خوببالابسيار کمبالاIBLEACHمتوسطمتوسطمتوسطمتوسطمتوسطبالاHEEDضعيفمتوسطبسيار ضعيفبسيار پايينزيادپايينCCSبسيار ضعيفبسياربالاخوببسيار پايينکمبالاBCDCP
2-2-4 پروتکلهاي مبتني بر حرکت
در اين دسته از پروتکلها ايستگاه اصلي و يا گره‌‌ها و يا هردو ميتوانند حرکت کنند، بنابراين بايد الگوريتم به نحوي کار کند که بتواند اين تغييرات پويا را در شبکه کنترل کند.
A.Mahapatro وP.Khilar ]18[ در سال 2013 از خوشهبندي در شبکهاي استفاده ميکند که در آن گره‌‌ها متحرک هستند. نحوه‌ي انتخاب سرخوشه به اين صورت است که هر گره بر اساس انرژي باقيماندهي خود و اطلاع از ميزان انرژي گره‌‌هاي همسايه مي‌تواند به عنوان سرخوشه انتخاب شود. هنگامي که يک گره به عنوان سرخوشه در نظر گرفته ميشود، ديگر گره‌‌ها بر اساس اينکه با کدام يک از اين سرخوشهها ارتباط پايدارتري دارند عضو خوشه مربوطه ميشوند. در اين روش ممکن است خوشهها از نظر تعداد گره‌‌ها با يکديگر تفاوت زيادي داشته باشند که از معايب اين روش محسوب مي‌گردد. وقتي انرژي سرخوشه کاهش ميبابد گره‌‌هاي ديگر که در همان خوشه هستند اگر بتوانند ارتباط مناسبي با سرخوشه ديگري که انرژي بيشتري دارد، داشته باشند از خوشه فعلي خود خارج شده و عضو خوشه ديگري مي‌گردند. در برخي از روشها فقط ايستگاه اصلي حرکت ميکند. براي مثال K.Jafri و همکاران ]19[ براي افزايش طول عمر شبکه از روش سلسله مراتبي معروفPEGASIS23 ]20[ استفاده ميکنند و براي افزايش طول عمر شبکه مسيرهاي خاصي براي حرکت ايستگاه اصلي انتخاب مي‌کند و در هر مسير نقاطي را مشخص ميکند که در آن ايستگاه اصلي مدت محدودي ثابت مي‌شود. نتايج ارايه شده در اين روش نشان ميدهد که اين الگوريتم نسبت به روشهاي ديگر نرخ تحويل دادهي بيشتري دارد.
2-2-5 پروتکلهاي مبتني بر چند مسير
در اين دسته از پروتکلها از هر حسگر به سوي ايستگاه اصلي چند مسير وجود دارد و هر حسگر مي‌تواند بر اساس الگوريتم مسيريابي اطلاعات را از هر يک از اين مسيرها به سمت ايستگاه اصلي منتقل کند. همچنين در اين گونه روشها ميتوان هر بسته داده را به تعداد بسته کوچکتري تقسيم نمود و هر يک از اين بستهها را از مسير متفاوتي به ايستگاه اصلي منتقل کرد. H.Hamadi و R.Chen ]21[ در سال 2012 الگوريتمي ارايه کردند که در آن چند مسير براي انتقال اطلاعات از مبدا به مقصد وجود دارد. هدف آنها علاوه بر افزايش طول عمر شبکه اين بود که شبکه و اطلاعات منتقل شده در آن از امنيت و قابليت اطمينان کافي برخوردار باشند. آنها براي دستيابي به تمامي اين اهداف آن را به عنوان يک مسئله بهينه سازي در نظر گرفتند تا بدين وسيله بتوانند بهترين سطح افزونگي داده را تعيين کنند. همچنين از روش توزيع شده مبتني بر راي‌گيري استفاده نمودند تا بدين وسيله نفوذ در شبکه را تشخيص دهند و در نهايت گره‌‌هاي مخرب را شناسايي کرده و آنها را از شبکه حذف کنند.

2-2-6پروتکلهاي مربوط به شبکههاي ناهمگن
شبکههاي ناهمگن از دو نوع حسگر تشکيل شدهاند، به طوري که تعدادي از حسگر‌ها معمولي هستند و انرژي آنها محدود است و نوع ديگر گره‌‌هايي هستند که از نظر انرژي محدوديت زيادي ندارند و نسبت به ديگر حسگرها داراي انرژي بسيار زيادي هستند. S.Taruna و همکاران ]22[ در سال 2013 يک روش سلسله مراتبي براي استفاده در شبکههاي حسگر بيسيم با هدف افزايش طول عمر شبکه معرفي کردند. خوشه‌بندي اين روش مانند الگوريتم LEACH ]23[ است، با اين تفاوت که علاوه بر ميزان انرژي حسگرها، پارامتر تراکم حسگرها را نيز در الگوريتم انتخاب سرخوشه به کار ميبرد. اندازهي هر خوشه نيز بر اساس تراکم حسگرها در نقاط مختلف شبکه تعيين ميگردند. در اين روش حسگرها ناهمگن هستند، ولي انرژي هيچ حسگري بي نهايت در نظر گرفته نميشود و پس از يک مدت شانس انتخاب شدن مجدد به عنوان سرخوشه را از دست ميدهند.
2-2-7 پروتکلهاي مبتني بر کيفيت سرويس
در برخي از کاربردهاي شبکههاي حسگر بيسيم تنها عمر شبکه مد نظر نيست، بلکه سرويسهاي ديگري همچون عدم تاخير، قابل اعتماد بودن اطلاعات منتقل شده به ايستگاه اصلي و يا تحمل‌پذيري در برابر خطا نيز بايد فراهم شوند. 24SAR ]24[ يکي از اولين پروتکلهاي مسيريابي است که مفاهيم کيفيت سرويس را در الگوريتم مسيريابي وارد کرد. مبناي کار اين پروتکل بر اساس جدول مبتني بر روشهاي چندمسيري است. از هر حسگر چند مسير به سمت ايستگاه اصلي وجود دارد و بر اساس اينکه بسته داده از چه نوعي است و يا چه اولويتي دارد يک مسير انتخاب ميگردد. براي مثال اگر لازم باشد اطلاعاتي بدون تاخير به ايستگاه اصلي انتقال يابند از مسير کوتاهتر استفاده ميشود و يا اگر لازم است گزارش دادهاي قابليت اطمينان کافي داشته باشد از مسيري که در آن ارتباطات مطمئن‌تري وجود دارد استفاده مي‌شود.
2-3 مسيريابي متمرکز و توزيع شده
طبقهبندي ديگري نيز براي پروتکلها و الگوريتمهاي مسيريابي در نظر گرفته ميشود]25[ که عبارتند از:
2-3-1 الگوريتمهاي مرکزي
در اين الگوريتمها يک حسگر و يا ايستگاه اصلي آگاه از توپولوژي شبکه مسيرهاي انتقال اطلاعات در شبکه را مشخص ميکند. تعداد اين الگوريتمها زياد نيست چون انتقال کل اطلاعات به يک حسگر و يا انتقال اطلاعات هر مسير از ايستگاه اصلي به همه حسگرها هزينه زيادي دارد و براي شبکههاي حسگري که محدوديت انرژي دارند مناسب نيست. البته اين روشها براي شبکههاي کوچکي که در آن ايستگاه اصلي به تمام حسگرها دسترسي دارد مناسب خواهد بود، چون تمام مسيرها در ايستگاه اصلي تعيين مي‌شوند و به طور مستقيم به گره‌‌هاي مربوطه اطلاع داده ميشود و از اين رو انرژي لازم براي مشخص کردن مسير در حسگر ذخيره ميگردد.
2-3-2 الگوريتم هاي توزيع شده
در اين الگوريتم ها مسيرها به صورت توزيع شده در حسگرها تعيين ميگردد و سپس در قالب پيام‌هاي خاصي به ديگر حسگرها انتقال مييابند. بيشتر روش‌هاي مسيريابي ارايه شده براي افزايش طول عمر شبکه در اين دسته قرار مي‌گيرند. چون يافتن مسيرها به صورت مرکزي انجام مي‌شود و اطلاع دادن مسيرها به تمامي حسگرها نياز به هزينه‌ي زيادي دارد و اين امر مي‌تواند تاثير منفي بسياري بر کارايي پروتکل مسيريابي داشته باشد.
در روش پيشنهاد شده در اين پژوهش از مزيت هريک از روش‌هاي مرکزي و توزيع شده استفاده شده است.

2-4 محيط سه بعدي
اگرچه در اکثر روشها و الگوريتمهايي که در اين بخش مطرح شدند شبکه‌ي حسگر بيسيم به صورت دو بعدي در نظر گرفته شده است، اما ممکن است قرار گرفتن حسگرها در يک محيط به صورتي باشد که يک شبکه سه بعدي را تشکيل دهند. بنابراين بايد در نظر داشت که فرض دوبعدي بودن يک شبکهي حسگر هميشه درست نبوده و در يک محيط واقعي در بسياري از موارد شبکه به صورت سه بعدي است. براي مثال گره‌‌هايي را در نظر بگيريد که روي درختان يک جنگل قرار ميگيرند يا يک شبکه زير دريايي و يا گره‌‌هاي که در يک ساختمان متشکل از چند طبقه قرار گرفتهاند]26[.
چکيده‌ي فصل دوم
در اين فصل انواع پروتکل‌هاي مسيريابي به‌طور مختصر معرفي گرديدند و در هر گروه تعدادي از مقالات و روش‌هايي که در سال‌هاي اخير مطرح شده‌اند و يا نتايج بهتري نسبت به ديگران ارايه کردهاند مورد بررسي قرار گرفتند.
با توجه به ويژگي‌هاي محيط و کاربرد شبکه‌ي حسگر، پروتکل‌هاي مسيريابي به چند دسته تقسيم مي‌شوند که در اين فصل هر دسته و الگوريتم‌هاي مربوطه بررسي شدند. در بيشتر الگوريتمهاي ارايه شده هدف نهايي الگوريتم افزايش طول عمر شبکه است، بنابراين نتايج اين روش‌ها مي‌تواند معيار مناسبي براي ارزيابي الگوريتم ارايه شده در اين مقاله باشد.
فصل سوم
متدولوژي والگوريتم پيشنهادي

3 الگوريتم پيشنهادي
يکي از مهمترين چالش‌هاي شبکه‌هاي حسگر بي‌سيم محدوديت انرژي است، بنابراين هنگام ارايه‌ي يک پروتکل مسيريابي بايد نسبت به آن توجه زيادي داشت. به‌همين منظور الگوريتم پيشنهادي اين پژوهش با هدف افزايش عمر شبکه مطرح شده است. در اين بخش مراحل الگوريتم و همچنين شرايطي که براي ارايه‌ي اين الگوريتم لازم است بيان شده است.
3-1 انواع روش‌هاي مسيريابي
به طور معمول نحوه‌ي يافتن مسيرها و آگاه کردن همه گره‌حسگرها به سه دسته‌ي کلي تقسيم مي‌شود که عبارتند از:
الگوريتم‌هاي مرکزي: اين الگوريتم‌ها نياز به آگاهي از کل شبکه دارند. اما تعداد اين الگوريتم‌ها بسيار کم است، چون تعداد پيام‌هايي که براي آگاه کردن گره حسگرها از توپولوژي شبکه بايد انتقال يابند هزينه‌ي زيادي دارد. در کاربردهايي که ايستگاه اصلي توپولوژي کل شبکه را مي‌داند، مي‌توان اين الگوريتم‌ها را در ايستگاه اصلي اجرا نمود و سپس مسيرها را به گره‌ها اطلاع داد، اما اين روش نيز هزينه‌ي بالايي دارد.
الگوريتم‌هاي توزيع شده: اين الگوريتم‌ها به‌صورت توزيع شده در کل شبکه اجرا مي‌گردند و گره‌ها براي ارتباط با يکديگر از انتقال‌ پيام25 استفاده مي‌کنند.
الگوريتم‌هاي مبتني برمکان: در اين روش هر گره از محيط نزديک خود اطلاعات محدودي به‌دست مي‌آورد و سپس بر اساس اين اطلاعات الگوريتم را اجرا مي‌کند.
هريک از اين روشهاي مسيريابي به شرايط خاص خود نياز دارند. براي مثال الگوريتم‌هاي توزيع شده نياز به ارتباط مناسب هر دو گره دارند، الگوريتم‌هاي مبتني بر مکان وابسته به کارايي روش‌هايي هستند که اطلاعات جغرافيايي محلي را فراهم مي‌کنند.
3-2 مفروضات در نظر گرفته شده درشبيه‌سازي
در اين پژوهش براي بيان ويژگي‌هاي شبکه و نحوه‌ي کار الگوريتم پيشنهادي فرض‌هايي در نظر گرفته شده است که در ذيل به آنها اشاره شده است.
* براي نمايش شبکه، گراف بدون جهتG(N,A) در نظر گرفته شده است که در آن N مجموعه‌ي تمام گره‌ها وA مجموعه‌ي تمام ارتباطات بين گره‌ها است. هر ارتباط به صورت(i,j) نمايش داده شده است وi,j ? N .
* fi مجموعه‌ي گره‌هايي است که از گره‌ي i قابل دسترسي هستند.
* مقصد نهايي تمام اطلاعات به‌دست آمده ازمحيط ايستگاه اصلي است.
* يک ايستگاه اصلي وجود دارد.
* ميزان انرژي هر گره در ابتداي قرار گرفتن در شبکه و شروع کار آن Ei است.
* براي محاسبه‌ي ميزان انرژي مصرف شده توسط هر گره‌ي حسگر، مدل انرژي رابطه‌ي(1)، در نظر گرفته شده است]27[. در اين مدل، انرژي لازم ETx براي فرستادن l بيت داده به مسافت d به‌صورت رابطه‌ي (1) مي‌باشد.
(1)
همچنين انرژي لازم ERx براي دريافت l بيت داده از رابطه‌ي(2) محاسبه مي‌شود:
ERx (l) = lEelec (2)
در اين روابط?fs و ?mp انرژي تقويت کننده‌ها26 هستند و در کاربردهاي مختلف متفاوتند. d0 فاصله‌ي معيني است که با توجه به نوع حسگر مشخص مي‌شود.
* Qi نرخ تعداد بسته‌هاي داده‌اي است که توسط گره i به سمت ايستگاه اصلي فرستاده مي‌شود. به طور معمول روش‌هايي که در آن اطلاعات به‌دست آمده از محيط به ايستگاه اصلي گزارش داده مي‌شوند به سه دسته تقسيم مي‌شوند. اين دسته‌ها عبارتند از :
> زمان‌محور27: هر گره با نرخ ثابت و مشخصي اطلاعات به‌دست آمده از محيط را گزارش مي‌کند.
> رويداد‌محور28: گره زماني داده‌هاي خود را ارسال مي‌کند که توسط يک رويداد خاص تحريک شود.
> درخواست‌محور29: زماني داده ارسال مي‌شود که ايستگاه اصلي و يا گره‌ي ديگري درخواست اطلاعات کند.
البته ممکن است در برخي از کاربردها ترکيبي از ‌روش‌هاي گزارش اطلاعات استفاده شود .در الگوريتم پيشنهادي اين پژوهش هر دو روش زمان‌محور و رويداد‌محور بررسي شده‌اند.
* ايستگاه اصلي از تعداد حسگرها و مساحت محيط آگاهي دارد. به عبارت ديگر چگالي شبکه مشخص است. البته اين آگاهي مي‌تواند تقريبي باشد.
* محيط قرار گيري گره‌حسگرها به صورت دو بعدي در نظر گرفته شده است.
3-3 الگوريتم PSO
در روش ارائه شده در اين فصل از الگوريتم PSO30 استفاده شده است، بنابراين قبل از ارا‌ئه‌ي جزئيات روش پيشنهادي، الگوريتم PSOبه‌طور مختصر بررسي خواهد شد. Kenedy و Eberhart ]29،30[ در سال 1997 الگوريتم PSO را معرفي کردند. اين الگوريتم اولين بار براي شبيه‌‌سازي شبکه‌هاي اجتماعي استفاده شد. PSO از خانواده‌ي الگوريتم‌هاي تکاملي محسوب مي‌شود و شباهت زيادي به الگوريتم ژنتيک دارد.
بر اساس نتايج به‌دست آمده در ]32 ،31[، براي مسائل پيوسته جوابهاي به‌دست آمده از الگوريتم PSO نسبت به ديگر الگوريتم‌هاي تکاملي به مقدار بهينه نزديکتر است واز نظر زماني نسبت به روشهاي ديگر هزينه‌ي کمتري دارد.
الگوريتم PSO در ابتدا تعدادي از جواب‌هاي منتخب (و به‌طور معمول تصادفي و در يک بازه‌ي مشخص) را در نظر مي‌گيرد. در اين روش به هر جواب منتخب ذره31 گفته مي‌شود. اين ذرات با يکديگر در ارتباط هستند و پس از ارزيابي توسط يک تابع شايستگي32 به سمت جواب بهينه حرکت مي‌کنند. اين روال با توجه به تعداد تکرارهاي مشخص شده ادامه مي‌يابد. مکان هر ذره بر اساس بردار شتاب‌‎33 به‌دست آمده از تساوي (3) تغيير مي‌کند و تساوي (4) تابع حرکت ذرات را نشان مي‌دهد. همچنين شکل‌هاي 3-1 و3-2 به ترتيب بيانگرنحوه‌ي حرکت ذرات و مراحل الگوريتمPSO هستند.
(3)
در تساوي (3)، w ضريب سکون34 ،c1 ضريب اعتماد محلي و c2 ضريب اعتماد سراسري را نشان مي‌دهد. rand ( pi – xik)/ ميزان تاثير از بهترين ذره‌ي محلي و rand ( Pgk – xik)/ ميزان تاثير از بهترين ذره‌ در کل جمعيت است.
Xik+1 = xik + vik+1t (4)
در تساوي (4)، Xik+1 مکان بعدي ذره را نشان مي‌دهد و xik بيانگر مکان فعلي ذره است.
ورژن‌هاي مختلفي از الگوريتم PSO معرفي شده اند. در ورژن استاندارد w در بازه‌ي ]0.4 تا 1.4 [، c1 در بازه‌ي ]1.5 تا 2[ و c2 در بازه‌ي] 2 تا 2.5[ قرار دارد.
شکل 3-1.نحوه‌ي حرکت ذرات در الگوريتم PSO
شکل3-2. مراحل الگوريتم PSO
3-4 مراحل الگوريتم پيشنهادي
الگوريتم پيشنهاد شده در اين پژوهش با توجه به معماري شبکه و اندازه‌ي آن، مراحل مختلفي دارد. براي افزايش قابليت انعطاف الگوريتم، جهت استفاده در شبکه‌هاي مختلف شرايط متفاوت شبکه‌هاي حسگر بي‌سيم بررسي شده است. آگاهي از مکان گره‌ها، نرخ گزارش اطلاعات و ميزان دسترسي ايستگاه اصلي به گره‌ها، مواردي هستند که در کاربردهاي مختلف تفاوت دارند. يک الگوريتم مسيريابي قابل انعطاف بايد به صورت مناسبي اين تفاوتها را مديريت کند.
گام اول: در اين مرحله براي تمام گره‌حسگرهاي شبکه مسير(هاي) بعدي مشخص مي‌شود. به‌طوريکه هر گره بر اساس يک سيستم وزن‌دهي مشخص، هربار يکي از همسايگان خود را به عنوان گره‌حسگر بعدي انتخاب مي‌کند. در برخي کاربردها ايستگاه اصلي به تمام گره‌حسگرها دسترسي دارد و به طور معمول اندازه‌ي اين شبکه‌ها کوچک است، اما در شبکه‌هاي بزرگتر ايستگاه اصلي فقط به بخشي از حسگرها دسترسي دارد، بنابراين در فاز اول الگوريتم دو حالت در نظر گرفته شده است:
* ايستگاه اصلي به تمام گره‌حسگرها دسترسي دارد: در اين حالت الگوريتم به صورت مرکزي و در ايستگاه اصلي اجرا مي‌شود، سپس مسيرها به گره‌حسگرها اطلاع داده مي‌شود. با توجه به دسترسي ايستگاه اصلي به تمام گره‌ها، ارسال مسيرهاي بعدي براي هيچکدام از حسگرها هزينه فرستادن نخواهد داشت. ارتباط گره‌حسگرها با ايستگاه اصلي يک ارتباط



قیمت: تومان


پاسخ دهید