الگوریتم های مسیریابی با بهره بری انرژی بالا برای شبکه های سنسوری بی سیم (2)
الگوریتم ACO یک مدل مشتق شده از رفتارهای واقعی مورچه هاست. ACO بهترین مسیر را از گره منبع تا پایگاه اصلی در WSN، جستجو می کند. این عوامل که مورچه نامیده می شوند، ابتدا در گره منبع قرار داده می شود و وظیفه ی
مترجم: حبیب الله علیخانی
منبع:راسخون
منبع:راسخون
تعاریف
الگوریتم ACO یک مدل مشتق شده از رفتارهای واقعی مورچه هاست. ACO بهترین مسیر را از گره منبع تا پایگاه اصلی در WSN، جستجو می کند. این عوامل که مورچه نامیده می شوند، ابتدا در گره منبع قرار داده می شود و وظیفه ی آنها پیدا کردن مسیرهایی است که از طریق آنها سایر گره های سنسوری به پایگاه اصلی می رسند. یک مورچه از گره منبع به پایگاه اصلی می رود و اطلاعاتی در مورد کیفیت راه بدست می آورد. این اطلاعات برای به روز رسانی سطح فرمون در گره های سنسوری میانجی مورد استفاده قرار می گیرد و با قوی تر شدن سطح فرمون در کوتاه ترین مسیرها، یک حالت از آگاهی در مورد میزان تقویت توزیع شده، حاصل می شود.یک الگوریتم مسیریابی اصلی بر پایه ی ACO از دو فاز تشکیل شده است. در مورد فاز اول، یک گروه از مورچه ها در گره منبع s_0 قرار داده می شوند و به سمت پایگاه اصلی
در نهایت یک WSN به عنوان یک گراف غیر جهت دهی شده و با وزن(G(V,E,L)) می باشد که :
V برابر گروه گره های سنسوری
L گره وزن ها( میزان سطح فرمون) است.
E گروه اضلاع است که در آن
هر گره
که در اینجا r متوسط ارتباط بی سیم گره های سنسوری است.
که
که در اینجا p(t) به سرعت تبخیر فرمون در زمان t و
بیان مسئله
در این کار شرایط بعدی برای WSN مورد استفاده قرار گرفته است: گره های سنسوری می تواند به طور تصادفی در یک ناحیه ی مربعی قرار داده می شوند به صورتی که گره های سنسوری باطری های نمی توانند تحت تأثیر قرار گیرند. آنها دارای آگاهی از محل قرارگیری هستند و از این رو آنها محل همسایه هایشان را می دانند. آنها همچنین مستعد شکسته شدن هستند که این مسئله باعث ایجاد تغییر در توپولوژی شبکه می شود.دو موضوع اصلی در WSN عبارتست از: عمر مفید شبکه و تأخیر در انتقال داده( این دو موضوع در این مقاله مورد بررسی قرار گرفته است). برای به حداکثر رساندن عمر مفید شبکه و به حداقل رساندن نهفتگی، این ضروری است که یک الگوریتم مسیریابی طراحی کنیم به نحوی که انرژی محدود شده در گره های سنسوری را محاسبه کند و همچنین تغییرات در توپولوژی شبکه را نیز بدست آورد.
این کار دوبیان الگوریتم از حالت هنری را به منظور اجرا و مطالعه، انتخاب کرده است. این دو الگوریتم عبارتند از: مسیریابی آگاهی مکانی برای شبکه های بی سیم که بر پایه ی کلنی زنبورها ساخته شده اند( ACLR) و الگوریتم مسیریابی با مصرف مناسب انرژی بر پایه ی مورچه( EEABR). ویژگی های اصلی آنها در یک الگوریتم مخلوط شده است که در مقایسه با دو الگوریتم، عملکرد بهتری( از لحاظ عمر مفید شبکه و تأخیر در انتقال داده) دارد. این الگوریتم ها در ادامه توضیح داده می شوند.
مسیریابی آگاهی مکانی برای شبکه های بی سیم که بر پایه ی کلنی زنبورها ساخته شده اند( ACLR)
هر گره سنسوری در WSN دارای یک بلوک حافظه ای است به نحوی که انرژی اضافی، اطلاعات در مورد محل قرار گیری گره، همسایه های آن و پایگاه اصلی در آن ذخیره می شود. هر مورچه ی K دارای یک لیست منع مصرف هستند که بوسیله ی آن گره های سنسوری که از آنها گذشته اند را در یک سفر در خود ذخیره کنند. ACLR از دو فاز توصیف شده در زیر ترکیب شده است: فاز اول: هر مورچه برای یک مسیر از s_o به
این فرمول احتمال انتقال نه تنها برای محل
که در اینجا
اگر هیچ هاپ همسایه ی دیگری برای انتخاب شدن، وجود نداشته باشد، در واقع
که Q یک ثابت است. d
الگوریتم مسیریابی با مصرف مناسب انرژی بر پایه ی مورچه( EEABR)
الگوریتم دومی که مورد مطالعه قرار گرفت الگوریتم EEABR است. این الگوریتم بازده ی انرژی را به منظور ماکزیمم کردن عمر مفید شبکه در نظر می گیرد. این اثبات شده است که وظایف انجام شده بوسیله ی گره های سنسوری به ارتباطات ( انتقال و دریافت داده) مربوط می باشد که در آن، مصرف انرژی نسبت به پردازش و مدیریت حافظه، بیشتر است. از آنجایی که یکی از دغدغه ها در WSN، ماکزیمم کردن دقیق عمر مفید شبکه است. که این مسئله ترجیح داده می شود که الگوریتم مسیریابی بتواند تا حد ممکنه در داخل شبکه، پردازش کند و بتواند تمام داده ها را به پایگاه اصلی ارسال کند.
در حقیقت EEABR تلاش می کند تا اندازه ی بسته های داده را تا حد ممکنه، مینیمم کند. EEABR یک تفاوت قوی میان مورچه های پیش رو( آنهایی که از منبع انرژی به پایگاه اصلی می روند) و مورچه های بازگشتی ( آنهایی که از
فاز اول( مورچه های پیش رو): وقتی یک گره سنسوری s یک مورچه K را شناسایی می کند، s حافظه ی آن را به منظور تشخیص حلقه های و جلوگیری از پدید آمدن آنها، جستجو می کند. اگر هیچ اطلاعات ثبت شده ای، نباشد، s اطلاعات مورد نیاز برای مورچه ی k را ثبت می کند و تایمر k را مقدار دهی می کند. سپس k تصمیم می گیرد که کدام گره سنسوری برای پرش مناسب تر است( این کار با توجه به فرمول احتمال انتقال، انجام می شود. این فرمول به صورت زیر تعیین می شود:
که
C سطح انرژی اولیه ی گره های سنسوری و e_j انرژی گره سنسوری j می باشد. اگر k از میان s عبور کند، پس k حذف می شود. وقتی مورچه ی k به پایگاه اصلی
که در ابنجا
الگوریتم های بهبود یافته ی مسیریابی برپایه ی کلنی مورچه ها برای WSN( IACAR)
با در نظر گرفتن برخی از ویژگی های الگوریتم های مورد بررسی در این مطالعه( EEABR و ACLR)، یک الگوریتم جدید پیشنهاد شده است. این ویژگی های آنهایی هستند که برای بهبود عمر مفید شبکه و تأخیر زمانی درانتقال، مناسب اند. IACAR پیشنهاد شده که از ACLR بدست آمده است، راهی برای محاسبه ی فرمولاسیون احتمال انتقال ارائه می نماید که بوسیله ی آن گره بعدی با کمک بدست آوردن مسیرهای کوتاهتر، انتخاب می شود و به عبارت دیگر، از EEABR، ایده ی حفظ مورچه های کوچک، به حداقل رساندن عمر مفید شبکه کمک می کند.چندین مورچه در گره منبع طبقه بندی می شوند و هر مورچه گره بعدی خود را با توجه به فرمول هشتم انتخاب می کند. به دلیل اینکه، EEABR و IACAR به مورچه ها اجازه می دهند تنها دو گره آخر را در حافظه یشان حفظ کنند، اندازه ی مورچه ها ثابت است. وقتی مورچه ی K از میان گره سنسوری S می گذرد، گره s مسئول ثبت و ذخیره ی اطلاعات یک مورچه را با توجه به فاز اول EEABR دارد. وقتی یک مورچه به پایگاه اصلی
آزمایشات
این بخش مقایسه ی تجربی میان الگوریتم ACLR، EEABR، و IACAR را نشان می دهد. این الگوریتم ها در زبان c اجرا شد. گره های Mica2 Motes از شرکت Crossbow شبیه سازی شد و مقدار انرژی مورد نیاز برای انتقال و دریافت یک بیت را می توان در مقالات دیگر پیدا کرد. این حقیقت وجود دارد که آن گره ها یا در حال مصرف انرژی هستند، یا خاموش اند و یا در حالت خواب هستند. به هر حال در این شبیه سازی، گره ها همواره روشن در نظر گرفته شدند تا بدین وسیله این مصرف انرژی که برای انتقال و دریافت بسته های داده مورد استفاده قرار می گیرند، محاسبه گردند. با این ملاحظات، این مسئله را می توان استنتاج نمود که مقایسه ی میان الگوریتم های ACLR، EEABR و IACAR واقعی تر است و از الگوریتم های ارائه شده در پروپزال اولیه منصفانه تر است. برای این، ما آزمایشات را با استفاده از این سه سناریوی تعریف شده در مرجع 5، انجام دادیم و حالت های مختلف یک WSN را شبیه سازی کردیم و یک سناریوی 4 گانه که انعکاس دهنده واقعی تر این حالات بود، را پیدا کردیم. ما همچنین سه استاندارد را برای تعیین کارایی الگوریتم های مسیریابی مورد ارزیابی قرار دادیم. این سناریوها و استانداردها به صورت زیر تعریف می شوند:سناریوها: سناریوی 1: تمام گره ها با یک سطح انرژی اولیه ی یکسان شروع به کار می کنند و تنها یک منبع s_o وجود دارد. سناریوی 2: تمام گره ها با انرژی اولیه ی یکسان شروع به کار می کنند و s_o به طور تصادفی تغییر می کند. سناریوی 3: انرژی اولیه ی گره ها به طور تصادفی انتخاب می شود و s_o به طور تصادفی تغییر می کند. سناریوی 4: تمام گره ها با انرژی اولیه ی یکسان شروع به کار می کنند و s_o به طور تصادفی تغییر می کند و شبیه سازی تا زمانی که برخی از گره ها خالی انرژی می شوند، ادامه می یابد.
استانداردها: این سه استاندارد مناسب هستند زیرا آنها در مورد مقادیری بحث می کند که به طور مستقیم برروی عمر مفید شبکه اثر می گذارند. مصرف انرژی به در فرایند پیدا کردن مسیرهای بهینه از گره منبع s_o به پایگاه اصلی
مقادیر پارامتر برای سه الگوریتم یکسان است. این مقادیر عبارتند از:
میدان قرارگیری گره ها دارای مساحت سطح 300m^2×200m^2 است.
تعداد مورچه ها برابر 20 است.
تعداد گره های مورد استفاده برابر 10000است.
شعاع ارتباط بی سیم سنسورها برابر 30 متر است.
وزن های قابل تنظیم برابر γ=1 و α=1است.
برای الگوریتم ACLR، β=1 و Q=1 است.
برای الگوریتم های EEABR، ψ=1 و سرعت تبخیر فرمون p(t) برابر 0.95 است.
سطح فرمون اولیه برای هر جفت از گره های مجاور برابر با φ_(i,j) (0)=0.01 قرار داده شده است.
تعداد واکنش ها برابر 50 بود.
مصرف انرژی در هر بیت ارسال شده، برابر با 4.28 میکروژول است. و در بیت دریافت شده برابر 2.36 میکروژول است.
برای هر الگوریتم، 30 آزمایش مجزا( در هر سناریو) اجرا شده است.
نتایج
در جدول 1 نتایج میانگین برای مصرف انرژی استاندارد، تأخیر و بازده انرژی به ترتیب برای 4 سناریو نشان داده شده است و ACLR، EEABR، و الگوریتم IACAR پیشنهاد شده، مقایسه شده است.در سناریوی اول، IACAR نتایج بهتری را نسبت به ACLR( از لحاظ مصرف انرژی) بوجود آورده اند( برای تمام 30 آزمایش). و این روش نتایج مشابهی با EEABR بدست آوردند. EEABR دارای یک استراتژی است که در آن مورچه ها کوچک هستند اما اطلاعات وابسته به مسیرهای آنها در گره ها نگهداری می شود. این استراتژی همچنین بوسیله ی IACAR دنبال می شود. از این نتایج، این به نظر می رسد که این استراتژی این استاندارد را بهبود می دهد. در مقایسه ی تأخیر استاندارد برای سه الگوریتم مورد مطالعه، ACLR بهترین الگوریتم برای این استاندارد است. بهترین نتایج بوسیله ی ACLR بدست آمده است و به طور دقیق بوسیله ی LACAR دنبال می شود. به طور خلاصه باید بگوییم که IACAR کارایی مشابهی با EEABR و ACLR در مصرف انرژی و تأخیر دارد. علاوه بر این، در مورد بازده انرژی،عملکرد IACAR نسبت دو الگوریتم دیگر فوق العاده است.
در سناریوی دوم برای استاندارد مصرف انرژی، IACAR بهتر از ACLR عمل می کند( در تمام 30 مورد) و همچنین نسبت به EEABR بهتر عمل می کند( در بیش از 24 مورد از 30 آزمایش). برای مسیرهای کوچکتر، مسئله ی تأخیر در IACAR بهترین نتایج را ایجاد می کند. محل دوم ACLR است که برای این استاندارد بهتر عمل می کند. از لحاظ بازده انرژی، IACAR بهترین نتایج را نشان می دهد که بوسیله ی EEABR دنبال می شود.
سناریوی سوم نشان می دهد که در مورد مصرف انرژی، بدترین نتایج بوسیله ی ACLR بدست می آید. IACAR بهترین کارایی را نشان می دهد و نسبت به EEABR بهتر عمل می کند( در بیش از 23 مورد از 30 مورد آزمایشات). EEABR مکان دوم را به خود اختصاص داده است. از لحاظ نهفتگی، ACLR و IACAR نتایج مشابهی را از خود نشان می دهد. از لحاظ بازده انرژی، بهترین کارایی بوسیله ی IACAR حاصل می شود. مکان دوم را EEABR به خود اختصاص داده است و مکان سوم را ACLR به خود اختصاص داده است.
سناریوی 4 ام
جدول 1 نشان می دهد که هیچ الگوریتمی وجود ندارد که نسبت به سایرین بهترین کارایی را داشته باشد. به هر حال IACAR نتایج متوسط بهتری را نسبت به EEABR و ACLR، در 3 استاندارد از خود نشان می دهد.شکل های 1 و 2 و 3 نتایج مصرف انرژی، تأخیر و بازده انرژی را به ترتیب برای EEABR، ACLR و IACAR برای سناریوی 4 را در سناریوی 4 نشان می دهند. به طور واضح نشان داده شده است که EEABRو IACAR دارای عملکرد بهتری نسبت به ACLR هستند اما هنوز هم IACAR مقام اول را دارد( در بیش از 22 مورد از 30 آزمایش). بهترین نتایج برای تأخیر در این سناریو IACAR است( 29 آزمایش). مکان دوم را EEABR و مورد آخر را ACLR است( مورد آخر برای یافتن مسیر نیازمند گره های بیشتری است). از لحاظ بازده انرژی، بهترین نتایج بوسیله ی IACAR بدست آمده است( 20 مورد از آزمایشات). به هر حال نتایج بدست آمده از EEABR نیز به این نتایج نزدیک است. بدترین نتایج در این زمینه بوسیله ی ACLR حاصل می شود.
بحث
مسئله ی مصرف انرژی: در سناریوهای 1 تا 3، IACAR بهتر از EEABR عمل می کند. به هر حال در سناریوی 4، هر دو مقدار بدست آمده به هم نزدیک هستند. به عبارت دیگر، ACLR در تمام سناریوها، نتایج بدتری ارائه می دهد. توجه کنید که این استراتژی در EEABR پیشنهاده شده است و در IACAR دنبال شده است ( IACAR به نگهداری مورچه های کوچک مربوط می شود که با کمک استاندارد انرژی مصرفی، به خوبی کار می کند).مسئله ی تأخیر
در سناریوی اول، ACLR بهتر از EEABR و IACAR عمل می کند. در مورد سناریوهای دوم و سوم، IACAR نتایج مشابهی با ACLR از خود نشان می دهد و در نهایت برای سناریوی 4، IACAR بهتر از دو الگوریتم دیگر عمل می کند و بدترین نتایج مربوط به ACLR است. دلیل این موضوع این است که استراتژی اصلی در ACLR عمدتا با جستجوی مسیرهای کوتاه تر، ایجاد می شود( بدون در نظر گرفتن اندازه ی مورچه ها). بنابراین در سناریوی 4، وقتی برخی از گره ها اتصال خود را از منبع قطع می کنند، ACLR قادر به پیدا کردن مسیرهای کوتاه تر نمی باشد( ولی مسیرهای بزرگتر را پیدا می کند). به عبارت دیگر IACAR بهترین نتایج را برای سناریوی 4 ام بدست می آورد زیرا وجود مورچه های کوچک به گره ها اجازه می دهد تا در دوره های زمانی بزرگتری باقی بمانند. بنابراین این روش قادر به پیدا کردن مسیرهای کوتاه تر است.مسئله بازده ی انرژی: برای تمام 4 سناریو، ACLR بدترین نتایج را بوجود می آورد. این مسئله به دلیل این رخ می دهد که این الگوریتم به مورچه ها اجازه می دهد اندازه یشان را در هر پرش، افزایش دهند. که این مسئله بر روی مصرف انرژی اثر گذار است. IACAR و EEABR نتایج مشابهی را برای سناریوهای اول، دوم و سوم ایجاد می کنند. و IACAR درسناریوی 4 بهتر از EEABR عمل می کند.
از این مشاهدات، این نتیجه می شود که الگوریتم پیشنهاد شده ( IACAR) عموما نتایج بهتری نسبت به EEABR و ACLR ( برای 3 استاندارد) از خود نشان می دهد( یعنی در مورد مصرف انرژی، بازده و تأخیر). بنابراین ایده ی در نظر گرفتن ویژگی های اصلی EEABR و ACLR باعث ایجاد الگوریتم بهتری می شود.
نتیجه گیری
نتیجه گیری های بوجود آمده به صورت زیر خلاصه می شوند: طراحی الگوریتم های مسیریابی برای WSN باید مد نظر قرار گیرد( نه تنها در به حداقل رساندن طول مسیرها، بلکه ماکزیمم نمودن عمر مفید شبکه( یعنی انرژی در باطری های گره ها). برای سبک و سنگین کردن و مقایسه ی واقعی میان الگوریتم های مسیریابی برای WSN، باید انرژی مصرف شده بوسیله ی گره ها محاسبه شود. استراتژی پیشنهاده شده در EEABR ،که در آن اندازه ی مورچه ها ثابت و کوچک است، باعث افزایش عمر مفید شبکه می شود. استراتژی پیشنهاد شده در ACLR به انتخاب گره ی بعدی بوسیله ی پرش، مربوط می شود که این مسئله نشاندهنده ی بهترین گزینه در مورد تأخیر است.یک کار در آینده برنامه ریزی شده است که بوسیله ی آن این الگوریتم ها در WSN واقعی اجرا می شود. علاوه بر این، این ضروری است که اثر مقادیر پارامتری در کارایی های الگوریتم ها، مورد ارزیابی شود. و همچنین این مقادیر در سایر الگوریتم هایی که بر پایه ی ACO نیز نیستند، مورد مقایسه قرار گیرد.
تازه های مقالات
ارسال نظر
در ارسال نظر شما خطایی رخ داده است
کاربر گرامی، ضمن تشکر از شما نظر شما با موفقیت ثبت گردید. و پس از تائید در فهرست نظرات نمایش داده می شود
نام :
ایمیل :
نظرات کاربران
{{Fullname}} {{Creationdate}}
{{Body}}