خوشه بندی تحمل پذیرخطا درشبکه های سنسور بی سیم

خوشه بندی تحمل پذیرخطا درشبکه های سنسور بی سیم

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

خرابی در شبکه های سنسور به علت محیط غریب نواز و نیروی خودکار اجتناب ناپذیر است. به هرحال خرابی با سطح بالاتر در روشهای سلسله مراتبی مثل خرابی سرخوشه خسارت زیادی به سیستم وارد می کند. زیرا توسط آنها دسترسی به دیگر گره های زیر شاخه خودش محدود می شود.

در این مقاله مکانیزمی را جهت مقابله با خرابی سرخوشه پیشنهاد می کنیم، این مکانیزم در مقابل خرابی سر خوشه سعی می کند گرهای زیرشاخه آن را بازیابی کند و موجب افزایش کارائی شبکه شود.

آنالیز مکانیزم: برای مقابله با هر خطا دو کار باید انجام دهیم A- کشف B- ترمیم

A- کشف خطا: کشف مرحله اول تحمل‌پذیری خطا در سیستم مان است.از پروتوکل TDMA MAC برای ارتباط استفاده می‌کنیم. به این ترتیب یک چرخه ای به صورت تکراری صورت می گیرد. و گره سرخوشه یک بازۀ زمانی را به یک گره می دهد تا اینکه داده های خود را ارسال کنندکه البته این گره بسته به انرژی، کار و اولویت اش انتخاب می شود گره ها از وضعیت های زمانبندی و مسیر یابی خود در بازه زمانیroute update متوجه می شوند بعد وضعیت خود را به گره سرخوشه ارسال می کنند. (انرژی و idو موقعیت x,y (.

گره های سرخوشه نیز وضعیت های خود را در بازه های زمانی   status update تغییر می دهندکه زمانش به پایداری سیستم بستگی دارد.

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

از تغییر وضعیت ها استفاده می شود و یک درخت آزمون ایجاد می شود بدین ترتیب که هر گاه یک گره تغییر وضیت ها را از گره های دیگر دریافت مقدار آن را در جدول 1 می کند.در غیر این صورت آن را 0 می کند.

 

 

در دو شکل بالا وضعیتی که هیچ خطایی صورت نگرفته نشان داده شده و می توان از جدول آزمون متوجه آن شد.

در دو شکل بالا وضعیتی که گره G4 دچار خرابی شده است نشان داده شده و می توان از جدول آزمون متوجه آن شد.

-Bترمیم خطا: بعد از کشف خطا باید آن را ترمیم کرد بعد از خرابی یک گره سرخوشه باید همه اعضای آن بازیابی شوند.خوشه بندی بر اساس فاصله بین سنسورها و گره سرخوشه می باشد.

سنسورSj متعلق به مجموعه محدوده Rset از پل‌‌‌ ارتباطی Gi اگر رابطه زیر برقرار باشد.

که R_Gi محدوده‌ای از پل‌ ارتباطی G_i است. R_Sj,max حداکثر محدوده سنسور S_j و G_i d_Sj→ فاصله بین سنسورS_j و پل‌ ارتباطی G_i است. از روی این یک مجموعه درست می شود که بر اساس مینیمم هزینه انتقال بین نود و سرخوشه می باشد.

برای بازیابی نودها در یک خوشه که دچار خرابی شده است سرخوشه های سالم شروع به ایجاد مجموعه جدیدی می کنند که که شامل گرهایی می شود ک در خوشه خودشان نیستند ولی عضو RSET آن خوشه می باشند که به این مجموعه backup set(BSET)گفته می شود. یک نودفقط می تواند متعلق به یک FSET باشد ولی می تواند متعلق به BSETزیادی باشد.تعریف BSETبه صورت زیر می باشد.

نودی بازیابی می شود که متعلق به BSETیک کلاستر باشد.اگر یک نود در BSETچندین خوشه باشد در آن صورت بر اسس مینیمم هزینه محاسبه میشود.

مزیت مکانیزم: روش ما گریزی است تمام عیار برای خوشه بندی مجدد و نیاز به گسترش پل های ارتباطی(برخی گره‌ها با انرژی بالا) تکراری ندارد. و لازم نیست سیستم خاموش شود که در این صورت باید سربار زیادی را تحمل کند. بنابراین کشف و ترمیم در زمان اجرا انجام می شود.

عیب مکانیزم: در این مقاله سرخوشه ها ثابت و بی حرکت در نظر گرفته شده و گره های متحرک را بررسی نکرده است.

در این مقاله فقط خطا های دائمی مورد بحث قرار گرفته اند و خطاهای گذرا و تکراری مورد بحث واقع نشده اند.

پارامترهای به کار رفته در این مکانیزم: در این مقاله از پارامترها تحمل پذیر خطا، در دسترس بودن رعایت شده چون موقع کشف و ترمیم نیازی نیست که سیستم خاموش شود. بدین ترتیب قابلیت اطمینان را بالا می برد.

شبیه سازی: آزمایشات شبیه‌سازی با 1000 سنسور و 3 پل‌ ارتباطی توزیع شده به صورت یکسان در یک محیط مربعی به ابعاد 10 × 10 کیلومتر انجام داده شده. فرض شده هر سنسور انرژی نخستین 5 ژول دارد. یک گره اگر سطح انرژی‌اش به 0 (صفر) ژول برسد غیر تابع مطرح می‌شود. بیشترین محدوده سنسورها مجموعه‌ای با 5 دوره بیشترین فاصله بین دو گره در سیستم است. فرض شده کانال تصادم آزاد است و بسته‌ها در متوسط ریخته نشده‌اند. به سنسورها IDS به روش تصادفی داده شده است. سنسورها درباره زمانبندی‌هایی اولیه TDMA توسط پل‌ ارتباطی مربوطه‌شان آگاه می‌شوند. زمانبندی برای ارتباط پل‌ ارتباطی ورودی اول در طول راه‌اندازی تصمیم گرفته شده است سوئیچ گره‌ها روی فرستنده اگر نیاز داشته باشند و مدارات مجتمع دریافت‌کننده تنها در طول تخصیص شیارهاشان انجام می‌شود.

شکل 5 طراحی محیط تزریق خطا را توصیف می‌کند. آن شروع تزریق خطای اتصال توسط خطای تزریقی در پل‌ ارتباطی G3 را نشان می‌دهد. قبلاً پل‌ ارتباطی G2 همه عملکردرا به علت خرابی کامل متوقف می‌کند. همچنین پل‌ ارتباطی G1 از یک محدوده خطا تحمل شده است. به این ترتیب اندازه‌گیری کارائی روش‌مان پوشش الگوریتم را محاسبه می‌کند.

1000 خطا به ترتیب برای اندازه‌گیری پوشش الگوریتم‌مان تزریق می‌کنیم. از زمانی که خرابی‌های کامل با خطاهای دیگر کمتر مقایسه شده‌اند. ما به آنها فرکانس پایین سپس محدود و خرابی‌های متصل اضافه می‌کنیم. همه خرابی‌های کامل بلافاصله در طول دوره وضعیت آنی کشف شده‌اند. ما خطاها را برای کاهش محدوده پل‌ ارتباطی G1 با %2 هر 15 دقیقه تزریق می‌کند. در همه موقعیت مکانیزم کشف‌مان، کشف خطاها و شناسایی سنسورها که خارج از محدوده پل‌های‌ ارتباطی می‌رود. سنسورها با موقعیت برای دیگر پل‌‌های ارتباطی ترمیم می‌کنند تا اینکه محدوده G1 به پایین یک آستانه و تنها سنسورهای خیلی نزدیک به G1 در خوشه چپ هست می‌ریزد. بعد از هر خطا محدوده بعدی در پوشش G1 کم می‌شود زیرا خرابی‌های الگوریتم برای پیدا کردن هر پل‌ ارتباطی تا سنسور را آماده بکند.

خرابی‌های اتصال در پل‌ ارتباطی G3 تزریق شده‌اند تا برای مطالعه کردن فشار روی تعداد پیامهای وضعیت برای پل‌های‌ ارتباطی دیگر و طرح ارسال فعال شوند دریافت نمی‌کند. شماره عمومی پیام توسط پل‌ ارتباطی در طرح ارسال N + 1 است. جائیکه N شماره عمومی پل‌های‌ ارتباطی در سیستم است. هر پل‌ ارتباطی یک پیام وضعیت، یک پیام تجربه و ارسال پیام‌های وضعیت N – 1 انتقال خواهد داد. دوره تناوب حالت جدید توسط الگوریتم MILD کنترل می‌شود تا اینکه ما یک قطع ساختن خطاها ترمیم مکرر تزریق کنند. پوشش اتصالات خراب بکلی 100% رعایت شده شبیه‌سازی تا وقتی که همه اتصالات ورودی/ خروجی از پل‌ ارتباطی خراب شود. بعد از خراب شدن همه اتصالات هر خطا روی G3 کشف شده‌اند همچون یک خرابی کامل توسط دیگر پل‌های‌ ارتباطی ترمیم سنسورها در خوشه G3 تنها روی اولین خرابی کامل انجام شده است.

نتایج بوضوح آزمایشات تزریق نقص که سیستم ارتجاعی در خرابی‌های ارتباط و ترمیم کارائی بدون پیکربندی مجدد یا تغییر راهنمایی را نشان می‌دهد.

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

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