مقاله شبکه های mobile ad hoc

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

  مقاله شبکه های mobile ad hoc دارای ۶۸ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله شبکه های mobile ad hoc  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله شبکه های mobile ad hoc،به هیچ وجه بهم ریختگی وجود ندارد

---

بخشی از متن مقاله شبکه های mobile ad hoc :

شبکه های mobile ad hoc

۱مقدمه
شبکه های mobile ad hoc به نحو چشمگیری رو به افزایش هستند به دلیل توانایی آنها در سازماندهی خودکار یک سری از Snode درون شبکه بدون اینکه نیازی به زیرساختهای از قبل تشکیل شده شبکه باشد. یک MANET به node موبایل این امکان را می‌دهد که به nodeهای دیگری که در محدوده انتقالی مستقیم نیستند دستیابی پیدا کند. این عمل با استفاده از multi-hop route از میان nodeهای واسطه کامل می شود که به معنای آن است که هر node در یک MANET لازم است که بصورت یک router عمل کند. عمل routing در یک MANET ذاتاً پیچیده است و نیاز به روشهای متفاوتی نسبت به آنچه که در زیر ساختهای اینترنتی ثابت در قدیم مورد استفاده قرار می گرفت، دارد. یک مرحله عمده در پروتکل های routing در MANETهای پروتکل rouing محلی است. (LAR)

پروتکل های LAR محلی شدیداً وابسته و متکی به یک سیستم تدارکاتی محلی هستند تا ذخیره، توزیع و query nodeها را ممکن ساخته و تشکیل موقعیت آنها را به روز سازد. پروتکل های routing و سیستمهای تدارکاتی محلی عموماً بعنوان زیر سیستمهای منفصل (disjoint) عمل می کنند. بطور نمونه یک query محلی قبل از انتقال داده های اصلی صورت می گیرد. مسئله ای که در این روش با آن روبرو خواهیم بود این است که query محلی برای کامل شدن وقت

بیشتری می گیرد. این نه تنها به تأخیر routing و سیستمهای تدارکاتی محل عموماً بعنوان زیر سیستمهای منفصل (disjoint) عمل می کنند. بطورنمونه یک query محل قبل از انتقال داده های اصلی صورت می گیرد. مسئله ای که در این روش با آن روبرو خواهیم بود این است که query محلی برای کامل شدن وقت بیشتری می گیرد. و این تنها به تأخیر تأخیر routing می انجامد، بلکه اطلاعات محلی بدست آمده ممکن است تا آن زمان و حتی در طول انتقال داده های اصلی تاریخ گذشته شوند. بنابراین یک روش ترکیبی از routing و query بهره گیرد، بهتر می‌باشد.

در این جزوه، ما یک سیستم ترکیبی از location management و routing ارائه می دهیم که بر مشکلاتی که قبلاً ذکر شد فائق آید. ویژگیها و امتیازهای عمده این سیستم عبارتند از:

۱location query و location-aided packet eouting با راندن داده ها به سمت location query همزمان با هم صورت می گیرند.
۲اطلاعات محلی یک mobile node تنها در server محلی نزدیک خواهد شد و این به روز بودن سریعتر و پایین تر overhead را تضمین می‌کند و در مقایسه، در بسیاری از سیستمهای دیگر، موقعیت یک node در یک server دور ثبت می شود که احتمال تاریخ گذشته شدن داده ها و overhead بالاتر افزایش می یابد.
۳این روش نزدیک ترین راه است بدون اینکه overhead عمده ای داشته باشد. از آنجا که database در بردارنده اطلاعات محلی (location) در میان serverهای

محلی پخش می شود، مسئله ثبت و ذخیره (storage) برای هر server کمتر می شود. این با سیستمهای سنتی که از database مرکزی استفاده می کردند، در تضاد است.

بقیه جزوه به صورت زیر سازمان یافته است: بخش ۲ شامل بررسی کوتاهی از کارهای مرتبط می‌باشد. بخش ۳ جزئیات ترکیبی location management و سیستم routing را شرح می‌دهد. در بخش ۴ و ۵، نحوه اجرای سیستم بصورت تئوریک آنالیز و ارزیابی خواهد شد. و بالاخره ۶ به نتیجه گیری می پردازد.
Related work

