شکل ۱-۱:معماری یک گره حسگر[۷]

براساس ویژگی های مولفه های تشکیل دهنده گره های حسگر ، شبکه های حسگر را میتوان به دو رده تقسیم کرد:

شبکه های حسگر همگن و شبکه های حسگر ناهمگن

در یک شبکه حسگر همگن ، قابلیت و توانمندیهای گره های حسگر از نظر نوع پارامتر حس شونده، قدرت ارتباطی و محدودیت منابع مانند هم است در حالیکه در یک شبکه ناهمگن گره ها دارای قابلیت‌ها و کارکردهای متفاوت هستند.

مثلا برخی از گره ها ممکن است منبع تغذیه بزرگتر و یا پردازنده قویتری نسبت به سایر گره ها داشته باشند.استقرار یک شبکه همگن به مراتب ساده تر از یک شبکه ناهمگن است.

۱-۳ ویژگیهای عمومی شبکه های حسگر

علاوه بر نکاتی که تاکنون درباره شبکه‌های حسگر به عنوان مقدمه آشنایی با این فناوری بیان کردیم، اینشبکه‌ها دارای یک سری ویژگی‌های عمومی نیز هستند. مهم‌ترین این ویژگی‌ها عبارت استاز:

بر خلاف شبکه‌های بی‌سیم سنتی، همه گره‌ها در شبکه‌های بی‌سیم حسگر نیازیبه برقراری ارتباط مستقیم با نزدیک‌ترین برج کنترل قدرت یا ایستگاه پایه ندارند،بلکه حسگرها به خوشه‌هایی (سلول‌هایی) تقسیم می‌شوند که هر خوشه (سلول) یک سرگروهخوشه موسوم به Parent انتخاب می‌کند.این سرگروه‌ها وظیفه جمع‌ آوری اطلاعاترا بر عهده دارند. جمع‌ آوری اطلاعات به منظور کاهش اطلاعات ارسالی از گره‌ها بهایستگاه پایه و در نتیجه بهبود بازده انرژی شبکه انجام می‌شود. ‌البته چگونگیانتخاب سرگروه خود بحثی تخصصی است که در تئوری شبکه‌های بی‌سیم حسگر مفصلاً موردبحث قرار می‌گیرد.

هر حسگر موجوددر شبکه دارای یک رنج حسگری است که به نقاط موجود در آن رنج احاطه کامل دارد. یکیاز اهداف شبکه‌های حسگر این است که هر محل در فضای مورد نظر بایستی حداقل در رنجحسگری یک گره قرار گیرد تا شبکه قابلیت پوشش همه منطقه موردنظر را داشتهباشد.

یک حسگر با شعاع حسگری r را می‌توان با یک دیسک با شعاع r مدل کرد. ایندیسک نقاطی را که درون این شعاع قرار می‌گیرند، تحت پوشش قرار می‌دهد. بدیهی است کهبرای تحت پوشش قرار دادن کل منطقه این دیسک‌ها باید کل نقاط منطقه رابپوشانند.

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

با این که توجه زیادی به پوشش کامل منطقه توسط حسگرها می‌شود،احتمال دارد نقاطی تحت پوشش هیچ حسگری قرار نگیرد. این نقاط تحت عنوان حفره‌هایپوششی نامیده می‌شوند. اگر تعدادی حسگر به علاوه یک منطقه هدف داشته باشیم، هر نقطهدر منطقه باید طوری توسط حداقل n حسگر پوشش داده شود که هیچ حفره پوششی ایجاد نشود. این موضوع لازم به ذکر است که مسأله حفره پوششیبسته به نوع کاربرد مطرح می‌گردد. در برخی کاربردها احتیاج است که درجه بالایی ازپوشش جهت داشتن دقت بیشتر داشته باشیم.

۱-۴ کاربردهای شبکه های حسگر

همانطور که در بحث مقدمه مطرح شد،امروزه کاربردهای بسیاری برای شبکه های حسگر مطرح شده است و روز به روز هم برتعداد آنها اضافه میشود.

برخی از کاربردهایی که تاکنون روی این شبکه ها مورد ارزیابی قرار گرفته اند عبارتند از:

میدانهای جنگی

درمیدان های جنگی ، میتوان جهت شناسایی و بررسی آماری تجهیزات و نیروی دشمن و همینطور کلاسبندی و پیگردی نحوه آرایش و مسیر حرکت نیروهای دشمن یا نیروهای خودی ، از شبکه های حسگر استفاده کرد و درنهایت وضعیت نیروهای خودی را در قالب نیروهای دشمن بررسی نمود.

شناسایی محیط های آلوده

در محیط های مختلف امکان وجود آلودگیهای مختلف وجود دارد.لذا با بهره گرفتن از چنین شبکه هایی میتوان وجود آلودگیهای مشخصی را در سطح محیط تحت نظر بررسی کرد وحتی میزان غلظت آلودگی در قسمتهای مختلف را مشاهده نمود ودرنهایت با بهره گرفتن از اطلاعات آماری بدست آمده در خروجی سیستم میتوان نمودار سه بعدی وضعیت آلودگی در سطح محیط مورد نظر را بدست آورد.

نوع آلودگی نیز میتواند یکتا نباشد و با توجه به امکانات ، هر گره در شبکه حسگر میتواند شناسایی چندین نمونه آلودگی را پشتیبانی کند.

مانیتورکردن محیط زیست

مجموعه ای از تحقیقات در زمینه محیط زیست نیازمند انجام مطالعات مکرر و متمرکز وصرف زمان زیادی جهت جمع آوری اطلاعات میباشد که معمولا از حوصله وتوانایی چشمان انسان خارج است و در چنین مواردی از دستگاه های مانیتورینگ ،تحلیلگر و ذخیره کننده نتایج استفاده میشود.

از طرفی دیگر ،به دلیل وجود برخی شرایط محیط زیست، اکثر کارهای تحقیقاتی بایستی در سکوت وآرامش صورت گیرد تا وجود انسان و تجهیزات در محیط ، اثر منفی بر عملکرد غریزه های ذاتی موجودات نداشته باشد.ازاین رو معمولا تمام سیستمهای مانیتورینگ قابلیت کنترل از راه دور را دارنددر عین حال این سیستمها طوری انتخاب میگردند که وجود آنها در محیط محسوس نباشد.

با در نظر گرفتن تمام موارد فوق ، ملاحظه میشود که تمام شبکه های حسگر ،علاوه بر بحث هزینه پایین مصرفی،در زمینه مانیتور کردن محیط زیست،ازتوانایی بالایی برخوردار میباشند.

در مواردی همچون بررسی وضعیت آب و هوای جوی محیط و بررسی وضعیت ظاهری آن،به خصوص محیط سرسبز وجنگلی،بررسی رشدونمو گیاهان وموجودات و موقعیت یابی وپیگردی موجودات زنده در محیط زیست میتوان از قدرت بالای شبکه های حسگر استفاده کرد.

بررسی وتحلیل وضعیت بناهای ساختمانی:

بسیاری از سازمان ها وموسسات تحقیقاتی در زمینه عمران ومسکن برای انجام مطالعات و تحقیقات خود از وضعیت بناهای مدنظر،در طول زمان یا در هنگام بروز حوادث طبیعی بخصوص زلزله،نیازمند استفاده از تجهیزات مانیتورینگ میباشد تا اطلاعاتی مانند میزان فشاروتحمل مصالح ، وجود ترک ،میزان آسیب وارده ،وضعیت فرسودگی ،امنیت و حفاظت ساختمان وسایر جزئیات مرتبط با هدف تحقیقات در مورد بناهایی مثل ساختمانهای قدیمی ، پلها، سدها و موزه ها و… را جمع آوری کنند و با توجه به توانایی های شبکه های حسگر ، میتوان ازاین شبکه ها برای دست یافتن به اهداف مطرح شده در بالا استفاده کرد.

درجاده ها و بزرگراههای هوشمند:

یکی از مشکلات جامعه و راهنمایی ورانندگی ،کنترل وضعیت ترافیک در سطح شهر میباشد.بابرپایی شبکه هایی از گره های حسگر در سطح شهر و قرار دادن گره ها در بزرگراهها و خیابانهای شهر ،میتوان بزرگراهها وخیابانها را هوشمند ساخت و از وضعیت تراکم عبور ومرور وسایل نقلیه ویا بروز حوادثی مانند برخورد چندین وسیله نقلیه، در نقاط زیر نظر گره های سنسور ،اطلاع یافت و در نهایت درکل سطح شهروضیت ترافیک وتصادفات را شناسایی وپیگیری نمود.

کاربردهای پزشکی

مراقبت از سلامت انسان:

این کاربردها شامل تشخیص و نظارت بر بیماریهای جسمی انسان از طریق نصب حسگرها در بدن ویا کنترل بیماریهای روانی از طریق ثبت رفتارهای محیطی انسان توسط حسگرهاست.

جراحی:

از حسگرهای بسیار ریز هوشمند که مجهز به روبات باشند میتوان در انجام جراحی های خاص و ظریف استفاده کرد.

سایر کاربردها

از دیگر کاربردهای این شبکه ها ، کاربردهای آن ها در صنعت می باشد ، برای مثال در فرآیندهای اتوماسیون صنعتی در قسمت هایی که حضور انسان مشکل و یا غیر ممکن است ، می توان با راه اندازی این شبکه ها بر مواردی چون کنترل کیفیت محصولات و از آن مهم تر کنترل امنیت و ایمنی این نوع محیط ها نظارت کرد.

همچنین با بهره گرفتن از شبکه های حسگر بی سیم می توان منازل هوشمند طراحی کرد و مثلا از اینترنت وسایل خانه را کنترل کرد و شاید بتوان گفت که شبکه های حسگر بی سیم یک جز جدانشدنی از زندگی انسانها در آینده نزدیک خواهد بود.

براساس ویژگیهای عملیاتی کاربردهای فوق ، درحالت کلی میتوان کاربردهای شبکه های حسگر را در دو رده اصلی طبقه بندی کرد:کاربردهای پرس و جویی و کاربردهای وظیفه ای.

در کاربردهای پرس وجویی هدف آن است که اطلاعات جمع آوری شده در شبکه مورد پرس وجو قرار گیرد. به عنوان مثال حس کردن محیط به منظور استخراج اطلاعات از محیط فیزیکی(مثلا اطلاعاتی نظیر دما،رطوبت، نور، فشارو…) یکی از پرکاربردترین موارد در این زمینه ست.

این کاربردها ممکن است دارای پرس وجو های ساده برای استخراج داده های خام از گره ها و یا دارای پرس وجوهای پیچیده ای باشند که مستلزم جمع آوری و ترکیب داده ها از گره های مختلف است.

کاربردهای وظیفه ای شامل برنامه ریزی گره ها برای اجرای وظیفه ای معین به هنگام وقوع رویدادی خاص است.

این رویدادها به عنوان مثال میتوانند شامل تغییرات محیطی ، دریافت پیام از گره های مجاور و یا تغییرات نرم افزاری/سخت افزاری درون گره ها باشد. کاربردهای وظیفه ای میتوانند بصورت گسترده تری هم باشد که در آن گره ها با همکاری هم کار خاصی را انجام میدهند.مثلا دنبال کردن یک شی متحرک در یک منطقه.

نوع کاربرد فوق بصورت شماتیک در شکل ۱-۲ نشان داده شده است.

شکل۱-۲ : کاربردهای پرس وجویی و وظیفه ای در شبکه های حسگر[۲]

۱-۵عوامل مهم در طراحی شبکه های حسگر[۹][۱۰]

شبکه های حسگر به دلیل ویژگی های خاصی که دارند با چالشهای زیادی روبرو هستند وعوامل مهمی در طراحی آنها دخیل اند. این چالشها بیشتر به محدودیتهای انرژی ،پردازش داده ها و مکانیزمهای ارتباطی و مسیریابی مرتبط هستند. در این قسمت به برخی ازاین عوامل مهم اشاره میکنیم.

۱-۵-۱ مسیریابی

قراردادها و الگوریتم های مسیریابی همواره یکی از مسائل مهم در طراحی شبکه بوده است.این قراردادها و الگوریتم ها در شبکه های حسگر باید به گونه ای باشد که میزان مصرف انرژی شبکه به حداقل برسد.

با توجه به اینکه مکان حسگرها از قبل در شبکه مشخص نمی باشد، وجود یک پروتکل مناسب مسیریابی برای انتقال اطلاعات بسیار مورد نیاز است. این پروتکل باید توانایی این را داشته باشد که به صورت تطبیقی بتواند عملیات مسیریابی را انجام دهد

در حالت کلی انتظار میرود که قراردادهای مسیریابی سه عملکرد را درشبکه پیاده سازی کنند.تعیین و تشخیص تغییرات توپولوژی (مثلا خرابی و از کارافتادگی بعضی از گره ها) ، برقراری اتصالات در شبکه و محاسبه ویافتن مسیرهای مناسب.

درحال حاضر تلاشهای زیادی برای طراحی قراردادهای مسیریابی جدید و خاص برای شبکه های حسگر در حال انجام است، زیرا قراردادهایی که برای شبکه های دیگر طراحی شده اند قابلیت انطباق کامل با شبکه های حسگر را ندارند.

۱-۵-۲ انرژی محدود

مهمترین مساله چالش در شبکه های حسگر، انرژی محدود است.

گره های حسگر معمولا انرژی مورد نیاز خود را توسط یک یا چند عدد باتری تامین میکنند. در بسیاری از کاربردها، امکان دسترسی به این گره ها جهت تعویض باتری وجود ندارد و یا اینکار مقرون به صرفه نیست. مثلا مواقعی که تعداد زیادی از این گره ها در یک منطقه وسیع جغرافیایی مثل جنگل و دریا و یا در یک منطقه خطرناک مثل منطقه جنگی توزیع شده اند.

بسیاری از تلاشهای تحقیقاتی با هدف صرفه جویی در مصرف انرژی از جنبه های مختلف ، در حال انجام است.

در شبکه های حسگر، انرژی معمولا به سه منظور اصلی مصرف میشود:[۹]

انتقال داده

پردازش سیگنال

عملیات سخت افزاری

با توجه به اینکه پرمصرف ترین بخش مربوط به انتقال اطلاعات است ، در طراحی پروتکل ها سعی می شود که تا آنجایی که امکان دارد ابتدا با بهره گرفتن از پردازش اطلاعات حجم اطلاعات مورد نظر برای انتقال کاهش داده شود.

همان طور که در شکل زیردیده می شود ، ارتباطات نیاز به انرژی مصرفی بیشتری نسبت به پردازش دارند که این موضوع، اهمیت پروتکل های ارتباطی (مسیریابی) را به خوبی روشن می کند.

شکل ۱ -۳ : انرژی مصرفی حسگرها در ارسال و پردازش داده

۱-۵-۳ مقیاس پذیری

گاهی تعداد گره های موجود در یک شبکه حسگر به چند ده هزار میرسد.به همین خاطر مقیاس پذیری دراین شبکه ها از اهمیت زیادی برخوردار است . مقیاس پذیری در یک شبکه حسگر به عوامل مختلفی از جمله الگوریتم مسیریابی ، تعداد Sink ها، سخت افزار مورد استفاده و الگوی ترافیکی شبکه بستگی دارد.

۱-۵-۴ زمان تاخیر

در بسیاری از موارد زمان رسیدن اطلاعات از یک گره به گرهSink از اهمیت زیادی برخوردار است.در برخی از کاربردها مانند کاربردهای بلادرنگ باید بازه زمانی مشخص برای رسیدن بسته تضمین شود.

۱-۵-۵ هزینه پایین

هزینه پایین تولید گره های حسگر استفاده از این شبکه ها را در بسیاری از کاربردها میسر میسازد.اصولا فلسفه وجودی شبکه های حسگر استفاده از تعداد زیادی گره حسگر ارزان قیمت به جای استفاده از تعدادکمی حسگر گرانقیمت است. استفاده از تعداد زیادی حسگر ارزان قیمت با قابلیت های محدود مزایای بیشتری نسبت به استفاده از تعداد کمی حسگر گران قیمت با قابلیت های زیاد دارد.

از جمله این مزایا میتوان به دقت سنجش ، پوشش بهتر و مقاومت در مقابل خرابی اشاره کرد.

۱-۵-۶تحمل پذیری خطا

گره های موجود در یک شبکه حسگر، ممکن است به دلایل مختلف از شبکه خارج شوند.از دلایل عمده میتوان به اتمام منبع تغذیه و خرابی فیزیکی گره حسگر اشاره کرد.شبکه های حسگر باید بتوانند دربرابر انواع خرابی مقاوم بوده بعد از تخریب برخی از گره ها در شبکه همچنان به کار خود ادامه دهند.

۱-۵-۷ امنیت

حفظ امنیت داده ها در شبکه های حسگر از پیچیدگی خاصی برخوردار است.در بسیاری از موارد مثل در یک منطقه جنگی ، تامین امنیت فیزیکی گره های حسگر نا ممکن است. علاوه براین گره های حسگر عموما بصورت بیسیم با یکدیگر ارتباط برقرار میکنند و این در حالیست که شبکه های بیسیم مشکلات بسیاری در زمینه امنیت دارند. همه اینها در شرایطی است که منابع لازم ، همچون قدرت پردازشی و حافظه ، برای رمز نگاری و رمز گشایی در گره های حسگر بسیار محدود است.

به همین دلیل سه فاکتور امنیتی محرمانگی ، جامعیت و نفوذ ناپذیری در این نوع شبکه ها در خطر است. کارهای انجام شده در زمینه امنیت هنوز در مراحل اولیه خود است و هنوز راه طولانی برای رسیدن به نقطه ای قابل قبول در پیش است.

۱-۶ صرفه جویی در مصرف انرژی در شبکه های حسگر

هر حسگر حدودا بین ۱۰۰ تا ۱۲۰ ساعت با یک باتری AAA در حالت فعال^[۴] کار میکند[۴۰].

از آنجا که معمولا تعداد زیادی حسگربسیار ظریف در نواحی دور دست ، خود کار^[۵] و یا خصومت آمیز مورد استفاده قرار میگیرند امکان شارژ مجدد و یا تعویض باتری آنها وجود تدارد.

این امر به همراه این نکته که گنجایش باتری ها هر ۳۵ سال تنها دوبرابر میشود[۴۱] اهمیت روش های صرفه جویی در مصرف انرژی را بهتر نشان میدهد. از آنجا که معمولا از شبکه های حسگر انتظار میرود که چندین ماه تا یکسال عمر کنند(بدون شارژ مجدد) [۱۸][۲۱]صرفه جویی در انرژی از مهمترین نکات در طراحی وپیاده سازی پروتکل ها در شبکه های حسگر میباشد.

از سوی دیگر توانایی حسگر در جمع آوری داده بستگی به کیفیت اتصال^[۶] آن به سایر حسگرها و پوشش^[۷] آن بر ناحیه دارد. روش های صرفه جویی انرژی معمولا بر کیفیت اتصال و پوشش حسگر ها تاثیر منفی میگذارند. از سوی دیگر باید برنامه ها در شبکه های حسگر در برابر وقوع خطا مقاومت داشته باشند که این امر نیز از این روشها تاثیر منفی میپذیرد.

از روش های رایج در جهت صرفه جویی در انرژی و حداکثر سازی طول عمر شبکه ، غیر فعال کردن تعدادی از گره ها و فعال نگه داشتن تعدادی دیگر برای اجرای وظایف جمع آوری داده و ارتباطات میباشد.

هنگامیکه یک حسگر غیر فعال میشود تمامی قسمتهای آن غیر از یک تایمر با مصرف پایین انرژی برای فعال سازی مجدد آن از کار می افتند[۴۲]. بنابراین مصرف انرژی در حسگر تنها در صد کوچکی از مصرف آن در حالت فعال میباشد.

روش های گوناگونی برای زمانبندی فعالیت گره ها ارائه شده اند که در لایه های مختلف شبکه فعالیت گره ها را زمانبندی میکنند.برای مقایسه این روشها لازم است پیش فرضها و شرایط در نظر گرفته شده در هر روش را مد نظر قرار دهیم.

هریک از روش های ارائه شده برای صرفه جویی در انرژی پیش فرضها و هدفهای گوناگونی دارند.

برای برخی از کاربردها سرعت انتقال داده مهم است و برای برخی دیگر انتقال بدون خطا ، برخی برای شبکه های با توزیع تصادفی طراحی شده اند و برخی برای شبکه های با توزیع دستی،….

با توجه به این نکات، لازم است که پیش فرضها و اهدافی که باعث تفاوت در روش های گوناگون ارائه شده برای حداکثرسازی عمر شبکه میشوند را مطرح و طبقه بندی کنیم.

۱-۶-۱ پیش فرضهای طراحی

از آنجاکه روش های مورد بررسی سعی در صرفه جویی در مصرف انرژی دارند ، دو فرض در بین تمامی آنها مشترک است:

هر حسگر منبع انرژی محدودی دارد.

حسگرها قرار است برای مدت زیادی فعالیت کنند.

در این قسمت به مقایسه طراحی های مختلف که منعکس کننده ساختارهای مختلف شبکه^[۸] ، روش های مختلف به کار اندازی^[۹] و قابلیت های مختلف حسگر^[۱۰]ها میباشد، میپردازیم.

ساختار شبکه:شبکه میتواند مسطح یا غیر سلسله مراتبی باشد به این معنی که همه حسگرها نقش یکسان و کارایی یکسان در شبکه دارند. در مقابل ممکن است که شبکه سلسله مراتبی باشد . به عنوان مثال در شبکه های حسگر با هدف تجسس و یا ردگیری^[۱۱] ، برخی گره ها مسئولیت ترکیب داده ها را به عهده میگیرند. این گره ها داده ها و گزارشهای سایر گره ها ی موجود در همسایگی شان را جمع آوری کرده و تشخیص میدهند که آیا شیئ ای کشف شده است یا نه و نتیجه حاصل را به مرکز اطلاع میدهند.به این نوع ساختار معمولا ساختار خوشه ای^[۱۲] و یا بر پایه نگهبان^[۱۳] گفته میشود که در آن سرگروه ها نقش مهمتری نسبت به سایر گره ها ایفا میکنند.بسیاری از روش های مورد بحث فرض خود را بر خوشه بندی بودن ساختار شبکه حسگر قرار میدهند[۴۲].

روش های مختلف به کار اندازی:کارایی شبکه حسگر و پوشش حسگر میتواند تحت تاثیر طرز اولیه چیدمان آنها قرار بگیرد.به عنوان مثال گره ها ممکن است که توسط یک هواپیمای در حال پرواز برروی منطقه تحت نظر ریخته شوند ویا ممکن است به صورت دستی در محل خود قرار داده شوند که در سناریوی اول توزیع گره ها تصادفی میباشد. بسیاری از روشها فرض میکنند که حسگرها توزیع یکنواخت تصادفی را در منطقه تحت نظر دنبال میکنند[۲۱][۲۵]. برخی از روشها بصورت مستقیم این فرض را بیان نمیکنند ولی در صورتیکه این فرض برقرار باشد ، برخی از روشها توزیع را پواسون دوبعدی در نظر میگیرند.برخی دیگر توزیع را توری در نظر میگیرند.[۱۸]اکثر روشها در نظر میگیرند که تعداد گره هایی که در یک ناحیه به کار گرفته شده اند از تعداد مورد نیاز برای انجام کار بیشتر است و بنابراین میتوان تعدادی از آنهارا خاموش کرد.(حتی در برخی در نظر گرفته میشود که مرتبه بزرگی تعداد گره های بکار رفته یک مرتبه بیشتر ازتعداد مورد نیاز است.)این چگالی ، بالا در نظر گرفته میشود.

مدلهای کشف: اکثر روش های مورد بحث در نظر میگیرند که در صورتیکه شئی در محدوده پوشش حسگر باشد حتما این شی کشف خواهد شد. به بیانی دیگر کشف شی قطعی میباشد.در مواردی برای کشف شئ احتمالاتی در نظر گرفته شده است که در آن احتمال کشف تابعی از فاصله حسگر از شئ میباشد.

محدوده حسگر: محدوده حسگر معمولا یک ناحیه دایره ای و یا یک کره سه بعدی به مرکزیت حسگر میباشد.به علاوه معمولا محدوده حسگرها مساوی در نظر گرفته میشود.برخی از روش های ارائه شده قابل کاربرد در هرگونه ناحیه محدب و غیر یکنواخت(ولی قطعی) قابل استفاده هستند.[۳۹]

دامنه ارسال^[۱۴]: روش های گوناگونی در نظر میگیرند که حسگر قادر است با تغییر قدرت ارسال رادیویی خود به دامنه های ارسال متفاوتی دست پیدا کند [۲۵][۴۲].برخی از انواع گره ها مانندMICA2 درجات مختلفی از دامنه های ارسال را فراهم میکنند[۴۳].

همزمان سازی: بسیاری از روشها فرض میکنند که گره ها همزمان شده اند تا با یکدیگر بیدار شده و دور جدیدی از زمانبندی را شروع کنند .روش های گوناگونی برای همزمان سازی گره های حسگر ارائه شده است[۳۶][۳۷].

مدلهای خرابی^[۱۵]: چگونگی خرابی گره ها فرض مهمی هم درباره گره ها و هم درباره محیطی که گره ها در آن بکار رفته اند ،میباشد. تمامی روشها در نظر میگیرند که هنگامیکه انرژی یک گره به اتمام میرسدآن گره خراب شده است. برخی روش های دیگر در نظر میگیرند که ممکن است گره ها پیش از آنکه انرژیشان به اتمام برسد خراب شوند .به عنوان مثال ممکن است حسگرها توسط تانکها در یک منطقه نظامی نابود شوند[۲۵].

پویایی حسگرها: در اکثر روشها در نظر گرفته میشود که حسگرها جابجایی ندارند ویا اینکه بطور مستقیم فرضی بیان نمیشود.در واقع اکثر مقالات به این بحث میپردازند که حسگرها در محیط واقعی جابجایی ندارند و یا جابجایی بسیار کمی دارند[۲۱].

اطلاعات مکانی: برخی از روشها در نظر میگیرند که حسگرها قادر هستند مکان جغرافیایی خودرا تعیین کنند.معمولا اطلاعات جغرافیایی برای تعیین اینکه چه مقدار از ناحیه تحت پوشش حسگر با همسایگانش همپوشانی دارد به کار میرود .اگر مکان به کار گیری حسگر ازقبل مشخص بوده و حسگر جابجایی نداشته باشد میتوان این اطلاعات را پیش از به کار اندازی درون حسگر برنامه ریزی کرد.درغیر اینصورت لازم است که گره ها به دستگاه موقعیت یاب جهانی مجهز باشند و یا یک الگوریتم مسیریابی را اجرا کنند[۴۴].

۱۰-اطلاعات فاصله: برخی از مقالات فرض میکنند که در یک ساختار خوشه ای گره ها قادر هستند که فاصله خود را از سرشاخه خود تعیین کنند .اطلاعات فاصله را میتوان از اطلاعات مکان گره ها استخراج نمود(ولی عکس این عمل ممکن نمیباشد.)به علاوه ممکن است بتوان فاصله را از قدرت سیگنال تخمین زد[۴۲].

۱-۶-۲ اهداف طراحی^[۱۶]

کاربردهای مختلف دارای نیاز مندیهای متفاوتی هستند، بنابراین شبکه های حسگر ممکن است در اهداف طراحی متفاوت باشند ویا اینکه اولویت اهداف آنها با یکدیگر فرق کند. بیشینه کردن طول عمر شبکه مسلما یکی از مهمترین اهداف طراحی در همه شبکه های حسگر است که قرار است برای مدت طولانی کار کنند. از سوی دیگر شبکه های حسگر برای انجام وظیفه ای مشخص مانند حس کردن محیط و انتقال داده به کار میروند بنابراین یک یا چند هدف کیفیت سرویس^[۱۷] مانند حفظ پوشش محیط ، نیز به همراه کمینه کردن مصرف انرژی در نظر گرفته میشوند.به علاوه طراحی ممکن است تعدادی هدف لایه بالا^[۱۸] ماننداستحکام^[۱۹]، مقیاس پذیری^[۲۰] و یا سادگی^[۲۱] داشته باشد. دستیابی به یک هدف ممکن است برروی یک هدف دیگر تاثیر بگذارد .بنابراین لازم است که رابطه بین این اهداف مورد مطالعه قرار بگیرد.

بیشینه کردن عمر شبکه: عمر شبکه بصورتهای مختلفی تعریف شده است و هر روش کارا در مصرف انرژی نوع خاصی از عمر شبکه رابیشینه میکند.[۲۱][۳۱] [۴۲] [۴۵] در ساده ترین حالت ،شبکه زنده در نظر گرفته میشود در صورتیکه یکی از حسگرها زنده باشند. عمر شبکه ممکن است بدین صورت تعریف شود که تازمانیکه درصد گره های فعال در یک شبکه از یک آستانه پایینتر است (مثلا۹۰%) شبکه زنده است. نوع دیگری از تعریف عمر شبکه به این صورت است که یک معیار کیفیت سرویس در نظر گرفته شود. به عنوان مثال تا زمانیکه پوشش ناحیه (یا اتصال،در صد انتقال داده و…) از یک حد بالاتر است شبکه فعال تعریف میشود.

پوشش حسگرها: از آنجا که حس کردن محیط وظیفه اصلی شبکه حسگر است فراهم آوردن پوشش برروی ناحیه مورد نظر یک معیار کیفیت مهم است.اگر تمامی نقاط در ناحیه مورد نظر تحت پوشش شبکه باشند گفته میشودکه شبکه پوشش۱- لایه ای^[۲۲] دارد .در صورتیکه هر نقطه حداقل توسط k حسگر پوشانده شود به آن پوشش –Kلایه ای^[۲۳] گفته میشود(پوشش ۱-لایه ای نوع خاصی از پوشش –Kلایه ای است.) یک شبکه حسگر همچنین ممکن است که پوشش ۱- لایه ای یا –K لایه ای جزئی^[۲۴] داشته باشد.گاهی ارائه تضمین قطعی با پیش فرضهای داده شده ممکن نمیباشد بنابراین برخی روشها ، پوشش حدی هنگامیکه تعدادگره ها به سمت بی نهایت میرود ارائه میکنند[۲۵] [۱۸].

اتصال شبکه:در صورتیکه داده های حسی^[۲۵] نیاز داشته باشند تا با چند گام^[۲۶] به ایستگاه پایه برسند حفظ اتصال بین گره ها اهمیت بسیاری پیدا میکند .برخی از روشها حتی سعی میکنند که شبکه را طوری پیکربندی کنند که درجه ای از اتصال^[۲۷] که مورد نیاز کاربرد است رافراهم کنند.مشابه پوشش حسگرها، اتصال آنها هم میتواند حدی در نظر گرفته شودبه این صورت که هنگامیکه تعدادگره ها به سمت بی نهایت حرکت کند شبکه حتما متصل خواهد بود.[۲۳]

نرخ انتقال داده:بالابودن نرخ انتقال داده معیار کیفیت سرویس دیگری برای برخی از کاربردها میباشد.این مقدار میتواند بصورت درصد داده های انتقال داده شده از یک منبع به یک مقصد تعریف شود.این معیار هنگامیکه درون شبکه تجمیع صورت میگیرد مناسب نیست.

کیفیت پایش^[۲۸]:یک معیار ارائه شده برای کیفیت پایش در شبکه های حسگر طراحی شده ویژه ردگیری اهداف بصورت میانگین فاصله ای که یک هدف طی میکند پیش از اینکه توسط شبکه کشف شود ، تعریف میشود.به این صورت شبکه ای که بتواند در مدت زمان و فاصله کوتاهتری هدف را شناسایی کند دارای کیفیت پایش بهتری میباشد.کیفیت پایش تنها به پوشش گره ها بستگی ندارد بلکه به چینش جغرافیایی آنها نیز بستگی پیدا میکند.درصورتیکه شبکه در برخی از نقاط خوشه بندی شده باشد ممکن است که هدف فاصله زیادی را طی کند پیش از اینکه کشف شود.بنابراین ممکن است فاصله ای که هدف پیش از کشف شدن طی میکند بیشتر از شبکه حسگری با پوشش مشابه ولی خوشه بندی نشده و دارای توزیع یکنواخت تر باشد.

نهانکاری: برخی از کاربردها در شبکه های حسگر نیاز دارند که کار آنها قابل کشف نباشندویا احتمال کشف آنها بسیار پایین باشد.نهانکاری از طریق کاهش تعداد پیامهای کنترلی ممکن میباشد.پایین آوردن مدت زمان ارسال نیز به نهانکاری کمک میکند در صورتیکه گره ها تنها در دوره های خاص اجازه ارسال داشته باشند.[۴۵]

مصرف انرژی متعادل: برخی از روشها سعی میکنند که مصرف انرژی بین گره ها را متعادل کنند.یک استدلال رایج برای این کار این است که اگر انرژی برخی از گره ها زودتر از بقیه به اتمام برسد پوشش شبکه و یا اتصال آن ممکن است پیش از موعد از بین برود.یک استدلال مخالف به چگالی بالای گره تکیه میکند و میگوید که حتی اگر برخی از گره ها از بین بروند گره های جایگزین آنها موجود خواهد بود.

مقیاس پذیری:یک تعریف همه گیر برای مقیاس پذیری ارائه نشده است.ولی در اکثر شبکه های حسگر افزایش بصورت خطی ویا سریعتر هزینه محاسبات نسبت به افزایش تعداد همسایگان یک گره ناخوشایند است.از سوی دیگر اگر هر گره تنها وضعیت همسایگان فعال خود را نگهداری کند از آنجا که تعداد این گره ها کم است الگوریتم همچنان مقیاس پذیر در نظر گرفته میشود.

استحکا^[۲۹]م:استحکام ،توانایی شبکه در تحمل خرابی های پیش بینی نشده است.به عنوان مثال حسگرهای یک شبکه ممکن است توسط تانک ها یا بمب ها پیش از اتمام باتری آنها خراب شوند.یک روش مستحکم نمیتواند انتظار داشته باشدکه همه گره های خواب شبکه بیدار شوند.زیرا ممکن است تعدادی از این گره ها در مدت زمان خواب خود از کار افتاده باشند.بدیهی است که پیش فرضهای طراحان تا حد زیادی تعیین کننده استحکام برنامه میباشد.

سادگی:حسگرهای فعلی دارای حافظه محدودی برای ذخیره کردن برنامه ها هستند.مثلاMICA2 تنها ۸کیلوبایت فضای حافظه برای ذخیره برنامه دارند.به علاوه حسگرها دارای قدرت محاسباتی پایین میباشندو اشکال زدایی آنها دشوار میباشد.

۱-۶-۲-۱ رابطه بین اهداف طراحی

ازآنجا که بررسی رابطه همه موارد فوق ممکن نمیباشدبرخی از روابط مهمتر بین این اهداف طراحی بررسی میشوند.

هنگامیکه دامنه ارسال گره ها حداقل دوبرابر دامنه پوشش حسگرها باشد،پوششK- لایه ای منجر به اتصال K تایی میشود.[۲۳]

بالاتر بودن درجه اتصال معمولا باعث بالارفتن استحکام شبکه دربرابر خرابی ها میشودزیرا تعداداتصالاتی که باید قطع شوند تا اتصال شبکه از بین برودافزایش می یابد.

نرخ انتقال داده معمولا با بالا رفتن درجه اتصال افزایش پیدا میکند ولی در صورتیکه این درجه بسیار بالا باشدبرخورد بین بسته های ارسالی ممکن است این رابطه را برعکس کند.

بالاتر بودن میزان نهانکاری میتواند منجر به مصرف انرژی کمتر شود درصورتیکه نهانکاری از طریق پایین آوردن پیام های کنترلی انجام شود.

۱-۶-۳ حالتهای صرفه جویی در مصرف انرژی حسگر^[۳۰]

برای فهم بهتر روش های صرفه جویی در مصرف انرژی لازم است حالتهای مختلف ذخیره انرژی که توسط حسگر فراهم میشوند را بررسی کنیم.یکی از پیچیدگی ها در اینجا متفاوت بودن پشتیبانی حسگرهای مختلف از حالتهای صرفه جویی در مصرف انرژی میباشد و حتی اگر حسگرها دارای حالات صرفه جویی مشابهی باشند واژگان بکار رفته توسط مقالات مختلف برای آنها متفاوت میباشد.حالات رایج صرفه جویی در مصرف انرژی را در این قسمت بررسی خواهیم کرد:

◄ فعال:تمامی قسمتهای حسگر فعال میباشند.حسگر قادر است که داده های حسی را جمع آوری کرده ، پیام را دریافت کند و یا بفرستد ، داده ها و پیامها را پردازش کند و سایر انواع محاسبات را انجام دهد.این حالت معمولا فعال خوانده میشود و یک حالت صرفه جویی در مصرف انرژی نیست.

◄ واحد حسی ^[۳۱]فعال: حداقل یکی از واحدهای حسی و پردازنده فعال میباشند ولی واحد گیرنده و فرستنده خاموش میباشد.در این حالت حسگر قادر است داده های حسی را جمع آوری و پردازش کند ولی قادر به فرستادن یا دریافت پیام نمیباشد.

◄ واحد فرستنده فعال: دستگاه فرستنده و پردازشگر روشن هستند ولی واحد های حسی حسگر خاموش میباشند.دراین حالت حسگر قادر است پیام بفرستد،دریافت کند و پیامها را پردازش کند ولی قادر به حس کردن محیط نیست.

◄غیرفعال: پردازشگر حسگر خاموش میباشد ولی یک تایمر و یا یک مکانیسم راه اندازی دیگر برای فعالسازی حسگر را برعهده دارد.به این حالت ، حالت خواب گفته میشود.

باید توجه داشت که برخی از حسگرها حالات مختلف غیر فعال دارند که هرکدام مکانیزم به راه اندازی متفاوتی دارند .برای مثال حسگرهایAMPSµ دارای سه حالت خواب میباشد:دیده بانی^[۳۲]،مشاهد^[۳۳]ه و خواب عمیق^[۳۴].[۴۶] در هر سه مورد پردازشگر خاموش میباشد بنابراین حسگر قادر به پردازش داده های حسی ویا پیام ها نمیباشد.درحالت دیده بانی ، هم واحد حسی و هم واحد فرستنده فعال هستندتا پیامهای فعالسازی را دریافت کنند. در حالت مشاهده ، تنها واحد حسی فعال میباشد.تفاوت آنها با واحد حسی فعال در این است که در این حالت پردازشگر نیز خاموش میباشد.در حالت خواب عمیق نه واحد حسی فعال است نه واحد فرستنده.بنابراین حسگر برای بیدار شدن به تایمر داخلی خود تکیه میکند.اکثر انواع حسگرها دارای حالتی شبیه AMPSµ میباشند که این حالت در اکثر روش های صرفه جویی در مصرف انرژی مورد استفاده قرار میگیرد.طراحانAMPSµ روشی را برای استفاده از هر سه حالت صرفه جویی ارائه داده اند.

بیشترین مقدار صرفه جویی انرژی در حالت خواب عمیق صورت میگیرد زیرا واحدهای حسگر ، پردازش وفرستنده همگی خاموش هستند.فعالیت واحد فرستنده معمولا مصرف انرژی بیشتری نسبت به واحد حسی دارد ولی مصرف انرژی دستگاه فرستنده همچنین بستگی به الگو و فرکانس ارتباط دارد.

تقریبا تمامی روشها از حالت غیر فعال استفاده میکنند.برخی از روشها از دوحالت واحد حسی و واحد فرستنده فعال نیز استفاده میکنند.گاهی اوقات تعیین اینکه حسگر در کدامیک از حالات فوق به سر میبرد دشوار است.

۱-۷ روش های زمانبندی توزیع شده در شبکه های سلسله مراتبی

در شبکه های سلسله مراتبی مانند شبکه های خوشه بندی شده^[۳۵] ، حسگرها توسط مکانیزمی در خوشه هایی محلی دسته بندی میشوند.هر خوشه دارای یک سرخوشه^[۳۶] (سرگروه) است.سرخوشه ها ممکن است حسگرهایی با توانایی بالاتر حسی ویا… نسبت به سایر گره ها باشند یا نباشند.سرخوشه ها وظیفه ارتباط گره های درون خوشه خود با ایستگاه پایه را به عهده دارند.ارتباط سرخوشه ها با ایستگاه پایه ممکن است چندگامه و از طریق سرخوشه های دیگر باشد.در این قسمت به روش های زمانبندی بر پایه خوشه بندی میپردازیم:

در[۵۱] روش ^[۳۷]LEACH(خوشه بندی سلسله مراتبی انطباقی کم مصرف) برای خوشه بندی گره ها در شبکه های حسگر ارائه شده است. در این روش به صورت تصادفی نقش سرخوشه بین گره های مختلف تقسیم میگردد تا مصرف انرژی به صورت یکنواخت بین گره های مختلف تقسیم شود.درLEACH فعالیتها به دوره هایی تقسیم میشوند.از آنجایی که سرخوشه وظایف بیشتری به عهده دارد در هر دوره سرخوشه عوض میشود تا از خالی شدن سریع باتری سرخوشه ها جلوگیری شود.سر خوشه ها بصورت خود بر گزیده تعیین میشوند.برای صرفه جویی در مصرف انرژی حسگرهای غیر سرخوشه همگی مگر در هنگام فرستادن داده خاموش میشوند.

در مقاله ژورنال LEACH دو مورد بهبود داده شده است:

الگوریتم بهتری برای انتخاب سرخوشه ها ارائه شده است.

تعداد بهینه خوشه ها در شبکه تعیین شده است.

به این روشE-LEACH^[38] گفته میشود.

در[۵۲]و[۵۳] یک روش ساده برای انتخاب سرخوشه ها ارائه شده است.در این روش سرخوشه ها با احتمال P انتخاب میشوند. در این روش دونوع سرخوشه وجود دارد.سرخوشه های داوطلب و سرخوشه های اجباری. هرگره با احتمال P به صورت یک سرخوشه داوطلب درمی آید. این گره سپس این موضوع را با پیامی اعلان میکند که این اعلان تاKگام پیش میرود.هر گره غیر سر خوشه ای که این پیام را میشنود به صورت جزئی از این خوشه قرار می گیرد.هرگاه حسگری بعد از طی t دوره زمانی به عضویت هیچ

گروهی در نیامد به صورت اجباری به عنوان سرگروه تعیین می شود.در [۵۲]و [۵۳] مقدار بهینه احتمالP برای کمینه سازی مصرف انرژی در یک شبکه سلسله مراتبی h- لایه ای تعیین شده است.

در[۴۵] یک روش دیده بانی کم مصرف(ESS^[39]) که کارایی دیده بانی را در برابر مصرف انرژی با تنظیم حساسیت سیستم،دادوستد می کند. در این روش گره ها به صورت پویا به دو دسته نگهبان^[۴۰] و غیر نگهبان تقسیم می شوند.نگهبان ها مشابه سرخوشه ها به صورت محلی توسط حسگرها انتخاب می شوند.یک حسگر در صورتیکه ببیند که هیچ یک از همسایگانش به عنوان نگهبان تعیین نشده اند ،خود را به عنوان نگهبان انتخاب میکند و قصد خود را به همسایگانش اطلاع می دهد.یک تاخیر با مدت زمان تصادفی برای جلوگیری از برخورد اعلان ها هنگامی که تعدادی همسایه همزمان تصمیم می گیرند که نگهبان شوند استفاده می شود.گره های غیر نگهبان به صورت متناوب از حالت بیدار به حالت خاموش می روند و بالعکس.دو روش مختلف پیش فعال^[۴۱] و واکنشی برای تعین دوره های خواب و بیدار ارائه شده اند.

در[۴۲] یک روش زمانبندی خواب گره ها به نام زمانبندی فاصله خطی(LDS^[42]) برای شبکه های سلسله مراتبی خوشه بندی شده با چگالی بالا ارائه شده است.هدف،کاهش مصرف انرژی در عین حفظ پوشش کافی است. برای دستیابی به این هدف گره هایی که در فاصله بیشتری از سرخوشه قراردارند با احتمال بالاتری به خواب می روند.منطق این کار بر این نکته استوار است که گره ها قادرهستند در گامهایی دامنه ارسال خود را تغییر دهند و از آنجاکه برای ارسال به نقاط دورترانرژی بیشتری نیاز است،گره های دور از سرخوشه بیشتر به خواب می روندتا هزینه بالای ارسال آنها به سرخوشه جبران گردد.در این روش ساختار خوشه ها ایستا است و هنگامیکه سرخوشه ها انتخاب شوند دیگر تغییر نمیکنند.

در[۵۴] نویسندگان به گسترش روشLDS پرداخته اند و روش زمانبندی با مصرف انرژی متوازن(BS) را ارائه کرده اند. در این روش با توزیع متوازن وظایف فرستادن و حس کردن بین گره های غیرسرخوشه تلاش شده است که مصرف انرژی گره ها مستقل از فاصله آنها از سرخوشه باشد.نویسندگان یک تابع بااحتمال به خواب رفتن p(x) به دست آورده اندکه در آن مصرف انرژی گره مستقل از x یعنی فاصله آن از سرخوشه می باشد.

۱-۸روشهای زمانبندی توزیع شده در شبکه های غیر سلسله مراتبی

دراین بخش برخی از روش های زمانبندی راکه قابل استفاده در شبکه های غیر سلسله مراتبی میباشند بررسی میکنیم.

در [۱۸]روش زمانبندی تصادفی مستقل (^[۴۳]RIS) برای افزایش طول عمر شبکه در عین دستیابی به پوشش

-kلایه ای ارائه شده است.درRIS زمان به دوره هایی تقسیم میشود .در ابتدای هردوره هر گره تصمیم میگیرد که در ادامه دوره به احتمال P فعال باشدو یا با احتمال ۱-P به خواب برود. طول عمر شبکه در این روش تقریبا به اندازه۱/p افزایش پیدا میکند.به علاوه برای پوشش –Kلایه ای حدی بااستفاده ازRIS برای سه نوع توزیع (توری،یکپارچه تصادفی و پواسون) شروط لازم محاسبه گردیده اند.

در[۳۰] یک روش توزیع شده برای زمانبندی در عین حفظ پوشش ارائه کرده اند.برای جلوگیری از کاهش پوشش شبکه یک گره تنها زمانی اجازه خاموش شدن پیدا میکند که تمامی ناحیه مربوط به آن توسط حسگرهای همسایه پوشانده شده باشند.به حسگرهای همسایه پشتیبانهای خاموشی^[۴۴] گفته میشود و ناحیه ای که هر حسگر میپوشاند بخش تحت پوشش^[۴۵] نامیده میشود.هر حسگر از اطلاعات جغرافیایی همسایگانش و دامنه حسی آنها برای تعیین بخشهای تحت پوشش استفاده میکند.اگر ۳۶۰درجه اطراف حسگر توسط همسایگان پوشانده شود گره واجد شرایط غیرفعال میشود. به این روش ، روش بخش تحت پوشش گفته میشود.

در[۴۷] مسئله زمانبندی حسگرها به صورت یک مسئله بیشینه سازی با شرطهایی بر روی عمر باتری و پوشش حسگرها حل میشود.

در این مقاله یک روش متمرکز و یک روش توزیع شده برای حداکثرسازی عمر شبکه در عین دستیابی به پوشش –kلایه ای ارائه شده است. در این روش دستیابی به یک درجه مشخص از پوشش ممکن است (در صورت کافی بودن چگالی) در حالیکه در روش بخش تحت پوشش که پیش ازاین مورد بحث قرارگرفت درجه پوشش فعلی شبکه حفظ میشود.در این روش هرحسگردر یکی از حالات زیر به سر میبرد:استراحت، بیدار ، آسیب پذیر^[۴۶].در حالت آسیب پذیر اگر حسگر به این نتیجه برسد که بخشی از ناحیه تحت پوشش آن دیگر توسط همسایه ها پوشش داده نمیشود ، بلافاصله به حالت بیدار وارد میشود.در صورتیکه ناحیه تحت پوشش آن توسط همسایگان بیدار پوشش داده شود و یا اینکه حسگر های دیگر همسایه های دارای سطح انرژی بالاتری موجودند که قادر به پوشش آن ناحیه هستند ، حسگر به حالت استراحت میرود.

در[۲۱] یک روش توزیع شده زمانبندی به نام LDAS^[47]ارائه شده است.در این روش بر خلاف روشهایی که پیش ازاین مورد اشاره قرارگرفت فرض براین است که حسگرها دارای دستگاه موقعیت یاب جهانی نیستند و به اطلاعات مکانی دسترسی ندارند.از آنجا که تعیین اینکه آیا محدوده حسگر توسط همسایگان آن پوشانده میشود یا نه در شرایطی که اطلاعات مکانی همسایگان در دسترس نیست بسیار مشکل و شاید غیر ممکن میباشد هدف به صورت دادن تضمینهای آماری برای پوشش حسگرها تغییر میکند. LDAS فرض میکند که هر گره روشی برای تعیین تعدادگره های فعال در همسایگیخوددارد.هنگامیکه تعداد این همسایگان از یک آستانه تعیین شده توسط برنامه عبور کند ،گره بصورت تصادفی برخی از همسایگان خود را برای خاموش کردن انتخاب کرده و برای آنها بلیت هایی را ارسال میکند.هنگامیکه یک گره به تعداد کافی از همسایگان خود بلیت دریافت کند میتواند به حالت غیرفعال بعد از یک دوره با طول تصادفی وارد شود.

در[۲۵] روشی به نام PEAS^[48](جستجوی محیط و حس کردن انطباقی) که میتواند عمر شبکه را در شبکه های با چگالی بالا در محیطهای ناملایم افزایش دهد ، ارائه شده است. نکته ای که این روش را از سایر روشها جدامیکند فرضهای آن است.فرض اول این است که خرابی گره ها رایج و غیر منتظره است ، که روش های به خواب رفتن همزمان را غیر ممکن میسازد زیرا این روشها به قابل پیش بینی بودن طول عمر گره ها تکیه میکنند. فرض دوم این است که تعداد گره های حسگر حداقل یک مرتبه بزرگی بیشتر از تعدادحسگرهای فعال در شبکه است.بنابراین نگهداری حالات فعالیت همسایه ها برای هرگره غیر ممکن است.فرض آخر اینکه گره ها دسترسی به اطلاعات مکانی ندارند.طبق ادعای نویسندگان این فرضها به یک طراحی مستحکم در برابر خرابیها و ساده تر برای پیاده سازی واقعی می انجامد.PEAS مصرف انرژی را از طریق جداکردن حسگرهای فعال با فاصلهc از یکدیگر کاهش میدهد.برای پیدا کردن گره های فعال در اطراف، هر گره یک پیام جستجو با دامنه ارسال c بعد از خوابیدن برای یک مدت زمان تصادفی ارسال میکند . یک گره تنها در صورتیکه هیچ پیامی از گره های فعال اطراف دریافت نکند به حالت فعال میرود درغیر اینصورت خاموش باقی میماند.در همین مقاله نویسندگان همچنین اثبات میکنند که برای برقراری اتصال در شبکه بصورت حدی کافیست که دو شرط برای چگالی و شعاع جستجوبرقرار باشد.

