الگوریتم مسیریابی مورچه ی در حال پریدن در شبکه های سنسوری

چکیده:

در تشکیلات حیاتی متحرک (مانند بیمارستان ها)، این نیاز وجود دارد تا اطمینان حاصل کنیم که محل کنونی وسایل متحرک شناخته شده باشند. علاوه براین، گره سنسور در هر یک از این وسایل باید به ما اطلاع دهند که آن وسیله ی مربوط به آن گره، در محیط خطرناک کار می کند یا نه! بنابراین وسایل حیاتی می توانند قبل از استفاده ی مجدد، تعمیر و نگهداری شوند. به دلیل محیط کاری و تحرک گره ی سنسوری ، این نوع از شبکه های سنسوری می توانند از طریق فرایند های مسیریابی، ایجاد شوند. یک شبکه ی سنسور یک راه حل بالقوه برای استفاده در این نوع کاربردهاست زیرا این نوع گره ها دارای مشابهت زیادی با شبکه های Ad-hoc متحرک( MANETs) هستند. این مطالعه یک الگوریتم مسیریابی مورچه ی در حال پریدن( JARA) را پیشنهاد می دهد که در آن، مزیت های مسیریابی فعل و انفعالی را ترکیب کرده و بدین وسیله زمان کشف مسیر را سرعت می دهد و بدین ترتیب هزینه های کلی کشف مسیر در شبکه ی سنسور کاهش می یابد.

مقدمه

در تشکیلات حیاتی متحرک ( مانند بیمارستان ها)، این نیاز وجود دارد تا اطمینان حاصل کنیم که محل کنونی وسایل متحرک شناخته شده باشند. یک شبکه ی سنسور یک راه حل بالقوه برای این نوع از کاربردهاست زیرا هر گره می تواند از طریق فرایند های مسیریابی، مکان یابی گردد. به دلیل محیط کاری این وسایل، این نوع از شبکه های سنسوری مشابهت زیادی با شبکه های MANET دارند( در این شبکه ها گره سنسور آزادانه می تواند حرکت کند).
پروتکل های زیادی برای الگوریتم های مسیریابی مورد استفاده در شبکه های سنسوری، توسعه پیدا کرده است. این پروتکل ها می تواند به پروتکل های فعال، انفعالی و ترکیبی تقسیم بندی شوند. در الگوریتم های فعال( proactive) هر گره از مرفولوژی کلی خبر دارد و بنابراین یک الگوریتم فعال باید به طور دوره ای یک جدول مسیریابی را حفظ کند. در مقابل، یک گره در الگوریتم انفعالی وقتی از محل گره دیگر اطلاع پیدا می کند، شروع به ساخت اطلاعات مسیریابی می کند. سپس یک بسته را از طریق مسیری که ساخته است، ارسال می کند در حالی که در پروتکل های ترکیبی سعی در استفاده از ترکیبی از این ایده ها وجود دارد.
مسیریابی مورچه ای یک پروتکل خود پیکربندی و خود ساخته است که می تواند تعداد پیام های منتشر شده را کاهش دهد و باعث حفظ مسیرهای چندگانه می شود. یک راه جایگزین برای ارسال بسته ها می تواند در زمانی پیدا شود که شبکه تغییر می کند بنابراین در این حالت شبکه به سرعت بازسازی می شود.
مسیریابی مورچه ای دارای برخی محدودیت ها نیز می باشد زیرا این روش به عنوان روشی انفعالی در نظر گرفته می شود. یک گره در زمانی که بخواهد یک بسته داده را به مقصد ارسال کند، شروع به کشف مسیر می کند. به هر حال مسیریابی فعال نیازمند پهنای باند زیادی است. بنابراین این تحقیق الگوریتمی را پیشنهاد می کند که به آن الگوریتم مسیریابی مورچه ی در حال پریدن( JARA) می گویند. این الگوریتم، مزیت های مسیریابی مورچه ی در حال پریدن را با مسیریابی فعال، ترکیب می کند. JARA دارای نقطه ی مربوط به خود می باشد. کل الگوریتم را می توان به دو بخش تقسیم نمود. اولا هر گره از پروتکل مسیریابی فعال، برای تعیین توپولوژی پرش های ρ مورد استفاده قرار می گیرد؛ سپس از روش مسیریابی مورچه ای برای کشف مسیر در خارج نقطه، استفاده می شود.

کارهای مربوطه

