خوشه بندی در شبکه های حسگر بی سیم

در این بخش با یک مقاله کوتاه در رابطه با خوشه بندی در شبکه های حسگر بی سیم در خدمت شما دوستان گرامی هستیم که امیدواریم بررسی و مطالعه مطالب ارائه شده در این بخش مفید و مورد استفاده قرار گیرد، در ادامه با ما همراه باشید.

شبکه های حسگر بی سیم

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

کاربرد شبکه های حسگر بی سیم

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

مسیریابی سلسله مراتبی در شبکه WSN

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

پروتکل های خوشه بندی در شبکه WSN

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

پروتکل LEACH

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

روش های خوشه بندی در شبکه WSN

از جمله تکنیک های رایج دیگر برای خوشه بندی شبکه های حسگر، استفاده از الگوریتم K Means و الگوریتم Fuzzy C Means (FCM) می باشد. در نوع ساده از این الگوریتم ها، ابتدا به تعداد خوشه های مورد نیاز نقاطی به صورت تصادفی انتخاب می شوند، سپس گره ها با توجه به کمترین فاصله تا مرکز خوشه، یکی از مراکز خوشه ها را انتخاب کرده و به آن خوشه ملحق می شوند و خوشه های جدید را ایجاد می کنند. با تکرار همین روال و با میانگین گرفتن از فاصله گره ها تا مرکز خوشه فعلی، مراکز جدید برای خوشه ها بدست خواهد آمد.

این روند تا زمانی که تغییری در مکان مراکز خوشه حاصل نشود ادامه پیدا می کند. به طور مثال الگوریتم ارائه شده در مقاله k-MEANS CLUSTERING IN WIRELESS SENSOR NETWORKS بر اساس الگوریتم K Means عملیات خوشه بندی شبکه حسگر را انجام می دهد. بعد از خوشه بندی، به منظور انتخاب سرخوشه مناسب، نزدیکترین گره به مراکز حاصل از اجرای الگوریتم K Means در مرحله قبل که بیشترین انرژی را داراست به عنوان سرخوشه انتخاب می گردد.

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

خوشه بندی کلاسیک

روش های خوشه بندی کلاسیک نسبت به نقاط شروع به شدت حساس هستند و اغلب به علت انتخاب غیر صحیح این نقاط، الگوریتم مورد نظر به سمت نقاط بهینه محلی همگرا شده و از نقاط بهینه سراسری دور می شوند. واضح است که خوشه بندی شبکه حسگر با هدف کمینه کردن میزان انرژی مصرفی یک مسئله NP Hard می باشد.

از آن جایی که الگوریتم های فرا ابتکاری رویکرد مؤثری برای حل مسائل بهینه سازی پیچیده در علوم مختلف هستند، بنابراین استفاده از این الگوریتم ها برای حل مسائل خوشه بندی مفید می باشد.