بخشی از مقاله
چکیده:
براي پروتکلهاي سلسله مراتبی مکانیزمهاي مختلفی براي
ارتباط سرخوشه با اعضاء خوشه پیشنهاد شده است. مکانموردیزمهاي استفاده بدون توجه به شرایط گرهها به هر یک از اعضاء خوشه، زمان یکسانی براي ارتباط با سرخوشه میدهند. در این مقاله یک مکانیزم زمانبندي بر اساس اتوماتاهاي یادگیر که آنراLASM مینامیم براي ارتباط اعضاي یک خوشه با سرخوشه پیشنهاد میگردد. در این روش هر سرخوشه به یک اتوماتاي یادگیر مجهز است که وظیفه زمانبندي براي ارتباط سرخوشه با اعضاي خوشه را بر عهده دارد. اتوماتاي یادگیر به مرور زمان یاد میگیرد که براي اعضایی از خوشهاطلاعاتکه داراي بیشتري براي ارسال میباشند شانس بیشتري را براي ارتباط با سرخوشه فراهم کند. به منظور ارزیابی، پروتکل LEACH که در آن مکانیزم زمانبندي پیشنهادي به کار گرفته شده است (LEACHLASM)
و پروتکل LEACH که از مکانیزم زمانبندي TDMA استفاده میکند (LEACHTDMA) با استفاده از نرمافزار شبیهساز ns2 شبیهسازي و نتایج بدست آمده با یکدیگر مقایسه شدهاند. نتایج شبیهسازيها برتري روش پیشنهادي را نشان داده است.
کلمات کلیدي: شبکههاي حسگر، اتوماتاهاي یادگیر، پروتکل سلسـله
مراتبی، مکانیزم زمانبندي
-1 مقدمه
شبکه هاي حسگر که در سالهاي اخیر مورد توجه بسیار قرار گرفتـهانـد از تعداد زیادي (که ممکن است بـه هـزاران مـورد برسـد) گـره حسـگر کوچک، ارزان قیمت با قابلیـت و قـدرت پـایین تشـکیل شـدهانـد. ایـن حسگرها می توانند اطلاعاتی را از محیط اطـراف خـود دریافـت کـرده و براي حسگرهاي همسایه ارسال دارند.[1,2] شبکه هاي حسگر می تواننـد در کاربردهایی مانند نظـارت هوشـمند بـر بزرگـراه هـا، امدادرسـانی در حوادث غیرمترقبه، دیدهبانی محیط و پیگیري هـدف[3,4] بکـار گرفتـه شوند. یکـی از مسـایل مهـم در شـبکههـاي حسـگر مسـاله مسـیریابی
می باشد که براي حل آن الگوریتمهاي فراوانی گزارش شده است. اکایـا1
و یانیس2 در [5] پروتکلهاي مسـیریابی را بـه چهـار گـروه کلـی "داده محور"، "سلسـله مراتبـی"، "بـر اسـاس موقعیـت" و "آگـاه از کیفیـت سرویس و جریان شبکه" تقسیم میکنند. در معمـاري سلسـله مراتبـی، گرههاي با انرژي بالاتر وظیفه پـردازش و ارسـال اطلاعـات را بـر عهـده دارند، درحالیکه گرههاي با انرژي پایینتر تنها نقش حسگرمحیط را در بازي میکنند. در مسیریابی سلسله مراتبی، گرهها به خوشههاي منطقی
تقسیم میشوند. در هر خوشه برخی گرهها سرخوشه و گرههاي دیگر به عنوان اعضاي خوشه در نظر گرفته میشـوند. اعضـاي خوشـه اطلاعـات مورد نظر را با توجه به کاربرد از محیط به دست میآورند و سـپس ایـن اطلاعات را به سرخوشه ارسال میکنند. سرخوشه نیز با جمعآوري ایـن اطلاعات آنها را به گره مرکزي میفرستد. اکثـر پروتکـلهـاي سلسسـله مراتبی داراي دو مرحله بـراي مسـیریابی هسـتند؛ مرحلـه اول انتخـاب سرخوشه و مرحله دوم مسیریابی میباشد. مسیریابی سلسله مراتبی یک راه مؤثر براي کاهش پیغامهاي ارسالی به ایستگاهاي اصلی و در نتیجـه افزایش طول عمر شبکه میباشد.
به منظور جلوگیري از تـداخل در ارتبـاط اعضـاي یـک خوشـه بـا سرخوشه خود، پروتکلهاي سلسله مراتبی از روشهاي مختلفی استفاده میمشابهکنند. AIMRP3 از روشی IEEE 802.11 اسـتفاده مـیکنـد
.[6] مکانیزمی که به طور معمول براي ارتباط اعضاي خوشه با سرخوشه استفاده میشودTDMA 4 است که در پروتکلهاي زیادي استفاده شده است .[7-15] مکانیزم زمانبندي TDMA تمایزي بین عضـو خوشـهاي که همواره دادهاي براي ارسال دارد و عضـو خوشـهاي کـه دادهاي بـراي ارسال ندارد قائل نیست و به هر دو عضو خوشه زمـان یکسـانی را بـراي ارتباط با سرخوشه میدهد. این در حالی است که ممکن است عضوي از خوشه در منطقهاي قرار داشته باشد که اطلاعات محیطـی آن مـدام در حال تغییر است، اما سایر اعضاي خوشه چنـین تغییراتـی را در محـیط اطراف خود حس نمی کنند. در این صورت، عضوي که اطلاعـات محلـی آن همواره در حال تغییر است باید زمـان بیشـتري را نسـبت بـه سـایر
اعضاء براي برقراري ارتبـاط بـا سرخوشـه و ارسـال اطلاعـات بـه آن در اختیار داشته باشد.
اخیراً اتوماتاهاي یادگیر در شبکههاي حسگر بیسیم مورد استفاده قرار گرفته است. در [16] با استفاده از اتوماتاهاي یادگیر مکانیزمی براي بیدار و خواب کردن گرهها به منظور حفظ کیفیت سـرویس ارایـه شـده است. در [17] پروتکل LACA5 که مبتنی بـر اتوماتاهـاي یـادگیر مـی باشد براي خوشهبندي گرهها و در[18] پروتکلی بـر اسـاس اتوماتاهـاي یادگیر براي چندپخشی متحرك براي شبکههاي حسگر ارائه شده است.
در این مقاله یک مکانیزم زمانبندي بر اساس اتوماتاهاي یادگیر که آنـرا
LASM6 مینامیم براي ارتباط اعضاي یک خوشه با سرخوشه پیشـنهاد میگردد. در این روش هر سرخوشه به یک اتوماتاي یادگیر مجهز اسـت و عهدهدار کنترل ارتباط سرخوشـه بـا اعضـاي آن مـیباشـد. اتوماتـاي یادگیر به مرور زمان یاد میگیرد که براي اعضـایی از خوشـه کـه داراي اطلاعات بیشتري براي ارسال میباشند شانس بیشتري را براي ارتباط با سرخوشه فراهم کند. به منظور ارزیـابی، پروتکـل LEACH7 کـه در آن مکانیزم زمانبندي پیشنهادي به کار گرفته شده است (LEACHLASM)
و پروتکل LEACH که از مکانیزم زمانبندي TDMA استفاده میکنـد (LEACHTDMA) با استفاده از نرمافزار شبیهساز [19] ns2 شبیهسازي
و نتایج بدست آمده با یکدیگر مقایسه شـدهانـد. نتـایج مقایسـه برتـري روش پیشنهادي را نشان داده است.
سازماندهی ادامه مقاله به ایـن صـورت اسـت. در بخـش 2 اتوماتاهـاي یادگیر و در بخش 3 پروتکل LEACH به اختصار شرح داده میشـوند.
در بخش 4 مکانیزم زمانبنـدي پیشـنهادي توضـیح داده مـیدرشـود و بخش 5 نتایج شبیهسازيها آمده است. بخش 6 نتیجهگیري میباشد.
-2 اتوماتاهاي یادگیر
یک اتوماتاي یادگیر[20,21]، ماشینی است که میتواند تعدادي متناهی عمل را انجام دهد. هر عمل انتخاب شده توسـط یـک محـیط احتمـالی ارزیابی میشود و نتیجه ارزیابی در قالب سیگنالی مثبـت یـا منفـی بـه اتوماتا داده میشود و اتوماتا از این پاسخ در انتخاب عمـل بعـدي تـاثیر میگیرد. هدف نهایی این است که اتوماتا یاد بگیرد تا از بین اعمال خود بهترین عمل را انتخاب کند. بهتـرین عمـل، عملـی اسـت کـه احتمـال دریافت پاداش از محیط را به حداکثر برساند. کارکرد اتوماتاي یادگیر در تعامل با محیط، در شکل 1 مشاهده میشود.
αn
محیط تصادفی
عمل اتوماتا
Archvie of SID
محیط را میتوان توسط سه تایی c} ,کهE ≡ {α , β نشان داد
در آن α ≡ {α1 , α2 ,..., αr } مجموعه وروديها,
β ≡ {β1 , β2 ,..., βm } مجموعه خروجیها و
c r } c ≡ {c1 , c 2 ,..., مجموعه احتمالهاي جریمههرگاهمیباشد.
β مجموعه دو عضوي باشد، محیط از نوع P میباشد. در چنین
محیطی β1 1 به عنوان جریمه و β2 0 به عنوان پاداش در نظر
گرفته میشود. در محیط از نوع Q، β (n ) میتواند به طور گسسته،
یک مقدار از مقادیر محدود در فاصله [0 1] و در محیط از نوع S،
β (n ) متغیر تصادفی در فاصله 1] [0 است. ci احتمال اینکه عمل
α i نتیجه نامطلوب داشته باشد میباشد. در محیط ایستا مقادیر ci
بدون تغییر میمانند، حال آنکه در محیط غیر ایستا این مقادیر در طی
زمان تغییر میکنند.
اتوماتاي یادگیر با ساختار ثابت توسط پنجتایی
{α , β , F , G , φ } نشان داده میشود که در آن
α ≡ {α1 , α 2 , L , α r } مجموعه عملهاي اتوماتا,
≡ { β1 , β 2 ,L , β m } β مجموعه وروديهاي اتوماتا,
φ ≡ {φ1 ,φ2 ,L,φs } مجموعه وضعیتهاي داخلی اتوماتا،
F :φ×β →φتابع تولید وضعیت جدید اتوماتا و G : φ → αتابع
خروجی میباشد که وضعیت کنونی اتوماتا را به خروجی بعدي مینگارد.
اتوماتاي یادگیر با ساختار متغیر را میتوان توسط
چهارتایی{α, β, p,T} نشان داد که K,αr مجموعه,αα1 ,α2
عملهاي اتوماتا، β β1 , β2 ,K, βm مجموعه وروديهاي اتوماتا،
p p1 , p2 ,K, pm بردار احتمال انتخاب هریک از عملها و
p(n 1) T[α(n), β(n), p(n)] الگوریتم یادگیري میباشد.
الگوریتم زیر یک نمونه از الگوریتمهاي یادگیري خطی است. فرض کنید عمل αi در مرحله n ام انتخاب شود.
- پاسخ مطلوب
(1) pi (n 1) pi (n) a[1− pi (n)]
i ∀j j ≠ p j (n 1) (1−a) p j (n)
- پاسخ نامطلوب
(2) pi (n 1) (1−b) pi (n)
p j (n 1) (b r −1) (1−b) p j (n) ∀j j ≠ i
در روابط (1) و (2)، a پارامتر پاداش و b پارامتر جریمه میباشند. بـا توجه بـه مقـادیر a و b سـه حالـت زیـر را مـیتـوان در نظـر گرفـت.
پاسخ محیط
βn
اتوماتاي یادگیر
زمانیکــه a و b بــا هــم برابــر باشــند، الگــوریتم را LRP مــینامنــد، زمانیکه b از a خیلـی کـوچکتر باشـد، الگـوریتم را LRεP مـینامنـد و زمانیکه b مساوي صفر باشد الگوریتم را LRI مینامند.[22]
شکل :(1) ارتباط بین اتوماتاي یادگیر و محیط
-3 پروتکل LEACH
یکی از اولین و معروفترین پروتکل هاي سلسله مراتبـی ارائـه شـده بـراي شبکه هاي حسگر، پروتکل LEACH می باشـد .[14] در ایـن پروتکـل، مدت زمان فعالیت شبکه به دورههایی تقسیم مـیشـود ( شـکلدر.(2
ابتداي هر دوره، به صورت تصادفی تعدادي از گرهها به عنوان سرخوشـه انتخاب میشوند. هبرايگرهاین کار یک عـدد تصـادفی مـابین 0و 1 تولید می کند. در صورتیکه این عـدد از مقـدار T(n) کـه بـا اسـتفاده از رابطه 3 به دست میآید، کمتر باشـد گـره مزبـور بـه عنـوان سرخوشـه معرفی میشود. در رابطه 3، P نسبت تعـداد خوشـه هـا بـه تعـداد کـل گرههاي شبکه، r شمارة دور و G تعداد گرههـائی مـی باشـد کـه در 1/P
دور قبل به عنوان رأس خوشه برگزیده نشده اند.
if n ∈G , P
1
(3) ( 1 − P × (r mod T (n)
p
otherwise
0,
پس از مشخص شدن گرههاي سرخوشه، سـایر گـرههـا بـر اسـاس قدرت سیگنال دریافتی از هر سرخوشه، تصمیم می گیرند که به عضویت کدام خوشه در آیند. گره سرخوشه بازه مسـئولیت خـود را بـه تعـدادي برش زمانی8 تقسیم میکند ( شکل .(2 این برشهاي زمـانی بـر اسـاس مکانیزم TDMA میان اعضاي خوشه به اشتراك گذاري می شوند. در هر برش زمانی، سرخوشه با یکی از اعضـاي خوشـه ارتبـاط برقـرار کـرده و بسته هاي اطلاعاتی آن عضو را دریافت می دارد. سرخوشـه در هـر چنـد برش زمانی، اطلاعات دریافتی از اعضاي خود را براي گره مرکزي ارسال میکند. به منظور توزیع بار برروي گرههاي مختلـف پـس از اتمـام یـک دور، براي آغاز دور جدید، سرخوشه ها بر اساس مکـانیزم بیـان شـده در فوق عوض می شوند.
شکل(:(2 دوره و برش زمانی در پروتکل LEACH
-4 مکانیزم زمانبندي پیشنهادي
در این قسمت مکانیزم زمانبندي پیشنهادي که آنرا LASM مینـامیم شرح داده میشود. ایـن مکـانیزم بعـد از مرحلـه خوشـهبنـدي و بـراي جمع آوري اطلاعات از اعضاي خوشه به کار گرفته میشـود. در مکـانیزم پیشنهادي، هر سرخوشه مجهز به یک اتوماتاي یادگیر است. سرخوشه با استفاده از اتوماتاي یادگیر خود، عضو خوشهاي را که باید بـا آن ارتبـاط برقرار کند انتخاب میکند. در مکانیزم پیشنهادياین LASM فرض بر
