بررسی راهکارهای مناسب جهت بهینه سازی مصرف انرژی در شبکه های حسگر بی سیم …

در بخش بعدی، الگوریتم خود تثبیتی کاملا توزیع شده ای را برای بهینه سازی طول عمر در شبکه حسگر بی سیم ارائه می کنیم. ابتدا روی فرمولاسیون حالت قانونی تمرکز می کنیم و سپس الگوریتم را ارائه می کنیم که شامل تنها دو قاعده می باشد و اثبات های صحت را ارائه می کنیم.
۴-۶ فرمولاسیون مسئله
فرض کنید G =(V;E) گراف مدل سازی شبکه حسگر باشد. فرض کنید Z=(z1,z2,…,zk} مجموعه منطقه های در حالت نظارتی است که قرار است پوشش داده شوند و S={1,2,…,n} مجموعه گره های حسگر است. هر منطقه در Z باید توسط حداقل یک گره حسگر موجود در S پوشش داده شود. را مجموعه حسگرهای همسایه منطقه می نامیم. هر حسگر همسایه قادر به نظارت منطقه zu است:
(۴-۷)
که در آن d(q,i) نشان دهنده فاصله بین نقطه و حسگر j است.
با توجه به مسئله ۱، حالت قانونی شبکه بصورت زیر بیان می شود:
(۴-۸)
بعبارت دیگر، هر منطقه در حالت نظارت توسط حداکثر یک گره حسگر پوشش داده می شود.
۴-۷ الگوریتم خود تثبیتی
در ادامه الگوریتم را ارائه می کنیم. زمانبندی توزیع شده/ آسنکرون را تحت یکپارچگی مرکب خواندن/نوشتن فرض می کنیم. همچنین شناسه گره حسگر را بصورت منحصربفرد در نظر می گیریم.
علامت گذاری های زیر نیز برای مسندهای گره i ارائه می شوند:
(۴-۹)
الگوریتم خود تثبیتی از دو قاعده زیر استفاده می کند:
(۴-۱۰)
۴-۸ اثبات های خود تثبیتی
قضیه ۲: هر منطقه در حالت نظارت zu در نهایت توسط حداکثر یک گره حسگر پوشش داده می شود.
اثبات: توسط قاعده r1 تضمین می شود، یعنی اگر دو یا چند گره فعال در منطقه یکسان وجود داشته باشد، تنها یکی با کوچکترین Id فعال باقی خواهد ماند.
قضیه ۳: اگر گرهی r2 را اجرا کرده باشد، در اینصورت آن گره و هر یک از همسایه هایش حداکثر یک قاعده بیشتر را تا زمان بیداری بعدی اجرا خواهند کرد و این قاعده r1 خواهد بود.
اثبات: فرض کنید i گرهی است که r2 را اجرا کرده است. زمانیکه گره i وارد حالت فعال می شود، تمام همسایه هایش یا در حالت خواب می باشند یا در حالت بیداری. بنابراین دو سناریو ممکن داریم:
(۱) همسایه ها در حالت خواب: هیچ برخوردی در این مورد وجود ندارد.
(۲) همسایه ها با حالت بیداری: این همسایه ها دارای Id بزرگتر از i می باشند.
قضیه ۴: زمانیکه گره در حالت خواب نیست، می تواند حداکثر ۲ حرکت داشته باشد.
اثبات: براحتی مشاهده می شود که هر قاعده می تواند حداکثر یک بار توسط گره اجرا شود. بنابراین، تنها مورد زمانیکه گرهی دو حرکت انجام می دهد زمانی است که r2 سپس r1 را با حالت فعال اجرا می کند.
فرضیه ۱٫ الگوریتم پیشنهادی با توجه به در ۲n حرکت خود تثبیت است.
اثبات: که طبق قضیه ۲ تا ۴ است.
استنباط ۱٫ برای شبکه های حسگر با شناسه گره اتفاقی، الگوریتم پیشنهاد با توجه به خود تثبیت است.
اثبات: زمانیکه گره در حال خواب بیدار می شود، یک پیام درخواست آزمایش برای بررسی اینکه آیا گره همسایه در حال کار در مجاورتش وجود دارد ارسال می کند. اگر بیش از یک حسگر برای فعال بودن بطور همزمان کاندید باشد، تصمیم های گره ها برای حل شکست گره با مقایسه شناسه اش تنها با شناسه های همسایه هایش گرفته می شوند، حتی اگر دو یا چند همسایه گره شناسه یکسان داشته باشند. بنابراین به نتیجه می رسیم.
۴-۹ آنالیز تئوری : آنالیز پیچیدگی پیام
زمانیکه به ارتباطات غیرقابل اطمینان رسیدگی می کنیم، مد آسنکرون الگوریتم پیشنهادی، مزایای عمده ی اجازه دادن به طرح های ارتباطاتی انعطاف پذیرتر را ارائه می کند که کمتر به تاخیرهای ارتباطات و انواع آنها حساس می باشند.
از آنجاییکه طرح ما به هیچ همزمان سازی گره وابسته نمی باشد و با توجه به قواعد r1 و r2 ، خسارت ها مانع پیشرفت فرایند خود تثبیتی روی هر دو گره فرستنده (بیدار) و گیرنده (در حال کار) نمی شوند، یعنی خسارت پیام های آزمایش/پاسخ توسط دو قاعده الگوریتم جذب/پشتیبانی می شود.
در ادامه، کران بالای تعداد واقعی پیام های آزمایش/پاسخ مبادله شده در طول بهینه سازی طول عمر شبکه را ارائه می کنیم.
فرضیه ۲: تعداد پیام های آزمایش/پاسخ موجود در الگوریتم حداکثر برابر است با:
(۴-۱۱)
که در آن n تعداد گره ها است، m تعداد لینک های ارتباطاتی مجازی است، عمر قابل اطمینان گره iاست و ، j امین بازه ی زمانی خواب گره i است.
اثبات: عمر قابل اطمینان، ، گره i، برای قابلیت اطمینان مشخص Ri با شروع ماموریت در لحظه صفر بصورت زیر محاسبه می شود:
(۴-۱۲)
عمری است که در این مدت گره حسگر i با موفقیت با قابلیت اطمینان Ri عمل خواهد کرد.
با توجه به زیرتقسیم های بازه های زمان خواب گره، داریم:
(۴-۱۳) ۰= t0< t1 <t2 < …< tk=t
 

دانلود کامل پایان نامه در سایت pifo.ir موجود است.