مقاله روشی برای خوشه بندی شبکه های حسگر بی سیم با چاهک متحرک

بخشی از مقاله

چکیده

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

یکی از راههای کاهش مصرف انرژی خوشهبندی است. با خوشهبندی گرههای حسگر و ایجاد توازن در خوشهها میتوان مصرف انرژی را در شبکه متوازن ساخت تا از مرگ زودرس گرهها جلوگیری و طول عمر شبکه را افزایش داد. در این مقاله، به منظور کاهش مصرف انرژی گرهها، الگوریتمی برای مسیریابی چاهک متحرک مبتنی بر خوشهبندی پیشنهاد شده است. نتایج با الگوریتم-های LEACH و LEACH-C و LEACH-F و VCH و EEHCCP مقایسه شده است و نشان میدهد الگوریتم پیشنهادی در مصرف انرژی و ایجاد توازن انرژی، موثر بوده است و طول عمر شبکه افزایش یافته است.

مقدمه

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

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

یکی از مسائل اساسی در شبکههای حسگر بیسیم، افزایش طول عمر شبکه میباشد. ازآنجا که طول عمر گرهها به علت محدودیت انرژی منبع تغذیه، کوتاه است و تعویض باتری گرهها امکانپذیر نیست، درنتیجه، عمر شبکهای حسگر نیز نوعاً کوتاه است. علاوه بر این، گاهی موقعیت ویژه یک گره در شبکه، مشکل را تشدید میکند؛ به عنوان مثال، گرهای که در فاصله یک قدمی گره اصلی یا چاهک قرار دارد، از یک طرف به دلیل بار کاری زیاد خیلی زود انرژی خود را از دست میدهد و از طرف دیگر، از کار افتادن آن باعث قطع ارتباط گره اصلی با کل شبکه میشود و لذا کار شبکه مختل میگردد.

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

خوشهبندی یک تکنیک یادگیری غیر نظارتی در یادگیری ماشین است. خوشهبندی برای پیدا کردن موقعیت مجموعه داده روی ویژگی خاصی استفاده میشود - Jordan and Mitchell, 2015 - که در برخی کاربردها این ویژگی میتواند فاصله باشد. تحلیل خوشهبندی عمدتاً در شناسایی الگو، پردازش تصویر، اطلاعات زیستی به کار برده میشود. - Le and Tuan, 2015 - - Benson et al. 2016 - . - Mehta and Dikshit, 2016 - - Yaqing et al. 2014 - برای اینکه کیفیت بالایی از خوشهبندی داشته باشیم روشهای متفاوتی پیشنهاد شده است.

این روشها تقسیم میشوند به: روشهای بخشبندی، روشهای سلسلهمراتبی، روشهای مبتنی بر چگالی، روشهای مبتنی بر گرید و روشهای محاسبات نرم. روش بخشبندی، با حرکت نقاط طبق فاصله، آنها را از یک طبقه به دیگری جابهجا میکند. این روشها همیشه نیازمند تعداد خوشهها میباشند. روش سلسهمراتبی، دستهبندی را به وسیلهی طبقهبندی بازگشتی داده به صورت بالا به پایین یا پایین به بالا انجام میدهد . - Murtagh and Contreras 2012 - روش مبتنی بر چگالی، فرض میکند نقاطی که متعلق به هر خوشه هستند از توزیع احتمال خاصی ناشی میشود.

خوشهها با اشکال دلخواه توسط روشهای مبتنی بر چگالی بدست میآیند. روش مبتنی بر مدل میتواند نتایج خوشهبندی را با استفاده از بهینهسازی تناسب بین داده معین و برخی مدلهای ریاضیاتی بدست آورد. در روش مبتنی بر گرید، فضای داده به تعداد محدودی واحد گرید تقسیم میشود. روشهای تکاملی متعلق به روشهای محاسبات نرم، برای رسیدگی به مشکلات خوشه-بندی استفاده میشوند. پروتکل مسیریابی LEACH مشهورترین پروتکل ارتباطی مبتنی بر خوشهبندی برای شبکههای حسگر بیسیم است.

این پروتکل از چرخش تصادفی سرخوشهها استفاده میکند تا انرژی را در میان گرهها در شبکه توزیع کند. هر سرخوشه یک پیام اعلان را برای به اشتراکگذاری وضعیتش با سایر گرههای حسگر به صورت همه پخشی ارسال میکند. هر گره خوشهای را که سرخوشه آن حداقل انرژی را برای ارتباط نیاز دارد انتخاب میکند. LACH-C نسخهی متمرکز LEACH است. تنها تفاوت این است که LEACH-C در هر دور از ایستگاه پایه برای تصمیمگیری در مورد سرخوشهها استفاده میکند.

LEACH-F نیز نسخهی ایستای LEACH است. تنها تفاوت آن این است که از خوشههای ایستا استفاده میکند. خوشههایی که در دور اول تشکیل میشوند ایستا هستند و برای طول عمر سراسر شبکه استفاده میشوند. در هر خوشه نقش سرخوشه درمیان اعضای وابسته به خوشه میچرخد. VCH بسیار شبیه LEACH است اما زمان خوشهبندی مجدد را به تأخیر میاندازد. در VHC خوشهها برای دو دور متوالی ایستا هستند و خوشهبندی مجدد در پایان هر دور دوم انجام میشود. سرخوشه جاری یک VCH میان اعضای خوشه انتخاب میکند، بنابراین سربار تنظیم سرخوشه برای یک دور کاهش می-یابد. EEHCCP فرایند ارتباط را به چند دور تقسیم میکند.

