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

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

برای اینکه گره ها قادر باشند که هم بسته های 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
شکل۴-۱:تغییر در چرخه فعالیت گره ها هنگامی که پیام تقویت دریافت می کنند،آغاز دوره گوش دادن هم چنان همزمان است.
افزایش چرخه کار گره ها همزمانی گره های همسایه را برهم نمی زند.گره هایی که برروی یک مسیر قرار دارنددارای چرخه فعالیت مشابهی می باشند.این گره ها بیشتر بیدار شده و در نتیجه دارای فرصت بیشتری برای فرستادن داده هستند که این امر به پایین بودن تاخیر و افزایش پهنای باند می انجامد.این گره ها همچنان قادر هستند با گره هایی که روی مسیر قرار ندارند و چرخه فعالیت خود را تغییر نداده اند ارتباط داشته باشند.از آنجا که چرخه فعالیت به صورت نمایی افزایش پیدا کرده است، این گره ها همچنان دارای چرخه بیداری همزمان هستند.بعد از دریافت یک تقویت مثبت ،هردو بیدار شدن گره با یک بیدار شدن گره های همسایه با دوره فعالیت معمولی همزمان می گردد.بنابراین گره قادر است به صورت طبیعی با این گره ها ارتباط برقرار کند.