بخشی از مقاله
بهبود پروتکل مسیریابی WRP با استفاده از الگوریتم یادگیری ماشین
چکیده - در یک شبکه موردی سیار تمامی نودها متحرک میباشند و به صورت پویا و با یک روش دلخواه ارتباطات را برقرار میکنند. در این نوع شبکه تمامی نودها به عنوان مسیریاب عمل کرده و در کشف و نگهداری مسیر به سایر نودها دخیل میباشند، بنابراین دانستن مدل تحرک نودها در ارزیابی کارایی آن بسیار مهم است. با توجه به اینکه در دنیای واقعی همیشه مدل تحرک نودها در دسترس نمی باشد و یا اینکه ممکن است مدل تحرک شبکه با گذشت زمان تغییر کند، لذا می توان با استفاده از الگوریتم هایی این مدل تحرک را تخمین زد و از این تخمین در مسیریابی ها استفاده نمود. در این مقاله پروتکل WRP توضیح داده شده و سپس با استفاده از الگوریتم یادگیری Q آنرا بهبود داده ایم.
کلمات کلیدی: الگوریتم های یادگیری ماشین، پروتکل مسیریابی، پروتکل WRP، شبکه های موردی سیار
1 مقدمه
شــبکههــای مــوردی ســیار( MANET هــا) گروهــی از کامپیوترهای بیسیم به شکل یک شبکه ارتباطی میباشـند کـه ساختار از پیش تعیین شدهایی ندارند. اداره و پیکربندی این نوع شبکهها به هیچ کاربر خاصی وابسـته نیسـت، بـه عبـارت دیگـر شبکهبندی مـوردی اجـازه مـیدهـد یـک مجموعـه خودمختـار تشکیل شود. سناریوهای بیشماری وجود دارند که یک شبکه بـا ساختار و پیکربندی ثابت نمـیتوانـد جوابگـوی آنهـا باشـد و بـه شبکهایی ماننـد شـبکه مـوردی نیـاز دارنـد ماننـد مأموریتهـای نظــامی، عملیاتهــای اورژانــس ، پــروژههــای تجــاری و بازرگــانی، کلاسهای آموزشی و غیره. به همین دلیل در سالهای اخیر توجـه زیادی به شبکههای موردی شده است. مشکلات زیادی در ایجاد یک شبکه مـوردی وجـود دارد از قبیـل مسـیریابی، رسـانههـای بیسیم ، قابلیت حمل و نقل. اگر چه این شبکهها در ابتـدا بـرای گروه کوچکی از نودهای همکـار تشـکیل شـده بودنـد ولـی هـم اکنون گروههای بزرگی بر روی نواحی جغرافیـایی وسـیع از ایـن شبکهها به خوبی استفاده میکنند. بنابراین مقیاسپـذیری یکـی دیگر از مشکلاتی است که در ایجاد این نوع شبکه وجود دارد. از اینرو دستگاههای محاسبات متحرک از لحاظ قابلیت حمل و نقل و شــکل شــبکه در رشــد شــبکههای مــوردی بســیار مناســب هستند1]و.[2
از مشکلات اساسی این شبکهها مسیریابی در آنهـا میباشـد، بـه علت متحرک بودن نودها نمیتوان از پروتکلهـای شـبکههـای بـا ساختار استفاده نمود. پروتکلهای مسیریابی در این شبکهها به دو دسته کلی بر حسب نیاز ٌ و مبتی بر جدولٍ تقسیم میشوند که اختلاف اساسی آنها در اطلاعات نگهداری شده و همچنین نحـوه
ارسـال ایــن اطلاعـات میباشــد. پارامترهـای زیــادی بـر کــارایی پروتکــل هــای مســیریابی اثــر دارنــد و یکــی از مــوثرترین ایــن پارامترها، مدل تحرک شبکه می باشد. مدل تحرک شبکه شـامل اطلاعاتی مانند سرعت، شتاب و جهـت حرکـت هـر گـره در هـر لحظه از زمان است.
هدف از این مقاله بهبود پروتکل [3] WRP با استفاده از الگوریتم یادگیری[4] Q میباشد که این پروتکل بهبود یافته را َQLWRP می نامیم. پروتکل های WRP و QLWRP هر دو پروتکل های مسیریابی برای شبکه موردی هستند به این صورت که WRP در ماشین های عادی و QLWRP در ماشین هایی با قابلیت یادگیری استفاده میشود. ابزار مورد استفاده برای این کار NS2 میباشد که این نرم افزار شامل پیادهسازی استاندارد برای پروتکل WRP است که بر اساس آن پروتکل QLWRP پیادهسازی شده است.
نسخه جدید QLWRP اجازه میدهد که نود مبدا مسیر حرکت نود مقصد را تخمین زده و اطلاعات مسیریابی را فقط برای نودهای لازم ارسال نماید. در مجموع، چندین عمل در این پروتکل جدید بهبود یافته و در نتیجه باعث بهبود پروتکل WRP شده است.
ساختار ادامه مقاله به این صورت است که : بخش 2 به بررسی پروتکل WRP می پردازد و بخش های 3 و 4 نیز به ترتیب مروری بر مدلهای تحرک و الگوریتم های یادگیری ماشین دارند، در بخش 5 روش پیشنهادی توضیح داده شده و در بخش 6 نتایج حاصل از شبیه سازی مطرح می شود.
2 پروتکل ُWRP
پروتکل WRP یک پروتکل مسیریابی در دسته پروتکل های مبتنی بر جدول و وابسته به بردار فاصله میباشـد. هـر نـود در شبکه یک جدول فاصله، یک جدول مسـیریابی، یـک جـدول هزینه پیوند و یک لیست ارسـال مجـدد پیغـام را نگـه مـیدارد. جدول فاصله برای هر نود ماننـد x شـامل فاصـله x تـا هـر نـود مقصدی مانند y که از طریق همسایههایش مانند z میتوانـد بـه آنها برسد میباشد 1]و.[2 جدول مسیریابی بـرای نـود x شـامل مسیر بهینه هر نود مقصد مانند y تا نود x مـیباشـد، همچنـین یک برچسب برای شناسایی مسیر دارد کـه توسـط آن مـیتـوان یک مسیر ساده یا یک حلقه و یا یک مسـیر اشـتباه را تشـخیص داد. نگهداری فواصـل قبلـی و گذشـته در تشـخیص حلقـههـا و اجتناب از شمارش تا بینهایت بسیار مفیـد و سـودمند هسـتند. جدول هزینه پیوند، هزینه هر نود تا همسایههایش و زمان انتظار معتبر آنها میباشد. لیست ارسـال مجـدد پیغـام (MRL) شـامل اطلاعاتی است که یک نود به وسیله آنها میتواند بفهمد که کدام همسایهاش پیغام بهروزآوری را دریافت نکرده است و مجبـور بـه ارسال مجدد این پیغام به او شده است.
نودها جداول مسیریابی خودشان را بر اساس پیغامهای متناوب مسیریابی یا به عبارت دیگر بر اساس تغییرات پیونـد، بـا همسایههایشان مبادله میکنند و یک لیست پاسخگویی به پیغام بهروزآوری را ارائه میدهند که این کار با استفاده از فرمت MRL میباشد. این لیست شامل نودهایی است که تصدیق این پیغام را ارسال کردهاند. اگر بعد از آخرین بهروزرسـانی هـیچ تغییـری در جدول مسیریابی ایجاد نشده باشد، نود فقـط یـک پیغـام Hello برای اطمینان از برقراری ارتباط میفرستد. هنگام دریافـت یـک پیغام بـهروزآوری ، نـود جـدول فاصـله خـودش را بـرای یـافتن بهترین مسیر با استفاده از اطلاعات جدیـد اصـلاح میکنـد. هـر مسیر جدیدی که پیدا میشود برای نودهای اصلی هـم فرسـتاده میشود تا آنها هم بتوانند جداولشان را بهروزآوری کننـد. نودهـا همچنین جداول مسیریابیشان را اگر که مسیر جدید پیدا شـده از مسیر موجود بهتر باشد، بهروزرسـانی میکننـد. یـک خصـلت منحصر به فرد این الگوریتم این است که سازگاری تمام نودهـای همسایه را هنگامی که یک تغییر در پیوند هر کدام از همسـایهها اتفاق بیفتد ، چک میکند. چک کردن سـازگاری در ایـن روش، در برطرف کردن ایجاد حلقه و سرعت بخشیدن در همگرا شـدن مسیر کمک زیادی میکند.
-3 مروری بر مدل های تحرک
مدل های تحرک به دو دسته تقسیم می شوند کـه شـامل مـدل های تحرک مستقل و مدلهای تحرک گروهی می باشـند.[3] در مدل های تحرک مستقل، حرکت یـک گـره مسـتقل از حرکـت سایر گره ها می باشد. مدل های تحرک گردش تصـادفی، RWP، جهت تصادفی، گاوس-مارکف و ... در این دسته قرار می گیرنـد. در مقابل، در مدل هـای تحـرک گروهـی حرکـت یـک گـره بـه حرکت یک یا چند گره دیگر در شبکه بستگی دارد. از مهمتـرین مدل های تحرک موجود در این دسته می تـوان بـه مـدل هـای تحرک بزرگـراه، منهـتن، RPGM ، سـتونی و ... اشـاره کـرد. در ادامه این بخش سه نوع مدل تحرکی که در اکثر شبیه سازی هـا از آنها استفاده می شود را مورد بررسی قرار می دهیم.
- مدل تحرک : RWP در هر لحظه، یک گره به صورت تصادفی یک مقصد انتخاب می کند و بـا یـک سـرعت تصادفی و بدون شتاب که با توزیـع یکنواخـت از بـازه
[0,Vmax] انتخاب شده است، به سمت آن حرکت می کند.[5]
- مدل : RPGM گره ها تشکیل یـک یـا چنـد گـروه را می دهند که در هر گروه یک گره به عنوان رهبر گروه انتخــاب مــی شــود. در ابتــدا اعضــای گــروه بــه طــور یکنواخت در همسایگی رهبـر گـروه قـرار مـی گیرنـد. سپس در هر لحظه، هر گره سرعت و جهت خـود را بـا کمی انحراف تصادفی از رهبر گروه اختیار می کند.[2]
- مدل تحرک بزرگراه: کاربرد اصلی این روش ردگیری اتومبیل ها در یک بزرگراه مـی باشـد. طبیعتـا تفـاوت های مهمی بین این روش و دو روش قبلی وجـود دارد که ناشی از قوانین حاکم بر بزرگراه ها می باشد.[6]
-4 مرورری بر روش های یادگیری ماشین
قبل از هر چیزی باید تعریف دقیقی از یـادگیری ارائـه شـود. بـه طور کلی اگر یک آزمایش را بـا E ، مجموعـه کارهـایی کـه یـک برنامه کامپیوتری می تواند انجـام دهـد را بـا S و معیـار ارزیـابی کارایی برنامه را با P نشان دهیم، آنگاه یادگیری بـه صـورت زیـر تعریف می شود:
تعریف: اگر کـارایی یـک برنامـه کـامپیوتری (P) هنگـام اجـرای کاری از مجموعه S بـا اسـتفاده از آزمـایش E بهبـود یابـد آنگـاه گوییم که این برنامه یک یادگیر است. به عبارت دیگـر یـادگیری ماشین عبارت است از اینکه چگونه میتوان برنامه ای نوشت که از طریق تجربه یادگیری کرده و عملکرد خود را بهتر کند. یادگیری ممکن است باعث تغییر در ساختار برنامه و یا داده ها شود.
هدف اصـلی الگـوریتم هـای یـادگیری ماشـین (ML)، آمـوزش اتوماتیک مشخصه های محیط و رفتارهای آن به صورت سریع و آسان به عوامل محیط می باشد. برخـی مشخصـه هـای مختلـف شــبکه هــای مــوردی ســیار شــامل: حافظــه، محــدودیت هــای محاسباتی، هزینه های ارتباطی، انـرژی باقیمانـده مـی باشـد. از سوی دیگر، تعداد زیادی تکنیک یادگیری ماشین وجود دارد کـه برای شبکه ها کاربرد دارند و با استفاده از مشخصه های مختلـف شبکه های موردی سیار می توان یک روش ML مناسب انتخاب نمود. از این مشخصه ها می توان طبیعـت غیـر ایسـتا، تغییـرات توپولوژی و تحرک، محدودیت انرژی و توزیع فیزیکی را نام بـرد. در بخش های زیر یک بررسـی اجمـالی از برخـی پرکـاربردترین تکنیک های ML آورده شده است4]و7و.[8
-1-4 درختهای تصمیم گیری
درختهای تصمیم گیـری یکـی از ابزارهـای قدرتمنـد و مشـهور هستند. درخت تصمیم گیری ساختمان داده ای اسـت کـه مـی تواند برای تقسیم یک مجموعه بزرگ از رکورد هـا بـه مجموعـه های کوچکتر رکوردها مورد استفاده قـرار گیرنـد. درخـت هـای تصمیم این کار را بـا اسـتفاده از یـک سـری سـوالات و قـوانین تصمیم گیری بسیار ساده ای انجام می دهد . با هـر بـار تقسـیم موفق، اعضایی که در یک مجموعه قرار می گیرند بیشتر و بیشتر به یکدیگر شبیه می شوند .
به عنوان یک شمای کلی از یک درخت تصمیم می توان آنرا یک ساختار سلسله مراتبی در نظر گرفت که در آن، گرههـای میـانی برای تست یک خصیصـه بـه کـار مـی رونـد. شـاخههـا نشـانگر خروجی تست بوده، برگها برچسب کلاس و یا توزیع بـر چسـب کلاس را مشخص مینمایند.[8]
-2-4 شبکه های عصبی
یــک شــبکه عصــبی مصــنوعی ( Artificial Neural Network ((ANN) ایده ای است برای پـردازش اطلاعـات کـه از سیسـتم عصبی زیستی الهام گرفته شده و مانند مغز به پردازش اطلاعـات می پردازد . عنصر کلیـدی ایـن ایـده ، سـاختار جدیـد سیسـتم پردازش اطلاعـات اسـت. ایـن سیسـتم از شـمار زیـادی عناصـر پردازشی فوق العاده بهم پیوسته تشکیل شده((neuronsکه بـرای حل یک مسأله با هم هماهنگ عمل می کنـد. ANN هـا، نظیـر انسانها، با مثال یاد می گیرند. یک ANN برای انجـام وظیفـه ای مشخص ، مانند شناسایی الگو ها و دسـته بنـدی اطلاعـات ، در طول یک پروسه یاد گیری ، تنظیم می شود .[8]
بوسیله کامپیوترها با هزینه کم امکان پذیر شد. منطق محاسباتی به صورت کلی به منطق از دید محاسباتی آن می نگرد، بـه ایـن صورت که در یک دستگاه منطقی انجام یک محاسـبه (بـه طـور مثال چک کردن درستی یک گزاره) امکان پذیر هسـت یـا نـه و اگر امکان پذیر است ایـن کـار چـه هزینـه ای دارد. از آنجـا کـه حقایق علمی ما با منطق پیوند عمیقی دارند، بـرای بررسـی ایـن حقایق استفاده از زبان منطقی، یکی از بهتـرین راه هـای ممکـن است. روش کلی برای فهمیدن درستی یک جمله این است که از فرضها شروع کرده و در هر مرحله یک جمله درست جدیـد را بـا توجه به جملات قبلی و استفاده از قواعد اسـتنتاج تولیـد کنـیم. این کار ادامه پیدا می کند تا وقتی که به جمله مـورد سـوال یـا نقیض آن برسیم.
-4-4 محاسبات تکاملی ( الگوریتم ژنتیک )
مختصراًگفته می شود که الگوریتم ژنتیک (یـا (GA یـک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنـوان یک الگوی حل مسئله استفاده می کند. مسئله ای که باید حل شود ورودی است و راه حلها طبق یک الگو کد گذاری می شود و متریک که تابع fitness هم نام دارد هر راه حل کاندید را ارزیابی می کند که اکثر آنها به صـورت تصـادفی انتخاب می شوند. کلا این الگوریتم ها از بخش هـای تـابع برازش، انتخاب، جابجایی و جهش تشکیل می شوند.
-3-4 یــادگیری از طریــق منطــق محاســباتی
(Computational Learning)
منطق محاسباتی بخشی از منطق است که به بررسی راهکارهـای مختلف بررسی درستی احکام در دسـتگاههای مختلـف منطقـی می پردازد. این رشته به طور عمیقی با علوم کامپیوتر پیوند یافته است و به صورت کلی رشد واقعی آن از وقتی شروع شد که توان محاسباتی کامپیوترها پیشرفت کرد و انجـام محاسـبات پیچیـدهearning) وقتی از یادگیری صحبت می کنیم، معمول ترین روشی کـه به نظر می رسد، یـادگیری بـه وسـیله تعامـل بـا محـیط اسـت. بنابراین طبیعی به نظر می رسد که یادگیری با استفاده از تعامل با محیط یکی از ایده های اساسی مباحـث مربـوط بـه یـادگیری ماشین و هوش مصنوعی باشد. یادگیری تقویتی روشی است کـه از این ویژگی بـه عنـوان اسـاس و پایـه تئـوری یـادگیری خـوداستفاده می کند. یادگیری تقویتی یکـی از روش هـای یـادگیری ماشـین اسـت کــه مسـاله آن یـادگیری عــاملی اسـت کــه از راه آزمایش و خطا و در تعامل با یک محیط پویا رفتاری را فـرا مـی گیرد4]و7و.[8
یادگیری تقویتی روش های گوناگونی دارد که مطـرح تـرین این روش ها، روش های اختلاف زمانی می باشد. الگوریتم هـایی که برای یادگیری تقویتی بکار می روند تحت عنوان کلی فراینـدتصمیم گیری مـاکوف (Markove decision Process) شـناخته می شوند. خروجی این الگوریتم ها هر فعالیت در هر موقعیت را تنها وابسته به همان فعالیت در همان موقعیت مورد بررسی قرار می دهند ( بدون وابسته سازی آن به فعالیت ها و موقعیت هـای پیشین). از جمله مسائلی که این الگوریتم ها پوشش می دهنـد می توان به بسیاری از کنترل گرهای ربـات هـا ، کارخانـه هـای اتوماتیک و مسائل اختلاف زمانی اشاره کرد.
یکی از انواع یادگیری تقویتی، یـادگیری ( Q Learning ) Q است که در آن، عامل بر اساس عمل و موقعیت، یک تابع ارزیابی را یاد می گیرد. به طور دقیق تر می توان گفت که تـابع ارزیـابی Q(s,a) به عنوان تابع بدست آوردن ماکزیمم پاسخ مـورد انتظـار که عامل می توانسته با انجام عمل a در موقعیت s بدسـت آورد، تعریف می شود. الگوریتم Q learning این امتیاز را دارد که مـی توانــد حتــی در صــورتی کــه عامــل هــیچ گونــه دانــش قبلــی از چگونچگی تاثیر عمل بر محیط نداشته باشد، نیز مـورد اسـتفاده قرار گیرد.
-5 روش پیشنهادی
در این قسمت به توصیف روش پیشنهادی برای تخمین مدل حرکت و بهبود پروتکل WRP در شبکه موردی سیار می پردازیم. الگوریتم یادگیری که جهت بهبود پروتکل و تخمین مدل حرکت استفاده شده است ، الگوریتم یادگیری Q می باشد.
در این روش فرض بر این است که مدل تحرک شبکه موردی سیار مدل RWP است و هر نود واقع در شبکه به عنوان یک عامل یادگیرنده عمل می کند؛ ضمنا الگوریتم هیچگونه دانش قبلی مبنی بر ارتباط میان مدل های تحرک و پارامترهای دریافت شده از شبیه سازی شبکه موردی سیار ندارد . در تحلیل مدل های تحرک شبکه های موردی سیار، دو معیار مهم وجود دارد که شامل درجه وابستگی مکانی و سرعت نسبی می باشد. معیار درجه وابستگی مکانی میزان شباهت میان بردارهای سرعت دو گره مختلف، که خیلی از هم دور نیستند را نشان می دهد و معیار سرعت نسبی نیز برای دو گره در یک لحظه خاص تعریف می شود.[9]
روش کار به این صورت است که برای هر نود واقع در شبکه موردی سیار علاوه بر اطلاعات مذکور در بخش 2 اطلاعات زیر نیز اضافه می گردد:
