بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
مسیریابی بهینه در شبکه حسگر بیسیم با استفاده از الگوریتم کرم شب تاب
چکیده:
با توجه به پیشرفتهای اخیر در زمینهی سیستمهای میکروالکترومکانیکی و تکنولوژی مخابرات بیسیم حسگرهای کوچک، ارزان قیمت و هوشمند قادرند در یک ناحیهی فیزیکی و شبکه بندی شده با استفاده از لینکهای بیسیم چیده شوند و طیف وسیعی از کاربردهای نظامی، کنترلهای طبیعی، اطلاعات مربوط به سازه ها و غیره فراهم آورند. در این نوع شبکه ها با توجه به ویژگیهای منحصر به فردی که نسبت به سیستمهای سلولی و شبکه های موردی متحرک دارند، باز هم محدودیتهای شدید در انرژی، محاسبات و حافظه وجود دارد. مسیریابی در این نوع شبکه ها به دلیل وجود تعداد زیاد گره های حسگر و مشخص نبودن ساختار صریح شبکه مشکل می باشد. از این رو در سالهای اخیر پروتکلها و الگوریتمهای متعددی برای یافتن مسیر بهینه در این نوع شبکه ها ارائه شده-اند.
در این پژوهش، تلاش شده که با بهرهگیری از قوانین شبکهی حسگر بیسیم، استقرار، موقعیتیابی و توزیع گره ها در محیط سنجش که در نرم افزار متلب، پیاده میشود را داشته باشیم. انتخاب زیر گراف مناسب به کمک نزدیکترین همسایه و بهره گیری از توپولوژی شبکهِ حسگر بیسیم ارائه میشود که مسیر بهینه را بین گره های شبکه مشخص میکند. بعلاوه، در بحث مربوط به محدودیت انرژی در شبکه، با استفاده از الگوریتم هوش ازدحامی با نام کرم شب تاب مسیرهای غلط را حذف کرده و مصرف انرژی شبکه را کاهش می-دهیم. همچنین در اینجا مسأله انتخاب کوتاهترین مسیر توسط الگوریتم کرم شب تاب و الگوریتم کلونی مورچگان حل و مقایسه شده و روش مناسبتر معرفی میگردد.
کلمات کلیدی: شبکه حسگر بیسیم - انتخاب زیر گراف مناسب- الگوریتم کرم شب تاب - الگوریتم کلونی مورچگان
.1 مقدمه
شبکه های حسگر بی سیم1، به عنوان یکی از مهمترین تکنولوژی های قرن بیت و یکم مطرح شده اند.[1] با توجه به پیشرفت های اخیر در زمینه سیستم های میکروالکترومکانیکی2 و تکنولوژی مخابرات بی سیم، حسگر های کوچک، ارزان قیمت و هوشمند قادرند در یک ناحیه فیزیکی و شبکه بندی شده با استفاده از لینک های بی سیم و اینترنت چیده شوند و فرصت های بی نظیری را برای طیف وسیعی از کاربردهای نظامی و غیرنظامی مانند مانیتورینگ محیطی، نظارت منطقه جنگی و کنترل فرآیند صنعتی فراهم آورند .[2] وجه تمایز بین شبکه های مخابرات بیسیم سنتی مانند سیستمهای سلولی و شبکه های موردی3 متحرک با شبکه حسگر بیسیم در این است که این شبکه ها ویژگیهای منحصر به فردی از قبیل سطح تراکم چیدمان گره4، عدم قابلیت اطمینان بالای گره های حسگر و محدودیتهای شدید در انرژی، محاسبات و حافظه[3] را دارند، همین امر چالش-های جدیدی را در توسعه و کاربرد شبکه حسگر بیسیم مطرح میسازد. در ده ه اخیر، شبکه حسگر بی سیم از سوی نهادهای آکادمیک و صنعتی سراسر جهان مورد توجه فراونی قرار گرفته است.
یک شبکه حسگر بیسیم، به طور معمول از تعداد زیادی گره-های حسگر ارزان قیمت چند منظوره با توان کم تشکیل شده است که در منطقه مورد نظر چیده شده اند. این گره های حسگراز نظر ابعاد کوچکند، اما به ریزپردازنده های جاسازی شده و گیرنده فرستنده های رادیویی مجهز بوده، بنابراین نه تنها از قابلیت حسگری برخوردارند، بلکه تونایی پردازش داده-ها و برقراری ارتباط را نیز دارا می باشند.
آنها در فواصل کوتاه از طریق رسانه بیسیم ارتباط برقرار کرده و برای انجام یک وظیفه مشترک مانند مانیتورینگ محیطی، مانیتورینگ منطقه جنگی و کنترل فرآیند صنعتی با یکدیگر همکاری دارند. در مقایسه با شبکه های مخابراتی بی-سیم سنتی مانند سیستم های سلولی و شبکه های موردی متحرک، شبکه های حسگر بیسیم ویژگیهای منحصر به فرد محدودیتهایی دارند:[4]
- چیدمان متراکم گره ها. گرهای حسگر معمولاً به صورت متراکم در منطقه مورد نظر چیده می شوند. تعداد گره های حسگر موجود در یک شبکه حسگر می تواند چندین برابر بیشتر از یک شبکه موردی متحرک باشد.
- تأمین انرژی گره های حسگر توسط باتری. گره های حسگر معمولاً از طریق باتری تغذیه می شوند. در اکثر مواقع گره های حسگر در محیطهای خشن و یا در مناطق جنگی چیده می-شوند، به طوری که تعویض یا شارژ مجدد باتریها مشکل و یا حتی غیر ممکن می باشد.
- محدودیتهای شدید در انرژی، محاسبات و حافظه. گره های حسگر به شدت از نظر ظرفیتهای انرژی، محاسبه و ذخیره سازی محدودند.
حسگرها میتوانند به منظور کشف و یا مانیتورینگ انواع مختلفی از پارامترها یا شرایط فیزیکی، مورد استفاده قرار گیرند[7]، به عنوان مثال پارامترهایی از قبیل:
نور
صوت
رطوبت
فشار
ترکیب خاک کیفیت آب یا هوا
صفاتی مانند اندازه، وزن، موقعیت، سرعت و جهت حسگرهای بیسیم نسبت به حسگرهای سیمی مرسوم از مزایای قابل توجهی برخوردارند.[5] حسگر های بی سیم نه تنها باعث کاهش هزینه و تأخیر در چیدمان می شوند، بلکه برای هر محیطی خصوصاً محیط هایی که استفاده از شبکه های حسگر مرسوم در آن ها غیرممکن است، مانند زمین های غیرقابل سکونت، مناطق جنگی، فضای خارج از جو زمین و یا اقیانوس های عمیق، به کار می روند. مِین وارینگ5 و همکارانش [6]، از دانشگاه کالیفرنیا در بر کلی و کالج آتلانتیک در برهابرور چیدمان 190 حسگر بی سیم شامل حسگرهای آزمایشی رطوبت، فشار، درجه حرارت و شدت نور را جهت مانیتورینگ زیستگاه پرندگان آشیانه ساز بر روی زمینهای گریت داک انجام داده اند.
آقای دکتر قسوری و همکاران در سال [7]، انتخاب زیر گراف بهینه را در شبکه های کدگذاری شده با تأخیر و با فرینگ با اندازه محدود ارائه کردند.
در این مقاله، مسأله یافتن زیر گراف چند بخشی1 با هزینه حداقل را بر مبنای کدگذاری شبکه در نظر گرفتهاند که در آن مقادیر تأخیر مرتبط با هر لینک، اندازه بافره حدود گره های واسط و تغییرات ظرفیت لینک با گذشت زمان به شمار آورده اند.
ایدهای که ما از این مقاله میگیریم این است، که با انتخاب زیرگراف مناسب به کمک نزدیکترین همسایه مسیر بهینه را بین گره های شبکه مشخص می کنیم. که در فصل سوم، توضیحات کامل آورده شده است.
آقای جمال ال کاراکی و همکاران در سال [8] ، تکنیکهای مسیریابی در شبکه های حسگر بی سیم را بررسی کردند. پروتکلهای مسیریابی2 در شبکه های حسگر بی سیم، ممکن است بسته به کاربرد و معماری شبکه متفاوت باشد. کاری که در این مقاله انجام شده، این است که تکنیک های مسیریابی حسگر در سه رده طبقه بندی شده و این طبقه بندی بر اساس ساختار شبکه متضمن است : مسیر یابی تغییر مکان، سلسله مراتبی و مبتنی بر مکان.
مسیریابی در شبکه های حسگر بیسیم بسیار چالش برانگیز است و این به دلیل مشخصه های اصلی است که بین این شبکه ها از دیگر شبکه های بی سیم نظیر شبکه های موردی متحرک یا شبکه های سلولی تفاوت قائل می شود.
به دلیل تعداد نسبتاً زیاد گره های حسگر، ساختن یک شمای کنترل کلی برای انتشار تعداد زیادی از گره های حسگر ممکن نیست چون سربار حفظ شناسه بالاست. از اینرو، پروتکلهای مبتنی بر IP مرسوم ممکن نیست که به شبکه-های حسگر بیسیم اعمال شوند. به علاوه، گره های حسگری که به شیوهی موردی پراکنده شده اند باید خود سازمان ده باشند چون انتشار موردی این گره ها مستلزم این است که سیستم ارتباطاتی تشکیل دهد و از عهده ی توزیع گرهای منتجه بر آید، خصوصاً به این دلیل که عملیات شبکه های حسگر غیر قابل حصول است. در شبکه های حسگر بیسیم، گاهی اوقات گرفتن داده ها مهم تر از دانستن شناسه های گره-هایی است که داده ها از آنها ارسال شده اند.
در مقابل شبکهای ارتباطی معمول، تقریباً تمام کاربردهای شبکه های حسگر مستلزم جریان یافتن داده های حس شده از چندین منبع به یک ایستگاه پایه معین است. اما این موضوع از جریان یافتن داده ها به شکل دیگر جلوگیری نمی کند.
گره های حسگر از نظر انرژی، قابلیت پردازش و ذخیره بسیار محدودند. از این رو، به مدیریت منبع دقیق نیاز دارند. مشکل ردیابی شعاع متحرک ابتدا در عملیات نظامی طی جنگ جهانی دوم بوجود آمده جایی که مکان یابی سربازان در موقعیت های حاد و سخت مسئله ای حیاتی بود10]،.[9 حدود 20 سال بعد در طی جنگ ویتنام وزارت دفاع آمریکا یک سری از ماهواره های دارای سیستم مکان یابی جهانی را برای حمایت از عملیات های نظامی در نواحی مورد منازعه در مدار زمین قرارداد.در سال 1990سیگنال های ماهواره ای برای بخش خصوصی نیز به لحاظ کا ربرد های تجاری مثلا مدیریت ناوگان ها نقشه های راهبر و کمک های اولیه و حیاتی، قابل استفاده و دسترسی اعلام شدند.
علیرغم موفقیت این سیستم، دقت سیستم مکان یابی جهانی بطور مشهودی در نواحی شهری و مسقف و داخل مکان ها به علت ناتوانی در دریافت سیگنال ها و بلوکه شدن یا اثرات چند بار ارسال شدن آن ها کاهش می یابددر سال 1996کمسیون ارتباطی فدرال قوانینی را برای شرکت های ارائه دهنده شبکه های بی سیم تنظیم نمود هدف از تعریف این قوانین ایجاد قابلیت مکان یابی موارد متحرک در موقعیت های حیاتی با دقت خاصی 100)متر دقت در 0/067موارد زمانی)بود. چنین سرویس مهمی را E-911 در کشور آمریکا و E-112در دیگر کشورها نامگذاری نمودند. با ظهور متقابل شبکه های محلی بی سیم،کمسیون ارتباط فدرال به خدمات E-911 درمورد افزایش سرعت پیشرفت صنعت بی سیم مرتبط با موارد جغرافیایی، هشداری جدی داد. همزمان فناوریهای زیادی به منظور پیاده سازی شامل تکنیک کمکی سیستم مکان یابی جهانی انواع متنوعی از تکنیکهای زمان رسیدن1، زاویه ورود2 قدرت سیگنال در یافتی3 ارائه شدند تعداد زیادی از تکنیک های و تفاضل زمانی4، یا بسط تفاضل زمانی5، نیازمند سخت افراز سنجش و مکان یابی خاص کالیبره و اصلاح شده مستقر در پایگاه های اصلی هستند و حتی در برخی موارد همزمان سازی دقیق میان ترمینالهای متحرک و ایستگاه های مزبور (کار برد های تلفن همراه)می باشند. برخلاف روشهای فوق سیستمهای یک راه حل کم هزینه تر را فراهم می آورند بکارگیری این سیستمها می تواند باعث عدم استفاده از نصف سخت افزارهای اضافی گردد ولی نیاز مند عملکردهای آموزشی مشارکتی در داخل سیستم می باشد.
در بخش دوم الگوریتمهای مبتنی بر هوش جمعی و مفهوم بهینه سازی توضیح داده میشود، در بخش سوم روشهای پیادهسازی و در بخش چهارم مقایسهی دو الگوریتم کرم شب تاب و کلونی مورچگان در حل مسئله انتخاب کوتاهترین مسیر
و در بخش آخر نتایج را میآوریم.
.2 الگوریتم بهینه سازی مبتنی بر هوش جمعی6
بهینه سازی، یکی از حوزه های تحقیقاتی مهم در ده ه های اخیر بوده است که نتیجه آن طراحی انواع مختلفی از الگوریتم ها بوده است. در بسیاری از مسائل مهندسیمعمولاً با تابع هدفی روبه رو هستیم که میخواهیم آن را بهینه کنیم .در روشهای گروهی، عاملها با هم همکاری مینمایند و رفتار جمعی تمام عاملها باعث یک همگرایی میشود .حال روش های گوناگونی برای رسیدن به این نقطه بهینه وجود دارد که مسلما هر کدام از این روش ها معایبی دارند. مفهوم بهینه سازی بدین صورت است که در بین پارامترهای یک تابع به دنبال مقادیری باشیم که تابع را کمینه یا بیشینه نماید. کلیه مقادیر مناسب جهت این امر را، راه حل های ممکن و بهترین مقدار از این مقادیر را، راه حل بهینه می نامند. الگوریتمهای بهینه سازی هر دو نوع مسائل بیشینه سازی و کمینه سازی را پوشش میدهند. بهینه سازی کاربردهای زیادی در زمینه تخصیص منابع، زمان بندی ها، تصمیم گیری ها و ... را دارد. بهینه سازی همواره با مشکلات فراوانی همراه بوده است. شیوه های سابق برای حل کردن مشکلات بهینه سازی، مستلزم تلاش های محاسباتی بیشماری می باشد. الگوریتم هایی از جمله الگوریتم های هوش جمعی تا حدی این مشکل را حل نموده اند. توسط این الگوریتم ها راه حل هایی پیدا می شوند که تقریبا به جواب نزدیکند .
هوش جمعی نوعی روش هوش مصنوعی7 ، مبتنی بر رفتارهای جمعی می باشد. عاملها، به طور محلی با یکدیگر و با محیط خود در تعامل هستند.
موفق ترین روشهای هوش جمعی که تاکنون به وجود آمده اند، روش بهینه سازی کلونی مورچه 8 ها ، روش بهینه سازی اجتماع ذرات 9 ، روش بهینه سازی زنبور عسل 10 و روش بهینه سازی کرم شب تاب 11می باشد.[11]
الگوریتم کرم شب تاب
الگوریتم کرم شب تاب عنوان الگوریتم ذهنی مبتنی بر ازدحام ، برای وظایف بهینه سازی محدود، توسط یانگ در سال 2007 در دانشگاه کمبریج ارائه شد و کتابی در سال 2010 به عنوان بهینه سازی مهندسی ارائه کردند. در این الگوریتم از رفتار تابشی کرم های شب تاب الهام گرفته شده است. این الگوریتم یک رویه تکراری مبتنی بر جمعیت را با عوامل بیشمار ( تحت عنوان کرم های شب تاب ) به کار می-گیرد.
الگوریتم کرم شب تاب دارای سه قانون خاص می باشد که مبتنی بر برخی ویژگی های کرم های شب تاب واقعی است. این سه قانون عبارتند از:
تمامی کرم های شب تاب دو جنسیتی هستند و آنها صرف نظر از جنسیت خود به صورت جذاب تر و شفاف تری حرکت خواهند کرد.
درجه جذابیت یک کرم شب تاب با درخشش آن متناسب است .همچنین ممکن است درخشندگی با افزایش فاصله از کرم های شب تاب دیگر کاهش یابد. حال اگر یک کرم شب تاب جذاب تر یا شفاف تری نسبت به این کرم وجود نداشته باشد، آنگاه به صورت تصادفی حرکت خواهد کرد.
درخشندگی یا شدت نور یک کرم شب تاب، توسط مقدار تابع هدف مشخص می شود.
این الگوریتم مبتنی بر برقراری ارتباط سراسری میان ذرات می باشد . بنابراین در بهینه سازی چند هدفی کارآمد تر و موثرتر است.[12]
سادگی، فرض همیشه بر این اساس است که جذابیت کرم شب تاب، توسط روشنایی آن تعیین میشود که به نوبه خود با تابع هدف کدگذاری، همراه است.
جهت حداکثر بهینه سازی مسائل، روشنایی با متغیر I برای کرم شب تاب در موقعیت ویژه x به عنوان انتخاب می شود. جذابیت β یک نقطه مشترک است که توسط چشم دیگر کرمهای شب تاب دیده می شود. بنابراین تفاوتی بین فاصله Rij بین کرم شب تاب i و j به وجود خواهد آمد. قابل ذکر است که شدت نور با فاصله از منابع خودش، کاهش پیدا می کند. در ساده ترین حالت، شدت نور I(r) با توجه به قانون معکوس مربع، متفاوت است و به صورت رابطه زیر تعریف میشود:
که در آن Is شدت در منبع است. یک ضریب جذب نور ثابت با متغیر γ در نظر گرفته شده است که شدت روشنایی I با فاصله r متفاوت است که رابطه آن به صورت رابطه زیر تعریف میشود:
که در آن I0 شدت روشنایی اصلی است.
فاصله بین دو کرم شب تاب i و j در XiوXj در حالت دو بُعدی به صورت رابطه زیر تعریف میشود:
الگوریتم کلونی مورچگان
این روش که از رفتار مورچه ها در یافتن مسیر بین حل لانه و غذا الهام گرفته شده، اولین بار در سال 1992 توسط مارکو دوریگو1 در پایان نامهی دکترایش مطرح شد.
الگوریتم کلونی مورچه ها الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه ها حشراتی اجتماعی هستند که در کلونیها زندگی میکنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا در جهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه ها دارای نوعی هوشمندی تودهای است که اخیرا مورد توجه دانشمندان قرار گرفته است.[13]
در دنیای واقعی مورچه ها ابتدا به طور تصادفی به این سو و آن سو میروند تا غذا بیابند، سپس به لانه بر میگردند و ردی از فرومون2 به جا میگذارند. چنین ردهایی پس از باران به رنگ سفید در میآیند و قابل رؤیتاند. مورچه های دیگر وقتی این مسیر را مییابند، گاه پرسه زدن را رها کرده و آن را دنبال میکنند، سپس اگر به غذا برسند به خانه برمیگردند و ردی از خود در کنار رد قبل میگذارند و به عبارتی مسیر قبل را تقویت میکنند. فرومون به مرور تبخیر میشود که از سه جهت مفید است:[14]
باعث میشود مسیر جذابیت کمتری برای مورچه های بعدی داشته باشد.
از آنجا که یک مورچه در زمان طولانی راه های کوتاهتر را بیشتر میپیماید و تقویت میکند هر راهی بین خانه و غذا که کوتاهتر باشد بیشتر تقویت میشود و آن که دورتر است کمتر.
اگر فرومون اصلا تبخیر نمیشد، مسیرهایی که چند بار طی میشدند، چنان بیش از حد جذاب میشدند که جستجوی تصادفی برای غذا را بسیار محدود میکردند.
وقتی غذا انتهای یک مسیر جذاب تمام میشد رد باقی میماند.
یک گراف G(V , L) مجموعهای از رأسها به صورت V {v 1,v 2 , ...,v n } و یالها به صورت تعریف میشود.[23]
تابع هزینه یا در واقع مسیر بین گرهی i ام و j ام به صورت زیر تعریف میشود:
احتمال انتخاب گرهی j ام توسط مورچهی k ام که در گرهی i میباشد به صورت زیر تعریف میشود:
k
مجموعه ی گره هایی که همسایه گرهی i هستند.
اعضایی از Ni که توسط مورچه k ام ویزیت نشدهاند.(مجموعه گره های قابل انتخاب).
مسیرهای طی شده توسط مورچه k ام.
مقدار کل فرومونی است که روی مسیر ij توسط همه ی مورچه ها ریخته شده است.
عملکرد وزنی دارد و نسبت آنها برای ما مهم است و مقدار مطلق آنها برای ما مهم نیست.
اگر باشد در واقع به تجربه و دانش جمعی اهمیت دادهایم، حال اگر سعی میکنیم حریصانه عمل
کنیم. ( اطلاعاتی که در مورد مسئله داریم برای ما معتبرتر است).
با توجه به مسئله ی هوش ازدحامی در الگویتم مورچگان که مبتنی بر مقدار فرومون ریخته شده در مسیر است، معمولا