شبکه های سنسور، شبکه های غیر متمرکزی از گره های مستقلی هستند که اطلاعات را به منظور ارسال به یک سینک در اتصال های بی سیم، جمع آوری می کنند. در برخی وضعیت ها، گره ی سنسوری می تواند به صورت تصادفی حرکت کند. قابلیت حرکت گره ها بدین معناست که توپولوژی شبکه ممکن است از یک زمان به زمان دیگر، تغییر کند. این مسئله موجب می شود تا استفاده از جدول های مسیریابی سنتی که دارای نقاط ثابت( روترها) هستند، امکان پذیر نباشد. در عوض، هر گره نیازمند این است تا بهترین مسیر را برای انتقال داده ها به سینک پیدا کند. این نوع از شبکه های سنسور بسیار شبیه شبکه هایMANET(شبکه های Ad-hoc سیار) هستند.
الگوریتم مسیریابی مورچه ای برای شبکه های Ad-hoc سیار( ARAMA)
الگوریتم بهینه سازی کلنی موچه ها بوسیله ی رفتار واقعی کلنی های مورچه ای الهام گرفته شده است. مطالعات گسترده ای بر روی استفاده از الگوریتم های کلنی مورچه ها برای حل مسائل مختلف انجام شده است. ARAMA در این بررسی مورد توجه قرار گرفته است زیرا این الگوریتم واقعی، بادوام و دینامیک است. راه حل بهینه ی برای ARAMA با ایجاد یک مورچه های ساختگی تعیین می شود. مورچه های ساختگی فضای راه حل را همانگونه که مورچه های طبیعی محیط پیرامونشان را برای پیدا کردن غذا سرچ می کنند، سرچ می کنند. حرکت احتمالاتی مورچه ها در داخل سیستم به مورچه ها اجازه می دهد تا راه های جدید را مطالعه کنند و همچنین راه های قدیمی را نیز دوباره بررسی کنند. میزان رسوبات فرمون( pheromone) مورچه های ساختگی را به سمت بهترین راه ها سوق می دهد در حالی که تبخیر فرمون اجازه می دهد تا سیستم اطلاعات قدیمی را فراموش کند و بدین صورت از انحراف های بوجود آمده در راه حل های غیر بهینه جلوگیری می شود. انتخاب احتمالاتی راه حل ها ما را قادر می سازند تا راه حل های فراونی را مورد بررسی قرار دهیم. شکل 1 فلوچارت مرتبه ی بالای را برای این عملکرد ها نشان می دهد. وقتی یک گره می خواهد تا یک راه را برای مقصد خود پیدا کند، این گره مورچه های پیش رو را برای پیدا نمودن این مقصد ارسال می کند. یک مورچه ی پیش رو در این شبکه به جستجوی مقصد می پردازد. او این کار را با استفاده از جداول مسیریابی احتمالاتی مربوط به گره های میانجی و اطلاعات ذهنی محلی، انجام می دهد. مورچه های پیش رو اطلاعات در مورد مسیرها و گره های میانجی را در هنگامی که در این مسیر حرکت می کند، جمع آوری می کند. وقتی یک مورچه ی پیش رو مقصد خود را جستجو می کند، اطلاعات بوسیله ی این مورچه ی پیش رو طبقه بندی می شود. مورچه ی پیش رو سپس کشته می شود و یک مورچه ی پس رو ایجاد می شود. مورچه ی پس رو طبقه بندی( درجه بندی) و مشخصات گره های میانجی مربوط به مورچه ی پیش روی خود را حمل می کند. مورچه ی پس رو به طور عکس در طول مسیر مورد استفاده بوسیله ی مورچه ی پیش رو عبور می کند. وقتی مورچه های پس رو در مسیر عکس حرکت می کنند، گره های میانجی جدول فرمون را بر اساس درجه بندی ارائه شده بوسیله ی مورچه ی پیش رو، اصلاح می کنند و با توجه به این مسئله احتمالات جدول فرمون آنها به روز رسانی می شود. در نهایت گره منبع اطلاعات مورچه های پس رو را دریافت نموده و جدول داده ی خود را به روز رسانی می کند و پس از آن این مورچه های پس رو کشته می شوند.

پروتکل مسیریابی منطقه ای( Zone routing protocol)