الگوریتم های routing در یک MANET می توانند به پروتکل های reactive و proactive تقسیم بندی شوند. در روش proactive اطلاعات routing در بردارنده مسیرهایی به همه مقاصد ممکن است در هر mobile node ذخیره می شود که ممکن است به دلیل قطع ارتباط و تغییرات topology در MANET از رده خارج شوند (out date شوند). در چنین مواردی روش reactive ترجیح داده می شود. در این روش یک مسیر multi-hop از فرستنده به گیرنده فقط طمانی که مورد نیاز است، ساخته می‌شود. بررسی های بیشتر در مورد این الگوریتم های routing می تواند در ۲۵/۲۱ صورت گیرد. یک دسته مهم از پروتکل های reactive از اطلاعات محلی درباره mobile node برای هدایت سازه ها مسیر استفاده می کنند.

در این الگوریتمها، اطلاعات محلی مقصد برای محدود کردن جریان ها به ناحیه کوچکی استفاده می شود به این ترتیب در مقایسه با flooding (جریان سیل آسا)overhead و efficiency(کارآیی) بهتر انجام می گیرد. الگوریتمهای LAR موقعیت مقصد را با استفاده از سیستم تدارکات محلی دارا هستند در اصل جدا از مکانیسم routing است. طراحی سیستم های تدارکاتی محلی کارا و منظم توجه قابل ملاحظه ای را در سالهای اخیر به خود جلب کرده است. در تمام این

طرحها location query قبل از routing داده های اصلی صورت می گیرد. چنان که ذکر شد این زمان تأخیر را برای انتقال داده های کوچک افزایش خواهد داد و ممکن است اطلاعات محلی (location) از زمانی که انتقال داده ها آغاز می شود، outdate شود. این مسئله بوسیله محققین دیگر مورد توجه قرار گرفته است. بخصوص در سیستم EASE سعی شده که این اشکال برطرف شود به این صورت که هر mobile node لازم است که آخرین node که با آن مواجه شده ثبت کند.(pocket) بسته ها با استفاده از اطلاعات recordها به سمت مقصد رانده می شوند. به هر حال EASE برای کار کردن متکی به mobility diffusion است که به این معنا است که وقتی node mobility پایین است نمی تواند packetها را به جلو براند.

در بخش ۵ اطلاعات محلی node ها برای ساخته دسته از شاخه های multicast برای تحویل بسته های کافی مورد استفاده قرار می گیرد. آنها از موقعیتهای هندسی مقاصد برای محاسبه این شاخه ها استفاده می کنند. با هدف به حداقل رساندن هزینه عرض باند (band width) کلی، توزیع بسته های روی هم، یک ساختار قابل انعطاف ایجاد می‌کند که انتقال و routing و processing سطح کاربر عمدی را انجام می‌دهد. اگرچه این جزوه به مسئله دیگری متفاوت با آنچه

مربوط به ماست می پردازد، مشاهده می کنیم که بعضی مشابهت ها در نگرشها و روشهای ما وجود دارد. برای مثال، روشی که آنها overlay trees (قطعات پوششی) را می سازند مشابه است با روشی که ما server. Overlay محلی را می سازیم. آنها یک بشما یا طراح کلی بروز دارند در طول trees قطعات و سیستم ترکیبی پیشنهادی ما نیز به این نوع طرح در میان serverهای محلی نیاز دارد.

در شبکه های سیمی (wired)، روش landmark routing یک hierachy از overlays بر روی شبکه زیرین ایجاد می‌کند چند node به تناوب انتخاب می شوند تا گروهی از node ها را در سطوح مختلف بر اساس radius ناحیه یا منطقه معرفی کنند. آدرس hierarchial از قبل تعریف شده از هر node وضعیت آن را در hierchy را در سطوح مختلف بر اساس radius ناحیه یا منطقه معرفی کنند. آدرس hierachial از قبل تعریف شده از هر node وضعیت آن را در hierachy منعکس کرده و به

یافتن یک route در آن کمک می‌کند. هر node، routeهایی را در همه nodeهای موجود در وضعیت hier خود می شناسد. کم و بیش هر node routeهایی را در landmark های مختلف در سطوح گوناگون می شناسد. حرکت به جلو بسته ها با landmark hierarchy بصورت مداوم و مسیر بتدریج با نزدیک شدن بسته packet به مقصد خود، از سطح بالای hierarchy به سطوح پایین تر صاف تر و بهتر می شود. نظریه hierachial landmark routing همچنین در محیط شبکه های ad hoc استفاده می شود. بهر صورت این روش یک انتقال و جابجایی مستقیم از شبکه های سیمی است و هیچ اطلاعات محلی برای هدایت packet routing استفاده نمی شود.

دو عقیده مهم که روش ما را حمایت کرده و از آن دفاع می‌کند استفاده از traingulation delaunay و فیلترهای Bloom است. بر خلاف طرحهای دیگری بر اساس Delaunay هستند، سیستم ما به نیازی ندارد تا محاسبه شود، چرا که یک Mobile node می تواند به آسانی نزدیک ترین server را بوسیله beacon که از server فرستاده می شود، تعیین کند. در هر حال، استفاده ما از فیلترهای bloom بوسیله سیستم آدرس IP در اینترنت ایجاد شده است. اولین قسمت هر آدرس IP، زیر شبکه ای را تعیین می‌کند که آدرس IP به آن تعلق دارد. وقتی که یک بسته (pocket) به یک route می رسد، فقط کافی است که router جدول routing آن را

در آدرس زیر شبکه مقصد جستجو کند. بنابراین همه packetهایی که مقصدشان یک زیر شبکه است می توانند در همان مسیری حرکت کنند که توسط همان آدرس زیر شبکه تعیین شده است. اگرچه این hierarchial routing برای اینترنت مؤثر و لازم است، مستقیماً نمی تواند برای استفاده در محیط شبکه ad hoc انتقال داده شود. مسئله عمده این است که در یک شبکه ad hoc، nideهای موجود در منطقه حقیقی یکسان، پیش آدرس IP یکسانی را آن چنان در اینترنت است ندارند. این مسئله در سیستم پیشنهادی ما با استفاده از فیلترهای bloom حل شده است.

۳the integrated location management & routing system
روش ترکیبی routing system و management location طراحی شده تا:

از نزدیکی بین node و serverهای محلی نزدیک استفاده کرده تا اطلاعات محلی آن را ذخیره کند و در نتیجه را قادر سازدو
به اجرا یا ذخیره مرکزی اکتفا نکند. بنابراین در مقابل قطع ارتباط با node رایج که از ویژگیهای MANET است مقاوم می‌باشد.
این دو نکته بالا توسط یک طرح طبقه بندی شده بر اساس Delaunay traingulation انجام می شوند.

Overhead تبادل اطلاعات را در میان serverهای محلی با فشرده کردن اطلاعات به حداقل می رساند.
این عمل بوسیله یک طرح پیام بر، بر اساس فیلترهای bloom انجام می شود. جزئیات سیستم ترکیبی ما در زیر شرح داده شده است.
۱-۳ Delaunay traingulation overlay network

در سیستم ترکیبی ما، زیر گروه nodeها در MANET به صورت serverهای محلی طراحی شده است. (در تصویر ۱ تا بصورت نقطه های بزرگ نشان داده شده است). لایه بالایی در تصویر ۱ یک شبکه overlay است که از پیوندهای حقیقی بین serverهای محلی تشکیل شده است. این پیوندها (یا اتصالات) در شبکه overlay با مسیرهای underlay در شبکه ad hoc مطابقت دارد. این اتصالات با استفاده از یک پروتکل location- aided برقرار و حفظ می شود. از آنجا که مسیرهای زیرین (underlying) بصورت دینامیک با توجه به node mobility تنظیم می شود، مسئله فشردگی و ترافیک کمتر می شود. عملکرد و نقش شبکه overlay به صورت زیر است:

۱serverهای محلی برای تبادل اطلاعات محلی خود و کنترل پیامهای دیگر با یکدیگر ارتباط دارند.
۲شبکه overlay همچنین در طول routing مورد استفاده قرار می گیرد تا مسیرهایی را در میان serverهای محلی برقرار سازد. مسئله این که چگونه این serverهای محلی انتخاب شوند از بحث این مقاله خارج است. ما فقط به این نیاز داریم که serverهای محلی شدیداً و بصورت یکنواخت در شبکه ad hoc پخش شوند. چندین پروتکل از جمله پروتکل انتخابی kand mark در طرح چندگانه landmark routing و الگوریتم انتخابی گروه GDMS می توانند در انتخاب serverهای محلی مورد استفاده قرار گیرند.

استفاده از serverهای محلی نوع عمده از شبکه های ad hoc مورد توجه قرار گرفته اند: battle field، vehicles و campus. شبکه ad hoc compus از nodeهای quasi-static تشکیل شده که از داخل یک دفتر کار یا در اطراف یک نقطه یا محل گردآوری خاص (مثل یک کافی شاپ) حرکت می کنند. روشن است که EASE در چنین شبکه low mobility به خوبی کار نمی کند، به دلیل اینکه بر اساس لیست آخرین nodeها مواجه شده عمل می‌کند. داشتن یک server محلی برای یک

دفتر کار یا محل گرداوری برای محیط های low mibility منطقی تر و راحت تر است. شبکه های ad hoc battle field سربازها و تانکهایی دارند که قویاً به همان سمت در حرکتند. این شبکه ها شباهت زیادی با شبکه adhoc vehicular دارند در جایی که vehicle ها با سرعت زیادی حرکت می کنند. در این شبکه های ad hoc، داشتن serverهای محلی سودمند است چرا که محل ها یا موقعیت های مربوطه بین nodeهای در حال حرکت و serverها به شدت حفظ می شوند. مجدداً EASE در چنین محیطی به خوبی کار نمی‌کند.

یک server محلی پیوندهایی با server محلی نزدیک دارد با آن در delaunay triangulation موجود در serverهای محلی در ارتباط است. Delaunay traingulation یک دسته از nodeهای A

استفاده از delaunay traingulation مزیتهای زیر را دارد
اول اینکه میزان متوسط یک server محلی در یک شبکه overlay کم یا (کوچک) است. از آنجا که کناره های delaunary traingulation تا ۳m-3 محدود می شود که در اینجا m تعداد serverهای محلی است، میزان متوسط serverهای محلی تا ۶ می‌رسد. دوم اینکه تضمین می شود که اتصالات حقیقی فقط بین serverهای محلی در ارتباط نزدیکی با هم هستند وجود داشته باشد. این اطمینان می‌دهد که مسیرهای مطابق با هم در شبکه underlay ad hoc از نظر تعداد hopها کوتاه بوده و حفظ مسیرها را آسانتر می سازند.

Voronoi cell virtual zone
منطقه حقیقی (virtual zone) به هر server محلی اطلاق می شود که با voronoi cell هر server محلی مطابقت دارد.(تصویر ۲)
بنابراین هر server محلی، اطلاعات محلی همه nodeهای درون voronoi cell خود را در بر دارد. با توصیف دیاگرام voronoi تضمین می شود به اطلاعات محلی یک node به نزدیک ترین server محلی فرستاده شود. یک mobile node بصورت تناوبی اطلاعات محلی خود را به نزدیک ترین serverهای محلی k می فرستد که در

آنجا K یک پارامتر سیستم است. وقتی که k=1 باشد یک server محلی، اطلاعات محلی همه mobile nodes را در voronoi cell خود ذخیره می‌کند. مقدار بیشتر K می تواند برای کمتر کردن مشکلات موجود داده ها مورد استفاده قرار گیرد، چرا که اطلاعات محلی در serverهای محلی دیگر هنوز وجود دارند حتی اگر یک server محلی fail شده باشد. در بخشهای ۴ و ۵ با تجزیه تئوریک و آزمایشات تجربی نشان خواهیم داد که k=2 یا ۳ محاسبه دقیقی از تبادل بین موجودیت داده ها و ذخیره (storage) ارائه خواهد داد. در زیر مجموعه های زیر ما با فرض اینکه برای سهولت کار k=1 باشد سیستم خود را شرح خواهیم داد. هم serverهای