در[۴۸] نویسندگان ثابت میکنند که پوشش ۱-لایه ای هنگامیکه دامنه ارسال حداقل دوبرابر دامنه حسی باشد منجر به اتصال۱- درجه ای میشود.بافرض اینکه این شرط برقرار شود نویسندگان یک روش توز یع شده به نام بهینه کنترل چگالی مکانی (OGDC^[49]) برای بیشینه سازی گره های خواب در عین تامین پوشش ۱-لایه ای و اتصال ۱- درجه ای ارائه کرده اند.OGDC تلاش میکند که ناحیه مشترک بین حسگرهای فعال راکمینه کند.یک حسگر تنها در صورتی فعال میشودکه ناحیه مشترک بین چند حسگر فعال را کمینه کندو یک ناحیه مشترک دوحسگرفعال را پوشش دهد.یک حسگر میتواند بااستفاده از اطلاعات مکانی خود و همسایگانش این شرطها را بررسی کند.این روش بسیار به روش بخش تحت پوشش شبیه است با این تفاوت که شرط های لازم برای خاموش شدن گره ها تفاوت میکند.روش بخشهای تحت پوشش محافظه کارانه تر است.

در[۲۳] یک روش یکپارچه برای فراهم آوردن پوشش و اتصال در شبکه به نامCCP^[50] ارائه کرده اند.در این روش تلاش برحداکثر کردن تعدادگره های خواب در عین حفظ کردن پوششK- لایه ای و اتصالK– درجه ای میباشد.توانایی CCP در این نکته نهفته است که پوششK–لایه ای در صورتی که دامنه ارسال آن دوبرابر دامنه حسی آن باشد خود به خود باعث اتصال K درجه ای میشود.برای اطمینان از پوشش K لایه ای لازم است که گره بررسی کندکه نقاط اشتراک ناحیه آن با سایر گره ها دارای پوششK– لایه ای است.

در[۴۹] از اندازه گیریهای محلی برای پیکربندی شبکه در شبکه های با چگالی بالا استفاده شده است.هدف خاموشی تعدادی از گره ها در عین اطمینان از دستیابی به نرخ انتقال داده مورد نظر است.برای دستیابی به این هدف لازم است که شبکه دارای درجه خاصی از اتصال باشد.درجه ای که نه آنقدر پایین است که امکان انتقال داده با نرخ مورد نظر موجود نیست ونه آنقدر زیاد که برخورد بین بسته های ارسالی همسایه ها بسیار بالا برود.این روش که توسط ASCENT اتخاذ شده است بر این پایه است که گره اتصال خود و مقدار از دست دادن داده را می سنجند و بر پایه این اندازه گیری های محلی گره های همسایه خود را فعال میکنند.

در[۵۰] روش PECAS ارائه شده است که تعمیمی بر روی روشPEAS میباشد.این روش دارای مکانیزمی شبیه بهPEAS برای حس کردن محیط میباشد ولی به گره های فعال اجازه نمیدهد که بصورتنامحدود فعال باقی بمانند.با توجه به اینکه اتمام انرژی برخی از گره ها میتواند به تکه تکه شدن شبکه منجر شود هدف در این روش توزیع بار بین گره های مختلف میباشد.

بنابراین گره های فعال درPECASپس از مدتی فعالیت دوباره به حالت خواب وارد میشوند.این گره ها همچنین در پاسخهای خود به همسایگان مدت زمان باقیمانده از فعالیت خود را به این گره ها اعلام میکنند و بدین ترتیب یک گره همسایه که قصد به خواب رفتن را دارد میتواند برنامه ریزی کند که پیش از به خواب رفتن این گره دوباره بیدار شود و در نتیجه از پدید آمدن نقاط کور در شبکه خودداری شود.

۱-۹ دسته بندی روشها

باتوجه به مطالعاتی که مورد اشاره قرارگرفت معیارهای گوناگونی را میتوان برای دسته بندی روش های گوناگون در نظر گرفت.بنابراین در این قسمت انتخاب هایی که توسط روش های گوناگون انجام گرفته است را جمع بندی میکنیم.استخراج پیش فرض های روشها کار چندان ساده ای نیست زیرا معمولا فرض های مهم به خوبی توسط مقالات مورد بررسی قرار میگیرنددر حالیکه سایر پیش فرض ها مورد اشاره قرار نمیگیرند و نیاز به حدس زدن آنها داریم.بنابراین اهداف سطح بالاهمچون سادگی،استحکام و مقیاس پذیری که تعیین کمیت آنها دشوارند را در نظر نمیگیریم.

یک روش در صورتی دارای نهانکاری است که دارای یکی از دوشرط زیر باشد:

برای زمانبندی گره نیاز به ارسال پیام نداشته باشد.برای مثال در روش RIS هر گره با بهره گرفتن از یک احتمال از پیش تعیین شده به خواب می رود.

فعالیت به دوره هایی تقسیم شده است و ارتباط میان گره ها تنها در ابتدای دوره لازم است.

به علاوه یک روش تنها در صورتی مصرف انرژی متوازن دارد که حسگرها به نوبت خاموش و روشن شوند.

دراینجا دسته بندی روشها بر اساس پیش فرضها آمده است:

جدول۱-۱:دسته بندی روشها بر اساس پیش فرضها

Assumptions

Scheme

Known Distance

Known Location

Mobility

Frequent Failures

Time Synch.

Adjustable Transmission Range

Uniform Sensing Range

Sensing Area

Deterministic Detection

Sensor Density

Sensor Placement

Network Structure

No

No

No

No

Yes

No

Yes

۲-D Disk

Yes

Normal, High

Grid,Uniform,Poisson

Flat

RIS (Kumar)

No

Yes

No

No

Yes

No

Yes

۲-D Disk

Yes

Normal, High

Any

Flat

Sponsored Sector

No

Yes

No

No

No

No

No

۲-D Conyex

Yes

Normal, High

Any

Flat

MSNL

No

No

No

No

No

No

Yes

۲-D Disk

Yes

Normal, High

Uniform

Flat

LDAS

No

No

No

Yes

No

Yes

Any

Any

Yes

High

Uniform

Flat

PEAS

No

Yes

No

No

Yes

No

Yes

۲-D Disk

Yes

Normal, High

Any

Flat

OGDC

No

Yes

No

No

No

No

Yes

۲-D Disk

Yes

Normal, High

Any

Flat

CCP

No

No

No

No

No

No

Any

Any

Yes

,High

Any

Flat

ASCENT

No

No

No

Yes

No

Yes

Any

Any

Yes

Normal, High

Uniform

Flat

PECAS

No

No

No

No

Yea

No

Any

Any

Yes

Normal, High

Any

Hierarchical

LEACH

No

No

No

No

Yes

No

Any

Any

Yes

Normal, High

Any

Hierarchical

E-LEACH

No

No

No

No

Yes

No

Yes

۲-D Disk

Yes

Normal, High

Poisson

Hierarchical

Bandyo etal.

No

No

No

No

Yes

No

Any

Any

Yes

Normal, High

Any

Hierarchical

ESS

Yes

No

No

No

Yes

Yes

Yes

۲-D Disk

Yes

Normal, High

Poisson

Hierarchical

LDS

Yes

No

No

No

Yes

Yes

Yes

۲-D Disk

Yes

Normal

Poisson

Hierarchical

BS

دسته بندی روشها بر اساس اهداف آنها درذیل آمده است:

Objectives					Scheme
Balaned Energy Consumption	Stealthiest	Data Delivery Ratio	Network Connectivity Guarantee	Sensing Coverage Gratee
Yes	Yes			Full,k,Asymptotic	RIS (Kumar)
Yes	Yes			Full,Original,Hard	Sponsored Sector
Yes				Full,K,Hard	MSNL
Yes				Partial,l,Statistical	LDAS
			l,Hard		PEAS
Yes	Yes		l,Hard	Full,l,Hard	OGDC
Yes			K,Hard	Full,K,Hard	CCP
		Yes			ASCENT
Yes			l,Hard		PECAS
Yes	Yes				LEACH
Yes	Yes				E-LEACH
	Yes				Bandyo etal.
Yes	Yes				ESS
					LDS
Yes					BS

چنانکه مشاهده شد، زمانبندی گره ها در لایه های مختلف تعریف و استفاده می شود و در صورتیکه گره های حسگر دارای قابلیت‌های مورد نیاز باشند(امکان فعال و غیر فعال کردن قسمتهای مختلف گره مستقل از سایر قسمتها) هرجزء می تواند به صورت جداگانه و بنا به نیاز برنامه ها و کاربردها زمانبندی شوند.روش زمانبندی میتواند متمرکز یا توزیع شده باشد و به صورتهایی که در بالا مورد بحث قرار گرفت دسته بندی شوند.

فصل دوم:مسیر یابی در شبکه های حسگر

مقدمه

پیشرفت ها در تکنولوژی حسگرها سبب تولید حسگرهای بی سیم با توانایی حس کردن و گزارش پدیده های متفاوت شده است . اما این سیستم ها با پهنای باند، انرژی و محدودیت های عملکردی که سبب تعیین میزان اطلاعات ارسالی می شود ، دست و پنجه نرم می کند . مسیریابی داده یک تکنیک شناخته شده برای کم کردن این مسائل است . اما بعضی از این محدودیت ها به سبب نبودن تطبیق با همبندی شبکه دینامیک و الگوهای ترافیکی پیش بینی نشده ، وجود دارد . مهمترین محدودیت ها در شبکه های حسگر بی سیم ، توان ، قدرت ذخیره سازی و پردازش می باشد.

تکنیک های مسیریابی در شبکه های حسگر به صورت گسترده در مقالات علمی مورد توجه قرار گرفته است . در این فصل یک مطالعه مجمل روی الگوریتم های مسیریابی و پارامترهای ایمن سازی مربوط انجام می شود.

با توجه به تفاوت های عمده بین شبکه های حسگر بی سیم با شبکه های امروزی و همچنین شبکه های MANET ، مسیریابی در این شبکه ها توجه بسیاری را به خود جلب کرده است. این تفاوت ها به قرار زیر است :

امکان ایجاد یک مبنای آدرس دهی کلی در این شبکه ها وجود ندارند. بنابراین پروتکل هایی مثل پروتکل اینترنت ( IP ) در این شبکه ها کاربرد ندارند.

تقریبا در تمامی کاربرد های شبکه های حسگر بی سیم نیاز به این امر می باشد که داده ها از نواحی مختلف به سمت یک ایستگاه پایه مشخص جریان پیدا کند( بر خلاف دیگر شبکه های مخابراتی )

با توجه به اینکه حسگرهایی که در نزدیکی پدیده مورد نظر برای اندازه گیری قرار دارند با احتمال زیاد یک نوع داده تولید می کنند ، بنابراین تعداد داده های تکراری در این شبکه ها زیاد است.

این حسگرها از نظر قدرت در ارسال داده ، انرژی ، قدرت پردازش اطلاعات و حافظه محدودیت دارند ، پس پروتکل های مسیر یابی باید یک مدیریت بسیار دقیق روی این منابع داشته باشند.

با توجه به اختلافات ذکر شده ، تعداد زیادی الگوریتم جدید برای حل مشکل مسیریابی برای شبکه های حسگر بی سیم ، پیشنهاد شده است. در طراحی این مکانیزم های مسیریابی ، علاوه بر مشخصات خاص حسگرها برای آن شبکه ، کاربرد شبکه و همچنین نیازمندی های ساختار آن نیز در نظر گرفته شده است.

۲-۱:تقسیم بندی پروتکلهای مسیریابی

تقریبا تمامی پروتکل های مسیریابی برای این شبکه ها را می توان به گروه های زیر تقسیم بندی کرد

پروتکل های با محوریت داده^[۵۱]: در بسیاری از کاربردهای شبکه های حسگر بی سیم ، تخصیص یک شناسه کلی برای هر حسگر در شبکه امکان پذیر نیست .عدم وجود این شناسه همراه با جایگذاری تصادفی حسگرها در شبکه باعث می شود تا درخواست اطلاعات از یک گروه مشخص از حسگرها کمی مشکل شود. بنابراین داده ها با تکرار زیاد به سمت ناحیه ی مورد نظر جاری می شوند . برای جلوگیری از مصرف بیهوده توان از روشهایی مانند ترکیب داده ها استفاده می شود. این مساله باعث می شود که مسیریابی در این شبکه ها ، به جای بر مبنای آدرس^[۵۲]، بر مبنای داده (Data-Centric) باشد.

در پروتکل های Data-Centric ، ایستگاه پایه درخواست های خود را به مناطق مورد نظر خود می فرستد و منتظر می شود تا داده ها از حسگرهایی که در آن ناحیه قرار دارند ، باز گردند. بنابراین در این روش مشخصات یک حسگر مهمتر از آدرس آن می باشد. این مشخصات شامل مکان ، پارامترهایی که می تواند اندازه بگیرد و … می باشند.

پروتکل های سلسله مراتبی^[۵۳]: در این پروتکل ها ، شبکه به زیر بخش هایی مختلف به نام خوشه تقسیم می شود که در هر یک از خوشه ها ، سرپرست آن خوشه ( CH ) وظایفی را از جمله ترکیب داده ها^[۵۴]و حذف داده های تکراری به عهده می گیرد.

پروتکل های مبتنی بر مکان^[۵۵]: اکثر پروتکل های مسیریابی برای شبکه های حسگر بی سیم ، به اطلاعات مکانی حسگرها نیاز دارند. در اکثر موارد این اطلاعات برای محاسبه فاصله بین حسگرها به منظور تخمین مقدار انرژی مورد نیاز برای ارسال داده ها به کار گرفته می شوند. با توجه به اینکه هیچ شمای آدرس دهی اساسی مثل IP در شبکه های حسگر بی سیم وجود ندارد ، اطلاعات جغرافیایی می تواند کمک بسیار مفیدی برای استفاده کارآمد از انرژی باشد. برخی از پروتکل های این دسته در ابتدا برای شبکه های adhoc طراحی شده اند ولی با این وجود در شبکه های حسگر بی سیم نیز کاربرد دارند. برخی از پروتکل هایی که برای شبکه های adhoc طراحی شده اند ، برای شبکه های حسگر بی سیم مناسب نیستند ، زیرا در طراحی آنها انرژی حسگرها مورد توجه قرار نگرفته است

در پروتکل های بر مبنای جریان شبکه ، مسیریابی و تعیین مسیرها به عنوان یک مساله جریان شبکه مطرح می شود و این مساله توسط روش های فعلی برای آن ، حل می شود. در پروتکل های بر مبنای Qos تاخیر ارسال داده به عنوان مساله اصلی مطرح می شود

در زیر چند پارامتر که برای پروتکل های مسیریابی در شبکه های حسگر بی سیم مورد نظر قرار می گیرند ، مطرح شده اند :

۲-۲ پارامترهای موردنظر در پروتکل های مسیر یابی

۲-۲-۱دینامیک شبکه

اکثرا حسگرها در شبکه های حسگر بی سیم ثابت هستند. فقط بعضی از شبکه ها وجود دارند که در آن برخی از حسگرها متحرک هستند. در حضور حسگرهای متحرک ، مساله پایداری مسیرها امر بسیار مهمی است. از طرفی خود پارامتر در حال اندازه گیری ، می تواند حالت استاتیک و یا دینامیک داشته باشد. مثلا در یک کاربرد تعقیب و تشخیص هدف ، شبکه حالت دینامیک به خود می گیرد، در صورتی که مثلا برای تشخیص آتش در یک جنگل دیگر اینطور نیست و شبکه حالت ثابت دارد. در حالت دینامیک ، داده ها از حسگرها به صورت متناوب به ایستگاه پایه فرستاده می شوند در صورتی که در حالت ثابت هر وقت پدیده ای رخ می دهد به ایستگاه پایه گزارش می شود.

۲-۲-۲جایگذاری حسگرها در شبکه

با توجه به کاربردهای مختلف ، جایگذاری حسگرها در شبکه های مختلف با یکدیگر متفاوت می باشند که این امر می تواند در کارایی کل شبکه تاثیر مستقیم بگذارد. در برخی از کاربردها ، مکان حسگرها از قبل تعیین شده است اما در اکثر شبکه های حسگر بی سیم به این صورت نیست.

در شبکه هایی که مکان حسگرها از قبل معین شده ، اطلاعات نیز از طریق مسیرهای از قبل تعیین شده ارسال می شوند. اما در شبکه هایی که مکان از قبل مشخص نشده باید حسگرها به صورت خودکار مسیریابی را انجام دهند. معمولا شبکه ها به این صورت هستند و برای این شبکه ها ایجاد زیر ساخت مناسب در کارایی سیستم تاثیر بسزایی دارد.

۲-۲-۳محدودیت انرژی

در طی مراحل طراحی زیر ساخت شبکه ، ایجاد مسیرها شدیدا تحت تاثیر محدودیت انرژی حسگرها قرار می گیرد. با توجه به اینکه توان ارسال به صورت بی سیم با توان دوم ( و بالاتر ) مسافت رابطه مستقیم دارد، استفاده از روش های ارسال چندگامی باعث می شود تا توان کمتری تلف شود. اما استفاده از این روش باعث ایجاد مشکلاتی در مدیریت همبندی و کنترل دسترسی به محیط انتقال می شود.

مدل انتقال اطلاعات

بنابر کاربرد یک شبکه حسگر بی سیم ، مدل انتقال اطلاعات در آن می تواند پیوسته^[۵۶] ، بسته به اتفاق^[۵۷] ، بسته به درخواست^[۵۸] و یا ترکیبی از این ها باشد.

در حالت پیوسته ، هر حسگر اطلاعات خود را به صورت متناوب ارسال می دارد. در حالت بسته به اتفاق ، هر وقت اتفاقی از قبل تعیین شده در یک بخش از شبکه به وقوع بپیوندد، این اتفاق گزارش می شود. در حالت بسته به درخواست ، از طرف ایستگاه پایه یک درخواست در شبکه منتشر شده و به حسگرهای دلخواه می رسد. حسگرهای مورد نظر نیز پاسخ مناسب را می دهند. برخی از شبکه ها از ترکیب این مدل ها استفاده می کنند. از نقطه نظر کم کردن مصرف انرژی و پایداری مسیرهای ایجاد شده ، مدل انتقال اطلاعات بسیار مورد اهمیت است. مثلا در یک کاربرد تشخیص آتش در جنگل، استفاده از یک پروتکل با مدل انتقال اطلاعات بسته به اتفاق بسیار کارا و مناسب است.

۲-۲-۵ ترکیب داده ^[۵۹]ها:

بسیاری از حسگرها ممکن است داده های تکراری تولید کنند. با بهره گرفتن از تکنیک ترکیب داده ها می توان از حجم اطلاعات ارسالی تا حد زیادی کم کرد. با توجه به اینکه پردازش اطلاعات کمتر از ارسال اطلاعات توان تلف می کند، ترکیب اطلاعات بسیار مهم جلوه می کند و به همین دلیل در بسیاری از پروتکل ها از این تکنیک استفاده شده است. می توان با بهره گرفتن از تکنیک های پردازش سیگنال اطلاعات دقیق تری بدست آورد که به این روش Data Fusion می گویند که یکی از روش های آن روش شکل دهی پرتو می باشد

۲-۳ پروتکل های مسیریابی

۲-۳-۱ روش سیل آسا^[۶۰]

در روش سیل آسا [۶۷] یک گره جهت پراکندن قسمتی از داده ها در طول شبکه ، یک نسخهاز داده مورد نظر را به هریک از همسایگان خود ارسال میکند. هروقت یک گره ، داده جدیدی دریافت کرد، از آن نسخه برداری میکند و داده را به همسایه هایش (به جز گرهی که داده را از آن دریافت کرده است.)ارسال میکند.الگوریتم زمانی همگرا میشود یا پایان می یابد که تمامی گره ها یک نسخه از داده را دریافت کنند.

زمانی که طول میکشد تا دسته ای از گره ها مقداری از داده را دریافت و سپس ارسال کنند، یک دور نامیده میشود.الگوریتم سیل آسا در زمانO(d) دور، همگرا میشود که d قطر شبکه است چون برای یک قطعه داده d دور طول میکشد تا از یک انتهای شبکه به انتهای دیگر حرکت کند . سه مورد از نقاط ضعف روش ارسال ساده جهت استفاده از آن در شبکه های حسگر در زیر آورده شده است[۶۸]:

انفجار^[۶۱]: در روش سنتی سیل آسا ، یک گره همیشه داده ها را به همسایگانش، بدون در نظر گرفتن اینکه آیا آن همسایه، داده را قبلا دریافت کرده یا خیر، ارسال میکند.این عمل باعث بوجود آمدن مشکل انفجار میشود که در شکل ۲-۳ آورده شده است.در این شکل گرهA پخش سیل آسا را با ارسال داده ها به همسایگانش یعنی گره هایB,C آغاز میکند.این گره ها داده ها را دریافت یکنند و یک نسخه از آن را به همسایه مشترکشان یعنی گرهD ارسال میکنند.

شکل ۲-۱ :پدیده انفجار[۸۰]

هم پوشانی:حسگرها معمولا نواحی جغرافیایی مشترکی را پوشش میدهند و گره ها معمولا قطعه داده هایی از حسگرها را دریافت میکنند که باهم همپوشانی دارند. شکل۲-۲ نشان میدهد که هنگامی که دو گره A,B داده هایی را که هم پوشانی دارند دریافت میکنند و آن را به همسایه مشترکشانC ارسال میکنند چه اتفاقی می افتد.الگوریتم در این حالت ، انرژی و پهنای باند را جهت ارسال دو نسخه از یک داده به همان گره ، هدر میدهد.

عدم اطلاع از منابع: در روش سیل آسا، گره ها بر اساس میزان انرژی موجود خود در یک زمان ، فعالیتهای خود را تغییر نمیدهند در صورتیکه یک شبکه از حسگرهای خاص منظوره ،میتواند از منابع موجود خود آگاهی داشته باشدو ارتباطات و محاسبات خود را با شرایط منابع انرژی خود مطابقت دهد.

شکل۲-۲:پدیده هم پوشانی[۸۰]

۲-۳-۲ روش شایعه پراکنی^[۶۲]

روش شایعه پراکنی [۶۷]، یک جایگزین برای روش سیل آسا سنتی محسوب میشود که از فرایند تصادف برای صرفه جویی در مصرف انرژی بهره میبرد.به جای ارسال داده ها به صورت یکسان، یک گره شایعه پراکن ، اطلاعات را بصورت تصادفی تنها به یکی از همسایگانش ارسال میکند.اگر یک گره شایعه پراکن ، داده ای را از همسایه اش دریافت کند، میتواند درصورتی که همان همسایه به صورت تصادفی انتخاب شد، داده را مجددا به آن ارسال کند.علت این امر در شکل ۲-۳ بحث شده است.دراین شکل اگر گرهD هیچگاه داده خود را به سمت گرهB باز نگرداند ، گرهC هیچگاه داده را دریافت نخواهد کرد.

شکل۲-۳: روش شایعه پراکنی [۶۷]

هرگاه داده در روش سیل آسا کلاسیک، به یک گره با مرتبه بالا برسد، نسخه های بیشتری از داده شروع به پراکنده شدن در داخل شبکه میکنند تا وقتی که این کپی ها در اثر تصادم به انتها برسد در صورتیکه روش شایعه پراکنی جلوی چنین تصادم هایی را میگیرد چون در این روش تنها یک کپی از داده در هر گره ایجاد میشودو هرچه تعداد کپی های ایجاد شده کمتر باشد احتمال تصادم این کپی ها کمتر میشود.

درحالیکه روش شایعه پراکنی اطلاعات را به کندی در شبکه پراکنده میکند، سرعت مصرف انرژی آهسته ای هم دارد .از آنجایی که هر گره داده را به صورت تصادفی ، تنها به یکی از همسایه های خود ارسال میکند.سریعترین سرعت پخش داده ها دراین روش،برابر یک گره در هر دور است.بنابراین باوجود C منبع در شبکه، حداکثر سرعت انتشار در این روش برابر C گره در هر دور است.

درنهایت اگرچه روش شایعه پراکنی میتواند تاحد زیادی از تصادم جلوگیری کندولی این روش، هیچ راه حلی برای جلو گیری از همپوشانی ارائه نکرده است.

۲-۳-۳ روش SPIN

SPIN ؛ از خانواده پروتکل های داده گرای مبتنی بر مذاکره در WSN می باشد. هدف اصلی، انتشار کارای مشاهدات جمع آوری شده توسط سنسورها به سایر گره های سنسور دیگر در شبکه می باشد. معمولاً پروتکل های ساده ی سیل آسا و gossiping ، برای انتشار اطلاعات در WSNپیشنهاد می شود. در تکنیک سیل آسا هر گره یک کپی از بسته ی داده را به همه ی همسایگانش ارسال می دارد آن بسته به همه گره ها در شبکه برسد. از طرف دیگر gossiping ، از تصادفی سازی بهره گرفته و جلوی تکثیر بی رویه بسته های یکسان در شبکه را می گیرد و نیاز است که گره گیرنده بسته ، آن را به همسایه انتخابی به صورت تصادفی اش بفرستد. هر دو تکنیک ساده و در عین حال بی نیاز از یادگیری و حفظ توپولوژی شبکه اند.

نقایص تأخیر بسته ها و به هدر دادن منابع، در الگوریتم های ذیل، همراه با افزایش سایز شبکه؛ و ترافیک Load ، کارآیی آنها را به شدت افت می دهد. این مانع معمولاً توسط همپوشانی جغرافیایی و ترافیک انفجاری انجام می شود. ترافیک انفجاری یعنی اینکه چندین کپی از یک بسته ی داده به یک نود در شبکه ارسال شود. همپوشانی جغرافیایی یعنی اینکه چندین گره با یک ناحیه ی جغرافیایی را برای انتشار بسته های اطلاعاتی یکسان به گره های دیگر در شبکه انتخاب کنند.

این پروتکل ها رفتارشان را نمی توانند تغییر دهند تا با شرایط جدید تطابق پیدا کرده و پویا باشند. این فقدان سبب کاهش طول عمر شبکه و مصرف بی رویه ی انرژی می شود. هدف اصلی SPIN برطرف کردن نقایص رایج در پروتکل های انتشار داده ی امروزی است.