پروتکل های فعال و انفعالی هر دو، دارای قوانین خاص خود می باشند. پروتکل های مسیریابی منطقه ای( ZRP) مزیت های هر دو نوع از این پروتکل ها را به صورت ترکیبی دارا میباشد و از یک مکانیزم فعال برای کشف همسایه ی محلی یک گره استفاده می کند و با اعمال پروتکل انفعالی در بین همسایه ها ارتباط برقرار می کند.
همانگونه که قبلا اشاره شد، ZRP یک چارچوب برای سایر پروتکل های MANET ایجاد می کند. جدانمودن همسایه های محلی گره ها از توپولوژی سراسری کل شبکه به ما اجازه می دهد تا از روش های مختلفی استفاده کنیم و بنابراین هر یک از ویژگی های فنی را در وضعیت معین بررسی کنیم. همسایه های محلی منطقه( zone) نامیده می شوند. هر گره ممکن است در داخل مناطق چندگانه قرار داشته باشد و هر منطقه ممکن است دارای اندازه ی مختلفی باشد. اندازه ی یک منطقه بوسیله ی اندازه گیری های جغرافیایی قابل محاسبه نمی باشد( همانگونه که قابل پیش بینی بود)، اما به جای آن این اندازه با شعاع طول ρ محاسبه می شود که در اینجا ρ نشاندهنده ی تعداد پرش ها( hops) در پیرامون منطقه است.

الگوریتم مسیریابی مورچه ی در حال پریدن

این بررسی یک الگوریتم مسیریابی مورچه ی در حال پریدن( JARA) ارائه می دهد که در آن مزیت های ARAMA و ZRP ترکیب شده است؛ در حالی که علاوه بر این مسائل از حالت پرش نیز استفاده شده است تا بدین وسیله سربار(overhead) فعال مورد نیاز، کاهش یابد. این الگوریتم به دو بخش تقسیم می شود. بخش اول مربوط می شود به این مسئله که چگونه هر گره از پروتکل مسیریابی فعال استفاده می کند تا بدین وسیله توپولوژی پرش های ρ حفظ گردد. این فرض شده است که شبکه ی داخلی هم اکنون بوسیله ی یکی از پروتکل های مسیریابی فعال، ساخته شده است؛ و بنابراین هم اکنون یک جدول شبکه ی داخلی ایجاد شده است. این کار بر روی بهترین مکانیزم مسیریابی فعال تمرکز نکرده است. بخش دیگر در مورد روشی است که هر گره مسیریابی مورچه ای اعمال می کند، است( در واقع بوسیله این کار مسیرهایی در بیرون ناحیه ی آن گره، کشف می شود). هر گره دارای ناحیه ی خاص خود می باشد و هر مورچه یک مسیر در داخل پرش های ρ بدست می آورد. از این رو هر فاصله ی پرش در پرش مورچه ای به عنوان یک حرکت در نظر گرفته می شود. این کار الگوریتم پیشنهاد شده را تشریح و شبیه سازی می کند( با استفاده از در نظر گرفتن ρ=2). وضعیت ρ=2 انتخاب شده است زیرا این وضعیت برای نشان دادن برتری الگوریتم پیشنهادی، کافی است.
هر گره در الگوریتم ما می تواند اطلاعات جزئی در مورد گره های همسایه را در داخل پرش های ، کشف کند. این گره های همسایه می توانند در یک ناحیه به نام شبکه ی داخلی، سازماندهی شوند. گره های داخل یک ناحیه به گره های داخلی و گره های مرزی طبقه بندی می شوند. مینیمم فاصله ی گره مرزی با گره مرکزی دقیقا برابر با شعاع ناحیه ی ρ می باشد. گره ها با فواصل مینیمم کمتر از ρ ، گره های داخلی نامیده می شوند. شکل 2 مثالی از یک ناحیه با ρ=2 است. گره مرکزی در شکل گره A می باشد. گره های B،D، E، H، F و J گره های مرزی می باشند. گره های Cو G و I گره های داخلی هستند. و گره های K و L خارج از ناحیه ی مسیریابی هستند. هرمورچه در گره A از جدول فرومون برای انتخاب گره ی مرزی به عنوان گره ی بعدی استفاده می کند. اگر مورچه گره ی B را انتخاب کند، پس او باید از طریق گره C به سمت گره B حرکت کند. گره C فقط بسته های ارسالی از گره ی مرکزی A به گره مرزی را باز پخش می کند. از این رو JARA می تواند به کشف و پیداکردن بهترین مسیر، سرعت ببخشد. بخش بعدی کشف مسیر را توضیح می دهد و سپس اثر تغییرات در توپولوژی شبکه را مورد بحث قرار می دهد. شکل 20 فلوچارت این الگوریتم است.

کشف مسیر