محلی و هم normal nodes در سیستم، mobile متحرک هستند. Serverهای محلی به فرستادن beacon packets ادامه می دهند تا با استفاده از الگوریتم flooding/ goossipinمحدود شده، اطلاعات محلی خود را پخش کنند. به این ترتیب هر node نرمال قادر است به نزدیک ترین server محلی را با محاسبه مساحت Euclidean بین آنها تعیین کند. بر اساس تئوری گراف، گذشتن voronoi cell border می تواند با تغییر نزدیک ترین serverهای محلی دریافته شود.

وقتی که یک mobile node از عرض یک voronoi cell border حرکت می‌کند که می توانست بوسیله حرکت خودش یا serverهای محلی ایجاد شده باشد، یک پیام join فرستاده و اطلاعات محلی خود را به server محلی جدید حمل می‌کند. همزمان با آن یک پیام leave به server محلی قبلی فرستاده می شود که در نتیجه اطلاعات محلی خعفیشفثی مطابق با آن از database server’s قبلی می تواند حذف گردد.

۳‌۳ فرستادن پیامهای اطلاعاتی با استفاده از فیلترهای bloom
فیلترهای bloom راه مؤثر و مفیدی در توصیف مجموعه های set هستند. یک فیلتر bloom یک بردار یک بینی با طول w از مجموعه (یا خانواده)ای با تابع های درهم و آشفته است که هر یک از آنها از اجزای مجموعه مربوط بصورت تابعی در (O.W) طرح می شود. برای توصیف یک دسته (set)، هر جزء در آن مجموعه بوسیله دسته توابع آشفته رانده می شود و bitها در پرداز که با نتایج آشفتگی مطابقت دارند، مجموعه هستند، برای تعیین اینکه آیا مجموعه ارائه شده توسط فیلتر bloom عنصر خاصی را در بردارد یا نه، آن عنصر توسط توابع آِفته (hash) و Bitهای مربوطه در فیلتر بررسی خواهد شد. اگر هریک از bitها تنظیم نشده باشد،

مجموعه ارائه شده قطعاً آن عنصر را در خود ندارد (و به مثال تصویر ۲ توجه کنید) اگر همه bitهای چک شده منظم باشند، مجموعه احتمالاً آن عنصر را دارا است. یک احتمال غیر صفر هنوز وجود دارد که نبوده است. این حالت positive flash (پشت خطا) نامیده می شود. میزان مثبت خطای یک فیلتر bloom یک تابع دقیق از عرض آن، تعداد توابع آشفته و اهمیت مجموعه ارائه شده است. ما مسئله به حداقل رساندن میزان مثبت خطا را در بخش ۴ بررسی خواهیم کرد.

از طرح ترکیبی ما هر server محلی از یک فیلتر bloom استفاده می‌کند تا مجموعه گره های mobile را که به کار می گیرد ارائه دهد.هر server اطلاعات محلی گره های موبایل (متحرک) را حفظ می‌کند. که در اینجا N تعداد گره های موجود در شبکه است. برای سهولت جستجوها (query) یا انتقالها، اطلاعات محلی بدست آمده از یک server لازم است در دیگر جاها هم وجود داشته باشد یک روش اصلی، سرایز کردن فیلتر bloom به serverهای دیگر می‌باشد. از آنجا که هر server فیلترهای bloom همه serverهای دیگر را در بردارد، وقتی که یک بستر می رسد، server به آسانی می تواند تعیین کند که کدام server اطلاعات مقصد را دارد. فیلترهای bloom M را حفظ کند که در اینجا m تعداد serverهای محلی در شبکه ad hoc است.

طرح ما مستلزم این است که هر server محلی فقط فیلترهای bloom d را حفظ کرده باشد که در اینجا d یا درجه میزان server در شبکه overlay است. از آنجا که میزان متوسط server محلی تا ۶ محدود می شود، این به مقدار زیادی تقاضا انبار را کاهش می‌دهد.

هر server محلی یک فیلتر bloom با هر اتصال بعدی در شبکه overlay هماهنگ می‌کند. وقتی یک server محلی لازم است که فیلتر bloom خود را پخش کند، فیلتر bloom را در امتداد کوتاهترین مسیر در شبکه overlay می فرستد. هربار که فیلتر bloom به server محلی دیگر A از راه یک اتصال خاص (A، B) می رسد، فیلتر bloom مربوط به آن در اتصال بعدی (B، A) serverمحلی A با میانگین عمل این دو براورد می شود.

