چکیدهاقناع قابلیت اطمینان مورد انتظار، یکی از چالشهای مهم در شبکههای حسگر بیسیم است.یکی از راهکارها برای افزایش قابلیت اطمینان استفاده از پروتکلهای مسیریابی چند مسیره است که در آنها بستههای داده از چندین مسیر به سمت مقصد هدایت میشوند. از یک طرف استفاده از تعداد زیادی مسیر، ممکن است سربار زیادی به شبکه تحمیل نماید.از طرف دیگر استفاده از مسیرهای کمتر ممکن است قابلیت اطمینان مورد انتظار شبکه را برآورده نکند؛ لذا وجود یک پروتکل تطبیقی که بتواند تعداد مسیرهای مناسب را به منظور اقناع قابلیت اطمینان مطلوب برقرار نماید، ضروری است. در این پایاننامه ابتدا یک پروتکل چند مسیره مبتنی بر DDبه نام LOMDDپیشنهاد و پیادهسازی میشود. در پروتکل چند مسیره پیشنهادی از یک مسیر به عنوان مسیر اصلی و از سایر مسیرها به عنوان جایگزین استفاده میشود. در ادامه یک راهکار برای تخمین قابلیت اطمینان مبتنی بر OBDDدر شبکههای حسگر بیسیم پیشنهاد و پیادهسازی میشود. راهکار پیشنهاد شده با دقت مناسبی قابلیت اطمینان کل شبکه را بر حسب قابلیت اطمینان لینکهای شبکه محاسبه میکند. در پایان یک پروتکل چند مسیره تطبیقی برای اقناع قابلیت اطمینان به نام AMPRSپیشنهاد و پیادهسازی میشود. پروتکل پیشنهادی بسته به شرایط شبکه (احتمال موفقیت لینکها، انرژی گرهها، قابلیت اطمینان مسیرها و دیگر پارامترها) مسیرها را به نحوی تعیین مینماید، که کمترین میزان مسیرها را استفاده کرده و قابلیت اطمینان مورد نظر را اقناع مینماید. پروتکل پیشنهادی سربار شبکه را حداقل میکند و میزان انرژی مصرف شده را کاهش می‌دهد. نتایج شبیهسازی حاکی از تطبیق پذیری بالای AMPRSبا شرایط شبکه میباشد.کلمات کلیدی : شبکههای حسگر بیسیم، قابلیت اطمینان، چند مسیره، دسترس پذیری فهرستفصل 1 مقدمه‌ای بر شبکههای حسگر بیسیم11-1............................................. مقدمه21-2............ کاربردهاومزاياياستفادهازشبکه‌هایحسگر31-3.................... محدودیت‌هایسختافزارييکگرهحسگر51-4................................ معماريشبکه‌هایحسگر61-5...................... معماريارتباطيدرشبکه‌هایحسگر61-6................................... اجزايسختافزاري71-6-1........... کنترلر یا واحد پردازنده مرکزي (CPU):81-6-2........................ فرستنده گیرنده-رادیویی91-6-3................................... حافظه جانبي91-6-4.................................. انواع حسگرها101-6-5.................................... منبع تغذيه101-6-6..................... باطري‌ها و سلول‌های خورشيدي111-7................................... اجزاينرمافزاري111-7-1............................... سيستمعامل Tiny OS111-8.............................................. خلاصه12فصل 2 تعریف مسئله132-1....................................... دسترس پذیری142-2................ دلایل وجود خطا در شبکههای حسگر بیسیم142-3........ دلایل نیاز به یک پروتکل با قابلیت تحمل پذیری خطا در شبکههای حسگر بیسیم نسبت به شبکههای دیگر152-4............ طبقه‌بندی تکنیک‌های قابلیت تحمل پذیری خطا152-5................................ مسیریابی چند مسیره172-5-1................................. مسیرهای مستقل182-5-2............................ مسیرهای شبه متمایز192-6.................................... قابلیت اطمینان192-7............................... نتیجه‌گیری و هدف کلی20فصل 3 مروری بر کارهای مرتبط و پروتکلهای مسیریابی213-1.............................. روش انتشار هدايت شده223-1-1................................. دسته خصوصیت‌ها243-1-2..................... روش انتشار جذب يک مرحله‌ای253-2کاربرد کدینگ در مسیریابی چند مسیره برای افزایش تحمل پذیری خطا263-2-1...................................... Erasure coding263-3چالشهای مختلف در مسیریابی چند مسیره برای افزایش قابلیت اطمینان293-3-1.... چالش بین سربار ترافیک و مسیریابی چند مسیره293-3-2....... چالشهای بین مصرف انرژی و قابلیت اطمینان313-3-3... محاسبه قابلیت اطمینان در شبکههای حسگر بیسیم35فصل 4 پروتکل پیشنهادی LOMDD384-1............................................. مقدمه394-2................. نحوه عملکرد پروتکلپیشنهادیLOMDD404-2-1................... فاز اول : انتشار علاقه‌مندی‌ها404-2-2.............. فاز دوم : انتشار بستههای اکتشافی424-2-3................ فاز سوم : ارسال داده‌های تقویتی474-2-4........ فاز چهارم: ارسال داده‌ها و تعویض مسیرها494-3......................... نحوه پیاده سازی و ارزیابی544-3-1............................... بستر پیاده سازی544-3-2........................... سناریوهای شبیه سازی554-4............................. بررسی نتایج شبیه سازی554-4-1......................... سربار بستههای اکتشافی554-4-2میانگین تعداد بستههای دریافتی در هر لحظه توسط چاهک564-4-3................................ قابلیت اطمینان564-4-4........................ سربار بستههای غیر داده574-5.............................................. خلاصه58فصل 5 پیشنهاد یک راهکار برای تخمین قابلیت اطمینان با استفاده از دیاگرام تصمیم‌گیری دودویی مرتب شده605-1............................................. مقدمه615-2................. دیاگرام تصمیم گیری دودویی مرتب شده625-2-1........................ درخت تصمیم گیری دودویی645-2-2....................... نمودار تصمیم‌گیری دودویی665-2-3...... نمودار تصمیم گیری دودویی مرتب شده (OBDD)685-3تحلیل و تخمین قابلیت اطمینان با استفاده از یک راهکار پیشنهاد شده مبتنی بر OBDD695-3-1................................ قابلیت اطمینان695-3-2..... نمادهای استفاده شده در راهکار پیشنهاد شده705-3-3................ نحوه عملکرد راهکار پیشنهاد شده715-4.............................................. خلاصه80فصل 6 پیشنهاد یک پروتکل چند مسیره تطبیقی برای اقناع قابلیت اطمینان826-1............................................. مقدمه836-2پروتکل چند مسیره تطبیقی پیشنهادی برای اقناع قابلیت اطمینان856-2-1................................. تنظیمات اولیه866-2-2........................................ تعاریف876-2-3.......................... نحوه تصمیم گیری چاهک886-2-4.. نحوه انتخاب مسیر هنگام افزایش یا کاهش مسیرها916-3......................... نحوه پیاده سازی و ارزیابی916-3-1........................... سناریوهای شبیه سازی926-3-2....................................... مدل خطا926-3-3........................................ مقایسه946-3-4......................... محاسبه قابلیت اطمینان956-3-5....... محاسبهمیانگین تعداد مسیرهای استفاده شده956-3-6.................................. محاسبه سربار966-3-7......................... محاسبه انرژی مصرف شده966-4................................... نتایج شبیه سازی976-4-1................................ قابلیت اطمینان976-4-2.......................... تعداد میانگین مسیرها1016-4-3.................................... سربار شبکه1016-4-4................................ انرژی مصرف شده1026-5.............................................. خلاصه106فصل 7 جمع بندی و نتیجه‌گیری1077-1............................ پروتکل چند مسیره LOMDD1087-2راهکاری برای تخمین قابلیت اطمینان با استفاده از دیاگرام تصمیم‌گیری دودوییمرتب شده1097-3.. پروتکل چند مسیره تطبیقی برای اقناع قابلیت اطمینان1107-4........................................ کارهای آتی1117-4-1گسترش LOMDDبرای توزیع بار در میان مسیرهای موجود1117-4-2گسترش LOMDDبرای توزیع بار در میان مسیرهای موجود با استفاده از کدینگ1117-4-3......... بهینه سازی مسئله اقناع قابلیت اطمینان111فهرست منابع و مآخذ112ضمیمهها115 علائم اختصاری Wireless Sensor NetworksLow Overhead Multipath Directed DiffusionDirected DiffusionBinary Decision DiagramOrder Binary Decision DiagramRoute requestRoute replyExploratory DataTwo-phase-pullGeographic Energy Aware RoutingDirected Acyclic GraphMinimum-Distance Multi-Hop ModMaximum-Distance Multi-Hop ModelRandom-Distance Multi-Hop ModelAdaptive Multi-path Protocol for Reliability SatisfactionReliable Fault-Tolerant MultipathSensor Protocols for Information via NegotiationOperating SystemsCentral Process UnitGlobal Positioning SystemInter-Integrated CircuitWSNLOMDDDDBDDOBDDRresRrepEDTPPGEARDAGMINMHMMAXMHMRMHMAMPRSRFTMSPINOSCPUGPSI2C فهرست جداول جدول 3‑1 : جدول تصمیم گیری چاهک29جدول 5‑1 : مشخصات لینک شماره 4 در شکل 5-1272جدول 6‑1: مشخصات پارامترهای شبیه سازی93 فهرست اشکالشکل 1‑1 : نحوه طبقه بندی گرهها در شبکههای حسگر بیسیم [4]7شکل 1‑2 : معماريارتباطيشبکه‌هایحسگربيسيم [4]7شکل 1‑3 : معماري سخت افزار هر گره شبکههای حسگر[4]8شکل 2‑1 : مسیرهای متمایز18شکل 2‑2 : مسیرهای شبه متمایز19شکل 3‑1 : ارسال داده با استفاده از erasure coding25شکل 3‑2 : ساختار Rreq28شکل 3‑3 :ساختار Rrep28شکل 3‑4 : تقسیم فضای شبکه به شش ضلعی‌ها35شکل 4‑1: اطلاعات موجود در بسته علاقه‌مندی40شکل 4‑2: انتشار بستههای علاقه‌مندی در شبکه توسط گرهها40شکل 4‑3 : تنظیم گرادیان‌ها در پروتکل DD41شکل 4‑4 : تنظیم گرادیان‌ها در پروتکل LOMDD41شکل 4‑5 : نحوه انتشار داده‌های اکتشافی در پروتکل انتشار هدایت شده42شکل 4‑6 : نحوه ارسال داده‌های اکتشافی توسط منبع درLOMDD43شکل 4‑7 : نحوه انتقال بستههای اکتشافی در گره‌های میانی و ارسال nackpathدر LOMDD44شکل 4‑8 : یک ارسال موفق داده اکتشافی در LOMDD44شکل 4‑9 : ارسال داده اکتشافی بعد از یک انتقال ناموفق در LOMDD45شکل 4‑10 : نحوه مسدود شدن یک مسیر در هنگام انتقال داده‌های اکتشافی در LOMDD45شکل 4‑11: فلوچارت تصمیم گیری گره‌های میانی برای بستههای اکتشافی و Nackpath46شکل 4‑12 : دریافت بستههای اکتشافی در چاهک47شکل 4‑13 : نحوه ارسال داده‌های تقویتی در DD47شکل 4‑14: نحوه ارسال داده‌های تقویتی در LOMDD48شکل 4‑15 نحوه انتقال داده‌ها در LOMDD49شکل 4‑16 : نحوه انتقال داده‌ها در DD49شکل 4‑17: نحوه انتقال بستههای Check-live-path50شکل 4‑18 : نحوه انتقال بستههای Ack-live-path50شکل 4‑19: خراب شدن یک گره و نحوه تغییر شمارنده در منبع و چاهک51شکل 4‑20 : نحوه ارسال front-negative-reinforcement52شکل 4‑21 :نحوه ارسال Back-negative-reinforcement52شکل 4‑22 : نحوه بررسی کردن زنده بودن گره‌های بعدی روی هر مسیر53شکل 4‑23 : نحوه ارسال Negative-reinforcement54شکل 4‑24 : جایگزینی مسیر با خراب شدن مسیر اصلی54شکل 4‑25: سربار بستههای اکتشافی56شکل 4‑26 : میانگین تعداد بستههای دریافتی در هر لحظه توسط چاهک57شکل 4‑27 : قابلیت اطمینان57شکل 4‑28 : سربار بستههای غیر داده58شکل 5‑1 : یک درخت انشعاب شده63شکل 5‑2 : نمایشی از درخت تصمیم گیری دودویی63شکل 5‑3 : نمایشی فشرده از درخت تصمیم گیری دودویی شکل 5-264شکل 5‑4 : ارزیابی فرمول با استفاده از درخت تصمیم گیری دودویی65شکل 5‑5: الگوریتم ساخت درخت تصمیم گیری دودویی65شکل 5‑6 :تبدیل درخت دودویی به BDD66شکل 5‑7 : یک درخت دودویی با آزمایش روی فرمول 66شکل 5‑8 : BDDبدست آمده از درخت دودویی شکل 5-767شکل 5‑9: یک BDDمرتب نشده68شکل 5‑10: دو OBDDو یک گراف کلی که هر دو را در بردارد.68شکل 5‑11 : نحوه نمایش گرهها و کمان‌ها در راهکار پیشنهاد شده70شکل 5‑12 : شبکه با دو منبع و یک چاهک71شکل 5‑13 گراف به دست آمده از شبکه شکل 5-12 با استفاده از راهکار پیشنهاد شده72شکل 5‑14 : شبه کد مراحل راهکار پیشنهاد شده برای تشکیل گراف جهت تخمین قابلیت اطمینان79شکل 5‑15 : قابلیت اطمینان شبکه شکل 5-12 به صورت تحلیلی و شبیه سازی80شکل 6‑1: شبکه با سه مسیر مستقل از منبع به چاهک84شکل 6‑2 : قابلیت اطمینان مسیرهای مختلف برای توپولوژی شکل 6-184شکل 6‑3 : فلوچارت عملکرد و تصمیم گیری چاهک در AMPRS90شکل 6‑4 :احتمال موفقیت لینکها با توجه به نرخ خطا94شکل 6‑5 :مقایسه قابلیت اطمینان AMPRSدر حالت‌های مختلف با LOMDDدر حالت استاتیک98شکل 6‑6 : تطبیق پذیری قابلیت اطمینان در AMPRS با تغییرات قابلیت اطمینان مورد انتظار و نرخ خطا99شکل 6‑7 : تطبیق پذیری تعداد مسیر انتخاب شده در AMPRS با تغییرات قابلیت اطمینان مورد انتظار و نرخ خطا99شکل 6‑8 : مقایسه تعداد مسیرهای استفاده شده در AMPRS با LOMDD100شکل 6‑9 :مقایسه سربار ناشی از مسیرهادر AMPRS103شکل 6‑10 : سربار اعمال شده به شبکه در AMPRS با تغییرات قابلیت اطمینان مورد انتظار و نرخ خطا104شکل 6‑11 : انرژی مصرف شده در AMPRS با تغییرات قابلیت اطمینان مورد انتظار و نرخ خطا104شکل 6‑12 : میانگین انرژی مصرف شده گرهها در AMPRS105 فصل 1امروزه بحث سيستمهاي کنترل و نظارت از راه دور يکي از مباحث پر چالش در زمينه علوم الکترونيک و کامپيوتر ميباشد. لذا تحقيقات در هر زماني به دنبال راهحلي ميباشد تا به شرايط خاص و انتظارات مدنظر ما پاسخ دهد؛ در شرايط و کيفيت کاري يکسان هر چه نسبت هزينه به کارائي پایین‌تر باشد، همان قدرمحبوبيت آن شيوه بالاتر خواهد رفت.براي آگاهي از تغييرات محيط اطراف و يا وضعيت هر مجموعه نيازمند به يکسري تجهيزات هست، که به عنوان حسگر[1] شناخته ميشوند و تغييرات مدنظر (تغييرات فيزيکي يا شيميائي) را در قالب يک پاسخ، به منظور اندازه‌گيري ميزان تغييرات و يا وجود آن، بررسی مینمایند. پس از جمعآوري اطلاعات مورد نياز مي‌توان ساير عمليات را بر اساس پاسخ ارائه شده انجام داد [1]و [2].پیشرفت‌های اخير در زمينه الکترونيک و مخابرات بيسيم باعث شدهاست، بتوانيم گرههاي حسگر چندکاره، با توان مصرفي پایین و هزينه کم داشته باشيم. این حسگرها از نظر اندازه بسیار کوچک هستند و براي مسافت‌هاکوتاه ميتوانند با هم ارتباط برقرار کنند. اين گرههاي حسگر کوچک طبق نظريه شبکههاي حسگر، داراي تجهيزات حس کردن، پردازش داده‌ها و مخابره آنها ميباشند. تفاوت اصلي شبکههاي حسگر بیسیم[2] با ساير شبکهها در ماهيت داده-محورو همچنين منابع انرژي و پردازشي بسيار محدود در آنها است. این تفاوتها موجب شده تا روش‌هاي مطرح شده جهت انتقال داده‌ها در ساير شبکهها و حتي شبکه‌هايي که تا حد زيادي ساختاري مشابه شبکههاي حسگر دارند (مانند شبکههاي موردي سيار[3] )، در اين شبکهها قابل استفاده نباشند. روند توسعه اين شبکهها در حدي است که مطمئناً اين شبکهها در آينده نزديک، نقش مهمي را در زندگي روزمره ما ايفا خواهند کرد.تکنيک‌ها و شيوههاي مورد استفاده در چنين شبکههاي وابستگي شديدي به ماهيت کاربرد شبکه دارد. ساختار توپولوژي شبکه، شرايط جوي و محيطي، محدودیت‌ها و ... عوامل موثري در پارامترهاي کارايي و هزينه شبکه ميباشند؛ لذا امروزه در سرتاسر دانشگاههاي معتبر و مراکز تحقيقاتي کامپيوتري، الکترونيکي و به خصوص مخابراتي، شبکههاي حسگر بيسيم، يک زمينه تحقيقاتي بسيار جذاب و پرطرفدار محسوب مي‌شود. تحقيقات و پيشنهادات زيادي در مباحث مختلف ارائه شده است و همچنان حجم تحقيقات در اين زمينه سير صعودي دارد.هدف اصلي تمامي اين تلاشها و ارائه راهکارها، داشتن سيستمي با شيوههاي کنترلي ساده، آسان و با هزينه پایین ميباشد. همچنین با پاسخگويي به نيازمنديهاي ما بتواند در مقابل محدوديتها (پهناي باند، انرژي، دخالت‌هاي محيطي، فيدينگ و ... ) ايستادگي کند و شرايط کلي را طبق خواسته‌ها و تمايلات ما (انتقال حجم زياد اطلاعات پر محتوا، بقاء پذيري و طول عمر بالا، هزينه پایین و...) را فراهم سازد؛ لذا محققين جنبههاي مختلف را تحليل و بررسي مينمايند و سعي مي‌کنند ايدههاي بهينه و کارا را استخراج کنند. اين ايدهها ميتوانند از محيط وحش اطرافمان الهام گرفته شده باشد و با استفاده از قوانين رياضي و نظريات تئوري و آماري مي‌توان آنها را تحليل نمود.در سالهاي اخير، رشد بسياري را در زمينه شبکههاي حسگر بیسیم [4] شاهد بودهايم. شبکههاي حسگر شامل تعداد زيادي از گرههاي[4] حسگر بسيار کوچک ميباشند که براي جمعآوري و پردازش اطلاعات محيطي، مورد استفاده قرار ميگيرند. بر خلاف شبکههاي موردي که شايد در نگاه اول بسيار شبيه به شبکههاي حسگر به نظر بيايند، گرهها در شبکههاي حسگر، معمولاً فاقد آدرسهاي منحصر به فرد ميباشند و آنچه بيشتر در اين شبکهها حائز اهميت است، اطلاعات جمعآوري شده توسط حسگرهاي شبکه است. همچنين به دليل عدم دسترسي به گرهها پس از فرآيند پراکندن آنها در محيط، گرههاي شبکه پس از مصرف انرژي موجود، عملاً بدون استفاده شده و خواهند مرد. بنابراین مسئله انرژي و بهينهسازي مصرف آن، يکي از چالشهاي مطرح در اين شبکههاست و کارهاي زيادي هم در سالهاي اخير در اين مورد صورت گرفته است.