دانلود فایل ها در مورد : بررسی خاصیت تحمل پذیری خطای الگوریتم های مسیریابی چند مسیره ... |
داده ها همچنین میتوانند به صورت مدل خصوصیت-نام[۶۰] ارسال شوند. گرهای که داده ها را ارسال می کند به عنوان یک منبع شناخته می شود. داده هنگام ارسال به مقصد در گرههای میانی ذخیره می شود که این عمل در اصل برای جلوگیری از ارسال داده های تکراری و جلوگیری از به وجود آمدن حلقه استفاده می شود. همچنین از این اطلاعات میتوان برای پردازش اطلاعات درون شبکه[۶۱] و خلاصه سازی اطلاعات استفاده کرد.
پیغامهای اولیه ارسالی به عنوان دادههای اکتشافی[۶۲] برچسب زده میشوند و به همه همسایههایی که به گره دارای داده، گرادیان دارند ارسال میشوند یا میتوانند از میان این همسایهها، یکی یا تعدادی را بر حسب اولویت جهت ارسال بستههای اطلاعات انتخاب کنند. (مثلاً همسایههایی که زودتر از بقیه پیغام را به این گره ارسال کردهاند) برای انجام این کار، گیرنده یا چاهک همسایهای را که جهت دریافت اطلاعات ترجیح میدهد تقویت میکند[۶۳]. اگر یکی از گرهها در این مسیر ترجیحی از کار بیافتد، گرههای شبکه به طور موضعی مسیر از کار افتاده را بازیابی میکنند. در نهایت گیرنده ممکن است همسایه جاری خود را تقویت منفی[۶۴] کند در صورتی که مثلاً همسایه دیگری اطلاعات بیشتری جمع آوری کند.
پس از ارسال دادههای اکتشافی اولیه، دادههای بعدی تنها از طریق مسیرهای تقویت شده ارسال میشوند. منبع اطلاعات به صورت متناوب هر چند وقت یکبار داده های اکتشافی ارسال میکند تا گرادیانها در صورت تغییرات پویای شبکه، بروز شوند. نحوه عملکرد این الگوریتم در ادامه آورده شده است.
بعضی از خصوصیات کلیدی روش انتشار هدایت شده را از روشهای سنتی در شبکه متمایز میکند. اول اینکه روش پخش اطلاعات یک روش داده– محور[۶۵] است و تمام ارتباطات دریک شبکه حسگر بر این مبنا از علاقهمندیها جهت مشخص کردن اطلاعات نامگذاری شده استفاده می کنند. دوم برخلاف شبکه های سنتی که روش انتقال انتها به انتها[۶۶] دارند در این روش از ارتباط همسایه با همسایه یا گام به گام[۶۷] استفاده میشود و هر گرهای میتواند داده ها و علاقهمندیها را تفسیر کند زیرا شبکه های حسگر معمولاً عملکرد واحدی دارند و وظیفه یکسانی را بر عهده دارند. سوم در این روش، گرهها آدرس سراسری یکسان یا مشخصه واحدی ندارند ولی هر گره باید از همسایگانش به صورت محلی قابل تفکیک باشد و نهایتاً چون هر گره می تواند داده ها را پردازش کند، میتوان حجم داده ها را در شبکه کاهش داد و داده ها را به صورت خلاصه ارسال کرد.
کارهای زیادی بر روی الگوریتم انتشار هدایت شده پایه صورت گرفته است که هر یک به نحوی عملکرد آن را بهبود دادهاند. الگوریتم انتشار هدایت شده پایه به الگوریتم انتشار، با خاصیت جذب دو مرحله ای هم معروف است چون در این روش در فاز اول، ابتدا گره گیرنده یا مقصد یک علاقه مندی را به سمت داخل شبکه منتشر می کند و هنگامیکه گرهای متوجه انطباق داده های جمعآوری توسط حسگرهای خود با علاقه مندی منتشر شده گردید، یک پیغام داده اکتشافی به سمت مقصد ارسال می کند و این داده از بین گرادیانهایی که هنگام انتشار پیغام علاقه مندی تشکیل شده اند، سعی می کند گرادیانی با بهترین زمان پاسخ یا کیفیت کانال را انتخاب کند و به همین صورت پیش میرود تا به مقصد برسد و سپس گره مبدأ داده های جمعآوری شده را به سمت مقصد ارسال می کند.
دسته خصوصیتها
در روش پخش اطلاعات برای تطبیق دادن خواسته ها و صفات از دستههای خصوصیت-مقدار –عملگر[۶۸] استفاده می شود که خصوصیتها هم در قالب داده (مانند اعداد صحیح ۳۲ بیتی در سادهترین شکل) تعریف میشوند و عملگرها مقایسه گرههای دودویی معمول هستند که عبارتند از مساوی، بزرگتر، کوچکتر، بزرگتر (EQ, NE, LE, GT, GE, …) و عملگر EQ_ANY که با همه چیز مطابقت دارد و IS به کاربر اجازه میدهد یک مقدار ثابت را مشخص کند. نمونه یک علاقه مندی و یک داده منطبق با آن را در زیر مشاهده میکنیم.
Interest: class IS interest
(type EQ four-legged-animal-search, interval IS 20ms, duration IS 10 seconds, x GE 100, x LE 200, y GE 100, y LE 400)
Data:
(type IS four-leg-animal-search, instance IS elephant, x IS 125, y IS 220, intensity IS 0.6, confidence IS 0.85, timestamp IS 1:20, class IS data)
شرح پارامترهای ذکر شده در بالا بدین صورت است :
Type: نوع پارامتری مورد علاقه که در مثال ذکر شده جستجوی حیوانات چهارپا است را بیان می کند.
Interval: فاصله بین دو ارسال را برای ارسال داده ها مشخص می کند.
Duration: مدت زمان اعتبار علاقه مندی را تعیین می کند.
x,y: موقعیت جغرافیایی محدوده مورد نظر را بیان می کند.
Instance: نمونه ای که از نوع ذکر شده حس شده است.
Intensity : تراکم داده های دریافتی را مشخص می کند.
Timestamp: زمان حس کردن داده را تعیین می کند.
در مثال بالا علاقه مندی تعیین می کند که برای حیوانات چهارپا که در محدوده جغرافیایی ذکر شده (۱۰۰<y<400 و ۲۰۰<x<400) قرار دارند در مدت ۱۰ ثانیه جستجو شود و داده ها در فواصل ۲oms ارسال گردند. نوع داده آن مشخص می کند که یک نمونه فیل در محدوده x=125 و y=220 در زمان ۱:۲۰ ثانیه مشاهده شده است.
روش انتشار جذب یک مرحله ای[۶۹]
روش جذب یک مرحله ای [۱۸] یک روش بر مبنای درخواست کننده است که یکی از مرحلههای روش جذب دو مرحله ای را حذف می کند. در این روش همانند روش جذب دو مرحله ای درخواست کنندهها پیغامهای علاقه مندی را تولید می کنند و در سطح شبکه پراکنده می کنند و گرادیانها را شکل می دهند، ولی بر خلاف روش جذب دو مرحله ای هنگامی که یک علاقه مندی به منبع رسید، منبع اولین بسته داده ها را به عنوان داده اکتشافی برچسب نمیزند و به جای این کار داده ها را تنها از طریق گرادیانهای ترجیح داده شده ارسال می کند. گرادیان ترجیح داده شده به وسیله همسایهای ایجاد شده که برای اولین بار علاقه مندی را به گره جاری ارسال کرده است و بنابراین تأخیر کمتری را نسبت به سایر همسایههای خود دارد. با این راهکار روش جذب دو مرحله ای دیگر نیازی به پیغامهای تقویت کننده ندارد.
روش جذب یک مرحله ای دو عیب عمده نسبت به روش جذب دو مرحله ای دارد به این ترتیب که فرض می کند که همیشه یک ارتباط متقارن بین گرهها برقرار است چون در این روش، مسیر داده ها (مسیر منابع به گیرندهها) توسط کانال با کمترین تأخیر در مسیر ارسال علاقه مندی مشخص می شود.
شکل ۳‑۱ : ارسال داده با بهره گرفتن از erasure coding
روش جذب دو مرحله ای جریمه ناشی از ارتباطات غیر متقارن را کاهش میدهد چون انتخاب مسیر داده ها به وسیله داده های اکتشافی با کمترین تأخیر صورت میگیرد. با این وجود الگوریتم انتشار جذب دو مرحله ای هنوز به سطوحی از تقارن نیاز دارد چون پیغامهای تقویت کننده مسیرهای بر عکس را طی می کنند. در هنگام استفاده از این روشها لایه MAC باید به الگوریتم انتشار این اجازه را بدهد که رابطهای غیر متقارن را تشخیص دهد.
ایراد دیگر روش جذب یک مرحله ای این است که در این روش پیغامهای علاقه مندی باید یک مشخصه جریان [۷۰]با خود حمل نمایند. اگرچه تولید کردن مشخصههای جریان بسیار ساده است و می تواند توسط MACمشخص شود یا به صورت تصادفی انتخاب شود این کار به نسبت تعداد منابع باعث افزایش اندازه پیغامهای علاقه مندی می شود و همچنین استفاده از مشخصه جریان انتها به انتها، به این معنی است که در این روش برای تصمیم گیری جهت ارسال اطلاعات، تنها از اطلاعات محلی استفاده نمی شود. در نهایت روش جذب یک مرحله ای برای کاربردهایی مناسب است که در آنها تعداد زیادی از منابع، داده ها را به تعداد کمی از گیرندهها ارسال می کنند.
در مرجع [۱۷] مقایسه و ارزیابی کاملی جهت انتخاب الگوریتم پخش اطلاعات مناسب با توجه به تعداد منابع و گیرندهها، به عمل آمده است.
کاربرد کدینگ در مسیریابی چند مسیره برای افزایش تحمل پذیری خطا
کدینگ یکی از راهکارهای انعکاس است که در پروتکلهای مسیریابی برای افزایش تحمل پذیری خطا و توزیع بار در شبکه های حسگر بیسیم استفاده می شود. که در زیر نمونههائی از کارهای انجام شده آورده شده است:
Erasure coding
در این نوع کدینگ منبع هر بسته داده را که سایز آن bM بیت است [p2] به M تکه[۷۱] b بیتی تقسیم می کند، سایز هر تکه b بیت است. سپس با بهره گرفتن از کدینگ ذکر شده K تکه دیگر نیز تولید می کند که در مجموع K+M تکه داریم [۲].
اگر فرض کنیم بین منبع و چاهک n مسیر مستقل تا وجود دارد، تکههای ایجاد شده با بهره گرفتن از یک الگوریتم توزیع بار مناسب در این مسیرها هدایت میشوند که هر مسیر تکه را به مقصد حمل می کند که در عبارت صدق می کند. نحوه توزیع بار در شکل ۳-۵ نشان داده شده است. برای بازیابی بسته اصلی چاهک باید حداقل M بسته را به درستی دریافت کند یا به عبارت دیگر از M+K تکه، K تکه می تواند خراب شود. اگر Zi معرف تعداد تکههای دریافت شده روی مسیر i ام باشد در نتیجه برای بازیابی بسته اصلی باید معادله زیر برقرار باشد:
( ۳-۱ )
نتایج در شبکه های حسگر بیسیم نشان میدهد که با استفاده ازerasure coding و توزیع بار مناسب به وسیله مسیریابی چند مسیره همراه با مقداری افزونگی که به بستهها افزوده می شود میتوان قابلیت اطمینان شبکه را افزایش داد، بدون اینکه سربار ترافیک را خیلی زیاد کند [۱۰].
در [۱۹] مقایسه ای بین شمای انتقال مجدد و erasure coding صورت گرفته است که میزان مصرف انرژی و احتمال موفقیت بستهها را تحلیل کرده است، نتایج نشان میدهد که استفاده ازerasure coding نسبت به Retransmission در حالتی که احتمال از دست رفتن بستهها پایین باشد، قابلیت اطمینان بیشتر و کارائی مصرف انرژی بهتری دارد، در حالی که اگر احتمال از دست رفتن بستهها بالا باشد کارایی erasure coding برای موارد تحلیل شده بدتر می شود.
در RFTM[9] یک پروتکل مسیریابی بر حسب تقاضا[۷۲] که باعث افزایش قابلیت اطمینان در شبکه های حسگر بیسیم می شود ارائه شده است. RFTM با بهره گرفتن از کیفیت لینک و قابلیت اطمینان خواسته شده توسط هر یک از منابع تعداد مسیرهای مستقل از هم را که باید استفاده شود تعیین می کند. در RFTM نیز از erasure coding استفاده می شود که در آن چاهک به صورت هوشمند، بر اساس منابع در دسترس برای هر نود، تعداد گامها[۷۳] تا منبع، تأخیر[۷۴] و دیگر پارامترها خاصیت تحمل پذیری خطا و قابلیت اطمینان مورد نظر را فراهم می کند.
نحوه عملکردRFTM در ادامه تشریح می شود:
الف- ابتدا هر گره که میخواهد داده را ارسال کند پیغامهای درخواست مسیر[۷۵] (Rreq) را انتشار میدهد. هر نود میانی که آن را دریافت می کند اطلاعات جدول مسیریابی همسایههای خود را بروز رسانی[۷۶] می کند و بسته را دوباره انتشار میدهد.
با رسیدن Rreq به چاهک، چاهک یک پیغام پاسخ مسیر[۷۷] (Rrep) را برای منبع ارسال می کند که این پیغام روی مسیرهای خاصی ارسال میشوند که بهترین مسیرها با توجه به شرایط شبکه، قابلیت اطمینان درخواستی از منبع و اطلاعات موجود در Rreq (مانند : تعداد گامها، حداقل انرژی در دسترس از هر مسیر، احتمال موفقیت بستهها رو مسیر و دیگر پارامترها) انتخاب میشوند. فیلدهای موجود در Rreq و Rrep در شکل ۳-۶ و ۳-۷ نمایش داده شده است.
Request ID |
Source ID |
Min. Energy Level EL | Sender ID |
Hop Count HC |
Successful |
فرم در حال بارگذاری ...
[شنبه 1400-08-22] [ 04:20:00 ب.ظ ]
|