مقایسه الگوریتم ­های خطایابی در شبکه­ های حسگر بی­سیم

صفحه 1:
کم سم ال رن ال گروه مهندسی کامپیوتر موضوع پروژه: مقایسه الگوریتمهای خطایابی در شبکههای حسکر بیسیم استاد راهنماء دانشجو : بهار ۱۳۹۳ 

صفحه 2:
نها و ضرورت هاى كلى اساغتار داغلى يك گر كاربره شبكه حسكر يسيم جالشهاى شبكه ای گر يسيم تحمل بذيرى خطا در شبكه هاى كر يسيم هس سره سیر تم ‎foe‏ مشكلات سر كروهها(كلاسثر هد الگوریتمهای خطا يابى در شبكه حسكر الكوريتم بيشتهادى براى تشخيص و تصحيح خطا قايسه و ارزيابى الكوريتم سيستم اعداد مانده لى با الكوريتم هلى قبل تصحیح خطا در برابر كمترين ميزان مصرف انرژی 

صفحه 3:
در این پروئه با توجه به محدودیتها و شرایط عملیاتی ویژهی شبکههای حسگر: روشی را برای بهبود تحمل پذیری خطا مانند تشخیص و تصحیح] تشخیص خطا و مصرف انرژٍی کمتر در شبکها إخطا در اين نوع شبكهها مورد بررسی قرار میدهیم. روش پیشنهادی به صورت روشی جدید لهای حسگر را بهبود میبخشد. لته الگوریتمهای دیگری هم عنوان شده است ام الگوریتم پیشنهادی کارایی بهتری نسبت به دیگر الگوریتمها دارد. شبكههاى حسكر بيسيم؛ تحمل بذيرى خطاء ترمیم وتصحیح خطا 

صفحه 4:
معد مه اه سر ییاز ستعل اربوای سس یدسا تسج ریسم مب یمرج سم و سا شاهدات را می دهد. اربردهای نوعی این نوع از حسگرها شامل جمع آوری داده؛ کنترل؛ نظارت و انجام اندازه گیریهای مختلف است. تجهیزات ارزان قب هوشمند همراه با چندین حسگر بر روی یک برد که از طریق لینکهای بیسیم با یکدیگر شبکه ای را تشکیل دادهاند امکانات این؛ شبکهها صتهای بسیاری را در مدیریت و کنترل شهرهاء خانه ها و حتی محیطهای پیرامون در اختیارمان قرار می دهند علاوه در مسائل دفاعی و نظامی مانند بررسی امکانات دشمن و نظارت بر اعمال و رفتار آنها امکانات فراوانی را در اختیار ما قرار 

صفحه 5:
همان طور که گفته شد تمایبل بیش پیشتر تحقیقات بر روی شبکههای حسگره وس کاربرد این شیکههای حسگر امروزه از سیستمهای کنترل صوتی زیر اقبانوسها گرفته تا شبکه های لحسگر بسیار کوچک و غير قابل شناسایی برای تعیین اهداف در میدانهای جنگ و محیط زیست |گسترده شده است. 

صفحه 6:
یک شبکه حسگر بیسیم مجموعه ای از تعداد بسیار زیادی گره حسگر با اعاد کوچکک و قبلیتهای مخابراتی و محاسباتی محدود است که به جمع آوری و انتقال اطلاعات از یک محیط به سمت یک کاربر و یا ایستگاه پایه به کاربرده می شود. فتهای اخیر در فناوری ساخت مدا مجتمع در اندازه های کوچک از یک سو و توسعه فناوری ارتباطات بیسیم از سوی ديكر, زمینه ساز طراحی شبکه های حسگر بیسیم گردیده است. تفاوت اساسی این شبکهها با شبکه های سنتی و قدیمی ارتباط آن با محیط و پدیدههای فیزیکی است. 