اصل مهم در این خانواده از پروتکل ها، مذاکره بر سر داده و وفق پذیری با منابع شبکه است. مذاکره بر سر داده یعنی اینکه گرهها محتوای داده را بررسی کرده و یک تم جدید به نام Metadata را درباره ی داده ها ( داده درباره ی داده ) تشکیل می دهند که توصیفی از داده ای است که قرار است ارسال شود.

و گره ها می توانند داده های خود را از طریق دسترسی به Metadata انتخاب بکنند و آن را آگهی کنند و بدین ترتیب داده ها فقط به گره هایی که نیازمند آن داده ها هستند ارسال می شود، همچنین موجب حذف ترافیک انفجاری و کاهش بسته های تکراری می شود.

از طرف دیگر استفاده از Metadata،احتمال همپوشانی را نیز از بین می برد البته با شرایط که گره ها می توانند درخواست هایشان را محدود به داده هایی بکنند که دقیقاً لازم دارند.

دو راه کار کلیدی دسته پروتکلهای SPIN برای برطرف کردن مشکلات مطرح شده در روش کلاسیک سیل آسا،استفاده از مذاکره و تطبیق منابع است.برای برطرف کردن مشکل تصادم و همپوشانی،گره هایSPIN، از مذاکره بایکدیگر قبل از ارسال اطلاعات استفاده میکنند.همچنین گره ها قبل از ارسال داده ها ، منابع خود را ارزیابی میکنند.هرگره حسگر،مدیر منابع مخصوص خودش را دارد که مصرف انرژی را دنبال میکند.برنامه های کاربردی قبل از ارسال یا پردازش داده ها مدیر منابع را بررسی میکنند که این امر به حسگرها کمک میکند تا بعضی از فعالیتهای خاص را هنگام کمبود انرژی متوقف کنند.

شبه داده ها که در SPIN به عنوان نماینده داده ها تولید میشوندباید حجمی کمتر از داده هایی که نماینده آنها هستند داشته باشند.همچنین اگر دو قطعه از داده ها باهم قابل تفکیک باشند،باید شبه داده های آنها نیز این خاصیت را داشته باشند.

گره ها درSPIN برای ارتباط با یکدیگر از سه نوع پیغام استفاده میکنند:

• ADV-برای تبلیغ داده های جدید استفاده میشود.وقتی یک گره SPIN ، داده ای برای به اشتراک گذاشتن در اختیار دارد ، این امر رامیتواند با ارسال شبه-داده مربوطه تبلیغ کند.
• REQ–جهت درخواست اطلاعات استفاده میشود.یک گره SPIN میتواند هنگامی که میخواهد داده حقیقی را دریافت کند ازاین پیغام استفاده کند.
• DATA–شامل پیغامهای داده ای است.پیغامهایDATA محتوی داده حقیقی جمع آوری شده توسط حسگرها هستند.

میتوان گفت این روش یک روش ساده دست تکانی برای پراکندن داده ها در یک شبکه بدون اتلاف است که در سه مرحله کار میکند و درهریک از مراحل ، از یکی از پیغامهای شرح داده شده در بالا استفاده میکند.پروتکل زمانی آغاز میشودکه یک گره ، داده جدیدی بدست می آورد که مایل است آن را پراکنده کند واین کاررا با نامگذاری داده جدید و فرستادن یک پیغامADV به همسایگانش انجام میدهد. با دریافت کردن پیغامADV، گرهء همسایه بررسی میکنند که آیا قبلا چنین داده ای را دریافت کرده اند یا درخواست چنین داده ای را داده اند یاخیر.اگر نه ، گره همسایه برای ارسال داده درخواست شده به فرستنده ، یک پیغامREQ به عنوان پاسخ برمیگرداند.پروتکل با ارسال داده موردنظر یعنی ارسال پیغامDATA در جواب پیغام REQ تکمیل میشود.

در شکل۲-۴ نمونه ای ازاین پروتکل نشان داده شده است.بادریافت یک پیغام ADV از طریق گرهA،گرهB بررسی میکند که آیا تمامی داده تبلیغ شده را در اختیار دارد یاخیر.در غیر این صورت ، گرهBیک پیغام REQ بهA برمیگرداند که در آن تمامی داده هایی که گره B نیازدارد ،فهرست شده است.وقتی گرهA پیغامREQ را دریافت کرد ، داده های درخواست شده را استخراج میکند و آنهارا بوسیله یک پیغام DATA به B ارسال میکند.سپس گرهB یک پیغامADV جدید تولید میکند که در آن داده جدید بدست آمده را به همه همسایگانش تبلیغ میکند ولی پیغامADV را برای گرهA ارسال نمیکند، چون که میداند گرهA قبلا داده مورد نظر را در اختیار دارد یا خیر.سپس این گره هاهم تبلیغات مربوط به داده جدید را به همسایگانش ارسال میکنند و پروتکل ادامه می یابد.

شکل۲-۴:الگوریتم دست تکانی درSPIN[69]

اگرچه این پروتکل برای شبکه های بدون اتلاف طراحی شده است ، به سادگی میتوان آنرا برای استفاده در شبکه های با اتلاف تعمیم دادبه این صورت که گره ها ، برای جبران پیغامهایADV از دست رفته ، میتوانند به صورت متناوب این پیغامها را ارسال کنند وهمچنین برای جبران پیغامهایREQوDATA ازدست رفته، گره ها میتوانند داده های مورد نیاز خود را در صورتیکه در یک بازه زمانی مشخص دریافت نشدند،دوباره درخواست دهند.همچنین درمورد شبکه های سیار در صورتی که گرهی مشاهده کرد که همسایگانش تغییر کرده اند میتواند فورا تمامی داده خود را تبلیغ کند.

مهمترین مزیت SPIN سادگی آن وهمچنین محلی بودن و عدم وابستگی به یک چینش خاص است که باعث میگردد بتوان آن را به سادگی برروی هر شبکه ای پیاده سازی کرد.

پروتکل توسعه یافته Spinتحت عنوانSpin-Ecیک فکر هوشمندانه ساده ، جهت صرفه جویی درمنابع بهSPIN-1 اضافه میکند به اینصورت که وقتیکه منابع به اندازه کافی موجود است گره هایSPIN-2 مانند گره ها درSPIN-1 از پروتکل سه مرحله ای استفاده میکنند.وقتیکه گرهی مشاهده میکند که میزان منابع انرژی اش از یک حد خاص کمتر شده است ، خودش را بوسیله کاهش شرکت خود در پروتکل با شرایط جدید تطبیق میدهد و در حالت کلی یک گره تنها هنگامی در پروتکل شرکت میکند که اطمینان دارد میتواند تمامی مراحل دیگر پروتکل را بدون اینکه منابع انرژی اش از محدوده تعیین شده پایینتر رود، به انتها برساند.در غیر اینصورت گره با دریافت پیغامADV هیچگونه پیغام REQ تولید نمیکند.این روش باعث میشود که گره هنگام پایین بودن انرژی درگیر پیغامهای DATA نشود.

۲-۳-۴ روش انتشار هدایت شده^[۶۳]

دراین روش[۷۰] منابع و دریافت کننده ها از خصوصیات، برای مشخص کردن اطلاعات تولید شده یا مورد نیاز استفاده میکنند و هدف روش انتشار هدایت شده پیداکردن یک مسیر کارآمد چندطرفه بین فرستنده ها وگیرنده هاست. در این روش هروظیفه به صورت یک علاقه مندی منعکس میشود که هر علاقه مندی مجموعه ای است از زوجهای خصوصیت – مقدار.برای انجام یک وظیفه ،علاقه مندی در شبکه در ناحیه مورد نظر منتشر میشود.در این روش هرگره،گرهی را که اطلاعات را از آن دریافت کرده بخاطر میسپارد و برای آن یک گرادیان تشکیل میدهد که هم مشخص کننده جهت جریان اطلاعات است و هم وضعیت درخواست را نشان میدهد.(که فعال یا غیر فعال است یا نیاز به به روز شدن دارد.) در صورتی که گره از روی گرادیان های قبلی یا اطلاعات جغرافیایی بتواند مسیر بعدی را پیش بینی کند تنها درخواست را به همه همسایه های مجاور ارسال میکند.وقتی یک علاقه مندی به گرهی رسید که داده های منطبق با آن را در اختیار دارد ، گره منبع ، حسگرهای خود را فعال میکند تا اطلاعات مورد نیاز را جمع آوری کنند و اطلاعات را به صورت بسته های اطلاعاتی ارسال میکند.

داده ها همچنین میتوانند به صورت مدل خصوصیت – نام ارسال شوند.گرهی که داده ها را ارسال میکند به عنوان یک منبع شناخته میشود.داده هنگام ارسال به مقصد در گره های میانی ذخیره میشود که این عمل دراصل برای جلوگیری از ارسال داده های تکراری و جلوگیری از بوجود آمدن حلقه استفاده میشود.همچنین از این اطلاعات میتوان برای پردازش اطلاعات درون شبکه وخلاصه سازی اطلاعات استفاده کرد.پیغامهای اولیه ارسالی به عنوان داده های اکتشافی برچسب زده میشوند و به همه همسایه هایی که به گره دارای داده ،گرادیان دارند ارسال میشوند یا میتوانند از میان این همسایه ها، یکی یا تعدادی را بر حسب اولویت جهت ارسال بسته های اطلاعاتانتخاب کنند.(مثلا همسایه هایی که زودتر از بقیه پیغام را به این گره ارسال کرده اند)برای انجام این کار ، گیرنده یا سینک همسایه ای را که جهت دریافت اطلاعات ترجیح میدهد تقویت میکند.اگر یکی از گره ها در این مسیر ترجیحی از کار بیفتد، گره های شبکه بطور موضعی مسیر ازکارافتاده را بازیابی میکنند.در نهایت گیرنده ممکن است همسایه جاری خود را تقویت منفی کند درصورتی که مثلا همسایه دیگری اطلاعات بیشتری جمع آوری کند.

پس از ارسال داده های اکتشافی اولیه ، داده های بعدی تنها از طریق مسیرهای تقویت شده ارسال میشوند.منبع اطلاعات به صورت متناوب هرچند وقت یکبار داده های اکتشافی ارسال میکند تا گرادیان ها در صورت تغییرات پویای شبکه ،به روز شوند.نحوه این الگوریتم درشکل ۲-۵ به صورت خلاصه آورده شده است.

1. c) ارسال داده ها از طریق مسیر تقویت شده b) تنظیم کردن اولیه گرادیان هاa )پراکندن علاقه مندی ها

شکل ۲-۵: نحوه عملکرد الگوریتم انتشار هدایت شده

برخی از خصوصیات کلیدی روش انتشار هدایت شده اطلاعات که آن را از روش های سنتی در شبکه متمایز میکند عبارتند از اول اینکه روش پخش اطلاعات یک روش داده-محور است و تمام ارتباطات در یک شبکه حسگر براین مبنا از علاقه مندی ها جهت مشخص کردن اطلاعات نامگذاری شده استفاده میکنند.دوم برخلاف شبکه های سنتی که روش انتقال انتها به انتها دارند در این روش از ارتباط همسایه با همسایه یا گام به گام استفاده میشود و هر گرهی میتواند داده ها وعلاقه مندی ها را تفسیر کند زیرا شبکه های حسگر معمولا عملکرد واحدی دارند و وظیفه یکسانی رابر عهده دارند.سوم ، دراین روش گره ها آدرس سراسری یکسان یا مشخصه واحدی ندارند ولی هرگره باید از همسایگانش به صورت محلی قابل تفکیک باشد و نهایتا چون هر گره میتواند داده ها را پردازش کند ،میتوان حجم داده ها را در شبکه کاهش داد و داده ها را بصورت خلاصه ارسال کرد.

فیلترها

همچنین در این روش از فیلترها[۷۱] استفاده میشود که وظیفه تجمیع^[۶۴] و خلاصه کردن داده هار ا در گره ها برعهده دارند.فیلترها پیمانه های نرم افزاری هستند که داده را هنگام عبوراز داخل شبکه حسگر پردازش و قواعد سازگاری را تعیین میکنند که چه فیلترهایی باید در هر مرحله فعال شوند و منابع و گیرنده ها چگونه به هم مرتبط میشوند.از فیلترها در مواردی مانند تجمیع داده ها در داخل شبکه پردازش داده ها به صورت پیمانکاری^[۶۵]، ذخیره کردن موقت اطلاعات^[۶۶] و سایر عملکردهای مشابهی که جهت کنترل کردن حرکت اطلاعات کاربرد دارند، استفاده میشود.

روش انتشار هدایت شده به صورت پایه داخل فیلتر گرادیان^[۶۷] پیاده سازی میشود.این فیلتر گرادیانهایی را فراهم میکند که حالت هر جریان به تمامی همسایه های هر گره را نگهداری میکنند و همچنین مسئولیت ارسال متناوب پیغام های علاقه مندی ها و پیغام های تقویت کننده را برعهده دارد.

یک جفت فیلتر به نام ^[۶۸]GEAR به صورت بهینه ، فیلتر گرادیان را در بر میگیرند تا بتوانند مسیریابی جغرافیایی با قابلیت کنترل مصرف انرژی را پیاده سازی کنند.یک فیلتر پیش پردازنده بالای فیلتر گرادیان مینشیند تا پیغام های مخصوص GEAR را دریافت کند و اطلاعات گذرای موقعیت جغرافیایی آن را هنگام رسیدن بردارد و یک فیلتر مسیریابی جغرافیایی که بعد از ماژول گرادیان وارد عمل میشود تا خواسته ها را در جهت مناسب ارسال کند.علاوه براینها برای کاربردهای مختلف مانند پردازش داده ها و ردگیری و سایر کاربردها فیلترهای دیگری پیاده سازی شده است.

یکی از کاربردهایی که برای کاهش حجم طلاعات بوسیله فیلترها پیاده میشود خلاصه سازی اطلاعات میباشد.همچنین یکی دیگر از تکنیکهای نرم افزاری که برای بهبود کارایی روش انتشار به کار میرود استفاده از پرسشهای تو در تو است که توضیح هرکدام در ذیل آورده شده است.

خلاصه سازی فرصت طلبانه

به طور کلی روش های متعددی جهت تجمیع اطلاعات ارائه شده است که یکی از این روشها که براساس روش انتشار مطرح شده است روش تجمیع تصادفی[۷۲] است.به این صورت که هنگامی که داده ها توسط منابع جمع آوری می شوند و به سمت گیرنده ها ارسال میشوند، گره های میانی اطلاعات مربوط به هم را ذخیره میکنند که این کار را با فیلترهایی در سطح برنامه کاربردی انجام میدهند.سپس این گره های میانی اطلاعات تکراری را حذف میکنند یا میتوانند اندکی تاخیر در ارسال اطلاعات ایجاد کنند و اطلاعات جمع آوری شده از منابع مختلف را تجمیع کنند.

در این روش درختی از منابع به سمت یک گیرنده به عنوان ریشه درخت، تشکیل میشود و اگر در هنگام ادغام شدن شاخه ای درخت داده های یکسان با هم برخورد کنند تنها یکی از آنها به سمت ریشه درخت ارسال میشود.یکی از اشکالهای این روش این است که مسیر داده ها ممکن است تا نزدیکی گیرنده به هم نرسند وادغام نشوند که کارایی الگوریتم خلاصه سازی را کاهش میدهد.روش تجمیع حریصانه جهت برطرف کردن این مشکل مطرح شده است.

خلاصه سازی حریصانه

تفاوت این روش با روش تجمیع تصادفی ،تشکیل مسیر و نگهداری مسیر است.برای ساختن یک درخت حریصانه افزایشی ، کوتاهترین مسیر تنها برای اولین منبع به سمت گیرنده تشکیل میشود و سایر منابع به صورت افزایشی به نزدیکترین نقطه درخت حاصل شده،متصل می شوند.در روش حریصانه هرنمونه داده اکتشافی یک هزینه انرژی برای رساندن این نمونه از منبع به گره جاری دارد و علاوه بر این هر منبع بر روی درخت موجود یک پیغام هزینه افزایشی روی درخت تولید میکند که مربوط به هر نمونه اکتشافی جدید دریافت شده است که این پیغام محتوی هزینه انرژی افزایشی است که برای رساندن نمونه اکتشافی به درخت موجود مورد نیاز است.این پیغام مربوط به هزینه افزایشی تنها در طول درخت خلاصه سازی به سمت گیرنده ارسال می شود.برای یافتن نزدیکترین نقطه روی درخت، فیلد هزینه افزایشی تنها میتواند توسط گره های نزدیکتر به روز شود.(مثلا گره ای که نمونه اکتشافی مربوطه را با هزینه پایینتری دریافت کرده اند.)

خلاصه سازی اطلاعات درون-شبکه ای

در شبکه های حسگر ، به منظور ایجاد پایداری و بالا بردن دقت ،حسگرها طوری در شبکه قرار داده میشوند که مقداری هم پوشانی داشته باشند.به همین دلیل رخ دادن یک رویداد چندین حسگر را تحت تاثیر قرار میدهد و همه حسگرها اطلاعات دریافت شده را به گیرنده ارسال میکنند ولی با تجمیع اطلاعات میتوان هزینه مصرف انرژی این تبادلات راتاحد زیادی کم کرد و از حجم اطلاعات مبادله شده به میزان محسوسی کاست.

پرسش تو در تو

رویدادها در جهان واقعی معمولا در پاسخ به یک سری تغییرات محیطی رخ می دهند.در شبکه های حسگر ، حسگرها می توانند از این پدیده همگرایی ، برای فعال کردن بعضی دیگر از حسگرها استفاده کنند و در عمل یک پرسش درون یک پرسش دیگر ایجاد کنند.با این کار میتوان زمان فعال بودن دسته ای از حسگرها را (که معمولا جزء حسگرهای با مصرف انرژی بالا هستند)کاهش داد و با این عمل مصرف انرژی کل شبکه را کاهش داد.(مثلا ممکن است یک حسگرشتاب سنج، یک گیرندهGPS را که یک حسگر پر مصرف است فعال کند); علاوه بر این در بعضی موارد میتوان ترافیک شبکه را هم کم کرد(مثلا یک حسگر تصویر بردار محرک ترافیک بسیار کمتری نسبت به یک جریان ویدیویی ثابت ایجاد میکند).

مزیت استفاده از پرسشهای تو در تو[۷۲] اینست که در آن اطلاعات حسگرهای اولیه، برای حسگرهای دیگر قابل دریافت است و نیازی به ارسال آنها به کاربر نمیباشد.در کاربردهای نظارتی شبکه های حسگر ، حسگرهای اولیه و حسگرهای تحریک شونده معمولا بسیار به یکدیگر نزدیک هستند، در صورتی که کاربر ممکن است بسیار دور باشد.استفاده از پرسش تو در تو باعث میشود که ترافیک به جای ارسال شدن به کاربر در دوردست، به صورت محلی در اطراف رویداد تحریک کننده ایجاد شود و بنابراین تاخیر و ترافیک شبکه کاهش می یابد.

۲-۳-۵ مقایسه روش انتشار هدایت شده با روشSPIN:

روش SPIN و روش انتشار هدایت شده ، هر دو روش ارتباطی برای کاربردهای خاص و بر اساس موضوع در شبکه های حسگر هستند[۷۳].در شبکه های حسگر به منظور دستیابی به مسیر یابی بهینه از لحاظ انرژی ،مدیریت منابع ومسیریابی باید کاملا با کاربردها هماهنگ و منطبق شوند.

هردو پروتکل برخلاف روش های سنتی مسیریابی،داده محور هستند که به این معنی است که در آنها همه ارتباطات بر مبنای داده های نامگذاری شده صورت میگیرد.در روش انتشار هدایت شده ، داده نامگذاری میشود و بوسیله یکسری خصوصیات مشخص میشود.در روش SPIN نیز داده ها توسط شبه-داده ها نامگذاری میشوند.

هردو روش SPIN و انتشار هدایت شده به منظور ایجاد یک واسط ارتباطی مطمئن طراحی شده اند.روشSPIN بدین منظور طراحی شده است که مشکلات روش کلاسیک سیل آسا با مباحثه بین گره ها قبل از ارسال داده های حقیقی برطرف شود، بنابراین روشSPIN یک روش فرستنده محور است.

درمورد الگوریتم انتشار هدایت شده گیرنده علاقه مندی های خود را در سطح شبکه منتشر میکند و اگر این علاقه مندی با داده های استخراج شده توسط منابع انطباق داشته باشد، فرستنده داده ها را به سمت گره فرستنده علاقه مندی،منتشر میکند.بنابراین در روش انتشار هدایت شده ارسال داده ها به صورت گیرنده محور صورت میگیرد.

همچنین هردو پروتکل نسبت به مصرف انرژی آگاه هستند. در SPIN گره ها منابع موجود را استخراج میکنند و بنابراین میتوانند برا ساس منابع موجود تصمیم گیری نمایند و بصورت مشابه در روش انتشار هدایت شده ، مسیر یابی جغرافیایی آگاه از انرژی (GEAR) کمک میکند که داده ها بتوانند به طرف ناحیه مورد نظر پراکنده شوند و عمل پخش سیل آسا را محلی میکند.به یک مفهوم هردو الگوریتم بر مبنای پخش سیل آسا کار میکنند ولی از لحاظ پیاده سازی روش های مختلف برای جلوگیری از پخش سیل آسای ناخواسته در شبکه با روش کلاسیک آن متفاوتند.

کارهای زیادی بر روی الگوریتم انتشار هدایت شده پایه صورت گرفته است که هر یک به نحوی عملکردآن را بهبود داده اند.الگوریتم انتشار هدایت شده پایه به الگوریتم انتشار،با خاصیت جذب دو مرحله ای هم معروف است چون در این روش در فاز اول ، ابتدا گره گیرنده یا مقصد یک علاقه مندی را به سمت داخل شبکه منتشر میکند و هنگامی که گرهی متوجه انطباق داده های جمع آوری توسط حسگرهای خود با علاقمندی منشر شده گردید،یک پیغام داده اکتشافی به سمت مقصد ارسال میکند و این داده از بین گرادیان هایی که هنگام انتشار پیغام علاقه مندی تشکیل شده اند،سعی میکند گرادیانی با بهترین زمان پاسخ یا کیفیت کانال را انتخاب کند و به همین صورت پیش میرود تا به مقصد برسد و سپس گره مبدا داده های جمع آوری شده را به سمت مقصد ارسال میکند.

یکی از روشهایی که برای بهبود مسیریابی الگوریتم به کار رفته،الگوریتمGEAR[74] است که با بهره گرفتن از اطلاعات جغرافیایی ، فضای مسیریابی را محدود می کند.روش جذب دو مرحله ای برای بعضی از کاربردها روش بسیار مناسبی است ولی در مقابل برای برخی کاربردها هم بسیار ضعیف عمل میکند; خصوصا کاربردهایی که در آنها تعداد زیادی منبع وگیرنده وجود دارد و گیرنده ها به نحوی باهم ارتباط دارند، حجم داده های ترافیکی بسیار افزایش می یابد به صورتی که حتی محدود کردن دامنه با مسیریابی جغرافیایی هم نمیتواند مشکل را برطرف نماید.برای برطرف شدن این مشکل، روش انتشار بیرون دهنده مطرح شده[۷۵] که در آن نقش منتشر کنندگان اطلاعات و استفاده کنندگان داده ها جابجا می شود و باعث می شود که منابع داده ها، به صورت فعالانه دنبال استفاده کنندگان بگردند.مزیت روش انتشار بیرون دهنده اینست که بر خلاف روش جذب دو مرحله ای تنها یک فاز دارد که در آن اطلاعات کنترلی پراکنده می شوند تا گیرنده ها را پیدا کنند.همچنین روش دیگری به نام روش جذب یک مرحله ای [۷۵] وجود دارد که این روش هم با حذف کردن یکی از مراحل روش جذب دو مرحله ای آن را ساده تر می کند.

۲-۳-۶ روش مسیریابی جغرافیایی^[۶۹](GEAR)

بر اساس ماهیت شبکه های حسگر ، در این شبکه ها پرسش های با دامنه جغرافیایی امری کاملا طبیعی است واگر هر گره بتواند محل خود را تشخیص دهد ،پرسشهای بر مبنای ناحیه جغرافیایی می توانند عمل پخش داده هارا سهولت بخشند و نیاز به انتشار سیل آسا را برای دستیابی به ناحیه مربوطه برطرف کنند.این الگوریتم[۷۴] ارتباطات در سطح شبکه را با ارتباطات محدود شده جغرافیایی جایگزین میکند به این صورت که هنگامی که این الگوریتم به الگوریتم جذب دومرحله ای اضافه می شود،وقتی که کاربران به صورت فعالانه علاقه مندی ها را به داخل شبکه ارسال می کنند، پرسشهایی که علاقه مندی در یک ناحیه خاص را ایجاد می کنند، بوسیله الگوریتم مسیریابی حریصانه جغرافیایی به سمت ناحیه مورد نظر رسیده باشد و دیگر عمل انتشار سیل آسا در سطح کل شبکه صورت نمیگیرد.همچنین داده های اکتشافی هم تنها در جهت گرادیان هایی حرکت می کنند که توسط علاقه مندی ها ایجاد شده اند و بنابراین هزینه داده های اکتشافی نیز کاهش پیدا میکند.در نهایت الگوریتمGEAR باعث عمل انتشار بهینه برای کاربردها وشبکه هایی می شود که از پرسش هایی در سطح ناحیه جغرافیایی استفاده می کنند.فرایند ارسال بسته ها به مقصد در این روش از دو مرحله تشکیل شده است:

۱)مرحله اول ارسال بسته ها به سمت ناحیه هدف است.GEAR برای مسیر یابی بسته ها به سمت ناحیه مورد نظر از ایده هوشمندانه انتخاب آگاهانه همسایه ها براساس میزان انرژی و ناحیه جغرافیایی،استفاده می کند و برای این عمل دو حالت را در نظر می گیرد:

هنگامی که یک همسایه نزدیکتر به مقصد وجود دارد ،GEAR، گرهی را انتخاب می کند که در میان گره های موجود به گره مقصد نزدیک تر باشد.

۲) هنگامی که فاصله همه همسایه ها از گره مقصدخیلی زیاد باشد به این معنی است که یک حفره در مسیر وجود دارد.الگوریتمGEAR در چنین شرایطی، گرهی را انتخاب می کند که بعضی از هزینه های این همسایه را به حداقل برساند.

مرحله دوم پخش کردن بسته ها در داخل ناحیه مورد نظر است و دراغلب موارد برای این منظور از یک الگوریتم بازگشتی پیش برنده جغرافیایی استفاده می شود.البته تحت بعضی از شرایط مکان یابی ضعیف ، این مسیریابی بازگشتی ممکن است خاتمه پیدا نکند.در چنین شرایطی می توان از روش سیل آسای محدود شده استفاده کرد.

۲-۳-۷روش انتشار بیرون دهنده

روش جذب دو مرحله ای برای شبکه های با تعداد گیرنده کم به خوبی کار می کند ولی بعضی از دسته برنامه های کاربردی نیاز به رابطه حسگر به حسگر دارند.مثلا شبکه ممکن است تعدادی حسگرداشته باشد که اغلب در حالت کم مصرف قرار گرفته باشند ولی هنگام به وقوع پیوستن یک رویداد خاص توسط گره های همسایه تحریک شوند و فعال گردند.خاصیت این رده از برنامه های کاربردی این است که تعداد زیادی از حسگرها به این داده ها علاقه مندند و بسیاری از حسگرها هم این داده ها را منتشر می کنند.در چنین کاربردی روش جذب دو مرحله ای بسیار ضعیف عمل می کند چون همه به طور فعال پیغامهای علاقه مندی ارسال می کنند و حتی در صورتی هم که چیزی تشخیص داده نشود برای حسگرهای دیگر گرادیان تشکیل می دهند.

روش انتشار بیرون دهنده [۷۵] برای چنین کاربردهایی طراحی شده است وبا وجود یکی بودن API های این روش با روش جذب دومرحله ای در این روش نقش منابع و گیرنده ها جا به جا می شود،یعنی گیرنده غیرفعال شده و اطلاعات مربوط به علاقه مندی ها به صورت محلی در داخل گره ای که درخواست داده موردنظر را دارد باقی می ماند.همچنین در مقابل ،منابع نقش فعالانه ای برعهده می گیرند و در این حالت ، داده های اکتشافی بدون رسیدن علاقه مندی ها به داخل شبکه فرستاده می شود.در این روش مانند روش جذب دو مرحله ای،با رسیدن داده اکتشافی به گیرنده،یک پیغام تقویت کننده تولید می شود و به صورت بازگشتی مسیر برگشتی را به سمت منبع طی میکند و یک گرادیان تقویت شده را شکل دهی می کند.

روش انتشار بیرون دهنده برخلاف روش جذب دومرحله ای ،برای کاربردهای با تعداد منابع بالا و همچنین تعداد گیرنده های بسیار،طراحی شده ولی در حالتی که منابع ، داده هارا هر از چند گاه تولید نمایند.روش انتشار بیرون دهنده برای کاربردهایی که در آنها تعداد زیادی منابع به صورت پیوسته اطلاعات تولید می کنند، مناسب نیست چون در این روش ممکن است داده ها حتی در صورت عدم نیاز هم در سطح کل شبکه ارسال گردد.

یکی از مزایایروش انتشار بیرون دهنده اینست که در این روش تنها در یک صورت اطلاعات به کل شبکه ارسال میگردد(داده های اکتشافی) برخلاف روش جذب دو مرحله ای که چنین عملی در دوحالت انجام می گیرد(علاقه مندی ها و داده های اکتشافی). در شبکه های بزرگ و بدون پرسشهای محدود به دامنه جغرافیایی ،به حداقل رساندن عمل انتشار سیل آسا مزیت بزرگی محسوب می شود.

۲-۳-۸ روش انتشار جذب یک مرحله ای

روش جذب یک مرحله ای[۷۵] یک روش بر مبنای درخواست کننده است که یکی از مرحله های روش جذب دو مرحله ای را حذف می کند.در این روش همانند روش جذب دو مرحله ای در خواست کننده ها پیغامهای علاقه مندی را تولید می کنند و در سطح شبکه پراکنده می کنند و گرادیان هارا شکل میدهند ولی برخلاف روش جذب دومرحله ای هنگامی که یک علاقه مندی به منبع رسید، منبع اولین بسته داده ها را به عنوان داده اکتشافی برچسب نمیزند و به جای این کار داده ها را تنها از طریق گرادیان های ترجیح داده شده ارسال می کند.گرادیان ترجیح داده شده بوسیله همسایه های ایجاد شده که برای اولین بار علاقمندی را به گره جاری ارسال کرده است و بنابراین کمترین تاخیر را نسبت به سایر همسایه های خود دارد .بنابراین با این راهکار روش جذب دومرحله ای دیگر نیازی به پیغام های تقویت کننده ندارد.

روش جذب یک مرحله ای دو عیب عمده نسبت به روش جذب دومرحله ای دارد به این ترتیب این فرض را می کند که همیشه یک ارتباط متقارن بین گره ها برقرار است چون در این روش، مسیر داده ها (مسیر منابع به گیرنده ها) توسط کانال با کمترین تاخیر در مسیر ارسال علاقه مندی مشخص می شود.روش جذب دو مرحله ای جریمه ناشی از ارتباطات غیر متقارن را کاهش می دهد، چون انتخاب مسیر داده ها بوسیله داده های اکتشافی با کمترین تاخیر صورت می گیرد.با این وجود الگوریتم انتشار جذب دو مرحله ای هنوز به سطوحی از تقارن نیاز دارد ، چون پیغام های تقویت کننده مسیرهای برعکس را طی می کنند.

ایراد دیگر روش جذبی یک مرحله ای اینست که در این روش پیغام های علاقه مندی باید یک مشخصه جریان با خود حمل نمایند.اگرچه تولید کردن مشخصه های جریان بسیار ساده است این کار به نسبت تعداد منابع باعث افزایش اندازه پیغام های علاقه مندی می شود وهمچنین استفاده از مشخصه جریان انتها به انتها، به این معنی است که در این روش برای تصمیم گیری جهت ارسال اطلاعات، تنها از اطلاعات محلی استفاده نمی شود.درنهایت روش جذب یک مرحله ای برای کاربرهایی مناسب است که در آنها تعداد زیادی از منابع داده ها را به تعداد کمی از گیرنده ها ارسال می کنند.

فصل سوم:MAC^[70]

۳مقدمه

گره های حسگر یک شبکه چندگامه را تشکیل میدهند تا پیامهارا به یک مقصد پیش ببرند تا اطلاعات بعدا توسط کاربر نهایی بازیابی شوند و یا توسط یک خط مستقل ارسال داده فرستاده شوند. گره های حسگر از ارسال داده برای مقصدهای دوردست که ممکن است در دوسوی ناحیه تحت پوشش قرار داشته باشند خودداری میکنندتا به قابلیت اطمینان بیشتری دست پیدا کنند.باوجود استفاده از روش ارسال چندگامه،واحدفرستنده بیسیم بیشترین میزان مصرف انرژی –بسته به مدت استفاده- در گره های حسگر را دارد و درنتیجه زمینه رابرای بیشترین صرفه جویی فراهم می آورد.

فراتر از بهبود طراحی رادیویی ، یک پروتکل کارا برای کنترل دسترسی به رسانه قادر است میزان مصرف انرژی دستگاه فرستنده را تاحدبسیار زیادی کاهش دهد زیرا بطور مستقیم فعالیت این دستگاه را تنظیم میکند.یک پروتکلMAC ممکن است بسته به نوع شبکه ،قابلیت‌های دستگاه و نیازهای لایه های بالاتر، کارایی های متفاوتی را فراهم آورد ولی بصورت کلی تمامی MAC ها در فراهم آوردن برخی قابلیت‌ها بایکدیگر اشتراک دارند .به صورت کلی برای یکMAC میتوان وظایف زیر را در نظر گرفت:[۵۵]

Framing: تعریف چهارچوب برای بسته های ارسالی و کپسوله کردن داده ها و خارج کردن آنها از کپسول برای ارتباط بین دستگاه ها.

دسترسی به رسانه: تعیین میکند که کدام دستگاه ها در چه زمانی به رسانه دسترسی پیدا میکنند.دسترسی به رسانه کار اصلیMAC پروتکلها میباشد چراکه انتشار پیامها میتواند به سادگی سبب برخورد و خراب شدن بسته ها گردد.

قابلیت اطمینان: کسب اطمینان از ارسال موفق بین دستگاه ها که معمولا از طریق فرستادن پیامASK و یا ارسال مجدد تامین میشود.

کنترل جریان: جلوگیری از از دست دادن داده به دلیل بارگذاری بیش از حد میانگیر گیرنده هامیباشد.

کنترل خطا: کشف و اصلاح خطاها برای کنترل میزان خطاها در بسته های ارسالی به لایه های بالاتر.

بیشتر کارها در زمینهMAC شبکه های حسگر بر روی شیوه دسترسی به رسانه بوده است زیرا مصرف انرژی زیادی دارد و MAC بیشترین کنترل را بر بهره گیری از آن دارد.منابع محدود انرژی مهمترین محدودیت را در طراحی های مربوط به شبکه های حسگر دارد و معمولاMAC سعی میکند میزان مصرف انرژی را کم کند.

جنبه های مختلفی از شبکه های حسگر باعث میشوند که طراحیMAC پروتکلها برای این شبکه ها متفاوت با سایر شبکه ها باشد.نخست اینکه در این شبکه ها گره ها قطعه های غیر ضروری را خاموش میکنند ، زیرا قطعات اگرچه در حالت غیرفعال باشند مقدار غیر قابل صرف نظری از انرژی را مصرف میکنند.به این ترتیب هرگره نیاز دارد با همسایگانش زمان فعالیت و ارسال خود را هماهنگ کند تا فرستندههمسایه او نیز فعال باشد.گره های حسگر معمولا این کار را انجام میدهند تا لایه هایبالاتر تنها مدلی انتزاعی از ارتباطهای موجود و اطلاعات ساختار شبکه داشته باشند.

شبکه های حسگر دارای الگوی ترافیکی متفاوتی نسبت به سایر شبکه ها میباشند.نظارت بر محیط یک نمونه کاربرد رایج برای شبکه های حسگر میباشد.گره های حسگری که بر یک محیط خاص نظارت میکنند داده هارا به صورت دوره ای به یک موجودیت مرکزی میفرستند.داده ها دوره ای و دارای حجم کم میباشند.داده ها علاوه بر دوره ای بودن دارای همبستگی فضایی بسیاری هستند و از آنجاکه دارای حجم کمی میباشند نقش سربار پروتکل اهمیت بیشتری پیدا میکند.

بسیاری از پروتکلهای MAC تمام مدت به کانال گوش میدهندتافعالیتها را کشف کنند، ولی در صورتیکه دستگاه فرستنده به صورت مداوم به کانال گوش بدهد به سرعت باتری گره خالی شده و عمر شبکه حسگر بسیار کاهش پیدا میکند.تفاوتهایMAC های شبکه های حسگر را در قسمت زیر مورد بررسی قرار میدهیم:

۳-۱تفاوتهای پروتکلهایMAC طراحی شده برای شبکه های حسگر

پروتکلهایMAC طراحی شده برای شبکه های بیسیم به دلایل زیادی برای شبکه های حسگر مناسب نمیباشد.

پروتکلهایMAC طراحی شده برای شبکه حسگر باید بیشترین کارآیی را با کمترین مصرف انرژی ، باتوجه به محدودیت منابع در اختیار هر حسگر ،فراهم کنند.

پروتکلهای MAC مخصوص شبکه های حسگر معمولا معیار های کارایی مانند توان عملیاتی و یا تاخیر را در برابر کاهش مصرف انرژی و افزایش طول عمر آن معاوضه میکنند. رایج ترین روش برای کاهش مصرف انرژی گره چرخیدن دوره ای حسگر بین حالتهای فعال با مصرف انرژی بالا و حالت غیر فعال با مصرف انرژی پایین میباشد.گره های حسگر در حالت خواب قادر به انجام وظایف خود نیستند ولی به خواب بردن آنها در صورتیکه مورد نیاز نباشند عمر آنهارا به طور چشمگیری افزایش میدهد.دوره های فعالیت، نسبت زمانیکه گره فعال است در بسیاری از موارد کمتر از۱% میباشد تا عمر شبکه به حد قابل قبولی افزایش پیدا کند.صرفه جویی دیگر ناشی از فعالیت گره به صورت چندگامه به جای یک گامه میباشد که در آن گره ها پیامهای دیگران را به پیش میرانند.روش های تک-گامه مصرف انرژی زیادی را در نواحی جغرافیایی بزرگ دارند.برنامه های کاربردی مورد استفاده در شبکه های حسگر نیز با برنامه های شبکه های عادی متفاوت است.نظارت بر محیط و ردگیری اهداف دو کاربرد رایج برای شبکه های حسگر هستند.هر دو کاربرد درحالت عادی میزان کمی انرژی مصرف میکنند ولی در صورتیکه رویدادی داخل شبکه شود حجم زیادی داده تولید میشود.به دلیل گستردگی کاربردهای شبکه های حسگر ، طراحان پروتکلها به چالش کشیده میشوند زیرا هرکدام از این کاربردها دارای ویژگیهای ترافیکی متفاوتی هستند و معیارهای کارآیی متفاوتی نیز دارند .پیامهای درون شبکه های حسگر معمولا حجم کمتری نسبت به بسته های موجود در شبکه های دیگر دارند.اندازه کوچکتر پیامها باعث افزایش حجم سربار پروتکلها میشود و در عین حال پروتکلها نیاز ندارند که مدت زمان زیادی را رزرو کنند تا پیامهای عادی را انتقال دهند.

باوجود تفاوتهای بسیاری که بین MAC شبکه های حسگر و سایر شبکه ها وجود دارد ،برخی از ویژگیهای آن با سایر شبکه ها یکسان است.بسیاری از روش های ارائه شده بر روی شبکه های موردی ،قابل استفاده برای شبکه های حسگر میباشند زیرا این شبکه ها نیز چند گامه هستند.شبکه های موردی بر روی پویایی شبکه تمرکز میکنند در حالیکه شبکه های حسگر معمولا پویا نیستند و یا پویایی کمی دارند. شبکه های موردی معمولا منابع بیشتری در اختیار دارند و از نظر سطح منابع و قابلیت‌ها بین شبکه های حسگر و شبکه های بیسیم قرار میگیرند.برخی از مسائل مانندHidden Terminal که در شبکه های موردی به گستردگی مورد بررسی قرار گرفته اند در شبکه های حسگر نیز موجود میباشد.بنابراین،این مسائل نیز باید علاوه بر مسائلی که مخصوص شبکه های حسگر میباشند توسط طراحان در نظر گرفته شوند.

۳-۲ محدودیت ها در طراحی پروتکلهای MAC در شبکه های حسگر

MACپروتکلها باید کاربرد های مورد نظررا در عین در نظر داشتن محدودیت منابع فراهمآورند. محدودیت منابع همچنین برروی کاربری هایی که گره حسگر میتواند فراهم آورد نیز تاثیر میگذارد .سخت افزارهای موجود برروی گره های حسگر باید طوری استفاده شوند که عمر شبکه حداکثر گردد.معمولا سه نوع منبع سخت افزاری اصلی بر روی هر گره حسگر وجود دارد : دستگاه فرستنده و گیرنده، پردازشگر و حسگرها. تمامی پروتکلهایMAC از دستگاه فرستنده گیرنده و پردازشگر استفاده میکنند امانوع استفاده آنها بستگی به طراحی و شرایط فعلی گره حسگر دارد. به علاوه ممکن است برخی از طراحی های MACپروتکلها نیاز به مدارهای اضافی برای اجرای درست عملیات خود (مانند دستگاه موقعیت یاب جهانی) داشته باشند. یک طراحی مناسب حداکثر کارایی را در قبال مصرف حداقل منابع فراهم می آورد.بیشتر تحقیقات انجام شده بر روی کاهش میزان مصرف انرژی در فرستنده و گیرنده تمرکز میکند زیرا این قطعه بالاترین میزان مصرف انرژی نسبت به سایر قطعه ها را دارا میباشد.در طراحی ها سعی میشود تا با محدود کردن تعداد برخوردها ، هرز گوش دادن و گوش دادن بیهوده مصرف انرژی را کاهش دهند.برخوردها در شبکه های حسگر همانند سایر شبکه ها یک منبع اتلاف انرژیکه کارایی را نیز پایین می آوردهستند.با اینکه اکثر کاربردها در شبکه های حسگر قادر به تحمل پایین آمدن کارایی هستند زیرا معمولا حجم داده زیادی برای ارسال ندارند ولی نسبت به اتلاف انرژی بسیار حساس هستند و عمر آنها در اثر آن به شدت کاسته میشود.فرستادن دوباره پیام نیاز داردکه گره از دستگاه فرستنده خود در بالاترین حدمصرف انرژی استفاده کند و چندین برابر انرژی که در اصل برای فرستادن پیام لازم بوده است را مصرف کند.برای شبکه های حسگر که نیازی به ارتباطات قابل اطمینان ندارند و پیام هارا دوباره ارسال نمیکنند، برخوردها تاثیر کمتری دارند، ولی از دست دادن داده ها ممکن است به پایین آمدن دقت برنامه های کاربردی منجر شود.در جریان ارسال مجددها ممکن است که برخی از گره ها چندین بار هر پیام را بشنوند در حالیکه فرستنده تنها آن پیام را برای یک گره فرستاده بوده است.در عین حال ممکن است یک گره هنگامی که تشخیص میدهد یک پیام متعلق به او نمیباشد برای جلو گیری از دریافت پیام اضافی و اتلاف انرژی زودتر به حالت خواب وارد شود. برای مثال اگر مقصد پیام در ابتدای پیام قرار دادهشود گره تنها بادریافت همان بخش و تشخیص اینکه این پیام به او تعلق ندارد میتواند به حالت خواب وارد گردد.

اتلاف انرژی هنگامی که هیچ گره ای پیامی ارسال نمیکند ،ولی گره های اطراف برای دریافت پیام تلاش میکنند،نیز رخ میدهد. در این حالت گره های اطراف بیهوده به رسانه گوش میدهند و انرژی آنها تلف میشود.دریافت پیام معمولا به اندازه فرستادن آن انرژی مصرف نمیکند ولی چندین برابر حالت خواب انرژی مصرف میکند.گوش دادن بیهوده به رسانه میتواند درصد بسیار زیادی از مصرف انرژی گره حسگر باشد[۵۶]. یک راه حل رایج برای حل این مساله خواباندن گره توسط یک تایمر برای مدتی میباشد.

باید توجه داشت که حس کردن رسانه که برای فعالیت درست اکثر پروتکلهایMAC مورد نیاز است جزئی از گوش دادن بیهوده به رسانه به حساب نمی آید.حس کردن رسانه جزئی از کارMAC به حساب می آید و برای فعالیت درست آن موردنیاز است بنابراین اتلاف انرژی به حساب نمی آید. در عوض حس کردن رسانه نوعی از سربار پروتکل MAC به حساب می آید.میزان سربار هر پروتکل به طراحی آن بستگی دارد و میتواند بین افزایش نرخ سوییچ تا پیامهای ارتباطی اضافی تغییر کند.سر بارهایی که معمولا در شبکه های حسگر وجود دارد ،پیام های همزمان سازی،premble طولانی تر و پیامهای کنترلی میباشد.سربار وظیفه ای را برای پروتکل انجام میدهد و معمولا عامل تفاوت بین پروتکلهای مختلف هستند.به عنوان مثال پروتکلهایMAC ممکن است که از پیامهای همزمان سازی برای سازمان دادن به گره ها استفاده کنند و یا به گره ها امکان تعیین فاصله شان از یکدیگر را از روی قدرت سیگنال رسیده بدهند.بیشترین سربار پروتکلها استفاده از پیامهای کنترلی برای حل مشکلHidden Terminal وفراهم آوردن قابلیت اطمینان میباشد.

طراحان پروتکلهایMAC در عین حال باید با قابلیت‌هایی که دستگاه فرستنده و گیرنده فراهم می آورد خود را وفق دهند.طراحان معمولا مصرف انرژی دستگاه فرستنده و گیرنده را در حالات مختلف در نظر میگیرند در حالیکه سایر ویژگیها نیز حائز اهمیت هستند.معمولا این دستگاه چه در حالت دریافت پیام و چه در حال دریافت خش باشند به یک اندازه انرژی مصرف میکنند.درصورتیکه دستگاه قادر باشد بامصرف انرژی بسیار کمی به رسانه گوش کندمصرف انرژی بسیار کاهش پیدا میکند که این صرفه جویی معمولا در گوش دادن بیهوده رخ میدهد.این ذخیره انرژی اگرچه هیچگاه به اندازه حالت خواب نیست ولی درصورتیکه درست استفاده شود میتواند عمر شبکه را افزایش دهد.درصورتیکه دستگاه فرستنده و گیرنده قادر باشندکه حالت های مختلف فعالیت را در اختیارMAC قراردهند امکان صرفه جویی انرژی بسیار افزایش یافته و در عین حال دستگاه قادر است در صورت نیاز به سرعت پاسخ دهد.برای مثال اکثر فرستنده و گیرنده ها معمولا دارای یک حالت خواب هستند که در آن تقریبا تمامی مدارها خاموش میشوند.

صرفه جویی انرژی که درحالت خواب به دست می آید در ازای تاخیر قابل توجهی است که در مدت زمانی که طول میکشد دستگاه از حالت خواب به حالت فعال برود که در این مدت دستگاه هیچ کار مفیدی انجام نمیدهد، به وجود می آید.درصورتیکه دستگاه فرستنده برخی از مدارهای اصلی را فعال نگه دارد در عین صرفه جویی در مصرف انرژی دستگاه قادر است که به سرعت به درخواست رسیده پاسخ دهد.در طراحی ها لازم است که طراحان مدت زمان تغییرحالت دستگاه فرستنده را در نظر بگیرند مثلا پروتکل در صورتیکه دارای دوره خوابی کوتاهتر از دوره تغییر حالت باشد گره ممکن است پیامی که برای او فرستاده میشود را از دست دهد.

مشکلات مشابهی ممکن است در اثر استفاده از نوسانگرهای غیردقیق رخ دهد که برای کاهش قیمت گره صورت میگیرد.چندین عامل در دامنه فرستادن گره تاثیر دارد .قدرت ارسال واضح ترین مثال است.فرستادن با توان بالاتر به گره اجازه میدهد یک گره به گره های دورتری در ازای مصرف بالاتر انرژی پیام بفرستد.نوع مدولاسیون نیز میتواند تعیین کننده نرخ ارسال برای نرخ خطای بیتی مشخص باشد. برای مدولاسیونهای پیچیده ممکن است به فرستنده های پیچیده تری که دارای مصرف انرژی بیشتروقیمت بالاتری هستند ،نیاز باشد.نوع مدولاسیونهایی که در شبکه های حسگر به کار رفته اندبسیار گسترده اند ، از مدولاسیونهای ساده مانند On-Off Keing(OOK)وBinary Phase Shift Keying(BPSK) گرفته تاDirect Sequance Spread Spectrum(DSSS) وUltra-Wide Band(UWB).

انواع مدولاسیونها و نرخ انتقالهای مختلف در شبکه های حسگر به کار رفته اند تا مصرف انرژی کاهش پیدا کند[۵۷] [۵۸].Channel Coding راه دیگری را برای افزایش دامنه ارسال و بهبود نرخ خطای بیتی در ازای منابع پردازشی در اختیار قرار میدهد.در نهایت انتخاب نوع فرستنده تعیین کننده نرخ بیت است ولی نوع مدولاسیون و کدگذاری و سربار پروتکل سطح داده قابل انتقال را پایین می آورند.

مشکل دیگری که طراحان پروتکل MAC در شبکه های حسگر باید با آن دست وپنجه نرم کنند محدودیت منابع پردازشی و فضای حافظه در مقایسه با سایر شبکه های بیسیم میباشد.تنها موارد معدودی از MAC های پیشنهاد شده مشکل توان پردازشی را در نظر گرفته اند.پیچیده بودن MAC پروتکل ممکن است مقدار زیادی از وقت پردازشگر رابگیرد و میزان منابع پردازشی و حافظه در اختیار برنامه کاربردی را بسیار محدود کند.در عین حال یکMAC خیلی ساده ممکن است نتواند به اندازه سایر MAC ها مصرف انرژی را کاهش دهد و خود را با شرایط شبکه وفق دهد .در عین حال یک MAC پیچیده ممکن است وظایفی مانند خوشه بندی و تخمین جانمایی شبکه را باهزینه کمتر نسبت به موقعی که این وظایف بدون دخالت MAC انجام شود اجرا کند.پروتکل MAC باید اطمینان حاصل کند که کارایی هایی که فراهم می آورد به درد لایه کاربرد میخورد.نگهداری وضعیت کانال و گره های حسگر توسطMAC میتواند به ذخیره انرژی بیشتر و کارآیی بهتر (مثلا تعداد برخوردها را کاهش میدهد) منجر شود ولی نیاز به حافظه بسیار زیادی دارد که میتواند فعالیت برنامه کاربردی را مختل کند.دسترسی مداوم به حافظه میتواند منجر به بالا رفتن مصرف انرژی در مدارهای حافظه گردد.

