مقاله بررسی و مقایسه روش های شناسایی گره های معیوب در شبکه حسگر بی سیم

بخشی از مقاله

بررسي و مقايسه روش هاي شناسايي گره هاي معيوب در شبکه حسگر بی سیم
چکيده : شبکه هاي حسگر بيسيم در کاربردهاي مختلفي مورد استفاده قرار ميگيرند که بدليل ويژگـيهـاي فيزيکـي و عوامـل مخـرب محيطـي، گره هاي حسگر مستعد خراب اند. با اين حال ، از کارافتادن برخي از گره هاي حسگر نبايد مانعي در وظيفـ منـدي مطلـوب شـبکه و تـأثير منفـي بـر عملکرد شبکه حسگر داشته باشد. اين ويژگي در شبکه هاي حسگر بی سیم بعنوان تحمل پذيري خرابي شبکه مورد بررسي قـرار مـيگيـرد. مـديريت خرابي يکي از تکنيک هاي افزايش تحمل پذيري خرابي براي بهبود قابليت اطمينان شبکه ميباشد. مديريت خرابـي از سـه مرحلـه ي کشـف خرابـي، تعيين گره هاي خراب و حذف گره هاي معيوب تشکيل ميشود. در اين مقاله به بررسي عملکرد الگوريتم هاي Lee،Chen ،Jianliang و Jiang که از معروف ترين الگوريتم هاي مديريت خرابي ميباشند ميپردازيم . نتايج بررسيها ميزان دقت کشف خرابي و نرخ اخطار نادرست اين الگـوريتم هـا را در شرايط مختلف شبکه و با نرخ هاي خرابي مختلف نشان ميدهند.
واژه هاي کليدي: تحمل پذيري خرابي، شبکه حسگر بيسيم ، کشف خرابي، مديريت خرابي .

