بخشی از مقاله
*** اين فايل شامل تعدادي فرمول مي باشد و در سايت قابل نمايش نيست ***
یک الگوریتم توزیع شده آگاه از انرژی برای ساخت ستون فقرات مجازی در شبکه حسگر بیسیم با برد ارسال متفاوت
خلاصه
از آن جا که در شبکه های حس گر بی سیم2 یک ساختار ثابت یا مدیریت متمرکز وجود نـدارد، انتخـاب تعـدادی از حسگرها برای تشکیل یک CDS (مجموعه غالب همبند (3 بهعنوان یک سـتونفقـرات مجـازی4 بسـیار مطلـوب و کارآمـد است. یک ستونفقـرات مجـازی در مسـیریـابی کارآمـد از احـاظ انـرژی5 ، زمانبنـدی فعالیـت6 و پخـشفراگیـر7 کـارایی فوق العاده ای دارد. شبکه های حسگر بی سیم جهت تشکیل یک CDSمعمولاً بوسیله UDG (گـراف قـرص واحـد(8 مـدل میشوند که در این مدل تمامی نودها برد ارسال9 یکسانی دارند، اما این مقاله بجای مدل UDG از یک مدل دیگـر کـه بـه واقعیت نزدیک تر است به نام DGB (گراف قرص با لینکهای دوطرفه(10 استفاده میکند که در آن نودها میتوانند بازه های انتقال متفاوتی را اختیار کنند. در بسیاری از کاربردها برای کاهش سربار، افزایش طول عمـر شـبکه و ماننـد ایـن هـا، پیـدا کردن MCDS (کوچکترین مجموعه غالب همبند(11 مطلوب میباشد، اما نکته اینجاست که مسئله MCDS در مدلهـای UDG و DGB، یک مسئله NP-hard است. این مقاله علاوه بر تحلیل الگوریتم های موجود، الگوریتم جدیدی ارائه خواهد کرد و کارایی این الگوریتم را، بـه خصـوص از لحـاظ مصـرف انـرژی، بواسـطه تحلیـل تئوریـک و شـبیهسـازی، نسـبت بـه الگوریتمهای موجود بررسی خواهد نمود.
کلمات کلیدی: شبکه حسگر بی سیم، توزیع شده، آگاه از انرژی، ستون فقرات مجازی، برد ارسال متفاوت
.1 مقدمه
شبکههای حسگر بیسیم دسته ای از شبکههای ویژه1 هستند که از صدها یا حتی هزاران حسگر کم هزینه، کـم توان2 و چندین کاره3 تشکیل شدهاند که میتوانند محیط اطراف خود را حسکرده و اطلاعات مربوطه را جمعآوری نموده و نموده و پردازش نمایند و این اطلاعات را از طریق امواج بیسیم برای نودهایی کـه درمحـدوده بـرد ارسـال آنهـا هسـتند، ارسال کنند .[1]
معمولاً در شبکه حس گر بی سیم یک یا چند نود مهم به نام sink وجود دارد که اطلاعات جمعآوری شده بوسیله حسگرها، یا بهطور مستقیم یا بواسطه چندین نود میانی4 به این نود ارسال میشوند.
شبکه های حس گر بی سیممعمولاً بوسیله UDG (گراف قرص واحد) مدل مـی شـوند .[2] در ایـن مـدل تمـامی نودها برد ارسال یکسانی دارند و دو نود همسایه یکدیگر هستند اگر در محدوده برد ارسال یکـدیگر باشـند. از آنجـا کـه در عمل این فرض که تمامی نودها دارای برد ارسال یکسانی باشند بدلیل تضعیف واحد فرسـتندهگیرنـده و بسـیاری از عوامـل دیگر غیرممکن است و همچنین در بسیاری از کاربردها نیازمند برد های ارسال مختلف هستیم، در این مقالـه از یـک مـدل دیگر به نام DGB (گراف قرص با لینک های دو طرفه) استفاده میکنیم [3] که در آن نودها مـی تواننـد بـرد هـای ارسـال متفاوتی را اختیار کنند.
برای انجام کارآمد بسیاری از عملیات ها در یک شبکه حس گر بی سیم از جمله ارتباطات چند پرشی5 و نظارت بـر محیط 6، انتخاب تعدادی از حسگرها برای تشکیل یک CDS (مجموعه غالب همبند) بهعنوان یک سـتون فقـرات مجـازی بسیار مطلوب و کارآمد است .[4] یک زیرمجموعه از نودها، DS (مجموعه غالب) نامیده می شوند اگر هـر نـود شـبکه، یـا عضو زیر مجموعه فوق باشد یا در همسایگی یکی از اعضای این زیرمجموعـه باشـد. یـک DS، همبنـد (CDS) اسـت اگـر زیرگراف بدست آمده از DS، متصل (Connected) باشد. یک CDS در واقع ستون فقرات مجازی بر روی گـراف شـبکه است.
در بسیاری از کاربردها برای کاهش ترافیک، کاهش سربار و افزایش طـول عمـر شـبکه و ماننـد آن، پیـداکـردن )MCDSکوچکترین مجموعه غالب همبند) مطلوب میباشد اما نکته اینجاست که مسئله MCDS در مدل UDG یـک مسئله NP-Hard می باشد [2] و این موضوع شامل مدل DGB نیز میگـردد .[5] لـذا بـرای حـل ایـن مسـئلهی NP-Hard راهحل های متفاوتی از جمله راه حل های متمرکز [6] (Centralized)، برمبنـای کلاسـتر 7] (Cluster-based)، [8، حریصانه [9] (Greedy) و اکتشافی [10 ](Heuristic) ارائه گردیده است.
برخی از روش ها، برای محاسبه یک CDS، ابتدا یک MIS را از گراف شبکه محاسـبه مـی کننـد. یـک مجموعـه مستقل (IS) از یک گراف غیرجهتدار(G(V, E، یک زیرمجموعه از V است که بین هیچکدام از نودهای آن، یالی نباشـد. یک مجموعه مستقل، ماکزیمال است اگر نتوان نود دیگری به این مجموعه اضافه کرد. به این معنا که با اضـافه کـردن نـود جدید، یالی بین نودهای زیرمجموعه برقرار می شود و خاصیت استقلال زیر مجموعه نقض می شـود. بنـابراین یـک MIS در واقع یک DS از یک گراف غیر جهتدار است. نودهای مشکی در شکل 1 یک MIS را نمایش می دهند.
نسبت تقریب نسبتی است که میزان بهینگی یک الگوریتم را نمایش میدهـد. ایـن نسـبت بـه صـورت رابطـه 1 تعریف میشود:
در این رابطه DA lg اندازه CDS ارائه شده (تعداد نودهای انتخاب شده به عنوان CDS در راهحل ارائـه شـده در بدترین حالت) و DOpt اندازه CDS بهینه (تعداد بهینه (کمتـرین) نودهـای (CDS را نمـایش مـیدهـد. در کاربردهـای مختلف، نسبت تقریب ثابت، بسیار مطلوب است که الگوریتم ارائه شده توسط این مقاله دارای این ویژگی است.
الگوریتم ارائه شده در این مقاله دارای خصوصیات زیر میباشد:
* توزیع شده :(Distributed) این خصوصیت برای شبکه حس گر بی سیم بسیار کلیدی و مهم می باشد چرا کـه نیازی به هیچ کنترل مرکزی نیست و هر حسگر میتواند این الگوریتم را اجرا نماید.
* محلی شده :(Localized) به این معنا که حسگر نیازمند اطلاع از توپولوژی کامل شبکه نـدارد و یـا نیازمنـد اطلاعات سراسری نیست و تنها از اطلاعات محدوده بردش استفاده میکند.
* الگوریتم ارائه شده دارای نسبت تقریب1 بهتری نسبت به الگوریتمهای موجود میباشد. نسـبت تقریـب، نسـبت اندازه (تعداد نودها) CDS ارائه شده به اندازه CDS بهینه می باشد که الگوریتم ارائه شده نسبت به الگوریتم هـای موجـود CDS کوچکتری ارائه میکند.
* دارای پیچیدگی زمانی2 و پیچیدگی پیام3 بهتری نسبت به الگوریتمهای موجود در آن زمینه میباشد.
* از لحاظ مصرف انرژی به عنوان یک عامل بسـیار مهـم، نسـبت بـه الگـوریتمهـای موجـود، بهینـه ( Energy (Efficient میباشد.
* .2 کارهای گذشته
به طور کلی روش های ساخت یک CDS به دو دسته، متمرکز1 و توزیع شده2 تقسیم مـیشـوند کـه روشهـای توزیع شده با توجه به ماهیت شبکههای بیسیم بسیار مورد توجه قرار میگیرند.
از آنجا که شبکههای حسگر بیسیم فاقد هرگونه مدیریت متمرکز هستند و معمولا بهطـور انبـوه در یـک فضـای بزرگ توسعه پیدا میکنند روش های توزیع شده بسیار موثرتر و کاراتر از روش های متمرکز می باشند، به این دلیـل در ایـن بخش به بررسی این روشها خواهیم پرداخت.
Das و همکاران در [11] یک الگوریتم حریصانه بر اساس الگوریتم [12] ارائه کردند که روشکار این الگوریتم به این گونه است: در فاز اول یک مجموعه غالب (DS) محاسبه میشود و سپس نودهایی به این مجموعه اضـافه مـیشـود تـا CDS بدست آید. اساس انتخاب نودها در فاز اول درجه هر نود میباشد بدین ترتیـب کـه هـر نـود درجـهاش را بـا درجـه همسایه هایی که فاصله 2 پرش را از آن دارند، مقایسه می کند و اگر درجهاش بالاتر بود به عنوان عضـوی از CDS انتخـاب میشود قابل ذکر است که درجه در این الگوریتم در واقع درجه موثر (effective degree) است که تعداد نودهای non-DS همسایه می باشد. زمانی که یک DS بدست آید فاز اول تمام است. در فاز دوم اجزاء (components) بدسـت آمـده، توسط یک درخت پوشا (Spanning Tree) به یکدیگر متصل میشوند که هدف آن انتخاب کمترین تعـداد نودهـا اسـت. این الگوریتم دارای پیچیدگی زمانی O (cn |c| ) و پیچیدگی پیام O (n| c| m n log (n)) می باشد کـه c| |بـه تعداد نودهای انتخاب شده به عنوان CDS اشاره میکند و ماکزیمم درجه گراف و m تعداد یالها در گراف میباشد.
Wan و همکاران در [13] یک الگوریتم بر مبنای MIS برای پیداکردن CDS در UDG ارائه کردند که از سـه فاز تشکیل میشد. در اولین فاز، این الگوریتم یـک روش انتخـاب رهبـر (leader election) توزیـع شـده [14] را بـرای بدست آوردن یک درخت پوشا از گراف شبکه، بهخدمت میگیرد. مفهوم رتبه (rank) در ایـن الگـوریتم بـه سـطح نـود در درخت ساخته شده اشاره میکند که ریشه با کمترین رتبه در سطح صفر است. فاز دوم از ریشه شروع میشود و در برگ ها خاتمه مییابد نودی که کمترین رتبه (سطح نود در درخت سـاخته شـده) را دارد خـودش را سـیاه مـی کنـد و یـک پیـام DOMINATOR را پخشفراگیر (Broadcast) میکند و بعد از آن الگوریتم براساس دو قانون زیر ادامه مییابد:
- اگر اولین پیام که یک نود دریافت می کنـد یـک پیـام DOMINATOR باشـد، آن نـود خـود را خاکسـتری میکند و یک پیام DOMINATEE را پخش میکند.
- اگر یک نود پیام DOMINATEE از تمامی همسایه هایش با رتبه کمتر دریافت کرد، خود را سیاه مـیکنـد و یک پیام DOMINATOR را پخش میکند.
این الگوریتم دارای پیچیدگی زمانی O(n) و پیچیدگی پیام O(nlogn) و همچنین نسبت تقریـب 8 opt 1 میباشد.
Thai و همکاران در[ 3] یک الگوریتم بر مبنای MIS برای پیدا کردن CDS در DGB ارائه کردهاند. این مقالـه اولین مقالهای است که به طور خاص به DGB میپردازد. در اولین فاز برای ساخت یک MIS، نود با بزرگترین برد ارسـال انتخاب شده و در دومین فاز با استفاده از یک درخت Steiner تعدادی نود به عنوان متصلکننده به ایـن مجموعـه اضـافه میشوند.
در فاز اول ابتدا همه نودها سفید هستند. هر نود یک لیست مرتب از شناسـه (id) تمـامی نودهـا بـه ترتیـب بـرد ارسال به نام Sortlist دارد. در ابتدا این لیست تنها شامل شناسه خود نود میباشـد. هـر نـود vi یـک پیـام WHITE را پخش میکند که این پیام شامل شناسه و برد ارسال <idi , ri> آن نود میباشد. بعد از دریافت یـک پیـام سـفید هـر نـود لیست مرتب خودش را بروز می کند که این کار با اضافه کردن شناسه ای که در پیام WHITE وجود داشته و با توجـه بـه برد ارسال نود، به لیست مرتب انجام می شود. یک نود که شناسه خودش را در جلو (اولین شناسه) لیسـت مرتـب مشـاهده میکند، خودش را سیاه میکند و یک پیام BLACK را پخش میکند چرا که وجود شناسـه در صـدر لیسـت مرتـب بـه معنای دارابودن بالاترین برد ارسال میان همسایه هایش می باشد. پیام BLACK شـامل شناسـه نـود سـیاه اسـت. بعـد از دریافت یک پیام BLACK، یک نود سفید، خودش را خاکستری میکند و پیام GREY که شامل شناسه نود و شناسـه موجود در پیام BLACK است را پخش می کند بعد از دریافت پیام GREY، یـک نـود سـفید لیسـت مرتـب خـودش را بوسیله حذف شناسه نودی که پیام GREY را ارسال کرده است، بروز میکند.
در فاز دوم تنها نیازمند یک درخت Steiner برای متصل کردن MIS هستیم. همه نودها در MIS سیاه هستند و نودهای دیگر خاکستری هستند. هر نودی متغییـری بـه نـام IDc دارد کـه، شناسـه جـزء سـیاه- آبـی ( black-blue (component که به آن متعلق است را نگهداری می کند. فرض کنید I یک MISتشکیل شده در فاز اول است. ابتداً I جزء سیاه- آبی (به تعداد نودهای (MIS داریم بنابراین ابتداً IDc هر نود سیاه به شناسه خود نود تنظیم می شود. هر نـود خاکستری نیز در ابتدا IDc = -1 را دارد که نشان میدهد که متعلق به هیچ جزء سیاه- آبی نیست. نـودهـای خاکسـتری همسایه و نودهای خاکستری که جزء سیاه-آبی مشترکی در همسایگی دارند، رقیب یکدیگر محسوب میشوند، بنابراین هـر نود خاکستری لیستی از رقبایش (COMPETITORS List) و لیسـتی از اجـزاء سـیاه-آبـی همسـایه (ADJ List) را داراست.