دلایل زیادی برای تمرکز طراحان در شبکه های حسگر برروی الگوریتم های توزیع شده به جای الگوریتم های متمرکز وجود دارد[۵۹]. در پروتکلهایMAC این بدین معنی است که روش های رایج اختصاص منابع و مدیریت که بر اطلاعات متمرکز و فراگیر تکیه میکنند در شبکه های حسگر قابل کاربرد نیستند . پایین بودن نرخ ارسال داده و گامهای زیادی که برای انتقال اطلاعات در کل شبکه مورد نیاز است میتواند زمان پاسخ شبکه را بسیار افزایش دهد.

تا زمانیکه واحد مدیریت بتواند خود را به تغییرات وفق دهد ممکن است وضعیت شبکه بدتر شده باشد و یا اینکه عامل تغییر از بین رفته باشد. به علاوه به اشتراک گذاشتن این داده ها مصرف انرژی را بسیار افزایش میدهد چراکه به ارسال و پیشرانی پیامهای کنترلی زیادی نیاز دارد . ولی طراح نیاز دارد که هزینه به اشتراک گذاشتن اطلاعات و سودهای ناشی از آن را تراز کند پروتکلهای MAC لازم است مقیاس پذیری را فراهم کنند تا قابل استفاده در شبکه های چگال با داشتن صدها یا هزاران گره باشند.

در پایان ، ممکن است کهMAC برای اجرای درست کارها نیاز به اطلاعات حسی گره داشته باشد.واحد های حسگر به همراه سایرواحدها مانند مبدل آنالوگ به دیجیتال ، نیاز به منابع پردازشی ، حافظه و توان دارند و قیمت تولید گره را بالا میبرند.یک نمونه MAC هایی را شامل میشود که با بهره گرفتن از اطلاعات سیگنال دریافتی فاصله گره را تخمین میزنند و یا کیفیت ارتباط را اندازه گیری میکنند.مانند سایر موارد مزیت های بدست آمده از جمع آوری این اطلاعات درازای هزینه هایی از جمله قیمت بالاتر و یا مصرف بیشتر بدست می آید. پروتکلهای MAC ی که از اطلاعات موجود گره استفاده میکنند کمترین هزینه را به گره تحمیل میکنند.

۳-۳ منابع اصلی هرز رفتن انرژی در شبکه های حسگر

بر پایه مطالبی که تا کنون مورد اشاره قرار گرفت میتوان چهار منبع اصلی هرز رفتن انرژی را در شبکه های حسگر برشمرد:

برخورد: زمانیکه یک بسته خراب میشود ، آن بسته دور انداخته میشود و لازم است که با فرستادن دوباره ، پیام به مقصد فرستاده شود که هم تاخیر را بالا برده و هم مصرف انرژی را افزایش میدهد.

هرز گوش دادن:گوش دادن به پیام فرستاده شده برای یک گره دیگر منجر به اتلاف انرژی زیادی میشود.

سربار بسته های کنترلی: فرستادن و دریافت بسته های کنترلی نیز باعث هرز رفتن انرژی میشود.

گوش دادن بیهوده: گوش فرا دادن برای دریافت پیامی که هیچگاه فرستاده نشده است.این نوع هرز رفتن انرژی به ویژه در شبکه های حسگر بسیار رایج است.درصورتیکه هیچ چیزی حس نگردد معمولا گره به حالت خواب واردمیشودولی بسیاری از MAC های موجود مانندIEEE802.11 وCDMA باید تمام مدت به رسانه گوش دهند تا هر فرستادن احتمالی را پیدا کنند.

اندازه گیری ها نشان میدهند که هرز گوش دادن حدود ۵۰% تا ۱۰۰% انرژی لازم برای دریافت را مصرف میکند.به عنوان مثال اندازه گیری صورت گرفته در[۶۰] نشان میدهد که نسبت حالات خواب ، دریافت ، فرستادن به این صورت است: ۱:۱٫۰۵:۱٫۴ در اندازه گیری دیگری برای

Digitan Wireless LanModule(IEEE 802.11/2Mb/S) این نسبت ها به این صورت به دست آمده است:[۶۱] ۱:۲:۲٫۵

اکثر شبکه های حسگر طراحی شده اند که برای مدتی طولانی کار کنند بنابراین مدت زمان زیادی را در حالت خواب به سر میبرند. بنابراین گوش دادن بیهوده بخش زیادی از هرز رفتن انرژی را سبب میشود.

۳-۴ مروری بر روی MAC های موجود

پروتکل MAC زمینه تحقیقاتی گسترده ای است که تحقیقات بسیاری در آن برای شبکه های بیسیم حسگر و کم مصرف انجام میگیرد.پروتکلهایی که تاکنون طراحی شده اند میتوان به دو دسته رقابتی و TDMA تقسیم کرد.

MAC های رقابتی: استاندارد IEEE802.11 نمونه یک پروتکل بر پایه رقابت و بر پایه یک تابع هماهنگ توزیع شده میباشد و بر اساس پروتکل تحقیقاتی MACAW ساخته شده است.این پروتکل به دلیل سادگی و مقاومت آن دربرابر مشکل Hidden Terminal بسیار مورد استفاده قرار گرفته است.ولی اندازه گیریهای صورت گرفته نشان میدهد که این MAC دارای مصرف انرژی بسیار بالایی حتی در حالت غیر فعال میباشد که علت اصلی آن گوش دادن بیهوده به شبکه میباشد.PAMAS تلاش میکند این مشکل را تا حدی با مسئله هرز گوش دادن بین گره های همسایه حل کند.PAMAS تلاشی برای حل مشکل گوش دادن هرز نمیکند.

روش های بر پایهTDMA:کلاس دیگری از پروتکلهایMAC روش های مبتنی بر رزرو کردن و زمانبندی میباشد که به آنها روش های بر پایهTDMA گفته میشود.این روش ها به صورت ذاتی مصرف انرژی کمتری نسبت به روش های بر پایه رقابت دارند.زیرا دوره فعالیت واحد رادیویی کاهش یافته و هیچ سرباری به خاطر رقابت و برخورد به وجود نمی آید.درعوضTDMA نیاز دارد که گره ها خوشه های ارتباطی واقعی تشکیل دهند (مانندBluetoothویا LEACH). در اکثر روشها گره هایی که درون یک خوشه قرار میگیرند باید تنها با گره های داخل خوشه ارتباط برقرار کنند .به علاوه هنگامی که تعداد گره های داخل خوشه تغییر میکند تغییر زمانبندی گره ها و طول پنجره برای TDMA بسیار دشوار است.بنابراین مقیاس پذیری آن در مقایسه با روش های برپایه رقابت مناسب نیست.برای مثال درBlutooth حداکثر هشت گره میتوانند فعال باشند.

در[۶۲] یک روش برای خود سامان دهی گره های حسگر ارائه شده است.هر گره یک فریم شبیه TDMA نگهداری میکند که به آن Super Frame گفته میشود و از آن برای زمانبندی ارسال در یک دوره به همسایگان استفاده میشود.به این ترتیب با اینکه Super Frame شبیه یکTDMA Frame میباشد ولی به همسایگان این اجازه داده میشود که همزمان به رسانه دسترسی پیدا کنند.این قابلیت به لطف استفاده از CDMA ویاFDMA به دست می آید.مشکل این روش کاهش استفاده از پهنای باند در اختیار است.برای مثال اگر یک گره تنها قصد ارسال به یک همسایه را داشته باشد قادر به استفاده از دوره های دیگر زمانی برای ارسال به سایر همسایه ها نیست.

در[۵۶] تنظیمات مختلفCSMA مورد بررسی قرار گرفته است و یک روش پویا و سازگار پذیر برای کنترل نرخ ارائه شده است که هدف آن در اختیار دادن عادلانه پهنای باند در اختیار تمامی گره ها در یک شبکه چندگامه است.ازmote ها وTinyOS برای تست انواع مختلف MAC ها استفاده شده است.

دراین قسمت به بررسی کاملتری ازSensor-MAC که ویژه شبکه های حسگر طراحی شده و یک روش بر پایه رقابت میباشد می پردازیم.

۳-۵ S-MAC

درS-MAC تلاش می شود که اتلاف انرژی در تمام مواردی که پیش از این اشاره شد کاهش پیدا کند.اما پیش از اینکه به توضیح جزئیات S-MAC بپردازیم لازم است که پیش فرضهایی که برای شبکه حسگر در نظر گرفته شده است را بهتر بشناسیم.

شبکه حسگر از تعداد زیادی گره با ارسال رادیوی با دامنه کوتاه و مصرف کم تشکیل شده است که دارای ارتباطات چندگامه میباشند.بیشتر ارتباطات بین گره ها به عنوان هم رده صورت میگیرد تا اینکه برای یک ایستگاه مرکزی فرستاده شود.پردازش درون شبکه ای دارای اهمیت بسیاری است به این معنی که پیام ابتدا دریافت، پردازش و ذخیره میشود و سپس برای گره بعدی فرستاده میشود.

واحدهای کوچکتر پیام تنها باعث افزایش تاخیر میگردند.درپایان این فرض وجود دارد که برنامه کاربردی دارای دوره های طولانی بدون فعالیت است و میتواند تاخیر ناشی از به خواب رفتن گره ها را تحمل کند.

۳-۵-۱گوش دادن و به خواب رفتن دوره ای

چنانکه در بالا مورد اشاره قرار گرفت ، در بسیاری از شبکه های حسگر، گره ها برای مدتی طولانی غیر فعال هستندو هیچ رویدادی برای گزارش در شبکه وجود ندارد.در چنین مواقعی نیازی نیست که گره فعال باشد و بی مورد به شبکه گوش کند.S-MAC با خواباندن دوره ای گره این دوره گوش دادن را کاهش میدهد.شمای ساده ای از این روش در شکل۳-۱نمایش داده شده است. هر گره برای مدت زمانی به خواب می رود و پس از بیدار شدن به شبکه گوش میدهد تا ببیند آیا گره ای قصد تماس با او را دارد یا نه . در دوره خواب گره ،رادیوی خود را خاموش میکند و یک تایمر را برای بیدار کردن خود تنظیم میکند.

Listen

Listen

Sleep Sleep Sleep

Time

شکل۳-۱: دوره های کار و خواب گره

به یک چرخه کامل خواب وبیداری یک چارچوب گفته میشود.دوره گوش دادن معمولا براساس متغیرهای لایه فیزیکی وMAC وپهنای باند و پنجره رقابت تعیین میشود و ثابت میباشد.چرخه فعالیت به صورت نسبت دوره گوش دادن گره به طول چارچوب گفته میشود.فاصله بین دوره های گوش دادن بر اساس نیاز برنامه کاربردی تعیین میشود. برای سادگی این مقادیربرای تمام گره ها یکسان میباشد.همه گره ها آزاد هستند که برنامه خواب وبیداری خود را جداگانه انتخاب کنند ولی برای کاهش سربار کنترل ترجیح داده میشود که گره های همسایه با یکدیگر هماهنگ گردند.به این معنی که با یکدیگر به شبکه گوش دهند و با یکدیگر به خواب روند.باید توجه داشت که تمامی گره های همسایه را نمیتوان در یک شبکه چندگامه هماهنگ کرد.چنانکه در شکل۳-۲ نشان داده شده است دو گره همسایهA,B ممکن است دارای زمانبندی متفاوتی باشند در صورتیکه خود را با گره های همسایه C,D هماهنگ کرده باشند.

D B A C

شکل۳-۲:گره های A,B دارای زمانبندی متفاوت هستند وبه ترتیب با گره های C,D هماهنگ می باشند.

گره ها برنامه زمانبندی خود را از طریق پخش یک بستهSYNC به همسایگان آنی خود فرستاده و آنهارا مطلع میکند.

یک گره با همسایگان خود در زمان گوش دادن آنها ارتباط برقرار میکند ، بنابراین گره ها در صورتیکه دارای برنامه متفاوتی نیز باشند قادر به ارتباط با یکدیگر خواهند بود.برای مثال در شکل ۳-۲ اگر گره A بخواهد با گره B ارتباط برقرار کند باید منتظر شود تا این گره دوره گوش دادن خود را آغاز کند.به دوره ای که در آن بستهSYNC فرستاده می شوددوره همزمان سازی گفته می شود.

یکی از ویژگی های S-MAC این است که ساختار شبکه در آن مسطح و یک به یک میباشد.S-MAC به هماهنگی از طریق سرخوشه ها نیاز ندارد.در عوض گره ها جزئی از خوشه های مجازی دارای زمانبندی های مشابهی میباشند ولی ارتباط آنها فقط با هم درجگان خود میباشد.یک مزیت این روش هماهنگی نرم مقاومت آن نسبت به تغییرات در پیکر بندی شبکه در مقایسه با روش های بر پایه خوشه بندی میباشد.

ضعف این روش افزایش تاخیر به دلیل خواب دوره ای گره ها میباشد. به علاوه تاخیر بصورت تجمعی بر روی هرگام افزایش پیدا میکند.

در صورتیکه چندین گره قصد ارسال به یک گره را داشته باشند،همگی سعی میکنند در زمانیکه آن گره شروع به گوش دادن میکند به او پیام ارسال کنند. در چنین شرایطی لازم است که این گره ها با یکدیگر رقابت کنند.بین روش های بر پایه رقابت،۸۰۲٫۱۱ کار مناسبی را برای پیشگیری از برخورد ارائه میدهد.S-MAC از روش های مشابهی از جمله حس کردن رسانه و استفاده ازRTS/CTS برای پیشگیری از مشکل Hidden Terminal استفاده میکند.

هرکدام از این بسته ها دارای یک بخش مدت زمان هستند که مدت زمانباقیمانده تا پایان ارسال را نشان میدهد.در صورتیکه گره ای بسته ای مربوط به گره دیگر را دریافت کند میفهمد که برای چه مدتی باید در این منطقه ساکت باقی بماند.به این مقدار ، بردار تخصیص شبکه یا به اختصارNAV^[71] گفته میشود.و هرگره تایمری را برای آن تنظیم میکند.هربار که تایمر یک تیک داشته باشد از مقدار NAV یک واحد کاسته میشود تا این مقدار به صفر کاهش پیدا کند تا زمانیکه این مقدار به صفر نرسد گره در نظر میگیرد که رسانه اشغال است.به این کار حس کردن مجازی رسانه گفته میشود.

حس کردن رسانه به صورت فیزیکی در لایه فیزیکی و با گوش دادن به شبکه برای ارسال احتمالی همسایگان صورت میگیرد.زمان گوش دادن به شبکه تصادفی میباشد و در پنجره رقابت صورت میگیردتا از برخورد وگرسنگی گره ها خودداری کند.رسانه تنها در حالی خالی در نظر گرفته میشودکه هم گوش دادن فیزیکی و هم مجازی، رسانه را آزاد اعلام کنند.

تمامی فرستندگان کار گوش دادن به رسانه و بررسی آزاد بودن آن را انجام میدهند.اگر فرستنده نتواند که رسانه را در اختیار بگیردبه خواب می رود و هنگامی که گیرنده آزاد و در حال گوش دادن است دوباره بیدار میشود.بسته های پخشی بدون RTS/CTS فرستاده میشوند.بسته هایی که دارای مقصد یکتا هستند باید یک رشته RTS/CTS/DATA/ACK را بین فرستنده و گیرنده طی کنند.پس از رد وبدل موفقیت آمیز RTS,CTS دو گره زمان عادی خواب خود را برای انتقال داده استفاده میکنند.

باداشتن دوره فعالیت کوتاه و روش های رقابتی در بین هر دوره گوش دادن، S-MAC قادر است که به خوبی مسئله اتلاف انرژی در اثر گوش دادن بیهوده و برخوردها را کاهش دهد. در قسمت بعدی ، جزئیات خواب دوره ای گره ها و هماهنگی آن را بررسی میکنیم.

۳-۵-۲ به خواب رفتن زمانبندی شده

به خواب رفتن دوره ای اتلاف انرژی در اثر گوش دادن بیهوده را بسیار کاهش میدهد.درS-MAC گره ها خوابیدن خود را هماهنگ میکنند به جای اینکه تنها بصورت تصادفی به خواب بروند.در این قسمت به بررسی جزئیات به خواب رفتن گره ها میپردازیم.در ادامه به توضیح روشی برای کاهش تاخیر به دلیل خوابیدن گره ها خواهیم پرداخت.

انتخاب و نگهداری زمانبندی ها

پیش از آنکه هر گره ای خواب و بیداری دوره ای خود را آغاز کند ، لازم است که ابتدا زمانبندی ای را انتخاب و آن را با همسایگانش رد و بدل کند.هر گره دارای یک جدول زمانبندی می باشدکه در آن زمانبندی کار همه گره های همسایه ای که میشناسد را در آن نگهداری میکند.گامهای زیر برای انتخاب و ساخت جدول زمانبندی برداشته میشود.

یک گره برای مدت زمان ثابتی گوش میدهد ، که طول آن حداقل به اندازه دوره همزمان سازی میباشد.درصورتیکه هیچ زمانبندی را از گره های اطراف نشنود، بلافاصله زمانبندی خود را انتخاب کرده و آن را دنبال میکند.در این ضمن گره برنامه خود را با فرستادن یک بستهSync به همسایگان خود اعلام میکندکه فرستادن این بسته SYNC یک روند عادی رقابت را طی میکند.این روش دسترسی تصادفی شانس برخورد بسته ها را کاهش میدهد.

در صورتیکه یک گره پیش از انتخاب و فرستادن برنامه خود برنامه ای را از گره های همسایه دریافت کند ، برنامه اعلام شده توسط آن گره را به عنوان برنامه خود انتخاب میکند.سپس این گره تلاش میکند که برنامه خود را در نوبت بعدی برای بقیه بفرستد.

در صورتیکه گره ای پس از اینکه زمانبندی خود را انتخاب و اعلام کرده است ، زمانبندی دیگری را دریافت کند دوحالت رخ میدهد:درصورتیکه همسایه دیگری نداشتهباشد زمانبندی فعلی خود را دور انداخته و زمانبندی دریافتی را انتخاب میکند.درصورتیکه برنامه فعلی را نیز از همسایه ای دریافت کرده است باید در زمان گوش دادن هردو همسایه ها بیدار شده و به شبکه گوش فرا دهد.

برای درک بهتر این الگوریتم شبکه ای را در نظر بگیرید که در آن تمامی گره ها میتوانند پیامهای یکدیگر را دریافت کنند.گره ای که زودتر از بقیه شروع بکار کند باید زمانبندی را زودتر از سایرین انتخاب کند و ارسال زمانبندی آن بقیه گره ها را با آن هماهنگ میکند.دزصورتیکه یک یا چند گره همزمان شروع به کار کنند همگی گوش دادن اولیه را با یکدیگر به اتمام رسانده و بصورت مستقل همزمان برنامه یکسانی را انتخاب میکنند.فرقی نمیکند که کدام گره در رقابت موفق شده وSYNC را میفرستد زیرا در نهایت همین پیام همه گره های دیگر را همزمان میکند.

ولی درصورتیکه دو گره قادر نباشند که پیام همدیگر را بشنوند ممکن است که زمانبندی متفاوتی را انتخاب کنند. در این صورت گره هایی که در دامنه هر دو زمانبندی هستندباید هر دو زمانبندی را قبول کنند.برای مثال گره های A,B باید در زمان گوش دادن هر دو زمانبندی بیدارشوند.(شکل۳-۲) به این ترتیب در صورتیکه گره ای قصد فرستادن یک بسته پخشی را داشته باشد ، تنها لازم است که این کار را یکبار انجام دهد.ضرر این روش این است گره های مرزی وقت کمتری برای خواب دارند ومصرف انرژی بالاتری دارند.

راه دیگر آن است که گره مرزی تنها یکی از دو زمانبندی را دنبال کند و چون زمان بیداری گره دیگر را میداند میتواند با او ارتباط برقرار کند ولی برای بسته های پخشی لازم است که بسته را دوبار ارسال کند.مزیت این روش این است که گره های مرزی نیز دارای همان الگوی خواب و بیداری مانند سایر گره ها میباشند.

انتظار میرود که زمانبندی های چندگانه کمی در شبکه بوجود بیایند زیرا هرگره تلاش میکند که زمانبندی که به او داده شده است را دنبال کند.ولی ممکن است که یک گره نتواند گره همسایه خودرا به برخی از دلایل پیدا کند.بستهSYNC همسایه ممکن است که به دلیل برخورد یا اختلال خراب شده باشد.گره همسایه ممکن استبه دلیل اشغال بودن رسانه بستهSYNC را خیلی دیر فرستاده باشد.در صورتیکه یک گره در مرز دو زمانبندی باشد ممکن است یکی از آنها را دریافت نکنددر صورتیکه زمانبندی دو دسته باهم همپوشانی نداشته باشد.

برای آنکه دو گره همسایه برای مدت نامحدودی از یکدیگر بی خبر باقی نمانند (زمانی که دارای دو زمانبندی کاملا مجزا هستند.)،S-MAC از روش کشف دوره ای همسایه ها استفاده میکندکه در آن یک گره هر از چند گاهی برای کل دوره همزمان سازی بیدار می ماندو به رسانه گوش فرا میدهد.

بسامد کشف دوره ای همسایه ها بستگی به تعداد همسایه های گره دارد، در صورتیکه گره ای دارای همسایه ای نباشد با بسامد بیشتری نسبت به حالتی که دارای همسایه میباشد به کشف همسایگان میپردازد.از آنجاکه مصرف انرژی در این حالت زیاد میباشد ، اینکار نباید زیاد انجام شود.در پیاده سازیS-MAC طول دوره همزمان سازی ۱۰ثانیه میباشدوهر گره در صورتیکه حداقل دارای یک همسایه باشد اینکار را هردو دقیقه انجام میدهد.

حفظ زمانبندی

از آنجا که گره های همسایه برنامه زمانبندی خود راهماهنگ میکنند،خطای راندگی ساعت گره ها ممکن است که همزمانی گره ها را برهم زند.از دو روش برای مقاوم سازی همزمانی گره ها در برابر چنین خطایی استفاده میشود.نخست آنکه تمامی زمان های ارسال شده نسبی هستند ونه مطلق. دوم آنکه، دوره گوش دادن به صورت مشخصی از نرخ خطای راندگی ساعتها بیشتر است. برای مثال دوره گوش دادن گره۰٫۵ ثانیه است که ده برابر بیشتر از خطای راندگی در حالت عادی است.در مقایسه با روش های TDMA که دارای پنجره های بسیار کوچکی هستند،S-MAC به همزمان سازی بسیار سست تری نیاز دارد.

با آنکه طولانی بودن دوره گوش دادن گره ها نسبت به خطای راندگی تا حد زیادی مشکل همزمان سازی را حل میکند ولی گره ها نیاز دارند هراز چند گاهی زمانبندی خود را برای دیگران ارسال کنند تا از خطای راندگی در دراز مدت جلوگیری شود.دوره همزمان سازی میتواند به نسبت بلند باشد.اندازه گیری های انجام شده برروی یک شبکه حسگر آزمایشی نشان میدهد که خطای راندگی بین دو گره بیشتر از ۰٫۲میلی ثانیه نمیشود.

چنانکه پیش ازاین اشاره شد، به روز رسانی زمانبندی ها از طریق فرستادن بسته SYNC صورت میگیرد.بستهSYNC بسیار کوچک بوده و تنها دارای آدرس فرستنده و زمان بعدی خواب او میباشد.زمان بعدی خواب نسبی بوده و نسبت به زمان فرستادن بستهSYNC اندازه گیری می شود.هنگامیکه گیرنده بسته را دریافت میکندمدت زمان ارسال بسته را از زمان درون بسته کم کرده و زمان درون بسته را برای زمانبندی استفاده میکند.

برای اینکه گره ها قادر باشند که هم بسته های SYNC وهم بسته های داده را دریافت کنند، دوره گوش دادن را به دو قسمت تقسیم میکنیم.قسمت اول برای بسته هایSYNC بوده و قسمت دوم برای بسته های داده میباشد.چنانکه در شکل۲-۳دیده می شودهر پنجره رقابت دارای دوره های بسیاری برای فرستادن بسته ها توسط فرستنده میباشد.برای مثال،درصورتیکه گره ای قصد ارسال یک بسته SYNC را داشته باشد، گوش دادن به رسانه را زمانی که دوره گوش دادن گیرنده آغاز میشودشروع میکند.بصورت تصادفی یک دوره را برای پایان گوش دادنش به رسانه انتخاب میکند.در صورتیکه هیچ ارسالی تا پایان آن دوره کشف نشود، او در رقابت برنده شده و بستهSYNC را ارسال میکند.همین روند هنگامیکه بسته های داده فرستاده میشوند دنبال میشود

شکل ۳-۳:زمانبندی گیرنده وچندفرستندهCS به معنای گوش دادن به رسانه است.

شکل۳-۳ رابطه بین سه حالت که در آن یک فرستنده به یک گیرنده پیام میفرستد را نشان میدهد.فرستنده ۱ تنها یک بسته SYNC میفرستد.فرستنده ۲ یک بسته داده میفرستد.فرستنده ۳ هم بسته SYNC و هم بسته داده میفرستد.

گوش دادن سازگار پذیر

روش خواب دوره ای قادر است که گوش دادن بیهوده را تاحد زیادی هنگامی که ترافیک شبکه پایین است بهبود ببخشد.اما هنگامیکه رویدادی در شبکه رخ میدهد لازم است که رویداد به سرعت در طول شبکه فرستاده شده و به مقصد برسد.هنگامیکه هر گره به دقت تنها دوره خواب خود را دنبال کند، تاخیری بالقوه در هر گام بر روی بسته به وجود می آید که به طول پنجره گره ها بستگی دارد.بنابراین ما روشی را برای بردن گره ها از حالت غیر فعال به فعال در چنین مواردی ارائه میدهیم.

S-MAC روش مهمی را بانام گوش دادن سازگارپذیر ارائه میدهد تا تاخیر ناشی از خوابیدن گره ها در شبکه چندگامه را کاهش دهد.ایده اصلی این است که گره ای که ارتباط گره دیگر را میشنود(در حالت ایده آل تنهاRTS,CTS) برای مدت کوتاهی در انتهای ارتباط بیدار باقی بماند.به این ترتیب،درصورتیکه این گره ،گام بعدی بسته باشد، گره قادر است آن را بلافاصله برای اوبفرستد.درصورتیکه گره چیزی را دریافت نکند به خواب رفته و در زمانبعدی گوش دادن زمانبندی شده بیدار میگردد.

با نگاه به زمانبندی ارائه شده در شکل۳-۳ در صورتیکه گام بعدی همسایه گیرنده باشدباید پیامCTS که توسط گیرنده فرستاده میشود را دریافت کند.بنابراین هم همسایگان گیرنده و هم فرستنده میتوانند پایان دوره انتقال داده بین دو گره را به دست آورده و در پایان آن بیدار شوند.

مدت زمان گوش دادن سازگارپذیر شامل دوره لازم برای بستهSYNC نمیشود.(شکل۳-۳).بسته هایSYNC تنها در زمان مربوط به آن فرستاده میشوند تا اطمینان حاصل شود که همسایگان آنهارا دریافت میکنند.برای اینکه برای بسته های SYNC اولویت قایل شویم، گوش دادن سازگار پذیر و فرستادن داده در صورتیکه مدت زمان طی شده از اتمام ارسال تا زمان گوش دادن طبیعی کوتاهتر از دوره گوش دادن سازگار پذیر باشد، صورت نمیپذیرد.

لازم به ذکر است که همیشه گره بعدی قادر به شنیدن ارسال قبلی نمیباشد به ویژه که ارسال قبلی از طریق گوش دادن سازگار پذیر ونه برسر زمانبندی از پیش تعیین شده ، انجام شده باشد.بنابراین درصورتیکه گره در دوره گوش دادن تطبیقی RTS را فرستاده باشد ممکن است که پاسخCTS را دریافت نکند.دراین صورت به خواب رفته و برنامه خواب از پیش برنامه ریزی شده را دنبال میکند.

۳-۶ برخی دیگر ازMAC های رایج در شبکه های حسگر

T-MAC[20] چرخه فعالیت پویا را معرفی میکند ، که با به پایان بردن پویای دوره فعالیت کار میکند.به این صورت که برای مدت کوتاهی در ابتدای دوره فعالیت بیدار بوده و درصورتیکه پیامی دریافت نشود به خواب میرود.

B-MAC[63] یک پروتکلCSMA برای فراهم آوردن رابطی انعطاف پذیر برای دستیابی به فعالیت کم مصرف ارائه میکند.B-MAC از روش های تخمین خالی بودن کانال وbackoff بسته ها برای وساطت دسترسی به کانال ، از اعلام وصولهای لایه لینک برای به دست آوردن قابلیت اطمینان و از گوش دادن کم مصرف برای ارتباط کم مصرف استفاده میکند.این روش به نرخ داده بالاتر و کارایی انرژی بالاتری نسبت به S-MAC وT-MAC دست پیدا میکند.B-MAC در واقع یک پروتکل در لایه لینک است که قابلیت‌هایی مانند سازماندهی، همزمان سازی،و مسیریابی برروی آن قرار میگیرند.S-MAC وT-MAC به عنوان سرویس هایی که از خدمات B-MAC استفاده میکنند قابل پیاده سازی هستند.

Z-MAC[64] یک روش ترکیبی است که سعی میکند از مزایای هردو روش CSMAوTDMA بهره ببرد.این روش از یک پیاده سازی توزیع شده RAND استفاده میکند تا بازه های زمانی را بین گره ها توزیع کند.گره ها میتوانند در بازه های زمانی مربوط به خودشان و سایر گره ها پیام بفرستند ولی صاحب بازه دارای اولویت میباشد.آزمایشات نشان میدهد که این روش میتواند به نرخ داده بالاتری نسبت بهB-MAC برسد.

D-MAC[65]یکMAC پروتکل دارای مصرف انرژی و تاخیر مناسب میباشد که ویژه شبکه های حسگری طراحی شده است که دارای ساختار درختی بوده و در آنها داده ها از چند منبع جمع شده وبرای یک مقصد از طریق درخت فرستاده میشود.در این روش یک زمانبندی خواب و بیداری پلکانی برای گره ها در طول درخت پیشنهاد شده است تا تاخیر ناشی از به خواب رفتن گره ها را کاهش دهد.این روش به همزمان سازی محلی بین گره ها نیاز دارد.

P-MAC[66]روش دیگری برای تغییر پویا در چرخه فعایت گره ها ارائه میکند.زمانبندی براساس ترافیک خود گره و همسایه های آن تعیین میشوند.درP-MAC گره اطلاعات لازم درباره فعالیت همسایه هایش را از طریق الگوها دریافت میکند.

فصل۴:الگوریتم پیشنهادی

۴ مقدمه

در این قسمت به ارائه یک پروتکل MAC رقابتی می پردازیم که به طور خاص برای مسیریابی انتشاری در گره های حسگر طراحی شده است.یکی از چالش ها در شبکه های حسگر تنظیم رابطه بین تاخیر و مصرف انرژی در شبکه های حسگر می باشد.از آنجا که منبع انرژی گره ها در شبکه های حسگر محدود است از خواب دوره ای برای افزایش طول عمر گره ها استفاده می شود که باعث افزایش تاخیر در شبکه می گردد. برای حل این مشکل ،ما از اطلاعات مسیریابی برای تنظیم چرخه فعالیت گره ها بسته به نیاز برنامه کاربردی استفاده میکنیم.پیام های کنترلی مورد استفاده در روش مسیریابی انتشار هدایت شده برای تنظیم چرخه فعالیت گره استفاده می شوند. در عین حال استفاده بیش از حد از برخیاز گره ها ممکن است منجر به تمام شدن زود هنگام باتری آن ها شده و شبکه را تکه تکه کند.برای حل این مشکل ما از روشی برای تنظیم بار موجود برروی گره ها استفاده می کنیم.در ادامه به بررسی طراحی الگوریتم پیشنهادی پرداخته و آن را با پروتکلهای IEEE802.11 وS-MAC که پایه اصلی این طراحی هستند مقایسه می کنیم.پروتکل پیشنهادی قادر است به تاخیری تا پنجاه برابر بهتر ازS-MAC دست پیدا کند و در عین حال از کارایی در مصرف انرژی و تحویل متوازن بسته ها اطمینان حاصل کند.

۴-۱ طراحی بین لایه ای

برای اینکه بتوان چرخه فعالیت گره ها را متناسب با نیاز برنامه کاربردی به خوبی تنظیم کرد،نیاز به اطلاعات لایه های بالاتری داریم.به عنوان مثال داده هایی در مورد نوع ترافیک،حجم آن و ویژگی های مورد نظر برنامه کاربردی می توانند در این زمینه بسیار کمک کننده باشند.ازآنجا که گره ها دارای حافظه و منابع بسیار محدود انرژی هستند به یک طراحی کارا و در عین حال ساده نیاز است.بنابراین بهترین راه برای به دست آوردن اطلاعات مورد نظر استفاده از داده های لایه کاربرد و مسیریابی می باشد تا بتوان چرخه فعالیت گره ها را متناسب با آن تنظیم کرد. طراحی بین لایه ای اجازه بهینه سازی فعالیت گره ها را در شبکه می دهد.

چنانکه اشاره شد روش انتشار هدایت شده یک روش داده محور برای حل مسئله مسیریابی در شبکه های حسگر ارائه می دهد.در انتشار هدایت شده تمامی گره ها کاربرد-آگاه هستند.انتشار هدایت شده ازچندین عنصر استفاده می کند.پیام های علاقه مندی ،پیام های داده ای،گرادیانها،پیام های تقویت.پیامهای علاقمندی دارای زوج های خصوصیت – مقدار می باشند وباهم یک مولفه را تعیین می کنند.گره ای که این بسته را وارد شبکه می کند به عنوان سینک شناخته می شود.سینک به صورت دوره ای پیام علاقه مندی میفرستد.

هر گره دارای یک ذخیره علاقه مندی می باشد که در آن علاقه مندی های متفات نگهداری می شوند.گره هایی که یک علاقه مندی را دریافت میکنند آن را به ذخیره خود اضافه کرده و دوباره برای همسایگان خود پخش می کنند.پیام علاقه مندی جدید به نظر می رسد که توسط خود گره فرستنده تولید شده است.در صورتی که رویدادی با یکی از علاقه مندی ها جور شود،گره شروع به فرستادن بسته های داده می کند.به این گره،گره منبع گفته میشود.

با دریافت این بسته ها در گره سینک،سینک شروع به فرستادن بسته های تقویتی به همسایگان انتخاب شده خود می کند.بسته های تقویتی باعث بالا رفتن مقدار گرادیان در همسایه ها در جهت فرستنده می شوند.این روند رویدادهای محلی باعث به وجودآمدن راهی از سوی منبع به سینک می شود.چندین راه ممکن است از این طریق بوجود آیند که برای حذف آنها گره منبع برای آنها پیام های تقویت منفی می فرستد و به این ترتیب یک مسیر بین دو گره بوجود می آید .

روش انتشار هدایت شده در مصرف انرژی بسیار کارا میباشد زیرا مسیرها تنها در صورت نیاز تشکیل شده و نیازی به حفظ ساختار کلی شبکه نیست.تنها از فرآیندهای محلی برای تشکیل مسیر به سوی مقصد استفاده می شود.به علاوه از آنجا که ارتباطات تنها بین گره های همسایه صورت می گیرند و گره ها کاربرد-آگاه هستند ،هر گره می تواند وظایف ذخیره سازی و تراکم را انجام دهند.

بیشتر مقالات ارائه شده برروی انتشار هدایت شده از۸۰۲٫۱۱ به عنوان MAC خود استفاده کرده اند زیرا تاخیر زیادS-MAC می تواند مانع از فعالیت مناسب فرآیندهای مسیریابی شود.

۴-۲ الگوریتم پیشنهادی

ما طراحی بین لایه ای جدیدی پیشنهاد می کنیم که در آن تاخیر ناشی از خواب دوره ای گره ها بسیار کاهش می یابد.اطلاعات لایه مسیریابی و کاربرد مورد استفاده قرار میگیرند تابهMAC اجازه دهند که خود را بهتر تنظیم نماید.ما از S-MAC به عنوان چهارچوب اصلی کار خود استفاده می کنیم و چرخه فعالیت آن را به صورت پویا تغییر می دهیم.

در این رویه ما از اطلاعات مسیریابی برای کاهش مدت خواب گره هایی که در کار مسیر یابی و فرستادن داده دخیل هستند استفاده می کنیم.دوره خواب گره هایی که توسط انتشار هدایت شده تقویت شده اند کاهش می یابد.گره هایی که تقویت نشده اند زمانبندی فعلی خود را حفظ میکنند .این کار باعث میشود که تاخیر در گره هایی که در کار مسیریابی و انتقال داده شرکت دارند بسیار پایین می آید (در قبال بالارفتن مصرف انرژی)درحالیکه گره هایی که دراین امر دخالتی ندارند هیچ تغییری نمیکنند.

در روش انتشار هدایت شده گره سینک به صورت دوره ای پیام علاقه مندی را ارسال میکند.در صورتیکه گره ای رویدادی که با علاقه مندی ارسال شده جور باشد را پیدا کند ، بصورت یک منبع داده در آمده و شروع به دادن داده های اکتشافی میکند.این پیام ها به سوی سینک پیش رانده می شوند.هنگامی که سینک این داده ها را دریافت کند، شروع به فرستادن تقویت مثبت میکند.پیام های تقویت مثبت مانند پیامهای علاقه مندی هستند تنها دارای وقفه کمتری می باشند.هر گره گرادیان خود را با گرادیان بسته تقویت مثبت کرده و در صورتیکه که گرادیان بسته رسیده دارای وقفه کوتاهتری باشد، گرادیان را به مقداردریافتی تغییر می دهد.درروش ما این پیام ها باعث کاهش دوره خواب در لایه MAC نیز میگردد. پیام های تقویت منفی دارای اثری کاملا برعکس بر روی دوره خواب MAC می باشند. از پیام های تقویت منفی در انتشار هدایت شده برای کاهش تعداد مسیرها و تعمیر مسیرها استفاده می شود.روش های مختلفی برای پیاده سازی پیام های تقویتی پیشنهاد شده اند(Timeout,Gradient,Reduction,…) هر روشی که برای تولید پیام های تقویت منفی به کار رود باعث افزایش دوره خواب در لایهMAC گره هانیز خواهد شد.

هدف این است که بتوان از ویژگیهای صرفه جویی در مصرف انرژی درS-MAC استفاده کرده و به تاخیر بسیار کمتری در مقایسه با آن دست پیدا کنیم.گره هایی که توسط انتشار هدایت شده تقویت نشده اند دارای زمانبندی کار مشابهی باS-MAC هستند.گره هایی که تقویت شده اند به صورت نمایی دوره کار خود را افزایش می دهند، بنابراین هنگامی که مسیر تشکیل می شود این گره ها تقریبا همیشه فعال بوده و دارای تاخیری مشابه به۸۰۲٫۱۱ می باشند.

گره هایی که در مسیر قرار ندارند زمانبندی فعالیت خود را تغییر نداده ومصرف انرژیمشابهS-MAC دارند . ولی گره های درگیر مسیریابی دارای دوره فعالیت زیادی بوده و میتوانند تاخیر بسیار پایینی را فراهم آورند .

در صورتیکه مسیری خراب شده ویا کیفیت آن پایین آید، مسیر توسط انتشار هدایت شدهتقویت منفی می شود و چرخه فعالیت گره ها در آن کاهش پیدا می کند.بنابراین درصورتیکه گره ها از مسیر خارج شوند، به زمانبندی عادی خود باز گشته و مصرف آنها به حالت عادی باز می گردد.بدین ترتیب کارایی در مصرف انرژی حداکثر می گردد.

S-MAC بر این پایه فعالیت می کند که گره های همسایه همزمان بیدار شده و به اینترتیب هستند که پیام های پخشی یکدیگر(SYNC,RTS/CTS) را بشنوند.در صورتی که همزمانی گره های همسایه به هم بخورد ، برقرار کردن ارتباط میان آنها غیر ممکن می شود.بنابراین کاهش پویایی چرخه فعالیت گره ها ممکن است همزمانی میان گره های همسایه را برهم بزند.برای حل این مشکل دوره خواب گره ها را طوری تغییر می دهیم که همچنان با گره های همسایه خود هماهنگ باشند.برای انجام این کار تغییرات در چرخه فعالیت گره ها بصورت نمایی اجرا می شوند. دوره خواب گره ها در S-MAC بسیار طولانی تر از دوره فعالیت آن است بنابراین این امکان وجود دارد که آن را طوری تقسیم کنیم که هر پنجره به دو پنجره مستقل تبدیل شود .هر پنجره به دو پنجره دارای قسمتهایSYNC,RTS/CTSوخواب تبدیل می شود.به عنوان مثال در صورتیکه چرخه فعالیت ۱۰%است (مقدار از پیش تعیین شده برایS-MAC) چرخه فعالیت بعد از دریافت تقویت مثبت به ۲۰% افزایش پیدا می کند.هر تقویت مثبت به این ترتیب چرخه فعالیت را دو برابر میکند تا به حداکثر ممکن (دراین مورد ۸۰%)دست پیدا کنیم. این فرایند در شکل ۴-۱ نشان داده شده است

Before

Sleep

Listen

Listen

Sleep

After

Listen

Sleep

Listen

Sleep

Listen

شکل۴-۱:تغییر در چرخه فعالیت گره ها هنگامی که پیام تقویت دریافت می کنند،آغاز دوره گوش دادن هم چنان همزمان است.

افزایش چرخه کار گره ها همزمانی گره های همسایه را برهم نمی زند.گره هایی که برروی یک مسیر قرار دارنددارای چرخه فعالیت مشابهی می باشند.این گره ها بیشتر بیدار شده و در نتیجه دارای فرصت بیشتری برای فرستادن داده هستند که این امر به پایین بودن تاخیر و افزایش پهنای باند می انجامد.این گره ها همچنان قادر هستند با گره هایی که روی مسیر قرار ندارند و چرخه فعالیت خود را تغییر نداده اند ارتباط داشته باشند.از آنجا که چرخه فعالیت به صورت نمایی افزایش پیدا کرده است، این گره ها همچنان دارای چرخه بیداری همزمان هستند.بعد از دریافت یک تقویت مثبت ،هردو بیدار شدن گره با یک بیدار شدن گره های همسایه با دوره فعالیت معمولی همزمان می گردد.بنابراین گره قادر است به صورت طبیعی با این گره ها ارتباط برقرار کند.

گره های درگیر مسیر یابی رفتاری مشابه به IEEE802.11 نشان می دهند در حالیکه سایر گره ها رفتاری مشابه S-MAC دارند.

از آنجا که پیام های کنترلی که توسط انتشار هدایت شده فرستاده می شوندبرای تنظیمپویایی چرخه کار گره ها استفاده می شوند، هیچ سربار پیامی به وجود نخواهد آمد.

۴-۳ تنظیم بار

گره هایی که برای مدتی طولانی درگیر کار مسیریابی وانتقال داده بوده اند،زودتر از سایر گره ها در شبکه خراب می شوند.این گره ها در اثر چرخه کار بالاتر دارای مصرف انرژی بیشتر نسبت به سایر گره ها هستند.از کار افتادن این گره ها می تواند منجر به تکه تکه شدن شبکه شود.این امر میتواند اتصال شبکه را ازبین ببرد و برخی از اثرات ناخواسته دیگر ازجمله کاهش پوشش شبکه را منجر شود.در شبکه های چگال که ممکن است چندین مسیربین دو گره وجود داشته باشد،می توان از مسیرهای گوناگون برای توزیع بار استفاده کرد و مصرف انرژی را بین گره های مختلف تقسیم نمود.[۷۶]نمونه یک روش مسیریابی بر پایه انتشار چند مسیره می باشد.انتشار هدایت شده بصورت طبیعی کاندیدای خوبی برای مسیریابی چندگانه به حساب می رود.درحقیقت در انتشار هدایت شده،ابتدا چند مسیر بین دو گره بوجود آمده و سپس انتشار هدایت شده از طریق پیام های تقویت منفی تعداد آنها را کاهش می دهد.

در طراحی بین لایه ای،ما از این ویژگی انتشار هدایت شده استفاده می کنیم تا با تنظیم چرخه فعالیت گره ها بار را بر اساس باقی مانده انرژی گره ها روی گره ها توزیع نماییم.برای هر گره یک حد بحرانی انرژی تعریف می شود.هر گاه سطح انرژی یک گره به این حد بحرانی برسد،گره چرخه فعالیت خود را به شدت کاهش میدهد که باعث می شود کیفیت انتقال داده به گره سینک کاهش پیدا کند.این کاهش کیفیت توسط انتشار هدایت شده کشف شده و یک فرایند تعمیر محلی آغاز میگردد.در این فرایند تعمیر محلی هنگامی که گره ای کاهش کیفیت را کشف میکند(یا از طریق کشف این نکته که نرخ انتقال داده از گره سرچشمه کاهش یافته است ، یا با رسیدن پیامهایی که قبل ندیده است توسط گره های دیگر) قوانین تقویت برای پیدا کردن مسیر دیگر را به کار میبندد.

این زنجیره رویدادهای محلی منجر به تشکیل مسیردیگری میشود که این مسیر دیگر شامل گره ای که به حد بحرانی انرژی خود رسیده است نمیگردد. در شبکه های چگال که تعداد زیادی گره وجود دارند که میتوانند جایگزین گره ای که به حد بحرانی انرژی رسیده است شوند،می توان ازاین روش برای توزیع بار برروی گره هایی که دارای انرژی زیادی هستند استفاده کرد.

برای فراهم آوردن کنترل بیشتر بر روی سطح انرژی های مختلف ما چندین سطح کاهش چرخه فعالیت تعریف می کنیم.هنگامی که گره ای به یک سطح بحرانی از پیش تعیین شده می رسد،چرخه فعالیت خود را به نصف چرخه فعالیت اصلی خود در دوره به کاراندازی کاهش می دهد.این امر منجر به تغییر شدیدی در چرخه فعالیت گره ای که تاکنون در انتقال داده دخیل بوده و چرخه فعالیت بالایی داشته است می شود.برای حفظ همزمانی بین گره ها کاهش چرخه فعالیت گره ها نمایی است(شبیه به پیامهای تقویت).هربار که گره به سطح بحرانی جدیدی برسد یک کاهش چرخه فعالیت صورت می گیرد.برای مثال،اگر سه سطح انرژی وجود داشته باشد، چرخه فعالیت گره به یک هشتم چرخه اولیه تغییر کاهش پیدا میکند.

سطوح بحرانی انرژی گره ها را می توان بسته به ترافیک شبکه و نیازهای برنامه کاربردی تعیین کرد.اگر بالا بودن نرخ انتقال داده برای ما مهمترین عامل است،باید سطح انرژی بحرانی پایینی در نظر گرفت تا انتقال داده حداکثر باشد که این امر به بالا بودن مصرف انرژی و کوتاهی عمر شبکه منجر می شود.ولی اگر طول عمر شبکه هدف نهایی می باشد،سطح بحرانی بالایی باید در نظر گرفته شود جلوی از کار افتادن زودهنگام گره ها گرفته شود.این سطوح انرژی را میتوان با تغییر شرایط و نیازمندیهای شبکه تغییر داد و شبکه را انعطاف پذیر نمود.

۴-۴ نتایج شبیه سازی

در این قسمت به مقایسه نتایج پروتکل خود با پروتکلهای S-MAC و۸۰۲٫۱۱ می پردازیم.برای شبیه سازی از شبیه سازNS2 استفاده شده است.تاخیر و مصرف انرژی یک برنامه انتشار هدایت شده برروی سه پروتکل مقایسه می شود.انرژی اولیه گره ها ۳۰۰۰ژول می باشد.برای مقایسه مصرف انرژی هر پروتکل از مدل مصرف انرژی کارت شبکه Cabletron 802.11 در حالت انتقال ، دریافت،غیرفعال و خواب استفاده می کنیم.مصرف انرژی در حالت های مختلف در جدول شکل ۴-۱ آمده است.

Sleeping	Idle	Receive	Transmit
۱۳۰ mW	۸۳۰ mW	۱۰۰۰ mW	۱۴۰۰ mW

جدول ۴-۱:جدول مصرف کارت شبکهCabletron در حالات مختلف

توزیع گره ها به صورت توری بوده و سینک و منبع در دوانتهای قطر قرار دارند.در۸۰۲٫۱۱ همه گره ها تمام مدت در حال کارهستند در نتیجه این روش دارای بالاترین مصرف انرژی می باشد.S-MAC از سوی دیگر دارای دوره خواب ثابت و طولانی بوده و در نتیجه بالاترین تاخیر و پایین ترین مصرف انرژی را دارد.در الگوریتم پیشنهادی ، گره های درگیر مسیریابی دارای چرخه فعالیت بالا هستند تا انتقال داده با تاخیر کم را ممکن سازند در نتیجه دارای مصرف انرزی بالایی می باشند. گره هایی که در مسیر قرار ندارند دارای چرخه کاری کوتاهی هستند و مصرف انرژی مشابهS-MAC دارند از آنجا که گره های درگیر انتقال داده ، خواب کوتاه مدت دارند،تاخیر قابل مقایسه با۸۰۲٫۱۱ می باشد.

پیش از تشکیل مسیر ،تاخیرS-MAC وپروتکل پیشنهادی مشابه است.زیرا هیچ پیغام تقویت مثبتی فرستاده نشده است ولی هر چه مسیر تقویت می شود،تاخیر مسیر از منبع به سینک به شدت کاهش می یابد.درفاز تشکیل مسیر برخی گره ها ممکن است بی دلیل تقویت گردند که باعث میشود چرخه فعالیت خودرا افزایش دهند.این گره ها هنگامی که تشکیل مسیر کامل شد و بصورت منفی تقویت شدند به چرخه عادی فعالیت خود باز میگردند.

شکل ۴-۲ میانگین تاخیر سه پروتکل را هنگامی که اندازه شبکه تغییر کند مورد بررسی قرار می دهد.S-MAC رفتاری غیر قابل پیش بینی را از خود نشان می دهد وتاخیر IEEE802.11 همیشه نزدیک صفر باقی می ماند.تاخیر پروتکل پیشنهادی بسیار از S-MAC پایینتر بوده و رفتار باثبات تری را از خود نشان میدهد.از آنجا که گره ها همیشه در پروتکل پیشنهادی فعال نیستند،هر گام تاخیری را به بسته ها اعمال می کند.بنابراین با افزایش تعداد گام تاخیر اندکی افزایش پیدا می کند.

شکل۴-۲:میانگین تاخیر برای اندازه های مختلف شبکه

شکل۴-۳ به مقایسه مصرف انرژی درS-MAC،IEEE802.11 وپروتکل پیشنهادی می پردازد.IEEE802.11 بالاترین مصرف انرژی را داراست و گره ها بسیار زودتر از سایر روش ها از کار میفتند. پروتکل پیشنهادی دارای مصرف انرژی بالاتری نسبت به S-MAC می باشد،زیرا گره های درگیر انتقال داده مصرف انرژی بالاتری دارند و دارای چرخه کار بالاتری نسبت به گره های عادی میباشند.

شکل۴-۳:مقایسه مصرف انرژی در روش های مختلف(مقدار انرژی در گره های درگیر انتقال داده)

