next node

جدول ‏۵‑۱ : مشخصات لینک شماره ۴ در شکل ۵-۱۲
در شکل ۵-۱۳ دو نوع از کمان‌ها برای اتصال بین گره­ها داریم. همان‏طور که در قبل ذکر شد در راهکار پیشنهاد شده این گره­ها بیانگر لینک­ها هستند. اگر لینک مورد نظر فعال در نظر گرفته شود یک کمان پر رنگ پیوسته از قسمت گره مربوطه به گره بعدی( یا در واقع گره مربوط به لینک ­بعدی) وصل می­ شود و اگر لینک مورد نظر غیر فعال در نظر گرفته شود یک کمان با خط چین قرمز رنگ به گره بعدی اتصال پیدا می­ کند. مثلاً در شکل ۵-۱۳ سمت راست­ترین گره، مربوط به لینک شماره ۶ در سطح سوم از گراف را در نظر بگیرید در صورتی که لینک شماره ۶ فعال در نظر گرفته شود یک کمان پر رنگ پیوسته به گره Reliable وصل می­ شود در غیر این صورت یک کمان خط چین به گره مربوط به لینک ۵ در سطح پایین­تر متصل می­گردد.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

تعاریف
فرض شده است منابع همراه با مسیرهای مورد نظر برای هر منبع به عنوان ورودی به الگوریتم داده می­ شود. برای راحتی کار اصطلاحات زیر در نظر گرفته می‌شود:
LinkList : لیستی که همه لینک­های مربوط به مسیرها بر اساس اولویت در آن قرار می­گیرند. اولویت طبق تعداد دفعاتی است که هر لینک روی مسیرهای متفاوت قرار می­گیرد تعیین می­ شود.
L : مشخص کننده سطح مورد نظر در گراف می­باشد، همچنین به عنوان یک شاخص^[۱۷۸] برای تعیین لینک مورد بررسی در لیستLinkList در نظر گرفته می­ شود مقدار پیش فرض آن ۱ می­باشد.
LinkList-v : لیستی از لینک­هائی که تا به حال در درخت پیمایش شده­­اند. در این لیست به هر لینک در صورتی که فعال در نظر گرفته شود برچسب ۱ و در غیر این صورت برچسب ۰ زده می­ شود. این لیست در طی اجرای الگوریتم تغییر می­ کند. در واقع این لیست کمان‌های پیمایش شده از ریشه تا سطح جاری در گراف را نشان می­دهد.
N_L : گره تشکیل شده در سطح L ام از گراف که مرتبط به لینک L ام از لیست LinkList است را نشان می­دهد.
:کمان خروجی از گره N_L برای زمانی که لینک مربوط به گره N_L فعال در نظر گرفته می­ شود.
: کمان خروجی از گره N_L برای زمانی که لینک مربوط به گره N_L غیرفعال در نظر گرفته می­ شود.
T_SN : در هر گره­ا­ی که بسط داده شده بعد از بازگشت از مراحل زیرین تعیین می­ کند که آیا لینک بسط داده شده بی اهمیت است یا خیر.
L_R : مشخص می­ کند سطح بعدی که کمان خروجی از شاخه سمت راست به آن متصل شده است چند سطح پایین‌تر از سطح جاری قرار دارد. مقدار پیش فرض آن ۱ می­باشد.
مراحل تشکیل گراف
در ادامه مراحل تشکیل گراف برای تحلیل و تخمین قابلیت اطمینان گام به گام تشریح شده است:
گام ۱. استخراج لینک­ها از مسیرها
برای هر منبع بر اساس مسیرهای در دسترس، لینک­های مورد نظر استخراج می­شوند. با استخراج هر لینک آن را در لیست LinkList وارد می­کنیم. در اینجا هر لینک به صورت یک ساختار داده تعریف می­ شود که پارامترهایی مانند احتمال موفقیت لینک در انتقال داده ­ها، تعداد دفعات تکرار شده در مسیرهای مختلف، شماره شناسایی گره قبلی و بعدی آن در شبکه در این ساختار درج می­ شود. جدول ۵-۱ مقدار این پارامترها را برای لینک ۴ در شبکه شکل ۵-۱۲ نشان می­دهد. متغیر Count بیانگر تعداد دفعاتی است که یک لینک در مسیرهای مختلف استفاده شده است. لینک­ها در LinkList بر اساس مقدار متغیر Count مرتب می­شوند. هرچه این مقدار بیشتر باشد اولویت لینک نیز بالاتر است و در هنگام بسط دادن لینک­ها زودتر مورد کاوش قرار می­گیرد. این امر کمک زیادی به کاهش محاسبات می­ کند. خروجی این گام لیستی از لینک­های مرتب شده بر اساس تعداد دفعات تکرار می­باشد. مثلاً در مثال مورد بررسی، LinkList به صورت زیر می­باشد:
LinkList = { 4, 3, 6, 5, 2, 1}
گام ۲. ایجاد گره­ها
لینک با اولویت L از لیست لینک­ها استخراج می­ شود و یک گره متناسب با این لینک در سطح مورد نظر ایجاد می­ شود (N_L). در صورتی که L بزرگ‌تر از ۱ باشد آخرین کمان در LinkList-v به این گره (N_L) وصل می­ شود. اگر محتویات لیست لینک­ها خالی باشد کمان انشعاب گرفته شده از گام قبل که همان آخرین کمان در لیست LinkList-v است را به گره Unreliable وصل می­کنیم، سپس به گامی که از آن فراخوانی شده است برمی­گردیم. در غیر این صورت به گام بعد می­رویم.
به طور مثال در شکل ۵-۱۳ ابتدا لینک با بالاترین اولویت یعنی لینک شماره ۴ از LinkList خارج می­ شود و گره متناسب با آن یعنی L₁ در اولین سطح درخت تشکیل می­ شود. در این شکل گره در سطح ۶ که مربوط به لینک­ ۱ است () را در نظر بگیرید. هنگامی که کمان خارج شده مربوط به غیرفعال بودن (کمان خط چین) گره بسط داده شده است؛ چونLinkList را خالی می­­بیند (دقت کنید که لینک شماره ۱ آخرین مقدار درLinkList است) کمان مورد نظر را به گره Unreliable وصل می­کنیم.
گام ۳. بسط شاخه سمت راست ) (pos(N_L)
برای گره ایجاد شده در سطح جاری (L) شاخه سمت راست آن را گسترش می­دهیم (). بدین صورت که یک کمان از قسمت ۱ گره مورد نظر خارج می­کنیم. همچنین کمان مورد نظر را با مشخص کردن فعال بودن آن در انتهای LinkList-v وارد می­کنیم. سپس به گام بعد می­رویم.
به طور مثال سمت راست‌ترین گره در سطح ۵ مربوط به لینک ۲ در شکل ۵-۱۳ را در نظر بگیرید که لینک مورد نظر فعال در نظر گرفته شده است. آنگاه محتویات LinkList-v برابر است با
LinkList-v={,}
که نشان­دهنده آن است که روی این شاخه لینک ۴،۲ و ۶ فعال و لینک ۳ غیر فعال است.
گام ۴. بررسی قابل اطمینان بودن
بر اساس لینک­های که درLinkList-v برچسب آن‏ها فعال است بررسی می­کنیم آیا شبکه قابل اطمینان است یا خیر. این بررسی با توجه به تعریف قابلیت اطمینان در بخش ۵-۳-۱ صورت می­گیرد. در صورت قابل اطمینان بودن کمان انشعاب گرفته شده از گام قبل که همان آخرین کمان در لیست LinkList-v است را به گره Reliable متصل می­کنیم. در غیر این صورت مقدار فیلد L را یک واحد افرایش می­دهیم و به گام ۲ می­رویم. توجه کنید در هر سطحی که تشخیص داده شود شبکه قابل اطمینان است لینک­های بعدی در سطوح پایین‌تر مورد بررسی قرار نمی­گیرند و کمان مستقیماً به گره Reliable وصل می­ شود­، چون نیازهای لازم بر طبق تعریف قابلیت اطمینان بر آورده شده است. با بازگشت از گام ۲ آخرین کمان در لیست LinkList-v را حذف می­کنیم و به گام بعد می­رویم. گراف شکل ۵-۱۳ را در نظر بگیرید، به طور مثال فرض می­کنیم محتوای لیست LinkList-v برابر با:
LinkList-v={,}
باشد. این لیست نشان می­دهد که لینک­های ۴،۶ و ۲ فعال هستند و لینک ۳ غیرفعال است. با وجود لینک­های فعال، برای هر یک از منابع S₁ و S₂ یک مسیر به سمت چاهک برقرار می­باشد؛ لذا با توجه به تعریف قابلیت اطمینان، شبکه قابل اطمینان است و نیازی به بسط لینک­های بعدی در سطوح پایین‌تر نمی ­باشد. همان‏طور که در شکل پیداست کمان خروجی از سمت راست‌ترین گره در سطح ۵ مربوط به لینک ۲ (آخرین عضو در لیست LinkList-v )به گرهReliable وصل می­ شود و لیستLinkList به صورت زیر بروز رسانی می­ شود:
LinkList-v={ }
حال فرض می­کنیم محتوای لیست LinkList-v برابر با :
LinkList-v={,}
باشد. این لیست نشان می­دهد که لینک­های ۴ و ۵ فعال و لینک­های ۳ و ۶ غیرفعال هستند. با وجود لینک­های فعال برای منبع S₁ یک مسیر وجود دارد ولی برای منبع S₂ هیچ مسیری پیدا نمی­ شود؛ لذا نمی­ توان گفت شبکه قابل اطمینان است و الگوریتم به مرحله ب می­رود تا بقیه حالات بررسی شود.
گام ۵. حذف کمان‌های بی اهمیت
بعد از بازگشت از فراخوانی­های انجام شده در گام ۴ اگر مقدار فیلد T_SN برابر ۱ باشد نشان دهنده این است که کمان بعدی یک حالت بی اهمیت است و در واقع گره­­ای که این کمان به آن وصل شده است اضافی است؛ لذا کمان ایجاد شده در مرحله ۳ به گره­­ای که کمان خروجی از گره اضافی به آن متصل است وصل می­ شود و بدین صورت گره­های بی­اهمیت حذف می­شوند.
شکل ۵-۱۳ را در نظر بگیرید به طور مثال در سمت چپ­ترین گره در سطح ۳ مربوط به لینک ۶ مشاهده می­ شود که با وجود اینکه لینک­های ۵ و ۲ لینک­های بعدی برای این گره هستند، ولی کمان خروجی از شاخه سمت راست آن به گره موجود در آخرین سطح متصل شده است. در نتیجه لینک­های ۲ و ۵ برای این شاخه بی اهمیت هستند.
گام ۶. بسط شاخه سمت چپ (neg(N_L))
برای گره ایجاد شده در سطح جاری (L) شاخه سمت چپ آن را گسترش می­دهیم (). یک کمان از قسمت ۰ گره مورد نظر استخراج می­کنیم. لینک مورد نظر را با مشخص کردن غیر فعال بودن آن در انتهای LinkList-v وارد می­کنیم. سپس به گام بعد می­رویم.
شکل ۵-۱۳ را در نظر بگیرید به طور مثال سمت راست­ترین گره در سطح ۳ مربوط به لینک ۶ در شکل ۵-۱۳ را در نظر بگیرید که لینک بسط داده شده غیر فعال در نظر گرفته شده است. آنگاه محتویات LinkList-v برابر است با :
LinkList-v={}
که نشان­دهنده آن است که لینک ۴ و۳ فعال و لینک ۶ غیر فعال است.
گام ۷. بررسی غیر قابل اطمینان بودن
برای لینک­های موجود در LinkList-v بررسی می­کنیم که آیا شبکه غیر قابل اطمینان است یا خیر. اگر غیر قابل اطمینان باشد کمان استخراج انشعاب گرفته شده از گام ۵ که همان آخرین کمان در لیست LinkList-v است را به گره Unreliable متصل می­کنیم. در غیر این صورت مقدار فیلد Lرا به صورت L=L+L_R بروز رسانی می­کنیم و به گام ۲ می­رویم. مقدار L_R نشان می­دهد که کمان خروجی از شاخه سمت راست گره تشکیل شده در این سطح به L_R سطح پایین‌تر وصل شده است. توجه کنید در هر سطحی که تشخیص داده شود شبکه غیر قابل اطمینان است لینک­های بعدی در سطوح پایین‌تر مورد بررسی قرار نمی­گیرند و کمان مستقیم به گره Unreliable وصل می­ شود، به این دلیل که بسط دادن بقیه گره­ها بی­فایده است و تأثیری در وضع موجود ندارد. با بازگشت از گام ۲ آخرین کمان در لیست LinkList-v را حذف می­کنیم و به گام بعد می­رویم.
گراف شکل ۵-۱۳ را در نظر بگیرید، به طور مثال فرض می­کنیم محتوای لیست LinkList-v برابر با :
LinkList-v={,}
باشد. این لیست نشان می­دهد که لینک­های ۲ و ۳ فعال و لینک­های ۵ و ۶ غیرفعال هستند. با وجود لینک­های غیر فعال، مشخص می­ شود که برای منبع S₂ دیگر هیچ مسیری نمی­ توان به سمت چاهک برقرار نمود یا به عبارت دیگر با شرایط موجود ارتباط با چاهک برای منبع S₂ غیر ممکن است؛ لذا با توجه به تعریف قابلیت اطمینان، شبکه در این شرایط غیر قابل اطمینان است و بسط دادن لینک­های بعدی در سطوح پایین‌تر بی­فایده است. همان‏طور که در شکل ۵-۱۳ پیداست کمان خروجی از سمت چپ­ترین گره در سطح ۴ مربوط به لینک ۵ (آخرین عضو در لیست LinkList-v (به گرهUnreliable وصل می­ شود و لیستLinkList به صورت زیر بروز رسانی می­ شود:
LinkList-v={ }
حال فرض می­کنیم محتوای لیست LinkList-v برابر با :
LinkList-v={,}