مقاله جایگذاری گره در شبکه حسگر بیسیم دارای زیرناحیه های هدف

بخشی از مقاله

چکیده

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

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

- 1 مقدمه

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

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

- 2 کارهاي گذشته

بیشتر کارهاي انجام شده بر روي جایگذاري قطعی حسگرها به دنبال تعیین الگوي جایگذاري بهینه هستند. بر پایه کاربردها و اهداف شبکه حسگر، معیار بهینگی متفاوت است. یک هدفمشترك در آن پژوهشها،کمینه کردن تعداد حسگرهاي موردنیاز است به گونهاي که همه فضاي زیرمانیتور توسط حسگرهاي جایگذاري شده پوشانده شود . [3] کمینه کردن تعداد حسگرها میتواند فرمی از مساله گالري هنر [5][4]را به خود بگیرد که تلاش میکند که کوچکترین دسته از مکانها را براي نگهبانهاي امنیتی درون یک گالري هنر چندگوشه پیدا کند به گونهاي که همه مرزهاي آن گالري در دید دستکم یکی از نگهبانان باشد. با این حال، در مساله گالري هنر فرض میشود که همه نگهبانان دید نامحدود دارند اگر هیچ مانعی وجود نداشته باشد. این فرض در شبکههاي حسگر درست نیست که برد حسی حسگرها در آنها محدود است. نشان داده شده است که جایگذاري حسگرها در مرکزششگوشهاي منظم بهینهترین پاسخ براي یک شبکه حسگر با یک میدان حسی بزرگ است.[6] این نتیجه براي مدت طولانی در جهان ریاضیات شناخته شده بوده است.[7] پژوهشهاي تازهاینیز در زمینهجایگذاري گرهها با هدف ماکزیمم نمودن پوشش وجود دارند که روشهایی مانند الگوریتمنیروي مجازي و جستجوي تبورا بکار میبرند .[9][8]

کارهایبالا تنها هدف پوشش را در نظر گرفتهاند و در مورد اتصال گفتگو نمیکنند، و یا بدون در نظر گرفتن برد ارتباطی حسگرها،به طور ضمنی فرض میکنند کهالگوي به دست آمده براي شبکه حسگر، متصل است . با این وجود، این فرضیه ممکن است درست نباشد. برایپیدا کردن الگوي بهینه جایگذاري گره با توجه به هر دو هدف پوشش و اتصال، پژوهش [10] مساله را به عنوان یک مساله بهینه-سازي مدل کرده است. با این حال، آن پژوهشیک راهحل کلی را پیدا نمیکند. در عوض، دسته بزرگی از الگوهاي منظم در جایگذاري حسگر را بررسی مینماید. این الگوها عبارتند از دایره، ستاره، و الگوهاي گریدمانندگریدهاي سهگوش، مربعی، و ششگوش . [11] ثابت کرد که یک الگوي جایگذاري نواري در شبکههاي بزرگ در فضاي دو بعدي به پاسخ بهینه نزدیک است. در الگوي نواري، گرهها به ترتیب در امتداد تعداد بسیاري نوار موازي افقی جاي میگیرند و گرههاي نوارهاي افقی گوناگونمیتوانند به کمکگرههاي یک دنده عمودي در ارتباط باشند . یک طرح بر پایه الگوي نواري در [12] پیشنهاد شده است که براي دستیابی به پوشش و 2-connectivityبهینه است. به تازگی، همان نویسندگان در یک پژوهش [13] الگوریتم بهینه اي را براي دستیابی به پوشش و-k connec tivity ارائه دادهاند. ویژگی k-connectivity تحمل خطا را فراهم میکند.

کارهاي بالا فرض میکنند که شبکه حسگر در یک منطقه باز بدون مانعهاییمانند ساختمان است . در مقابل، [14] یک طرح کلی در جایگذاري حسگر را ارائه است کهمیتواند مکان بهینه حسگرها را براي پوشش یک فضاي دلخواه با مانع به دست آورد. هدفهاي دیگري غیر از کمینه کردن تعداد حسگرها نیز در نظر گرفته شدهاند. [15] مساله جایگذاري یک تعداد داده شده از گرهها را در یک شبکه حسگر گرید بررسی مینماید. تلاش در آن پژوهش بر این است که فاصله بین حسگرها براي افزایش تحمل خطا کمینه شود به گونهاي که همه حسگرها بر روي نقطه هاي گرید جاي گیرند. [16] تلاش میکند که به یک طرح جایگذاري گره براي پوشش برسد که هزینه حسگرها را کمینه مینماید.

درجه پوشش یک نقطه هدف را به صورت k-coverage نمایش میدهیم که به این معناست که آن نقطه زیر پوشش k حسگر جداگانه است [17]. و [18] الگوریتمهاییبراي جایگذاري گره بر پایه الگوریتم ژنتیک پیشنهاددادهاند. هدف از جایگذاري حسگرها در [18] رسیدن به k-coverage و ماکزیمم کردن فضاي پوشانده شده است. نزدیکترین کار به کار ما یک الگوریتم بر پایه Divide-and-Conquer است که در [19] طراحی شده است . در آن الگوریتم، یک تعداد نقطه هدف در ناحیه هستند که به پوشش دوگانه نیاز دارند. تفاوت آن الگوریتم با کار ما این است که ما زیرناحیه هدف را بجاي نقطه هدف در نظر میگیریم.

- 3 تعریف مساله و بهترین پاسخ - 1-3 تعریف مساله

مساله - Connected Target subArea Coverage - CTAC را به صورت شکل 2 تعریف میکنیم. مساله :CTAC فضاي دوبعدي A با زیرناحیههاي هدف دلخواه را در نظر میگیریم. میخواهیم A را به طور کامل به کمک حسگرهایی با شعاع حسی rs و شعاع ارتباطی rc به گونهاي بپوشانیم که:

•    هر زیرناحیه هدف زیر پوشش دستکم دو حسگر باشد.

•    مسیري بین هر دو حسگر پدید آید.

•    به کمترین گره حسگر نیاز باشد.

- 2-3 الگوریتم بهترین پاسخ

متناسب ترین روش حل مساله این است که آزمایش کنیم که آیا میتوان با یک تعداد کم از حسگر این شبکه را پوشاند. اگر پاسخ نه بود، آنگاه تعداد بیشتري از حسگر را آزمایش نماییم. بر پایه این روش که ایده آن را از [19] گرفتیم، الگوریتم بهترین پاسخ - الگوریتم - findBestCTAC را در شکل 3 طراحی کردیم. چون باید همه حالتهاي گزینش N نقطه از بین نقطههاي کاندیدا آزمایش شوند، زمان اجراي این الگوریتم - شکل - 3 داراي پیچیدگی نمایی است . مقدار اولیه Nبه گونهاي انتخاب شده است که تعداد مقدارهایی که N میتواند داشته باشد کاهش یابد. این مقدار اولیه برابر است با مساحت شبکه تقسیم بر مساحت دایره حسی یک حسگر. به بیان دیگر، این مقدار اولیه برابر است با کمترین تعداد حسگرهایی که براي پوشش ساده ناحیه A نیاز داریم.

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