صفحه 7:
همان گونه که از شکل ميتوان ديد هر گره در يكك شبكه حسكرء شامل حس کننده؛ واحد بردازش داده هاء فرستنده- كيرنده بيسيم و منبع تغذيه ميباشد. بخشهاى اضافى؛ همچون واحد متحركك سازه سيستم مكان ياب و تولید توان نیز ممکن است بسته به کاربرد در گرهها وجود داشته باشد. واحدپرازش داد شامل بك بردازنده كوجدك و يكك حافظه با ظرفيت محدود ست كه ‎Wen pa fu Se tbat‏ كازيرد قورف إد نظرء يردازش محدودى روى آنها انجام ميدهد و لز طريق فوستئده رسال مى كند. واحد بردازش ه وظیفه مدیریت و هماهنگی و مشارکت با سایر گرهها در شبکه را انجام میدهد. واحد فرستنده -گیرنده ارتباط گره با شبكه را برقرار مى کند. واحد ‎Se‏ شامل یک سری حسگر و مبدل آنالوگ به دیجیتال است که اطلاعات آال وگ را از حسگر گرفته و به صورت ديجيتال به پردازنده تحویل می دهد. واحد تامین انرژیی» که اغلب یک باتری با انرژی محدود است توان مصرفی تمام بخشها را تامین می کند. ساختار داخلی یکت گره ‘Tranamigson Un Trmeeiver | ‎a |‏ و ‎Processor‏ عا ‎Storage ‏اس‎ ‎ ‎ ‎ ‎ ‎ ‎Power Unit ‎ ‎ ‎ ‏ا ومد ‎Sensor | ADC‏ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 8:
۱- مقایسه الگوریتمهای خطایابی در شبکههای حسگر بیسیم ۲-ارائه روش بهبود تحمل پذیری خطا در این نوع شبکه ها ۳-مصرف انرژی کمتر در شبکههای حسگر ۴-تشخیص خطا کمتر در شبکههای حسگر ۵-استفاده از سیستم اعداد ماندهای در ساختار شبکه حسگر جهت ترمیم وتصحیح خطا, 

صفحه 9:
۱ موارد استفاده از شبکه های سنسوری بی سیم متنوع و زیاد است. به عنوان مثال در کاربردهای تجاری و صنعتی برای کنترل داده‌ها و مواردی که استفاده از گیرنده‌ها: سیمی مشکل و گران است به کار می‌روند. برای مثال این شبکه‌ها می‌توانند در محیط‌های بیابانی هم گسترش يابند و سالها باقی بمانند. کاربرد دیگر اعلام خطر ورود مهاجم به یک محل کنترل شده و سپس ردیابی مهاجم است. از موارد دیگر کاربرد این شبکه هامیتوان به نظارت بر محل‌های مسکونی؛ ردیابی هدف‌های متحرککه کنترل راکتورهای هسته ای. آشکار سازی حریق. نظارت! ترافیک و ... اشاره نمود. نظارت بر محیط کنترل یا نظارت بر محیط نوعی استفاده از نده بی سیم است. 

صفحه 10:
چالشهای شبکه های حسگر پیسیم به طور کلی شبکههای حسگر با مسائل فنی از قبیل پردازش داده؛ ارتباطات و مدیریت حسگرها روبرو هستند و از دلائلی که سبب به وجود آمدن این مسائل شده است میتوان به استفاده از این شبکه ها در محیطهای خشن( گرما و سرمای زیاد)؛ نامعین و دینامیکک و همراه با محدودیتهای پهنای باند و انرژی اشاره کرد. همین عوامل سبب شده است تا شبکه های موردی ( بدون زیر ساختار) در مسیریابی و کنترل شبکه پردازش اطلاعات مشتررکک» روشهای تقاضا و انجام وظایف خود دچار مشکل گردند. 

صفحه 11:
تحمل پذیری خطا در شبکه های حسکر يسيم تحمل پذیری خطا را می توان در پنج سطح مورد بررسی قرار داد: لایهفیزیکی لایه سخت افزاری لسأ لايه نرم افزارى لأ لايه ميانى الا لايه كاريردى بيشترين اهميت تحمل يذيرى خطا در شبكه هاى حسكر بيسيم درون لايه سخت افزارى ولايه ارتباطى يا ميانى شبكه مى باشد. 

صفحه 12:
(خطا ]لا۴2): یک نقص فیزیکی یا عدم کا کرد یک مولفه سخت افزاری با نرم افزاری (اشتباه 6۲۳0۵۲): وجود خطا در یک سیستم. تشخیص خطا: برای تامین کردن هر ارزیابی اولین مرحله ای که یک سیستم باید انجام دهد شناسایی عملکرد های خطاست. بهبود خطا: بعد از اینکه سیستم خطا را شناسایی کرد گام بعدی این است که از خطا اجتناب شود یا خطا را بهبود داد. تکنیک اصلی دستیابی به این هدف تکرار اجزای سیستم(فزونگی)است که برای اجرای صحیح آن ضروری است. 

صفحه 13:
به علت فشار محيط و محصور سازی نامناسب؛ گره های حسگر در معرض تماس مستقیم با آب قرار می گیرند که باعث مدار کوتاه در آنها می شود. محصور كردن و در معرض گذاشتن فشار محیط میتولند باعث خرابی سخت افزار شود. نقص سخت افزاری به طور کلی باعث نقص نرم افزاری خواهد شد. یک برنامه اکتساب داده ای اگر سنسور های اصلی درجات را نادرست بخواند به طور صحیح انجام نخواهد شد. خرابی های نرم اقزاری یک منبع خطادر ‎WSN‏ ميباشد. محققان گزارش دادهاند که نقص یک نرم افزار باعث می شود که باشد تا گره ها بتونند به صورت دستی دوباره برنامه ریزی شوند. 