شکل ۴-۴ به مقایسه میانگین انرژی باقیمانده شبکه می پردازد.IEEE802.11 چنانکه انتظار می رود دارای بالاترین مصرف انرژی می باشد.گره ها همیشه فعال می باشند و تعداد گره های درگیر مسیریابی تاثیری در میانگین باقیمانده انرژی شبکه ندارد .S-MAC پایین ترین مصرف انرژی را دارا میباشد و شبیه به IEEE802.11 باقیمانده انرژی بستگی به تعداد گره های درگیر کار انتقال داده ندارد.مقدار انرژی باقیمانده در پروتکل پیشنهادی نزدیک بهS-MAC میباشد ولی از آنجا که گره های درگیر انتقال داده دارای مصرف انرژی بالاتر هستند با افزایش تعداد این گره ها باقیمانده انرژی شبکه کاهش پیدا میکند.افزایش اندازه شبکه تاثیردیگری نیز بر میانگین انرژی باقیمانده شبکه دارد.با افزایش تعدادمسیرها، تغییر چندباره مسیرها ممکن می گردد، وگره های گوناگونی ممکن است درگیر مسیر یابی گردند و به این ترتیب تعداد گره هایی که دارای چرخه کاری بسیار بالا می باشند کاهش پیدا می کند.این امر به پایین آمدن مصرف انرژی کلی شبکه منجر می شود.ولی با افزایش بیشتر تعداد گره های شبکه و افزایش تعداد گره های درگیر انتقال دادن و رسیدن تعدادآنها به درصد بالایی از گره های شبکه میانگین انرژی باقیمانده کاهش پیدا می کند.

شکل۴-۴:میانگین انرژی باقیمانده شبکه در اندازه های مختلف

فصل ۵

لایه کاربرد و مساله پوشش

5. مقدمه

با رشد استفاده از شبکه های حسگر بسیاری از وظایف نظارتی به عهده این شبکه ها گذارده شده است. از آن جایی که گره های حسگر ممکن است به صورت تصادفی توزیع شده باشند، مسئله فراهم آوردن پوشش کامل به صورت یکی از مسائل اساسی در شبکه های حسگر در می آید. معمولا از شبکه های حسگر انتظار می رود که چندین برابر طول عمر یک گره در حالت فعال، عمر کنند. برای فراهم آوردن این امکان لازم است که گره ها بیشتر عمر خود را در حالت خواب بگذرانند. در عین حال ممکن است که کاربرد در نظر گرفته شده نیاز داشته باشد که هر نقطه از ناحیه مورد نظر توسط k حسگر پوشیده شده باشد. بنابراین تعیین تعداد گره های لازم و یا درصد خواب گره به طوری که نیاز برنامه کاربردی تامین شود به صورت مسئله ای مهم در می آید.

این مسئله را می توان به صورت زیر بیان کرد:

با داشتن یک ناحیه، چه تعداد گره برای اینکه هر نقطه از ناحیه حداقل توسط k گره پوشانیده شده باشد ( برای بهینه بودن دسته بندی و ردگیری رویداد ) مورد نیاز است با این فرض که شبکه باید برای مدت از پیش تعیین شده ای فعال باشد.

گره های حسگر تنها قادر هستند ۱۰۰-۱۲۰ ساعت (۴-۵ روز ) با بهره گرفتن از یک جفت باتری AAA در حالت فعال به سر ببرند. در حالی که معمولاً مورد نیاز است که شبکه برای چندین ماه به فعالیت بپردازد. گره ها در حالت خواب ممکن است تا ۰٫۱% از انرژی در حال فعال خود را مصرف کنند. بنابر این یک روش رایج برای افزایش طول عمر گره ها خواباندن آنها می باشد. برای اینکه چنین کاری ممکن باشد ابتدا باید سه مسئله حل شده باشند.

نخست، روشی موجود باشد که بتواند چرخه فعالیت گره ها را تعیین نماید. دوم، با داشتن چرخه فعالیت هر گره باید تعیین کند که چه زمان باید فعال بوده و کی به خواب رود. سوم، روشی مورد نیاز است که بتوان با بهره گرفتن از آن تعداد گره های مورد نیاز را برای فراهم آوردن پوشش k- لایه ای ( با تامین نیازمندی های مربوط به عمر شبکه ) به دست آورد.

این مسئله بدین دلیل مهم است که از یک سو مسائل اقتصادی باعث می شوند تمایل داشته باشیم که حداقل گره های ممکن را در شبکه استفاده کنیم و از سوی دیگر نیاز داریم که کیفیت بالایکشف، دسته بندی، و ردگیری اهداف برای مدت طولانی را به دست آوریم .

ابتدا به حل مسئله ساده تر می پردازیم:

تعیین چرخه فعالیت مورد نیاز برای رسیدن به طول عمر مورد نیاز.

برای حل این مسئله روشی به نام خوابیدن تصادفی مستقل ارائه می گردد که در آن زمان به دوره هایی تقسیم می گردد. در ابتدای هر دوره هر گره به صورت مستقل تصمیم می گیرد که برای ادامه دوره فعال باقی بماند (با احتمال p)و یا به خواب برود (با احتمال۱-p). به این ترتیب عمر شبکه به اندازه ۱/p افزایش خواهد یافت. به این ترتیب با دانستن عمر مدت نظر برای شبکه و دانستن مدت فعالیت گره ها در حالت فعال به دست آوردن چرخه فعالیت لازم برای رسیدن به طول عمر مورد نظر ساده می باشد. به علاوه این روش یکنواخت خواب گره ها باعث مصرف متوازن انرژی در شبکه می گردد.[۱۸]

باید توجه داشت که تقسیم فعالیت گره ها به دوره های مختلف قبلاً نیز در گره های حسگر پیشنهاد شده و مورد استفاده قرار گرفته است. روش بر پایه نگهبان [۷۷] که در آن گره فعال به عنوان نگهبان خوانده می شود پیشنهاد شده است. ولی انتخاب گره های نگهبان در آن به صورت پویا در نظر گرفته نشده است. در [۴۵] روشی برای انتخاب نگهبانان ارائه شده است.

در این حالت گره برای مدتی به نسبت عکس انرژی باقی مانده اش عقب نشینی می کند و سپس با انتخاب شعاع ارسال به اندازه شعاع حسگرش قصد خود را برای نگهبان شدن به سایر گره ها اعلام می دارد .با اینکه استفاده از باقی مانده انرژی روش خوبی برای تعیین نگهبان ها می باشد و مصرف انرژی را توزیع می نماید ولی در این روش راهی برای تعیین احتمال انتخاب نگهبانان برای رسیدن به یک طول عمر مشخص ارائه نشده است، بنابراین در این قسمت می توان از روش خوابیدن تصادفی مستقل استفاده کرد. به علاوه در این روش گره نیازی ندارد با همسایگانش هماهنگی کند که آیا حق دارد به خواب برود یا خیر؟

در کاربرد های پوشش توزیع بار تنها یک ویژگی دلخواه به شمار می رود. در حالی که هدف اصلی فراهم آوردن پوشش مورد نظر با بهره گرفتن از گره های نگهبان بر روی ناحیه حسگر به شمار می رود. یکی از اهداف روش ارائه شده در [۳۳] برای انتخاب گره های نگهبان فراهم آوردن پوشش کامل با بهره گرفتن از این گره ها می باشد. ولی اگر تعداد کافی گره های حسگر به کار نرفته باشند دسترسی به پوشش کامل غیر ممکن می باشد. هم چنین در [۷۸] [۲۳] روش های ارائه شده به این نکته می پردازند که چگونه گره های نگهبان پوشش k- لایه ای را بر روی ناحیه مورد نظر فراهم آورند ( با ارتباط با سایر گره ها و تعیین این نکته که به بیداری آنان نیازی هست یا نه).

ولی باز هم اگر تعداد کافی گره در شبکه به کار نرفته باشد این امر غیر ممکن می گردد. بنابراین توسعه روشی که بتواند پوشش k- لایه ای تضمینی ارائه کند و در عین حال این امکان را فراهم آورد که گره ها تنها به اندازه p درصد از وقت خود را فعال باشند از مسائل اساسی که در حال حاضر در شبکه های حسگر وجود دارد می باشد.

مزیت دیگر این روش این است که می توان به خواب رفتن گره ها را نوعی از کار افتادن در نظر گرفت و به این ترتیب می توان احتمال خرابی و از کار افتادن گره ها را نیز در این کار داخل گرداند. در این بخش می خواهیم روابط لازم را با داشتن تعدادی گره، k مورد نظر، شعاع حسگر، و اندازه ناحیه به دست آوریم. سه نوع توزیع برای گره ها در نظر گرفته می شود. توزیع تصادفی یکنواخت، توزیع پواسون، و توری ()می باشد.

پیش از اینکه به روابط موجود بپردازیم بد نیست برخی از دلایل نیاز به پوشش k- لایه ای به جای ۱-لایه ای را بر شمریم.

در برنامه های کشف نفوذگر برای تامین هدف دسته بندی، لازم است که نفوذگر توسط بیش از یک گره کشف شده و در عوض حداقل توسطk گره حس شود. مقدارk بستگی به میزان دقت برنامه دسته بندی دارد. به عنوان مثال دامنه حسگرهای مغناطیس سنج بستگی به نوع نفوذگر دارد. این مقدار برای افراد مسلح۲-۳ متر، برای ماشین ها ۷-۵ متر می باشد. بنابراین یک ماشین توسط تعداد بیشتری گره کشف می شود. از این امر می توان برای جداسازی یک اتومبیل از افراد مسلح استفاده کرد.

در یک شبکه چندگامه حسگر ممکن است نرخ از دست دادن بسته ها بسیار بالا باشد. بنابراین لازم است که k یا تعداد بیشتری حسگر نفوذگر را کشف کرده و گزارش کنند تا بتوان از رسیدن پیام به ایستگاه مرکزی اطمینان حاصل کرد.

پوشش k- لایه ای هم چنین برای تشخیص تحریک بی دلیل گره ها مورد نیاز است. به این ترتیب قادر هستیم که تحریک بی دلیل گره ها به دلیل باد و یا سایر رویدادهای طبیعی را از یک نفوذ جدا کنیم.

دلیل دیگر نیاز به پوششk- لایه ای بهبود کیفیت ردگیری اهداف می باشد. پوشش نفوذگر توسط k گره باعث می شود که بتوانیم موقعیت جغرافیایی و یا سرعت گره را با دقت بیشتری به دست اوریم ( برابر) در صورتی که داده های کشف به حالت بهینه ای ترکیب گردند.

۵-۱ تحقیقات پیشین

در [۳۰] روشی قطعی برای فراهم آوردن پوشش بر روی یک ناحیه تحت پوشش ارائه داده است. این روش تضمین می کند که پس از خاموش شدن گره های اضافی پوشش شبکه به اندازه قبل باقی می ماند. در این روش فرض می شود که همه گره ها دارای اطلاعات جغرافیایی می باشند. در این روش هم چنین فرض می شود که می توان جهت سیگنال را به دست آورد که برای فراهم آوردن این پیش فرض ممکن است به بیش از یک آنتن نیاز پیدا کرد. در این روش هم چنین نیاز است روشی برای به دست آوردن اطلاعات جغرافیایی گره های اطراف وجود داشته باشد.

در [۷۹] نویسندگان روشی بر پایه کلونی مورچه برای خودسازمان دهی در شبکه های حسگر ارئه داده اند. هر گره به صورت یک مورچه غیر متحرک در نظر گرفته می شود. هر مورچه در هر چرخه به احتمال p بیدار می شود با کشف شدن یک نفوذگر مورچه فرومون ترشح می کند که به تدریج به گره های اطراف انتشار پیدا می کند. گره هایی که این فرومون را دریافت می کنند احتمال بیداری خود را در دوره بعدی بالا می برند. در واقع بر اساس مقدار تجمعی فرومون دریافت شده در هر چرخه احتمال به خواب رفتن در چرخه بعدی تعیین می گردد. این روش درصد گره های سودمند ( گره هایی که نفوذگری را دریافت کرده اند) در شبکه را افزایش می دهد.این روش تضمینی برای کشف شدن رویدادها ارائه نمی دهد.

در [۳۲] به این نکته پرداخته شده است که احتمال به دست آوردن پوششk- لایه ای به چه نسبتی با شعاع حس کردن و تعداد گره های به کار رفته در توزیع های گوناگون (پواسون و تصادفی یکنواخت) تغییر می کند. در این مقاله اثر مرزی نیز در نظر گرفته شده است. گره ها همیشه فعال بوده و هیچ دوره خوابی نیز وجود ندارد.

در [۲۹] و [۴۵] نتایج به کار اندازی واقعی گره های حسگر ارئه شده و نکاتی کلیدی در مورد کشف، دسته بندی، مدل خطا ( از کار افتادن گره ها، خطای ارتباطی، …)، قابلیت های رادیویی، اعلان خطرهای اشتباه، و مصرف انرژی در حالت های مختلف ارائه می دهد.

در [۲۶]به مسئله پوشش k تایی که در آن با داشتن یک مجموعه متناهی از نواحی، هدف تقسیم گره ها به پوشش هایی است که در آن تعداد پوشش هایی که یک ناحیه را شامل می شوند حداکثر باشد. در حقیقت تعداد دفعاتی که ناحیه پوشیده می شود حداکثر می گردد. به این معنی که با چرخش میان k پوشش درصد مشخصی (مثلا۸۰%) از نواحی در پنجره ای به طول k مرحله قبلی پوشانیده شده باشند. بنابراین پوشش در این روش حفظ نمی گردد.

[۳۴] مسئله حداکثر سازی مجموعه پوشش را برای دانستن اهدافی که قرار است پوشانده شود حل می کند. هم چنین ثابت می کند مسئله بیشینه سازی تعداد پوشش ها np-complete می باشد.

در [۲۳] نشان داده شده است که برای به دست آورده اتصال در شبکه در شرایطی که پوشش ۱- لایه ای بر روی ناحیه وجود دارد، لازم است که شعاع فرستادن گره دو برابر و یا بیشتر بزرگتر از شعاع حسی حسگر باشد. .

در این مقاله هم چنین روشی برای فراهم آوردن اتصال و پوشش تضمینی (با درجه های مختلف) ارائه می دهد.

[۳۱] روشی توزیع شده برای کنترل چگالی در شبکه های حسگر بی سیم ارائه می دهد که از طریق کاوش محلی گره های همسایه صورت می گیرد این روش نیاز به اطلاعات ساختاری و موقعیتی گره های همسایه ندارد.

در [۷۵] روشی برای حساب کردن پوشش فراهم شده برروی هر ناحیه ارائه شده است که با بهره گرفتن از آن می توان تعیین کرد چه نقاطی از شبکه به اندازه کافی پوشانیده نشده اند.

اکثر روش های قطعی مانند [۳۰][۲۳][۳۱] از یک معیار شایستگی برای خاموشی های اضافی در هر ناحیه استفاده می کنند. برای اینکه تعیین شود که چه گره هایی می توانند به خواب بروند گره ها به اطلاعات جغرافیایی همسایگان خود نیاز دارند. هم چنین نیاز دارند که ناحیه برای گره های فعال جستجو کنند. این سربار ارتباطی و محاسباتی بیشتری نسبت به روش های احتمالاتی به شبکه تحمیل می گرداند.

تا حد اطلاع نویسنده تنها موردی که در آن سعی شده است تا با تنظیم پویای شبکه حسگر سطوح مختلفی از پوشش ارائه شود در [۲۳] ارائه شده است.

در [۱۸] شرایط مرزی مورد نیاز برای فراهم آوردن پوشش k-لایه ای در شبکه خواب آلود در سه توزیع (توری،یکنواخت تصادفی،پواسن) ارائه شده است. ما از حدهای ارائه شده در این مقاله برای حساب کردن احتمال مورد نیاز در شبکه استفاده می کنیم.

۵-۲ پوشش k-لایه ای پویا

۵-۲-۱ تعریف مسئله

مجموعه ای متشکل از N حسگر {s1,s2,s3,….}=S ،در محیط دو بعدی A وجود دارند.گره ها در سه توزیع تصادفی یکنواخت ، توری ، و یا پواسن ریخته شده اند.همه گره ها دارای شعاع حسی مشابه r می باشند.

همانطور که در شکل نشان داده شده است گره ها دارای دوره های خواب و بیداری می باشند.

شکل ۵-۱:دوره های خواب بیداری گره

گره ها در حالت خواب می توانند دستگاه حسگر ودستگاه فرستنده خود را خاموش کنند تا صرفه جویی انرژی بیشینه گردد. روشن و خاموش کردن دستگاه فرستنده توسط MAC کنترل می گردد واحتمال خواب و یا بیداری دستگاه حسی از روشی که در ادامه ارائه می گردد تعیین می شود.

پیش فرض های ما بسیار به مقالات [۱۸][۲۵] شبیه می باشد. شبکه بسیار چگال(چنان که تعداد گره هایی که در شبکه به کار رفته اند ممکن است چند مرتبه بزرگی بزرگتر از تعداد گره های فعال در شبکه باشد. (تعداد کافی گره در شبکه به کار رفته اند تا بتوان پوششk- لایه ای فراهم کرد. گره ها با بهره گرفتن از یکی از روش های همزمان سازی که همزمانی در سطح میکرو ثانیه را فراهم می آورند،هم زمان شده اند [۳۶][۳۷].

ما فرض می کنیم که تعداد رویدادهایی که در شبکه رخ می دهند زیاد باشد. پویا بودن پوشش بیهوده است. گره ها در حالت های مختلف خواب، بیداری، دریافت و ارسال دارای مصرف انرژی متفاوتی هستند[۲۹][۲۷]. ما فرض می کنیم که گره ها دارای اطلاعات جغرافیایی نمی باشند. هم چنین گره ها اطلاعاتی در مورد موقعیت و وضعیت گره های همسایه ندارند. شعاع ارتباطی گره ها مساوی و یا بیشتر از شعاع حسی گره ها می باشد. به علاوه ما فرض می کنیم که در شرایطی که مزاحمی در محدوده حسی حسگر باشد حتما توسط حسگر کشف خواهد شد.

ما روشی را برای فراهم آوردن پوشش ۱- لایه ای بر روی همه ناحیه ارائه می دهیم.در صورتی که رویدادی در شبکه توسط تنها گره فعال در آن ناحیه پیدا شود تعداد گره های فعال در آن ناحیه به k تا افزایش پیدا می کند. از آنجا که ما نمی خواهیم از اطلاعات جغرافیایی استفاده کرده و یا پیام کنترلی به کار ببریم از روشی احتمالاتی برای تعیین وضعیت گره ها استفاده می کنیم.

برای احتمال بیداری گره ها از معادلات ارائه شده در [۱۸] استفاده می کنیم.

تابع یک تابع با رشد آرام می باشد در صورتی که صعودی یکنواخت بوده

O(log log (np)) بوده به ازای n→∞ به سمت بی نهایت میل کند.

تابع را در نظر بگیرید، در صورتی که برای توزیع های تصادفی یکنواخت برای یک تابع داشته باشیم:

آنگاه تمامی نقاط شبکه تقریبا دارای پوششk- لایه ای می باشند [۱۸] . که در آنn تعداد گره ها، p احتمال بیداری هر گره در هر چرخه، و r شعاع حسی هر حسگر، و k سطح پوشش مورد نظر باشد.

برای توزیع توری به ازای یک تابع داریم که اگر

آنگاه تقریبا همه نقاط با رفتن n به سمت بی نهایت دارای پوششk- لایه ای هستند.

مشابه [۱۸]ما فرض می کنیم که تعداد گره های شبکه به اندازه کافی بزرگ می باشد. بنابراین روابط حدی (۱) و (۲) برقرار می باشند ما از این روابط برای به دست آوردن احتمال بیداری مورد نیاز برای دست یابی به سطوح مختلف پوشش( برای تعداد ثابتی گره) استفاده می کنیم.

هدف ما پیدا کردن پایین ترین احتمالی است که شرایط بالا را فراهم می آورد. کمینه کردن این احتمال منجر به پایین تر بودن تعداد گره های فعال در هر چرخه شده و صرفه جویی انرژی را بهبود می بخشد. البته احتمالات بالاتر هم ممکن می باشد، و پوشش بالاتری را فراهم می آورند ولی در عوض مصرف انرژی نیز افزایش می یابد. به کار بردن احتمالات بالاتر گاهی اوقات در شبکه ضروری می باشد چرا که ممکن است برنامه کاربردی به احتمال بالاتر و تضمین های بیشتری نیاز داشته باشد.

ما از این حدود برای تعیین احتمال مورد نیاز برای فراهم آوردن پوشش ۱- لایه ای بر روی شبکه استفاده می کنیم. هم چنین این احتمال برای فراهم آوردن پوششk- لایه ای در موردی که نفوذگری کشف شده است استفاده می گردد.

۵-۳ روش پیشنهادی

چنانکه در شکل ۵-۲ نشان داده شده است هدف ما داشتن حداقل یک گره فعال در تمامی نواحی می باشد تا بتوان ناحیه مورد نظر را کاملأ پوشش داد.از شرایط (۱) و (۲) برای تعیین احتمال بیداری مورد نیاز برای دستیابی به سطح پوشش مورد نیاز استفاده می گردد. تمامی گره ها برای محاسبه احتمال مورد نیاز برای رسیدن به پوشش ۱-لایه ای نیاز به داشتن نوع توزیع و تعداد گره های به کار رفته دارند.این مقادیر باید در شبکه پس از به کاراندازی آن به صورت سیل آسا پخش گردند. در صورتی که یکی از این مقادیر تغییر کرد و یا مثلأ سطح پوشش مورد نیاز کاربر عوض شد،لازم است که این داده ها دوباره در شبکه پخش گردند.

تمامی گره ها پس از دریافت این متغیرها احتمال مورد نیاز برای دستیابی به پوشش ۱-لایه ای و k-لایه ای را محاسبه و ذخیره می کنند.تمامی گره ها در ابتدا سطح احتمال پوشش ۱-لایه ای تنظیم می کنند،بنابراین از آنجا که شبکه دارای پوشش ۱-لایه ای می باشد در صورت ورود یک نفوذ گر،او حداقل توسط یک گره کشف میگردد.گره ای که نفوذ گر را کشف کرده است باید تا انتهای چرخه خواب همسایگانش صبر کرده وسپس پیام هشدار برای آن ها ارسال گرداند.

شکل ۵-۲٫ شبکه حسگر با توزیع یکنواخت تصادفی. شبکه دارای پوشش ۱- لایه ای می باشد.در صورتی که نفوذگری کشف شود، گره کاشف پیامی را در همسایگی خود می فرستد.

گره هایی که این پیام هشدار را دریافت می کنند، احتمال بیداری خود را به سطح پوششk- لایه ای افزایش می دهند. بنابراین در چرخه بعدی تعداد گره ها ی فعال تقریبا به k حسگر افزایش پیدا می کند.(شکل۵-۳)

شکل۵-۳٫ در چرخه بعدی تعداد گره های فعال به k گره افزایش پیدا می کند.

بقیه شبکه هم چنان دارای پوشش ۱- لایه ای می باشند.

تمامی گره های فعال در این دوره که یک نفوذگر را تشخیص می دهند یک پیام پخشی را در ابتدای چرخه بعدی می فرستند. در صورتی که یک گره فعال با احتمال بیداری پوششk- لایه ای در چرخه بعدی نفوذگری را کشف نکند بلافاصله سطح احتمال بیداری خود را پوشش ۱- لایه ای کاهش می دهد. (شکل۵-۳).

۵-۳-۱ مسئله پوششk- لایه ای جا به جا

از آنجا که تنها گره هایی که درشعاع ارسال گره اولی که نفوذگر را پیدا کرده قادر هستند که پیام هشدار او را دریافت کنند ممکن است تعداد گره هایی که در چرخه بعدی نفوذگر را پوشش می دهند کمتر از k گره باشد.(مثلا در شکل۵-۳ تعداد گره های مؤثر به جای ۵ گره، ۴ گره می باشد.)

تمامی گره هایی که لازم است پیام گره اول را بشنوندپیام او را دریافت نخواهند کرد. هم چنین ممکن است که نفوذگر تا زمان آغاز چرخه بعدی جای خود را تغییر دهد که این امر می تواند باعث شود حتی تعداد کمتری حسگر پیام گره اول را دریافت کنند. به این مسئله مشکل پوششk- لایه ای جا به جا گفته می شود.

شکل۵-۴٫ مشکل پوششk- لایه ای جابجا

برای حل این مشکل، در یک حدس بدبینانه می توان در نظر گرفت که تنها نیمی از گره های موجود در ناحیه مؤثر (ناحیه ای که باید واقعا دارای پوششk- لایه ای باشد) می توانند پیام هشدار پخشی را که گره ای که نفوذگر را کشف کرده است، در چرخه قبلی فرستاده است بشنوند. این یک حس بدبینانه به شمار می رود چرا که سرعت نفوذگران نسبت به شعاع حسی حسگر و چرخه کار گره ها پایین می باشد. داشتن این فرض باعث می شود که احتمال بالاتری برای پوششk- لایه ای محاسبه گردد و باعث به دست آمدن پوششی بالاتر از k در ناحیه پیام هشدار می گردد)این امر باعث می گردد که در ناحیه نفوذگر پوششی نزدیک بهk ویا بالاتر به دست آید.

هم شبیه سازی های ما و هم شبیه سازی های ارائه شده در[۱۸] نشان می دهند که پوشش واقعی (به صورت میانگین)بر روی ناحیه پایین تر از پوششی است که از فرمول ها به دست می آید، بنابراین این فرض باعث می شود که پوششی نزدیکتر به پوشش مورد نیاز به دست آوریم.

از آنجا که هنگامی که n به سمت بی نهایت می رود n/2 نیز به سمت بی نهایت می رود ، شروط (۱) و (۲) هم چنان برقرار می باشند،به همین ترتیب (np)ø هم چنان ((np)log log)ø می باشند،بنابراین این این فرض تغییر شدیدی را در احتمال p به دست آمده ایجاد نمی کند ولی باعث به دست آمدن پوشش بالاتر (در ازای مصرف بالاتر انرژی) می گردد.