بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
مسيريابي داده محور سلسله مراتبي در شبکه هاي حسگر بيسيم
چکيده : در دهه هاي اخير، شبکه هاي حسگر بيسيم از محبوبيت زيادي برخوردار شده اند. ايـن شـبکه هـا داراي کاربردهـاي زيـادي در زمينـه هـاي مختلف ميباشند. مهم ترين چالش اين شبکه ها، انرژي حسگرها ميباشد. روش هايي براي ذخيره انرژي و افزايش طول عمر شـبکه نيـاز مـيباشـد. در اين مقاله روش جديد براي مسيريابي در اين شبکه ها ارائه شده است که موجب افزايش طول عمر شبکه ميشود. اين الگوريتم داده محور ميباشـد و داراي ساختار سلسله مراتبي ميباشد. اين روش با پروتکل مشابه در اين زمينه مقايسه شده و نتايج بهتري به همراه داشـته اسـت . عـلاوه بـر انـرژي، مزيت هاي ديگر اين روش ، بهبود تأخير و فضاي حافظه مصرفي هر نود مي باشد.
واژه هاي کليدي: داده محوري ؛ خوشه بندي؛ انرژي .
١- مقدمه
شبکه هاي حسگر بيسيم (WSN) به دليل کاربردهاي جذاب و با ارزش در سال هاي اخير اهميت زيادي يافته است . به گفته ي موسسـه بازرگاني هفت [١] شبکه هاي حسگر بيسيم يکي از بيست و يک تکنولوژي مهم در قرن بيست و يک مي باشـد. ايـن شـبکه هـا توانـايي فراهم کردن تنوعي از داده هاي پيش پردازش شده و اطلاعات گسترده و معمولاً متمرکز با استفاده از کاربردهاي زياد دارند[٢]. شبکه هاي حسگر بيسيم از طريق نوهايي به نام چاهک يا نقاط دسترسي که ميتوانند ثابت يا متحرک باشند قابل دسترسي ميباشـند. بـر اسـاس کاربرد WSN و کثرت کاربران درخواست دهنده ، چندين چاهک در شبکه مي تواند قرار داشته باشد. هدف نودهاي چاهک فـراهم کـردن واسط ميان WSN و انواع ديگر شبکه ميباشد [٢].
در شبکه هاي کامپيوتري معمولي، انتخاب نودها با استفاده از شناسه واحد مثل آدرس شبکه انجام ميشود. اين متد بسـيار موفـق اسـت زيرا که ارتباط در اين شبکه ها بر انتقال داده بين توده اي خاص انجام ميشود [٣]. در WSN، به دليل استقرار هم پوشانه نودهاي حسـگر که باعث تکرار ميشود، کاربر به دريافت داده از نود خاص علاقمند نميباشد اما به منطقه جغرافيـايي خـاص يـا نودهـايي کـه اطلاعـات مشخصي فراهم مي کند، علاقه دارد. مهم ترين موضوع اطلاعات يا داده ميباشد. به اين ارتباط ، داده محور در مقابل مدل ارتبـاطي آدرس محور ناميده ميشود[٤]. اين شبکه ها سربار ناشي از نگاشت نام را از بين ميبرند و وابسـته بـه کـاربرد مـيباشـند [٥]. مشخصـات داده محوري نيازمنديهايي را براي پروتکل هاي مسيريابي فراهم ميکند که نودها توسط داده اي که توليد ميکننـد انتخـاب شـوند و نـه بـر اساس آدرسشان [٦، ٧].
مسيريابي در شبکه هاي حسگر بيسيم با توجه به ويژگي هايي که اين شبکه ها را از شبکه هاي بيسيم ديگر مثل شبکه هاي متحـرک يـا ad hoc متمايز ميکند، بسيار چالش برانگيز ميباشد. معمولاً، شبکه هاي حسگر بيسيم شبکه هايي داده محور ميباشند و داده بر اسـاس ويژگي مشخصي در خواست ميشود؛ به اين کار آدرس دهي مبتني بر ويژگي گفته ميشود. هر آدرس مبتني بر ويژگـي شـامل پـرس و جويي از ويژگي و مقدار ميباشد[٨].
در اين مقاله پروتکل مسيريابي داده محور چند لايه ارائه شده است . در اين روش انتقال اطلاعات ابتدا با مذاکره اوليه و انتقال پيـام هـاي متاداده بين نودها انجام ميشود. سپس انتقال به چند لايه تقسيم ميشـود، در لايـه اول انتقـال بـه سرخوشـه ، در لايـه دوم انتقـال بـه سرخوشه اصلي و در لايه سوم انتقال به ايستگاه پايه انجام ميشود.
در بخش ٢ مقدمه اي بر انواع روش هاي مسيريابي ارائه ميشود. در بخش ٣ پروتکل SPIN و معايب آن بحث ميشود. در بخـش ٤ روش پيشنهادي ارائه ميشود و در بخش ٥ نتايج شبيه سازي و مقايسه تحليل ميشود و در بخش آخر نتيجه گيري گفته ميشود.
٢- مسيريابي
ساختار شبکه نقش مهمي در عملکرد پروتکل هاي مسيريابي ايفا ميکند. پروتکل هاي اين دسته به مسيريابي مسـطح ، سلسـله مراتبـي و مبتنـي بـر ساختار تقسيم ميشوند.
٢-١ مسيريابي مسطح
در شبکه هاي مسطح ، نقش تمام نودها مثل جمع آوري داده يا ارتباط با چاهک ، يکسان است ، يعني تمام داده هاي جمع آوري شده در مناطق دور مي - توانند تکراري يا مشابه باشند به گونه اي که به نظر ميرسد نودهاي حسگر مشابه هم کار مي کنند ٩]. به دليل تعداد زياد نودها، امکان دادن شناسـه جهاني به نودها وجود ندارد. بنابراين از مسيريابي داده محور استفاده ميشود. تعدادي از اين پروتکل ها عبارتند از: پروتکل حسـگر بـراي اطلاعـات از طريق مذاکره [١٠]، پخش جهت دار [١١]، مسيريابي شايعه [١٢]، الگوريتم مسيريابي با کمترين هزينه [١٣].
٢-٢ مسيريابي سلسله مراتبي
در معماري سلسله مراتبي [١٤] از نودهاي با انرژي بيشتر براي پردازش و ارسال اطلاعات و از نودهاي با انرژي کم براي حس کردن محـيط اسـتفاده ميشود. مسيريابي سلسله مراتبي، روشي کارا براي مصرف انرژي کمتر درون خوشه به وسيله اجراي تجميع و ترکيب داده بـه منظـور کـاهش تعـداد انتقالات به ايستگاه پايه ميباشد. دو نمونه از اين پروتکل ها شامل پروتکل LEACH[١٥]، پروتکل PEGASIS[١٦] مي باشد.
٢-٣ مسيريابي مبتني بر مکان
در اين روش ، حسگرها به وسيله مکانشان آدرس دهي ميشوند. فاصله بين نودهاي همسايه بر اساس قدرت سيگنال دريافتي، تخمـين زده مـيشـود. براي ذخيره انرژي، در برخي از اين روش ها، زماني که هيچ فعاليتي نباشد، نودها به خواب ميرونـد. پروتکـل هـاي نمونـه در ايـن دسـته عبارتنـد از: پروتکل GAF[١٧]، پروتکل GEAR و پروتکل SPAN.
٣- پروتکل SPIN
انگيزه توسعه SPIN، انتشار اطلاعات ميباشد. انتشار اطلاعات پروسه جمع آوري مشاهدات از حسگرها ميباشد به گونه اي که هر حسگر را به عنـوان چاهک در نظر ميگيريم . کار اختصاص داده شده به اين حسگرها، جمع آوري نماي کامل محيط شبکه به فرم داده و بهبود ساختار تحمل پذير شبکه ميباشد. مصرف انرژي هم در محاسبه و هم در ارتباطات بايد کنترل شود تا طول عمـر حسـگرها را افـزايش دهـد. ايراداتـي نظيـر انفجـار از داخـل ، همپوشاني و کوري منبع در پروتکل هاي پيچيده باعث ايجاد SPIN شده است [١٨].
در SPIN، نودها قبل از انتقال داده ، ابتدا منابع خود را بررسي ميکنند. هر نود حسگر براي خود مدير منبع دارد که مصرف انرژي را رديابي ميکنـد.
کاربردها قبل از انتقال يا پردازش داده ، از مدير تحقيق ميکنند. با اين روش ، زماني که انرژي نود کم باشد، در فعاليت ها شرکت نميکند. اين ويژگي - ها باعث غلبه بر نقايص توزيع سيل آسا ميشود. مذاکره که زودتر از انتقال داده انجام ميشود، از انفجار از داخل نيز جلوگيري ميکند زيرا ارسال داده تکراري را حذف ميکند. استفاده از فراداده نيز از همپوشاني جلوگيري ميکند زيرا اجازه ميدهد که نودها بر قسمتي از داده که به دست مـيآورنـد، نام بگذارند.
در بدترين حالت تمام نودها در شبکه مقداري انرژي براي دريافت و ارسال ADV،REQ و Data صرف ميکنند [١٩]. اين پروتکل براي شبکه هايي با تعداد زياد نود کارا نميباشد. هم چنين در اين روش ، اگر نودهاي علاقمند به داده در فاصله دور از نود منبع قرار داشته باشند و نودهاي ميـاني نيـز علاقمند به دريافت داده نباشند، داده توسط نود علاقمند دريافت نمي شود[٢٠].
٤- الگوريتم مسيريابي پيشنهادي
در روش SPIN، نود تبليغ کننده داده ، پيام ADV را براي تمام همسايگانش ارسال ميکند. هر نود با دريافت اين پيام ، در صورت علاقمنـدي بـه آن ، پيام REQ را براي نود تبليغ کننده ميفرستد. يعني در بدتربن حالت ، تمام نودهاي همسايه علاقمند به داده ميباشند و بنابراين پيام REQ را ارسال مي کنند و نود به ازاي هر پيام REQ، بايد داده را انتقال دهد. بنابراين حجم زيادي از پيام هاي کنترلي و حتي داده انتقـال داده مـي شـوند. ايـن امـر باعث به هدر رفتن پهناي باند و مصرف بيشتر انرژي ميشود. از طرف ديگر هر نود همسايه نيز داده را براي همسـايگانش تبليـغ مـيکنـد و بنـابراين روند فوق دوباره تکرار ميشود. از طرف ديگر، ممکن است هيچ کدام از همسايگان نود تبليغ کننده علاقمند به دريافت داده نباشند بنابراين پيام REQ ارسال نشده و داده جديد در اختيار BS قرار نميگيرد، در نتيجه قابليت اطمينان اين روش نيز کم ميباشد.
٤-١ پروتکل مسيريابي داده محور چند لايه
در روش ارائه شده در اين تحقيق ، سعي بر آن شده است که معايب فوق از بين رفته و مصرف انرژي در شبکه کـاهش يابـد. در ايـن روش ابتـدا کـل فضاي شبکه به گريدهايي با اندازه يکسان ( λ ) تقسيم ميشود. سپس براي هر گريد يک نود با انرژي زياد به عنوان سرخوشه اصلي (MCH) انتخاب مي شود. سپس نودها به صورت تصادفي و با توزيع مشخصي (پواسن * يا يکنواخت ) درون گريدها استقرار مييابند. شعاع انتقال هـر نـود را r در نظـر ميگيريم . در مرحله بعد، نودهاي هر گريد به خوشه هايي تقسيم شده که هر خوشه داراي يک سرخوشه (CH) ميباشد. وظيفه هر سرخوشـه جمـع - آوري، تجميع داده و ارسال داده به MCH ميباشد و هر MCH با دريافت داده آن را براي BS ارسال ميکنـد. فلوچـارت ايـن روش در شـکل ٤ نشان داده شده است . در اين روش ، زماني که يک رخداد در شبکه به وقوع بپيوندد، نود داده جديد را پويش نموده و آن را تبليغ ميکند. از آنجايي که نودها درون خوشه قرار دارند، تنها سرخوشه به اين پيام پاسخ مي دهد و بقيه نودها، پيام تبليغ را دور مي اندازند. نـود سرخوشـه بـا دريافـت پيـام تبليغ ، بافر خود را بررسي نموده و در صورت نداشتن داده در بافر خود، پيام REQ را براي نود تبليغ کننده ارسال ميکنـد. نـود تبليـغ کننـده داده را براي CH ميفرستد و CH داده را در بافرش ذخيره نموده و آن را براي نودهاي همسايه در سطح بالاتر که شامل سرخوشه هاي ديگر و MCH مـي- باشد، تبليغ ميکند. در اين مرحله نيز داده به روش فوق براي MCH و در مرحله بعد براي BS ارسال مي شود.
اين روش را به دليل مسيريابي داده محور در چند لايه ي خوشه ها، سرخوشه ها، سرخوشه هاي اصلي هر گريد و در نهايت BS، مسـيريابي داده محـور چند لايه (MDC) ناميده ايم . در اين روش ، تعداد پيام هاي کنترلي و تعداد پيام هاي داده کاهش يافته و در نتيجه انرژي مصرفي شبکه کاهش يافته و طول عمر شبکه افزايش مييابد.
٤-٢ پيام هاي روش پيشنهادي
پيام تبليغ : تمام نودها درون شبکه با حس و دريافت داده جديد ملزم به تبليغ آن براي نودهاي همسايه خود ميباشند. اين پيام متا داده ميباشد و سايز آن به مراتب از پيام داده کمتر ميباشد. قالب يک پيام آگاهي مطابق شکل ١ ميباشد.
شکل ١. قالب پيام تبليغ
در اين پاکت ، Packet_type نوع پاکت ارسالي ميباشد. سه نوع پاکت در اين روش تعريف شده است : MDC_ADV براي پيام تبليغ ، MDC_REQ براي پيام درخواست و MDC_Data براي پيام داده . المان Data_type براي تعيين نوع داده ارسالي است . هر نود با توجه به اين نوع داده بافر خود را بررسي ميکند. دو المان بعدي براي تعيين مقصد و منبع پيام ميباشد.
پيام درخواست : زماني که نود سرخوشه و سرخوشه اصلي بافر خود را بررسي نمودند و داده تبليغ شده را نداشتند، يک پيام REQ ايجاد نموده و براي نود تبليغ کننده ارسال ميکنند. اين پيام به صورت شکل ٢ ميباشد. اين پيام نيز متاداده ميباشد.
شکل ٢. قالب پيام درخواست
پيام داده : يک پيام داده داراي سايز متفاوت از پيام هاي کنترلي ميباشد. يک پيام داده شامل عناصر زير ميباشد:
شکل ٣. قالب پيام داده
شکل ٤. فلوچارت روش پيشنهادي
٤-٣ انرژي
در هر دو مدل SPIN و MDC، ارسال و دريافت پيام هاي کنترلي و داده باعث مصرف انرژي نود ميباشد. انرژي ارسـال k بيـت داده در فاصـله d در شبکه با توجه به منبع [٢١] برابر با معادله (١) ميباشد.
مقدار انرژي مصرفي براي دريافت k بيت داده برابر با رابطه (٢) ميباشد.