تصویر ۳ مثالی از توزیع فیلتر bloom را نشان می‌دهد. Server محلی اطلاعات محلی را از یک گروه mobile “۱۴۳۸۹۰۱” در بر دارد و فیلتر bloom آن bitهای مطابق با آن را (۷، ۳،۰) تا ۱ تنظیم می‌کند. وقتی که فیلتر bloom در امتداد کوتاهترین مسیر پخش می شود همچنانکه بوسیله فلشها نشان داده شده است، فیلترهای bloom اتصالات بعدی (up date) به روز می شوند:
( ) و ( )و ( ) و و
توجه کنید که بعد از server محلی فیلتر bloom در طول کمانهای نقطه چین پخش می کند، فیلتر bloom مربوط به اتصال براورد فیلترهای bloom و است.
وقتی که گره های mobile جدید به voronoi cell یک server محلی وارد می شوند. فیلتر bloom مطابق با آن لازم است با روشن کردن bitهای خرد شده (update) به روز شود. Server فقط باید bitهای تغییر یافته در فیلتر bloom را محاسبه کرده و آنها را به serverهای محلی دیگر بفرستد. این عمل differentiated update

خوانده می‌شود. توجه به این نکته مهم است که وقتی که یک گره mobile یک voronoi cell را ترک می کند، bitهای مطابق با آن به آسانی نمی توانند reset (تنظیم مجدد) شوند. به دلیل اینکه گره های دیگر ممکن است به آن bitها تجزیه شده باشند. برای برطرف کردن این مسئله، یا فیلتر bloom باید نیاز داشته باشد که به طور تناوبی بازسازی شود و یا یک counter (شمارش گر) با هر Bit از فیلتر bloom در ارتباط باشد. روش دوم (فیلتر bloom شمارشی) نامیده می شود.

۴‌۳ location- aided routing
انتقال یک بسته از فرستنده S به مقصد D به سه مرحله تقسیم می شود: اول فرستنده بسته را به نزدیک ترین server محلی می فرستد، server محلی با کمک فیلترهای bloom تعیین می‌کند که به کجا این بسته را در شبکه coverlay با پیرویهای محلی تشکیل شده انتقال دهد. قدم به قدم، بسته به نزدیک ترین پیرور محلی مقصد از راه شبکه overlay به جلو رانده می شود . سرانجام یک سرور محلی بسته را به به سمت مقصد می راند. یک پروتکل انتقالی محلی (LRP) در اولین مرحله مورد استفاده قرار می گیرد. (از فرستنده به سرور محلی خودش) و در مرحله سوم (از سرور محلی به مقصد)پروتکل سرور محلی داخلی دیگر

(ILSP) برای انتقال در بین سرورهای محلی شبکه overlay استفاده می شود که با تبادل اطلاعات با استفاده از فیلترهای bloom هدایت می شوند. بعنوان مثال در تصویر ۱ وقتی که گره مبدأ S لازم است پیامی را به گره مقصد D بفرستد، پیام اول به نزدیک ترین سرور محلی با استفاده از پروتکل LRP فرستاده می شود. پیام سپس در شبکه overlay به سمت سرور محلی که در بردارنده اطلاعات محلی گره مقصد D است منتقل می شود. پروتکل LRP مجدداً به کار گرفته می شود تا پیام را از به D انتقال دهد. مسیر واقعی در شبکه Overlay و مسیر مطابق با آن در شبکه underlay به وسیله فلش هایی در تصویر ۱ نشان داده شده اند.

از آنجا که هر سرور محلی اطلاعات محلی خود را به همه گره های mobile در voronoi cell خود توزیع می کند، پروتکل LRP می تواند از اطلاعات محلی برای انتقال و هدایت بسته استفاده کند. بنابراین هر پروتکل LAR می تواند بکار گرفته شود. ما از پروتکل پیشنهادی LAR در ۱۷ استفاده می کنیم.

