بخشی از مقاله
چکیده
شبکه های حسگر بیسیم شامل صدها یا هزاران گره باانرژی محدود میباشند. از آنجایی که عمر هر حسگر به میزان عمر باتری آن حسگر است، مسئله انرژی بهعنوان چالش اساسی در این شبکهها محسوب میشود. خوشهبندی یکی از کاراترین روشهای کنترل توپولوژی برای کاهش مصرف انرژی بهمنظور افزایش طول عمر در شبکههای حسگر بیسیم است.
متعادل ساختن بار سرخوشه بهعنوان یک چالش برای شبکههای حسگر بیسیمی است که زمان اجرای طولانی دارند. همچنین در نظر گرفتن فاصله گره ها از سرخوشه ها تاثیر بسزای در طول عمر شبکه حسگر بیسیم دارد. از ابن رو یافتن خوشه های بهینه با در نظر گرفتن تعادل بار در سرخوشه ها و فاصله گره ها از سرخوشه ها بهعنوان یک مسأله NP-Hard برای شبکههای حسگر بیسیم با بار نابرابر در گرههای حسگر، محسوب میشود. از این رو برای حل این مساله از الگوریتم تکاملی بیهنه سازی جنگل استفاده نموده ایم. این الگوریتم دارای سرعت و دقت بسیار مناسب در بین الگوریتم های تکاملی می باشد.
در این تحقیق توابع برازندگی جدیدی برای الگوریتم خوشهبندی بر پایه الگوریتم جنگل با در نظر گرفتن تعادل بار و کاهش انحراف میعار فاصله و تعداد گره های هر خوشه برای شبکههای حسگر بیسیم ارائهشده است. نتایج شبیهسازی نشان میدهد که روش پیشنهادی بهبود چشمگیری در پارامترهایی مانند تعادل بار، مصرف انرژی، فرم مناسب خوشه، تعداد گرههای حسگر فعال و تعداد سرخوشههای فعال نسبت به روش قبلی دارد.
-1 مقدمه
پیشرفتهای اخیر در الکترونیک و مخابرات بی سیم توانایی ساخت حسگرهایی با توان مصرفی پایین، کوچک، قیمت مناسب و کاربردهای گوناگون داده است. این حسگرهای کوچک که توانایی انجام اعمالی چون دریافت اطلاعات مختلف محیطی، پردازش و ارسال آن اطلاعات را دارند، موجب پیدایش شبکههایی موسوم به شبکههای حسگر بیسیم شدهاند. شبکههای حسگر بی سیم دارای محدودیتهایی از جمله محدودیت منابع میباشند. محدودیت منابع شامل میزان انرژی محدود، برد ارتباطی کوتاه، پهنای باند پایین، میزان حافظه و پردازش محدود در هر حسگر است.
از آنجایی که یکی از محدودیتهای مهم و جدی در شبکههای ح سگر بی سیم، محدودیت انرژی گرههای حسگر است چرا که با تخلیه شدن انرژی حسگرها و غیر فعال شدن آنها، ارتباط آنها با شبکه قطع شده و دیگر اطلاعاتی از آن ناحیه به کاربر نهایی گزارش نخواهد شد، به همین دلیل محدودیت انرژی پارامتری است که در طراحی الگوریتمها در افزایش طول عمر شبکه حسگر بیسیم بسیار مورد توجه قرار گرفته ا ست و نیاز به روشهایی داریم که بتوانند طول عمر شبکههای حسگر بیسیم را افزایش دهند.
خوشهبندی به عنوان راهکاری برای افزایش طول عمر در شبکه ح سگر بی سیم مطرح میگردد. در خو شه بندی ، محیط شبکه حسگر بیسیم به بخشهای با نام خوشه تقسیم میگردد. گرهها در هر خوشه، اطلاعات را از محیط دریافت و به سرخوشه ارسال میکنند. سرخوشه پس از دریافت آنها را تجمیع میکند. پس از تجمیع، اطلاعات از طریق مسیر تکگامه یا چندگامه به ایستگاه اصلی منتقل میگردد
اندازه خوشه، تعداد سرخوشه در هر شبکه و انتخاب سرخوشه از عوامل مهم در خوشهبندی به شمار میآیند. افزایش تعداد سرخوشه خود باعث سربار اطلاعات کنترلی و مسیریابی میگردد. کاهش تعداد سرخو شه باعث افزایش بار ورودی سرخو شه و تخلیه زود هنگام سرخوشه میگردد. تخلیه زود هنگام سرخوشه باعث تعویض سریعتر سرخوشه میگردد. تعویض زود هنگام باعث افزایش ارسال اطلاعات کنترلی و به دنبال آن اتلاف انرژی میگردد.
موقعیت سرخوشه به عنوان مساله مهم در خوشهبندی به شمار میآید. براساس مدل انرژی، انرژی مصرفی با مجذور فاصله ارتباط مستقیم دارد و در مواردی که فاصله گره از سرخوشه زیاد باشد با توان چهار فاصله رابطه مستقیم دارد. انتخاب نامناسب سرخوشه باعث افزایش فاصله و مصرف انرژی بی شتر خواهد شد. انتخاب سرخو شه تابع تعداد اع ضای خو شه، فاصله اعضای خوشه، فاصله تا سرخوشهها، فاصله تا ایستگاه اصلی و انرژی باقیمانده میباشد
از طرفی در شبکههای حسگر بی سیمی که مبتنی بر خوشه هستند، سرخوشه ها یک بار کاری اضافی را متحمل می شوند زیرااولاً سرخو شه ها با گرههای موجود در خو شهها در ارتباط هستند و ثانیاً عملیات تجمیع داده انجام می دهند و در آخر دادههای پردازش شده را به ای ستگاه ا صلی میفر ستند.
طول عمر سرخوشه ها در زمانی که یک عملیات طولانی در حال اجرا شدن است، ب سیار بحرانی ا ست. بنابراین فرم نامنا سب خو شهها باعث ایجاد کردن بار اضافی میشود. این سربار ممکن است زمان ارسال را به تأخیر بیاندازد و انرژی زیادی از سرخوشه ها مصرف کند وکارایی کل شبکه را پایین بیاورد. بنابراین تعادل بار در سرخوشه ها یک مهم در خوشه بندی محسوب میشود. در حقیقت خوشه بندی با در نظر گرفتن تعادل بار در حالتی که گره ها بار ترافیکی نابرابر دارند، یک NP-Hard است..
الگوریتم های تکاملی مانند الگوریتم ژنت یک یا الگوریتم جنگل می توانند به عنوان یک راه حل مناسب اکتشافی بکار گرفته شوند تا خوشه های بهینه کشف شوند. هدف از این تحقیق ارائه یک روش جدید خوشهبندی با بهرهگیری از الگوریتم جنگل میباشد
که مشکلات توزیع بار نا متنا سب و اتصال با پراکنده گره ها را نیز حل میکند. این الگوریتم خوشهها را طوری فرم میدهد که بار ماکزیمم از هر سرخوشه کم شود. همچنین به دنبال ایجاد خوشه ها به نحوی ا ست، که فا صله گره های ح سگر از سرخو شه ها کمینه شود. هدف بعدی ما در این تحقیق توزیع متناسب گره ها در سرخوشه به نوعی می با شد که انحراف معیار تعداد گره های هر خو شه کمینه شود. زیرا در خو شه هایی که تعداد بی شتری گره ح سگر موجود می ا شد تاخیر ارسال پیام به شدت افزایش می یابد. این الگوریتم باید پارامترهایی نظیر تعادل بار، مصرف انرژی، تعداد گرههای حسگر فعال، تعداد سرخوشه های فعال را اندازه گیری میکند.
در ادامه مقاله، در بخش دوم به بررسی مفاهیم خوشهبندی در حسگر بیسیم و مروری بر مفاهیم الگوریتم جنگل میپردازیم و در ادامه به مروری بر کارهای گذشته میپردازیم. در بخش سوم به روش پیشنهادی جهت افزایش طول عمر شبکه های حسگر بی سیم با استفاده از روش های خوشه بندی و الگوریتم ژنتیک میپردازیم. در بخش چهارم نتایج شبیه سازی ارائه میشود و در انتها نیز نتیجهگیری و پیشنهادات ارائه شده بیان میشود.
-2 پیشینه تحقیق
با پیشر فت تکنولوژی در ارت با طات بیسیم، الکترون یک و میکروسنسور زمینه ایجاد گرههای کوچک، کم هزینه، کم مصرف و چندکاره با برد رادیویی کوتاه و انرژی محدود فراهم گردید. گره ح سگر شامل واحد پردازش، واحد ارسال، واحد دریافت میباشد. شبکه حسگر بی سیم شامل گرههای معمولی، سرخوشه و ایستگاه اصلی میباشد. گره حسگر به دوصورت همگن و ناهمگن میباشد. شبکه حسگر بیسیم شامل صدها یا هزاران گره برای مانیتور کردن محیط میباشد. از گرهها پس از دریافت اطلاعات از محیط، بر روی آنها پردازش انجام میدهد، سپس به ایستگاه اصلی به صورت تکگامه یا چندگامه ارسال می نمایند
با توجه به انرژی محدود گره ها، فعال یت تمامی گره ها به طور همزمان، خود باعث تخلیه انرژی گرهها و کاهش طولعمر میگردد. از این رو مساله انرژی خود یک بحران در شبکه حسگر بیسیم محسوب میگردد. پروتکلهای خوشهبندی، روش مناسبی برای بالابردن طول عمر شبکه حسگر بیسیم میباشند. در خوشهبندی، کل شبکه به خو شههای تقسیم میگردد. در هر خوشه یک گره به عنوان سرخوشه انتخاب میگردد. اعضای خوشه اطلاعات پردازش شده خود را به صورت تکگامه یا چندگامه به سرخو شه منتقل مینمایند. سپس سرخو شه اطلاعات را پس از تجمیع، به ای ستگاه ا صلی از طریق م سیر تکگامه یا چند گامه منتقل مینماید
-1-2 اهداف خوشهبندی
اهداف خوشهبندی براساس کاربردهای خاص متفاوت میباشد. برای مثال در برخی کاربردها تاخیر داده، ارتباطات درون-برون خوشه مد نظر میباشد. به طور کلی این اهداف به چندین دسته تقسیم میگردد. در زیر به مهمترین آنها پرداخته میشود
- 1متعادل ساختن بار - 2تحمل پذیری خطا - 3 افزایش طول
2-2مزایای خوشهبندی
مقیاسپذیری به عنوان یکی از مهمترین عوامل در شبکه حسگر بیسیم مطرح میگردد. با استفاده از خوشهبندی میتوانیم به مقیاسپذیری و افزایش طول عمر در شبکه حسگر بیسیم دست یابیم. در زیر به مزایای خوشهبندی شبکه حسگر بیسیم میپردازیم:
1 - کاهش اندازه جدول مسیریابی: با خوشهبندی، مسیریابی در هر خوشه به صورت محلی میباشد. که منجر به کاهش اندازه جدول مسیریابی میگردد.
- 2 صرفه جویی در پهنای باند: با استفاده از خوشهبندی،
ارتباطات برون کاهش مییابد. این کار باعث صرفه جویی در پهنای باند ارتباطی میگردد.
- 3 مدیریت آسانتر شبکه حسگر بیسیم: خوشه بندی باعث کاهش اطلاعات توپولوژی شبکه بی سیم می گردد.
-3-2 چالشهای خوشهبندی
برخی چالشهای خو شهبندی در شبکه ح سگر بی سیم به صورت زیر میباشد :
1 - اندازه خوشه: فرآیند انتخاب سرخوشه و اندازه خوشه باید به گونهای باشد که بار خوشهها متعادل باشد. در صورتیکه اندازه خوشهها نامتوازن باشد، برخی از خوشهها زودتر از بین میروند. برخی دیگر دیرتر از بین میروند.
2 - تعداد سرخوشه : ایجاد تعداد مناسب خوشه باعث افزایش کارایی در شبکه حسگر بیسیم میگردد.
3 - همپوشانی خوشهها: در خوشهبندی گرهها، حداقل همپوشانی خوشهها چالش در شبکه حسگر بیسیم به شمار میآید.
4 - انتخاب سرخوشه: انتخاب سرخوشه چالش محسوب میگردد. هدف از خوشهبندی در نظر گرفتن حفظ انرژی و پوشش شبکه میباشد. البته رعایت حفظ انرژی دلیل بر پوشش مناسب شبکه نخواهد بود. داشتن پوشش مناسب شبکه، دلیل بر کارآمد بودن مصرف انرژی نخواهد بود.
-4-2 الگوریتمهای خوشهبندی
ارتباطات شبکه را میتوان به صورت گراف بدون جهت G= - V,E - مدل کرد. V مجموعه رئوس که بیانگر گرههای حسگر و E مجموعه لبههای گراف، بیانگر لینک ارتباطی بین دو گره همسایه میباشد. هدف الگوریتمهای خوشهبندی، تقسیم گراف G به زیر مجموعههای ارتباطی میباشد. زیر مجموعه گرههای VD ، مجموعه ناحیه -Dگامه نامیده میشود. در خوشه -Dگامه، هر گره حداکثر -Dگام تا سرخوشه فاصله دارد. الگوریتمهای خوشهبندی معمولا در دو فاز راهاندازی و فاز نگهداری اجرا میشوند. در فاز راهاندازی مراحل انتخاب سرخوشه و شکلگیری خوشه انجام میگیرد. در فاز نگهداری زمانبندی اعضای خوشه، جمعآوری اطلاعات اعضای خوشه و پیکربندیهای ناشی از تغییرات گره در طی فاز راهاندازی یا تغییرات توپولوژی انجام میگیرد.
1-5 -1 -5-2 الگوریتمهای انتخاب خوشه بندی با استفاده از روش های فرا ابتکاری
در [5] الگوریتم ژنتیکی برای پیدا کردن سرخوشه های مناسب جهت مینیمم کردن مسافت کلی شبکه ارائه شد. در این جا از نمایش باینری کروموزوم ها استفاده می کند که هر بیتِ موجود در آن با یک گره ی حسگر انطباق دارد. دو فاکتور جهت کاهش در این الگوریتم ژنتیک مد نظر قرار می گیرند. مسافت کلی انتقال و تعداد سرخوشه ها، دو فاکتور اصلی مورد نیاز می باشند که می بایست کاهش یابند.
تابع برازندگی ارائه شده به شکل زیر میاشد:
در این فرمول D فاصله ی کلی تمامی گره ها تا ایستگاه اصلی می باشد که از مجموع فاصله تمامی گره ها تا سرخوشه ها به اضافه ی مجموع فاصله ی تمامی سرخوشه ها تا ایستگاه اصلی می باشد.
