بخشی از مقاله
برخی از منابع:
[1] Antoine Gallais, Jean Carle, David Simplot-Ryl, et al. “Localized Sensor Area Coverage with Low(a) area coverage by SDBGA Communication Overhead”. IEEE Transaction MOBILE COMPUTING , 2008, 7(5):661-672.
[2] Chong Liu, Kui Wu, Yang Xiao. “Random Coverage with Guaranteed Connectivity:Joint Scheduling for Wireless their valuable comments. This work is supported by National High Technology Research and Development Sensor Networks”. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2006,17(6):562-
575.
[3] Lan Wang , Yang Xiao1. “A survey of energy- efficient scheduling mechanisms in sensor networks”. Mobile
Networks and Applications , 2006 , 11 (5) : 723- 740.
[4] Fan Ye, Zhong, G., Cheng, J, et al. “PEAS: a robust energy conserving protocol for long-lived sensor networks”. Proceedings of the 23rd International Conference on Distributed Computing Systems. Rhode Island, USA: IEEE
Computer Society , 2003:.28-37.
[5] E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang,and A. Chandrakasan. “Physical layer driven protocol and algorithm design for energy -efficient wireless sensor networks ”. In Proc.
چکیده:امروزه شبکه های حسگر در شاخه های مختلف علم، کاربردهای زیادی پیدا کـرده اسـت. شبکه های بیسم در مقیاس بزرگ، با نظارت وکنترل بر روی محیط اطراف بـا محـدوده ی زمـانی و مکانی بالا انتظار میرود که نقش مهمی را در برنامه های کاربردی مختلف بازی کننـد. یـک شـبکه حسگر از تعداد زیادی حسگر کوچک تشکیل شده است. این حسگرها با کمک یکدیگر اطلاعـاتی را در مورد میدان حسی قرار گرفته در آن به کاربران می دهند. یکی از مسائل مهم در این شـبکه ها، مسئله پوشش است. یکی از شاخه های مسئله پوشش، پوشش 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> یک مدل بازی ساکن،ایستا و محدود است:
