X
تبلیغات
computer - پروتکل‌های مسیریابی در شبکه‌های حسگر بیسیم

computer

پروتکل‌های مسیریابی در شبکه‌های حسگر بیسیم

LEACH-HPR: An Energy Efficient Routing Algorithm for Heterogeneous WSN

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

1) مقدمه

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

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

در این بخش، سه نوع گره حسگر مورد بررسی قرار گرفته است. بخشی از آنها با منابع انرژی افزونه‌ای نسبت به باقی گره‌ها تجهیز شده‌اند. فرض بر این است که کلیه گره‌های حسگر به شکل یکنواختی توزیع گردیده‌اند. در شبکه‌های حسگر بیسیم غیرهمگن، پروتکل انتخاب سرخوشه با مصرف بهینه انرژی پیشنهاد گردیده است (LEACH-HPR) که از الگوریتم درخت پوشای مینیمم استفاده می‌کند تا مسیریابی داخل خوشه را ایجاد نماید.

2) ماجول شبکه

شبکه حسگری مبتنی بر خوشه‌بندی را صدها گره حسگر در نظر بگیرید که در محیطی توزیع شده‌اند. ایستگاه مرکزی (BS) در مرکز زمین واقع شده و هر خوشه تنها دارای یک سرخوشه می‌باشد که به عنوان یک مرکز کنترل کننده محلی برای هماهنگی انتقال داده عمل می‌کند. n گره‌ی شبکه را می‌توان با مجموعه داده‌ای S، S={S1, S2, …, Sn} نمایش داد.

انرژی کلی برای انتقال L بیت پیام بر روی فاصله d، به صورت زیر است:

 

که Eelec انرژی پراکنده شده به ازای هر بیت برای راه‌اندازی مدار دریافت‌کننده یا ارسال‌کننده است. fs ε و εmp بستگی به مدل آمپلی‌فایر ارسال کننده دارد و d فاصله بین دریافت کننده و ارسال کننده است. با مساوی قراردادن این دو عبارت در d=d0، برای دریافت L بیت پیام رادیویی داریم: ERx=L*Eelec.

3) الگوریتم

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

در الگوریتم این بخش، شبکه حسگر بیسیم ناهمگن سه نوع گره با انرژی متفاوت دارد (نوع A، نوع B و نوع C). گره‌ها در خوشه‌های محلی که در آنها یک گره به عنوان سرخوشه عمل می‌کند، سازمان‌دهی می‌گردند. تمامی گره‌های غیر از سرخوشه باید داده‌هایشان را به سرخوشه انتقال دهند و گره سرخوشه باید داده‌ها را از اعضای خوشه دریافت نموده و تابع پردازش سیگنال را روی آنها اجرا و داده را به ایستگاه مرکزی دوردست ارسال نماید. بنابراین سرخوشه شدن بسیار بیشتر از باقی گره‌های غیرسرخوشه انرژی مصرف می‌کند.

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

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

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

A) مدل انرژی

ناحیه‌ای با ابعاد S=M*M m2 در نظر بگیرید که n گره در آن به صورت یکنواخت توزیع گردیده‌اند. گره Sink در مرکز ناحیه واقع شده و فاصله هر گره تا ایستگاه مرکزی از طریق سرخوشه کوچکتر یا مساوی d0 است. بنابراین انرژی پراکنده شده توسط سرخوشه درطی هر دور توسط فرمول زیر محاسبه می‌شود:

که k تعداد خوشه‌ها، EDA هزینه پردازشی یک بیت گزارش به ایستگاه مرکزی، و dBS میانگین فاصله بین یک سرخوشه و Sink است. انرژی استفاده شده در یک گره غیرسرخوشه برابر است با:

که dCH فاصله میانگین بین یک عضو خوشه و سرخوشه‌اش است.

انرژی پراکنده شده در شبکه برابر خواهد بود با:

اگر درصد زیادی از گره‌ها فاصله‌شان از Sink بزرگتر از d0 باشد، آنگاه خواهیم داشت:

احتمال بهینه یک گره برای سرخوشه شدن، Popt به شکل زیر قابل محاسبه خواهد بود:

شعاع ارتباطی بهینه R، از طریق محوطه ناحیه ارتباطی S و kopt قابل محاسبه است:

B) مرحله انتخاب سرخوشه

همانطور که عنوان شد از یک شبکه ناهمگن با سه نوع گره با سطوح انرژی متفاوت استفاده می‌کنیم (نوع A، نوع B و نوع C). گره از نوع A و نوع B به ترتیب با انرژی a و b برابر نسبت به نوع C تجهیز شده‌اند. درصد گره‌های از نوع A و نوع B در مجموعه گره‌ها m1 و m2 است. این طور می‌توان استنتاج نمود که گره‌های از نوع A و B اغلب بیشتر از گره‌های از نوع C سرخوشه می‌شوند. تنظیم اولیه ناهمگنی به طور کامل انرژی اولیه شبکه را تغییر می‌دهد. با فرض EC به عنوان انرژی اولیه گره از نوع C، EA، EB به صورت زیر خواهد بود:

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

دوره جدید شبکه ناهمگن به صورت زیر است:

دوره جدید Ne باید با افزایش انرژی سیستم متناظرا تغییر یابد. ناحیه پایدار شبکه حسگر با ضریب (1+Q) افزایش می‌یابد؛ این بدین معناست که (1) هر گره از نوع C تنها یکبار در هر دوره (1+Q)/ popt  سرخوشه می‌شود. (2) هر گره از نوع A دقیقا (1+a) مرتبه در هر (1+Q)/ popt سرخوشه می‌گردد. (3) هر گره از نوع B دقیقا (1+b) مرتبه در هر دوره (1+Q)/ popt سرخوشه می‌شود. بنابراین، درصد انتخاب بهینه هر گره عبارت خواهد بود از:

آستانه‌های T(s1)، T(s2) و T(s3) را برای گره‌های نوع A، B و C تعریف می‌کنیم. بنابراین برای گره از نوع C داریم:

که r دور جاری، G مجموعه گره‌های از نوع A است که در 1/ P1 قبلی سرخوشه نشده‌اند، و T(s3) آستانه‌ای است که به جمعیت n*(1-m1-m2) گره از نوع C اعمال می‌شود. به صورت مشابه T(s1) و T(s2) برای گره‌های نوع A و B ارزیابی می‌گردند. بنابراین سرخوشه‌ها براساس شعاع ارتباطی بهینه موجود در رابطه 7 حاصل می‌شود.

در آغاز مرحله تنظیم سرخوشه، تمامی گره‌ها تایمرشان را برای شمارش معکوس راه‌اندازی می‌کنند و پیامی با عنوان "من سر خوشه هستم" ارسال می‌نمایند. برای گره S، تمامی پیام‌ها از گره‌های دورن ناحیه با شعاع r قابل دریافت است. اگر S پیامی قبل از کم شدن تایمرش دریافت نماید، وضعیت گره S سرخوشه نخواهد بود. در غیر این صورت اگر گره S نتواند پیامی تا پایان زمانش دریافت نماید، پیامی مبتنی بر سرخوشه شدن را منتشر می‌نماید. این پیام بسیار کوچک بوده و شامل شناسه گره S، انرژی باقیمانده و مشخصه سرآمدی است که پیام را به عنوان یک پیام آگهی از باقی پیام‌ها متمایز نماید. سپس وضعیت گره S سرخوشه خواهد بود.

C) فاز تنظیم خوشه

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

پارامتر رقابتی به صورت Cjoin تعریف و آن را به صورت زیر محاسبه می‌کنیم:

که Eremainder انرژی باقیمانده کاندیدای سرخوشه است.

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

گره سرخوشه، شماره یک شماره‌گذاری می‌شود و دستیار سرخوشه شماره دو و به همین ترتیب شماره‌ها تا (x+1) به ترتیب نزولی Erem شماره‌گذاری می‌گردند. سرخوشه‌ها به عنوان مراکز کنترلی محلی برای هماهنگ‌سازی انتقال داده‌ای در خوشه‌شان عمل می‌کنند. گره سرخوشه زمان‌بندی TDMA را استفاده می‌نماید و این زمان‌بندی را برای گره‌های داخل خوشه ارسال می‌کند. این امر اطمینان می‌دهد که هیچ تداخلی بین پیام‌های داده رخ نخواهد داد. کل زمان انتقال داده به صورت مساوی به m تکه تقسیم می‌شود. در هر تکه زمانی TDMA، گره شماره 1 تا (x+1) اطلاعات را ترکیب و داده را به ترتیب برای ایستگاه مرکزی ارسال می‌کنند. استراتژی همکاری سرخوشه و دستیارش باعث بهبود کارایی انرژی و طولانی‌تر شدن عمر شبکه می‌گردد.

شکل 1 رویه تنظیم خوشه را مشخص می‌کند.

D) فاز ایجاد مسیر مسیریابی

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

توپولوژی  شبکه حسگر بیسیم به صورت گراف وزن‌دار G=(V, E, w) داده شده که V مجموعه گره‌های سرخوشه است که ایستگاه مرکزی را نیز شامل می‌شود، و E مجموعه یال‌ها و w مجموعه فواصل مستقیم بین گره‌ها در مجموعه Vاست. هدف استفاده از الگوریتم Prim برای یافتن درخت پوشای مینیمم[1] در گراف G است؛ بدین معنا که MST ارتباط کوتاه مسیر و چندگامه‌ای را میان سرخوشه‌ها و ایستگاه مرکزی پیاده‌سازی می‌نماید و مسیر با فاصله کوتاه بهینه را در ارتباطات سرخوشه می‌یابد. برای بررسی توازن مصرف انرژی میان سرخوشه‌های نزدیک به ایستگاه مرکزی، از انرژی باقیمانده به عنوان فاکتور محدودکننده‌ای برای انتخاب گره‌های میانی بین سرخوشه‌ها و ایستگاه مرکزی استفاده می‌کنیم. الگوریتم Prim بهبود یافته به صورت زیر است:

که Einit انرژی اولیه سرخوشه، و EAVG میانگین انرژی باقیمانده تمامی سرخوشه‌هاست.

الگوریتم Prim بهبودیافته مذکور، به نظر می‌رسد که بیشتر وقتش را صرف یافتن کوتاهترین یال برای رشد می‌کند. در روش مستقیم، کوتاهترین یال با جستجو در میان لیست رئوس همسایه در V یافت می‌شود: هزینه‌های هر تکرار O(m) است و منجر به زمان اجرای کلی O(mn) خواهد شد.



[1] MST: Minimum Spanning Tree

+ نوشته شده در  شنبه بیست و هفتم آبان 1391ساعت 16:20  توسط reza jadidi  |