پبشرفت‏های روز افزون در ساخت مدارات مجتمع و همچنین، توسعه ارتباطات ‏بی‏سیم باعث توسعه ریز حسگرهایی شده است که بدنه اصلی یک شبکه حسگر بی‏سیم را ایجاد می‏کنند. ‏به عبارت دیگر یک شبکه حسگر متشکل از گره‏هایی است که به شکل متراکم در محیط پخش شده و با همکاری یکدیگر یک وظیفه[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 مقایسه می‏شوند. ‏در بخش هشتم نتایج تحلیل و برخی پیشنهادات برای کارهای بعدی ارائه خواهد شد. ‏

 

1- مروری بر کارهای پیشین

الگوریتم LEACH [11] یکی از الگوریتم‏های اولیه در حوزه خوشه‏بندی شبکه‏های حسگر بی‏سیم است که به شکل توزیع شده[9] به خوشه‏بندی شبکه حسگر می‏پردازد. ‏هر گره در ابتدا یک عدد تصادفی بین صفر تا یک را تولید می‏کند. ‏سپس، بر اساس مقدار حاصل از (1) میزان احتمال سرخوشه شدن در مرحله جاری را مشخص می‏کند. ‏در صورتی که عدد تصادفی از مقدار احتمال T(s) کمتر باشد، گره حسگر به عنوان سرخوشه در مرحله جاری انتخاب خواهد شد. ‏که T(s) از رابطه زیر محاسبه می‏شود. ‏

 

در این رابطه، P عبارت است از درصد مطلوب تعداد سرخوشه، r مرحله جاری و G مجموعه گره‏هایی است که در  مرحله قبل سرخوشه نبوده‏اند. ‏به منظور توزیع نقش سرخوشه بین تمام گره‏ها، در ابتدای هر مرحله انتخاب سرخوشه جدید با استفاده از رابطه (1) انجام می‏گیرد. ‏از جمله معایب الگوریتم LEACH عدم توزیع مناسب سرخوشه‏ها در محیط شبکه و انتخاب غیر بهینه گره‏ها به عنوان سرخوشه است. ‏

در [12] یک روش خوشه‏بندی مبتنی بر الگوریتم ژنتیک ارائه شده است. ‏دراین الگوریتم از کروموزم‏های دودویی[10] به منظور تعیین نقش هر گره استفاده می شود. ‏تابع هدف این الگوریتم در (2) بیان شده است. ‏

 

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

در [13] یک روش خوشه‏بندی مبتنی بر الگوریتم ژنتیک ارائه شده است که هدف آن بهبود طول عمر شبکه از طریق کاهش انرژی مصرفی است. ‏در این الگوریتم هر کروموزم، پیکربندی شبکه در مرحله جاری را نشان می‏دهد. ‏در (3) تابع برازندگی الگوریتم مورد نظر بیان شده است. ‏

در این رابطه، ND مجموع فواصل گره‏های عضو خوشه تا گره سرخوشه و  تعداد سرخوشه‏هاست. ‏هدف انتخاب راه‏حلی(کروموزم جواب) است که مقدار تابع برازندگی برای کروموزم انتخابی کمینه باشد. ‏

در [14- 17]، نویسندگان با در نظر گرفتن شاخص‏هایی دیگری نظیر، انحراف معیار در فواصل درون خوشه (SD)، تخمین انرژی ارسالی (E) و تعداد مراحل ارسال داده (T)، به دنبال بهبود تابع برازندگی ارائه شده در [12] هستند. ‏استفاده از این مجموعه از شاخص‏ها در تعریف تابع برازندگی مفروض این اطمینان را خواهد داد که پیکربندی شبکه حاصل از بهترین کروموزم، در میزان داده ارسالی بیشینه و در میزان انرژی مصرفی کمینه خواهد بود. ‏در نتیجه، الگوریتم HCR با تابع برازندگی بیان شده در (4) نسبت به تابع برازندگی الگوریتم ارائه شده در [12] در میزان داده ارسالی برتری دارد [18]. ‏

 

در این رابطه، مقدار TD برابر با مجموع فواصل تمام گره‏های حسگر تا چاهک، D برابر با جمع فواصل گره‏های عضو خوشه تا سرخوشه و جمع فواصل بین سرخوشه‏ها تا چاهک است. ‏برای مثال، مقدار  برای یک خوشه با k گره عضو در (5) محاسبه شده است. ‏همچنین، هر f_i قسمتی از تابع هدف را تشکیل می‏دهد. ‏بنابراین،‏ مجموع مقادیر f_i حاصل از هر قسمت، کل تابع هدف الگوریتم HCR را تشکیل می‏دهد. ‏

که  به فاصله گره i تا سرخوشه c و  به فاصله سرخوشه c تا چاهک اشاره دارد. ‏مقدار E اشاره به مجموع انرژی مصرفی برای دریافت و ارسال داده‏های تجمیع شده از خوشه‏ها به چاهک دارد. ‏

اگرچه مقادیر اولیه ها در تابع برازش (4) به شکل دلخواه تعیین می‏شود ولی در حین مراحل بعدی این مقدار بر اساس ارزش بهترین کروموزم به روز رسانی می‏شود. ‏

در [19]، یک روش خوشه‏بندی مبتنی بر الگوریتم ژنتیک ارائه شده است که هدف آن بهبود تابع برازش بیان شده برای الگوریتم [14- 17] است. ‏تابع برازش (6) علاوه بر پنج شاخص‏ بیان شده برای تابع برازش (4)، دو شاخص‏ انرژی باقی‏مانده (RE) و تعداد بسته دریافتی(FT) را نیز در زمان محاسبه مقدار تابع برازش برای هر کروموزم در نظر گرفته است. ‏f_i برابر با مقدار حاصل از تابع برازش برای بخش های مختلف است که مجموع f_i ها، مقدار کل تابع برازش را تشکیل می‏دهد. ‏

 

در [18] یک الگوریتم خوشه‏بندی پویا، تک‏گامی، انرژی آگاه و مبتنی بر الگوریتم تکاملی(EAERP) ارائه شده است که هدف آن کاهش انرژی اتلافی، و افزایش طول عمر شبکه است. ‏

در رابطه (7)،  تعداد سرخوشه‏ها و  تمام اعضای خوشه i ام است. ‏ برابر با انرژی مصرفی برای دریافت داده،  برابر با انرژی مصرفی برای تجمیع داده توسط سرخوشه و  انرژی مصرفی برای ارسال داده از گره عضو به سرخوشه i ام است. ‏

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

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

در [19] یک الگوریتم خوشه‏بندی تک‏گامی و مبتنی بر الگوریتم تکاملی (ERP) ارایه شده است. ‏هدف تابع برازندگی الگوریتم ERP کمینه کردن تعداد سرخوشه‏ها و مجموع فواصل درون و برون خوشه‏ای است. ‏کمینه کردن مجموع فواصل در الگوریتم EAR شامل سه بخش کمینه سازی فواصل درون خوشه‏ای (چسبندگی خوشه‏ای[11]) و پراکندگی مناسب سرخوشه‏ها در محیط (انفصال خوشه‏ای[12]) است. ‏بخش اول تابع برازندگی الگوریتم ERP، در (8) اشاره شده است، که وظیفه این بخش کمینه کردن مجموع فواصل درون خوشه‏ای است و به چسبندگی خوشه‏ای اشاره می‏کند. ‏مقدارn به تعداد گره‏های عضو سرخوشه i ام یا () اشاره دارد. ‏ نیز به فاصله بین گره n ام تا  اشاره دارد. ‏

بخش دوم تابع برازندگی در (9) اشاره شده است، که وظیفه توزیع مناسب سرخوشه‏ها در سطح شبکه را بر عهده دارد. ‏

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

بخش سوم تابع برازندگی در (11) اشاره شده است، که هدف این بخش تعیین تعداد مناسب سرخوشه‏هاست. ‏

تابع برازندگی الگوریتم ERP در (12) به طور کامل بیان شده است. ‏مقادیر w و (1-w) میزان تاکید بروی هر بخش از تابع برازندگی را مشخص می‏کند. ‏

الگوریتم جستجوی هارمونی[13] [20] از جمله الگوریتم‏های فرا اکتشافی است که به تازگی در حوزه خوشه‏بندی شبکه حسگر استفاده شده است. ‏در [21] یک روش خوشه‏بندی مبتنی بر الگوریتم جستجوی هارمونی با هدف کمینه کردن مجموع فواصل درون خوشه‏ای و بهینه کردن مصرف انرژی ارائه شده است که هدف آن افزایش طول عمر شبکه حسگر خواهد بود. ‏تابع برازش این روش خوشه‏بندی در رابطه (13) بیان شده است. ‏

 اشاره به بیش‏ترین‏ فاصله اقلیدسی بین گره‏ها دارد که نحوه محاسبه آن در (14) بیان شده است. ‏

 اشاره به سرخوشه k ام، ‏ اشاره به فاصله بین گره i ام و سرخوشه k ام و  اشاره به تعداد اعضای خوشه  دارد. ‏f2 برابر با نسبت انرژی تمام گره‏های زنده به انرژی تمام سرخوشه‏های مرحله جاری است که در (15) بیان شده است. ‏

 مجموع انرژی تمام سرخوشه‏های انتخاب شده و  مجموع انرژی تمام گره‏های حسگر است. ‏مقدار کمینه ، نشان از کمینه بودن مجموع فواصل درون خوشه‏ای دارد. ‏همچنین، مقدار کمینه  در انتخاب گره‏هایی با انرژی باقی‏مانده بیشتر به عنوان سرخوشه تاثیرگذار است. ‏بنابراین هدف کمینه کردن مقدار تابع برازش بیان شده در (13) است. ‏مقادیر w و (1-w) نشان‏دهنده میزان تأکید بروی هر بخش از تابع برازندگی است که می‏تواند مقادیر مختلفی را به خود اختصاص دهد. ‏از جمله معایب الگوریتم HSA، عدم توجه به شاخص‏‏هایی نظیر بار ارسالی گره در زمان انتخاب سرخوشه است. ‏همچنین، در تابع برازش HSA کمینه کردن فواصل سرخوشه تا چاهک به عنوان یک شاخص‏ تاثیرگذار در مصرف انرژی گره‏ها، در نظر گرفته نشده است که ممکن است به مرگ زودرس گره‏های سرخوشه منجر شود. ‏

 

2- مروری بر الگوریتم ژنتیک

امروزه یکی از روش‏های مطرح برای حل دسته‏ای از مسائل بهینه‏سازی، استفاده از روش‏های موسوم به روش‏های بهینه‏سازی مبتنی بر هوش دسته جمعی است. ‏

الگوریتم‏های خوشه‏بندی تکاملی، با بهره گیری از الگوریتم‏های تکاملی نظیر الگوریتم ژنتیک[14]، بهینه‏سازی ازدحام ذرات[15]، بهینه‏سازی کلونی مورچگان[16] و . ‏. ‏. ‏تلاش می‏کنند بهترین جواب ممکن برای ساخت خوشه را پیدا کنند. ‏به طوری که خوشه حاصل دارای کمینه مقدار انرژی مصرفی، بیشینه مقدار داده ارسالی به چاهک و. ‏. ‏. ‏باشد. ‏الگوریتم‏های [13، 17 و 23] از نمونه الگوریتم‏های مطرح در حوزه خوشه‏بندی شبکه حسگر بی‏سیم مبتنی بر الگوریتم‏های تکاملی است. ‏

الگوریتم ژنتیک [24] نوع خاصی از الگوریتم‌های تکاملی است که از روش‏‌های زیست‌شناسی مانند وراثت و جهش استفاده می‌کند. ‏در الگوریتم ژنتیک، یک کروموزوم، مجموعه‌ای از شاخص‏هاست به طوری که یک راه حل پیشنهادی را برای مسأله‌ای که الگوریتم ژنتیک سعی در حل آن دارد، تعریف می‏کند. ‏الگوریتم ژنتیک با تولید یک جمعیت اولیه تصادفی شروع به کار می‏کند. ‏پس از تولید جمعیت اولیه، درصدی از کروموزم‏ها به تصادف به عنوان والد از جمعیت فعلی انتخاب می‏شوند. ‏

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

شکل (1) الگوریتم ژنتیک ارایه شده است. ‏در این مقاله، نحوه تولید جمعیت اولیه و عمل پیوند، از الگوریتم ژنتیک استاندارد متفاوت خواهد بود. ‏

 

 

 

شکل (1):فلوچارت الگوریتم ژنتیک

3-الگوریتم EAGCA

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

سپس، به معرفی الگوریتم EAGCA* می‏پردازیم. ‏این الگوریتم کوشش دارد تا با تغییراتی در خوشه‏های ایجاد شده، عملکرد EAGCA را بهبود بخشد. ‏در ادامه، ویژگی‏های الگوریتم ژنتیک نظیر تابع برازش الگورتیم EAGCA، نوع پیوند کروموزم‏ها، جهش و نحوه‏ مدل کردن الگوریتم EAGCA برای حل با الگوریتم ژنتیک بیان خواهد شد. ‏

 

3-1- نمایش کروموزم

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

برای مثال، اگر مقدار i امین ژن یک کروموزم نوع دوم برابر با j باشد، یعنی گره n_i به سرخوشه g_j انتساب داده شده است. ‏برای هر گره حسگر یک عدد انحصاری (شروع از یک) به عنوان شماره شناسایی در نظر گرفته می‏شود. ‏بنابراین، در کروموزم جواب، اندیس هر ژن اشاره به شماره یک گره حسگر دارد. ‏مقدار هر ژن نیز به شماره گره سرخوشه برای گره حسگر اشاره دارد. ‏چون گره‏های سرخوشه از گره‏های حسگر انتخاب می‏شوند، برای گره سرخوشه، مقدار ژن که نشان‏دهنده گره سرخوشه است با اندیس ژن برابر است. ‏

شکل (2) یک شبکه حسگر بی‏سیم با 10 گره را نشان می‏دهد. ‏به علت وجود 10 گره در شبکه، کروموزم راه حل نیز10 ژن خواهد داشت. ‏کروموزم راه حل در شکل (2) نشان داده شده است. ‏با توجه به کروموزم جواب، g₂ و g₅ به عنوان سرخوشه و مابقی گره‏ها، عضو خوشه هستند. ‏برای مثال، گره n₃ به سرخوشه g₂ متصل است. ‏نکته قابل بیان اینکه هر کروموزم نشان‏دهنده یک جواب برای خوشه‏بندی شبکه حسگر است. ‏

 

شکل (2): نمایش کروموزم

 

3-2- جمعیت اولیه

جمعیت اولیه مجموعه‏ای از کروموزم‏های تولید شده تصادفی است. ‏هر کروموزم یک پیکربندی غیربهینه از شبکه را نشان می‏دهد که هر ژن از کروموزم با مقدار 1 به معنای سرخوشه و با مقدار صفر به معنای عضو خوشه و 1- به عنوان گره غیرفعال (مرده) پر شده است. ‏بنابراین،‏ بر اساس (16) برای ژن مربوط به گره j ام در کروموزم I داریم:

 

این جمعیت به عنوان راه‏حل‏های اولیه تصادفی به الگوریتم ژنتیک به منظور شروع کار تحویل داده می‏شود. ‏از آن‏جا که جمعیت اولیه اثر بالایی در رسیدن به جواب‏های بهتر دارد،‏ در عوض ایجاد جمعیت اولیه به شکل کاملا تصادفی از روش آگاهانه‏تری برای ایجاد جمیعت اولیه در الگوریتم EAGCA بهره گرفته شده است. ‏

در این روش، ابتدا میانگین انرژی گره‏ها محاسبه می‏شود و سپس، به تصادف از گره‏هایی که انرژی باقی‏مانده بالاتر از میانگین دارند تعدادی گره به عنوان سرخوشه انتخاب خواهد شد. ‏در کروموزم‏های تصادفی حاصل از این روش، گره‏هایی به عنوان کاندید سرخوشه ( ) انتخاب خواهند شد که انرژی باقی‏مانده بالاتری از میانگین انرژی کل گره‏ها دارند و در واقع از انتخاب گره‏هایی با انرژی پایین به عنوان سرخوشه پرهیز می‏شود. ‏

بهره گرفتن از این روش سبب می‏شود تا الگوریتم ژنتیک با سرعت بیشتری به سمت جواب‏ بهنیه سراسری و انتخاب سرخوشه مناسب حرکت کند. ‏نحوه انتخاب گره سرخوشه برای جمعیت اولیه در ادامه بیان شده است. ‏ابتدا هر گره یک عدد تصادفی بین صفر تا 1 را حدس می‏زند. ‏اگر مقدار عدد تصادفی حدس زده شده کمتر از  باشد و گره مورد نظر نیز عضو مجموعه کاندید سرخوشه یعنی باشد ژن مربوط به آن گره در کروموزم جواب‏های تصادفی برابر یک قرار می‏گیرد، در غیر اینصورت، ژن مورد نظر برابر با صفر در نظر گرفته می‏شود. ‏نحوه محاسبه  در (17) بیان شده است. ‏

 

مجموعه  اشاره به مجموعه گره‏هایی دارد که میزان انرژی فعلی این گره‏ها از میانگین انرژی تمام گره‏های زنده بیشتر است. ‏ اشاره به انرژی فعلی گره i ام و N اشاره به مجموع گره‏های زنده در مرحله جاری دارد. ‏

 

3-3- تابع برازش

میزان ارزش هر کروموزم نسبت به سایر کروموزم‏ها براساس تابع برازش تخمین زده می‏شود. ‏در الگوریتم ژنتیک مقدار حاصل از تابع برازش برای هر کروموزم، تاثیر بالایی در ایجاد نسل بعدی از نسل فعلی دارد. ‏

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

مقدار  برابر با مجموع انرژی مصرفی K گره عضو خوشه برای ارسال داده به سمت سرخوشه(c) است. ‏ و  به ترتیب به مجموع انرژی مصرفی سرخوشه برای دریافت داده‏های از K گره عضو و انرژی مصرفی سرخوشه برای تجمیع داده‏ها اشاره دارد. ‏ انرژی مصرفی برای ارسال داده تجمیع شده از سوی سرخوشه(c) به چاهک است. ‏بخش اول تابع برازش الگوریتم EAGCA، مشابه رابطه بالا به دنبال کمینه کردن انرژی مصرفی گره‏های عضو خوشه به منظور ارسال داده تا سرخوشه و انرژی مصرفی گره‏های سرخوشه به منظور تجمیع و ارسال داده به چاهک است. ‏

یکی از شاخص‏‏های مؤثر‏ در کمینه کردن انرژی یاد شده، فاصله ارسال داده است. ‏تابع برازش یاد شده کوشش می‏کند تا با ایجاد توازن در فواصل درون و برون خوشه‏ای به خوشه‏های مناسبی دست پیدا کند. ‏این بخش از تابع برازش، خوشه‏هایی ایجاد خواهد کرد که مجموع فواصل درون خوشه‏ای (از گره عضو خوشه تا سرخوشه) کمینه و از طرفی مکان قرارگیری سرخوشه نیز تا حد امکان نزدیک به چاهک در نظر گرفته شود تا میزان انرژی مصرفی برای ارتباطات درون و برون خوشه‏ای کمینه شود [18]. ‏رابطه (19) بخش اول تابع برازش الگوریتم پیشنهادی را بیان می‏کند. ‏

مقادیر شاخص‏ بالا در بخش دوم این مقاله مفصل بیان شده است. ‏در واقع تابع برازش یاد شده به شکل ضمنی، به انتخاب سرخوشه‏هایی اقدام می‏کند که میزان فاصله این سرخوشه‏ها تا چاهک کمینه شود. ‏اگرچه شاخص‏ فاصله تا چاهک یک مقدار مؤثر‏ در انتخاب سرخوشه است، اما شاخص‏های دیگر نظیر مقدار انرژی باقی‏مانده، مقدار ترافیک ارسالی و میزان تراکم گره‏های همسایه در انتخاب سرخوشه نیز تاثیر‏گذارهستند که در تابع برازش یاد شده نه تنها به روشنی به وجود این شاخص‏‏ها در انتخاب سرخوشه اشاره‏ای نشده، بلکه به شکل ضمنی نیز این شاخص‏‏ها در تابع برازش استفاده نشده اند که به نوعی ضعف تابع برازش [19] است. بنابراین، نیاز است تا با ارائه یک تابع برازش جدید، شاخص‏‏های یاد شده را به روشنی در انتخاب سرخوشه دخیل و سرخوشه‏های بهینه‏ای را برای یک خوشه انتخاب کنیم. ‏هر چه مقدار حاصل از بخش دوم تابع برازش، برای یک کروموزم کمتر باشد، سرخوشه‏های انتخاب شده توسط کروموزم یاد شده بهینه‏تر هستند. ‏نحوه محاسبه بخش دوم تابع برازش برای کروموزم I^k در (20) بیان شده است. ‏

N اشاره به کل گره‏های شبکه،  یک متغیر باینری است که مقدار آن در صورتی که گره i ام سرخوشه باشد برابر با یک و در صورتی که گره i ام سرخوشه نباشد برابر با صفر است. ‏هدف  جلوگیری از تاثیر شاخص‏  مربوط به گره‏های عضو خوشه در رابطه (20) است. ‏هر چه مجموع  گره‏های کاندید سرخوشه در یک کروموزم کمتر باشد، کروموزم مفروض شامل سرخوشه‏های بهتری خواهد بود. ‏چگونگی محاسبه  در (21) بیان شده است. ‏

در این رابطه NB مجموعه همسایگان تک‏گامی در شعاع R گره i ام، R شعاع استاندارد ارسال داده گره حسگر،  برابر با انرژی باقی‏مانده جاری گره i،  بیش‏ترین انرژی موجود در مرحله جاری،  برابر با بیش‏ترین ترافیک تولید شده در مرحله جاری توسط گره‏های زنده و  برابر با ترافیک تولیدی گره i ام در مرحله جاری است. ‏

بر اساس (21) هر چه سرخوشه‏های انتخاب شده در یک کروموزم دارای مقدار انرژی باقی‏مانده بیشتر، مقدار ترافیک کمتر، مجموع انرژی همسایه‏ها کمتر و فاصله محلی کمتری باشند، شاخص‏  بیشتر و مقدار حاصل از بخش دوم تابع برازش (20) کمتر خواهد شد که نشان از وجود سرخوشه‏های مناسب تر در کروموزم یاد شده دارد. ‏در (22) تابع برازش الگوریتم EAGCA به طور کامل بیان شده است. ‏

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

 

3-4- انتخاب

فرآیند انتخاب به دنبال یافتن کروموزم‏های بهینه از جمعیت فعلی برای مرحله پیوند[17] و ساخت جمعیت جدید است. ‏روش‏های متفاوتی نظیر چرخه رولت، الگوریتم تورنمت و الگوریتم رتبه‏بندی به منظور انتخاب کروموزم‏ها استفاده می‏شود. ‏در این مقاله، از روش چرخه رولت به منظور انتخاب کروموزم‏ها استفاده شده است. ‏در چرخه رولت احتمال هر کروموزم بر اساس مقدار تابع برازش و براساس (23) محاسبه می‏شود. ‏

 

در این رابطه N برابر با تعداد جمعیت اولیه کروموزم‏ها و  برابر با مقدار تابع برازش هر کروموزم است. ‏سپس، جمع تجمعی هر کروموزم از جمعیت براساس (24) محاسبه می‏شود. ‏با استفاده از توزیع یکنواخت یک عدد تصادفی بین 0 و 1 تولید می‏شود. ‏اولین کروموزمی که مقدار عدد تصادفی از مقدار تجمعی احتمالات آن کروموزم کمتر باشد، به عنوان کروموزم هدف شناخته می‏شود. ‏

 

3-5- پیوند

عمل ترکیب دو کروموزوم از جمعیت فعلی (والدین[18]) و به دست آوردن دو کروموزوم جدید (فرزندان[19]) را پیوند می‏نامند. ‏الگوریتم‏های متفاوتی نظیر پیوند یک نقطه‏ای، دو نقطه‏ای و یکنواخت برای عمل پیوند استفاده می‏شود. ‏نوع پیوند مورد استفاده در این پژوهش، پیوند ترکیبی شامل پیوند یک و دو نقطه ای و یکنواخت است. ‏در پبوند یکنواخت یک رشته ماسک[20] به طول رشته والد از اعداد تصادفی صفر و یک پرمی‏شود. ‏اگر بیت i ماسک صفر باشد، ژن i رشته جدید برابر با ژنi ام والد اول و در غیراین‏صورت برابر با بیت i ام رشته دوم خواهد بود. ‏این روش روی تک تک بیت‏ها اعمال می‏شود. ‏

3-6- جهش

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

 

3-7- مراحل اجرای الگوریتم EAGCA

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

جدول (1): مراحل اجرای الگوریتم EAGCA

عملکرد اصلی الگوریتم EAGCA را در دو بخش مختلف با عنوان مراحل 2 و5 می‏توان بررسی کرد که عبارتند از:

• مرحله انتخاب سرخوشه و ایجاد خوشه (Clustering Setup)
• مرحله ارسال داده (Data Transmission)

 

3-7-1- بخش انتخاب سرخوشه و ایجاد خوشه (Clustering Setup)

در مرحله ساخت خوشه، گره‏های حسگر اطلاعاتی نظیر انرژی باقی‏مانده، ترافیک و مختصات مکانی را در قالب یک پیام سلام[21] (Hello Message) به سمت چاهک ارسال می‏کنند. ‏چاهک پس از دریافت تمام پبام‏های Hello ارسالی حسگر‏ها، میانگین انرژی گره‏های حسگر را محاسبه می‏کند. ‏گره‏هایی که میزان انرژی باقی‏مانده آن‏ها بیشتر از میانگین انرژی باشد کاندیدای مناسبی برای سرخوشه شدن هستند. ‏

الگوریتم ژنتیک با تولید جمعیت تصادفی اولیه شروع به کار می‏کند و پس از اتمام تعداد مراحل اجرای الگوریتم ژنتیک، بهترین کروموزم انتخاب می‏شود که پیکربندی شبکه حسگر شامل سرخوشه‏ها و اعضای سرخوشه را نشان می‏دهد. ‏چاهک با استفاده از پیام‏های پاسخ[22] (Reply Message)، نقش هر گره و نحوه انتساب گره‏های عضو خوشه به سرخوشه را به گره‏های حسگر اطلاع رسانی می‏کند. ‏پس از شکل‏گیری خوشه‏ها، هر گره سرخوشه وظیفه دارد تا با استفاده از پروتکل TDMA[23] یک برنامه زمان‏بندی برای ارسال داده گره‏های عضو خوشه ایجاد کند. ‏Clustering Setup در ابتدای هر مرحله اجرا شده و انتخاب سرخوشه و ساخت خوشه‏های جدید را انجام می‏دهد. ‏

 

3-7-2- ارسال داده (Data Transmission)

پس از آنکه سرخوشه‏ها انتخاب و برنامه زمان‏بندی ارسال داده گره حسگر توسط سرخوشه‏ها به گره‏های حسگر اعلام شد، گره‏های حسگر بر اساس برنامه زمان‏بندی به ارسال داده به سمت سرخوشه شروع می‏کند. ‏

بر اساس پروتکل TDMA گره‏های حسگر فقط در زمان ارسال داده قسمت رادیویی را فعال کرده و در زمان دیگر این بخش سخت‏افزاری گره خاموش است. ‏استفاده از پروتکل TDMA علاوه بر کاهش انرژی مصرفی، به کاهش تصادم[24] بسته‏های داده نیز کمک می‏کند. ‏پس از ارسال داده از سمت گره‏های حسگر به سرخوشه‏ها، عملیات تجمیع داده توسط سرخوشه انجام و داده‏های تکراری حذف می‏شود. ‏

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

 

4- الگوریتم EAGCA*

بر اساس شکل (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*

 

 

در رابطه بالا،  انرژی مصرفی مورد نیاز براساس شیوه ارسال داده نوع اول است. ‏ به انرژی مصرفی موردنیاز برای ارسال داده به شکل مستقیم یا به شیوه ارسال داده نوع دوم اشاره می‏کند. ‏برای هر گره عضو خوشه مانند گره A مقادیر  و محاسبه شده سپس، در صورتی که  بزرگتر از  باشد گره مستقل و در غیر این‏صورت گره عضو خوشه باقی خواهد ماند. ‏در جدول (2) مراحل اجرای الگوریتم EAGCA* بیان شده است. ‏

 

جدول (2): مراحل اجرای الگوریتم EAGCA*

 

5- ارزیابی الگوریتم‏های پیشنهادی

در این بخش، الگوریتم‏های پیشنهادی در مقایسه با یک الگوریتم خوشه‏بندی کلاسیک و یک الگوریتم خوشه‏بندی مبتنی بر هوش تکاملی ارزیابی خواهد شد. ‏

الگوریتم‏های پیشنهادی با الگوریتم‏های LEACH [11] و EAERP[19] مقایسه شده است. ‏هر دو الگوریتم فرض شده در بخش دوم این مقاله به شکل کامل تحلیل شده‏اند. ‏

نحوه چیدمان گره‏های حسگر در محیط، مقادیر انرژی اولیه و ترافیک ارسالی اولیه در تمام شبیه‏سازی‏ها به شکل کاملا تصادفی تولید می‏شود. ‏همان گونه که بیان شد تمام سناریو‏های مطرح در شبیه‏سازی به شکل ناهمگن در انرژی اولیه و ترافیک ارسالی هستند. ‏بنابراین، سناریو شبیه‏سازی تا حد زیادی به واقعیت نزدیک خواهد بود و می‏توانیم تا حدی عملکرد الگوریتم پیشنهادی را در محیط واقعی نیز بررسی کنیم. ‏برای پیاده‏سازی الگوریتم پیشنهادی این مقاله از نرم افزار متلب[25] 2012 استفاده شده است. ‏شبیه‏ساز نوشته شده بروی یک کامپیوتر با CPU Core i5، 6GByte RAM و بروی سیستم عامل Windows 7 SP1 اجرا شده است. ‏

از مدل رادیویی بیان شده در [11] برای محاسبه میزان انرژی مصرفی ارتباطات رادیویی در ارسال داده  و دریافت داده  استفاده می‏شود. ‏انرژی مصرفی برای ارسال داده به طول k بیت و به فاصله d بین دو گره i و j در Error! Reference source not found. بیان شده است. ‏

 

همچنین، انرژی مصرفی برای دریافت داده به طول k بیت بین دو گره i و j در Error! Reference source not found. بیان شده است. ‏

برابر با انرژی مصرفی مدارت فرستنده گیرنده است و و  انرژی لازم برای ارسال k بیت داده با نرخ خطای بیتی قابل قبول است. همچنین، مقادیر بالا به فاصله ارسال داده در مدل Free Space و multipath fading وابسته است [22]. ‏مواردی که در زمان شبیه سازی باید به آن توجه کرد. ‏1- محیط استقرار گره‏ها یک مربع N*N است و گره‏ها با استفاده از توزیع تصادفی در محیط پخش شده اند. ‏تمام گره‏ها و چاهک به شکل ایستا در محیط قرار دارند. ‏2- گره حسگر دارای کنترل توان خروجی بر حسب فاصله است. ‏بنابراین،‏ می‏تواند برحسب فاصله، میزان توان ارسالی را کاهش یا افزایش می‏دهد. ‏3- تمام گره‏ها توان ارسال داده به شکل مستقیم به سمت گره چاهک را دارند. ‏4-شبکه حسگر از نوع ناهمگن است و تمام گره‏ها در انرژی ارسالی، ترافیک ارسالی متفاوت از یکدیگر هستند. ‏5- شبکه حسگر دارای تنها یک چاهک و ظرفیت داده ورودی آن به شکل نامحدود در نظر گرفته شده است. ‏

شاخص‏های سناریو مورد استفاده در این شبیه‏سازی در جدول‏های (3) و (4) و

جدول (5) بیان شده است. ‏بسته‏های داده کنترلی در مرحله ساخت خوشه و به منظور ارسال اطلاعات گره‏ها تا چاهک استفاده می‏شود. ‏در ابتدای هر مرحله از اجرا شبیه‏سازی، گره‏ها از طریق بسته‏های Hello مختصات، انرژی باقی‏مانده و میزان ترافیک ارسالی خود را به چاهک اعلام می‏کنند. سپس، چاهک عملیات خوشه‏بندی را شروع و در نهایت، از طریق بسته‏های کنترلی Reply نقش هر گره در مرحله جاری را اطلاع‏رسانی می‏کند. ‏همچنین، در مرحله ارسال داده، سرخوشه‏ها با استفاده از بسته کنترلی Hello برنامه زمان‏بندی ارسال داده گره‏ها را به اطلاع گره‏های عضو خوشه می‏رساند. ‏در این سناریو وزن W₁ در حدود 4 برابر وزن W₂ در نظر گرفته شده است. ‏این به معنای تاکید بالا بروی انتخاب سرخوشه مناسب نسبت به ایجاد خوشه‏های بهینه در این سناریو است. ‏البته می‏توان مقادیر دیگری برای وزن‏های فوق متناسب با نوع هدف (خوشه‏بندی بهینه یا انتخاب سرخوشه بهینه) در نظر گرفت و در پی آن جواب‏هایی دیگر نیز یافت. ‏

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

جدول (4) به بیان شاخص‏های مورد استفاده الگوریتم ژنتیک پرداخته است. ‏روش پیوند مورد استفاده در الگوریتم ژنتیک از نوع ترکیبی است و از سه روش پیوند یک نقطه‏ای، دو نقطه‏ای و یکنواخت استفاده شده است. ‏میزان درصد هر روش پیوند در هر مرحله بیان شده است. ‏

 

جدول (3): شاخص‏های محیط شبیه‏سازی

 

جدول (4):شاخص‏های الگوریتم ژنتیک

 

جدول (5): شاخص‏های ارسال داده

 

5-1- تحلیل نتایج انواع گره‏های مرده در طول شبیه‏سازی

به نوع گره‏های مرده در طول مدت شبیه‏سازی اشاره می‏کند. ‏بر اساس شکل (4)، تعداد گره‏های سرخوشه مرده در الگوریتم EAGCA و EAGCA* به علت انتخاب سرخوشه مناسب نسبت به سایر الگوریتم‏ها بسیار کمتر است و بیش‏ترین گره‏های مرده از نوع گره‏های عضو خوشه هستند که نشان از ایجاد خوشه‏های بهینه و انتخاب سرخوشه مناسب دارد. ‏از طرفی، الگوریتم EAGCA* نیز به علت بهره بردن از گره‏های مستقل، بار کمتری بر روی سرخوشه‏ها اعمال می‏کند. بنابراین، میزان مرگ سرخوشه‏ها در روش EAGCA* از روش EAGCA نیز کمتر است. ‏

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

 

 

شکل (4): مقایسه انواع گره‏های مرده در الگوریتم‏های مختلف

 

شکل (5): مقایسه شاخص‏ FND و HNA

5-2- تحلیل نتایج شاخص‏‏های FND وHNA

شکل (5) به مقایسه میزان بهبود الگوریتم‏های مختلف در شاخص‏ FND² و HNA¹ پرداخته است. ‏از آن‏جا که طول عمر شبکه یک مفهوم کاربرد- محور است.، باید به اقتضای شرایط این شاخص‏ را تعریف کرد. ‏در [25 و 26] از شاخص‏هایی نظیر HNA[26] و FND[27] به منظور تخمین طول عمر شبکه حسگر بی‏سیم استفاده شده است. ‏در این شبیه‏سازی، FND به مرگ نخستین گره و HNA به مرگ نیمی از گره‏های حسگر اشاره دارد. ‏علت بهبود شاخص‏های FND و HNA در الگوریتم‏های EAGCA و EAGCA*، انتخاب سرخوشه مناسب است که نتیجه آن کاهش انرژی اتلافی و افزایش طول عمر شبکه می‏باشد. ‏

بنابراین، در الگوریتم EAGCA* به علت کاهش انرژی اتلافی شاهد بیش‏ترین بهبود عملکرد و در الگوریتم LEACH به علت بیش‏ترین مقدار انرژی اتلافی شاهد کم‏ترین بهبود در عملکرد شاخص‏های یاد شده هستیم. ‏

 

تحلیل نتایج داده دریافتی در چاهک

شکل (6) میزان داده دریافتی توسط چاهک در الگوریتم پیشنهادی را با سایر الگوریتم‏ها مقایسه می‏کند. ‏اتلاف انرژی کم در الگوریتم EAGCA سبب افزایش طول عمر شبکه حسگر و در نتیجه، بیشینه شدن مقدار شاخص‏ داده دریافتی در چاهک است. ‏از طرفی، در الگوریتم EAGCA* به علت ارسال داده بهینه‏تر، انرژی اتلافی کمتر و افزایش داده دریافتی بهتری را در چاهک خواهیم داشت. ‏

الگوریتم EAERP و LEACH به علت انتخاب سرخوشه نامناسب اتلاف انرژی بالایی خواهند داشت که نتیجه آن کاهش داده دریافتی در چاهک است. ‏

 

 

شکل (6): مقایسه داده دریافتی در چاهک‏ بین الگوریتم‏ها

 

شکل (7): مقایسه تعداد گره‏های زنده در طول شبیه‏سازی

5-3- تحلیل نتایج تعداد گره‏های زنده در طول شبیه‏سازی

شکل (7) به مقایسه تعداد گره‏های زنده در کل مراحل شبیه‏سازی اشاره می‏کند. ‏همان‏گونه که پیش از این نیز بیان شد، عدم توجه الگوریتم‏های LEACH و EAERP در انتخاب سرخوشه مناسب انرژی اتلافی را افزایش و به دنبال آن، باعث افزایش مرگ گره‏ها در اوایل استقرار شبکه خواهد شد؛ که نیتجه آن کاهش طول عمر شبکه است. ‏الگوریتم‏های EAGCA و EAGCA* به علت انرژی اتلافی کمتر طول عمر بالاتری نسبت به سایر الگوریتم‏ها دارند. ‏همچنین، درEAGCA* برخی از گره‏ها به طور مستقل به ارسال داده به سمت چاهک مبادرت می‏ورزند که این عامل باعث صرفه‏جویی در انرژی مصرفی برای ارسال داده می‏شود و برتری EAGCA* نسبت به EAGCA را نشان می‏دهد. ‏

5-4- تحلیل نتایج نسبت انرژی مصرفی سرخوشه‏ها به داده دریافتی در چاهک

شکل (8)، به مقایسه نسبت انرژی مصرفی تمام سرخوشه‏ها به کل داده ارسالی از سمت سرخوشه به سمت چاهک در مرحله جاری پرداخته است. ‏بر اساس رابطه بالا، هر چه مقدار داده ارسالی بیشتر یا کل انرژی مصرفی کمتر باشد، مقدار عددی این شاخص‏ نیز کمتر خواهد بود. ‏بنابراین، مقدار کمتر این شاخص‏ اشاره به ارسال داده بالا به سمت چاهک با مصرف انرژی کم دارد. ‏علاوه بر این، مقدار کمتر این شاخص‏ به ایجاد خوشه‏های بهینه و کاهش انرژی اتلافی در شبکه اشاره دارد.

بر اساس شکل (8)، مجموع انرژی مصرفی در الگوریتم EAGCA* و EAGCA نسبت به EAERP کمتر بوده است. همچنین، EAGCA* با کم‏ترین انرژی مصرفی سرخوشه، بیش‏ترین داده ارسالی به سمت چاهک را داشته است. بنابراین، مقدار شاخص‏ یاد شده برای EAGCA* کم‏ترین مقدار نسبت به سایرین خواهد بود. ‏EAGCA در مقایسه با EAGCA* به علت عدم بهره‏گیری از وجود گره‏های مستقل در ارسال داده، انرژی مصرفی بالاتر و کاهش داده دریافتی در چاهک را به دنبال خواهد داشت. ‏بنابراین، مقدار شاخص‏ یاد شده برای EAGCA بالاتر است. ‏اما در EAERP وجود سرخوشه‏های نامناسب باعث ارسال داده کمتر به سمت چاهک و مصرف انرژی بالاتر شده است که این امر باعث افزایش مقدار شاخص یاد شده، شده است. ‏

همچنین، ‏مقدار شاخص‏ مفروض در الگوریتم LEACH به علت کمینه بودن داده دریافتی در چاهک و بیشینه بودن انرژی مصرفی سرخوشه‏ها، نسبت به سایر الگوریتم‏ها بیشتر است. ‏

 

 

شکل (8): نسبت مجموع انرژی مصرفی سرخوشه‏ها به مجموع داده دریافتی در هر مرحله شبیه‏سازی

 

5-5- بهره‏وری انرژی[28]

در [27] شاخص‏بهره وری انرژی مصرفی تعریف شده که عبارت است از: مجموع بسته‏های رسیده به مقصد به مجموع انرژی مصرفی گره‏های حسگر شبکه. ‏در شکل (10) به مقایسه بهره‏وری انرژی برای الگوریتم‏های مفروض پرداخته شده است. ‏هر چه مقدار انرژی مصرفی کمتر و میزان بسته‏های دریافتی در مقصد بیشتر باشد، میزان بهره وری انرژی بالاتر خواهد بود. ‏الگوریتم‏های پیشنهادی براساس تعریف بالا دارای بیش‏ترین میزان بهره‏وری انرژی است. ‏

 

 

شکل (9): مقایسه بهره وری انرژی در الگوریتم‏های مختلف

 

شکل (10): مقایسه نرخ موفقیت در الگوریتم‏های مختلف