مورچه ها به مورچه های پیش رو، پس رو و راهنما طبقه بندی می شوند. مورچه های پس رو و پیش رو مانند مورچه های بیان شده در ARAMA هستند و مسئول جمع آوری اطلاعات مسیری و به روز رسانی فرومون هستند. یک مورچه راهنما یک مسیر بهینه را وقتی که تمام مورچه های پسرو به منبع یک گره میرسند یا وقتی توپولوژی شبکه تغییر می کند، می سازد. هر گره همچنین دارای یک جدول فرومون مانند جدول 1 می باشد.
کشف مسیر به صورت زیر است:
گره منبع چندین مورچه ی پیشرو ایجاد می کند تا مقصد را جستجو کنند. این مورچه ها وقتی در طول یک مسیر حرکت می کنند، اطلاعات مسیر را جمع اوری می کنند.
یک گره وقتی مورچه ی پیشرو به انجا میرسد، یک مورچه ی پسرو ایجاد میکند.
مورچه های پسرو در جهت عکس مسیر، پس فرستاده میشوند و جدول فرومون را بروز رسانی می کنند.
مورچه راهنما وقتی که همه ی مورچه های پسرو به منبع می رسند، ایجاد میشوند. این مورچه جدول مسیریابی را در طول مسیر بهینه شده بروز رسانی میکند و یک مسیر بهینه ایجاد میکند.
بخش زیر جزئیات این روش را توضیح می دهد.

مورچه ی پیشرو

هر گره در شبکه می تواند به عنوان یک گره منبع، مقصد و یا میانجی درنظر گرفته شود. گره ای که میخواهد مسیری را به یک مقصد پیدا کند، مورچه های پیش رو را برای جستجوی این مقصد و بدست آوردن اطلاعات در زمینه ی مسیر ارسال می کند.
وقتی یک مورچه ی پیش رو بوسیله ی گره منبع ایجاد می شود، این مورچه از جدول فرومون برای بدست آوردن گره مشاهده شده ی بعدی و ثبت اطلاعات مربوط به مسیر، استفاده می کند. با توجه به قوانین مسیریابی ARAMA، گره مشاهده شده ی بعدی بوسیله ی یک مورچه تنها به احتمالات جدول فرمون وابسته است. یک چنین رفتاری برای جلوگیری از بدام افتادن مورچه ها در مسیر یکسان انجام می شود( به دام افتادن مورچه ها باعث می شود تا مزیت های اکتشافی کاسته شود). مقادیر احتمالات با توجه به اطلاعات ذهنی و جدول فرمون (جدولی مشابه جدول 1)، محاسبه می شود. انتخاب گره بعدی در مسیر مورچه به صورت زیر تعیین می شود:
احتمال انتخاب همسایه ی j به گره i با مقصد D بوسیله ی فرمول فرمول زیر محاسبه می شود:

که در اینجا ، مقدار ذهنی محلی اتصال (i,j) در میان گره های i و j است. و مقدار فرمون در اتصال (i,j) است. ARAMA در بخش الگوریتم مسیریابی مورچه ای برای شبکه های Ad-hoc سیار( ARAMA) توصیف شد. تابعی از و است.
یک مورچه ی پیش رو که در حال حرکت به سمت یک گره میانجی است، از احتمالات جدول فرومون استفاده می کند و گره مقصد بعدی را به دسته گره میانجی اضافه می کند و بدین صورت اطلاعات ذهنی محلی برای به روز رسانی اطلاعات مسیر را از بسته اطلاعاتی مورچه ی پیش رو بدست می آورد. اگر مورچه ی پیش رو به سمت گره میانجی حرکت کند، پس گره داخلی نیازی به انجام عملی ندارد و تنها مورچه ی پیش رو را به گره مقصدی بعدی، مربوط می کند. مورچه ی پیش رو در زمانی که به گره میانجی می رسد، کشته می شود و مورچه ی پس رو ایجاد می شود. گره مقصد همچنین اطلاعات مسیر را برای درجه بندی و ارزیابی مورچه ی پس رو، استفاده می کند.

مورچه ی پس رو

وقتی مورچه ی پس رو به یک گره رسید، اگر این گره، یک گره میانجی از بسته اطلاعاتی مورچه های پس رو باشد، پس گره، درجه بندی ها را از بسته اطلاعاتی مورچه ی پس رو دریافت نموده و سپس جدول فرومون را با استفاده از این درجه بندی، به روز رسانی می کند و مورچه را به گره میانجی بعدی می فرستد. اگر این گره یک گره داخلی باشد، پس گره به جدول مسیریابی مراجعه نموده و مورچه را به مقصد بعدی انتقال می دهد. مورچه ی پس رو در زمانی که به گره منبع می رسد، کشته می شود.
تابع به روز رسانی فرومون مقدار فرومون را در اتصال ورودی افزایش می دهد و مقدار آن را در اتصال های دیگر کاهش می دهد( با استفاده از تابع زیر):
برای مقصد Dدر گره میانجی i:

که در اینجا f(ρ) تابع تبخیر و g(ρ) نشاندهنده ی تابع اجراست. کمک تابع تبخیر این است که به سیستم کمک می کند تا اطلاعات قدیمی را به سرعت فراموش کند. یک مقدار بالاتر از ρ نشاندهنده ی این است که تبخیر سریع تر انجام می شود. عموما تابع تبخیر باید دارای مقدار اندکی باشد. یک تابع تبخیر نمونه وار تابع است. تابع اجرا به سیستم کمک می کند تا مقدار فرومون را در کناره ها افزایش دهد. وقتی مقدار درجه ی ρ افزایش می یابد، تابع اجرا باید افزایش یابد. یک مثال از تابع اجرا برابر است.

مورچه ی راهنما

این بخش در مورد این مسئله بحث می کند که چرا مورچه ی راهنما مورد استفاده قرار می گیرد. و با در نظر گرفتن این مسئله کار خود را شروع می کند که چگونه ARAMA ، محل بسته های تحویل داده شده را بدون مورچه ی راهنما تعیین می کند. ARAMA می تواند همچنین دو روش توصیف شده در زیر را مورد استفاده قرار دهد. روش اول تعیین مسیریابی در زمانی است که بسته بر روی شبکه ها در حال جریان است و روش دوم روشی است که در آن از مورچه ی پسر و استفاده می شود.
با استفاده از روش اول، کشف مسیر زود تر انجام می شود. تعیین مسیریابی در حالی که بسته ها در حال انتقال بر روی شبکه هستند، روشی زمان بر است و کارایی انتقال را کاهش دهد. وقتی از روش دوم استفاده می شود، مسیریابی به مورچه ی پس رو بستگی پیدا می کند. یک چنین روشی فرکانس به روز رسانی مسیریابی را کاهش می دهد و ممکن است حتی باعث شود مقادیر ثبت شده در طول یک مسیر غیر ضروری فرستاده شوند.
مورچه ی راهنما در شبکه های Ad-hoc مورد استفاده قرار می گیرند تا این اشکالات را برطرف کنند. مورچه ی راهنما می تواند داده ها را حمل کند و بنابراین بسته های اضافی ایجاد نمی شود. این عملیات ها بعدا به طور جزئی توصیف می شوند. مورچه ی راهنما همچنین مسیرهای منقطع به یک مقصد را تعمیر می کند( همانگونه که در بخش بعدی جزئیات این موضوع بیان شده است).
گره منبع یک مورچه ی راهنما ایجاد می کند تا بوسیله ی آن مسیر بهینه معین گردد. مورچه ی راهنما جدول مسیریابی را به روز رسانی می کند. و می تواند تعیین کند که آیا گره مورد نظر گرهی مرزی است یا گرهی داخلی است. اگر این گره، یک گره مرزی باشد، پس مورچه ی راهنما جدول مسیریابی را با توجه به جدول فرومون و انتخاب گره با بالاترین احتمال در جدول فرمونی، به روز رسانی می کند. به عبارت دیگر اگر گره یک گره داخلی باشد، پس مورچه ی راهنما جدول مسیریابی را به روزرسانی می کند و این گره به عنوان یک عامل حمل و نقل عمل( forwarder) می کند.

تغییر توپولوژی شبکه

