بخشی از مقاله
چکیده :
یکی از مهمترین مباحث مربوط به شـبکه هاي حسـگر بیسـیم ، بحث خوشه بندي می باشد و این بحث در شبکه هاي حسگر بیسـیم متحرك نمود بیشتري پیدا میکند. زیرا مکان قرار گرفتن گرههاي حسگر، از قبل تعیین شده نیست و این گره ها داراي حرکت هسـتند. ویژگی اصلی این نوع شبکههاي بیسیم خودسازماندهی میباشد. براي انجام این کار الگوریتمهاي مختلفی ارائه شده است. در اکثر روشهاي ارائه شده قبلی به فاکتورهاي مهمی همچون مرکزیت، چگالی و حتیانرژي توجه کمتري دارند درحالیکه خصوصاً در مورد شـبکه هاي متحرك این فاکتورها باید مورد توجه بیشـتري قرار گیرند. همچنین از کار افتادن سـرخوشـه در یک راند باعث میشود تا اطلاعات خوشـه در آن راند بدسـت پایگاه مرکزي نرسد و این امر باعث افت شدید کارایی شبکه خواهد گشت . در الگوریتم پیشنهادي تمام این فاکتورها براي انتخاب سرخوشه مورد نظر قرار گرفته است. همچنین شبکه بگونهاي خوشه بندي میشود که براي هر سرخوشه یک جایگزین در نظر گرفته میشـود. بدین ترتیب عمر مفید شبکه افزایش مییابد. این متد توسط نرمافزار Matlab شبیه سازي شده و
نتایج آن نشان میدهد که این متد موجب بهبود قابل توجهی در بازدهی و نیز پوشش شبکه بدست آمده است.
کلمات کلیدي : گره حسگر بیسیم، خوشه بندي، متحرك، مصرف بهینه.
-1 مقدمه
یک گره حسگر بی سیم شامل یک میکروکنترلر ، رادیو ، سنسورهاي مختلف ، حافظه و باتري است. یک شبکه حسگر بی سیم شامل گره هاي حسگري است که پدیده هاي مختلف محیط اطراف را حس می کنند. یک شبکه حسگر متشکل از تعداد زیادي گره هاي حسگر است که در یک محیط به طور گســترده پخش شــده و به جمع آوري اطلاعات از محیط می پردازند. شبکه هاي حسگر بیسیم از لحاظ مصرف انرژي داراي محدودیت میباشند. روش هایی که براي مســیریابی و انتقال داده ها در این نوع شــبکه ها ارائه می شــود باید حتی المقدور از نقطه نظر مصــرف انرژي بهینه باشــند. یکی از روش هایی که براي نیل به این هدف ارائه شـــده روش خوشـــه بندي میباشـد. در این روش، در هر خوشه یک گر ه به عنوان سـرخوشـه در مرکز خوشه قرار گرفته و گره هاي دیگر داده هاي خام را به آن گره ارســال می نمایند. ســپس گرة مرکزي داده ها را پس از فشــرده ســازي به پایگاه مرکزي ارســال می نمایند. انتخاب مناســب ســرخوشــه باعث کاهش مصــرف انرژي مصــرفی و در نتیجه باعث افزایش طول عمر مفید شـبکه می شود. تشکیل خوشه
هـا جهـت برپـایی این نوع مســـیریابی باید به گونه اي صــورت گیرد تا به محدودیت هاي شــبکه هاي حســگر بیسیم مانند انرژي مصرفی توجه شود. در سالهاي اخیر بـا توجـه بـه کـاربردهـاي این نوع شـــبکه ها از جمله کاربردهاي نظامی، فوریت هاي پزشــکی، زلزله نگاري و غیره محققان پیشــنهادات گوناگونی را جهت برپایی هر چه بهتر این نوع شبکه ها معرفی نموده اند.
-2 کارهاي انجام شده
با توجه به جدید بودن شـــبکه هاي بیســـیم متحرك کارهاي محدودي در این زمینه انجام گرفته اســـت. که در زیر به برخی از آنها اشاره میکنیم :
در[1] الـگـوریـتـم Tandem بـراي هر گره، الگوریتم شناسایی اطلاعات همسایه را بطور مداوم با همسایگانش انجـام میـ دهـد. این الگوریتم عـددي که نمایانگر نحوه ارتباط دو گره با یکدیگر است را تولید میکند و با توجه به آن تصمیم به ترك یا اتصال خوشه میکند.
در [2] الگوریتم DMAC خوشه هاي تک گامی را تولید میکند. آن الگوریتمی سبک وزن است که بصورت ثبت سرویس توزیعی عمل میکند و با تصمیم گیري فقط بر اســاس اطلاعات همســایه نســبت به تغییرات توپولوژي
عکسالعمل نشان میدهد.
در [3] الگوریتم G-DMAC همـانند DMAC خوشـــه هاي تک گامی ایجاد میکند با این تفاوت که با مشخص کردن حداکثري براي سـرخوشه، آنها را براي سرخوشه عوض کردن محـدود میکنـد و کاري میکند تا هر گره حتی المقدور ســرخوشــه خود را عوض نکند واین باعث کاهش سربار شبکه نسبت به DMAC میگردد..
الگوریتم خوشه بندي سلسله مراتبی
الگوریتم HEED یکی از معروفترین و بهترین روشهایی اســت که تاکنون در زمینه خوشــه بندي شــبکه هاي حسگر بیسیم ارائه شده است. این الگوریتم به دو فاکتور مهم انرژي گره ها و فاصـــله آنها براي انتخاب مناســـب ترین سرخوشه ها توجه می کند.
چگونگی انتخاب سـرخوشه ها در الگوریتم [4] HEED بـه این شـــکل اســـت که در این روش فرآیند انتخاب سرخوشه براي هر گره نیازمند چندین چرخه می باشد. بازة زمانی هر چرخه باید به اندازة کافی بزرگ باشـــد تا یـک گره بتوانـد تمامی پیام هاي ارســـالی از گره هاي اطرافش را دریـافــت کنـد. هر گره احتمــال اولیــه براي انتخاب شدن به عنوان سرخوشه را به این شکل در نظر می گیرد : . = C
در فرمول فوق بیـانگر انرژي باقیماندة گره و بیانگر انرژي اولیه گره می باشـــد. در ابتداي هر چرخه، هر گره با احتمال تصمیم می گیرد که سرخوشه شود. اگر گره اي تصمیم بگیرد سرخوشه شود یک پیام به دیگر گره ها ارســال می کند. این تصــمیم گیري در ابتدا موقتی اســـت و پس از گذشـــت چندین تکرار نهایی می شـود. هر یک از همسـایگان در صورتی که پیش از این عضـو خوشـهاي نشـده باشـد، عضو این خوشه می گردد. در صورتی که همسایه اي پیش از این عضو خوشهي دیگري باشد که انرژي باقیماندة سرخوشه آن نسـبت به انرژي باقیماندة سـرخوشه جدید پایین تر باشد، همسایه به خوشه جدید ملحق می شود. به علاوه، در صـورتی که همسایه اي خود سرخوشه باشد، پس از
مقایسـه خود با میزان انرژي باقیماندة سرخوشه معرفی شـده، تصـمیم می گیرد که همچنان رأس خوشه باقی بماند یا به خوشـه جدید منتقل شـود. الگوریتم HEED سـرخوشه ها را براساس دو فاکتور مهم انرژي گره ها و فاصــله بین آنها انتخاب می کند. یکی از مشــکلات این الگوریتم لزوم ارسال چندین پیام بین گره هاي شبکه و گذر از چندین چرخه براي انتخاب سرخوشه هاي نهایی می باشد.
بطور خلاصه پروتکل بصورت زیر کار می کنند :
• گرههـایی کـه درجههاي قابلیت بالایی نســـبت به همسایگان خود دارند. سرخوشه ها را به آنها اعلام میکنند و پیغام SetRoot را پخش می کنند.
• گره هاي باقیمانده ، همسایه با درجه قابلیت بالاتر را به عنوان پدر انتخاب می کنند.
• زمـانیکـه گره پیغـام SetRoot را از پدرش دریافت کرد عضـــویـت خوشـــه را متوجه شـــده و پیغام SetRoot را پخش می کند.
-3 الگوریتم پیشنهادي
همانطور که در بخش پیش اشـــاره شـــد بســـیاري از روشـهاي ارائه شـده در زمینه خوشـه بندي شبکه هاي حسـگر بیسـیم متحرك و ثابت ارائه شده است، اما آنها فاکتورهاي اندکی را براي انتخاب ســرخوشــه ها در نظر میگیرنـد و ممکن اســـت به فاکتورهاي مهمی همچون مرکزیـت، چگـالی و حتی انرژي توجه کمتري داشـــته باشند. درحالیکه براي نیل به روش خوشه بندي مطلوب بـاید فاکتورهاي ذکر شـــده مورد توجه بیشـــتري قرار گیرند. در ادامه این بخش ضمن توضیح روش یشنهادي به بررسـی این فاکتور پرداخته شده و چگونگی استفاده از آنها در الگوریتم پیشنهادي توضیح داده میشود.
