بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
خوشه بندي شبکه هاي حسگر بي سيم و بهينه سازي مصرف انرژي با استفاده از
الگوريتم رقابت استعماري
چکيده
امروزه اکثر دستگاه ها مي توانند با هم ارتباط برقرار کنند و يکي از اين ارتباطات شبکه حسگر١ بي سيم مي باشد . با توجه به اينکه انرژي سنسورهاي بي سيم از طريق باتري تامين مي شود و طول عمر محدودي دارند ، تاکنون الگوريتم هاي مختلفي در جهت کاهش مصرف انرژي و افزايش طول عمر حسگرهاي بي سيم ارائه شده است . در اين مقاله با استفاده از خوشه بندي حسگرها با الگوريتم رقابت استعماري ٢، حسگرهاي بي سيم را در خوشه هاي مختلفي دسته بندي کرده و در ميان هر خوشه ٣ يکي از حسگرهاي قويتر را به عنوان سرخوشه انتخاب نموده که نحوه انتخاب سرخوشه خود عاملي مهم در بهينه کردن انرژي مصرفي و افزايش طول عمر شبکه مي باشد ، تا از طريق آن اطلعات حس شده را از ساير حسگرها دريافت و براي ايستگاه اصلي ارسال نمايد که با اين هدف مي توانيم انرژي مصرفي سنسورها و مسيريابي بين حسگرها را بهينه نماييم .
کلمات کليدي
رقابت استعماري ، خوشه بندي ، حسگر بي سيم، بهينه سازي ، بهينه سازي مصرف انرژي .
١- مقدمه
يک شبکه حسگر متشکل از تعداد زيادي گره هاي حسگري مي باشـد که در يک محيط به طور گسترده پخش شده و به جمع آوري اطلاعات از محـيط مي پردازنـد. لزومـاً مکـان قـرار گـرفتن گره هـاي حسـگر، از قبل تعيين شده و مشخص نيست . چنين خصوصيتي اين امکان را فراهم مي آورد که بتوانيم آنها را در مکان هاي خطرناک و يا غيرقابل دسترس رها کنـيم . از طـرف ديگـر ايـن بـدان معنـي اسـت کـه پروتکل هـا و الگوريتم هاي شبکه هاي حسگر بايد داراي تواناييهـاي خودسـاماندهي باشند. ديگر خصوصيت هاي منحصر به فرد شبکه هاي حسـگر، توانـايي همکاري و هماهنگي بين گره هاي حسگر است . هر گره حسگر روي برد خود داراي يک پردازشگر است و به جـاي فرسـتادن تمـامي اطلاعـات خام به مرکز يا به گره اي که مسئول پردازش و نتيجـه گيري اطلاعـات است ، ابتدا خود يک سري پردازش هاي اوليه و ساده را روي اطلاعـاتي که به دست آورده است ، انجام مي دهد و سپس داده هاي نيمه پردازش شده را ارسال مي کند.
٢- خوشه بندي حسگرها
وظيفه اصلي گره هاي شبکه حسگر، جمع آوري اطلاعـات از محيطـي است که در آن قرار مي گيرند. از آنجايي که يکـي از مهمتـرين دلايـل مصرف انرژي گره ها، انتقال داده ها مي باشد و توان ارسـال اطلاعـات بصورت بي سيم با تـوان بـالاتر مسـافت رابطـه مسـتقيم دارد، ارسـال مستقيم هر گره حسگر به ايستگاه اصلي به دليل فاصله زيـاد بعضـي از گره ها از ايستگاه اصلي باعث مصرف انرژي زيادي از گره ها مي گردد. در نتيجه طرح هايي که فاصله ارتباطي گره ها را کوتاه تر مي کنند مي توانند مصرف انرژي را در آنها کاهش داده و باعث افـزايش طـول عمـر شبکه حسگر گردند . [١]
حالت ايده آل در شبکه هاي حسگر به گونه اي اسـت کـه انـرژي محيط هاي جنگي ). در اين شبکه ها، که رايجترين مورد در کاربردهاي همه گره ها با هم به پايان برسد و لذا براي افزايش طـول عمـر شـبکه امروزي هستند، هرگره مي تواند سرخوشه باشد. بعلاوه در ايـن شـبکه سعي مي شود توزيع بار در شبکه يک توزيع يکنواخت باشد تـا فاصـله ها، نقش سرخوشه ، مي تواند بصورت دوره اي (و درجهت ايجاد تـوازن زماني بين مرگ اولين گره و مرگ آخرين گره حـداقل گـردد. جهـت بار بهتر و مصرف يکپارچه تر انرژي )، ميان گره ها تعـويض شـود.زماني نيل به اين هدف ، تاکنون پروتکل هاي ارتبـاطي متعـددي ارائـه شـده که همه گره ها قابليت هاي يکساني دارنـد(در محـيط هـاي همگـن )، است که در اين بين پروتکل هاي مبتني بر خوشه بنـدي بطـور قابـل فرايند شکل دهي خوشه و انتخـاب سرخوشـه ،بصـورت توزيـع شـده ، توجهي انرژي مصرفي شبکه را پايين مي آورد. [٢]صحيح ترين تکنيک (در راستاي کسب انعطاف پـذيري بيشـتر و زمـان خوشه بندي کردن به اين صورت است که کل شبکه به چنـدين هاي سريعتر اجرا يا همگراييِ مسـتقل از تعـداد گـره هـا) مـي باشـد.
گروه مستقل که هر کدام يک خوشه ناميده مي شوند افراز مي گردد و درمقابل ، تعداد کمي از رويکردهـا از تکنيـک هـاي متمرکـز شـده يـا هر گره در شبکه حسگر در يکي از اين خوشه ها قرار گرفتـه و يکـي از ترکيبي استفاده مي کنند که در آن ها، يک يا چند هماهنگ کننده يـا اين گره ها در هر خوشه به عنوان گره سرخوشـه انتخـاب مـي گـردد ايستگاه مبنا، مسـئول تفکيـک کـردن تمـام شـبکه بصـورت منفصـل لازم به ذکر است نحوه انتخاب گره سرخوشـه تـاثير زيـادي در بهينـه وکنترل عضويت در خوشه ها هستند. به هرحال ايـن شـبکه هـا بـراي کردن مصرف انرژي و افزايش طول عمر شبکه دارد. وظيفـه سرخوشـه کاربردهاي عملي شـبکه هـاي حسـگر بـزرگ مقيـاسِ همـه منظـوره ، اين است که تمامي اطلاعات را از گره هاي داخـل خوشـه اش جمـع مناسب نيستند (و تنها براي شبکه هـاي کوچـکِ خـاص منظـوره کـه آوري نموده و سپس اين اطلاعات را مستقيما و يا بـا اسـتفاده از سـاير کيفيت بالاي اتصال و تفکيک شبکه مورد نياز است ، کاربرد دارنـد)، در گره هاي سرخوشه به ايستگاه اصلي ارسـال مـي کنـد. بـدين ترتيـب اينجا اساسا روي پروتکل هاي خوشه بندي توزيع شده (که مخصوصا در خوشه بندي مي تواند به ميزان زيادي هزينه هاي ارتباطي اکثر گره ها شبکه هاي بزرگ کارايي بيشتري دارند)، در محيط هـاي همگـن (کـه را کاهش دهد . [٣]
٣- راه هاي مختلف دسته بندي کردن الگوريتم
گيري خوشه و پارامترهايي که در انتخاب سرخوشه استفاده مي شوند،
ها خوشه بندي
راه هاي مختلفي جهت متمـايز کـردن و سـپس دسـته بنـدي کـردن خوشه بندي مبتني بر اطلاعـات همسـايگان ، الگـوريتم هـاي خوشـه الگوريتم هاي خوشه بندي شبکه هاي حسگر بي سيم ، وجـود دارنـد. بندي مبتني بر احتمالات ، الگوريتم هاي خوشـه بنـدي الهـام گرفتـه دودسته اوليه و رايج درمراجع به صورت زير هستند:
١. الگوريتم هاي خوشه بندي در شبکه هاي همگن و الگوريتم الگوريتم هاي خوشه بندي مبتني بر سيگنال . [٥] هاي خوشه بندي در شبکه هاي ناهمگن
٢. الگوريتم هاي خوشه بندي متمرکز شـده و الگـوريتم هـاي خوشه بندي شده توزيع شده
اولين دسته ، بر پايه مشخصه و کارکرد گره هاي حسگر در خوشه است ، در حالي که ديگري براي شکل دهي خوشه دلالت دارد. در شبکه هاي حسگر ناهمگن ، درحالـت کلـي دو نـوع حسـگر وجـود دارد .نـوع اول ، حسگرهايي با قابليت هاي پردازشي بالاتر و سخت افزار پيچيده هستند که به طور کلي جهت ايجاد نوعي ستون فقرات در داخـل شـبکه هـاي حسگر، استفاده شده اند. اين حسـگرها، از قبـل بـه عنـوان گـره هـاي سرخوشه ، انتخاب شده اند. و به عنوان جمـع کننـده داده هـا و مراکـز پردازش داده هاي دريافتي از ساير گره هاي حسگر، انجام وظيفـه مـي کنند. نوع دوم ، گره هاي معمولي با قابليت هاي کمتر هسـتند کـه در واقع براي حس کردن خواص مورد نظر محيط ، استفاده مي شوند. امـا در شبکه هاي حسگر همگن ، همه گره ها، مشخصات و سـخت افـزار و قابليت هاي پردازشي يکساني دارند (مثـل گـره هـاي پخـش شـده در
٣-١- پروتکل هاي خوشه بندي در شبکه هاي همگن
در شبکه هاي همگن مي توان الگوريتم ها را به دو دسته اصلي تقسيم کرد؛ اين دسته بنـدي بـر اسـاس معيـار هـاي شـکل دهـي خوشـه و پارامترهاي استفاده شده جهت انتخاب سرخوشه ، صورت مي گيرد و به اين ترتيب ، الگوريتم هاي خوشه بندي يا احتمالاتي (تصـادفي ،ترکيبي) هستند و يا غير احتمالاتي(قطعي ).
در الگوريتم هاي خوشه بندي احتمالاتي ، جهت تعيين سرخوشـه هاي آغازين ، يک احتمال به هر گـره تخصـيص داده مـي شـود. البتـه ممکن است رويه هاي ديگري جهت انتخاب تصادفي ، برنامه ريزي شده باشند اما آنچه مسلم است اين است که تخصيص احتمـالات اوليـه بـه گره ها(مطابق هر اصولي )، اغلب ، به عنوان معيار اصلي تصـميم گيـري در مورد انتخاب سرخوشه (به کمک يک روش انعطاف پذير، يکپارچـه ، سريع و کاملا توزيع شده )، به شمار مي رود. الگورتم هاي خوشه بندي احتمالاتي ، فراتر از بازدهي انرژي بالاتر، معمولا باعث سريع شدن زمان های اجرا همگرایی وکاهش حجم پیام های تبادلی میگردد.درالگریتم های خوشه بندی غیراحتمالی اصولا معیار های قطعی ویژه بیشتری برای انتخاب سرخوشه وشکل دهی خوشه مورد توجه قرار گرفته است
، اين معيارها اساسا مبتني بر نزديکي پايــه هاي اصــلي ايــن الگــوريتم را سياســت همســان ســازي ، رقابــت و مجاورت گره ها (مثل اتصال و درجه و..) و اطلاعات دريافـت شـده از استعماري و انقلاب ٥ تشکيل مي دهند. اين الگـوريتم بـا تقليـد از رونـد گره هاي نزديک تر، انرژي باقيمانده گره ها و فاصله ، مي باشند. در اين تکامل اجتماعي ، اقتصادي و سياسي کشـورها و بـا مدلسـازي رياضـي حالت ، رويه شکل دهي خوشه ، برمبناي ارتباط گره ها با همسايگانشان بخشـهايي از ايـن فراينـد، عملگرهـايي را در قالـب مـنظم بـه صـورت است (همسايه هاي تک گامه يـا چندگامـه ) و عمومـا نيازمنـد تبـادل الگوريتم ارائه مي دهد که مي توانند به حل مسائل پيچيده بهينه سـازي فشرده تر پيام ها و در برخـي مـوارد گـراف پيمـايش اسـت ، بنـابراين کمک کنند. در واقع اين الگوريتم جواب هاي مسئله بهينه سازي را در دربعضي موارد منجر به پيچيدگي زماني بدتر نسبت به الگـوريتم هـاي قالب کشورها نگريسته و سعي مي کند در طي فراينـدي تکـرار شـونده خوشه بندي احتمالاتي .تصادفي مي گردند. در عين حال ، معمولا، ايـن اين جواب ها را رفته رفته بهبود داده و در نهايت به جواب بهينه مسئله الگوريتم ها به هنگام مواجهـه بـا وضـعيت هـاي پـيش بينـي نشـده وهمچنين در مورد توازن خوشه ها، قابل اطمينان تر هستند. عـلاوه بـر
معيار نزديکي گره ها، برخي از الگوريتم هاي غير احتمالاتي، از ترکيب معيارهاي اندازه اي (مثل انرژي باقيمانده و قدرت ارسـال ) و معيارهـاي سياري(شکل دهي خوشه بر اسـاس وزن هـاي ترکيـب شـده )، جهـت رسيدن به اهداف کلي تر نسبت به پروتکل هاي تـک معيـاره اسـتفاده مي کنند. [٥]
4- الگوريتم رقابت استعماري
اخيرا الگوريتم جديدي با نام الگوريتم رقابت استعماري ، توسط آتش پز گرگري و لوکاس در سال ٢٠٠٢ ارائه شده است که نه از پديده طبيعي بلکه از يک پديده اجتماعي سياسي الهام گرفته اسـت .الگوريتم رقابـت استعماري يک الگوريتم جديد در زمينه محاسبات تکاملي است که بـر مبناي تکامل اجتماعي سياسي انسان پايه گذاري شده اسـت . هماننـد ديگر الگوريتم هاي تکاملي ، اين الگوريتم نيز با تعدادي جمعيـت اوليـه تصادفي که هر کدام از آنها يک کشور٤ ناميده مـي شـوند، شـروع مـي شود. تعدادي از بهترين عناصر جمعيت ) معادل نخبه هـا در الگـوريتم ژنتيک ( به عنوان استعمارگر انتخـاب و باقيمانـده جمعيـت نيـز بـه عنوان مستعمره ، در نظر گرفته مي شوند. [٦]
ايـن الگـوريتم بـا مدلسـازي رياضـي فراينـد تکامـل اجتمـاعي - سياسي، الگوريتمي براي حل مسائل رياضي بهينه سازي ارائه مي دهـد از لحاظ کاربرد، اين الگوريتم در دسـته الگـوريتم هـاي بهينـه سـازي تکاملي همچون الگوريتم هاي ژنتيک ، بهينه سازي انبوه ذرات ، بهينـه سازي کلوني مورچگان ، تبريد فلزات شبيه سازي شده و ... قـرار مـي گيرد. همانند همه الگوريتم هاي قرار گرفتـه در ايـن دسـته ، الگـوريتم رقابت استعماري نيز مجموعه اوليه اي از جوابهاي احتمالي را تشـکيل مي دهد. اين جوابهاي اوليه در الگوريتم ژنتيک با عنوان کروموزوم ، در الگوريتم ازدحام ذرات با عنوان ذره و در الگوريتم رقابت استعماري نيز براي ايجاد امپراتوري جديد نیز باعنوان کشور شناخته میشودالگریتم های رقابت استعماری این جواب های اولیه کشور ها به تدریج بهبود ودرنهایت جواب مسله بهینه سازی کشور مطلوب رادراختیار میگزاردپایه های اصلی این الگریتم راسیاست همسان ساز رقابت استعماری وانقلاب تشکیل میدهداین الگریتم با تقلید روندتکاملی اجتماعی اقتصادی وسیاسی کشور هاوبا مدل سازی ریاضی بخش هایی ازاین فرایندعملگر هایی منظمی را در قالب الگریتم ارایه میدهدکه میتواند به حل مسله پیچیده بهینه سازی کمک کنند درواقع این الگریتم جواب های مسله بهینه سازی را درقالب کشور ها نگریسته وسعی میکند درطی فرایند تکرار شونده این جواب ها را بهبود دادهو درنهایت به جواب بهینه مسله برساند.
شکل-1-حرکت یک کشور مستعمره به سمت استعمارگر
برای ایجادامپراطوری جدید:
country{p1.p2......pnvar}
کدمربوط به ایجاد کشور جدید:
function newcountry =
generatenewcountry(numofcountries.problemparams)
varminmatrix=
repmat(.problemparams,varmin, numofcountries,1)
varminmatrix=
repmat(.problemparams,varmax, numofcountries,1)
new country=(varmaxmatrix-varminmatrix)
*rand(size(varminmatrix))+ varminmatrix)
end
کدمربوط به نرمالیره کردن
function xn=normalize(x,minx,maxx)
xn=(x-minx)/(maxx-minx)*2-1,
end
هزینه نرمالیزه کردن
cn=maxi{ci}-cn
قدرت نرمالیزه کردن هر امپریالیست
استعمارگر
٥- رقابت استعماري
هر امپراطوري اي که نتواند بر قدرت خود بيفزايد و قدرت رقابت خود را از دست بدهد، در جريان رقابت هاي امپرياليستي، حـذف خواهـد شـد. این حذف شدن به صورت تدریجی صورت میگیرد مرور زمان ، امپراطوري هاي ضعيف ، مستعمرات خود را از دسـت داده امپراطوري هاي قويتر برقدرت خويش مي افزايند. در الگوريتم رقابت استعماري ،، ضعيف ترين امپراطوري موجود است ، اين مسـتعمرات را تصـاحب کـرده و بـر قـدرت درصدي از قدرت کل مستعمرات آن تعريـف مي شـود. بنـابراين بـراي اين حذف شدن ، به صورت تدريجي صورت مي پذيرد. بدين معني که به هزينه کل يک امپراطوري داريم امپراطـوري در حـال احتمال انتساب اين مستعمره جديد به هر يک از استعمارگران نيز می تواند متناسب با ميزان قدرت آنها باشد.
شکل ٢ رقابت استعماري ميان چند استعمارگر را نشان مي دهد.