یک مورچه ی راهنما وقتی ایجاد می شود که توپولوژی شبکه تغییر می کند. مورچه ی راهنما می تواند داده ها را انتقال دهد و یک مسیر بهینه ی جدید انتخاب کند. این بخش به دو مورد را مورد بررسی قرار می دهد. یکی جایی که گره تغییر کرده یک گره داخلی باشد و زمانی که گره تغییر کرده، یک گره مرزی باشد.
حالتی که گره تغییر کرده، یک گره داخلی باشد
وقتی یک گره داخلی حذف گردد، یک راه جدید با استفاده از جدول شبکه ی داخلی ایجاد می شود و این راه بوسیله ی مورچه ی راهنما مورد استفاده قرار می گیرد تا بدین وسیله جدول مسیریابی به روز رسانی گردد. بنابراین کشف مسیر نیازمند انجام عملیات جدید نمی باشد. مورچه ی راهنما در زمانی که در مسیر اولیه به یک گره برسد، کشته می شود و با این کار، انتقال بسته ی عمومی ری استور( restore) می شود.
شکل 3 مثالی از این مورد را نشان می دهد. گره A دارای یک مسیر به گره C از طریق گره B است و گره B یک گره داخلی از گره A است. وقتی گره B منقطع می شود، گره A گره دیگری را به گره C پیدا می کند( این کار را با استفاده از نگاه کردن به جدول شبکه ی داخلی انجام می دهد).
در شکل 4 گره A یک مسیر جدید به گره C را از طریق گره D کشف می کند و بنابراین یک مورچه ی راهنما ایجاد می شود که به این مسیر راهنمایی می شود. مورچه ی راهنما جدول مسیریابی را در گره های A و D به روز رسانی می کند. این فرایند زمان پردازش را می کاهد( با حذف تکرار در فرایند کشف مسیر).
حالتی که گره تغییر کرده، یک گره مرزی باشد
یک مورچه ی راهنما همچنین در زمانی ایجاد می شود که یک گره مرزی حذف شود. این مورچه ی راهنما مناسب ترین گره مرزی جایگزین را در جدول فرومون جستجو می کند، سپس جدول مسیریابی را در مسیر جدید به روز رسانی می کند.
مثال زیر این سناریو را شرح می دهد. در شکل 5 گره C شکسته می شود و گره A به گره مرزی تبدیل می شود. بنابراین گره A باید یک مسیر جدید به گره F پیدا کند.
مورچه ی راهنما سپس ایجاد می شود و در جدول فرومون گره A جستجو می کند تا یک گره بهتر برای مقصد پیدا کند. با توجه به شکل 6، فرض شده است که گره E بوسیله ی این مورچه پیدا شده است. جدول شکل 6 بخشی از جدول فرومون گره A است و نشان می دهد که گره F می تواند از طریق گره E به مقصد برسد. ID گره E در فیلد آدرس دهی مقصد واقعی و با توجه به فرمت مورچه ی راهنما، پر شده است. روش بالا به طور تکراری در زمانی انجام می شود که مورچه ی راهنما به گره E می رسد( و تا زمانی ادامه می یابد که به گره F برسد). مقادیر فرومون برابر 0.6 و 0.4 است( همانگونه که در شکل 6 لیست شده است). ARAMA تنها در زمانی گره همسایه را می شناسد که برخی گره ها نقل مکان کنند. بنابراین اگریک گره شکسته شود و فاصله ی آن دو پرش دورتر باشد، پس نمی تواند اطلاعات کافی جمع آوری کند و ممکن است نیازمند ارسال مجدد بخش کشف مسیر باشد.

آنالیزها و مقایسه ها

این بخش JARA و ARAMA را با استفاده از استنتاج زمان کشف مسیر، اوور هید( overhead) و مسیر، مقایسه و آنالیز می کند. در اینجا P نشاندهنده ی گروهی از تمام مسیرها در توپولوژی است. مسیر یک توالی محدود از اتصال ها در توپولوژی است که در اینجا نشاندهنده ی پرش است.

زمان کشف مسیر

این بخش زمان های کشف مسیری را که بوسیله ی الگوریتم پیشنهادی و ARAMA( در مسیر یکسان) بدست آمده است را مقایسه می کند.


که در اینجا نشاندهنده ی زمان پردازش ARAMA است که شامل زمان مصرف شده برای جستجو در جدول فرومون، جستجوی جدول فرومونی احتمالاتی و جمع آوری اطلاعات در مورچه ی پیشرو و تبدیل مورچه پیشرو به پسرو است. نشاندهنده ی زمان پردازش JARA است که شامل و زمان مصرف شده برای جستجوی در جدول مسیریابی است. T_t نشاندهنده ی زمان تبدیل است. T_oaزمان کشف مسیر ARAMA است و T_ja بیان کننده ی زمان کشف مسیر JARA است.
زمان مصرف شده برای جستجو در جدول مسیریابی بسیار کوچک است و جدول مسیریابی به سهولت برای یک سنسور تکی، بهینه می شود. بنابراین در این مطالعه فرض شده است که .

سربار( overhead) کشف مسیر

این بخش سربار کشف مسیر دو پروتکل را با هم مقایسه می کند. یک مسیر تصادفی برای مقایسه ی سربار تغییر می کند( OH).


