بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه الگوریتم -kپوشش با استفاده از نظریه بازیها در شبکه های حسگر بیسیم
چکیده:امروزه شبکه های حسگر در شاخه های مختلف علم، کاربردهای زیادی پیدا کـرده اسـت. شبکه های بیسم در مقیاس بزرگ، با نظارت وکنترل بر روی محیط اطراف بـا محـدوده ی زمـانی و مکانی بالا انتظار میرود که نقش مهمی را در برنامه های کاربردی مختلف بازی کننـد. یـک شـبکه حسگر از تعداد زیادی حسگر کوچک تشکیل شده است. این حسگرها با کمک یکدیگر اطلاعـاتی را در مورد میدان حسی قرار گرفته در آن به کاربران می دهند. یکی از مسائل مهم در این شـبکه ها، مسئله پوشش است. یکی از شاخه های مسئله پوشش، پوشش kتایی است. هـدف ایـن نـوع پوشش، نظارت حداقل k حسگر گوناگون بر تمام نقاط میدان حسی است. با توجه به محدود بـودن انرژی حسگرها، مسئله مهم دیگر که در شبکه های حسگر مورد بررسی قـرار مـی گیـرد ذخیـره انرژی می باشد که باعث افزایش طول عمر شبکه نیز خواهد شد.در این مقاله، مسئله بهبود مصرف انرژی در شبکه های حسگر با پوشش kتایی مورد بررسی و ارزیابی قرار گرفته و الگـوریتم بهینـه ای برای افزایش کارایی انرژی حسگرها پیشنهاد می شود.طبق نتایج شـبیه سـازی،این الگـوریتم طول عمر شبکه را بیشتر افزایش می دهد.
واژه های کلیدی: شبکه حسگر بیسیم،پوشش kتایی،مدل نظریه بازیها
-1مقدمه
یک شبکه حسگر بیسیم عبارتست از تعداد زیادی حسگرهای کوچک باتوان پایین در ارسال و دریافت که مـیتوانـد ابـزاری مـؤثر برای گردآوری داده در محیطهای گوناگون باشد. داده جمعآوری شده توسط هرحسگر از طریق شبکه با مرکزپردازش ارتباط دارند که این دادهها برای تعیین مشخصات محیط یا شناسایی یک رویداد استفاده میشوند. فرآیند انتقال پیام باید براساس انرژی محدود منابع حسگرها طراحی شود. بررسی مسائل مطرح در شبکه های حسگر با توجه به شرایط منحصر به فرد آنها ضـروری بـه نظرمـی رسد. پیشرفت نمایی از ادغام تکنولوژی، گام هایی که توسط قانون مور صورت گرفته جهت سنجش، محاسبه و ارتباطـات بیسـیم و همچنین ترکیب آن ها در بسته های کوچک می باشد، دستگاه های کم قدرت مـی تواننـد بـه صـورت یکپارچـه در محـیط هـای پیچیده فیزیکی جاسازی شوند.گره های حسگرها سنجش، پردازش سیگنال و قابلیت های ارتباطاتی را محدود کره اند و معمولا بـا باتری کار می کنند. بررسی هر یک از دستگاه ها به صورت جداگانه ممکن است کاربردهای کـوچکی داشـته باشـد. بـا ایـن وجـود تحقق شبکه های حسگر بیسیم بسته به همکاری و هماهنگی تعداد زیادی از چنین دستگاه هایی برای به انجـام رسـاندن وظـایفی است که به سختی با سیستم های سنجش متداول و متمرکز قابل انجام و اجرا است.شبکه های حسـگر بیسـیم دارای برنامـه هـای کاربردی مفید زیادی هستند و انتظار می رود که نقش مهمی را در برنامه های مختلف بازی کنند. از جمله مسائل مطـرح در ایـن گونه شبکه ها،نحوه چیدمان حسگرها در راستای پوشش بیشتر و کنترل انرژی مصرفی در آنها برای استفاده بهینه و طولانی مـدت حسگرها می باشد. شبکه های حسگر بی سیم (WSN)، نسل جدیدی از سیستم های تعبیـه شـده زمـان واقعـی را بـا محاسـبات محدود، منابع انرژی و حافظه نشان می دهد که در موارد کاربردی گسترده مختلف، زمانی که زیرساخت های ایجـاد شـبکه سـنتی عملا غیرمحتمل می باشد، مورد استفاده قرار می گیرند. در این مقاله هدف اصلی کنترل سطح پوشـش پیرامـون هـر حسـگر مـی باشد و ثابت شده است که کل منطقه تحت نظر، پوشش kتایی دارد اگر و تنها اگر هر حسگر در این منطقه پوشش kتـایی داشـته باشد. در ادامه در بخش 2 به معرفی کارهای انجام شده می پردازیم.در بخش 3 نظریه بازیها را توصیف میکنیم و در بخـش 4 یـک الگوریتم توزیعی برای شبکه حسگر ارائه می دهیم. در بخش 5 نتایج شبیه سازی و در بخش 6 نتیجه گیری از تحقیـق آورده شـده است.
-2کارهای انجام شده
تحقیقات زیادی در شبکه های حسگر برای افزایش پوشش حسگرها و طول عمر آنها صورت گرفته است و نظریه هـای مختلفـی در این خصوص صادر شده است. اسلی چپسویک تعریفی از مسئله پوشش k را ارائه داده و اشاره میکند که مشکل بخش مجموعـه k یک مشکل NP است. او در تحقیق خود از یک الگوریتم متمرکزشده ذهنی استفاده میکنند تا مجموعه منطقـه پوشـش را تقسـیم کنند. هونگ های ژانگ یک مفهوم طول عمر را پیشنهاد میدهد. او مدت زمانی که حداقل یک قسمت از ناحیه نظارت،پوشش داده میشود را ارائه میدهد و از الگوریتم متمرکز برای پیدا کردن حداقل یک مجموعه گره منطقه پوشش در میان گـره هـای باقیمانـده استفاده میکنند که بیشینه یا حداکثر حد بالایی یک طول عمر را ایفا میکنند. همه الگوریتم های ذکر شده در بالا تعـداد مجموعـه گره های منطقه پوشش را به حداکثر میرسانند و تا آنجا که ممکن است بر اساس قابلیت اطمینان از ناحیه کل منطقه پوشش عمـر شبکه را طولانی میکنند.با این وجود آبرام دامنه ناحیـه منطقـه پوشـش را بـه حـداکثر رسـاند.آبـرام سـه نـوع الگـوریتم را فـراهم کرد:الگوریتم تصادفی،الگوریتم حریص توزیعی،الگوریتم حریص یکپارچه.نظریه بازی در تـلاش اسـت توسـط ریاضـیات رفتـار را در شرایط راهبردی یا بازی، که در آنها موفقیت فرد در انتخاب کردن وابسته به انتخاب دیگران میباشد، بدست آورد و مناسب ویژگـیگره در شبکه های حسگر است که فقط برای آگاهی از اطلاعات خود و مجاورین بکـار میـرود.در زمـان اخیر،تحلیـل رفتـار گـره در شبکه حسگر طبق نظریه بازیها و اجرای مدل کارکرد مرتبط با مطالعه به تدریج باعث جلب توجه افراد میشوند.در چهارچوب حفـظ , نگهداری از انرژی،یوآن از نظریه بازیها استفاده کرد و بهینه سازی لایه ی میان توزیعی را بـرای کنتـرل نیـرو در لایـه فیزیکـی و تخصیص سرعت در لایه کاربردی پیشنهاد داد.بازی کنترل نیرو در لایه فیزیکی تاثیر انتقال را در حسـگرهای مجـاور مـدنظر قـرار میدهد.او یک مکانیزم مالیاتی را در این بازی به عنوان محرک در گره ها برای اجتناب از مداخله ارائه می دهند.کنان در مورد مسیرارسال بسته کوچک یک طرح مسیریاب جستجوی مطمئن پیشنهاد میدهد، او از یک رویکرد نظریه بازیها استفاده می نماینـد. در این رویکرد،حسگرها به عنوان عوامل منطقی در همکاری با یکدیگر برای پیدا کردن بهترین معماری های شبکه مدلسازی میشـوند که بازدهیهایشان را در یک بازی حسگر به حداکثر می رسـانند.در ابتـدا ژی آی و همکـارانش از نظریـه بازیهـا بـرای حـل مسـئله مجموعه پوشش k استفاده کردند و حداکثر عمر شبکه را اتخاذ کردند.آنها الگوریتم تـوزیعی پیشـنهاد دادنـد کـه عملکـرد منطقـه پوشش در مجموعه پوشش k را به حداکثر میرساند.با این وجود این الگوریتم محدودیت های بسیاری دارد.اولا عمر شبکه به تعـداد مجموعه های گره منطقه پوشش بستگی دارد. دوما الگوریتم، افزایش عمر شبکه را هدف قرار میدهد.تا جاییکـه امکـان دارد ناحیـه منطقه پوشش را توسعه میدهد و نمی تواند سرتاسر ناحیه منطقه پوشش را تشخیص دهد.در ایـن مقالـه،ما اولا زیرفیلـد روی هـم افتادگی لایه کمینه گره را برای تشخیص مقـدار منطقـه پوشـش حـداقل ناحیه،ماننـد حـد بـالایی تعـداد مجموعـه گـره منطقـه پوشش،بکار میگیریم. ثانیا،حداکثر تعداد الگوریتم محاسبه شده مجموعه منطقـه پوشـش بـرای محاسـبه حـداکثر تعـداد مجموعـه منطقه پوشش پیشنهاد میشود.طبق تحلیل ذکر شده در بالا،این مقاله از مشخصه بازیکنان در نظریه بازیها اسـتفاده میکنـد و یـک الگوریتم توزیعی را برای تقسیم مجموعه پوشش کا مطرح میکند.
-3نظریه بازیها و مدل تقسیم مجموعه گره پوشش
1-3 مفهوم نظریه بازیها
بر اساس توجه عقلانی به بازیکنان، نظریه بازیها بهترین تصمیم را در یک وضعیت فعل و انفعالی میگیرد، استراتژی اولویت بازیکنان ایجاد حداکثر رضایت مندی می باشد. در بازی با بازیکنان متعدد،تصمیم در مورد رفتار یک بازیکن بستگی به رفتار دیگـر بازیکنـان دارد.اگر تعداد بازیکنان و استراتژی هایی که بازیکن میتواند انتخاب کند محدود باشد،یک بازی محدود نامیده میشـود.اگر بازیکنـان بصورت همزمان اقداماتی را انجام دهند یا بصورتی که نظم خاصی وجود داشته باشد،بازیکن دومی انتخاب بازیکن قبلی را ندانـد،این نوع از بازیها بازی ساکن نامیده میشـود. بـازی سـاکن شـامل مجموعـه بازیکن،مجموعـه اسـتراتژی بـازیکن و تـابع کـاربردی مـی باشد.مجموعه بازیکن شامل همه بازیکنان است،مجموعه استراتژی شـامل اسـتراتژی هـایی اسـت کـه بازیکنـان انتخـاب میکننـد. استراتژی برگزیده شده، قاعده رفتاری بازیکن می باشد و برای هدایت رفتار بازیکن استفاده می شود.هر انتخـاب اسـتراتژی بـازیکن در بازی، کارکردی خاص در بازیکن بوجود می آورد و این کارکرد از طریق تابع کارکردی توضـیح داده مـی شـود.در وضـعیتی کـه استراتژی های دیگری از بازیکن داده میشود،آن استراتژی از بازیکن که بزرگترین مقدار تابع کارکرد آن را دارد،اسـتراتژی ایـده آل بازیکن نامیده میشود. موازنه نش،یک گروهی از استراتژیهاست که باعث میشود استراتژی هر بازیکن بهتـرین بازتـاب را روی دیگـر استراتژی های بازیکنان بگذارد،یعنی اگر دیگر بازیکنان اسـتراتژی هایشـان را تغییـر ندهنـد ایـن بازیکنـان در ایـن زمـان بهتـرین استراتژی را خواهد داشت.اگر استراتژی به تنهایی تغییر کند مقدار تابع کارکردی کاهش پیدا خواهد کرد.بنابراین،موازنه نـش بـرای هر بازیکن نتیجه یک بازی ثابت است.تا زمانیکه موازنه نش به قوت خود باقی است، هیچ یک از بازیکنان به تنهایی انگیزه ای بـرای تغییر استراتژی خود ندارند.یک بازی ممکن است دارای چندین موازنه نش باشد،حتی ممکن است هیچ موازنه نشی نداشته باشد.
2-3 توجه عقلایی به گره
در شبکه حسگر بیسیم میتوان گره را عقلانی در نظر گرفت.مسیر گره برای انجام عمل انتخـاب اسـتراتژی توجـه عقلانـی بـه گـره میباشد.در تکنیک منطقه پوشش ناحیه، پارامتر عملکرد مناسب همیشه درجه منطقی پوشش ناحیه و عمـر شـبکه در نظـر گرفتـه میشود. بنابراین در تقسیم مجموعه گره منطقه پوشش،توجه عقلانی به گره بدین صورت مد نظر قـرار میگیـرد:((1دامنـه مجموعـه گره منطقه پوشش میتواند برای رویارویی با تقاضای کاربر سرتاسر ناحیه را پوشش دهد.((2تعداد مجموعـه گـره مسـاوی بـا زمـان هایی است که عمر شبکه دارد،بنابراین تعداد مجموعه گره پوشش منطقه باید تا آنجایی که ممکن اسـت افـزایش یابـد کـه در ایـن صورت طولانی شدن عمر شبکه را تسهیل می سازد.دو منطق ذکرشده در بالا بر یکدیگر تحمیل میشوند.در توجه منطقی اولیه،گره امیدوار است که مجموعه گره منطقه پوشش را که انتخاب میشود بتواند در سرتاسر ناحیه پوشش دهـد.بنابراین درجـه تعـداد گـره منجر به افزایش درون مجموعه گره میشود که خود باعث کاهش تعداد مجموعه گره پوشش منطقه ای میشـود کـه انتخـاب شـده است و عمر شبکه را کوتاه میکند.در توجه منطقی ثانویه،برای اینکه گره عمر شبکه را طولانی کند تا جایی که ممکـن اسـت تعـداد مجموعه گره منطقه پوشش را افزایش میدهد و این خود منجر به کاهش تعداد گره در هر مجموعه گره میشود که در نهایت سوراخ هایی روی منطقـه پوشـش ایجـاد و ناحیـه بطـور کامـل پوشـش داده نمیشـود.بنابراین،با وجودیکـه تقسـیم مجموعـه گـره انجـام میشود،توجه های مختلفی منجر به مدل های مختلف بازی میشود.اگر طولانی شدن عمر شبکه را بر هر چیزی تـرجیح دهـیم،پس در وضعیت کاهش درجه منطقی پوشش ناحیه، باید تا آنجاییکه ممکن است بیشتر مجموعه هـای گـره منطقـه پوشـش را تقسـیم کنیم. الگوریتم بازی که در این مقاله ارائه میشود تفهیم این نوع توجه عقلانی میباشد.اگر ترجیح میدهیم تا از درجه منطقه پوشش ناحیه مطمئن شویم،مثلا اطمینان از منطقه پوشش سرتاسر ناحیه،بنابراین الگوریتم بازی بـه مجموعـه هـای گـره منطقـه پوشـش تقسیم خواهد شد و بیشینه عمر شبکه بر اساس رویارویی تقاضاهای منطقـه پوشـش خواهـد بود.الگـوریتم منطقـه پوشـش ناحیـه توزیعی در این تحقیق بر اساس بازی،کاربرد این نوع توجه عقلانی است.
3-3 مدل نظریه بازیها بر اساس انتخاب مجموعه گره منطقه پوشش
1-3-3 توصیف مدل
حداکثر تعداد مجموعه پوشش :kاگر یک ناحیه از چندین لایه تشکیل شده باشد و توسط گره های حسـگری کـه روی آن مسـتقر شده،پوشش داده شود،گره های حسگر میتوانند به مجموعه های گره مختلف منطقه پوشش تقسیم شوند،که در انجـا حـداقل یـک تقسیم از مجموعه های گره منطقه پوشش وجود خواهد داشت و باعث میشود هر مجموعه گره منطقه پوشش بتواند سرتاسر ناحیه را پوشش دهند و بدین صورت تعداد مجموعه های گره منطقه پوشش که تقسیم شده اند باید کوچکتر یا مساوی با تعداد لایه های منطقه پوشش از کمینه زیرفیلدهای روی هم افتادگی ناحیه باشند.
لم :1 اگر یک ناحیه از چندین لایه تشکیل شده باشد و توسط گره های حسگری که روی آن مستقر شده پوشش داده شود و تعداد لایه منطقه پوشش کمینه زیرفیلدهای روی هم افتادگی ناحیه به عنوان بیشینه تعداد مجموعه منطقه پوشش گـره در نظـر گرفتـه شود،تقسیم گره ها،همه گره های MLOF را در هر مجموعه گره تحت پوشش قرار میدهد که میتواند از پوشش مجموعه هر گـره در سرتاسر ناحیه مطمئن شود. تقسیم مجموعه k یک مسئله NP است و برای صـحیح بـودن الگـوریتم جهـت جسـتجوی نسـبی بهترین مقدار باید هر کاری را که میتوان انجام داد.در ابتدا،این تحقیق بیشترین تعداد مجموعه گره منطقه پوشـش را در وضـعیتی که از سرتاسر ناحیه منطقه پوشش اطمینان حاصل میشود،بکار میگیرد تا حداکثر عمر شبکه را مشخص نماید.دوما الگوریتم تقسیم مجموعه گره بر اساس مدل نظریه بازیها که در این تحقیق برای اجرای تقسیم مجموعه های گـره ارائـه شـده، بهتـرین راه حـل را جست و جو میکند.مدل بازی بر اساس انتخاب مجموعه گره منطقه پوشش است که در زیر آمده است،مدل بـازی G=<R,S,U> یک مدل بازی ساکن،ایستا و محدود است:
مجموعه بازیکنان را نشان میدهد. تعداد آن n تاست که یک مقدار محدود است.
مجموعه ترکیبی از همه استراتژی های انتخاب شده توسط گره ها را نمایش میدهـد.در میـان آنهـا نشاندهنده مجموعه استراتژی است که از طریق گره حسگر i انتخاب میشود یـک مجموعـه ای اسـت کـه دربردارنده مجموعه گره منطقه پوشش id می باشد و از طریق گره i انتخاب میشود.k به تعداد مجموعه گره منطقه پوشـش اشـاره دارد که یک مقدار محدود میباشد.مثلا نشان میدهد که گره i مجموعه گره منطقه پوشـش J ام بـه عنـوان اسـتراتژی بـازی انتخاب میکند. ترکیب استراتژی همه گره هـا را در زمـان خاصـی نشـان میدهـد. در R ترکیـب استراتژی همه گره ها بجز گره i را در زمان خاصی نشان میدهد ترکیب استراتژی همه مجاورهـای گـره i را در یـک زمـان خاصی نشان میدهد.
تابع کارکردی گره i را نشان میدهد، برای نشان دادن مقدار بکارگیری گره i استفاده میشود که میتوان آنرا بصورت مختصر با بیان کرد.
برترین ویژگی نظریه بازیها در کنترل منطقه پوشش ناحیه،ویژگی است که طی آن از طریق انتخاب استراتژی خود گـره بـه هـدف تاثیرگذاری روی عملکرد سرتاسر شبکه دست می یابد.طبق قضیه1،تا زمانیکه هر گره بتواند این اطمینان را حاصل کند که گره ها، MLOF تشکیل شده از طریق گره را تحت پوشش قرار می دهند و همه مجاورین آن به هر مجموعه گره منطقـه پوشـش تقسـیم میشوند،همه مجموعه گره منطقه پوشش میتوانند سرتاسر ناحیه را پوشش دهند.مثلا در ناحیه A از شکل1، اگر همه پوشش گـره های MLOF به هر مجموعه گره منطقه پوشش تقسیم میشود،این مجموعه میتواند سرتاسر ناحیه را پوشـش دهد،شـما میتوانیـد این وضعیت را در شکل 1 قسمت a و b مشاهده کنید.
4-3 استفاده از تابع توصیف شده
1-4-3 آرایه پوششی
تعریف .1 آرایه منطقه پوششی ، نشان میدهد که آیا گره های MLOF تشکیل شده بوسیله گره i و گره j به هر مجموعه گـره منطقه پوشش تقسیم میشود.در نظر بگیریـد کـه تعـداد مجموعـه هـای گـره منطقـه پوشـش تقسـیم شـده،k باشـد و اسـتراتژی باشد. آرایه منطقی پوشش گره i و گره مجاور j,m:1..k را نشان میدهـد. k بـه تعـداد مجموعـه گـره منطقه پوشش در مجموعه id اشاره میکند. همه پوشش گره های MLOF که از طریق گره i و گره مجاور j تشکیل شده اند یـک مجموعه گره منطقه پوش Z,z∈Z را میسازند. اگر استراتژی Z مجموعه گره منطقه پوشش m را انتخاب کند،به مقدار 1 داده میشود، اگر گره های درون Z هیچ گره ای را از m انتخاب نکنند,. برای مثال، همانطور که در شکل 1 نشان داده شده است، دو گره MLOF پوششی که id آن 11 است بوسیله گره 1 و گره 6 تشکیل داده شده،پس تعداد مجموعه گـره تقسـیم شده 2 میباشد.اگر استراتژی باشد به این معنی است که که گره 1 مجموعه گره اولیه و گره ششـم مجموعـه گـره ثانویه را انتخاب میکند.پس ،طبق a و b در شکل 2، اگر استراتژی باشد بدین معنیسـت که هیچیک از گره 1 و گره 6 مجموعه 2 را انتخاب نمی کنند. بنابراین خواهد بود.شما میتوانیـد آنـرا در شکل 2 قسمت c و d مشاهده کنید.
2-4-3 استفاده از تابع
اگر باشد، نشان می دهد که در مجموعه گره mام ،هیچ گره ای با مجموعه گره منطقه پوشش Z وجـود نـدارد یعنـی مجموعــه گــره mام نمــی توانــد ناحیــه روی هــم افتــادگی تشــکیل شــده از طریــق گــره i و J را بپوشــاند. بنــابراین اگــر باشد،در استراتژی جاری همه MLOF پوششی گره ها که توسط گـره i و J تشـکیل شده به هر مجموعه گره منطقه پوشش تقسیم میشوند.پس ما میتوانیم بگوییم که این MLOF برای ایجاد شرایط تقسیم در نظـر گرفته میشود و بوسیله نشان داده میشود و ثابت میکند که شرایط مورد نظر را فراهم نمیکند.فرمول بصورت زیر نوشته میشود:
در استراتژی تابع کارکردی گره بصورت زیر نوشته میشود:
فرمول بالا نشان می دهد که در استراتژی همه MLOF تشکیل شده بوسیله گره i و همه گره های مجـاور آن را بررسی میکند،تعداد MLOF که از شرایط راضی نیستند را جمع میکند. N(i) مجموعه گره های مجاور i می باشـد.مقدار تـابع کارکردی کوچکتر، تعداد بیشتری از MLOF که از شرایط راضی هستند،است و نتیجه بهتری کـه حاصـل میشـود تنهـا از طریـق استراتژی جاری می باشد. چون اثبات گره i تنها به گره های مجاور آن مربوط میشود،تابع کارکرد را میتوان بصورت مختصر نوشت که در زیر نشان داده شده است:
اگر همه MLOF گره i در شرایط راضی باشند،مقدار تابع کارکرد آن بزرگترین خواهد بـود یعنـی ،در ایـن زمـان ∗ ایده آل ترین استراتژی گره i خواهد بود. مثلا گره 1 را در شکل 1 در نظر بگیریـد،مجاورین متنـاظز آن، گـره هـای 2و3و5و6 زیرفیلدهای 6و1و3و10و11 هستند.توجه کنید که شاید MLOF بی نظیر نباشد مثلا MLOF تشکیل شده بوسیله گره 1 و گـره 3 ،MLOF پوششی مجموعه هـای گـره متنـاظر 1}و{2 و 1}و2و{3و1}و3و{5و1}و{5و1}و{6 هسـتند. در اسـتراتژی جـاری ( , (i))، محاسبه مقدار تابع کارکردی مدل 1 به این خاطر است که بفهمید آیا گره های MLOF پوششی مجموعـه گـره بـه مجموعه گره هر منطقه تقسیم میشوند،مقدار تابع کارکرد گره 1 در جدول 1 نشان داده شده است.
مثلا،دو مجموعه گره منطقه پوشش تقسیم شده که id آن 1 یا 2 و میباشد.پس برای هر دو گره 1 و گره 2در مجموعه،1 گره منطقه پوشش هستند و به مجموعه گره منطقه پوشـش مختلفـی تقسـیم نمیشـوند. چون دو MLOF تشکیل شده بوسیله گره 1 و گـره 3 وجـود دارد، بـه طـور جداگانـه دو زیرفیلـدهای گـره 1}و3و{5 و 1}و2و{3 متناظر میشوند.تنها وقتیکه دو مجموعه میتوانند به مجموعه های گره منطقه پوشش مختلفی تقسیم شوند کـه باشد،حالا مجموعه 1}و2و{3 نمیتواند از شرایط راضی باشد بنابراین اسـت. اسـت چونکـه مجموعـه گـره1}و{5 توسط گره 1 و گره 5 میتواند به مجموعه های گره منطقه پوشش مختلفی تقسیم شـود. . بنـابراین طبـق فرمـول 3،مقـدار کاربردپذیری گره 3،-1 است.