در پروتکل ILSP، هدف انتقال بسته به سرور محلی در بردارنده اطلاعات محلی مقصد است. وقتی که یک سرور محلی بسته ای را از یک گره موبایل در voronoi cell خود با آدرس مقصد (desti- name) دریافت می کند، اول فیلتر bloom خود را چک می‌کند که ببیند آیا اطلاعات محلی مقصد در آنجا هست. اگر باشد پایگاه (data base) محلی در جریان گذاشته شده و بسته با استفاده از پروتکل LRP به سمت مقصد رانده می شود. در غیر اینصورت سرور محلی فیلترهای bloom همه اتصالات بعدی خود را بررسی می‌کند. اگر یکی از فیلترها مطابقت داشته باشد، بسته به سمت کناری اتصال به جلو رانده می شود. اگر چندین اتصال مطابقت داشته باشند، اولین انتخاب می شود. بسته در همان راه باقی می ماند تا به هدف مورد نظر سرور محلی برسد.

بعنوان مثال به تصویر ۳ توجه کنید: فرض کنید که یک گره mobile در voronoi cell، لازم است که یک بسته را به گره دیگر “adhoc. Node1.nk” بفرستد. در اینجا فرض می کنیم که “ad hoc.node.1.hk” توسط سرور محلی به کار گرفته شده و به تجزیه شده است. گره منبع (یا مبدأ source) اول بسته را به نزدیک ترین سرور محلی خود با استفاده از پروتکل LRP می فرستد. سپس فیلتر bloom خود را چک می‌کند و در می یابد که اطلاعاتی درباره گره مقصد ندارد. سپس فیلترهای bloom سه پیوند بعدی را چک می‌کند. اتصال ( ، ) به دلیل اینکه هر سه bit تنظیم شده اند انتخاب می شود. بسته به سمت به جلو رانده شود و اتصال بعدی آن ( ، ) انتخاب می شود. وقتی که بسته به ، می رسد در می یابد این سرور محلی مورد نظر است و بسته به گره مقصد “adhoc.node1.hk” با استفاده از پروتکل LRR انتقال داده می شود.

به دلیل مثبت خطا ممکن است که بسته به یک سرور محلی برسد که فیلتر bloom آن بنظر می رسد که شامل مقصد است در حالیکه پایگاه (data base) محلی اصلی آن را ندارد. وقتی این اتفاق می افتد، فرد می تواند به سادگی بسته را متوقف کرده یا به یکی از اطرافیان آن به جلو براند. برای اجتناب از پیش روی نامشخص در امتداد loops، تعداد گامهای منتقل شده در شبکه overlay ثبت می شود که در نتیجه بسته می تواند جدا شود وقتی که تعداد از حد خاصی فراتر رود.یک روش معادل این است که لیست همه سرورهای دیده شده را همراه با هر بسته ضمیمه کنیم. این لیست برای جلوگیری از به جلو رفتن یک بسته به سمت سروری قبلاً رفته، مورد استفاده قرار می‌گیرد.

۴، تجزیه تئوریک
در این بخش ما چندین سیستم متریک جالب را برای طرح پیشنهادی مورد بررسی قرار می دهیم.
۴۱ تعداد optimal سرورهای محلی

فرض کنید NC تعداد گره ها در شبکه ad hoc و m تعداد سرورهای محلی باشد. ما قرار می دهیم تا اجرای سیستم را به حداکثر برسانیم. این به صورت زیر توجیه می شود. با فرض کردن اینکه جلسات ارتباطی بین جفت گره ها بطور موقتی در شبکه قرار گرفته باشند. این در تصویر ۱۶ نشان داده شده است که عبور متوسط هر گره است.