که در اینجا 〖OH〗_oنشاندهنده ی سربار ARAMA است. 〖OH〗_jسربار JAARA است. λ نشاندهنده ی اندازه ی بسته ی مورچه به استثنای گره های میانجی است. و نشاندهنده ی طول آدرس می باشد.
اگر JARA دارایباشد، پس کشف مسیر نمی تواند مورد استفاده قرار گیرد. زیرا این گره ها گره های داخلی هستند که می تواند بسته ها را به طور مستقیم به مقصدهایشان انتقال دهند. از این رو سر بار ARAMA به طور واضح بزرگتر از سربار JARA است.
به خاطر اینکه توپولوژی یکسان است، مجموعه ی تمام مسیرهای JARA باید متعلق به مجموعه ی ARAMA باشد. اگر هر مسیر در ARAMA بتواند از الگوریتم JARA برای بدست آوردن مسیر کوتاه تر استفاده کنند، پس JARA می تواند همیشه مسیر بهتری از ARAMA باشد. ما ابتدا، تمام پردازش ها را با استفاده از ρ=2 توضیح خواهیم داد. که در اینجا P نشاندهنده ی مجموعه ی همه ی مسیرها در توپولوژی G، می باشد. که نشاندهنده ی پرش است. فرض شده است که یک مسیر تصادفی برای ووجود دارد. شکل 7 این مسیر را نشان می دهد. یک مسیر جدید B در زمانی که پردازش مسیر با استفاده از JARA انجام می شود، ایجاد شده است. اگر باشد، و عضو گره مرزی a_k باشد، پس یک مسیر S باید به عنوان ، عضو گره ی مرزی وجود داشته باشد( و بنابراین یا از این رو)، مسیر T می تواند بوسیله ی مسیر S جایگزین گردد تا بدین وسیله مسیر جدید B: ایجاد گردد. از این رو این مسیر دارای ویژگی های است الگوریتم پیشنهاد شده می تواند یک راه کوتاه تر از ARAMA ایجاد کند.

شبیه سازی

این بررسی دو فاکتور را برای نشان دادن توپولوژی در نظر گرفته است که مقیاس و دانسیته نامیده می شوند. 4 توپولوژی شبکه( یکی بزرگ، دیگری کوچک، سومی خلوت و دیگری شلوغ) برای نشاندادن توپولوژی طراحی شده است. JARA و ARAMA برای این 4 توپولوژی اجرا شده اندتا بدین وسیله زمان کشف مسیر و سربار تعیین شود. شبیه سازی برای ρ=2 مورد استفاده قرار گرفت و مشخص شد که توپولوژی ها برای JARA مناسب تراست.

مورد توپولوژی

توپولوژی 1 : 40 گره و 57 لینک: این توپولوژی دارای 40 گره و 57 لینک است( شکل 8). این توپولوژی کوچک و خلوت است. جستجوی مسیر سریع و حفظ توپولوژی نسبتا ساده است.
توپولوژی 2: 40 گره و 91 لینک: این توپولوژی دارای 40 گره و 91 لینک می باشد( شکل 9). این توپولوژی کوچک تر و متراکم تر از توپولوژی 1 می باشد. جستجوی مسیر سریع تر است اما حفظ این توپولوژی پیچیده تر است.
توپولوژی 3: 80 گره و 115 لینک: این توپولوژی دارای 80 گره و 115 لینک است( شکل 10). این توپولوژی بزرگ و خلوت است و بنابراین جستجوی مسیر کند اما حفظ توپولوژی ساده تر است.
توپولوژی 4: 80 گره و 175 لینک: این توپولوژی 80 گره و 175 لینک دارد( شکل 11). این توپولوژی بزرگ و شلوغ است. جستجوی مسیر کند است و حفظ توپولوژی پیچیده است.

زمان متوسط کشف مسیر