١- مقدمه
تحمل پذيري خرابي در شبکه هاي حسگر بيسيم بدليل محدوديت هاي خاص گر هاي حسگر، يکي از مهم ترين ملزومات اين شبکه هـا مـيباشـ . بـه عبارتي از کار افتادن گره هاي حسگر بدليل تأثير عوامل مخرب محيطي مانند رطوبت و گرد و خاک يا بدليل خرابي اجزاء فيزيکي، نبايد بر کارکرد و وظيفه مندي مطلوب شبکه تأثير بگذارد. براي افزايش تحمل پذيري خرابي در شبکه حسگر بيسيم بايد گره هاي معيوب شناسايي شـده و در هـدايت بسته ها از آنها استفاده نشود.
جهت آشکارسازي وقايع نامطلوب ، مي توان از چهار نوع افزونگي استفاده کرد که عبارتند از: افزونگي سخت افزاري، نرم افزاري، اطلاعـاتي و زمـاني.
روش هاي مختلفي براي تحمل پذير کردن شبکه وجود دارد. از آن جمله مي توان به روش هاي ذخيره سازي فعال ١، ارسـال چنـد مسـيري و مـديريت خرابي اشاره کرد. در روش ذخيره سازي فعال تعدادي از گره هاي مياني بسته هاي دريافت شده را در حافظه خود ذخيره ميکنند تا در صورتي که اين بسته ها در گام هاي بعدي گم شدند و درخواستي مبني بر گم شده اين بسته ها دريافت کردند آنها را ارسال مجدد کنند. بـدين ترتيـب ديگـر نيـازي نيست گره مبدأ ارسال مجدد را انجام دهد با استفاده از اين رويکرد انرژي مصرفي در گره ها کاهش يافته و طول عمر شبکه افزايش مييابد. در روش ارسال چند مسيري براي اينکه شبکه تحمل پذير در مقابل خرابي شود داده از چند مسير ارسال ميشود تا در صورت بروز مشکل در يک مسير و گم شدن بسته ، داده از مسير ديگري به مقصد برسد. هر دو روش مذکور به نوعي سعي دارند تا تأثير گره هاي معيوب در عملکرد شبکه را کـاهش دهنـد.
ولي در روش مديريت خرابي سعي ميشود تا با شناسايي و حذف گره هاي معيوب شبکه ، براي هميشه مشکل گره هـاي معيـوب حـل شـود. کشـف ، موقعيت يابي و حذف گره هاي حسگر معيوب سه گام اساسي مديريت خرابي ميباشند. مديريت خرابي در شبکه امري ضروري به نظـر مـيرسـد. در غير اينصورت گره هاي معيوب ، بعنوان گره هاي ارتباطي استفاده خواهند شد که موجب اختلال در مسيريابي شده و همچنين بـدليل نادرسـت بـودن داده هاي توليد شده اين گره ها، تصميمات اشتباهي در چاهک گرفته ميشود.
تحمل پذيري خرابي شبکه حسگر بيسيم در چهار لايه ي سخت افزار، نر افزار، ارتبـاطي شـبکه و کـاربردي مطـرح مـيشـود. خرابـي در هـر جـزء سخت افزاري يک گره حسگر مانند حافظه ، باتري، ريزپردازنده و واحد حسگر را خرابي در لايه سخ افزار گويند. نـرم افـزار يـک گـره حسـگر شـامل سيستم عامل و ميان افزار ميباشد. ايجاد تحمل پذيري خرابي در لايـه سـخت افـزار از نظـر اقتصـادي مقـرون بـه صـرفه نيسـت ؛ پـس بـراي افـزايش تحمل پذيري خرابي، لايه ميان افزار مورد توجه قرار ميگيرد. خطاها در لايه ارتباطي شبکه ، مربوط به خطاهاي خطوط ارتبـاطي بـيسـيم مـيشـود.
مقابله با اين خطاها و افزايش کارايي کانال ، باعث افزايش تأخير و انجام محاسبات اضافي ميشود؛ ولي براي افزايش تحمـل پـذيري خطـا مجبـور بـه استفاده از اين روش ها ميباشيم . تحمل پذيري خرابي در لايه کاربردي شامل ارسال اطلاعات از چندين مسير متفاوت از گره مبدأ به چاهک مي باشـد که تحمل پذيري خرابي در مسيريابي را فراهم ميآورد. در صورت شکست بعضي از مسيرهاي ارتباطي و غير قابل دسـترس شـدن آنهـا، اطلاعـات از مسير ديگري به چاهک ميرسد[٤].
ما در اين مقاله از سه گام موجود در مديريت خرابي ، کشف گره معيوب را بررسي ميکنيم . کشف گره معيوب يکي از مهمتـرين مراحـل مـديريت خرابي ميباشد که در اين مقاله ما چند الگوريتم مشهور در اين زمينه را بررسي و انواع خرابي که اين الگوريتم ها م توانند شناسـايي کننـد را بيـان کرده ايم . هدف از اين مقاله بررسي هر چه بهتر راهکارهاي موجود و ارائه راهکاري جديد در اين زمينه در کارهاي آتي است .
در ادامه اين مقاله ، در بخش دوم انواع خرابي، در بخش سوم بررسي تکنيک هـاي کشـف خرابـي در شـبکه را خـواهيم داشـت . در بخـش چهـارم جزئيات بيشتر در مورد الگوريتم Lee،Chen ،Jiang و Jianliang معايب و مزاياي هر کدام را مورد بررسي قرار ميدهيم . در نهايت در بخش پنجم نتيجه گيري خواهيم داشت .
٢- انواع خرابي در شبکه حسگر بيسيم
کاربرد شبکه هاي حسگر بيسيم معمولا در مناطق دور از دسترس ميباشد که با کمترين نظارت ، حسگرها در منطقه پخش مـ شـوند. همـين امـر باعث ميشود برخي از حسگرها در مناطقي قرار گيرند که احتمال خرابي آنها بيشتر باشد. همچنين در سـاخت حسـگرها از قطعـات ارزان قيمـت استفاده مي شود تا هزينه تمام شده شبکه مقرون به صرفه باشد. بنابراين حسگرها بخاطر محدوديتهاي ذاتي شان بيشتر مستعد خرابي هستند.
وجود هر نوع نقص در اجزاء داخلي يک واحد که باعث مي شود آن واحد در عملکرد خود با شکست مواجه شود را خرابي ٣ گويند. در صورت وجـود خرابي در شبکه ، اطلاعات دريافتي در مقصد نادرست خواهند بود. تأثير وقايع نامطلوب ٤ بر هر يک از قسـمت هـاي سيسـتم بـا توجـه بـه منشـاء آن متفاوت خواهند بود. خرابيها به دو صورت عمدي و غيرعمدي در شبکه ايجاد ميشوند. خرابيهاي عمدي بيشتر در خاک دشمن و به صورت عمدي ايجاد ميگردند و باعث ميشوند که شبکه از عملکرد مطلوب خارج شود. خرابيهاي غير عمدي معمولا به علت پخش شدن حسگرها در محيط هـاي غير قابل دسترس و بدليل عوامل مخرب محيطي ايجاد ميشوند. خرابي غير عمدي بدليل بلاياي طبيعي و عوامل طبيعـي ايجـاد مـيشـود. خرابـي ايجاد شده در اثر بلاياي طبيعي مانند طوفان ، سيل ، و زلزله جزء خرابيهاي غير عمدي محسوب ميشوند و نادر هستند. علاوه بر اين عوامل مخـرب مانند گرد و خاک، رطوبت و دماي محيط نيز باعث ايجاد خرابي ميشود که جزء عوامل طبيعي محسوب ميشوند. بلاياي طبيعـي بيشـتر منجـر بـه خرابي حالت مشترک ٥ ميشوند، زيرا اثر مخرب خود را بر روي تمامي گره هاي موجود در يک محدوده مشخص ميگذارند.
خرابيها از نظر ماندگاري به سه نوع ، خرابي دائمي، متناوب و گذرا تقسيم بندي ميشوند. خرابي دائمي خرابيهايي هستند که بصورت هميشگي و ثابت در شبکه رخ ميدهند و حسگر نميتواند خود را به وضعيت مطلوب برگرداند. خرابي متناوب خرابيهايي هستند که به صورت متناوب در فاصـله زماني مشخصي در شبکه رخ ميدهند. خرابي گذرا، که در يک برهه زماني رخ ميدهد و شبکه بصورت خود به خود، به وضعيت عـادي برمـيگـردد.
شناسايي اين نوع خرابي بخاطر ماهيت آن مشکل است و تنها با صرف زمان در شبکه قابل تشخيص ميباشد[١].
خرابيها از نظر نوع تأثير گذاري به دو گروه خرابي سخت ٦ و خرابي نرم ٧ تقسيم ميشـوند. در خرابـي سـخت يـک گـره بعلـت خرابـي در يکـي از قسمت هاي عمده آن ، نميتواند با گره هاي ديگر ارتباط داشته باشد. بعنوان مثال اتمام باتري در يک گره حسگر باعث قطـع کلـي ارتباطـات آن گـره شده و اين اشکال از نوع خرابي سخت محسوب ميشود. ولي در خرابي نرم گره هاي معيوب ميتوانند با گره هاي ديگر ارتباط برقـرار کننـد امـا داده ارسالي آنها صحيح نميباشد. بعنوان مثال اشکال در يکي از اجزاء گره حسگر که باعث قطع فعاليت کلي حسگر نشود، خرابي نرم گفته ميشود[٢].
در يک گروه بندي براي خرابيهاي نرم آنرا به چهار گروه تقسيم مي کنند. خرابي Stack-at fault که خرابي ايستا ميباشد و حسگر هميشـه داده ثابتي را ارسال ميکند. در خرابي Gain fault حسگر داده حس شده را در يک مقدار ثابت ضـرب مـيکنـد. خرابـي Offset fault کـه حسـگر داده حس شده را با يک مقدار ثابت جمع ميکند. در خرابي تصادفي حسگر داده هاي تصادفي ارسال ميکنـد. تفکيـک دو خرابـي Gain fault و Offset fault از همديگر بدون آگاهي از محيط حسگرها و تخمين داده توليدي از محيط تحت نظر امکان پذير نخواهد بود. خرابيهاي Gain fault و Offset fault به داده حس شده حسگر وابسته هستند ولي Stack-at fault و Random fault به داده هاي حس شده حسگر وابسته نيستند[٣].
نوع ديگري از خرابي که اغلب روش هاي مديريت خرابي در شناسايي آن با مشکل مواجه مي شوند خرابي حالـت مشـترک مـيباشـد. در ايـن نـوع خرابي ، حسگرهاي يک محدوده ، بنا به يک دليل مشترک و در يک زمان واحد خراب ميشوند. اغلب رو هاي کشف خرابـي، مبتنـي بـر مقايسـه و تصميم گيري محلي هستند که اين روش ها قادر به شناسايي خرابي حالت مشترک نيستند.
در صورت عدم مديريت خرابي شبکه ، از گر هاي معيوب بعنوان گره هاي ارتباطي استفاده خواهند شد که در نتيجه موجـب اخـتلال در مسـيريابي شده و همچنين بدليل نادرست بودن داده هاي توليد شده توسط گره ها، تصميمات نادرستي در شبکه اتخاذ ميشود. مديريت خرابي در شبکه حسگر شامل سه مرحله ي کشف خرابي، تعيين گره هاي معيوب و حذف گره هاي معيوب و بازيابي شبکه ميباشد[٥].
٣- بررسي تکنيک هاي کشف خرابي
کشف خرابي عبارتست از کشف هرگونه عامل مخرب که شبکه يا گره را از وضعيت مطلوب خارج ميکند. به تعيين گره هاي معيـوب و حـذف آنهـا و بازيابي شبکه ، اصطلاحا ترميم خرابي نيز گفته مي شود. تکني هاي کشف خرابي از نظر نحوه عملکرد بـه دو گـروه کشـف خرابـي متمرکـز و کشـف خرابي توزيع شده تقسيم بندي ميشوند. در روش کشف خرابي متمرکز يک گره حسگر بصورت متمرکز، خرابي موجود در گره هاي شبکه را شناسايي ميکند. اين روش در شبکه هايي با مقياس بزرگ قابل اجرا نيست . در روش کشف خرابي توزيع شده همه گره ها در تشخيص خرابي شرکت ميکنند.
در کشف خرابي توزيع شده ، گره ها با اطلاعات رسيده از همسايه ها و بر اساس رويکردهاي مشخص مانند رأي اکثريت يا مقايسه اطلاعات رسـيده بـا ميانگين اطلاعات همسايه ها قادر به کشف خرابي خواهند بود[٥].
در روش Mahmood از يک پردازنده نگهبان براي خطايابي شبکه هاي حسگر بيسيم استفاده شده است . پردازنده نگهبان ، کمک پردازنـده سـاده و کوچکي است که خرابي را از طريق کنترل رفتار سيستم کشف ميکند. مزيت اين روش ، پائين بودن سربار سخت افزاري آن ميباشد[٦].
در روش Khadivi در هر خوشه ، گره با حداکثر انرژي بعنوان سرخوشه انتخاب ميشود و گره ديگري در هر خوشه بعنوان سازماندهي کننـده در نظر گرفته ميشود که بر عملکرد سرخوشه نظارت ميکند و با ديگر گره هاي متحرک در ارتباط است و شبکه را در مقابل خرابي تحمل پذير ميکند.
مزيت اين روش افزايش طول عمر شبکه ميباشد[٧].
در روش Ruiz براي کشف و مديريت خرابي از روش مديريت متمرکز استفاده شده است . در اين روش يک مـدير خـارجي در شـبکه وجـود دارد.
مزيت اين روش اين است که مدير ديد وسيعي از شبکه دارد و ميتواند کارهاي پيچيده اي که انجام آنها در داخل شبکه امکان پذير نيسـت را انجـام دهد. اما برقراري ارتباط بين گره هاي حسگر و مدير، باعث اعمال سربار بسيار زيادي به سيستم ميشود که از معايب اين روش بحساب ميآيد[٨].
در الگوريتم Lee روش ساده با دقت بالا براي شناسايي حسگرهاي معيوب ارائه شده است . در اين الگوريتم براي تحمل پذيري خرابيهاي گـذرا از افزونگي زماني استفاده شده است . مزيت اين روش شناسايي خرابيهاي گذرا و دقت بالا در کشف گره هاي معيوب ميباشد. از معايـب ايـن الگـوريتم ناتواني در شناسايي و کشف خرابيهاي حالت مشترک ميباشد[٩].
Ding از يک روش محلي براي کشف خرابي استفاده کرده است . در اين روش اگر اطلاعـات رسـيده از هـر گـره تفـاوت چشـمگيري بـا اطلاعـات همسايه هايش داشته باشد، معيوب تشخيص داده ميشود. بايد توجه داشت که اين روش تشخيص موقعي مفيد خواهد بود که احتمال خرابي گره هـا پايين باشد. مزيت اين روش مقياس پذيري بالا و سربار محاسباتي پائين آن است . عيب اين روش اين است که اگر تعداد گـره هـاي معيـوب بيشـتر از گره هاي سالم باشد، قادر به تشخيص خرابي نخواهد بود[١٠].
در الگوريتم Chen يک رويکرد کشف خرابي توزيع شده براي شبکه هاي حسگر بيسيم ارائه شده است . در ايـن الگـوريتم بـراي رسـيدن بـه يـک تصميم قطعي در مورد وضعيت حسگرها، دو مرحله عمل مقايسه بين گره ها صورت ميگيرد. مزيت اين روش ، پايين بودن پيچيدگي اجراي الگـوريتم و بالا بودن احتمال تشخيص درست ، ميباشد و نيز اين الگوريتم خرابيهاي دائمي را پوشش ميدهد. عيب اين الگوريتم اين اسـت کـه ، خرابـيهـاي گذرا که در ارتباطات ممکن است براي بيشتر گره ها پيش آيد و خرابي حالت مشترک ناديده گرفته شده است [١١].
٤- مقايسه الگوريتم هاي کشف خرابي تحت بررسي
در اين قسمت الگوريتم هاي Chen ،Lee ،Jianliang و Jiang با جزئيات بيشتري مورد بررسي قرار ميدهيم .
٤-١ الگوريتم Lee براي کشف خرابي
مرحله اول : تمامي حسگرها ماتريس مجاورت که شامل شناسه گر هاي همسايه و ماتريس افزونگي که وضعيت داده هاي حس شده در هر بازه زماني را مشخص ميکند ايجاد ميکنند. وضعيت اوليه هر گره معيوب فرض مي شود.
مرحله دوم : داده هاي حس شده هر گره به تعداد بار با همسايگانش مقايسه مي شود، اگر ايـن اخـتلاف کمتـر از حـد آسـتانه باشـد، در مـاترس افزونگي مقدار صفر به مفهوم برابري داده ها و در غير اين صورت يک نوشته ميشود. مقايسه داده هر حسگر به تعداد بـار خرابـي گـذرا را پوشـش مي دهد.
مرحله سوم : اگر اطلاعات هر گره با  تا از گره هاي همسايه برابر باشد وضعيت گره به سالم تغيير پيدا مي کند.
مرحله چهارم : گره هايي که داراي وضعيت سالم هستند بصورت موازي وضعيتشان را به گره هاي همسايه ارسال ميکنند و آن گره ها براسـاس ايـن پيغام وضعيت خودشان را تعيين ميکنند.