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

این پروتکل سعی در افزایش طول عمر شبکه با رسیدن به سطح بالایی از کارایی انرژی و مصرف انرژی یکنواخت در بین همه گره های شبکه دارد.
این پروتکل سعی در کاهش تاخیری که داده در طول مسیرش برای رسیدن به سینک، تحمل می کند دارد.
مدل شبکه ای که به وسیله این پروتکل بررسی می شود، مجموعه ای متجانس از گره ها را فرض می کند که در داخل یک ناحیه جغرافیایی آرایش یافته اند. فرض می شود که گره ها، اطلاعات و دانش کلی درباره موقعیت های سایر حسگرها را داشته باشند. به علاوه گره ها توانایی کنترل توان خودشان به منظور پوشش دادن محدوده های دلخواه را دارند. گره ها ممکن است همچنین به وسیله فرستنده -گیرنده های رادیویی به قابلیت دسترسی چندگانه با تقسیم بندی کد ، مجهز شده باشند. مسئولیت گره ها جمع آوری و تحویل داده به یک سینک مثلا یک ایستگاه پایه بی سیم است. هدف، توسعه و بهبود یک ساختار مسیریابی و یک طرح تراکم به منظور کاهش مصرف انرژی و تحویل داده متراکم شده به ایستگاه پایه با کمترین تاخیر است، در حالی که مصرف انرژی بین گره های حسگر متعادل شده است. برخلاف سایر پروتکل ها، که بر روی یک ساختار درختی و یا یک ساختار سلسله مراتبی مبتنی بر خوشه، برای جمع آوری داده و پخش داده تکیه دارند، روش PEGASIS ، یک ساختار زنجیری را به کار می گیرد. بر اساس این ساختار، گره ها، با نزدیک ترین همسایه هایشان ارتباط برقرار می کنند. ساختار زنجیر، با دورترین گره از سینک شروع می شود. گره های شبکه به صورت تصاعدی و با شروع از نزدیکترین همسایه به گره آخری، به زنجیر اضافه می شوند. نزدیک ترین همسایه به گره راس در زنجیر جاری، اول اضافه می شود و به همین ترتیب، تا جایی که همه گره ها در بر گرفته شوند. برای مشخص کردن نزدیک ترین همسایه، یک گره، قدرت سیگنال را به منظور اندازه گیری فاصله، تا همه ی گره های همسایه اش به کار می گیرد. با استفاده از این اطلاعات، گره، قدرت سیگنال را طوری تنظیم می کند فقط داده های نزدیک ترین گره، بتواند شنیده شود. یک گره در داخل زنجیر، به عنوان رهبر زنجیر انتخاب میشود. مسئولیت گره رهبر،انتقال داده متراکم شده به ایستگاه پایه است. در روش PEGASIS [۵۳] به منظور اطمینان از چرخش نقش رهبریت بین گره های مختلف، در هر دوره، گره I mod N به عنوان رهبر زنجیر در آن دوره انتخاب می شود . که در این رابطه I به شماره دوره جاری اشاره می کند و N نشان دهنده کل تعداد گره ها در شبکه است.
با این انتخاب، نقش رهبری زنجیر، در بین مکانهای مختلف زنجیر، بعد از هر راوندی انتقال پیدا می کند.دوره ها می توانند به وسیله سینک داده مدیریت شوند و گذار (انتقال) از یک دوره به دوره دیگر، به وسیله یک موج رادیویی با توان بالا که به وسیله سینک داده منتشر شده است، گردش می یابد. این چرخش نقش رهبریت در بین گره های زنجیر، مصرف انرژی متعادل شده ای را از لحاظ میانگین، در بین گره های شبکه، تضمین می کند. اما به هر حال، گره هایی که به عنوان نقش رهبریت زنجیر در نظر گرفته میشوند، ممکن است به طور دلخواه و یا قراردادی از سینک داده دور در نظر گرفته شوند. چنان گرهی، ممکن است لازم باشد با توان بالایی به منظور رساندن داده هایش به ایستگاه پایه، انتقال دهد. تراکم داده در این روش، در طول زنجیر به دست می آید. در ساده ترین شکل آن، فرآیند تراکم، می تواند به صورت متوالی و طبق روند زیر انجام شود:
ابتدا، رهبر زنجیر، یک نشانه[۵۴] را برای گره های آخری در انتهای سمت راست و چپ زنجیر می فرستد. به محض دریافت نشانه، گره های انتهایی، داده شان را به همسایه های پایین دست خود در زنجیر و به طرف رهبر انتقال می دهند. گره همسایه، داده را متراکم می کند و آن را به همسایه پایین دستش انتقال می دهد. این فرآیند ادامه پیدا می کند تا زمانی که داده متراکم شده،به رهبر برسد. به محض دریافت داده از هر دو طرف زنجیر، رهبر، داده را متراکم می کند و آنها را به سینک داده منتقل می کند. با وجود سادگی این روش، اما طرح متراکم کردن متوالی، قبل از این که داده های متراکم شده به ایستگاه پایه تحویل داده شوند، منجر به تاخیرهای طولانی خواهد شد. در واقع یکی از مهمترین عیبهای روش PEGASIS تاخیر در پاسخگویی است. یک راه بالقوه، برای کاهش تاخیر مورد نیاز برای تحویل داده متراکم شده به سینک، استفاده از متراکم ساختن موازی داده، در طول زنجیر است. یک روش که درجه بالایی از موازی کردن را به دست می دهد، به این ترتیب به دست می آید که گره های حسگر، به فرستنده -گیرنده هایی که قابلیت دسترسی چندگانه با تقسیمبندی کد را دارند، مجهز شده باشند. قابلیت اضافه شده، برای اجرای ارتباطات نزدیک و بدون تداخل میتواند به منظور پوشش دادن یک ساختار سلسله مراتبی بر روی زنجیر استفاده شود و نتیجتاً، از ساختار جاسازی شده موجود برای متراکم نمودن داده استفاده شود. در هر دوره ای، گره ها، در یک سطح داده شده از سلسله مراتب، با یک همسایه نزدیکشان در سطحی بالاتر از سلسله مراتب موجود ارتباط برقرار می کنند. این فرآیند، تا زمانی که داده متراکم شده، به رهبر که در سطح راس آن سلسله است، برسد ادامه پیدا می کند. سپس رهبر، داده متراکم شده نهایی را به ایستگاه پایه منتقل می کند. روشهای دیگری با الهام گرفتن از روش مبتنی بر زنجیر و به منظور بهبود عملکرد آن پیشنهاد شده که اغلب به جای ساختار زنجیری از ساختارهای دیگر بهره می گیرد. با این روشها، میزان تاخیر تا حد زیادی کاهش پیدا

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