کشف مسیر برای بدست آوردن زمان متوسط هر مورچه، شبیه سازی شد. 1 تا 10 مورچه برای شبیه سازی فرستاده شده است.
توپولوژی 1: در شکل 12، محور X نشاندهنده ی تعداد مورچه و محور y زمان متوسط کشف مسیر هر مورچه است. همانگونه که در شکل 12 آشکار می شود، JARA زمان کمتری نسبت به ARAMA، برای اجرای فرایند کشف مسیر، مصرف می کند.
توپولوژی 2: این توپولوژی 40 گره دارد. شبیه توپولوژی 1 است اما شلوغ تر. شکل 13 نشان می دهد که هر دو خصوصیت یکسان دارند اما در دانسیته ی گره ی بالا، JARA می تواند مناسب تر از ARAMA باشد.
توپولوژی 3: همانگونه که در شکل 14 آشکار شده است، JARA زمان اجرای کمتری نسبت به ARAMA برای کشف مسیر مصرف می کند.
توپولوژی 4: این توپولوژی شبیه توپولوژی 3 است که 80 گره دارد اما دانسیته ی گره آن بالاتر است. شکل 5-7 توپولوژی های 3 و 4 را نشان می دهد که دارای ویژگی های یکسانی هستند. در توپولوژی 4، JARA مناسب تر از ARAMA است( به دلیل دانسیته ی گره بالاتر).
این شبیه سازی ها نشان می دهد که زمان کشف مسیر وقتی توپولوژی شبکه از لحاظ اندازه بزرگتر می شود، طولانی تر می شود. JARA زمان کمتری نسبت به ARAMA در توپولوژی 1و 3 مصرف می کند اما شکل 12 و 14 این مسئله را نشان می دهد که شکاف میان دو خط، قابل توجه نمی باشد. در عوض، شکاف میان دو خط در شکل 13 و 15 بزرگتر از شکل های 12 و 14 است که این مسئله نشاندهنده ی این است که JARA می تواند کشف مسیر را سریع تر از ARAMA انجام دهد.

سربار کشف مسیر

سربار هر مورچه برای کشف مسیر فاکتور مهمی محسوب می شود. 5 مورچه برای اجرای کشف مسیر در توپولوژی 1 و2 مورد استفاده قرار گرفت( به دلیل اندازه ی کوچک این توپولوژی ها). به دلیل اینکه توپولوژی های 3 و 4 بزرگترند، کشف مسیر بر روی آنها با استفاده از 10 مورچه انجام شد.
توپولوژی 1: 5 مورچه برای اجرای فرایند کشف مسیر مورد استفاده قرار گرفت. سربار کشف مسیر برای هر مورچه در شکل 16 ثبت شده است.
توپولوژی 2: 5 مورچه برای اجرای فرایند کشف مسیر مورد استفاده قرار گرفت. سربار کشف مسیر برای هر مورچه در شکل 17 ثبت شده است.
توپولوژی 3: 10 مورچه برای اجرای فرایند کشف مسیر مورد استفاده قرار گرفت. سربار کشف مسیر برای هر مورچه در شکل 18 ثبت شده است.
توپولوژی 4: 10 مورچه برای اجرای فرایند کشف مسیر مورد استفاده قرار گرفت. سربار کشف مسیر برای هر مورچه در شکل 19 ثبت شده است.
مورچه ی پیش رو در زمانی که گره بعدی خود را انتخاب می کند، هم اندازه و هم سربار را افزایش می دهد، در حالی که مورچه ی پسرو در زمانی که به نقطه ی شروع خود باز می گردد، هم اندازه و هم سربار را کاهش می دهد. پیک های موجود در شکل 16 -19 نشاندهنده ی فروان ترین تعداد مورچه های پیش رو و پس رو است که به نزدیکی گره مقصد رسیده اند.
سربار کشف مسیر JARA و ARAMA سپس محاسبه شد. 6 روش مختلف شبیه سازی شد( در جدول 2 نشان داده شده است). نتایج تجربی به طور واضح نشان داد که سربار در زمانی که تعداد مورچه های و اندازه ی شبکه افزایش می یابد، افزوده می شود. علاوه بر این، نتایج تجربی نشان دهنده ی این است که در توپولوژی های متراکم، ARAMA دارای سربار بیشتری نسبت به JARA است.
به طور خلاصه باید گفت که نتایج تجربی نشان داد که الگوریتم پیشنهادی، کشف مسیر را در زمان کمی انجام می دهد و دارای سربار کشف مسیر کمتری نسبت به ARAMA دارد مخصوصا در توپولوژی های متراکم (شکل 20).

نتیجه گیری

این کار یک الگوریتم مسیریابی مورچه ی در حال پریدن( JARA) را برای شبکه ی ad-hoc سیار ارائه داده است. JARA مزیت های مسیریابی فعال و انفعالی را ترکیب کرده است و همچنین الگوریتم مسیریابی را برای ad-hoc سیار ( ARAMA) بهبود بخشیده است. در الگوریتم پیشنهادی، هر گره یک ناحیه را نگهداری می کند و هر مورچه می تواند در یک ناحیه پرش کند. JARA ی پیشنهادی زمان کشف مسیر و سربار کشف مسیر را کاهش می دهد مخصوصا در توپولوژی های متراکم.