صفحه 14:
تعداد کمی از گره ها برای کلاستر هد انتخاب می شوند ‎OUT‏ مسئرول هماهنگی در گروه هایشان هستند. همچنیر مسژول جمع آوری داده ها از آنها و جلو رانندن آن به سمت ایستگاه اصلی خواهند بود. کلاستر هدی خراب است که نتواند هیچ داده ای را به سمتا ایستگاه های اصلی بفرستد.همچنین کلاستر هد ممکن است عمدا یا به علت نقص نرم افزاری اطلاعات نادرست بفرستد. بسته به حالتا کاربرد گره تآثير چنین خرابی می تواند از تنزل ارزیابی به هشدار پیام هایی تغیبر کند که به سیستم تحویل داده شده است. در حالی که با جلو رفتن پیام هاء گره ها می توانند داده های گره های متعدد را انباشت کنند. تا مقدار داده های فرستاده شده را به ایستگاه پای کاهش دهند. 

صفحه 15:
مسیریلبی یکی از بلوک های اساسی ساختمان در یک ‎WSN‏ مى باشد. براى جمع هاى سنسور نرم افزار توزيع كتنده و تنظیمات به روز رسانی؛ برای هماهنگی بین گره ها ضروری می باشد علاوه بر این ممکن است پروتکل های مسیر یبی خاص مورد ناز میباشد. به عنوانمثالبرای ردیابی کردن اهداف حرکت اشيامه خطاهای روی لایه مسير يابى فى تولئذ منجر به كافش پیام ها و گمراهشدا بر ‎UWSN‏ زوابط بين گره ها بى تهايت چند کاره است.[[5 18 ها همشه همان میزانتحویل یم ها را در آزمایشات حوزه همنن آزماشاتا آنها و یا باعث تاخیرات غیر قابل قبول آزمایشگاهی را نمی دهند اختلال راديوبى مى تولتد باعث رابطه بين ككره و خحرابى باشدء به عنوان مثال در زمین های کشاورزی مکان گره ها بايد به دقت در نظر كرفته شود ما بررسى كند جه موقع گیهان در محدوده ستیکک شروع با رشد مى كنند. يكى ديكر از منابع نقص. تصادم بيام ها است. محققان مشاهده كردند يكك يتانسيل براى برخورد بيام هاى گره های نزدیک به هم به دلیل تغیر فاز و همبوشانى ايجاد مى شود. در موقعيتا ديك ؛ اگر چه ممکن است اتصالاث كاء نشدند, یک نقص نرم افزاری در لیه مسیریابی می تواد پام ها رابه مقصد نادرست تحو لی داشته باشند» ام یام ها به علت خطای مسیر به مقصدشان تحویل دا دهد. تویز پذیری-تضعیف سيكنال به سبب فاصله ميان كره ها- عدم تقارن سينكك هاى ارتباطى و رخداد ازدحام در شبکه- خطا های کانل در طول ارسال داده-تداخل امواج- تصادم ناشی از رقلیت پر سر دسترسی به کانال مشترک-تداخل چند مسیری و اعوحاج ناشی از رخداد پدیده محو شد گی بر اثر طبیعت ‎JEN‏ 

صفحه 16:
عاای 071 ۹1 در یک سطح بزرگتر ‎SINTK oS‏ ابزاری است که همه ی داده های ایجاد شده در شبکه را گرد آوری می کند. و آن را به قسمت پایانی سیستم انتشار می دهد علت خطا در اینجا اجزایش می باشد. وقتی که این وسیله خراب و ناتوان است؛ اگر ارزیابی های تلرانس خطا موجود نباشد» یک خطای گسترده در شبکه اتفاق می افتد که داده ها را از گره های حسگر قابل دسترسی نیستنند. سينكك مى تواند در حوزه هايى كه هيج منبع ضروری بکار برده تغذیه دایمی وجود ندارد مستقر گردد. در چنین بر نامه های کاربردی باتری همراه با سلول های خورشیدی برای تا می شود. 

صفحه 17:
در اینجا خطا هایی را طبقه بندی می کنیم که یک *[5 ۷۷ به آنها حساس است که عبارتند از: سقوط گره یا حذف-زمانبندی- مقدار یا ارزش الف) سقوط یا حذف: وقتی یک سرویس از بين می ر در این صورت در صورت وجو: یک غواین آیباد من ۳ اضاها به آنها واکنش نمی دهد. حدف می تواند توسط اختلالات رادیویی ایجاد شود که منجر به از دست دادن پیام ها به صورت گاه گاه می شود؛ یک خرابی زمانی اتفاق می افتد که این ي در بعضی | نقطه ها متوقف می شود و به هر تقاضایی پاسخ می دهد. ب)زمانبندی: خرایی زمانبندی فقط زمانی اتفاق می افند که برنامه از محدودیت زمانی استفاده می کند. ج)مقدار یا ارزش: ست. خراب در نظر گرفته می شود اگر چه زمانی که سرویس؛ یک واکنش به موقع می فرسند 