در هر دور EEHCCP نقش سرخوشه را بر اساس انرژی باقی مانده می-چرخاند. EEHCCP تشکیل خوشهبندی ایستا و پویا را ترکیب میکند و یکی از این توابع رابراساس پارامتر کنترلیِ میانگین انرژی اعضای خوشه انتخاب میکند. در دور اول هر گره اطلاعات خودش را به ایستگاه پایه ارسال میکند. سرخوشه تعداد سرخوشههایی را که میخواهد انتخاب میکند، انتخاب سرخوشه براساس مکان و وضعیت انرژی همهی گرهها است. ایستگاه پایه گرهای که در هر خوشه بالاترین مقدار انرژی را دارد پیدا میکند و آنها را برای سرخوشه بودن تعیین میکند. - Pachlor and Shrimankar, 2018 - در این مقاله یک روش خوشهبندی برای دستهبندی گرهها و همچنین روشی برای تعیین مسیر حرکت چاهک متحرک برای جمعآوری اطلاعات پیشنهاد شده است.

کارهای مرتبط:

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

Rodriguez و Laio، یک الگوریتم خوشهبندی جدید برای پیداکردن قلههای چگالی ارائه دادهاند. این الگوریتم میتواند یک گراف پراکندگی که دیاگرام تصمیم نامیده میشود ایجاد کند. این گراف طبق چگالی محلی نقاط و فاصلهاش تا نزدیکترین نقطه که بالاترین چگالی را دارد بدست میآورد. با کمک قضاوت بصری، این نقاط که متعلق به مراکز خوشه هستند میتوانند از دیاگرام تصمیم تشخیص داده شوند و نقاط باقی مانده را به نزدیکترین همسایهای که بالاترین چگالی را دارند اختصاص داده میشوند.

این الگوریتم قادر است خوشههای غیرکروی را تشخیص دهد و نیازمند تعیین تعداد خوشه ها نمیباشد. - Rodriguez and Laio, 2014 - Du و همکارانش، ایدهی KNN و PCA را در میان DPC مطرح نمودند تا عملکرد DPC را بهبود دهند. - Du et al, 2016 - روش LEACH، اولین پروتکل مسیریابی خوشهبندی برای شبکههای حسگر بیسیم است. ایده کلیدی این پروتکل انتخاب تصادفی مجموعهای از گرههای حسگر به عنوان سرخوشه و انتصاب این وظیفه به صورت چرخشی برای توزیع یکنواخت انرژی میان گرههای شبکه میباشد.

Aslamet و همکارانش، پروتکل ناهمگونی با نام پروتکل خوشهبندی انرژی متمرکز - CEEC - را پیشنهاد دادهاند. نویسندگان سه سطح ناهمگن معرفی کردهاند. منطقه شبکه به سه منطقه مستطیلی تقسیم شده است که اندازه آنها با هم برابر است. این منطقه به عنوان منطقه انرژی سطح بالا نامیده میشوند که شامل تنها گرههای فوقانی است، منطقه انرژی متوسط، شامل تنها گرههای پیشرفته و منطقه انرژی کم، حاوی گرههای طبیعی است. گره فقط میتواند با انواع خاص خود در یک خوشه قرار گیرد.

- Aslamet al, 2012 - Qureshi و همکارانش، یک پروتکل فوقالعاده ناهمگن را به نام - BEENISH - پیشنهاد کردهاند. درBEENISH، چهار سطح ناهمگونی در نظر گرفته شده است، سطوح مختلف گرهها به عنوان گرههای طبیعی، پیشرفته، فوقالعاده و فوقالعاده فوق شناخته میشوند. گرهها به صورت تصادفی در سراسر شبکه پخش میشوند و انتخاب سرخوشه به طور کامل بر اساس انرژی باقیمانده و همچنین انرژی متوسط گرههای مستقر شده است. استراتژی انتخاب سرخوشه از BEENISH اجازه میدهد تا گرههای با انرژیهای بالاتر با تبدیل شدن به سرخوشه به این ترتیب، گرههای که انرژی بالاتری نسبت به بقیه دارند شانس بیشتری برای تبدیل شدن به سرخوشه دارند. انتخاب سرخوشه با انرژی بیشتر کمک میکند تا ثبات و عمر بیشتری کسب کنید.

- Qureshi et al, 2013 - Gao و همکارانش الگوریتمی به نام ICFS ارائه داده است، این الگوریتم بر ضعفهای CFS غلبه میکند. الگوریتم CFS براساس چگالی و فاصله نقاط از یکدیگر گراف تصمیم را رسم کرده و مراکز خوشه را تعیین میکند. فاصله قطع درخوشهبندی بسیار موثر است. الگوریتم ICFS یک فرمول جدید برای محاسبه فاصله قطع طراحی کرده است. همچنین با ادغام و تجزیه خوشهها دقت خوشهبندی را افزایش میدهد. - Gao et al, 2016 -