بخشی از مقاله
چکیده
شبکه هاي حسگر بی سیم از زمان ظهور خود باعث چالشهاي زیادي از سوي محققان براي بهبود هرچه بهتر پارامترهاي آن بوده اند. یکی از مهمترین چالش ها پوشش هرچه بیشتر منطقه تحت مطالعه می باشد. در این مقاله ما یک الگوریتم ژنتیک ارائه داده ایم که سعی دارد با جابجایی سرخوشه ها تعداد گره هاي عضو هر خوشه را افزایش دهد که به این ترتیب تعداد گره هاي تحت پوشش در کل شبکه و منطقه تحت پوشش افزایش می یابد. نتایج بدست آمده نشان داد که الگوریتم ما می تواند به خوبی میزان پوشش گره ها را افزایش دهد.
کلید واژه- شبکه هاي حسگري بی سیم، الگوریتم ژنتیک، سرخوشه، خوشه بندي، پوشش شبکه
-1 مقدمه
پیشرفت تکنولوژي هایی از قبیل حسگرها، الکترونیک و محاسبات باعث گرایش محققان به سوي شبکه هاي حسگر بی سیم شده است. یک شبکه حسگر بی سیم معمولا متشکل ازتعداد بسیار زیادي از گره هاي حسگر ارزان قیمت،چند کاره و محدود از جنبه انرژي و قابلیت محاسباتی و قابلیت هاي ارتباطی می باشد.[1] یک گره حسگر از چهار جزء اصلی پردازشگر ، واحد ارتباطی ، واحد انرژي ، واحدحسگر تشکیل شده است.[10] این گره ها معمولا به صورت انبوه در محیط پخش می شوند تا پدیده اي خاص مثل دما، رادیو اکتیو،زلزله، رطوبت و.. را مونیتور کنند. در شبکه هاي حسگر بی سیم گره هاي حسگر یا به صورت تصادفی و یا به صورت از پیش تعیین شده، بر اساس کاربرد مورد نظرجایگذاري می شوند.[11]
جایگذاري گره ها در میادین جنگ و محیط هاي خطرناك معمولا بصورت تصادفی است در حالی که در محیط هاي بی خطر روش از پیش تعیین شده بهتر است. معمولا روش از پیش تعیین شده نیاز به تعداد گره کمتري نسبت به روش تصادفی دارد.جایگذاري بهینه گره ها یک مسئله چالش برانگیز است و ثابت شده است که یک مسئله NP-Complete می باشد.[2]روش هاي مختلفی مانند شبکه هاي عصبی ، هوش مصنوعی ، بهینه سازي دسته جمعی و بهینه سازي کلونی مورچه ها براي حل این مسئله ارائه شده اند. الگوریتم ژنتیک یکی از قدرتمندترین روشهاي براي حل مسائل بهینه سازي می باشد که بر اساس پروسه تکامل ژنتیکی موجوددر طبیعت عمل می کند.
الگوریتم ژنتیک به طور مداوم با انتخاب تصادفی راه حل ها ، تغییراتی تصادفی روي یک جمعیت از راه حل ها انجام می دهد و جمعیت دیگري را تولید می کند و در طول نسل هاي مختلف جمعیت به سوي راه حل بهینه تکامل پیدا می کند. محققان بسیاري الگوریتم ژنتیک را در بهینه سازي طراحی شبکه حسگر بی سیم به کار برده اند.[9-3] معماري هاي مختلفی براي شبکه هاي حسگر بی سیم مورد استفاده قرار می گیرند و ممکن است داده ها به صورت گام به گام به ایستگاه مرکزي فرستاده شوند یا اینکه از معماري مبتنی بر خوشه بندي استفاده کنند. عموما معماري مبتنی بر خوشه بندي براي بیشتر پروتکل ها به کار می رود.
در معماري مبتنی بر خوشه بندي گره ها در خوشه هایی گروه بندي می شوند و یک سرخوشه براي هر خوشه مشخص می شود. سرخوشه اطلاعات را از گره هاي داخل خوشه اش جمع آوري می کند و آنها را به ایستگاه مرکزي می فرستد. تکنیک هاي خوشه بندي با هدف کاهش مصرف انرژي ، افزایش طول عمر شبکه ، تجمیع اطلاعات[12]، دنبال کردن هدف [13]و مسیریابی[ 16-14]ارائه شده اند. بقیه مقاله به بصورت زیر سازماندهی شده است: در قسمت 2 مدل شبکه ارائه می شود. قسمت 3 الگوریتم ژنتیک ارائه شده را توضیح می دهد.قسمت 4 مربوط به نتایج تجربی است که در طول آزمایشات و با داده هاي مختلف بدست آمده است و بالاخره قسمت 5 که به نتیجه گیري می پردازد.
-2 مدل شبکه
در مدل شبکه ما دو نوع گره وجود دارد نوع اول گرههاي معمولی هستند و گرههاي نوع دوم گرههاي سرخوشه می باشند. گرههاي سرخوشه داراي قابلیت حرکت هستند و می توانند منطقهاي به شعاع 2 واحد را تحت پوشش دهند. گرهها در یک محیط L*L پخش می شوند.در ابتدا همه گرهها به صورت تصادفی پخش می شوند سپس سر خوشه ها که به صورت تصادفی در محل هاي مختلف در محیط پخش شده اند به محلهاي دیگر حرکت می کنند تا بیشترین پوشش را داشته باشند.
-3 الگوریتم ژنتیک
براي حل این مسئله ما از یک الگوریتم ژنتیک استفاده کردیم براي هر الگوریتم ژنتیک باید 5 مرحله زیر را مشخص کنیم.
-1بازنمایی
-2ارزیابی
-3انتخاب
-4عملگرهاي ژنتیک
-5شرط خاتمه
بازنمایی
براي بازنمایی هر راه حل از یک ماتریس m*2 استفاده شده است که m تعداد سرخوشه ها و 2 ستون متناظر به عنوان مختصات x , y هر سرخوشه می باشد. شکل 2 نحوه بازنمایی راه حل ها در الگوریتم ژنتیک ارائه شده را نمایش می دهد.به عنوان مثال گره سرخوشه شماره 4 در سطر 1 و ستون 7 در محیط مورد نظر قرار دارد.تابع ارزیابی تابع ارزیابی ما بسیار ساده بوده و برابر با مجموع خانه هايتحت پوشش هر سرخوشه می باشد و خانه هاي تحت پوشش هر سرخوشه برابر با مجموع خانه هایی است که به فاصله 2 خانه از سر خوشه قرار دارند - شکل . - 1تابع ارزیابی ما در فرمول 1 ارائه شده است.که در آن n برابر تعداد سرخوشه ها می باشد و coverage - i - برابر تعداد گره هر سرخوشه می باشد.انتخاب بعد از اینکه تابع ارزیابی براي هرکدام از کروموزوم ها درجمعیت محاسبه شد توسط مکانیزم انتخاب کروموزوم هایی را که برازندگی بیشتري دارند انتخاب می کنیم و به حوضچه امیزش انتقال می دهیم . براي انجام اینکار از مکانیزم انتخاب تورنمنت استفاده می کنیم.به این ترتیب که k کروموزوم را به صورت تصادفی انتخاب می کنیم و از میان آنها کروموزومی که داراي برازندگی بیشتري است را انتخاب می کنیم.
عملگرهاي ژنتیک عملگر ترکیب
براي انجام عمل ترکیب از عملگر ترکیب تک نقطه اي استفاده کردیم که نحوه انجام آن در شکل 3 نشان داده شده است. نرخ ترکیب را در الگوریتم خود برابر 0.8 قرار دادیم.
-4 نتایج تجربی
الگوریتم ارائه شده را در مطلب پیاده سازي کردیم و تعداد جمعیت را برار 300 قرار دادیم وهر بار عملیات تکامل را 3000 بار انجام دادیم. در اجراهاي مختلف تعداد سرخوشه هاي متفاوتی را در نظر گرفتیم و به ازاي هر یک تعداد گره هاي تحت پوشش را ثبت کردیم. همچنین در اجراهاي مختلف چگالی گره ها در محیط را تغییر دادیم تا رفتار الگوریتم نسبت به چگالی گره ها بررسی کنیم. همچنین درصد پوشش گره ها و میزان بهبود پوشش در روش ژنتیک نسبت به روش تصادفی را بدست آوردیم که در ادامه هرکدام را جداگانه بررسی می کنیم.در آزمایش 1 ابعاد محیط را 10 در 10 و تعداد گره ها در محیط را برابر 50 قرار دادیم سپس میزان پوشش هر دو روش را بدست آوردیم که نتایج در جدول 1 ارائه شده است.
شرط خاتمه
براي اینکه عملیات تکامل تا ابد ادامه نداشته باشد والگوریتم خاتمه پیدا کند روشهاي مختلفی وجود دارد به عنوان مثال می توان تعداد تکرار مشخصی را تعیین کرد یااینکه تا وقتی که برازندگی به یک مقدار مشخصی نرسیده اس تکرارها انجام شود. روش دیگر این است که وقتی در چند تکرار پشت سرهم بهبودي در برازندگی راه حل ها ایجاد نشد تکرار ها خاتمه یابد. در اینجا تعداد تکرار حلقه خود را برابر با 3000 تکرار قرار داده ایم..