صفحه 18:
شده به طور صحیح عمل کند. ساده ترین روش انجام يكك جنين و مشاهده دیداری و برداشت دستی مقادیر نادرست می باشد» این روش دارای اشکالاتی است. تقابل عمل انسان منجر به اشتباه می شود که هزینه بالایی دارد و سودمند نیست بنابراین ما تکنیک های تشخیص خطای اتوماتیک را بررسی کرده وآنها را طبقه بندی) کردیم و با توجه به طرف درگیر در این فرایند مورد بررسی قرار دادیم. از طریق تشخیص خود گره می تواند خطاها را در اجزایش تشخیص داد. 

صفحه 19:
الكوريتمهاى خطا يابى 0 شبکه. محدوده ای از ارسال بسته از گرهمبدابه مقصد در نظر گرفته شده است که می بایستی این گره ها پاسخ دریافتی رابه گره مبدا ارسال کند بهبود تحمل پذیری خطا مسیرهای دیگری که در اولین مکان یابی توسط گره ها انجام می شود ؛ همچنین گره مقصد مسیرهای نزدیک به گره مبدا را محاسبه و در آن بسته جایگز: من ند گزه های ‎teas era lao‏ گرههای سار زميق غناك کسدهبو گره مای تجایگزین نیم ‎aad cea‏ ند و از معتاری وود ریق که عبت اول 5ن لزه مانا کمک کننده واقعی و در ردیف گره های حسگر استفاده شده است که از اين سبکک معماری می توان جهت توانا سازی کشف خطا درون شبکه حسگر بیسیم استفاده کرد در این الگو یتم گره هاى كمكك کننده» جایگزین شوند قبل از تبودی کامل گره اصلی بر اثر ی و عوامل خطای درون شبکه, جا ن آن میشود همچنین گره های کمکدا کننده جایگزین شونده نیز به دو دسته عقبی پاینی و جلویی پایینی دسته بندی می شوند که هدف از دسته دوم جم‌آوری اطلاعات و ذخیره آن و تحویل به دسته عقبی پایین باشد. 

