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

بخشی از مقاله

شبكه هاي mobile ad hoc

1.مقدمه
شبكه هاي 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 ارائه مي دهيم كه بر مشكلاتي كه قبلاً ذكر شد فائق آيد. ويژگيها و امتيازهاي عمدة اين سيستم عبارتند از:

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

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

بقية جزوه به صورت زير سازمان يافته است: بخش 2 شامل بررسي كوتاهي از كارهاي مرتبط مي‌باشد. بخش 3 جزئيات تركيبي location management و سيستم routing را شرح مي‌دهد. در بخش 4 و 5، نحوة اجراي سيستم بصورت تئوريك آناليز و ارزيابي خواهد شد. و بالاخره 6 به نتيجه گيري مي پردازد.
Related work

الگوريتم هاي routing در يك MANET مي توانند به پروتكل هاي reactive و proactive تقسيم بندي شوند. در روش proactive اطلاعات routing در بردارندة مسيرهايي به همة مقاصد ممكن است در هر mobile node ذخيره مي شود كه ممكن است به دليل قطع ارتباط و تغييرات topology در MANET از رده خارج شوند (out date شوند). در چنين مواردي روش reactive ترجيح داده مي شود. در اين روش يك مسير multi-hop از فرستنده به گيرنده فقط طماني كه مورد نياز است، ساخته مي‌شود. بررسي هاي بيشتر در مورد اين الگوريتم هاي routing مي تواند در 25/21 صورت گيرد. يك دستة مهم از پروتكل هاي 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ها را به جلو براند.

در بخش 5 اطلاعات محلي 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 حل شده است.

3.the integrated location management & routing system
روش تركيبي routing system و management location طراحي شده تا:

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

Overhead تبادل اطلاعات را در ميان serverهاي محلي با فشرده كردن اطلاعات به حداقل مي رساند.
اين عمل بوسيلة يك طرح پيام بر، بر اساس فيلترهاي bloom انجام مي شود. جزئيات سيستم تركيبي ما در زير شرح داده شده است.
1-3 Delaunay traingulation overlay network

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

1.serverهاي محلي براي تبادل اطلاعات محلي خود و كنترل پيامهاي ديگر با يكديگر ارتباط دارند.
2.شبكة 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 تا 3m-3 محدود مي شود كه در اينجا m تعداد serverهاي محلي است، ميزان متوسط serverهاي محلي تا 6 مي‌رسد. دوم اينكه تضمين مي شود كه اتصالات حقيقي فقط بين serverهاي محلي در ارتباط نزديكي با هم هستند وجود داشته باشد. اين اطمينان مي‌دهد كه مسيرهاي مطابق با هم در شبكة underlay ad hoc از نظر تعداد hopها كوتاه بوده و حفظ مسيرها را آسانتر مي سازند.

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

آنجا K يك پارامتر سيستم است. وقتي كه k=1 باشد يك server محلي، اطلاعات محلي همة mobile nodes را در voronoi cell خود ذخيره مي‌كند. مقدار بيشتر K مي تواند براي كمتر كردن مشكلات موجود داده ها مورد استفاده قرار گيرد، چرا كه اطلاعات محلي در serverهاي محلي ديگر هنوز وجود دارند حتي اگر يك server محلي fail شده باشد. در بخشهاي 4 و 5 با تجزية تئوريك و آزمايشات تجربي نشان خواهيم داد كه k=2 يا 3 محاسبة دقيقي از تبادل بين موجوديت داده ها و ذخيره (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 قبلي مي تواند حذف گردد.

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

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

از طرح تركيبي ما هر 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 محلي تا 6 محدود مي شود، اين به مقدار زيادي تقاضا انبار را كاهش مي‌دهد.

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

تصوير 3 مثالي از توزيع فيلتر bloom را نشان مي‌دهد. Server محلي اطلاعات محلي را از يك گروه mobile “143.89.0.1” در بر دارد و فيلتر bloom آن bitهاي مطابق با آن را (7، 3،0) تا 1 تنظيم مي‌كند. وقتي كه فيلتر 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 شمارشي) ناميده مي شود.

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

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

از آنجا كه هر سرور محلي اطلاعات محلي خود را به همة گره هاي mobile در voronoi cell خود توزيع مي كند، پروتكل LRP مي تواند از اطلاعات محلي براي انتقال و هدايت بسته استفاده كند. بنابراين هر پروتكل LAR مي تواند بكار گرفته شود. ما از پروتكل پيشنهادي LAR در 17 استفاده مي كنيم.

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

بعنوان مثال به تصوير 3 توجه كنيد: فرض كنيد كه يك گره 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 ثبت مي شود كه در نتيجه بسته مي تواند جدا شود وقتي كه تعداد از حد خاصي فراتر رود.يك روش معادل اين است كه ليست همة سرورهاي ديده شده را همراه با هر بسته ضميمه كنيم. اين ليست براي جلوگيري از به جلو رفتن يك بسته به سمت سروري قبلاً رفته، مورد استفاده قرار مي‌گيرد.

4، تجزية تئوريك
در اين بخش ما چندين سيستم متريك جالب را براي طرح پيشنهادي مورد بررسي قرار مي دهيم.
4.1 تعداد optimal سرورهاي محلي

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

فرض كنيد كه شبكه بطور يكنواخت تقسيم بندي به voronoi cells، مي توانيم بحث كنيم كه تعداد متوسط گره ها در هر ناحيه واقعي باشد. پس عبور متوسط در هر گره از ناحيه واقعي محلي است. عبور از هر گره در شبكه overlay يا نشان داده مي شود. از آنجا كه فشردگي در نواحي اصلي در سرورهاي محلي از منطقه محلي به شبكه هاي overlay يا بر عكس تغيير مي يابد نسبت فرستاده شده به نواحي اصلي از راه شبكه overlay بايد باشد با فرض اينكه توزيع فشردگي يكنواخت باشد. براي اجتناب از فشردگي خيلي زياد اين نسبت نبايد از بيشتر شود. از آنجا كه ما مي خواهيم ماگزيمم جريان را بدون فشردگي زياد داشته باشيم، داريم: كه مي‌دهد در آزمايش ها، تعداد سرورهاي محلي را قرار مي دهيم. در مثال تصوير 1 39 گره و 6 سرور محلي داريم.
4.2 موجوديت سرور محلي

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

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

4.3 كيفيت مسير
ما از اين كيفيت مسير بين هر دو گره اي كه بصورت تصادفي انتخاب شده اند در شبكه 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

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