می کند. این روشها که در مراجع معرفی شده اند عملکرد بهتری از لحاظ میزان تاخیر در تحویل داده نسبت به روش مبتنی بر زنجیر PEGASIS از خود نشان می دهند.
۳-۷-۴ روش های مبتنی بر انرژی باقیمانده هر گره (آگاه از انرژی)[۵۵]
دسته دیگر از روشهایی که به منظور بهبود عملکرد شبکه های حسگر بیسیم معرفی شده اند، از یک فرض منطقی برای پروتکل خود استفاده می کنند. در اغلب این روشها که روشهای آگاه از انرژی خوانده می شود، فرض می شود که هر گره حسگر در هر لحظه بتواند تخمینی از انرژی باقیمانده منبع توانش بزند. این فرض با توجه به اینکه مدل مصرف انرژی کاملاً واضح است و همچنین تعداد پرشهایی که به وسیله هر بسته پیموده می شود نیز تقریباً مشخص است فرضی منطقی است. از جمله روشهایی که بر اساس اطلاع از انرژی باقیمانده گره ها کار می کنند روشهای X-LEACH و ERA و Improved LEACH و HEED است .
توجه شود که روشهایی که بر اساس اطلاع از انرژی باقیمانده گره ها کار میکنند به این دلیل که در انتخاب نقش برای گره ها، مسئله انرژی را مدنظر قرار می دهند می توانند طول عمر شبکه را در مقایسه با روشهای قبلی افزایش بخشند. در همه الگوریتمهای مسیریابی که بر اساس انرژی باقیمانده گره ها به تصمیم گیری می پردازند هر گره با اطلاع از انرژی اولیه اش و دانستن تعداد بسته های انتقالی خود می تواند تخمینی از انرژی باقیمانده اش را در هر لحظه در اختیار داشته باشد.توجه شود که در مورد این الگوریتمها، دو معیار FND [۵۶] و LND [۵۷] برای بررسی عملکرد آنها از لحاظ طول عمر شبکه استفاده خواهد شد . معیار FND ،مدت زمانی را مشخص می کند که طول می کشد تا اولین گره حسگر داخل شبکه انرژیش تمام شده و یا به عبارت دیگر بمیرد. معیار دوم یعنی LND مدت زمانی را مشخص می کند که طول می کشد تا همه گره های داخل شبکه بمیرند . در حقیقت معیار دوم، مقیاسی از طول عمر کلی شبکه خواهد بود.
۳-۷-۵ الگوریتم خوشه بندی مبتنی بر انرژی باقیمانده (آگاه از انرژی باقیمانده ) [۵۸]ERA
در ادامه روشهای مبتنی بر خوشه پیشنهاد شده برای این شبکه ها که برای افزایش طول عمر پیشنهاد شد، یک روش مطلع از انرژی دیگر که ما آن را ERA می نامیم برای مسیریابی در شبکه های حسگر بیسیم معرفی شد . همانطور که از نام این روش برمی آید، یکی از مهمترین معیارها برای تصمیم گیری در مورد انتخاب مسیر، انرژی باقیمانده گره های موجود در آن مسیر خواهد بود. در حقیقت بر خلاف اکثر روشهای قبلی که سعی در مینیمم کردن طول مسیر پیموده شده داشتند، این روش با مدنظر قرار دادن انرژی، سعی در ماکزیمم کردن انرژی باقیمانده مسیر به وجود آمده از هر گره تا ایستگاه پایه خواهد نمود.
روش ERA ، دقیقاً مشابه با روش LEACH ، تعدادی از گره ها را در هر دوره به عنوان سرگروه خوشه انتخاب خواهد کرد. اما نحوه تعیین اعضای داخل هر خوشه مانند LEACH نخواهد بود. در این روش ، بعد از آن که سرگروه ها انتخاب شدند، هر سرگروه تخمینی از انرژی باقیمانده اش برای انتقال بسته داده به ایستگاه پایه را با استفاده از رابطه ی ( ۳-۳ ) به دست خواهد آورد .
(۳-۳ )
که در این رابطه ، SC مجموعه سرگروه خوشه ها است . (ECH-rem)i انرژی باقیمانده سرگروه i ام در دوره جاری و (Eto-BS)i انرژی لازم برای انتقال داده از سرگروه iام به ایستگاه پایه را بیان می کند. سپس هرسرگروهی مقدار انرژی باقیمانده تخمینی خود را در داخل بسته، اعلان سرگروهی خود قرار داده و آن را برای بقیه گره های شبکه می فرستد. این فرآیند به وسیله همه گره هایی که بعنوان سرگروه انتخاب شده اند انجام می شود.
حال گره های عادی بایستی یکی از سرگروه ها را برای قرار گرفتن در گروه مربوطه به عنوان سرگروه خودشان انتخاب کنند.در این مرحله، هر گره عادی نیزانرژی باقیمانده اش را برای فرستادن بسته به تک تک سرگروه های موجود طبق رابطه ( ۳-۴ ) تخمین می زند .
(۳-۴)
که در این رابطه ، SN مجموعه گره های عادی شبکه است و (Enon-CH-rem)j انرژی باقیمانده گره عادی i ام در دوره جاری را بیان می کند و (EtoCH)ji jام تا سرگروه i ام را بیان می کند.
سرانجام هر گره عادی این مقادیر را برای همه سرگروه های موجود محاسبه کرده و نهایتا گرهی را به عنوان سرگروه خود انتخاب می کند که رابطه (۳-۵ ) را ماکزیمم کند .
(۳-۵)
به این ترتیب خوشه ها برای ماکزیمم کردن انرژی باقیمانده مسیر به وجود آمده از هر گره عادی تا سرگروه و از سرگروه تا ایستگاه پایه تشکیل خواهد شد.در مرحله بعدی، مشابه با روش LEACH هر گرهی بسته داده اش را مستقیما برای سرگروه فرستاده و سرگروه ها نیز بسته های دریافتی را برای ایستگاه پایه خواهند فرستاد.
فصل چهارم
شبیه سازی
۴-۱ مقدمه
در مورد الگوریتم های غیر گسسته، حسگرها ممکن است در بیش از یک مجموعه پوشش شرکت کنند. در برخی موارد، ممکن است طول عمر شبکه را در مقایسه با الگوریتم های مجموعه پوشش گسسته طولانی سازد ولی طراحی الگوریتم ها برای مجموعه های پوشش غیر گسسته در کل منجر به درجه ی بالاتری از پیچیدگی می شود.
تمام راه حل های متمرکز ارائه شده در فصل سوم برای بیشینه سازی طول عمر شبکه با سازماندهی گره های حسگر در تعداد مناسبی پوشش مجموعه گسسته یا غیرگسسته که بطور دوره ای فعال می شوند، توسعه می یابند. با اینحال، برای تطبیق با شبکه های بزرگتر مقیاس پذیری بهتری ندارند و به تحمل پذیری خرابی دست نمی یابند، یعنی فرض
می شود که گره هایی که به مجموعه پوشش یکسان تعلق دارند هرگز خراب نخواهند شد یا در طول نوبت پوشش مجموعه هرگز غیرقابل دستیابی نخواهند بود.
به منظور مخفی سازی وقوع خرابی ها، یا عدم دسترس پذیری ناگهانی گره های حسگر، طبق مطالعات وسیعی توسط دانشمندان ، تعدادی الگوریتم توزیع شده توسعه یافته اند. اطلاعات زمانبندی در کل شبکه منتشر می شود و تنها حسگرهای موجود در حالت فعال مسئول نظارت تمام هدف ها می باشند، در حالیکه بقیه گره ها در مد خواب با انرژی کم قرار دارند. گره ها بطور مشارکتی تصمیم می گیرند که کدام یک در مد خواب به مدت مشخصی باقی بمانند.
محققان ، پیش بینی برای طولانی کردن طول عمر شبکه را با استفاده از همبستگی های زمانی – فضایی میان داده های حس شده توسط گره های حسگر مختلف انجام می دهند. بر اساس فرایند گاوسی، محققان این مسئله را بصورت یک مسئله ی پوشش مجموعه زیرپیمانه ای با مینیمم وزن فرموله کردند و الگوریتم های حریصانه هرس شده ی متمرکز و توزیع شده ([۵۹]ITAG و [۶۰]DTGA) پیشنهاد کردند. ثابت کردند که این الگوریتم ها به مجموعه پوشش یکسان دست می یابند.
بهینه سازی طول عمر با استفاده از دانش مربوط به داینامیک های رویدادهای تصادفی در مقالات گوناگون مورد مطالعه قرار گرفته است. در این پایان نامه تعاملات بین زمانبندی دوره ای و خواب هماهنگ برای هر دو شبکه حسگر استاتیک متراکم سنکرون و آسنکرون ارائه شده است و نشان داده شده است که داینامیک های رویداد می توانند برای صرفه جویی های انرژی عمده با قرار دادن حسگرها روی زمانبندی روشن / خاموش دوره ای بکار گرفته شوند. این تحقیق برمبنای این واقعیت است که بدون پوشش قرار دادن ناحیه ای در برخی مواقع می تواند قابل قبول باشد، زیرا رویدادی که زمانی وارد می شود که هیچ حسگر فعال وجود ندارد، ممکن است به مدت طولانی بماند تازمانیکه حسگر فعال گردد.
محققان یک الگوریتم توزیع شده با زمان چندجمله ای برای بیشینه سازی طول عمر شبکه طراحی کرده و ثابت کردند که طول عمر بدست آمده توسط الگوریتم آنها، ماکزیمم طول عمر احتمالی درون فاکتور تقریب لگاریتمی را تقریب می زند. الگوریتم پیشنهادی به دنبال بیشینه سازی طول عمر شبکه های حسگر با فعال سازی حسگرهای مبتنی بر میزان انرژی پسماندشان می باشد.
بر این اساس الگوریتم پوشش کلی ارائه می شود که اتصال شبکه را نیز در بر می گیرد. پروتکل پیشنهادی که پروتکل پوشش احتمالی[۶۱] (PCP) نیز نامیده می شود برای مدل حس کردن دیسک رایج همانند مدل حس کردن احتمالی کار می کند. برای پشتیبانی از مدل های حس کردن احتمالی، محققان مفهوم پوشش احتمالی ناحیه هدف را با آستانه مشخص مطرح می سازند که به این مفهوم است که یک ناحیه در صورتی پوشش یافته در نظر گرفته می شود که احتمال حس کردن رویدادی که در هر نقطه ای در ناحیه روی می دهد، حداقل باشد. آنها صحت پروتکل را ثابت می کنند و کران هایی روی زمان همگرایی اش و پیچیدگی پیام فراهم می سازند.
گرچه این الگوریتم ها کاربردها را برای دستیابی به کارایی خیلی خوب فعال می سازند، با مشکل رایجی مواجه می شوند، یعنی وابستگی شان به این فرضیه که انتظار نمی رود که قابلیت های اطمینان گره های حسگر در طول زمان کاهش یابند. بعلاوه، هیچ ضمانتی برای اطمینان از این واقعیت پیشنهاد نشده است که تنها یک گره حسگر باید برای هر منطقه نظارتی در حالت فعال باشد که منجر به شرایطی می شود که در آنها دو گره حسگر همسایه ممکن است در گام همزمان انتخاب شوند و تصمیم دو گره همسایه ممکن است یکسان باشد. در این پایان نامه ، یک الگوریتم خود تثبیتی موثر برای غلبه بر مشکل بهینه سازی طول عمر در شبکه های حسگر مقیاس بزرگ ارائه می کنیم. این مطالعه به دلایل زیر متفاوت از کارهای قبلی است:
از توزیع Weibull[62] برای در نظر گرفتن خرابی های استهلاک و بنابراین افزایش طول عمر شبکه استفاده می کنیم.
یک کران بالا از تعداد واقعی پیام های probe/reply مبادله شده در طول بهینه سازی طول عمر شبکه بیان می کنیم.
رابطه های جایگزینی بین قابلیت اطمینان شبکه حسگر و تعداد مورد نیاز مجموعه های پوشش را هماهنگ می سازیم، یعنی می خواهیم برای آستانه قابلیت اطمینان ثابت، حداقل تعداد مجموعه های پوشش را مشخص سازیم که می توانند در پوشش سیستم مورد استفاده قرار گیرند، در حالیکه به قابلیت اطمینان از پیش تعیین شده شبکه حسگر دست می یابند.
ضمانت های قابل اثباتی برای فرایند انتخاب گره های کاری برای هر منطقه نظارتی فراهم می سازیم.
برخلاف روش های قبلی، از مفهوم جدید خود تثبیتی برای دستیابی به صرفه جویی های انرژی عمده استفاده می کنیم.
۴-۲ اصول پایه و مدل حس کردن
توپولوژی شبکه حسگر را با یک گراف بدون جهت – گراف ارتباطات G=(V,E) مدل سازی می کنیم. فرض کنید V مجموعه گره ها است (مجموعه رئوس) و E لینک های بین گره ها (مجموعه یال ها). گره ها با i=1,2,…,n برچسب گذاری می شوند و لینک بین گره های i و j با (I,j) نمایش داده می شود. مجموعه همسایه های گره i با نمایش داده می شود و درجه (تعداد همسایه ها) گره i با نمایش داده می شود.
با Rs و Rc بترتیب بازه حس کردن و بازه ارسال رادیویی گره حسگر را نشان می دهیم. فرض می کنیم که گره های حسگر بطور اختیاری در ناحیه مورد نظر گسترده می شوند. کل ناحیه به شبکه های مربعی با طول ضلع تقسیم می شود و یک گره حسگر بصورت بیدار در هر شبکه انتخاب می شود. ماکزیمم فاصله بین هر دو زوج گره حسگر در ش
بکه های مجاور درون بازه ی ارسال یکدیگر می باشد. مدل های حس کردن و اتصالی که استفاده می کنیم .اگر باشد، در اینصورت پوشش دلالت بر اتصال دارد. چنین استنباط می کنیم که به منظور حفظ پوشش، سایز شبکه باید بصورت زیر انتخاب شود:
(۴-۱)
بنابراین برای ناحیه بزرگی با سایز l × l، نیاز به گره حسگر برای عمل کردن در حالت فعال برای تضمین پوشش کامل دارد. بهرحال، در راهکار ما، زیرتقسیم منطقه نظارت شده به شبکه های مربعی تنها برای دستیابی به ارزیابی بهتر کارایی پوشش انجام می گیرد. در واقع، الگوریتم پیشنهادی ما می تواند روی هر توپولوژی شبکه اختیاری عمل کند.