پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 42 |
| تعداد شماره‌ها | 1,537 |
| تعداد مقالات | 12,623 |
| تعداد مشاهده مقاله | 25,817,054 |
| تعداد دریافت فایل اصل مقاله | 10,659,942 |
بهبود کارایی شبکه‌های حسگر بی‌سیم سه‌بعدی با قابلیت جابهجایی گرهها | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| هوش محاسباتی در مهندسی برق | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مقاله 7، دوره 11، شماره 3، مهر 1399، صفحه 65-82 اصل مقاله (1.53 M) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| شناسه دیجیتال (DOI): 10.22108/isee.2020.118189.1258 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| نویسندگان | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مهدی سالخورده حقیقی* 1؛ پیام امین امین الشریعه نجفی2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 1استادیار، دانشکده مهندسی کامپیوتر و فناوری اطلاعات - دانشگاه صنعتی سجاد - مشهد - ایران | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 2کارشناسی ارشد، دانشکده مهندسی کامپیوتر و فناوری اطلاعات - دانشگاه صنعتی سجاد - مشهد - ایران | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| چکیده | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| یکی از مهم‌ترین ابزار کسب اطلاعات و درک محیط، شبکه‌های حسگر بی‌سیم‌اند[i]. این شبکه‌ها پژوهش‌های گسترده‌ای را به خود معطوف کرده‌اند. پیشرفت‌های اخیر در حوزۀ الکترونیک و مخابرات بی‌سیم باعث شده است حسگر‌هایی با توان مصرفی پایین، اندازۀ کوچک، قیمت مناسب و کاربردهای گوناگون، طراحی و ساخته شوند. تا کنون بیشتر پژوهش‌های انجامشده در این زمینه، روی طراحی دوبعدی شبکه‌های حسگر بی‌سیم تمرکز داشته‌اند؛ درحالی‌که این طراحی از دنیای واقعی و کاربردهای آن به‌دور است. از این نظر، مطالعه‌ها روی شبکه‌های حسگر بی‌سیم سه‌بعدی آغاز شدهاند که با محیط واقعی تطابق بیشتری دارند و در کاربردهای متداولی همچون شبکه‌های حسگر زیر آب، اتمسفر و جنگل‌ها و محیط‌هایی با موانع مرتفع استفادۀ بیشتری دارند. هدف این مقاله، افزایش طول عمر شبکه با تغییر پارامترها و افزودن قابلیت‌هایی به الگوریتم خوشهبندی فازی است که برای استفاده در خوشهبندی سه‌بعدی توسعه داده شده است. این الگوریتم تعمیم‌یافته، الگوریتم فازی C میانگین[ii] است که برای شبکه‌های حسگر بی‌سیم سه‌بعدی طراحی شده است. با افزودن قابلیت جابهجایی محدود به گرهها و در نظر گرفتن محیط سه‌بعدی برای گرهها، انتظار بهبود در عملکرد شبکه به‌ویژه ازنظر طول عمر وجود دارد. نتایج آزمایش‌ها نشان می‌دهند روش پیشنهادی برای افزایش طول عمر شبکه، موفق به بهبود عملکرد نسبت به الگوریتم‌های دیگر شده است. [i] Wireless Sensor Network [ii] Fuzzy C-means | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| کلیدواژه‌ها | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| شبکۀ حسگر بی‌سیم سه‌بعدی؛ خوشهبندی فازی؛ FCM-3؛ FCM | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| اصل مقاله | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
1- مقدمه[1] شبکۀ حسگر بی‌سیم، شبکه‌ای است که شامل حسگرهای خودمختار است. این حسگرها برای نظارت بر شرایط فیزیکی یا محیطی در منطقه پخش شدهاند. گره شبکۀ حسگر بی‌سیم شامل اجزای تکنیکی متعددی ازجمله رادیو، باتری، میکروکنترلر، مدار آنالوگ و واسط حسگر[i] است [1]. گرههای حسگر، مسئولیت حس‌کردن، اندازه‌گیری و تجمیع اطلاعات از محیط را دارند که آنها را ازطریق امواج رادیویی در یک ارتباط بی‌سیم به ایستگاه پایه منتقل می‌کنند [2]. طراحی شبکه‌های حسگر بی‌سیم همیشه بر یک نقطه‌نظر خاص تمرکز کرده و آن طراحی شبکه در فضای دوبعدی است [2]. این تقریب خوبی برای کاربردهایی است که در آنها گرهها روی سطح زمین پخش شدهاند و ارتفاع شبکه در مقایسه با طول و پهنای آن ناچیز است [3]؛ ولی این فرض دوبعدی در کاربردهای نقض می‌شود که ارتفاع شبکه در آن زیاد است و گرهها در یک فضای سه‌بعدی پخش می‌شوند،؛ درنتیجه، نا‌مناسب‌بودن این طراحی و نیاز به مطالعه روی بعد سوم حس می‌شود. درحقیقت سناریوهای سه‌بعدی شبکۀ حسگر بی‌سیم با کاربردهای دنیای واقعی تطبیق بیشتری دارند [4]. نظارت بر یک منطقۀ بزرگ با شبکۀ حسگر بی‌سیم مستلزم تعداد زیادی گره حسگر با مصرف انرژی بالا است [4]. بعد از توزیع گرههای حسگر در محیط، شارژکردن یا جابهجا کردن باتری آنها تقریباً غیر‌ممکن است، زیرا محیط‌هایی که شبکه در آنها مستقر می‌شود، دور از دسترس انسان‌اند. بنابراین مهم‌ترین چالش گرههای حسگر، بهینه‌سازی مصرف انرژی آنها است که مستلزم یک توپولوژی مناسب از گرهها در محیط سه‌بعدی است تا مصرف انرژی آنها کمینه شود [5-7]. خوشهبندی، روش مؤثر برای این مسئله است. این استراتژی در بعضی از پروتکل‌های خوشهبندی معروف مانند LEACH-C، [8] K-means و[6] FCM استفاده شده است؛ اما هیچ‌یک از آنها ارتباط مستقیم بین گره غیر سرخوشه و گره سرخوشه و بین گره سرخوشه و ایستگاه پایه را تضمین نمی‌کنند؛ درنتیجه، این احتمال وجود دارد که تعداد گرههای معمولی (غیر سرخوشه) که فاصلۀ آنها تا گره سرخوشه بیشتر از محدوده رادیویی‌شان است، در خوشه‌های جدید افزایش یابد [9،10]. همچنین تعداد گرههای سرخوشه‌ای که فاصله‌شان تا ایستگاه پایه بیشتر از محدوده رادیویی‌شان است، بیشتر می‌شود. این مشکل به بهینه‌بودن انتقال داده مربوط می‌شود [10]. همچنین موقعیت‌هایی پیش می‌آید که در آنها اندازۀ خوشه‌ها بسیار بزرگ است یا تعداد گرههای غیرسرخوشه در خوشه زیاد می‌شود که این مسئله باعث کاهش شدید انرژی گره سرخوشه و مرگ زودرس آن می‌شود [11]؛ بنابراین، طراحی یک الگوریتم خوشهبندی جدید، نیاز مبرم است تا مشکل مصرف انرژی، انتخاب سرخوشه‌ها و ایجاد توازن بار[ii] بین خوشه‌ها را حل کند. به‌طور کلی یک تقسیم‌بندی در شبکه‌های حسگر بی‌سیم، ایستا یا پویابودن آنها از جنبه‌های مختلف است. این جنبه‌ها شامل توپولوژی، مسیریابی، قرارگیری گرهها، چرخش یا جابهجایی آنها یا موارد دیگرند؛ بنابراین، روش‌های خوشهبندی باید سازگار و قابلیت تغییر پیکربندی را داشته باشند. در این پژوهش، پویایی در جابهجایی محدود گرههای حسگر در نظر گرفته شده و پروتکل خوشهبندی ارائه‌شده با این فرض تحلیل شده است. یکی از پروتکل‌های بهینه ارائه‌شده در زمینۀ بهینه‌سازی مصرف انرژی گره در خوشهبندی شبکه‌های حسگر بی‌سیم، الگوریتم فازی C میانگین است که مشکل ابهام مرزهای بین خوشه‌ها را در روش‌های خوشهبندی همچون LEACH و K-means برطرف می‌کند [12]. فازی C میانگین به‌طور گسترده برای بهینه‌سازی مصرف انرژی گرهها در شبکۀ حسگر بی‌سیم استفاده شده است؛ بااین‌حال این روش، مصرف انرژی را در تابع هدف خود در خوشهبندی در نظر نگرفته است. همچنین از محدودیت‌ها در ارتباطات بین گرهها و سرخوشه‌ها و از سرخوشه‌ها به ایستگاه پایه، چشم‌پوشی کرده است؛ درنتیجه، این الگوریتم برای شبکه‌های حسگر بی‌سیم سه‌بعدی که با کاربردهای دنیای واقعی تطابق بیشتری دارند، مناسب نیست؛ ازاین‌رو، الگوریتم FCM-3WSN [13] ارائه شد که بسیاری از نقص‌های الگوریتم FCM را برطرف کرد و آن را برای شبکه‌های حسگر بی‌سیم سه‌بعدی مناسب‌تر کرد. در این مقاله تلاش شد با اضافه‌کردن قابلیت‌هایی به الگوریتم FCM-3WSN و ایجاد تغییراتی در آن، این الگوریتم ازنظر کارایی و مصرف انرژی، بهتر باشد و نتایج مطلوبی به دست آید. در ادامه از این الگوریتم با نام الگوریتم پایه اشاره شده است. در ادامه، در بخش دوم، مروری بر مطالعات پیشین و کارهای انجامشده در زمینۀ خوشهبندی در شبکه‌های حسگر بی‌سیم دوبعدی و سه‌بعدی انجام شد. در بخش سوم، روش پیشنهادی، ارائه و تشریح شد. در بخش چهارم، نتایج حاصل از پیاده‌سازی روش پیشنهادی، بررسی و با دیگر روشها مقایسه شدند. در بخش پنجم، نتیجه‌گیری شد و منابع معرفی شدند. 2- مطالعات پیشین همان‌طور که گفته شد مصرف انرژی حسگرها و طول عمر شبکه، همواره از مهم‌ترین چالش‌های شبکه‌های حسگر بی‌سیم است و هدف ما نیز کاهش مصرف انرژی و افزایش طول عمر شبکه است. برای دست‌یابی به این مهم، باید توپولوژی مناسب برای شبکه انتخاب شود. سه نوع توپولوژی شبکه در شبکۀ حسگر بی‌سیم وجود دارد: توپولوژی ستاره، سلسله‌مراتبی و متمرکز [2]. در توپولوژی ستاره، هر گره حسگر به‌طور مستقیم به ایستگاه پایه متصل می‌شود. تمام گرههای حسگر، نقش‌ها و کاربردهای یکسان دارند و برای انجام وظایف حسگری و ارتباطی با یکدیگر همکاری می‌کنند. اشکال اصلی این توپولوژی، مصرف انرژی بالای گرهها است؛ زیرا هر کدام از آنها باید وظایفی را انجام دهند که انرژی زیادی مصرف می‌کنند [6]. در پروتکل سلسله‌مراتبی هر گره با گره بالاتر به نام سرخوشه و سپس با ایستگاه پایه در یک درخت ارتباط برقرار می‌کند و داده از پایین‌ترین گره به ایستگاه پایه منتقل می‌شود [14]. با توجه به محدودبودن برد ارتباطی گره، بهتر است گره، ابتدا داده را به همسایه‌اش در درخت انتقال دهد و سپس به ایستگاه پایه بفرستد تا اینکه به‌طور مستقیم به ایستگاه پایه بفرستد. با وجود این، انرژی گرههای بالایی معمولاً سریع‌تر از گرههای پایینی مصرف می‌شود. بنابراین تعداد گرههای مرده افزایش می‌یابد و کارایی سیستم کاهش پیدا می‌کند [15]. در شبکۀ متمرکز[iii]، دو نوع گره وجود دارد: سرخوشه[iv] و غیرسرخوشه[v]. گرههای غیرسرخوشه وظیفۀ حس‌کردن و فرستادن داده به گره سرخوشه را در مواقع لازم بر عهده دارند؛ درحالی‌که گرههای سرخوشه، داده‌ها را از گرههای دیگر دریافت می‌کنند و به ایستگاه پایه می‌فرستند. خوشهبندی به‌صورت مکرر معمولاً برای متعادل‌‌کردن مصرف انرژی گرهها و سرخوشه‌ها انجام می‌شود. این استراتژی مصرف انرژی منابع را از این طریق بهبود می‌بخشد که کل دادۀ انتقال‌‌یافته به ایستگاه پایه به‌طور چشمگیری کاهش پیدا می‌کند. ارتباطات میان‌خوشه‌ای باعث می‌شوند فواصل انتقال داده برای گرههای بعضی از پروتکل‌های معمول این رویکرد عبارت‌اند از: HAC [16]، LEACH-C، BSDCP [17]، AHP [2]، TEEN [18]، APTEEN [19]، DWECH [20]، SCEEP [21]، H-LEACH [22]، K-Means [7]، Fuzzy C Means (FCM) [6]، Distributed load-balancing Unequal Clustering [23]، differential evolution [24]، Unequal Multi-hop Balanced Immune Clustering Protocol (UMBIC) [25]، the Bollinger Bands [26] و Improved Harmony Search Based Energy-Efficient Routing [27].
2-1- الگوریتم فازی C میانگین روش فازی C میانگین، یکی از پروتکل‌های بهینه‌سازی است که در آن، خوشه‌های یکسان در شبکۀ حسگر بی‌سیمی تشکیل می‌شوند که به‌طور تصادفی چیده شدهاند. خوشه‌ها، گروههایی با چگالی زیاد از گرههای حسگرند که درنتیجۀ فاصلۀ بین گرههای غیر سرخوشه با سر‌خوشه‌شان به‌طور چشمگیری کاهش پیدا می‌کنند [6]. رابطه (1) تابع هدف و رابطه (2) محدودیت‌های آن را مشخص می‌کند. در اینجا درجۀ عضویت، است که نشاندهندۀ درجۀ عضویت گره حسگر به خوشه jام است و مرکز خوشه jام است.
مرکزهای خوشه‌ها v و ماتریس عضویت u با حل معادله (1) به دست می‌آیند. الگوریتم تکرار فازی C میانگین به‌طور مکرر اجرا می‌شود تا زمانی که شرایط توقف ارضا شوند. توپولوژی شامل گرههای سرخوشه و غیر سرخوشه با بااین‌حال در تابع هدف این الگوریتم (1)، مصرف انرژی شبکۀ حسگر بی‌سیم در نظر گرفته نشده که نتیجۀ آن تشکیل خوشه‌های نا‌مناسب است. نبود شرایط ارتباطی در محدودیت‌ها (2) مدل ارتباط مستقیم[vi] را تضمین نمی‌کند و در کل این الگوریتم برای محیط دوبعدی طراحی شده است.
2-2- الگوریتم پایه )FCM-3WSN) الگوریتم FCM-3WSN ارتقایافتۀ روش فازی C میانگین است که در آن، مصرف انرژی و محدودیت‌های ارتباطی، در محاسبۀ مرکز خوشه و ماتریس عضویت دخیل‌اند [13]؛ بنابراین، نتایج بهتری نسبت به روش فازی C میانگین و سایر روش‌های خوشهبندی به همراه دارد. این روش یکی از نخستین تلاش‌ها برای خوشهبندی شبکۀ حسگر بی‌سیم سه‌بعدی است. مطالعه روی خوشهبندی شبکۀ حسگر بی‌سیم سه‌بعدی تقریباً جدید است و روش‌های بسیار کمی در این زمینه ارائه شدهاند [28, 29]؛ بنابراین، طراحی یک الگوریتم خوشهبندی بهینه برای شبکۀ حسگر بی‌سیم سه‌بعدی، قدم مهم برای تکامل و تطبیق تکنیک‌های موجود با کاربردهای دنیای واقعی محسوب می‌شود. این روش مدل انرژی سه‌بعدی شبکۀ حسگر بی‌سیم را فازی‌سازی می‌کند. تابع هدف فاصله بین گرههای عادی (غیرسرخوشه) تا گرههای سرخوشه و همچنین فاصله بین گره سرخوشه تا ایستگاه پایه را در یک ارتباط مستقیم محاسبه می‌کند. بعلاوه محدودیت‌های ارتباطی در مدل جدید گنجانده شدهاند [13]. این خصوصیات، این روش را از مدل‌ها و الگوریتم‌های مرتبط دیگر متفاوت می‌کند. تابع هدف این الگوریتم با رابطه (3) مشخص می‌شود:
در این رابطه قسمت ، درجۀ عضویت یک گره سرخوشه را (که با مشخص شده است) به ایستگاه پایه (که با مشخص شده است) اندازه‌گیری می‌کند. به سبب اینکه گرههای سرخوشه با توجه به خوشه‌ها، در هر دور خوشهبندی می‌توانند تغییر کنند، نشاندهندۀ درجه‌ای است که یک سرخوشه به ایستگاه پایه تعلق دارد؛ بدین معنا که اگر یک سرخوشه به ایستگاه پایه نزدیک باشد، انرژی آن کمتر از سرخوشه‌هایی است که از ایستگاه پایه دورترند. همچنین بخش در این رابطه، نشاندهندۀ درجۀ عضویت یک گره معمولی (که با مشخص شده است) به سرخوشه‌اش (که با مشخص شده است) است. این اجزا یک توپولوژی خاص از گرههای معمولی، گرههای سرخوشه و ایستگاه پایه را تشکیل می‌دهند که می‌توانند مقدار تابع هدف را تغییر دهند. پارامترهای دیگر مانند مقادیر ثابت شبکه‌اند. محدودیت‌های رابطه (3) به‌صورت رابطه (4) بیان می‌شوند:
در رابطه (4) m یک فازی‌ساز است (معمولاً مقدار آن 2 است)، C تعداد خوشه‌هاست، N تعداد گرههاست، ، jامین مرکز خوشه است . موقعیت مکانی ایستگاه پایه است و برد ارتباطی است. معیار || . || در محیط سه‌بعدی محاسبه می‌شود (با مؤلفه‌های x، y و z). 3- روش پیشنهادی در این بخش، روش پیشنهادی به‌طور مفصل معرفی شده است. در این مقاله سعی شده است با ایجاد تغییراتی در الگوریتم پایه، مصرف انرژی و طول عمر شبکه بهبود یابد و نتایج بهتری کسب شوند. پوشش، ارتباط و طول عمر شبکه، سه پارامتر اساسی در شبکه‌های حسگر بی‌سیم سه‌بعدی‌اند و از مهم‌ترین چالش‌های موجود در این شبکه‌ها محسوب می‌شوند؛ برای نمونه، یک موضوع کلیدی در استقرار شبکه‌های حسگر این است که گرههای مستقرشده در محیط، پوشش کافی روی منطقۀ مدنظر را داشته باشند؛ در عین حال ارتباط شبکه نیز تضمین شود و طول عمر آن افزایش یابد. پوشش بدین معنا است که چه میزان از هر نقطه از منطقۀ مدنظر، با گرههای مستقرشده در آن نظارت می‌شود. این مسئله درحقیقت کیفیت خدمات[vii] نیز در نظر گرفته می‌شود [30]. ارائه‌دهندگان الگوریتم پایه، این چالش مهم (پوشش) را در الگوریتم خود در نظر نگرفته‌اند که درنتیجه، این موضوع سبب کاهش کارایی آن می‌شود. هدف اصلی یک شبکۀ حسگر بی‌سیم، نظارت هرچه کامل‌تر و دقیق‌تر بر محیط مدنظر است. به سبب اینکه گرهها به‌طور تصادفی در محیط پخش می‌شوند، این احتمال به وجود می‌آید که ازنظر موقعیت مکانی، منطقه را به‌طور کامل پوشش ندهند و چگالی گرهها در بخشی از منطقه، زیاد و در بخش دیگر کم باشد؛ درنتیجه، کیفیت نظارت و حسگری محیط کاهش می‌یابد. این موضوع در مناطقی که دسترسی به گرهها در آنها سخت یا خطرناک و استقرار گرهها در آنها مشکل است، چالشبرانگیز می‌شود و شبکه ازنظر پوشش دچار نقص می‌شود و نتیجه و بازدهی مطلوب را نخواهد داشت. پویایی، یکی از عواملی است که بر پوشش در شبکه‌های حسگر بی‌سیم تأثیرگذار است [31-34]. پویایی به توانایی یک گره برای تغییر موقعیت مکانی‌اش بعد از استقرار اولیه گفته می‌شود. همچنین پویایی تأثیر بسزایی در کاهش مصرف انرژی و افزایش طول عمر شبکه دارد [35]. همچنین در صورت افزودن این ویژگی به شبکه، الگوریتم‌های مسیریابی نیز نیازمند تغییرند [36]. فرض کنید شبکۀ حسگر بی‌سیم در محیط مستقر می‌شود و گرهها به‌طور تصادفی پخش می‌شوند، هر دور خوشهبندی انجام می‌شود و گرهها با موقعیت مکانی ثابتی که دارند، سرخوشه‌ای مناسب‌تر را انتخاب می‌کنند و به خوشۀ آن می‌پیوندند. گرهها بعد از دورهای متعدد خوشهبندی و انجام وظایفشان، انرژی خود را رفته‌رفته از دست می‌دهند و به دلیل ثابت‌بودن موقعیت مکانی‌شان، توانایی استفادۀ بهتر از انرژی کاهش‌یافتۀ خود را ندارند و همان روند خوشهبندی تکرار می‌شود؛ تا زمانی که انرژی‌شان به صفر برسد و بمیرند. حال اگر این امکان وجود داشته باشد که هر گره در هر دور خوشهبندی، موقعیت مکانی خود را به اندازۀ یک حد آستانۀ از پیش تعریف شده تغییر دهد و با نزدیک‌تر کردن خود به سرخوشۀ خوشه‌ای دیگر، از انرژی‌اش - که از یک سطح خاص کمتر شده است - استفادۀ بهینه بکند، تأثیر مثبتی بر خوشهبندی خواهد گذاشت و هر بار خوشه‌ها هدفمندتر تشکیل می‌شوند و درنتیجه، مصرف انرژی، کاهش و طول عمر شبکه به‌طور چشمگیری افزایش پیدا خواهد کرد؛ زیرا هرچه گره معمولی به گره سرخوشه خود نزدیک‌تر باشد، انرژی کمتری، مصرف و طول عمرش افزایش پیدا می‌کند. در روش پیشنهادی، قابلیت جابهجاشدن گرهها به الگوریتم پایه اضافه شد و در بخش آزمایش‌ها نشان داده شد این روش عملکرد بهتری نسبت به الگوریتم پایه و الگوریتم‌های خوشهبندی دیگر دارد. ابتدا برای هر گره این قابلیت در نظر گرفته شد که در صورت دارابودن شرایط از پیش تعیین شده، بتواند جابهجا شود. برای این منظور، گرهها باید مجهز به سکوی لوکوموتیو[viii] شوند که این قطعه گرهها را قادر می‌سازد بعد از استقرار اولیه در محیط، موقعیت مکانی خود را تغییر دهند و جابهجا شوند [37]. یک رابطه برای محاسبۀ میزان انرژی مصرفی برای جابهجایی در ]38[ ارائه شده است. با توجه به اینکه شبکۀ حسگر بی‌سیم مدنظر، سه‌بعدی است و در فضای سه‌بعدی پیاده‌سازی می‌شود، امکان جابهجاشدن گرهها در سه جهت محورهای مختصات فرض کنید گره‌ای که می‌خواهد جابهجا شود در نظر گرفته شود که در خوشه قرار دارد و سرخوشه آن باشد و خوشه که سرخوشه آن است، در همسایگی آن قرار داشته باشد و باشد؛ حال با در نظر گرفتن فرضیه‌های بیان‌شده، روش پیشنهادی شرح می‌شود. بعد از استقرار شبکۀ حسگر بی‌سیم سه‌بعدی در زمین مدنظر و پخش‌شدن گرهها، با استفاده از روش خوشهبندی FCM-3 شبکه خوشهبندی می‌شود، خوشه‌ها ایجاد و گرههای سرخوشه انتخاب می‌شوند. سپس گرههایی برای جابهجایی انتخاب می‌شوند که دو شرط زیر را داشته باشند: شرط 1: میزان انرژی باقیمانده گره ، از یک حد آستانه از پیش تعیین شده کمتر باشد. شرط 2: در صورت جابهجاشدن گره، فاصلۀ سه‌بعدی آن تا گره سرخوشۀ خوشۀ دیگر، نسبت به سرخوشۀ خودش کمتر شود. به‌عبارت دیگر، اگر با جابهجایی، فاصلۀ سه‌بعدی‌اش تا کمتر از فاصلۀ سه‌بعدیش تا شود، شرط لازم برای جابهجایی گره محقق می‌شود. الگوریتم کلی روش پیشنهادی در شکل (1) مشاهده می‌شود. در این شکل، جزئیات روش بررسی امکان جابهجایی و محاسبۀ میزان آن در ادامه ارائه شدهاند. تعاریف مربوط به روش پیشنهادی و همچنین هریک از پارامترهای حد آستانۀ انرژی و حد آستانۀ جابهجایی در ادامه ارائه شدهاند.
3-1- حد آستانۀ انرژی تعیین پارامترهای مناسب به‌منزلۀ حد آستانه‌های استفاده‌شده در دو شرط جابهجایی، چالشی است که در این بخش بررسی شده است. انتخاب اینکه انرژی باقیماندۀ گره‌ای که می‌خواهد جابهجا شود، از چه حدی کمتر باشد تا شرط اول جابهجایی دربارۀ آن برقرار شود، یکی از مسائلی است که مستلزم بررسی‌های فراوان و تحلیل مناسب است. کمینۀ انرژی باقیماندۀ گرهها، پارامتری است که از آن به‌عنوان حدی استفاده می‌شود که در شرط اول جابهجایی، انرژی باقیماندۀ گرهها با آن مقایسه می‌شود. این پارامتر به‌تنهایی برای این انتخاب مناسب نیست؛ زیرا در صورت انتخاب آن، گره‌ای پیدا نمی‌شود که انرژی باقیماندۀ آن از کمینۀ انرژی باقیماندۀ گرههای کل شبکه کمتر باشد و درنتیجه، هیچ گره‌ای از شرط اول عبور نخواهد کرد و جابهجا نخواهد شد.
شکل (1): الگوریتم روش پیشنهادی
ازاین‌رو سعی شد ضریبی برای این پارامتر در نظر گرفته شود و در عین حال باید به این نکته توجه داشت که ضریب انتخاب‌شده یک مصالحه برقرار کند تا تعداد گرههای انتخاب‌شده در شرط اول جابهجایی، نه آنقدر زیاد باشند که در صورت انتقال به خوشۀ جدید، تعادل خوشه‌ها بر هم خورد و نه آنقدر کم باشند که تأثیری بر طول عمر شبکه نداشته باشند. برای این منظور، از روش تجربی استفاده شد و با آزمون و خطا، ضرایب زیادی انتخاب شدند، سپس با توجه به نتایج به‌دست‌آمده از انتخاب آنها، تعدادی حذف شدند. پس از بررسی‌های فراوان، پنج عدد برای شرکت در گزینش برای انتخاب ضریب مناسب حد آستانۀ استفاده‌شده در شرط اول جابهجایی انتخاب شدند. در بخش آزمایشات با توجه به ترکیب آن با پارامترهای دیگر، ضریب مناسب، انتخاب خواهد شد. در الگوریتم شکل (1)، بخش کلیدی آن، بررسی امکان جابهجایی و جابهجایی گرههایی است که شرایط را دارند. با توجه به اینکه مرتبۀ زمانی انجام این اعمال است، مرتبۀ زمانی الگوریتم افزایش نمی‌یابد و فقط ضریبی از N به زمان در هر دور افزوده می‌شود.
3-2- حد آستانه جابهجایی حد آستانه جابهجایی گره، حداکثر میزان مسافتی است که هر گره طی می‌کند. در این بخش مناسب‌ترین معیاری انتخاب شد که می‌توان به‌عنوان این پارامتر برگزید. برای این معیار، ضریبی از میانگین مختصات گرههای شبکه روی هر محور در نظر گرفته شد که می‌تواند انتخاب مناسب و منطقی برای حداکثر میزان جابهجایی گره باشد. پس از بررسی‌های انجامشده روی این پارامتر، مشخص شد اگر ضریبی به همراه آن وجود داشته باشد، عملکرد الگوریتم بهتر خواهد شد؛ زیرا این معیار به‌تنهایی، بازۀ جابهجایی گره را بسیار محدود می‌کند که در نتیجۀ آن احتمال انتقال گرهها به خوشۀ جدید کاهش می‌یابد؛ ازاین‌رو با آزمون و خطاها، پنج عدد انتخاب شد که از قراردادن آنها به‌عنوان ضریب پارامتر حد آستانۀ جابهجایی، نتایج بهتری به دست آمد. با توجه به ضرورت محدودسازی انرژی مصرفی برای جابهجایی، در نظر گرفتن حد آستانۀ انرژی برای گرههای کاندید به‌منظور جابهجایی، می‌تواند تعداد آنها را کاهش و این محدودسازی را انجام دهد. علاوه بر آن، میزان جابهجایی نیز با توجه به توضیحات بالا محدود شده است تا به این امر کمک کند؛ درنتیجه، طبق رابطه (7) میزان انرژی لازم برای جابهجایی محاسبه شده است که با توجه به این محدودسازی‌ها نسبت به انرژی مصرفی هر خوشه شایان توجه نخواهد بود. در بخش چهارم، با انجام آزمایش‌ها و با توجه به ترکیب‌های مختلف این پارامترها، میزان تأثیر آنها در عملکرد شبکه ارزیابی می‌شود.
3-3- مدل مصرف انرژی مدل در نظر گرفته شده برای فاصلۀ زیاد انتقال اطلاعات (ارتباطات برون‌خوشه‌ای) از مدل چندگامی و برای ارتباطات نزدیک (درون‌خوشه‌ای) از مدل کانال انتقال هوای باز استفاده می‌کند. اگر تعداد N گره و C خوشه باشد، به‌طور متوسط تعداد گره در هر خوشه وجود دارد. انرژی مصرف شده یک گره سرخوشه برای دریافت، تجمیع و انتقال اطلاعات به ایستگاه پایه به‌صورت زیر محاسبه می‌شود [13]:
در اینجا تعداد بیت‌های موجود در هر بسته داده، انرژی مصرفشده برای تجمیع داده، فاصله سه‌بعدی از گره سرخوشه تا ایستگاه پایه، انرژی مصرفشده برای راه‌اندازی زیرسیستم‌های رادیویی گره که شامل بخش رادیو الکترونیکی و تقویت‌کننده توان است و در هنگام دریافت اطلاعات نیز برای راه‌اندازی زیرسیستم‌های رادیویی استفاده می‌شود. و به ترتیب برای ارزیابی انرژی مصرفی در انتقال چند گامی و انتقال فضای آزاد هستند. انرژی مصرفشده برای عملکرد یک گره معمولی با رابطه (6) قابل محاسبه است:
که فاصله سه‌بعدی گره معمولی تا سرخوشه است. انرژی مصرفی برای به حرکت درآوردن گره است که از طریق رابطه (7) محاسبه می‌شود:
رابطه (7) با این فرض محاسبه شده است که تصویر میزان جابهجایی سه بعدی گره برای انتقال از نقطه A به B بر روی سه محور x و y و z به ترتیب باشد که در اینجا پارامتر هزینه جابهجایی بر روی سطح برای گره است که یک مقدار ثابت از پیش تعیین شده است و فاصله اولری بین موقعیت ابتدایی گره (A) تا موقعیت نهایی آن بعد از جابهجایی (B) است. مقدار m وزن گره و g شتاب گرانش زمین است. بنابراین انرژی مصرفی شبکه در هر دور برابر است با:
که انرژی مصرفشده در هر خوشه است
که با جای‌گذاری فرمول‌های (5) و (6) در فرمول (9) داریم:
درنتیجه، انرژی مصرفشده هر خوشه با رابطه (10) محاسبه می‌شود [13]. حال تابع انرژی مصرفشده کل شبکۀ حسگر بی‌سیم را داریم. هدف از خوشهبندی، برقراری یک توپولوژی مناسب از گرهها است تا مصرف انرژی کل شبکه را کاهش دهد.
3-4- معیار فاصله معیار فاصله در طراحی پروتکل‌های مسیریابی برای شبکۀ حسگر بی‌سیم نقش مهمی دارد. فاصله در پروتکل‌های مسیریابی مبتنی بر خوشهبندی، به‌عنوان فاصله بین گرهها یا فاصله بین یک گره تا ایستگاه پایه تعریف می‌شود. اگر مختصات دو گره مبدأ و مقصد را در فضای سه‌بعدی به‌ترتیب به‌صورت و نشان داده شود، فاصلۀ اولری بین این گرهها با رابطه (11) محاسبه می‌شود [39]:
4- آزمایش‌ها در این بخش، نتایج شبیهسازی حاصل از دو پارامتر چالشبرانگیز این مقاله، تحلیل و مقایسۀ نتایج آن با دیگر الگوریتم‌های خوشهبندی ارائه شدهاند. برای شبیهسازی از نرم‌افزار متلب استفاده شده است. منطقۀ آزمایش‌شده، یک زمین سه‌بعدی است و شبکۀ حسگر بی‌سیم سه‌بعدی در آن مستقر می‌شود که شامل مدل شبکه یکنواخت در نظر گرفته شد؛ به این معنی که همۀ گرهها دارای انرژی اولیۀ یکسان‌اند که مقدار آن 5 ژول در نظر گرفته شد. هر گره حسگر وظیفۀ اندازه‌گیری پارامترهای محیطی و فرستادن دورهای پیام به گره گیرنده را دارد. گره گیرنده سرخوشه یا ایستگاه پایه است. گره سرخوشه در صورت گرفتن داده از دیگر گرهها، وظیفۀ تجمیع پیام و فرستادن آن به ایستگاه پایه را بر عهده دارد. درخور ذکر است این شبکه، ناهمگن در نظر گرفته شد؛ زیرا گرهها امکان جابهجایی بین خوشه‌ها را دارند [40]. کانال رادیویی برای انتقال داده چندجهته است و محدودۀ انتقال آن، در نظر گرفته شده است. همچنین، انرژی مصرفشده برای انتقال داده از گره X به گره Y با انرژی مصرفشده برای انتقال داده در جهت مخالف آن برابر است. آزمایش‌های انجامشده در این مقاله در محیط واقعی از کشور ویتنام انجام شدهاند که شامل زمین‌های سه‌بعدی از تا با مرفولوژی‌های متفاوت‌اند. اندازۀ این زمین‌ها 250×200 است. به‌منظور انجام مقایسه‌ها و شبیهسازی شرایط مرجع ]13[ ابعاد محیط و توزیع سنسورها و شرایط آنها در آزمایش‌های این بخش مشابه در نظر گرفته شدهاند. در این آزمایش‌ها فرض بر این است که سنسورها می‌توانند به‌صورت محدود در بازۀ محاسبه‌شده در آزمایش‌ها جابهجا شوند. جدول 1 بر مبنای پیش‌فرض‌های آزمایش‌های مرجع فوق تنظیم شده است. گرهها در شبکۀ حسگر بی‌سیم در هر زمین (T1,…,T10) مستقر می‌شوند. اگر انرژی گره‌ای در شبکه تمام شود، آن گره مرده محسوب می‌شود. با توجه به اینکه هدف این پژوهش، تمرکز بر توپولوژی است، اندازه‌گیری‌های دورهای و بار محاسباتی آن در محاسبات کل در نظر گرفته نشد. مدل انتشار، شرایط باتری و نرخ ارسال و دریافت با مقادیر پیش‌فرض تنظیم شدهاند. جدول 1 نشاندهندۀ پیش‌فرض‌های سناریو و مقادیر پارامترهای گرهها است. این شرایط برای تمام آزمایشات یکسان در نظر گرفته شدهاند. جدول (1): پارامترهای شبیهسازی
4-1- نتایج شبیهسازی در این بخش اهداف زیر دنبال شدند: 1) در مجموعۀ آزمایش‌های اول، با انجام آزمایش‌های زیر بهترین ترکیب از ضرایب دو پارامتر حد آستانۀ انرژی و حد آستانۀ جابهجایی انتخاب شدند.
2) در آزمایش‌های دوم، ترکیب انتخاب‌شده در مرحلۀ قبل در الگوریتم، جای‌گذاری و آزمایش‌های زیر انجام شدند:
4-1-1- مجموعه آزمایش‌های اول: انتخاب ترکیب مناسب از دو پارامتر حد آستانۀ انرژی و حد آستانۀ جابهجایی با توجه به مطالب گفته‌شده در بخش قبل، حد آستانۀ انرژی و حد آستانۀ جابهجایی گرهها، دو پارامتر چالشبرانگیز در این مقاله‌اند که به دو شرط تعیین‌شده برای حرکت گرهها مربوط‌اند. شرط اول برای جابهجاشدن گرهها، کمتربودن انرژی باقیماندۀ آنها از حد آستانه از پیش تعیین شده است. حد آستانه‌ای در نظر گرفته شده در این پژوهش، ضریبی از کمینۀ انرژی گرهها است؛ حال آنکه مقدار این ضریب برای گرفتن بهترین نتیجه، چالشی بود که با آن مواجه بودیم. برای این منظور با روش تجربی و با سعی و خطا و مشاهدۀ نتایج به‌دست‌آمده از هریک، 5 عدد انتخاب شدند. ضریب در نظر گرفته شده برای حد آستانۀ انرژی، CoefE نامیده شد که پنج مقدار 1.9 و 2 و 2.1 و 2.2 و 2.3 برای آن برگزیده شدند. سپس به چالش بعدی پرداخته شد و آن انتخاب حد آستانۀ مناسب برای حداکثر میزان جابهجایی گره بود. ضریبی از میانگین مختصات گرههای شبکه در هر محور به‌منزلۀ حد آستانۀ میزان جابهجایی گره انتخاب شد و برای تعیین ضریب مناسب برای این معیار، آزمایش‌هایی انجام شدند. سپس پنج عدد انتخاب شدند که برای انتخاب به‌عنوان ضریب میانگین جابهجایی گرهها مناسب‌تر بودند. این ضریب CoefD نامیده شد که مقادیر انتخابی برای آن 2 و 2.1و 2.2 و 2.3 و 2.4 هستند. هدف ما به دست آوردن بهترین ترکیب از این دو پارامتر است. با داشتن 5 مقدار از CoefE و 5 مقدار از CoefD، 25 حالت به وجود می‌آید که در مجموعۀ آزمایش‌های اول به انتخاب بهترین ترکیب از میان این 25 حالت پرداخته شد. جدول (2) این 25 حالت مختلف را نمایش می‌دهد. آزمایش‌ها برای هریک از وضعیت‌های ذکرشده 5 بار تکرار شدند که شکل‌ها و مقایسه‌های ارائه‌شده میانگین این 5 بار اجرا هستند. همچنین تعداد دور در نظر گرفته شده برای اجرای الگوریتم 3000 دور است.
جدول (2): حالت‌های مختلف از ترکیب دو پارامتر CoefD و CoefE
4-1-1-1- مقایسۀ ترکیب‌های مختلف از ضرایب حد آستانۀ انرژی و جابهجایی ازنظر روند مصرف انرژی کلی شبکه و تعداد دور خوشهبندی شکل‌های (2) تا (6) مصرف انرژی کلی شبکه را در 25 حالت مختلف با یکدیگر مقایسه می‌کند. هر شکل نشاندهندۀ 5 ترکیب از دو پارامتر حد آستانۀ انرژی و حد آستانۀ جابهجایی است.
شکل (2): روند مصرف انرژی کلی 5 ترکیب اول با توجه به شکل (2)، خط قرمزرنگ نشاندهندۀ ترکیب دو پارامتر CoefE و CoefD با مقادیر 1.9 و 2.2 است که بدترین عملکرد را نسبت به 4 ترکیب دیگر در این شکل دارد. در این حالت انرژی شبکه در دور 1534 به پایان می‌رسد. در ترکیب پنجم، ضریب حد آستانۀ انرژی، 1.9 و ضریب حد آستانۀ جابهجایی، 2.4 است و با رنگ زرد نشان داده شده است. این ترکیب نسبت به سایرین بهتر عمل کرده است و انرژی شبکه با این ترکیب در دور 1839 تمام می‌شود. پنج ترکیب دوم در شکل (3) نشان داده شده است که انرژی شبکه با ترکیب دو پارامتر ضریب حد آستانۀ انرژی و جابهجایی دارای مقادیر 2 و 2، در دور 1395 تمام می‌شود که در بین پنج ترکیب دوم کارایی ضعیف‌تری داشته است. شبکه با ترکیب هشتم (مشخص‌شده با خط قرمز) طول عمر بیشتری را تجربه می‌کند و انرژی آخرین گره آن در دور 1615 تمام می‌شود. سه ترکیب دیگر عملکرد مشابه با یکدیگر داشته‌اند.
شکل (3): روند مصرف انرژی کلی 5 ترکیب دوم
شکل (4): روند مصرف انرژی کلی 5 ترکیب سوم با مشاهدۀ شکل (4) مشخص شد اگر برای ضریب حد آستانۀ انرژی مقدار 2.1 و برای ضریب حد آستانۀ جابهجایی مقدار 2 تعیین شود، زمان مرگ آخرین گره شبکه در دور 2022 خواهد بود که این زمان بسیار خوبی برای تمامشدن انرژی کل شبکه محسوب می‌شود. همچنین از این شکل مشهود است که ترکیب سیزدهم نسبت به سایرین ضعیف‌تر عمل کرده است؛ بدین‌گونه که در این حالت، دور 1234 زمان تمامشدن انرژی شبکه است.
شکل (5): روند مصرف انرژی کلی 5 ترکیب چهارم
در پنج ترکیب چهارم در شکل (5)، در دو پارامتر ضریب حد آستانۀ انرژی و جابهجایی مشاهده می‌شود ترکیب شانزدهم، مصرف انرژی سریع‌تری نسبت به چهار ترکیب دیگر دارد و انرژی شبکه در این حالت در دور 1362 به اتمام می‌رسد. خط آبی‌رنگ نشاندهندۀ ترکیب هفدهم است و مقدار ضریب حد آستانۀ انرژی در آن 2.2 و ضریب حد آستانۀ جابهجایی 2.1است و بهترین طول عمر شبکه را در میان این پنج ترکیب داراست. آخرین گره شبکه، ترکیب نوزدهم و بیستم، به‌ترتیب در دور 1720 و 1703 می‌میرد که عملکرد نزدیک به یکدیگر دارند.
شکل (6): روند مصرف انرژی کلی 5 ترکیب پنجم
با توجه به شکل (6)، دو خط مشکی و آبی نشاندهندۀ ترکیب‌های بیست‌و‌یکم و بیست‌ودوم از دو پارامتر ضریب حد آستانۀ انرژی و جابه‌جایی‌اند که روند مصرف انرژی مشابه یکدیگر دارند. ترکیب بیست‌و‌پنجم که در آن و است، روند مصرف انرژی تندتری از بقیه دارد و در دور 1442 کل انرژی شبکه مصرف می‌شود. خط سبز رنگ نمایانگر ترکیب بیست‌و‌چهارم است که در بین این پنج ترکیب عملکرد بهتری دارد. به‌طور کلی در شکل‌های (2) تا (6)، تأثیر هریک از 25 ترکیب دو پارامتر CoefE و CoefD بر مصرف انرژی شبکه و طول عمر آن، نشان داده و با یکدیگر مقایسه شدهاند. با توجه به شکل (5)، ترکیبی که در آن مقدار و است، بهترین عملکرد را نسبت به سایر ترکیب‌ها دارد. انرژی کل شبکه با این ترکیب که با خط مشکی نمایش داده شده است، در دور 2022 به پایان می‌رسد که در این حالت، شبکه بیشترین طول عمر را نسبت به ترکیب‌های دیگر دارد و می‌توان این ترکیب - که یازدهمین ترکیب از ضرایب دو پارامتر حد آستانۀ انرژی و حد آستانۀ جابهجایی است - را بهترین ترکیب انتخاب کرد که در آن مصرف انرژی شبکه به کمترین حالت خود می‌رسد و طول عمر شبکه افزایش پیدا می‌کند. همچنین در شکل مذکور، خط قرمز رنگ نمایانگر سیزدهمین ترکیب است و مقادیر در نظر گرفته شده در آن برای CoefE برابر با 2.1 و برای CoefD برابر با 2.2 است. این ترکیب نسبت به سایرین ضعیف عمل می‌کند و انرژی شبکه در این حالت در دور 1234 به اتمام می‌رسد.
4-1-1-2- مقایسۀ ترکیب‌های مختلف از ضرایب حد آستانۀ انرژی و جابهجایی ازنظر تعداد گره جا‌به‌جاشده در شکل (7) تعداد کل گرههای جا‌به‌جاشده در هریک از 25 ترکیب دو پارامتر حد آستانۀ انرژی و حد آستانۀ جابهجایی نشان داده شده است. تعداد گرههای جا‌به‌جاشده در ترکیب یازدهم - که ترکیب منتخب ما است - 272 گره است. در ترکیب هشتم که در آن ضرایب در نظر گرفته شده برای حد آستانۀ انرژی، 2 و برای حد آستانۀ جابهجایی، 2.2 است، تعداد گرههای جا‌به‌جاشده 650 گره است که بیشترین میزان جابهجایی را نسبت به سایر ترکیب‌ها دارد. در ترکیب ششم با ضریب انرژی 2 و ضریب جابهجایی 2، 561 گره نقل مکان کرده‌اند که بعد از ترکیب هشتم، بیشترین گره جا‌به‌جاشده را دارد. ترکیب چهارم که در آن و است، با 201 گره جا‌به‌جاشده، کمترین تعداد جابهجایی را به خود اختصاص داده است.
شکل (7): تعداد گرههای جابهجا شده در 25 ترکیب
4-1-2- مجموعه آزمایش‌های دوم: مقایسۀ روش پیشنهادی با دیگر الگوریتم‌ها در مجموعۀ آزمایش‌های اول، ترکیب مناسب از ضرایب حد آستانه انرژی و حد آستانه جابهجایی انتخاب شد. با انجام آزمایش‌های گوناگون، ترکیبی انتخاب شد که بهترین عملکرد را ازنظر مصرف انرژی بهینه و طول عمر شبکه و زمان مرگ گرهها، نسبت به سایر ترکیب‌ها دارا بود. در این ترکیب، ضریب حد آستانۀ انرژی 2.1 و ضریب حد آستانۀ جابهجایی 2 است و در الگوریتم اعمال شد. حال الگوریتم پیشنهادی، تکمیل و ارائه می‌شود. در این بخش، الگوریتم ارائه‌شده با الگوریتم خوشهبندی فازی سه‌بعدی که الگوریتم پایه در نظر گرفته شد و چند الگوریتم دیگر، ازنظر مصرف انرژی، طول عمر شبکه، زمان مرگ گرهها، پوشش و عملکرد آنها در شرایط و نواحی مختلف مقایسه شد.
4-1-2-1- مقایسۀ روش پیشنهادی با الگوریتم پایه ازنظر مصرف انرژی در شکل (8)، نتایج حاصل از پیاده‌سازی الگوریتم پیشنهادی و الگوریتم پایه نشان داده و با یکدیگر مقایسه شدهاند. همان‌طور که مشاهده می‌کنید الگوریتم ارائه‌شده موفق به بهبود روش پایه شده و عملکرد بهتری نسبت به آن داشته است. ایجاد امکان جابهجایی گرهها و انتخاب حد آستانه‌های مناسب برای شروط جابهجایی، به بهبود در الگوریتم پایه، چه ازنظر دورۀ ثبات (زمان مرگ اولین گره) و چه ازنظر طول عمر شبکه منجر شد. با توجه به
شکل (8): روند مصرف انرژی روش پیشنهادی و روش پایه
4-1-2-2- مقایسۀ روش پیشنهادی با الگوریتم پایه ازنظر زمان مرگ گرهها یکی از آزمایش‌های متداول انجامشده در خیلی از بحث‌های پژوهشی در شبکه‌های حسگر بی‌سیم، مقایسۀ روش پیشنهادی با روش‌های پیشین ازنظر زمان مرگ گرههاست. در این مقاله نیز تلاش شد از این مقایسه استفاده شود. در این بخش، زمان مرگ اولین گره براساس تعداد دور (FND[ix])، زمان مرگ نیمی از گرهها (HND[x]) و زمان مرگ آخرین گره شبکه (LND[xi]) در هر الگوریتم، محاسبه و با یکدیگر مقایسه شدهاند. انجام این آزمایش از این نظر حائز اهمیت است که با توجه به تعریف در نظر گرفته شده برای طول عمر شبکه، می‌توان عملکرد روش پیشنهادی را ازنظر طول عمر شبکه با روش پایه مقایسه کرد. با توجه به نتایج در شکل (9)، الگوریتم پیشنهادی به دورۀ ثبات بیشتری نسبت به الگوریتم پایه دست یافته است؛ به این صورت که زمان مرگ اولین گره در الگوریتم پایه در دور 63 بوده و این زمان در الگوریتم ارائه‌شده به دور 144 رسیده است. همچنین مرگ آخرین گره در الگوریتم پیشنهادی در دور 2022 اتفاق افتاده است؛ درحالی‌که آخرین گره شبکه در الگوریتم پایه در دور 150 مرده است. تعریف ما از طول عمر شبکه در این مقاله، مدت زمانی است که نیمی از گرههای شبکه زنده‌اند و از شکل (10) پیداست طول عمر شبکه در الگوریتم پایه در دور 85 به پایان رسیده است؛ درحالی‌که در الگوریتم پیشنهادی، نیمی از گرههای شبکه تا دور 810 زنده بوده‌اند. بدیهی است پیاده‌سازی الگوریتم پیشنهادی، بهبود مصرف انرژی و طول عمر شبکه را به دنبال داشته و موفق شده است با افزایش دورۀ ثبات از الگوریتم پایه پیشی گیرد.
شکل 9- زمان مرگ گرهها در روش پیشنهادی و روش پایه
4-1-2-3- مقایسۀ روش پیشنهادی با الگوریتم پایه ازنظر پوشش شبکه در این بخش، پوشش شبکه در روش پیشنهادی و روش پایه بررسی شدهاند. نرخ پوشش شبکه برای دو الگوریتم در شکل (10) نشان داده شده است که یک معیار برای کارایی شبکه محسوب می‌شود. نرخ پوشش به معنای میزان درصد از ناحیۀ آزمایش‌شده است که با گرهها پوشش داده شده است. با محاسبۀ نرخ پوشش دریافته می‌شود چه میزان از منطقۀ آزمایش‌شده با گرهها حمایت قرار شده است. در این حالت، اگر یک نقطه P در منطقۀ آزمایش‌شده، در محدودۀ برد حسگری گره n قرار داشته باشد، فرض می‌شود P با n پوشش داده شده است. ناحیۀ حسگری n یک دایره با مرکزیت n و با شعاع به اندازۀ برد حسگری r است. تابع پوشش از گره n و نقطه P به‌صورت رابطه (12) است که در آن فاصلۀ اقلیدوسی در فضای 3 بعدی بین گره n و نقطه P است:
شکل (10): مقایسۀ روش پیشنهادی با الگوریتم پایه ازنظر پوشش شبکه
با توجه به شکل (10)، پوشش اولیۀ شبکه بعد از استقرار اولیۀ گرهها در محیط، 53% است که در روش پایه این مقدار تا دور 70 ثبات خود را حفظ و از دور 70 به بعد شروع به کاهش می‌کند و سرانجام در دور 150 به صفر می‌رسد. این درحالی است که در روش پیشنهادی، میزان پوشش شبکه، ابتدا از 53% به 67% افزایش پیدا می‌کند و سپس تا دور 193، شبکه پوشش خود را با این مقدار حفظ می‌کند و ثابت می‌ماند و بعد از آن، میزان پوشش کاهش می‌یابد که این سیر نزولی تا آخرین دور شبکه ادامه پیدا می‌کند و به صفر می‌رسد. از نتایج به‌دست‌آمده مشهود است روش پیشنهادی موفق به بهبود میزان پوشش شبکه شده و توانسته است پوشش ابتدایی شبکه را از 53% به 67% ارتقا دهد و این مقدار را تا دور 193 حفظ کند. همچنین پوشش شبکه در روش پایه در دور 150 به صفر می‌رسد؛ درحالی‌که در روش پیشنهادی پوشش شبکه تا دور 2022 ادامه پیدا کرده است.
4-1-3- مقایسۀ روش پیشنهادی با برخی دیگر از الگوریتم‌ها در این بخش، الگوریتم پیشنهادی با الگوریتم‌هایی همچون LEACH، LEACH-C، SCEEP، H-LEACH، K-Means و FCM مقایسه شده است. شرایط انجام آزمایش‌ها و مجموعه دادۀ استفاده‌شده برای پیاده‌سازی این الگوریتم‌ها، کاملاً یکسان و مشابه با شرایط پیاده‌سازی الگوریتم ارائه‌شده در نظر گرفته شدهاند. آزمایش‌ها در این بخش ازنظر مصرف انرژی، زمان مرگ گرهها، عملکرد الگوریتم‌ها در نواحی مختلف، با تعداد گرههای مختلف و تعداد خوشه‌های مختلف، انجام و نتایج با یکدیگر مقایسه خواهند شد.
4-1-3-1- مقایسۀ روش پیشنهادی با الگوریتم‌های دیگر ازنظر مصرف انرژی ابتدا روش پیشنهادی با الگوریتم‌های مذکور ازنظر مصرف انرژی مقایسه می‌شود.
شکل (11): روند مصرف انرژی روش پیشنهادی و روش‌های دیگر با توجه به نتایج به‌دست‌آمده از شکل (11)، الگوریتم پیشنهادی با اختلاف زیادی نسبت به دیگر روشها عملکرد بهتری از خود نشان داده است. الگوریتم FCM با خط آبی نمایش داده شده و بعد از روش پیشنهادی، بهتر از سایرین عمل کرده است؛ بدین صورت که انرژی آخرین گره شبکه در این الگوریتم در دور 130 به اتمام رسیده است. این در حالی است که انرژی کل شبکه در روش LEACH-C در دور 25 تمام شده است که نتیجه گرفته می‌شود این روش ضعیف‌ترین عملکرد را در بین روش‌های آزمایش‌شده داشته است. الگوریتم‌های LEACH و SCEEP عملکرد مشابهی داشته‌اند و روند مصرف انرژی آنها بسیار نزدیک به یکدیگر بوده است. دو روشH-LEACH و K-Means در سومین رتبه ازنظر مصرف انرژی قرار دارند و انرژی کل شبکه در این دو الگوریتم نیز در زمان‌های نزدیک به یکدیگر به اتمام رسیده است.
4-1-3-2- مقایسۀ روش پیشنهادی با روش‌های دیگر ازنظر زمان مرگ گرهها در بخش‌های قبل مطرح شد که یکی از آزمایش‌های مهم در ارزیابی الگوریتم‌های شبکه‌های حسگر بی‌سیم، مقایسه ازنظر زمان مرگ گرهها است. در شکل (12) دورۀ ثبات هر الگوریتم، زمان مرگ نیمی از گرهها و زمان مردن آخرین گره شبکه در هر الگوریتم، نشان داده و با یکدیگر مقایسه شدهاند.
شکل (12): زمان مرگ گرهها در روش پیشنهادی و روش‌های دیگر
از شکل (12) بدیهی است الگوریتم پیشنهادی در مقایسه با دیگر الگوریتم‌ها با اختلاف زیاد دارای عملکرد بهتری بوده و ازنظر طول عمر شبکه و زمان مرگ گرهها از دیگر الگوریتم‌ها پیشی گرفته است. روش LEACH-C که در آن زمان مرگ آخرین گره شبکه در دور 15 بوده، بدترین عملکرد را در این میان داشته است. عملکرد الگوریتم FCM نسبت به دیگر الگوریتم‌ها به الگوریتم ارائه‌شده نزدیک‌تر بوده و روند مصرف انرژی بهتری داشته است. دورۀ ثبات این الگوریتم تا دور 52 بوده و مرگ نیمی از گرهها در دور 89 اتفاق افتاده است. دورۀ ثبات دو روش H-LEACH و K-Means به‌ترتیب 14 و 12 بود که نشان می‌دهد عملکرد این دو روش در شبکه بسیار نزدیک به یکدیگر است. همین‌طور دو الگوریتم LEACH و SCEEP با زمان مرگ آخرین گره در دورهای 25 و 26 روند مصرف انرژی مشابهی داشته‌اند. 5- نتیجه‌گیری در حال حاضر بیشتر پژوهش‌ها در زمینه شبکۀ حسگر بی‌سیم فرض می‌کنند گرهها در یک فضای دوبعدی چیده می‌شوند. این تقریب خوبی است برای کاربردهایی که در آنها گرهها روی سطح زمین پخش می‌شوند و ارتفاع شبکه از برد رادیویی گره کمتر است. در این شبکه‌ها ارتفاع شبکه در مقایسه با طول و پهنای آن ناچیز است. شبکه‌های دوبعدی در کاربردهای زیرآب، کوهستان، جنگل‌ها، اتمسفر و فضا کارایی پایینی دارند که در آنها ارتفاع شبکه زیاد است و گرهها در یک فضای سه‌بعدی پخش می‌شوند؛ برای مثال، در شبکه‌های حسگر زیر آب، گرهها ممکن است در اعماق متفاوتی از اقیانوس قرار گیرند و درنتیجه، شبکۀ سه‌بعدی می‌شود. همچنین پیش‌بینی و نظارت بر آب‌وهوا با استقرار شبکۀ سه‌بعدی در اتمسفر بهتر انجام می‌شود. استقرار گرهها در مناطق کوهستانی و جنگلی نیز شرایط مشابهی دارند. هدف ما در اینجا خوشهبندی در شبکه‌های حسگر بی‌سیم سه‌بعدی است. در این مقاله تلاش شده است با ترکیب پارامترهای مختلف و اضافه‌کردن قابلیت‌هایی به شبکه، خوشهبندی، بهینه شود. الگوریتم خوشهبندی FCM-3 الگوریتم پایه انتخاب شده است. این الگوریتم نسخۀ تعمیم‌یافتۀ الگوریتم FCM است که برای شبکه‌های حسگر بی‌سیم سه‌بعدی طراحی شده است و عملکرد بهتری نسبت به روش FCM دارد. در روش پیشنهادی، سعی شد با ایجاد تغییراتی در این الگوریتم، عملکرد آن، بهبود و مصرف انرژی کاهش یابد. برای این منظور، قابلیت جابهجایی برای گرهها در نظر گرفته شد؛ بدین‌صورت که اگر انرژی باقیماندۀ گره‌ای از حد مشخصی کمتر باشد و با جابهجایی به خوشۀ دیگر، فاصله‌اش تا سرخوشۀ خوشه جدید کمتر از فاصله‌اش تا سرخوشۀ فعلی شود، شرایط لازم برای جابهجایی را دارد و به خوشۀ جدید نقل مکان خواهد کرد. بدین ترتیب انرژی مصرفشده شبکه کاهش می‌یابد و درنتیجه، طول عمر شبکه افزایش پیدا خواهد کرد. در بخش آزمایش‌ها روش پیشنهادی با الگوریتم FCM-3 و FCM و چند روش خوشهبندی دیگر مقایسه شد. نتایج این آزمایش‌ها نشان دادند روش پیشنهادی عملکرد بهتری نسبت به الگوریتم FCM-3 و دیگر الگوریتم‌ها دارد و مصرف انرژی را تا حد زیادی کاهش می‌دهد. [1] تاریخ ارسال مقاله: 24/04/1398 تاریخ پذیرش مقاله: 07/11/1398 نام نویسندۀ مسئول: مهدی سالخورده حقیقی نشانی نویسندۀ مسئول: ایران - مشهد - دانشگاه صنعتی سجاد - دانشکده مهندسی کامپیوتر و فناوری اطلاعات | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مراجع | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
[1] D. T. Hai, N. T. Tam, L. H. Son, and L. T. Vinh, "A novel energy-balanced unequal fuzzy clustering algorithm for 3D wireless sensor networks," in Proceedings of the seventh symposium on information and communication technology, pp. 180-186 , 2016. [2] J. Yick, B. Mukherjee, and D. Ghosal, "Wireless sensor network survey," Computer networks, Vol. 52, pp. 2292-2330, 2008. [3] S. Alam and Z. J. Haas, "Topology control and network lifetime in three-dimensional wireless sensor networks," arXiv preprint cs/0609047, 2006. [4] S. Roy and N. Mukherjee, "Topology construction of 3D wireless sensor network," in Advances in Computing and Information Technology, ed: Springer, pp. 533-542, 2012. [5] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," IEEE Transactions on wireless communications, vol. 1, pp. 660-670, 2002. [6] D. Hoang, R. Kumar, and S. Panda, "Fuzzy C-means clustering protocol for wireless sensor networks," in Industrial Electronics (ISIE), 2010 IEEE International Symposium on, pp. 3477-3482, 2010. [7] L. Tan, Y. Gong, and G. Chen, "A balanced parallel clustering protocol for wireless sensor networks using K-means techniques," in Sensor Technologies and Applications, 2008. SENSORCOMM'08. Second International Conference on, pp. 300-305, 2008. [8] N. T. Tam, H. D. Thanh, and V. T. Le, "Optimization for the sensor placement problem in 3D environments," in Networking, Sensing and Control (ICNSC), 2015 IEEE 12th International Conference on, pp. 327-333, 2015. [9] R. Logambigai, K. Thanigaivelu, and K. Murugan, "Extending network lifetime using optimal transmission range in wireless sensor networks," in International Conference on Wireless Communications, Networking and Mobile Computing, 2012. [10] S. Misra, N. E. Majd, and H. Huang, "Approximation algorithms for constrained relay node placement in energy harvesting wireless sensor networks," IEEE Transactions on Computers, Vol. 63, pp. 2933-2947, 2014. [11] G. A. Montoya and Y. Donoso, "Energy load balancing strategy to extend lifetime in wireless sensor networks," Procedia Computer Science, Vol. 17, pp. 395-402, 2013. [12] M. Baghouri, Abderrahmane Hajraoui, Saad Chakkor, "Low energy adaptive clustering hierarchy for three-dimensional wireless sensor network", Recent Advances in Communications, 2014 [13] D. T. Hai and T. Le Vinh, "Novel fuzzy clustering scheme for 3D wireless sensor networks," Applied Soft Computing, Vol. 54, pp. 141-149, 2017. [14] J. N. Al-Karaki and A. E. Kamal, "Routing techniques in wireless sensor networks: a survey," IEEE wireless communications, Vol. 11, pp. 6-28, 2004. [15] J. Zhu, C.-H. Lung, and V. Srivastava, "A hybrid clustering technique using quantitative and qualitative data for wireless sensor networks," Ad Hoc Networks, Vol. 25, pp. 38-53, 2015. [16] C.-H. Lung and C. Zhou, "Using hierarchical agglomerative clustering in wireless sensor networks: An energy-efficient and flexible approach," Ad Hoc Networks, Vol. 8, pp. 328-344, 2010. [17] S. D. Muruganathan, D. C. Ma, R. I. Bhasin, and A. O. Fapojuwo, "A centralized energy-efficient routing protocol for wireless sensor networks," IEEE Communications Magazine, Vol. 43, pp. S8-13, 2005. [18] A. Manjeshwar and D. P. Agrawal, "TEEN: a routing protocol for enhanced efficiency in wireless sensor networks," in null, p. 30189a, 2001. [19] A. Manjeshwar and D. P. Agrawal, "APTEEN: A hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks," in ipdps, p. 0195b, 2002. [20] P. Ding, J. Holliday, and A. Celik, "Distributed energy-efficient hierarchical clustering for wireless sensor networks," in International conference on distributed computing in sensor systems, pp. 322-339, 2005. [21] S. Kandukuri, N. Murad, and R. Lorion, "A single-hop clustering and energy efficient protocol for wireless sensor networks," in Radio and Antenna Days of the Indian Ocean (RADIO), pp. 1-2, 2015. [22] A. Razaque, S. Mudigulam, K. Gavini, F. Amsaad, M. Abdulgader, and G. S. Krishna, "H-LEACH: Hybrid-low energy adaptive clustering hierarchy for wireless sensor networks," in Systems, Applications and Technology Conference (LISAT), 2016 IEEE Long Island, pp. 1-4, 2016. [23] B. Baranidharan and B. Santhi, "DUCF: Distributed load balancing Unequal Clustering in wireless sensor networks using Fuzzy approach," Applied Soft Computing, Vol. 40, pp. 495-506, 2016. [24] P. Kuila and P. K. Jana, "A novel differential evolution based clustering algorithm for wireless sensor networks," Applied soft computing, Vol. 25, pp. 414-425, 2014. [25] N. Sabor, M. Abo-Zahhad, S. Sasaki, and S. M. Ahmed, "An unequal multi-hop balanced immune clustering protocol for wireless sensor networks," Applied Soft Computing, Vol. 43, pp. 372-389, 2016. [26] A. Thakkar and K. Kotecha, "A new Bollinger Band based energy efficient routing for clustered wireless sensor network," Applied Soft Computing, Vol. 32, pp. 144-153, 2015. [27] B. Zeng and Y. Dong, "An improved harmony search based energy-efficient routing algorithm for wireless sensor networks," Applied Soft Computing, Vol. 41, pp. 135-147, 2016. [28] P. Abakumov and A. Koucheryavy, "Clustering algorithm for 3D wireless mobile sensor network," in Conference on Smart Spaces, pp. 343-351, 2015. [29] M. V. Babu and A. Ramprasad, "Modified fuzzy c means and ensemble based framework for min cost localization and power constraints in three-dimensional ocean sensor networks," Indian Journal of Science and Technology, Vol. 9, 2016. [30] S. M. Mohamed, H. S. Hamza, and I. A. Saroit, "Coverage in mobile wireless sensor networks (M-WSN): A survey," Computer Communications, Vol. 110, pp. 133-150, 2017. [31] N. Bartolini, T. Calamoneri, E. G. Fusco, A. Massini, and S. Silvestri, "Autonomous deployment of self-organizing mobile sensors for a complete coverage," in International Workshop on Self-Organizing Systems, pp. 194-205, 2008. [32] G. Wang, G. Cao, T. La Porta, and W. Zhang, "Sensor relocation in mobile sensor networks," in INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, pp. 2302-2312, 2005. [33] N. Bartolini, T. Calamoneri, T. La Porta, and S. Silvestri, "Mobile sensor deployment in unknown fields," in INFOCOM, 2010 Proceedings IEEE, pp. 1-5, 2010. [34] X. Li and N. Santoro, "ZONER: a ZONE-based sensor relocation protocol for mobile sensor networks," in Local Computer Networks, Proceedings 2006 31st IEEE Conference on, pp. 923-930, 2006. [35] K. Romer and F. Mattern, "The design space of wireless sensor networks," IEEE wireless communications, vol. 11, pp. 54-61, 2004. [36] Mostafa Mirzaie, Sayyed Majid Mazinani and Armin Mazinani, " A new energy-efficient fuzzy cluster-based routing algorithm with a Constant threshold in wireless sensor network", Journal of Soft Computing and Information Technology (JSCIT), Vol 7, No 1, pp. 87-103, 2018 [37] Y.-C. Tseng, Y.-C. Wang, K.-Y. Cheng, and Y.-Y. Hsieh, "iMouse: an integrated mobile surveillance and wireless sensor system," Computer, Vol. 40, 2007. [38] J. Guo and H. Jafarkhani, "Movement-efficient sensor deployment in wireless sensor networks," in 2018 IEEE International Conference on Communications, ICC, pp. 1-6, 2018. [39] V. K. Chaurasiya, N. Jain, and G. C. Nandi, "A novel distance estimation approach for 3D localization in wireless sensor network using multi dimensional scaling," Information Fusion, Vol. 15, pp. 5-18, 2014. [40] Mehdi Honarmand, Ali Ghiasian and Hossein Saidi, "Design of an energy aware clustering scheme based on genetic algorithm in heterogeneous wireless sensor networks", Journal of Computational Intelligence in Electrical Engineering, Vol 6, No 3, pp. 16-36, 2016. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
آمار تعداد مشاهده مقاله: 528 تعداد دریافت فایل اصل مقاله: 228 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||