باشد. این لیست نشان می­دهد که لینک­های ۴ و ۶ فعال و لینک­های ۲ و ۳ غیرفعال هستند. با وجود این لینک­های غیر فعال نمی­ توان گفت شبکه غیر قابل اطمینان است و در واقع وابسته به بسط دادن لینک­ها در سطوح بعدی است. در نتیجه به گام ۲ می­رود تا بقیه حالات بررسی شود.
گام ۸. حذف افزونگی­ها
در اینجا برای هر یک از زیر شاخه­ های این گره (N_L) بررسی می­ شود که آیا زیر گرافی همریخت با زیر گراف­های مربوط به این گره وجود دارد یا خیر؟ اگر چنین زیر گرافی وجود داشته باشد زیر گراف مربوط به شاخه مورد نظر حذف می­ شود و کمان مربوطه به زیر گراف همریخت متصل می­گردد. سپس به گام قبلی بازگشت داده می­ شود.

به طور مثال در شکل ۵-۱۳ زیر گراف مربوط به شاخه سمت راست، از سمت چپ‌ترین گره در سطح ۳ با زیر گراف مربوط به شاخه سمت چپ از سمت راست‌ترین گره در سطح ۵ با یکدیگر همریخت هستند؛ لذا همان‌طور که در شکل پیداست کمان‌های مربوطه به هر دو زیر شاخه به زیر گراف مربوطه متصل می­گردند.
شبه کد مراحل راهکار پیشنهاد شده برای تشکیل گراف جهت تخمین قابلیت اطمینان در شبکه ­های حسگر بی­سیم در شکل ۵-۱۴ نشان داده شده است.
محاسبه قابلیت اطمینان
بعد از اجرای الگوریتم روی شبکه مورد نظر و بدست آوردن گراف می­توان قابلیت اطمینان را محاسبه کرد. برای محاسبه قابلیت اطمینان از یک رابطه بازگشتی که قانون شانون [۲] نامیده می­ شود استفاده می­کنیم این رابطه در فرمول ۵-۴ نشان داده شد است :
(۵-۴)
که در این معادله قابلیت اطمینان زیر گراف­های مربوط به لینکe_i است. قابلیت اطمینان مربوط به زیر گراف سمت راست و قابلیت اطمینان مربوط به زیر گراف سمت چپ می­باشد. P احتمال موفقیت لینک e_i را نشان می­دهد.
برای محاسبه قابلیت اطمینان این فرمول از ریشه شروع کرده و در کل سطح­های گراف گسترش پیدا می­ کند. هنگامی که به گره Reliable می­رسد مقدار ۱ برگردانده می­ شود. همچنین با رسیدن به گرهUnreliable مقدار صفر برگردانده می­ شود. شکل ۵-۱۴ قابلیت اطمینان شبکه را با توجه به احتمالات مختلف از لینک­ها برای شبکه شکل ۵-۱۲ نشان می­دهد. همچنین نتایج شبیه سازی برای این شبکه که در شبیه‌ساز NS-2 شبیه­سازی شده است در شکل نشان داده شده است. همان‌طور که مشاهده می­ شود قابلیت اطمینان با یک تقریب خوب تخمین زده می­ شود. این راهکار به طور کامل در زبان C++ پیاده­سازی شده است.
R_OBDD (LinkList-v) {
If (Network-Is-Reliable()){
Connect last arc in LinkList-v to Reliable Node
return
}
If (Network-Is-UnReliable() or List-Is-empty(LiskList)){
Connect last arc in LinkList-v to UnReliable Node
return
}
Link=select-link(L) // Index L of LinkList
N_L =Create-node(Link)
Connect last arc in LinkList-v to N_L
L++;
Extract N_L and create
Add to end of LinkList-v
Pos(N_L)=R_OBDD(LinkList-v)
remove from end of LinkList-v
L=T_SL+L-1
Extract N_L and create
Add to end of LinkList-v
Neg(N_L)=R_OBDD(LinkList-v)
remove from end of LinkList-v
if (check-Equal(Pos(N_L) , Neg(N_L) ))
merge Pos(N_L) and Neg(N_L)
if (pointer=Find-Isomorphic(Pos(N_L)))
connect to pointer
if (pointer=Find-Isomorphic(Neg(N_L)))
connect to pointer
return
}
شکل ‏۵‑۱۴ : شبه کد مراحل راهکار پیشنهاد شده برای تشکیل گراف جهت تخمین قابلیت اطمینان
شکل ‏۵‑۱۵ : قابلیت اطمینان شبکه شکل ۵-۱۲ به صورت تحلیلی و شبیه­سازی
خلاصه
در این فصل با توجه به تعریف قابلیت اطمینان، مسیرهای موجود برای انتقال داده و لینک­های مرتبط به مسیرها یک راهکار جدید مبتنی بر OBDD برای تخمین قابلیت اطمینان در شبکه ­های حسگر بی­سیم پیشنهاد شد. راهکار پیشنهاد شده یک راهکار بازگشتی است که با کاهش محاسبات اضافی و حذف زیر گراف­ها^[۱۷۹] یک الگوریتم کارا برای محاسبه قابلیت اطمینان پیشنهاد می­ کند.
با حذف دو نوع از افزونگی­ها از درخت تصمیم ­گیری دودویی دیاگرام تصمیم ­گیری دودویی ساخته می­ شود:
حذف آزمایش­های اضافی
ادغام زیر گراف­های همریخت
یک شبکه قابل اطمینان در نظر گرفته می­ شود اگر هر منبع حداقل یک مسیر فعال و زنده برای انتقال بسته­ها به سمت چاهک داشته باشد. همچنین یک شبکه غیر قابل اطمینان در نظر گرفته می‌شود اگر حداقل یک منبع ارتباطش با چاهک قطع شود یا به عبارت دیگر مسیری برای انتقال بسته­ها به سمت چاهک وجود نداشته باشد. قابلیت اطمینان به صورت احتمال اینکه یک شبکه قابل اطمینان باشد تعریف شد.
در راهکار پیشنهاد شده ابتدا تمام لینک­ها در یک لیست مرتب شده قرار داده می­ شود. در گرافی که در پایان بدست می ­آید لینک­ها نشان دهنده گره­ها در گراف هستند. در هر مرحله یک لینک از گراف بسط داده می­ شود و بررسی می­ شود که در صورت فعال بودن یا غیرفعال بودن آن آیا شبکه قابل اطمینان است یا غیر قابل اطمینان. در صورت قابل اطمینان بودن گره مورد نظر به گره Reliable وصل می­ شود و در صورت غیر قابل اطمینان بودن گره مورد نظر به گره Unreliable وصل می­ شود. در غیر این صورت اگر لیست لینک­ها خالی نباشد لینک بعدی بسط داده می­ شود.
بعد از ساخته شدن گراف مربوطه با توجه به قانون شانون و با پیمایش از ریشه قابلیت اطمینان شبکه محاسبه می­ شود. با نتایج بدست آمده از تحلیل و شبیه سازی دقت بالای راهکار پیشنهادی نشان داده شد.
فصل۶
پیشنهاد یک پروتکل چند مسیره تطبیقی برای اقناع قابلیت اطمینان
مقدمه