Document Type : Research Article
Authors
Abstract
Keywords
پبشرفتهای روز افزون در ساخت مدارات مجتمع و همچنین، توسعه ارتباطات بیسیم باعث توسعه ریز حسگرهایی شده است که بدنه اصلی یک شبکه حسگر بیسیم را ایجاد میکنند. به عبارت دیگر یک شبکه حسگر متشکل از گرههایی است که به شکل متراکم در محیط پخش شده و با همکاری یکدیگر یک وظیفه[1] مشترک را انجام میدهند.
امروزه شبکههای حسگر بیسیم در حوزههای مختلف نظامی، بهداشت و درمان، نظارت بر زیستگاه، نظارت بر فرآیندهای صنعتی و . . . کاربرد ویژهای دارند [1 و 2]. ترکیب محدودیتها و نحوه استقرار گرهها دراین قبیل از شبکهها، ضرورت طراحیهای انرژی آگاه در تمام لایههای شبکه را برای این حوزه دو چندان می‌کند. برای نمونه، در لایه شبکه باید زمان طراحی الگوریتم‌های مسیریابی به شاخص محدودیت انرژی مصرفی توجه شود تا الگوریتم ارائه شده افزایش طول عمر شبکه و کاهش انرژی را به دنبال داشته باشد [1]. بنابراین، چالشهای فراوان در شبکههای حسگر مانند: منابع ذخیرهسازی، قابلیتهای محاسباتی، پهنای باند ارتباطات و از همه مهمتر منابع انرژی، در دهه اخیر پژوهشهای گستردهای را در این حوزه پدید آورده است [، 3 و 4].
یکی از روشهای مناسب به منظور افزایش طول عمر شبکههای حسگر بیسیم استفاده از مسیریابی سلسله مراتبی[2] است. در این نوع مسیریابی، گرهها در گروههای مجزا به نام خوشه[3] قرار میگیرند و برای هر خوشه نیز یک سرخوشه[4] انتخاب میشود. گرههای عضو دادههایشان را به سمت سرخوشه ارسال میکنند، سرخوشهها با دریافت و انجام تجمیع بروی دادهها، آنها را به شکل تک گامی یا چندگامی به سمت ایستگاه پایه که به آن چاهک[5] گفته میشود ارسال میکنند. خوشهبندی گرههای حسگر میتواند به عنوان یک عامل مؤثر در کاهش انرژی مصرفی و به دنبال آن افزایش طول عمر شبکه حسگر و همچنین، افزایش قابلیت گسترشپذیری[6] مطرح شود [5].
در الگوریتم‌های خوشهبندی، گره سرخوشه بار اضافی زیادی را به علت برخی از فعالیتها، نظیر تجمیع داده، ارسال داده به سمت چاهک و. . . متحمل میشود. بنابراین، گرههای سرخوشه نسبت به سایر گرهها در معرض مرگ زودرس به علت انرژی مصرفی بالا هستند.
بنابراین، انتخاب سرخوشه مناسب یکی از چالشهای اصلی در خوشهبندی شبکه حسگر به شمار میآید و در واقع این شاخص یکی از عوامل مهم در افزایش داده دریافتی در چاهک و کاهش طول عمر شبکه است. خوشهبندی شبکه حسگر با هدف کمینه کردن میزان انرژی مصرفی یک مسأله NP-Hard است که یکی از چالشهای موجود در حوزه خوشهبندی شبکه حسگر، انتخاب و نحوه چیدمان سرخوشهها میباشد [6].
در سالهای اخیر پروتکلهای خوشهبندی متعددی به منظور افزایش طول عمر شبکه جسگر مطرح شدهاند. LEACH یکی از الگوریتم‌های خوشهبندی است که از روش ساخت خوشه به شکل توزیع شده بهره میگیرد. در الگوریتم LEACH انتخاب سرخوشه براساس یک مدل احتمالاتی انجام میشود. سایر گرهها نیز براساس کمترین فاصله به انتخاب سرخوشه اقدام میکنند. به هرحال الگوریتم LEACH توزیع یکنواخت سرخوشهها در محیط را تضمین نمیکند. همچنین، در برخی از مراحل به علت استفاده از مدل احتمالاتی برای انتخاب سرخوشه، ممکن است گرهای به عنوان سرخوشه انتخاب شود که شایستگی سرخوشه شدن را دارا نیست.
از جمله روشهای رایج دیگر برای خوشهبندی شبکههای حسگر، استفاده از الگوریتم‌های K-Means و Fuzzy C-Means است [7]. در نوع ساده از این الگوریتمها، ابتدا به تعداد خوشههای مورد نیاز، نقاطی به شکل تصادفی انتخاب میشوند. سپس، گرهها با توجه به کمترین فاصله تا مرکز خوشه، یکی از مراکز خوشهها را انتخاب کرده و به آن خوشه ملحق میشوند و خوشههای جدید را ایجاد میکنند. با تکرار همین روال و با میانگین گرفتن از فاصله گرهها تا مرکز خوشه فعلی، مراکز جدید برای خوشهها بدست خواهد آمد.
این روند تا زمانی که تغییری در مکان مراکز خوشه حاصل نشود ادامه پیدا می‌کند. الگوریتم ارائه شده در [8] بر اساس الگوریتم K-Means عملیات خوشهبندی شبکه حسگر را انجام میدهد. پس از خوشهبندی، به منظور انتخاب سرخوشه مناسب، نزدیکترین گره به مراکز حاصل از اجرای الگوریتم K-Means در مرحله قبل که بیشترین انرژی را داراست به عنوان سرخوشه انتخاب میشود. عدم توجه این الگوریتم به تعداد مناسب سرخوشهها و همچنین، عدم توجه به شاخصهای دیگری مانند فاصله تا چاهک، ترافیک ارسالی، درجه همسایگی، فاصله محلی[7] و. . . . در زمان انتخاب سرخوشه باعث ایجاد خوشههایی غیربهینه میشود که باعث کاهش طول عمر شبکه حسگر میشود. روشهای خوشهبندی که تاکنون مطرح شد ازجمله روشهای خوشهبندی کلاسیک به شمار میآیند.
روش های خوشهبندی کلاسیک نسبت به نقاط شروع به شدت حساس هستند و بیشتر به علت انتخاب غیر صحیح این نقاط، الگوریتم مورد نظر به سمت نقاط بهینه محلی همگرا شده و از نقاط بهینه سراسری دور میشود [9]. واضح است که خوشهبندی شبکه حسگر با هدف کمینه کردن میزان انرژی مصرفی یک مساله NP-Hard است [10]. از آنجا که الگوریتم های فرا ابتکاری[8]رویکرد مؤثری برای حل مسائل بهینه سازی پیچیده در علوم مختلف هستند، استفاده از این الگوریتمها برای حل مسائل خوشهبندی مفید است.
این مقاله، به ارائه یک روش خوشهبندی انرژی آگاه مبتنی بر الگوریتم ژنتیک (EAGCA) در شبکههای حسگر بیسیم ناهمگن پرداخته است که هدف آن افزایش طول عمر شبکه و افزایش داده دریافتی در چاهک با تاکید بر انتخاب سرخوشه مناسب است. بخش اول تابع برازش این الگوریتم به دنبال کمینه کردن مجموع انرژی مصرفی درون و برون خوشهای ناشی از ارتباطات است. بخش دوم تابع برازش کوشش می‌کند با درنظر گرفتن شاخصهای انرژی باقیمانده، تراکم گرههای همسایه، فاصله محلی و ترافیک ارسالی گره، سرخوشه مناسب را برای هر خوشه انتخاب کند.
به منظور ارزیابی، الگوریتم پیشنهادی با دو الگوریتم LEACH وEAERP مقایسه خواهد شد وتحلیل و بررسی نتایج بروی یک سناریو از پیش تعریف شده انجام خواهد گرفت. تحلیل نتایج حاصل، نشان از برتری الگوریتم EAGCA در انرژی مصرفی، میزان داده دریافتی در چاهک و طول عمر شبکه حسگر نسبت به سایر الگوریتمها دارد.
همچنین، پس از ارائه الگوریتم EAGCA، الگوریتم مطرح با عنوان الگوریتم EAGCA* بهبود بخشیده خواهد شد. EAGCA* با معرفی نوع جدید از گرهها به نام گرههای مستقل، سعی در بهبود طول عمر شبکه و داده دریافتی در چاهک نسبت به الگوریتم EAGCA دارد. نتایج حاصل، نشان از عملکرد بهتر الگوریتم EAGCA* نسبت به الگوریتم EAGCA و سایر الگوریتمها مورد مقایسه دارد.
در بخش دوم این مقاله، مروری بر کارهای پیشین درحوزه خوشهبندی خواهد شد. در بخش سوم و چهارم، به ترتیب مدل انرژی و مدل شبکه بیان شده است. در بخش پنجم، مروری بر الگوریتم ژنتیک خواهیم داشت. بخش ششم به توضیح کامل الگوریتم EAGCA میپردازد. بخش هفتم به بهبود الگوریتم پیشنهادی و ارائه یک الگوریتم پیشنهادی جدید با عنوان EAGCA* میپردازد. در بخش هفتم به منظور ارزیابی، الگوریتم‌های پیشنهادی با الگوریتم‌های LEACH و EAERP مقایسه میشوند. در بخش هشتم نتایج تحلیل و برخی پیشنهادات برای کارهای بعدی ارائه خواهد شد.
الگوریتم LEACH [11] یکی از الگوریتم‌های اولیه در حوزه خوشهبندی شبکههای حسگر بیسیم است که به شکل توزیع شده[9] به خوشهبندی شبکه حسگر میپردازد. هر گره در ابتدا یک عدد تصادفی بین صفر تا یک را تولید می‌کند. سپس، بر اساس مقدار حاصل از (1) میزان احتمال سرخوشه شدن در مرحله جاری را مشخص می‌کند. در صورتی که عدد تصادفی از مقدار احتمال T(s) کمتر باشد، گره حسگر به عنوان سرخوشه در مرحله جاری انتخاب خواهد شد. که T(s) از رابطه زیر محاسبه میشود.
|
(1) |
در این رابطه، P عبارت است از درصد مطلوب تعداد سرخوشه، r مرحله جاری و G مجموعه گرههایی است که در مرحله قبل سرخوشه نبودهاند. به منظور توزیع نقش سرخوشه بین تمام گرهها، در ابتدای هر مرحله انتخاب سرخوشه جدید با استفاده از رابطه (1) انجام میگیرد. از جمله معایب الگوریتم LEACH عدم توزیع مناسب سرخوشهها در محیط شبکه و انتخاب غیر بهینه گرهها به عنوان سرخوشه است.
در [12] یک روش خوشهبندی مبتنی بر الگوریتم ژنتیک ارائه شده است. دراین الگوریتم از کروموزمهای دودویی[10] به منظور تعیین نقش هر گره استفاده می شود. تابع هدف این الگوریتم در (2) بیان شده است.
|
(2) |
در معادله (2) مقدار TD برابر با مجموع فواصل تمام گرههای حسگر تا چاهک، D برابر با جمع فواصل گرههای عادی تا سرخوشه و جمع فواصل بین سرخوشهها تا چاهک است. TN برابر با تعداد کل گرههای حسگر، برابر با تعداد سرخوشهها و یک مقدار از پیش تعریف شده است که اشاره به میزان اهمیت هر جزو در تابع هدف دارد. مقادیر کمینه D و باعث افزایش مقدار به دست آمده از تابع هدف میشود. الگوریتم ژنتیک در زمان تشکیل خوشه به دنبال یافتن راه حلی است که مقدار تابع هدف را بیشینه کند. در تابع برازش الگوریتم مفروض، به شاخصهایی نظیر میزان انرژی باقیمانده، میزان فاصله محلی و مجموع انرژی گرههای همسایه در زمان تشکیل خوشهها اشارهای نشده است. عدم توجه به انتخاب سرخوشه مناسب موجب کاهش طول عمر شبکه و کاهش دادههای دریافتی توسط چاهک خواهد شد.
در [13] یک روش خوشهبندی مبتنی بر الگوریتم ژنتیک ارائه شده است که هدف آن بهبود طول عمر شبکه از طریق کاهش انرژی مصرفی است. در این الگوریتم هر کروموزم، پیکربندی شبکه در مرحله جاری را نشان میدهد. در (3) تابع برازندگی الگوریتم مورد نظر بیان شده است.
|
(3) |
در این رابطه، ND مجموع فواصل گرههای عضو خوشه تا گره سرخوشه و تعداد سرخوشههاست. هدف انتخاب راهحلی(کروموزم جواب) است که مقدار تابع برازندگی برای کروموزم انتخابی کمینه باشد.
در [14- 17]، نویسندگان با در نظر گرفتن شاخصهایی دیگری نظیر، انحراف معیار در فواصل درون خوشه (SD)، تخمین انرژی ارسالی (E) و تعداد مراحل ارسال داده (T)، به دنبال بهبود تابع برازندگی ارائه شده در [12] هستند. استفاده از این مجموعه از شاخصها در تعریف تابع برازندگی مفروض این اطمینان را خواهد داد که پیکربندی شبکه حاصل از بهترین کروموزم، در میزان داده ارسالی بیشینه و در میزان انرژی مصرفی کمینه خواهد بود. در نتیجه، الگوریتم HCR با تابع برازندگی بیان شده در (4) نسبت به تابع برازندگی الگوریتم ارائه شده در [12] در میزان داده ارسالی برتری دارد [18].
|
(4) |
در این رابطه، مقدار TD برابر با مجموع فواصل تمام گرههای حسگر تا چاهک، D برابر با جمع فواصل گرههای عضو خوشه تا سرخوشه و جمع فواصل بین سرخوشهها تا چاهک است. برای مثال، مقدار برای یک خوشه با k گره عضو در (5) محاسبه شده است. همچنین، هر fi قسمتی از تابع هدف را تشکیل میدهد. بنابراین، مجموع مقادیر fi حاصل از هر قسمت، کل تابع هدف الگوریتم HCR را تشکیل میدهد.
|
(5) |
که به فاصله گره i تا سرخوشه c و به فاصله سرخوشه c تا چاهک اشاره دارد. مقدار E اشاره به مجموع انرژی مصرفی برای دریافت و ارسال دادههای تجمیع شده از خوشهها به چاهک دارد.
اگرچه مقادیر اولیه ها در تابع برازش (4) به شکل دلخواه تعیین میشود ولی در حین مراحل بعدی این مقدار بر اساس ارزش بهترین کروموزم به روز رسانی میشود.
در [19]، یک روش خوشهبندی مبتنی بر الگوریتم ژنتیک ارائه شده است که هدف آن بهبود تابع برازش بیان شده برای الگوریتم [14- 17] است. تابع برازش (6) علاوه بر پنج شاخص بیان شده برای تابع برازش (4)، دو شاخص انرژی باقیمانده (RE) و تعداد بسته دریافتی(FT) را نیز در زمان محاسبه مقدار تابع برازش برای هر کروموزم در نظر گرفته است. fi برابر با مقدار حاصل از تابع برازش برای بخش های مختلف است که مجموع fi ها، مقدار کل تابع برازش را تشکیل میدهد.
|
(6) |
در [18] یک الگوریتم خوشهبندی پویا، تکگامی، انرژی آگاه و مبتنی بر الگوریتم تکاملی(EAERP) ارائه شده است که هدف آن کاهش انرژی اتلافی، و افزایش طول عمر شبکه است.
|
(7) |
در رابطه (7)، تعداد سرخوشهها و تمام اعضای خوشه i ام است. برابر با انرژی مصرفی برای دریافت داده، برابر با انرژی مصرفی برای تجمیع داده توسط سرخوشه و انرژی مصرفی برای ارسال داده از گره عضو به سرخوشه i ام است.
تابع برازش (7)، کوشش می‌کند تا با ایجاد توازن در فواصل درون و برون خوشهای به خوشههای مناسبی از نظر انرژی مصرفی دست پیدا کند. به طوری که مجموع فواصل درون خوشهای (از گره عضو خوشه تا سرخوشه) کمینه و از طرفی مکان قرارگیری سرخوشه نیز تا حد امکان نزدیک به چاهک در نظر گرفته شود.
پس از تعیین سرخوشهها، هر گره غیرسرخوشه به نزدیکترین سرخوشه (به منظور کاهش انرژی مصرفی در ارتباطات درون خوشهای) ملحق میشود. الگوی انتخاب سرخوشه در EAERP شبیه به الگوریتم LEACH است. بنابراین، معایب انتخاب سرخوشه در الگوریتم LEACH نظیر عدم توجه به انرژی گره سرخوشه و عدم پراکندگی مناسب سرخوشهها در شبکه برای EAERP نیز وجود دارد.
در [19] یک الگوریتم خوشهبندی تکگامی و مبتنی بر الگوریتم تکاملی (ERP) ارایه شده است. هدف تابع برازندگی الگوریتم ERP کمینه کردن تعداد سرخوشهها و مجموع فواصل درون و برون خوشهای است. کمینه کردن مجموع فواصل در الگوریتم EAR شامل سه بخش کمینه سازی فواصل درون خوشهای (چسبندگی خوشهای[11]) و پراکندگی مناسب سرخوشهها در محیط (انفصال خوشهای[12]) است. بخش اول تابع برازندگی الگوریتم ERP، در (8) اشاره شده است، که وظیفه این بخش کمینه کردن مجموع فواصل درون خوشهای است و به چسبندگی خوشهای اشاره می‌کند. مقدارn به تعداد گرههای عضو سرخوشه i ام یا () اشاره دارد. نیز به فاصله بین گره n ام تا اشاره دارد.
|
(8) |
بخش دوم تابع برازندگی در (9) اشاره شده است، که وظیفه توزیع مناسب سرخوشهها در سطح شبکه را بر عهده دارد.
|
(9) |
در رابطه (9) فاصله بین دو سرخوشه مجزا در شبکه حسگر است. مقدار برابر با نسبت چسبندگی درون خوشهای به انفصال برون خوشهای است که در (10) اشاره شده است. هر چه مقدار کمتر باشد، نشان از توزیع مناسب سرخوشهها نسبت به یکدیگر(انفصال خوشهای) و کمینه بودن فواصل درون خوشه ای (اتصال خوشهای) دارد. بنابراین، هر چه مقدار برای یک راه حل(کروموزم جواب) کمینهتر باشد آن راه حل مناسبتر است.
|
(10) |
بخش سوم تابع برازندگی در (11) اشاره شده است، که هدف این بخش تعیین تعداد مناسب سرخوشههاست.
|
(11) |
تابع برازندگی الگوریتم ERP در (12) به طور کامل بیان شده است. مقادیر w و (1-w) میزان تاکید بروی هر بخش از تابع برازندگی را مشخص می‌کند.
|
(12) |
الگوریتم جستجوی هارمونی[13] [20] از جمله الگوریتم‌های فرا اکتشافی است که به تازگی در حوزه خوشهبندی شبکه حسگر استفاده شده است. در [21] یک روش خوشهبندی مبتنی بر الگوریتم جستجوی هارمونی با هدف کمینه کردن مجموع فواصل درون خوشهای و بهینه کردن مصرف انرژی ارائه شده است که هدف آن افزایش طول عمر شبکه حسگر خواهد بود. تابع برازش این روش خوشهبندی در رابطه (13) بیان شده است.
|
(13) |
اشاره به بیشترین فاصله اقلیدسی بین گرهها دارد که نحوه محاسبه آن در (14) بیان شده است.
|
(14) |
اشاره به سرخوشه k ام، اشاره به فاصله بین گره i ام و سرخوشه k ام و اشاره به تعداد اعضای خوشه دارد. f2 برابر با نسبت انرژی تمام گرههای زنده به انرژی تمام سرخوشههای مرحله جاری است که در (15) بیان شده است.
|
(15) |
مجموع انرژی تمام سرخوشههای انتخاب شده و مجموع انرژی تمام گرههای حسگر است. مقدار کمینه ، نشان از کمینه بودن مجموع فواصل درون خوشهای دارد. همچنین، مقدار کمینه در انتخاب گرههایی با انرژی باقیمانده بیشتر به عنوان سرخوشه تاثیرگذار است. بنابراین هدف کمینه کردن مقدار تابع برازش بیان شده در (13) است. مقادیر w و (1-w) نشاندهنده میزان تأکید بروی هر بخش از تابع برازندگی است که میتواند مقادیر مختلفی را به خود اختصاص دهد. از جمله معایب الگوریتم HSA، عدم توجه به شاخصهایی نظیر بار ارسالی گره در زمان انتخاب سرخوشه است. همچنین، در تابع برازش HSA کمینه کردن فواصل سرخوشه تا چاهک به عنوان یک شاخص تاثیرگذار در مصرف انرژی گرهها، در نظر گرفته نشده است که ممکن است به مرگ زودرس گرههای سرخوشه منجر شود.
امروزه یکی از روشهای مطرح برای حل دستهای از مسائل بهینهسازی، استفاده از روشهای موسوم به روشهای بهینهسازی مبتنی بر هوش دسته جمعی است.
الگوریتم‌های خوشهبندی تکاملی، با بهره گیری از الگوریتم‌های تکاملی نظیر الگوریتم ژنتیک[14]، بهینهسازی ازدحام ذرات[15]، بهینهسازی کلونی مورچگان[16] و . . . تلاش میکنند بهترین جواب ممکن برای ساخت خوشه را پیدا کنند. به طوری که خوشه حاصل دارای کمینه مقدار انرژی مصرفی، بیشینه مقدار داده ارسالی به چاهک و. . . باشد. الگوریتم‌های [13، 17 و 23] از نمونه الگوریتم‌های مطرح در حوزه خوشهبندی شبکه حسگر بیسیم مبتنی بر الگوریتم‌های تکاملی است.
الگوریتم ژنتیک [24] نوع خاصی از الگوریتم‌های تکاملی است که از روشهای زیست‌شناسی مانند وراثت و جهش استفاده می‌کند. در الگوریتم ژنتیک، یک کروموزوم، مجموعه‌ای از شاخصهاست به طوری که یک راه حل پیشنهادی را برای مسأله‌ای که الگوریتم ژنتیک سعی در حل آن دارد، تعریف می‌کند. الگوریتم ژنتیک با تولید یک جمعیت اولیه تصادفی شروع به کار می‌کند. پس از تولید جمعیت اولیه، درصدی از کروموزمها به تصادف به عنوان والد از جمعیت فعلی انتخاب میشوند.
کروموزمهای والد با هم ترکیب شده و با تبادل اطلاعات بین یکدیگر دو کروموزم فرزند را ایجاد میکنند. همچنین، به منظور ایجاد فرزندان بهینهتر از روش جهش نیز میتوان بهره گرفت. پس از این مرحله، نسل جدید با استفاده از تابع برازش ارزیابی میشوند. از جمعیت بهترین فرزندان و جمعیت نسل قدیم، نسل جدید تولید میشود. در
شکل (1) الگوریتم ژنتیک ارایه شده است. در این مقاله، نحوه تولید جمعیت اولیه و عمل پیوند، از الگوریتم ژنتیک استاندارد متفاوت خواهد بود.
شکل (1):فلوچارت الگوریتم ژنتیک
یکی از اصلیترین قسمتهای یک الگوریتم خوشهبندی بهینه، انتخاب سرخوشه مناسب است که به افزایش طول عمر شبکه کمک خواهد کرد. الگوریتم خوشهبندی پیشنهادی (EAGCA) کوشش کرده تا با بهرهگیری از برخی شاخصهای حسگر نظیر انرژی باقیمانده، مجموع انرژی باقیمانده گرههای همسایه با یک گام، فاصله محلی و ترافیک ارسالی به انتخاب سرخوشههای مناسب دست یابد و باعث افزایش طول عمر شبکه حسگر و افزایش داده دریافتی در چاهک شود. تابع برازش الگوریتم خوشهبندی پیشنهای از دو قسمت تشکیل شده است. قسمت اول این تابع برازش، به کمینه کردن میزان انرژی مصرفی برای ارسال داده و قسمت دوم تابع برازش، به انتخاب سرخوشه مناسب میپردازد.
سپس، به معرفی الگوریتم EAGCA* میپردازیم. این الگوریتم کوشش دارد تا با تغییراتی در خوشههای ایجاد شده، عملکرد EAGCA را بهبود بخشد. در ادامه، ویژگیهای الگوریتم ژنتیک نظیر تابع برازش الگورتیم EAGCA، نوع پیوند کروموزمها، جهش و نحوه مدل کردن الگوریتم EAGCA برای حل با الگوریتم ژنتیک بیان خواهد شد.
در الگوریتم پیشنهادی این فصل، هر کروموزم به نوعی نشاندهنده نحوه اتصال گرههای حسگر به سرخوشههاست. طول هر کروموزم برابر با تعداد گرههای حسگر در مرحله جاری است.
برای مثال، اگر مقدار i امین ژن یک کروموزم نوع دوم برابر با j باشد، یعنی گره ni به سرخوشه gj انتساب داده شده است. برای هر گره حسگر یک عدد انحصاری (شروع از یک) به عنوان شماره شناسایی در نظر گرفته میشود. بنابراین، در کروموزم جواب، اندیس هر ژن اشاره به شماره یک گره حسگر دارد. مقدار هر ژن نیز به شماره گره سرخوشه برای گره حسگر اشاره دارد. چون گرههای سرخوشه از گرههای حسگر انتخاب میشوند، برای گره سرخوشه، مقدار ژن که نشاندهنده گره سرخوشه است با اندیس ژن برابر است.
شکل (2) یک شبکه حسگر بیسیم با 10 گره را نشان میدهد. به علت وجود 10 گره در شبکه، کروموزم راه حل نیز10 ژن خواهد داشت. کروموزم راه حل در شکل (2) نشان داده شده است. با توجه به کروموزم جواب، g2 و g5 به عنوان سرخوشه و مابقی گرهها، عضو خوشه هستند. برای مثال، گره n3 به سرخوشه g2 متصل است. نکته قابل بیان اینکه هر کروموزم نشاندهنده یک جواب برای خوشهبندی شبکه حسگر است.
|
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
|
5 |
5 |
2 |
5 |
2 |
5 |
2 |
2 |
2 |
5 |
شکل (2): نمایش کروموزم
جمعیت اولیه مجموعه‌ای از کروموزمهای تولید شده تصادفی است. هر کروموزم یک پیکربندی غیربهینه از شبکه را نشان میدهد که هر ژن از کروموزم با مقدار 1 به معنای سرخوشه و با مقدار صفر به معنای عضو خوشه و 1- به عنوان گره غیرفعال (مرده) پر شده است. بنابراین، بر اساس (16) برای ژن مربوط به گره j ام در کروموزم I داریم:
|
|
(16) |
این جمعیت به عنوان راهحلهای اولیه تصادفی به الگوریتم ژنتیک به منظور شروع کار تحویل داده میشود. از آنجا که جمعیت اولیه اثر بالایی در رسیدن به جوابهای بهتر دارد، در عوض ایجاد جمعیت اولیه به شکل کاملا تصادفی از روش آگاهانهتری برای ایجاد جمیعت اولیه در الگوریتم EAGCA بهره گرفته شده است.
در این روش، ابتدا میانگین انرژی گرهها محاسبه میشود و سپس، به تصادف از گرههایی که انرژی باقیمانده بالاتر از میانگین دارند تعدادی گره به عنوان سرخوشه انتخاب خواهد شد. در کروموزمهای تصادفی حاصل از این روش، گرههایی به عنوان کاندید سرخوشه ( ) انتخاب خواهند شد که انرژی باقیمانده بالاتری از میانگین انرژی کل گرهها دارند و در واقع از انتخاب گرههایی با انرژی پایین به عنوان سرخوشه پرهیز میشود.
بهره گرفتن از این روش سبب میشود تا الگوریتم ژنتیک با سرعت بیشتری به سمت جواب بهنیه سراسری و انتخاب سرخوشه مناسب حرکت کند. نحوه انتخاب گره سرخوشه برای جمعیت اولیه در ادامه بیان شده است. ابتدا هر گره یک عدد تصادفی بین صفر تا 1 را حدس میزند. اگر مقدار عدد تصادفی حدس زده شده کمتر از باشد و گره مورد نظر نیز عضو مجموعه کاندید سرخوشه یعنی باشد ژن مربوط به آن گره در کروموزم جوابهای تصادفی برابر یک قرار میگیرد، در غیر اینصورت، ژن مورد نظر برابر با صفر در نظر گرفته میشود. نحوه محاسبه در (17) بیان شده است.
|
(17) |
مجموعه اشاره به مجموعه گرههایی دارد که میزان انرژی فعلی این گرهها از میانگین انرژی تمام گرههای زنده بیشتر است. اشاره به انرژی فعلی گره i ام و N اشاره به مجموع گرههای زنده در مرحله جاری دارد.
میزان ارزش هر کروموزم نسبت به سایر کروموزمها براساس تابع برازش تخمین زده میشود. در الگوریتم ژنتیک مقدار حاصل از تابع برازش برای هر کروموزم، تاثیر بالایی در ایجاد نسل بعدی از نسل فعلی دارد.
همانگونه که پیش از این نیز بیان شد انرژی مصرفی در یک فرآیند ارسال داده به چاهک برابر با انرژی مصرفی برای ارسال داده از گره عضو خوشه تا گره سرخوشه، انرژی مصرفی برای تجمیع داده توسط سرخوشه و انرژی مصرفی برای ارسال داده توسط سرخوشه است. نحوه محاسبه مقدار انرژی مصرفی یاد شده برای K گره حسگر به شکل ریاضی در (18) آمده است.
|
(18) |
مقدار برابر با مجموع انرژی مصرفی K گره عضو خوشه برای ارسال داده به سمت سرخوشه(c) است. و به ترتیب به مجموع انرژی مصرفی سرخوشه برای دریافت دادههای از K گره عضو و انرژی مصرفی سرخوشه برای تجمیع دادهها اشاره دارد. انرژی مصرفی برای ارسال داده تجمیع شده از سوی سرخوشه(c) به چاهک است. بخش اول تابع برازش الگوریتم EAGCA، مشابه رابطه بالا به دنبال کمینه کردن انرژی مصرفی گرههای عضو خوشه به منظور ارسال داده تا سرخوشه و انرژی مصرفی گرههای سرخوشه به منظور تجمیع و ارسال داده به چاهک است.
یکی از شاخصهای مؤثر در کمینه کردن انرژی یاد شده، فاصله ارسال داده است. تابع برازش یاد شده کوشش می‌کند تا با ایجاد توازن در فواصل درون و برون خوشهای به خوشههای مناسبی دست پیدا کند. این بخش از تابع برازش، خوشههایی ایجاد خواهد کرد که مجموع فواصل درون خوشهای (از گره عضو خوشه تا سرخوشه) کمینه و از طرفی مکان قرارگیری سرخوشه نیز تا حد امکان نزدیک به چاهک در نظر گرفته شود تا میزان انرژی مصرفی برای ارتباطات درون و برون خوشهای کمینه شود [18]. رابطه (19) بخش اول تابع برازش الگوریتم پیشنهادی را بیان می‌کند.
|
|
(19) |
مقادیر شاخص بالا در بخش دوم این مقاله مفصل بیان شده است. در واقع تابع برازش یاد شده به شکل ضمنی، به انتخاب سرخوشههایی اقدام می‌کند که میزان فاصله این سرخوشهها تا چاهک کمینه شود. اگرچه شاخص فاصله تا چاهک یک مقدار مؤثر در انتخاب سرخوشه است، اما شاخصهای دیگر نظیر مقدار انرژی باقیمانده، مقدار ترافیک ارسالی و میزان تراکم گرههای همسایه در انتخاب سرخوشه نیز تاثیرگذارهستند که در تابع برازش یاد شده نه تنها به روشنی به وجود این شاخصها در انتخاب سرخوشه اشارهای نشده، بلکه به شکل ضمنی نیز این شاخصها در تابع برازش استفاده نشده اند که به نوعی ضعف تابع برازش [19] است. بنابراین، نیاز است تا با ارائه یک تابع برازش جدید، شاخصهای یاد شده را به روشنی در انتخاب سرخوشه دخیل و سرخوشههای بهینهای را برای یک خوشه انتخاب کنیم. هر چه مقدار حاصل از بخش دوم تابع برازش، برای یک کروموزم کمتر باشد، سرخوشههای انتخاب شده توسط کروموزم یاد شده بهینهتر هستند. نحوه محاسبه بخش دوم تابع برازش برای کروموزم Ik در (20) بیان شده است.
|
|
(20) |
N اشاره به کل گرههای شبکه، یک متغیر باینری است که مقدار آن در صورتی که گره i ام سرخوشه باشد برابر با یک و در صورتی که گره i ام سرخوشه نباشد برابر با صفر است. هدف جلوگیری از تاثیر شاخص مربوط به گرههای عضو خوشه در رابطه (20) است. هر چه مجموع گرههای کاندید سرخوشه در یک کروموزم کمتر باشد، کروموزم مفروض شامل سرخوشههای بهتری خواهد بود. چگونگی محاسبه در (21) بیان شده است.
|
(21) |
در این رابطه NB مجموعه همسایگان تکگامی در شعاع R گره i ام، R شعاع استاندارد ارسال داده گره حسگر، برابر با انرژی باقیمانده جاری گره i، بیشترین انرژی موجود در مرحله جاری، برابر با بیشترین ترافیک تولید شده در مرحله جاری توسط گرههای زنده و برابر با ترافیک تولیدی گره i ام در مرحله جاری است.
بر اساس (21) هر چه سرخوشههای انتخاب شده در یک کروموزم دارای مقدار انرژی باقیمانده بیشتر، مقدار ترافیک کمتر، مجموع انرژی همسایهها کمتر و فاصله محلی کمتری باشند، شاخص بیشتر و مقدار حاصل از بخش دوم تابع برازش (20) کمتر خواهد شد که نشان از وجود سرخوشههای مناسب تر در کروموزم یاد شده دارد. در (22) تابع برازش الگوریتم EAGCA به طور کامل بیان شده است.
|
(22) |
و میزان اهمیت هر بخش از تابع برازش را مشخص می‌کند. برای آنکه علاوه برخوشهبندی مناسب، انتخاب سرخوشه مناسب نیز در تابع برازش مدنظر قرار بگیرد میتوان وزن را بزرگتر از درنظر گرفت.
فرآیند انتخاب به دنبال یافتن کروموزمهای بهینه از جمعیت فعلی برای مرحله پیوند[17] و ساخت جمعیت جدید است. روشهای متفاوتی نظیر چرخه رولت، الگوریتم تورنمت و الگوریتم رتبهبندی به منظور انتخاب کروموزمها استفاده میشود. در این مقاله، از روش چرخه رولت به منظور انتخاب کروموزمها استفاده شده است. در چرخه رولت احتمال هر کروموزم بر اساس مقدار تابع برازش و براساس (23) محاسبه میشود.
|
(23) |
در این رابطه N برابر با تعداد جمعیت اولیه کروموزمها و برابر با مقدار تابع برازش هر کروموزم است. سپس، جمع تجمعی هر کروموزم از جمعیت براساس (24) محاسبه میشود. با استفاده از توزیع یکنواخت یک عدد تصادفی بین 0 و 1 تولید میشود. اولین کروموزمی که مقدار عدد تصادفی از مقدار تجمعی احتمالات آن کروموزم کمتر باشد، به عنوان کروموزم هدف شناخته میشود.
|
(24) |
عمل ترکیب دو کروموزوم از جمعیت فعلی (والدین[18]) و به دست آوردن دو کروموزوم جدید (فرزندان[19]) را پیوند مینامند. الگوریتم‌های متفاوتی نظیر پیوند یک نقطهای، دو نقطهای و یکنواخت برای عمل پیوند استفاده میشود. نوع پیوند مورد استفاده در این پژوهش، پیوند ترکیبی شامل پیوند یک و دو نقطه ای و یکنواخت است. در پبوند یکنواخت یک رشته ماسک[20] به طول رشته والد از اعداد تصادفی صفر و یک پرمیشود. اگر بیت i ماسک صفر باشد، ژن i رشته جدید برابر با ژنi ام والد اول و در غیراینصورت برابر با بیت i ام رشته دوم خواهد بود. این روش روی تک تک بیتها اعمال میشود.
جهش یکی از پدیدههای علم ژنتیک است که به ندرت در برخی از کروموزومها رخ میدهد و در طی آن فرزندان ویژگیهایی پیدا خواهند کرد که به هیچ یک از والدین متعلق نیست. نقش جهش در الگوریتم ژنتیک بازگرداندن مواد ژنتیکی گم شده و یا پیدا نشده داخل جمعیت است، تا از همگرایی زودرس الگوریتم به جوابهای بهینه محلی جلوگیری شود. در جهش یکسری از ژنها را به طور تصادفی برگزیده صفرها را به یک و یکها را به صفر تبدیل میشود. از آنجا که عمل جهش در طبیعت به ندرت رخ میدهد، در الگوریتم ژنتیک هم با احتمال بسیار کم (کمتر از 0. 05) عمل جهش را انجام میدهیم. جهش مورد استفاده در الگوریتم EAGCA به شکل تصادفی ژن مورد نظر را انتخاب می‌کند و جهش صفر به یک و بالعکس را انجام میدهد.
الگوریتم EAGCA یک الگوریتم خوشهبندی مرکزی است که در آن چاهک با دریافت اطلاعات جانبی نظیر انرژی باقیمانده، ترافیک ارسالی، تعداد گرههای همسایه از گرههای حسگر به انتخاب سرخوشه و ایجاد خوشهها مبادرت میورزد. سپس، نقش هر گره مشخص شده و چاهک از طریق بسته کنترلی به گرههای حسگر اطلاع رسانی می‌کند. مراحل اجرای الگوریتم پیشنهادی در جدول (1) بیان شده است.
جدول (1): مراحل اجرای الگوریتم EAGCA
|
1) هر حسگر مختصات مکانی، ترافیک و انرژی جاری خود را در قالب پیام Hello به سمت چاهک ارسال می‌کند. |
|
2) دریافت پیامهای Hello توسط چاهک و اجرای الگوریتم خوشهبندی(EAGCA) با بهره بردن از الگوریتم ژنتیک |
|
3) پس از خوشهبندی، چاهک نقش هر حسگر را با استفاده از پیام Reply اطلاع رسانی می‌کند. |
|
4)هر سرخوشه با استفاده از پروتکل TDMA یک زمانبند ارسال داده ایجاد کرده و به گرههای عضو اطلاع رسانی می‌کند. |
|
5) پس از تشکیل خوشهها، ارسال داده از سمت گرههای عضو به سرخوشهها و از سرخوشهها به چاهکها شروع میشود. |
|
6) پس از اتمام مرحله ارسال داده، به مرحله 1 برو. |
عملکرد اصلی الگوریتم EAGCA را در دو بخش مختلف با عنوان مراحل 2 و5 میتوان بررسی کرد که عبارتند از:
در مرحله ساخت خوشه، گرههای حسگر اطلاعاتی نظیر انرژی باقیمانده، ترافیک و مختصات مکانی را در قالب یک پیام سلام[21] (Hello Message) به سمت چاهک ارسال میکنند. چاهک پس از دریافت تمام پبامهای Hello ارسالی حسگرها، میانگین انرژی گرههای حسگر را محاسبه می‌کند. گرههایی که میزان انرژی باقیمانده آنها بیشتر از میانگین انرژی باشد کاندیدای مناسبی برای سرخوشه شدن هستند.
الگوریتم ژنتیک با تولید جمعیت تصادفی اولیه شروع به کار می‌کند و پس از اتمام تعداد مراحل اجرای الگوریتم ژنتیک، بهترین کروموزم انتخاب میشود که پیکربندی شبکه حسگر شامل سرخوشهها و اعضای سرخوشه را نشان میدهد. چاهک با استفاده از پیامهای پاسخ[22] (Reply Message)، نقش هر گره و نحوه انتساب گرههای عضو خوشه به سرخوشه را به گرههای حسگر اطلاع رسانی می‌کند. پس از شکلگیری خوشهها، هر گره سرخوشه وظیفه دارد تا با استفاده از پروتکل TDMA[23] یک برنامه زمانبندی برای ارسال داده گرههای عضو خوشه ایجاد کند. Clustering Setup در ابتدای هر مرحله اجرا شده و انتخاب سرخوشه و ساخت خوشههای جدید را انجام میدهد.
پس از آنکه سرخوشهها انتخاب و برنامه زمانبندی ارسال داده گره حسگر توسط سرخوشهها به گرههای حسگر اعلام شد، گرههای حسگر بر اساس برنامه زمانبندی به ارسال داده به سمت سرخوشه شروع می‌کند.
بر اساس پروتکل TDMA گرههای حسگر فقط در زمان ارسال داده قسمت رادیویی را فعال کرده و در زمان دیگر این بخش سختافزاری گره خاموش است. استفاده از پروتکل TDMA علاوه بر کاهش انرژی مصرفی، به کاهش تصادم[24] بستههای داده نیز کمک می‌کند. پس از ارسال داده از سمت گرههای حسگر به سرخوشهها، عملیات تجمیع داده توسط سرخوشه انجام و دادههای تکراری حذف میشود.
در برخی از پیکربندیهای موجود، اگر گره عضو خوشه، داده ارسالی را به شکل مستقل به چاهک ارسال کند انرژی کمتری مصرف خواهد کرد که نتیجه آن افزایش طول عمر شبکه و افزایش داده دریافتی در چاهک خواهد بود. این انرژی مصرفی شامل: انرژی مصرفی برای ارسال داده، انرژی دریافت داده توسط سرخوشه، انرژی تجمیع داده و انرژی ارسال داده توسط سرخوشه خواهد بود.
بر اساس شکل (3)، گرههای A و B به دو شیوه قادر به ارسال داده به چاهک هستند. در شیوه اول، گرههای A و B باید داده را تحویل گرههای سرخوشه خود به ترتیب CH1 و CH2 دهند و گرههای سرخوشه نیز پس از تجمیع، داده را به چاهک ارسال کنند. در شیوه دوم، گرههای A و B به جای ارسال داده به سمت گرههای سرخوشه، داده خود را به شکل مستقیم به سمت چاهک و مستقل از سرخوشهها ارسال میکنند.
در شیوه اول ارسال داده، انرژی مصرفی برابر است با: انرژی ارسال داده از گره A و B به سمت سرخوشههای CH1 و CH2 به فواصل d1 و d2، انرژی دریافتی داده توسط سرخوشهها و انرژی ارسال داده از سرخوشه به چاهک با مسافتی بیشتر از d1 و d2.
در شیوه دوم ارسال داده، انرژی مصرفی برابر است با: انرژی ارسال داده از گره A و B به سمت چاهک به شکل مستقل به فواصل d3 و d4.
همانگونه که روشن است انرژی مصرفی ارسال داده نوع دوم بهینهتر از ارسال داده نوع اول است. در ارسال داده نوع اول، به علت انرژی مصرفی بالا، گرههای حسگر دچار افت انرژی شدید شده و در نتیجه دچار مرگ زودرس خواهد شد که نتیجه آن کاهش داده ارسالی به سمت چاهک، افزایش انرژی اتلافی و افزایش داده گم شده در شبکه است. بنابراین، دو عیب روش ارسال داده نوع اول، مرگ زودرس گرههای سرخوشه و انرژی مصرفی بالاست.
برای بیان الگوریتم EAGCA* نیاز به معرفی نوع سوم از گرههای حسگر به نام گرههای مستقل است. گرهای که به شکل مستقیم به ارسال داده به سمت چاهک اقدام کند گره مستقل نامیده میشود. الگوریتم EAGCA* پس از پایان خوشهبندی و دریافت بهترین کروموزم یا پیکربندی حاصل از اجرای الگوریتم EAGCA، به انتخاب گرههای مستقل و تصحیح خوشههای ایجاد شده میپردازد تا با استفاده از گرههای مستقل، میزان داده دریافتی و طول عمر شبکه حسگر را افزایش و از مرگ زودرس گرههای سرخوشه نیز دوری کند. نتایج شبیهسازی نشان از بهبود الگوریتم EAGCA* نسبت به الگوریتم EAGCA در تمامی شاخصهای شبیهسازی دارد.
شبه کد مربوط به اجرای الگوریتم EAGCA* در جدول (2) آمده است. رابطه (25) به چگونگی تغییر تقش گرههای عضو خوشه به گره مستقل در پیکربندی جدید اشاره می‌کند در حالیکه ممکن است برخی از گرههای عضو خوشه بدون تغییر نقش در پیکربندی جدید حضور داشته باشند.
شکل (3):نمایش گرههای مستقل در EAGCA*
|
(25) |
در رابطه بالا، انرژی مصرفی مورد نیاز براساس شیوه ارسال داده نوع اول است. به انرژی مصرفی موردنیاز برای ارسال داده به شکل مستقیم یا به شیوه ارسال داده نوع دوم اشاره می‌کند. برای هر گره عضو خوشه مانند گره A مقادیر و محاسبه شده سپس، در صورتی که بزرگتر از باشد گره مستقل و در غیر اینصورت گره عضو خوشه باقی خواهد ماند. در جدول (2) مراحل اجرای الگوریتم EAGCA* بیان شده است.
جدول (2): مراحل اجرای الگوریتم EAGCA*
|
1) ابتدا الگوریتم EAGCA اجرا و در پایان، کروموزم پیکربندی حاصل میشود. |
|
2) به ازای هر گره غیرسرخوشه در کروموزم نهایی مقدار E1 و E2 محاسبه میشود. نوع گره براساس مقادیر حاصل و بر اساس رابطه بیان شده مشخص می شود. |
|
3) کروموزم اصلاح شده به عنوان پیکربندی بهینه به دست آمده در مراحل ساخت خوشه برای الگوریتم EAGCA* استفاده خواهد شد. |
در این بخش، الگوریتم‌های پیشنهادی در مقایسه با یک الگوریتم خوشهبندی کلاسیک و یک الگوریتم خوشهبندی مبتنی بر هوش تکاملی ارزیابی خواهد شد.
الگوریتم‌های پیشنهادی با الگوریتم‌های LEACH [11] و EAERP[19] مقایسه شده است. هر دو الگوریتم فرض شده در بخش دوم این مقاله به شکل کامل تحلیل شدهاند.
نحوه چیدمان گرههای حسگر در محیط، مقادیر انرژی اولیه و ترافیک ارسالی اولیه در تمام شبیهسازیها به شکل کاملا تصادفی تولید میشود. همان گونه که بیان شد تمام سناریوهای مطرح در شبیهسازی به شکل ناهمگن در انرژی اولیه و ترافیک ارسالی هستند. بنابراین، سناریو شبیهسازی تا حد زیادی به واقعیت نزدیک خواهد بود و میتوانیم تا حدی عملکرد الگوریتم پیشنهادی را در محیط واقعی نیز بررسی کنیم. برای پیادهسازی الگوریتم پیشنهادی این مقاله از نرم افزار متلب[25] 2012 استفاده شده است. شبیهساز نوشته شده بروی یک کامپیوتر با CPU Core i5، 6GByte RAM و بروی سیستم عامل Windows 7 SP1 اجرا شده است.
از مدل رادیویی بیان شده در [11] برای محاسبه میزان انرژی مصرفی ارتباطات رادیویی در ارسال داده و دریافت داده استفاده میشود. انرژی مصرفی برای ارسال داده به طول k بیت و به فاصله d بین دو گره i و j در Error! Reference source not found. بیان شده است.
|
(26) |
همچنین، انرژی مصرفی برای دریافت داده به طول k بیت بین دو گره i و j در Error! Reference source not found. بیان شده است.
|
(27) |
برابر با انرژی مصرفی مدارت فرستنده گیرنده است و و انرژی لازم برای ارسال k بیت داده با نرخ خطای بیتی قابل قبول است. همچنین، مقادیر بالا به فاصله ارسال داده در مدل Free Space و multipath fading وابسته است [22]. مواردی که در زمان شبیه سازی باید به آن توجه کرد. 1- محیط استقرار گرهها یک مربع N*N است و گرهها با استفاده از توزیع تصادفی در محیط پخش شده اند. تمام گرهها و چاهک به شکل ایستا در محیط قرار دارند. 2- گره حسگر دارای کنترل توان خروجی بر حسب فاصله است. بنابراین، میتواند برحسب فاصله، میزان توان ارسالی را کاهش یا افزایش میدهد. 3- تمام گرهها توان ارسال داده به شکل مستقیم به سمت گره چاهک را دارند. 4-شبکه حسگر از نوع ناهمگن است و تمام گرهها در انرژی ارسالی، ترافیک ارسالی متفاوت از یکدیگر هستند. 5- شبکه حسگر دارای تنها یک چاهک و ظرفیت داده ورودی آن به شکل نامحدود در نظر گرفته شده است.
شاخصهای سناریو مورد استفاده در این شبیهسازی در جدولهای (3) و (4) و
جدول (5) بیان شده است. بستههای داده کنترلی در مرحله ساخت خوشه و به منظور ارسال اطلاعات گرهها تا چاهک استفاده میشود. در ابتدای هر مرحله از اجرا شبیهسازی، گرهها از طریق بستههای Hello مختصات، انرژی باقیمانده و میزان ترافیک ارسالی خود را به چاهک اعلام میکنند. سپس، چاهک عملیات خوشهبندی را شروع و در نهایت، از طریق بستههای کنترلی Reply نقش هر گره در مرحله جاری را اطلاعرسانی می‌کند. همچنین، در مرحله ارسال داده، سرخوشهها با استفاده از بسته کنترلی Hello برنامه زمانبندی ارسال داده گرهها را به اطلاع گرههای عضو خوشه میرساند. در این سناریو وزن W1 در حدود 4 برابر وزن W2 در نظر گرفته شده است. این به معنای تاکید بالا بروی انتخاب سرخوشه مناسب نسبت به ایجاد خوشههای بهینه در این سناریو است. البته میتوان مقادیر دیگری برای وزنهای فوق متناسب با نوع هدف (خوشهبندی بهینه یا انتخاب سرخوشه بهینه) در نظر گرفت و در پی آن جوابهایی دیگر نیز یافت.
فرآیند انتخاب به دنبال یافتن کروموزمهای بهینه از جمعیت فعلی برای مرحله پیوند و ساخت جمعیت جدید است. چرخه رولت به عنوان عملگر انتخاب در مرحله پیوند داده در این سناریو استفاده شده است. فرآیند تولید جمعیت اولیه در الگوریتم ژنتیک مورد استفاده در این پژوهش، براساس میزان انرژی باقیمانده و بر اساس رابطه (17) است. در پایان نیز سهم عملگرهای مختلف در ایجاد جمعیت نسل جدید برحسب درصد بیان شده است.
جدول (4) به بیان شاخصهای مورد استفاده الگوریتم ژنتیک پرداخته است. روش پیوند مورد استفاده در الگوریتم ژنتیک از نوع ترکیبی است و از سه روش پیوند یک نقطهای، دو نقطهای و یکنواخت استفاده شده است. میزان درصد هر روش پیوند در هر مرحله بیان شده است.
جدول (3): شاخصهای محیط شبیهسازی
|
شاخص |
سناریو شماره یک |
|
ابعاد محیط استقرار |
300 *300 مترمربع |
|
مختصات چاهک |
(150و150) مرکز |
|
تعداد گرهها |
100 |
|
انرژی اولیه گره |
0. 2~0. 05 ژول |
|
تعداد مراحل اجرا |
800 |
|
اندازه بسته |
5120~3072 بیت |
|
اندازه بسته کنترلی (Hello-Reply) |
64 بیت |
|
وزن W1 |
0. 72 |
|
وزن W2 |
0. 18 |
جدول (4):شاخصهای الگوریتم ژنتیک
|
شاخص |
-- |
|
مراحل اجرای الگوریتم ژنتیک |
40 |
|
جمعیت اولیه الگوریتم ژنتیک |
20 |
|
الگوریتم تولید جمعیت اولیه |
بر اساس انرژی باقیمانده |
|
الگوریتم پیوند |
(یکنواخت، دو و تک نقطهای) |
|
الگوریتم انتخاب(پیوند) |
چرخه رولت |
|
الگوریتم جهش |
تصادفی |
|
سهم عمل پیوند در جمعیت جدید |
50 % |
|
سهم عمل جهش در جمعیت جدید |
20% |
|
سهم عملگر پیوند یک نقطهای |
10% |
|
سهم عملگر پیوند دو نقطهای |
20% |
|
سهم عملگر پیوند یکنواخت |
70% |
جدول (5): شاخصهای ارسال داده
|
50 nJ/bit |
Eelec |
|
10 pJ/bit/m |
Efs |
|
0. 0013 pJ/bit/m4 |
Efs |
|
87 m |
d0 |
|
5 nJ/bit |
EDA |
به نوع گرههای مرده در طول مدت شبیهسازی اشاره می‌کند. بر اساس شکل (4)، تعداد گرههای سرخوشه مرده در الگوریتم EAGCA و EAGCA* به علت انتخاب سرخوشه مناسب نسبت به سایر الگوریتمها بسیار کمتر است و بیشترین گرههای مرده از نوع گرههای عضو خوشه هستند که نشان از ایجاد خوشههای بهینه و انتخاب سرخوشه مناسب دارد. از طرفی، الگوریتم EAGCA* نیز به علت بهره بردن از گرههای مستقل، بار کمتری بر روی سرخوشهها اعمال می‌کند. بنابراین، میزان مرگ سرخوشهها در روش EAGCA* از روش EAGCA نیز کمتر است.
تابع برازش الگوریتم EAERP فقط کمینه کردن انرژی ارتباطات درون و برون خوشهای است. بنابراین، تابع برازش EAERP به شکل ضمنی کوشش در انتخاب گرهای به عنوان سرخوشه دارد که تا حد امکان به چاهک نزدیک باشد. بنابراین، شاخصهای دیگری نظیر انرژی باقیمانده و ترافیک ارسالی که تاثیر بهسزایی در انتخاب سرخوشه بهینه دارند در روش انتخاب سرخوشه توسط EAERP مدنظر قرار نگرفته اند که موجب انتخاب سرخوشههای غیربهینه خواهد شد. درالگوریتم LEACH نیز به علت انتخاب سرخوشه به شکل تصادفی و عدم توجه به انرژی گرهها تعداد سرخوشههای مرده نیز افزایش یافته است. این مرگ بالا در تعداد سرخوشه باعث کاهش طول عمر شبکه، افزایش انرژی اتلافی و کاهش داده دریافتی در چاهک خواهد شد. انرژی اتلافی عبارت است از انرژی که توسط گرههای عضو برای ارسال داده به سرخوشه مصرف شده، ولی گره سرخوشه پس از دریافت داده به علت عدم وجود انرژی لازم، از ارسال دادهها امتناع می‌کند.
شکل (4): مقایسه انواع گرههای مرده در الگوریتم‌های مختلف
شکل (5): مقایسه شاخص FND و HNA
شکل (5) به مقایسه میزان بهبود الگوریتم‌های مختلف در شاخص FND2 و HNA1 پرداخته است. از آنجا که طول عمر شبکه یک مفهوم کاربرد- محور است.، باید به اقتضای شرایط این شاخص را تعریف کرد. در [25 و 26] از شاخصهایی نظیر HNA[26] و FND[27] به منظور تخمین طول عمر شبکه حسگر بیسیم استفاده شده است. در این شبیهسازی، FND به مرگ نخستین گره و HNA به مرگ نیمی از گرههای حسگر اشاره دارد. علت بهبود شاخصهای FND و HNA در الگوریتم‌های EAGCA و EAGCA*، انتخاب سرخوشه مناسب است که نتیجه آن کاهش انرژی اتلافی و افزایش طول عمر شبکه میباشد.
بنابراین، در الگوریتم EAGCA* به علت کاهش انرژی اتلافی شاهد بیشترین بهبود عملکرد و در الگوریتم LEACH به علت بیشترین مقدار انرژی اتلافی شاهد کمترین بهبود در عملکرد شاخصهای یاد شده هستیم.
تحلیل نتایج داده دریافتی در چاهک
شکل (6) میزان داده دریافتی توسط چاهک در الگوریتم پیشنهادی را با سایر الگوریتمها مقایسه می‌کند. اتلاف انرژی کم در الگوریتم EAGCA سبب افزایش طول عمر شبکه حسگر و در نتیجه، بیشینه شدن مقدار شاخص داده دریافتی در چاهک است. از طرفی، در الگوریتم EAGCA* به علت ارسال داده بهینهتر، انرژی اتلافی کمتر و افزایش داده دریافتی بهتری را در چاهک خواهیم داشت.
الگوریتم EAERP و LEACH به علت انتخاب سرخوشه نامناسب اتلاف انرژی بالایی خواهند داشت که نتیجه آن کاهش داده دریافتی در چاهک است.
شکل (6): مقایسه داده دریافتی در چاهک بین الگوریتمها
شکل (7): مقایسه تعداد گرههای زنده در طول شبیهسازی
شکل (7) به مقایسه تعداد گرههای زنده در کل مراحل شبیهسازی اشاره می‌کند. همانگونه که پیش از این نیز بیان شد، عدم توجه الگوریتم‌های LEACH و EAERP در انتخاب سرخوشه مناسب انرژی اتلافی را افزایش و به دنبال آن، باعث افزایش مرگ گرهها در اوایل استقرار شبکه خواهد شد؛ که نیتجه آن کاهش طول عمر شبکه است. الگوریتم‌های EAGCA و EAGCA* به علت انرژی اتلافی کمتر طول عمر بالاتری نسبت به سایر الگوریتمها دارند. همچنین، درEAGCA* برخی از گرهها به طور مستقل به ارسال داده به سمت چاهک مبادرت میورزند که این عامل باعث صرفهجویی در انرژی مصرفی برای ارسال داده میشود و برتری EAGCA* نسبت به EAGCA را نشان میدهد.
شکل (8)، به مقایسه نسبت انرژی مصرفی تمام سرخوشهها به کل داده ارسالی از سمت سرخوشه به سمت چاهک در مرحله جاری پرداخته است. بر اساس رابطه بالا، هر چه مقدار داده ارسالی بیشتر یا کل انرژی مصرفی کمتر باشد، مقدار عددی این شاخص نیز کمتر خواهد بود. بنابراین، مقدار کمتر این شاخص اشاره به ارسال داده بالا به سمت چاهک با مصرف انرژی کم دارد. علاوه بر این، مقدار کمتر این شاخص به ایجاد خوشههای بهینه و کاهش انرژی اتلافی در شبکه اشاره دارد.
بر اساس شکل (8)، مجموع انرژی مصرفی در الگوریتم EAGCA* و EAGCA نسبت به EAERP کمتر بوده است. همچنین، EAGCA* با کمترین انرژی مصرفی سرخوشه، بیشترین داده ارسالی به سمت چاهک را داشته است. بنابراین، مقدار شاخص یاد شده برای EAGCA* کمترین مقدار نسبت به سایرین خواهد بود. EAGCA در مقایسه با EAGCA* به علت عدم بهرهگیری از وجود گرههای مستقل در ارسال داده، انرژی مصرفی بالاتر و کاهش داده دریافتی در چاهک را به دنبال خواهد داشت. بنابراین، مقدار شاخص یاد شده برای EAGCA بالاتر است. اما در EAERP وجود سرخوشههای نامناسب باعث ارسال داده کمتر به سمت چاهک و مصرف انرژی بالاتر شده است که این امر باعث افزایش مقدار شاخص یاد شده، شده است.
همچنین، مقدار شاخص مفروض در الگوریتم LEACH به علت کمینه بودن داده دریافتی در چاهک و بیشینه بودن انرژی مصرفی سرخوشهها، نسبت به سایر الگوریتمها بیشتر است.
شکل (8): نسبت مجموع انرژی مصرفی سرخوشهها به مجموع داده دریافتی در هر مرحله شبیهسازی
در [27] شاخصبهره وری انرژی مصرفی تعریف شده که عبارت است از: مجموع بستههای رسیده به مقصد به مجموع انرژی مصرفی گرههای حسگر شبکه. در شکل (10) به مقایسه بهرهوری انرژی برای الگوریتم‌های مفروض پرداخته شده است. هر چه مقدار انرژی مصرفی کمتر و میزان بستههای دریافتی در مقصد بیشتر باشد، میزان بهره وری انرژی بالاتر خواهد بود. الگوریتم‌های پیشنهادی براساس تعریف بالا دارای بیشترین میزان بهرهوری انرژی است.
شکل (9): مقایسه بهره وری انرژی در الگوریتم‌های مختلف
شکل (10): مقایسه نرخ موفقیت در الگوریتم‌های مختلف
مجموع داده دریافت شده در چاهک بر حسب کیلوبایت به مجموع داده تولید شده در شبکه برحسب کیلوبایت را نرخ موفقیت داده مینامند [27]. هر چه مقدار داده دریافتی در چاهک نسبت به داده تولید شده بیشتر باشد، درصد نرخ موفقیت بیشتر است. شکل (10) به مقایسه نرخ موفقیت در الگوریتم‌های مختلف پرداخته است.
در این مقاله، دو روش خوشهبندی مبتنی بر الگوریتم ژنتیک در شبکه حسگر ناهمگن ارایه شد. در خوشهبندی شبکههای حسگر، یکی از شاخصهای مهم که در میزان داده دریافتی در چاهک، افزایش طول عمر شبکه و کاهش انرژی اتلافی مؤثر است، انتخاب سرخوشه مناسب میباشد. اما در بیشتر روشهای خوشهبندی مبتنی بر الگوریتم‌های تکاملی، تنها به ایجاد خوشههای بهینه پرداخته شده و به این شاخص مهم توجه نشده است. در این مقاله، با بیان یک تابع برازش دو بخشی، نه تنها به ایجاد خوشههای بهینه پرداخته شده، بلکه انتخاب سرخوشه مناسب براساس شاخصهای انرژی باقیمانده گره، تراکم گرههای همسایه و فاصله گره تا چاهک را نیز در نظر گرفته شده است. نتایج نشان میدهد که الگوریتم EAGCA در بیشینه کردن طول عمر شبکه و دادههای دریافتی در چاهک و همچنین، کمینه کردن انرژی اتلافی نسبت به سایر روشها موفقتر عمل کرده است. همچنین، با ارایه یک الگوریتم جدید در نحوه ارسال داده با عنوان الگوریتم EAGCA*، به بهبود و ترمیم خوشههای ایجاد شده کمک شده است. به عنوان پیشنهاد برای کارهای آینده میتوان به بررسی مقادیر w های متفاوت بر عملکرد الگوریتم اشاره کرد. همچنین، به علت اینکه تابع هدف بیان شده از نوع چند هدفه است، میتوان از الگوریتم‌های بهینهسازی چند هدفه مانند NSGAII یا MOPSO برای حل دقیقتر این تابع هدف بهره برد. افزون بر این، میتوان به بررسی تاثیر مکان های قرارگیری متفاوت چاهک و تاثیر آن بر شاخصهای متفاوت شبکه حسگر اشاره کرد. همچنین، میتوان شاخص متفاوت دیگری را در نحوه وزندهی به گرهها در نظر گرفت و رابطه ریاضی جدید را با رابطه ارایه شده در این مقاله مقایسه کرد. از الگوریتم‌های فرا ابتکاری دیگری نظیر الگوریتم ازدحام ذرات، جستوجوی هارمونی و. . . به جای الگوریتم ژنتیک استفاده شده در این مقاله بهره گرفت و میزان بهبود عملکرد سایر الگوریتم‌های فرا ابتکاری در یافتن سرخوشه بهینه را با این الگوریتم مقایسه کرد. در نهایت، میتوان به بررسی عملکرد این الگوریتم با سایر الگوریتم‌های خوشهبندی در محیطهای همگن نیز پرداخت و میزان بهبود عملکرد این الگوریتم را در محیطهای همگن نیز بررسی کرد.
[1] Task
[2] Hierarchical
[3] Cluster
[4] Cluster Head
[5] Sink
[6] Scalability
[7] Local Distance
[8] Metaheuristic Algorithms
[9] Distributed
[10] Binary
[11] Cluster Cohesion
[12] Cluster Separation
[13] Harmony Search
[14] Genetic Algorithm
[15] Particle Swarm Optimization
[16] Ant Colony Optimization
[17] Crossover
[18] Parent
[19] Offspring
[20] Mask
[21] Hello Message
[22] Reply Message
[23] Time Division Multiple Access
[24] Collision
[25] MATLAB
[26] Half Alive Node
[27] First Node Dead
[28] Energy Efficiency
[xxix] Success Rate
)