فرض کنید که شبکه بطور یکنواخت تقسیم بندی به voronoi cells، می توانیم بحث کنیم که تعداد متوسط گره ها در هر ناحیه واقعی باشد. پس عبور متوسط در هر گره از ناحیه واقعی محلی است. عبور از هر گره در شبکه overlay یا نشان داده می شود. از آنجا که فشردگی در نواحی اصلی در سرورهای محلی از منطقه محلی به شبکه های overlay یا بر عکس تغییر می یابد نسبت فرستاده شده به نواحی اصلی از راه شبکه overlay باید باشد با فرض اینکه توزیع فشردگی یکنواخت باشد. برای اجتناب از فشردگی خیلی زیاد این نسبت نباید از بیشتر شود. از آنجا که ما می خواهیم ماگزیمم جریان را بدون فشردگی زیاد داشته باشیم، داریم: که می‌دهد در آزمایش ها، تعداد سرورهای محلی را قرار می دهیم. در مثال تصویر ۱ ۳۹ گره و ۶ سرور محلی داریم.
۴۲ موجودیت سرور محلی

اطلاعات محلی هر گروه mobile در سرورهای محلی k ذخیره می شود. فرض کنید PC احتمال این باشد که یک سرور محلی واحد بطور درست کار می‌کند. از آنجا که داده ها قابل بررسی هستند وقتی که حداقل یک سرور محلی موجود باشد، موجودیت داده ها با فورمول توزیع زیر داده می شود:

ما موجودیت مورد نظر را a تعیین می کنیم همچنانکه میزان موجودیت داده هایی که باید بصورت تضمین شده باشند که سیستم معتبر باشد. جدول ۱ تعداد سرورهای محلی K را می‌دهد که لازم است به تقاضاهای موجود را برای میزان شکست مختلف در برداشته باشند. از این جدول می توانیم ببینیم که اگر فقط گره های معتبر (مثلاً ) را انتخاب کنیم که یک تقاضای منطقی است) که بعنوان سرورهای محلی عمل کنند، فقط تعداد کمی از نسخه های لازم است به سیستمی با موجودیت داده ای بالا برسند.

۴۳ کیفیت مسیر
ما از این کیفیت مسیر بین هر دو گره ای که بصورت تصادفی انتخاب شده اند در شبکه ad hoc بررسی می کنیم. برای سهولت این بررسی فرض می کنیم همه گره‌های mobile بطور یکنواخت در منطقه پخش شده اند. ما بعداً فرض می کنیم که شبکه وصل شده و هیچ گره ایزوله شده در شبکه وجود ندارد.
فرض کنید که S و D دو گروهی هستند در شبکه ad hoc و مسیری که آنها ربط‌می‌دهد از میان سرورهای ، ، در شبکه overlay می گذرد. ما از استفاده می کنیم تا فاصله اقلیدسی بین آنها را بدست آوریم.

Lemm a1 تعداد متوسط گامها، P، بین هر دو سرور محلی در شبکه است.
Lemma2. فاصله Delaunay بین هر دو سرور محلی را تعیین کنید همچنان به طول کوتاهترین مسیر در گراف Delaunay با سرورها مربوط است. سپس نسبت بین فاصله Delaunay و فاصله اقلیدسی هر جفت از سرورهای محلی با یک ثابت C محدود می‌شود. این ثابت c در گرافهای موقتی است و تا کاهش داده می شود اگر c موقعیتها در گراف Delaunay با توجه به poisson process صورت گرفته باشد.

Lemma 3. اگر طول مسیر رابط و را بصورت ( ، ) DIST بگیریم. سپس LSP1، قضیه ( ، ) از طولهای مسیر رابط دو سرور تشکیل شده است. به یاد داشته باشید مسیر بین هر دو سرور، کوتاهترین مسیر است که از مسافت delaunay کوتاهتر است، اگر گره ای mobile بین آنها سه زاویه (traingulated) delaunay باشد. بنابراین، ( ، ) Dist

تئوری ۱: در حالت متوسط، با دادن دو گره S و D بصورت تصادفی، نسبت بین مسیر طی شده توسط سیستم پیشنهادی و فاصله اقلیدسی محدود می شود. برای مثال:
قضیه: فرض کنید که گره های مبدأ و مقصد D نیز سرورهای محلی باشند.. قضیه سپس همان بحث Lemma 3 را دنبال می‌کند. در این مقاله، تعداد گامهای استفاده شده در مسیر طی شده( ) اهمیت دارد. می توان دید که
که در اینجا L طول متوسط کناره های مسیر است. این همچنین برای کوتاهترین مسیر صحیح است. برای مثال ](S,D) کوتاهترین مسیر[. E