صفحه 20:
الگوریتم پیشنهادی برای تشخیص و تصحیح خطا ثبکه حسگر بیسیم یک شبکه ویژ است که مصرف انرژی در آن یک مسئله مهم است. از آنجائیکه حسگر های بیسیم دارای محدودیت انرژی هستند. و عمر شبکه به اين موضوع بستگی دارد؛ تمامی کد های تصحیح خطا برای این کاربردها مناسب نمی باشند به همین منظور از پروتکل سیستم اعداد مانده ای برای حل این مشکل| استفاده شده است. ه رگاه بخواهیم قابلیت تشخیص و تصحیح وامنیت اطلاعاش در سیستم اعداد مانده ای داشته باشیم. پیمانه هایی به سیستم افزوده می شود که ۱ پیمانه های افزونه و چنین سیستمی را سیسیتم اعداد مانده ای افزونه می نامند. این سیستم دارای ۱+۲ پیمانه می باشد که (1 پیمانه اصلی(مجموعه پیمانه هایی که برای کد گذاری کافی است) و ۲ پیمانه افزونه(مجموعه پیمانه هایی که برای تشخیص و تصحیح خطا اضافه می شوند) داریم. 

صفحه 21:
موزل 7 مدای رم ای ‎a‏ لگوریتم سیستم اعداد مانده ای دارای تاخیر کمتر نسبت به الگوریتم های موجود می باشد که به اين دلیل می باشد که نیاز به ارسال مجدد ندارد در ضمن از مسیرهایی ارسال می شود که قابلیت اطمینان بالاتری دارند همچنین محتویات ‎ply‏ به مجموعه ای از پیمانه های کوچک تقسیم شده| باقی مانده اعداد ارسال می شود. 

صفحه 22:
در شکل مقابل مصرف انرژیی در مقابل قابلیت تصحیح خطا نشان داده شده است که در الگورریتم سیستم اعداد مانده ای به علت اینکه تشخیص و تصحیح خطا دارای قابلیت بالایی هست و نیاز به ارسال مجدد خیلی کم می باشد بنابراین انرژی مصرفی نیز کمتر خواهد بود. در الگوریتم سیستم اعداد مانده ای در مسیریابی ما بسته هایی با پیمانههای متفاوت را از چندین مسیر كه هر مسير شامل بستهای با بقیماندههای یک مجموعه پیمانه هست ارسال می نمایيم.بنابراین بسته گمشده كمترى خواهيم داشت و در صورتی که بستهای گم شود میتوان از مجموعه پیمانههای دیگر نیز برای بازیابی اطلاعات استفاده نمود. = = 

صفحه 23:


صفحه 24:
بافته ها در شبکههای حسگر مشکل شناسابی و مجزا کردن خطا بنابه ماهیت ساختار و استقرارشان یک وظیفه سخت افزار به شمار مبآید.انواع خطاهای بیتی در ارتباطات بیسیم؛ می تواند به عنوان خطاهای تصادفی و یا خطاهای متوالی طبقه بندی شود. برای خدمات تشخیص و تصحیح خطا در شبکههای حسگر بیسیم؛ معمولا پروتکلهای ارتباطی موجود درا لایه های پیوند داده فراهم می شود. الگوریتمهای اصلاح فراوانی وجود دارد که در شبکههای حسگر قابل پیاده سازی نیست. چون سخت افزارهای خاصی می طلبد یا قدرت) تصحیح ندارند که باعث تقاضای مجدد و مصرف توان بیشتر می شوده که مقرون به صرفه نیست. شبکههای حسگر پیسیم توجه محققان را در زمبنه های متنوع به علت نقش کلیدی شان در انواع کاربرد های گسترده ماند: نظارت بر محل سکونت و محیط دقاع نظامی؛ سیستمهای هشدار حادثهه کشاورزی و به خود جلب کرده است. شبکه های| حگر بیسیم شامل تعداد زیادی گره حسگر شبکه بندی شده هستند که داده های حسگر را به چاهک یا مرکز پخش روی لینکهای بیسیم ارسال می کند. در طول این فرایند ارسال و دریافت؛ خطاها در داده ها دریافت شده به علت نويز در كيرنده و ماهیت محو شدگی کانال بیسیم به وجود می آید. قبلیت اطمینان داده یک فاکتور خیلی مهم برای| پیاده سازی عملی شبکههای حسگر بیسیم مخصوصا در کاربردهای اتوماسیون و تشخیص خطر است. 

صفحه 25:
رخی از مشکلات شیکههای حسگر ‎tl ogee‏ در دادههاى منتقل شده؛ انرزى مصرفى كرهها و تاخير مى باشد سپس برض از قاب هاى موجود در 11115 مى ‎ily‏ به منظور بهبود مشکلات موجود در شبکه ها حسگر بیسیم استفاده شوند. مزایای شرح داده شده) ۱ کاهش میزان ترافیک در شبکه های حسگر بیسیم. با کاهش میزان انتقال داده که باعث کاهش انریی مصرفی گرههای حسگر می شود ی بر اين 1115 قابلیت تشخیص و تصحیح خطا را در دادههای انتقالی با حداقل افزونگی وبا پیچید گی بسیار پایین (100)10 انرژی محاسباتی کمتری برای کد گذاری و تشخیص و تصحیح خطا در شبکه. گرهها انرژی کمتری از دست می دهنددر ضمن پیچیدگی| الگوریتمهای مورد مقایسه (0)10 می باشد. 

صفحه 26:
در كل ميتوان نتيجه كرفت که خطا در شبکههای حسگر امری غیر قابل اجتناب است اما میتوان برای بالا بردن کارایی » خطا را به حداقل رساند. دلایل عمده به وجود آمدن خطا در شبکه های حسگر بیسیم عبارتند از: ‎)١‏ از دست دادن انرژی ۲ خرابی فیزیکی ش ۴ مشکلات سخت افزاری و نرم افزاری 

صفحه 27:
سه دلیل اصلی که باعث خطای سخت افزاری درون شبکههای حسگر بیسیم میشود عبار تند از: ۱)گرههایی که در موارد تجاری از آنها استفاده میشوند و دارای کیفیت خوبی نیستند ۲)اختلال انرژی و محدود بودن درون گره حسگر “)تحت تاثیرقرار گرفتن گرهها در شرایط جوی و محیطی 

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

صفحه 29: