• Home
  • Adaptive Probabilistic Flooding for Ad Hoc Networks

Share To

Article Url


Manuscript ID : 202005091321 Visit : 10763 Page: 27 - 35

Article Type: Original Research

Adaptive Probabilistic Flooding for Ad Hoc Networks

Subject Areas : ICT

fateme nourazar 1 * , sabaei sabaei 2

1 -
2 -

Received: 2013-08-03 Published : 2019-11-08

Keywords:

Abstract :

Broadcasting is one of the most fundamental operations in mobile ad hoc networks. Broadcasting serves as a building block in many routing protocols. The simplest approach for broadcasting is flooding. However, it generates many redundant messages that cause to loss of scarce resources such bandwidth and battery powers and it may lead to contention, collision and extreme decrease of network performance. Many schemes have been developed to improve the performance of flooding algorithm that are mainly classified into two basic approaches: deterministic and probabilistic approaches, of which the second is more considered. However, the existing schemes either increase the latency or decrease the reach ability of the algorithm. In this paper, we propose a new scheme to improve the performance of flooding algorithm. The basis of the new method is the probabilistic rebroadcasting based on local observations. In this method, the probability function of each node is adjusted dynamically based on local observations. Simulation results show that the new scheme considerably decrease average latency compared with similar existing schemes while maintaining the reach ability and saving messages.

References:


Full-Text:


 

فصلنامه علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال دوم، شماره‌هاي‌5و6، پاييز و زمستان 1389

صص: 35- 27

E:\E Drive\logo\iicta Logo0.JPG 

 

 

یک الگوریتم سیل‌آسای مبتنی بر احتمال تطابقی برای شبکه‌های موردی سیار

 

فاطمه نورآذر▪ *                مسعود صبائی **

* کارشناس ارشد، دانشکده مهندسی برق، رايانه و فناوری اطلاعات،  دانشگاه آزاد اسلامی واحد قزوين

** استادیار، دانشکده مهندسی کامپيوتر و فناوری اطلاعات، دانشگاه صنعتی اميرکبير

 

تاريخ دريافت: 15/03/1389                                تاريخ پذيرش: 24/08/1389

 

 

 

چکيده

الگوريتم سيل­آسا، يکی از مهمترين عمليات اوليه و زيربنايي برای پروتکل­های مسيريابی در شبکه­های موردی سيار است. اما، از آن­جايي که اين الگوريتم پيغام­های اضافی زيادی توليد می­کند، بسيار پرهزينه بوده، باعث اتلاف پهنای باند شبکه، مصرف بيش از نياز انرژی گره­ها شده که در نهايت ممکن است موجب طوفان همه پخشی شود. روش­های زيادی برای بهبود الگوريتم سيل­آسا پيشنهاد شده است که عمدتاً به دو دسته روش­های قطعی و احتمالی تقسيم می­شوند که دستة دوم بيشتر مورد توجه قرار گرفته است. اما اين روش­ها عمدتاً باعث افزايش تأخير و عدم پوشش کامل می­شوند. در اين مقاله، ما يک روش جديد برای بهبود عملکرد الگوريتم سيل­آسا پيشنهاد کرده­ايم. اساس کار اين روش بازپخش احتمالی بر مبنای مشاهدات محلی می­باشد. در اين روش جديد احتمال بازپخش پيغام توسط هر گره، تابعی از مشاهدات محلی می­باشد. نتايج شبيه­سازی نشان داده است که روش پيشنهادی در مقايسه با روش­های مشابه ضمن کاهش قابل توجه تأخير تحويل بسته­ها با سربار پيغام قابل قبول پوشش کامل شبکه را فراهم می­کند.

 

کلید واژگان: شبکه­های موردی سيار، الگوريتم سيل­آسا، الگوريتم مبتنی بر شمارش، احتمال بازپخشی.

 

 

 

▪ نویسنده عهده‌دار مکاتبات (F.nourazar@gmail.com)

1-       مقدمه

انتشار همه­پخشی1، نقش اساسی را در شبکه­های موردی سيار ايفا می­کند. انتشار همه­پخشی به اين معنی است که پيغامی را که توسط يک گره ارسال شده است به تمام گره­های شبکه منتشر کنيم. پروتکل­های مختلف مسيريابی مانند DSR [1] ، AODV [2]، ZRP [3] و LAR [4] و همچنين پروتکل­های مسيريابی چندپخشی از انتشار همه پخشی برای کشف و نگهداری مسير، در محيط­هايي که توپولوژی آن­ها به سرعت در حال تغيير است، استفاده می­کنند.

ساده­ترين راهکار برای پياده­سازی انتشار همه پخشی، الگوريتم سيل آسا است که در آن هر گره پيغامی را که برای اولين بار دريافت کرده است بلافاصله پس از دريافت بازپخش می­کند. اگرچه الگوريتم سيل­آسا، نرخ موفقيت بالايي در رساندن پيغام به تمام گره­های شبکه دارد، با اين وجود پيغام­های اضافی زيادی را توليد می­کند. اين افزونگی پيغام مخصوصاً در شبکه­های با چگالی بالا، باعث از دست رفتن توان باتری گره­ها، کمبود پهنای باند و کاهش شديد کارايي شبکه می­شود. به اين پديده "طوفان همه­پخشی2" [5] می­گوييم.

الگوريتم­های مختلفی برای بهبود عملکرد الگوريتم سيل آسا و پرهيز از بروز طوفان همه­پخشی ارائه شده است که معمولاً آن­ها را به دو گروه اصلی تقسيم­بندی می­کنيم: روش­های قطعی و روش­های احتمالی. روش­های قطعی يک ساختار انتزاعی مسيريابی را در شبکه ايجاد می­کنند که با فرض داشتن يک لايه MAC ايده­آل، پوشش شبکه 100% را تضمين می­کنند. ولی اين ساختار بايد مکرراً به روز رسانی شود که باعث تحميل هزينه بصورت پيچيدگی زمانی و پيامی به الگوريتم می­شود. الگوريتم­های هرس کردن [6]، بازپخشی چندنقطه­ای [7]، بازپخشی انتخابی [8]، حذف همسایگان [10،9]، مبتنی بر کلاستر و ... مثال­هايي از روش­های قطعی به شمار می­روند.

در مقابل، روش­های احتمالی مبتنی بر هيچ ساختار اساسی مسيريابی نيستند بلکه هر گره با استفاده از اطلاعات محلی که از بسته­های دريافت شده به دست آورده است به تنهايي و مستقل از ديگر گره­ها تصميم می­گيرد که پيغام را بازپخش کند و يا آن را دور بيندازد. اين روش­ها نسبت به روش­های قطعی سربار کمتری را به الگوريتم تحميل می­کنند و در برابر تغييرات توپولوژی شبکه تطبيق­پذيری بهتری دارند. برای اولين بار Ni در [5] چند روش احتمالی را پيشنهاد داد که عبارتند از: الگوريتم مبتنی بر احتمال، مبتنی بر شمارش، مبتنی بر فاصله و مبتنی بر موقعيت. در روش­های مبتنی بر احتمال، هر گره که پيغام را دريافت می­کند، آن را با احتمال  بازپخش می­کند. در ديگر روش­ها هنگامی که گره­ای يک پيغام همه پخشی را برای اولين بار دريافت می­کند تايمری را به مدت زمان تصادفی  فعال می­کند. پس از گذشت زمان  گره در صورتی پيغام را بازپخش می­کند که شرايط بازپخشی فراهم باشد. شرايط بازپخشی در الگوريتم­های مختلف، بصورت متفاوت تعريف می­شود: در الگوريتم مبتنی بر شمارش اگر گره کمتر از تعداد معينی (حد آستانه C) پيغام­های تکراری دريافت کند اقدام به بازپخشی پيغام می­کند. در الگوريتم مبتنی بر فاصله اگر فاصله گره گيرنده و فرستنده بيشتر از يک فاصله معينی (حد آستانه ) باشد، گره پيغام را بازپخش می­کند. در الگوريتم مبتنی بر موقعيت اگر در محدوده ارسالی گره تصميم گيرنده منطقه پوشش داده نشده­ای وجود داشته باشد که مساحت آن از مقدار  بيشتر باشد، گره پيغام را بازپخش خواهد کرد. يکی از مشکلات روش­های احتمالی تنظيم مناسب مقادير آستانه­ای است. از طرف ديگر جمع­آوری اطلاعات باعث افزايش تأخير الگوريتم می­شود. برای بهبود عملکرد روش­های احتمالی الگوريتم­های مختلفی [13،12] پيشنهاد شده است. بيشتر آن­ها تلاش کرده­اند که با ترکيب روش­های مختلف با يکديگر و انتخاب مناسب مقادير آستانه­ای عملکرد اين روش­ها را بهبود دهند.

الگوريتم پيشنهادی ما، يک الگوريتم مبتنی بر شمارش بهبوديافته است. ايده اصلی اين الگوريتم استفاده از احتمال در بازپخش کردن پيغام­هاست. بر خلاف الگوريتم مبتنی بر شمارش، در اين الگوريتم هر گره بلافاصله پس از دريافت پيغام جديد و بدون اينکه مدت زمانی را صبر کند بصورت احتمالی اقدام به بازپخش کردن پيغام می­کند. اگر موفق به بازپخش کردن پيغام نشود، به تدريج و با جمع آوری اطلاعات محلی شبکه(مانند تعداد گره­های همسايه و تعداد پيغام­های تکراری دريافت شده) تابع احتمال را دقيق­تر محاسبه کرده و در مرحله بعد با مقدار احتمال دقيق­تری اقدام به بازپخش کردن پيغام می­کند.

ساختار ادامه مقاله به صورت زير است: در بخش دوم ابتدا به کارهايي که تا کنون دربارة اين موضوع انجام شده است می­پردازيم. سپس در بخش سوم انگيزه طرح پيشنهادی خود را شرح می­دهيم. در بخش چهارم روش پيشنهادی خود را توضيح می­دهيم. در بخش پنجم به ارزيابی کارايي روش پيشنهادی خود پرداخته و نتايج آن را با ديگر روش­ها مقايسه می­کنيم. در بخش ششم نيز نتيجه گيری کرده و کارهای آينده را معرفی می­کنيم.

 

2-       مروری بر کارهای مرتبط

الگوريتم مبتنی بر شمارش، ابتدا در [5] به عنوان راهکاری برای کاهش تعداد پيغام­های بازپخشی اضافی و پرهيز از بروز "طوفان همه پخشی" در الگوريتم سيل­آسا پيشنهاد شد. مبنای ايده الگوريتم مبتنی بر شمارش اين است که پوشش اضافی مورد انتظار(EAC)3 رابطه عکس با تعداد پيغام­های تکراری دريافت شده دارد. اگر پوشش اضافی مورد انتظار گره کم باشد، گره از بازپخش کردن پيغام منصرف مي‌شود. مفهوم پوشش اضافی مورد انتظار (EAC) را با يک مثال در شکل 1 توضيح داده­ايم. گره­های توخالی گره­های مبدأی هستند که پيغام را به شبکه ارسال کرده­اند و گره­های سياه رنگ گره­هايي هستند که ما از آن­ها برای بيان ايده خود استفاده می­کنيم. با توجه به شکل 1 چگالی همسايگی گره a بالاتر از گره b است. بنابراين تعداد پيغام­های تکراری که گره a دريافت می­کند بايد بيشتر باشد. علاوه بر اين به احتمال قوی گره­هايی که در محدوده ارسال گره سياه a قرار دارند، در محدوده ارسال ديگر گره­های بازپخش کننده نيز قرار دارند. بنابراين پوشش اضافی مورد انتظار گره سياه a کمتر از گره سياه b است.

eac2.jpg 

شکل 1: مثالی از پوشش شبکه مورد انتظار(EAC)

 در الگوريتم مبتنی بر شمارش هر گره به محض اين که پيغامی را برای اولين بار دريافت می­کند يک شمارشگر(c) را به منظور شمارش پيغام­های تکراری دريافتی فعال می­کند و به مدت زمان RAD4 منتظر می­ماند. مدت زمان RAD به طور تصادفی و بين 0 تا  ثانيه انتخاب می­شود، که  ماکزيمم تأخير زمانی ممکن است. وجود تایمر RAD به دو دلیل ضروری است: اول این­که به گره­ها فرصت کافی برای دریافت پیغام­های اضافی می­دهد تا بر اساس آن تصمیم گیری کنند که پیغام را بازپخش کنند یا نه. همچنین زمانبندی تصادفی بازپخش پیغام­ها مانع از بروز تصادم می­شود. به محض این­که تایمر RAD منقضی شد، مقدار شمارشگر c با مقدار آستانه یعنی C مقایسه می­شود و اگر  پیغام بازپخش نخواهد شد.

Ni  در ادامه کار خود در [12] يک الگوريتم مبتنی بر شمارش تطبيقی ارائه داده است که در آن هر گره مقدار حد آستانه شمارشگر (C) را با توجه به تعداد همسايگان خود به طور ديناميکی و پويا تغيير می­دهد. اگر چه آن­ها کوشيدند که مقدار حد آستانه شمارشگر را به عنوان تابعی بر حسب n (C(n)) بيان کنند، با اين وجود آن­ها بيان کرده­اند که تابع c(n) هنوز تعريف نشده است. روش همه پخشی مبتنی بر رنگ [14] نيز يک الگوريتم مبتنی بر شمارش است که ايده اصلی آن افزودن رنگ به پيغام­های همه پخشی است. با استفاده از n رنگ  هر گره يک رنگ را انتخاب کرده و آن را در فيلد رنگ پيغام می­نويسد. همه گره­هايي که اين پيغام را دريافت می­کنند آن را بازپخش می­کنند مگر اينکه همه n رنگ را قبل از اينکه مدت زمان انتظار به اتمام برسد دريافت کرده باشند. سوالی که در اينجا مطرح می­شود اين است که : اگر n=3 باشد و يک گره 2n پيغام را فقط با رنگ­های {} دريافت کرده باشد، چه بايد بکند؟ با توجه به الگوريتم ارائه شده اين گره با وجودی که پيغام­های تکراری زيادی را دريافت کرده ولی همچنان پيغام را بازپخش می­کند. علاوه بر اين الگوريتم مبتنی بر رنگ مشکلی را که الگوريتم مبتنی بر شمارش با C ثابت با آن مواجه بود دارد: اين الگوريتم­ها فقط در شبکه­های با چگالی همگن داراری پوشش بالايي هستند و در شبکه­های ناهمگون کارايي­شان کاهش می­يابد. الگوريتم مبتنی بر شمارش مطلع از فاصله [15]، فاصله گره­ها را در تصميم گيری آن­ها در بازپخش کردن پيغام­ها دخالت می­دهد. همسايگانی که به مرز محدوده ارسالی نزديکتر هستند با مقدار احتمال بيشتری اقدام به بازپخشی می­کنند زيرا پوشش اضافی مورد انتظاری که تأمين می­کنند بيشتر است.

در [16] يک الگوريتم مبتنی بر شمارش تطبيقی ارائه شده است که مقدار حد آستانه شمارشگر (C) را برای شبکه­های با چگالی بالا و پايين متفاوت در نظر می­گيرد. برای شبکه­های با چگالی بالا مقدار C را عدد کوچکی می­گيرد در صورتی که برای شبکه­های با چگالی پايين لازم است که مقدار C را عدد بزرگتری در نظر بگيريم. اين مقاله همچنين مدت زمان انتظار هر گره برای شمارش تعداد پيغام­های تکراری را برای شبکه ­های با چگالی های مختلف متفاوت در نظر می­گيرد. در شبکه­های با چگالی بالا هر گره مدت زمان کمتری را صبر می­کند در حاليکه در شبکه­های تنک لازم است هر گره زمان بيشتری را برای شمارش تعداد پيغام­های تکراری صرف کند. آن­ها مدت زمان انتظار را با رابطه  تنظيم می­کنند که RF فاکتوری است که مقدار آن در شبکه­های با چگالی­های مختلف فرق می­کند. به­گونه­ای که در شبکه­های با چگالی زياد مقدار RF را عدد کوچکی در نظر می­گيريم و برای شبکه­های با چگالی کم بايد مقدار RF را بزرگتر بگيريم. x نيز يک مقدار تصادفی بين [1و0] است. الگوریتم توسعه RAD [17]، مدت زمان انتظار گره­هایی را که پیغام­های تکراری بیشتری دریافت کرده­اند افزایش می­دهد. با دریافت هر پیغام اضافی، مدت زمان انتظار آن گره به مقدار مشخصی افزایش می­یابد.

 الگوريتم ECS [18] يک الگوريتم مبتنی بر شمارش بهبوديافته است که الگوريتم مبتنی بر احتمال را با الگوريتم مبتنی بر شمارش ترکيب کرده است. در اين الگوريتم هر گره به محض دريافت پيغام جديد يک شمارشگر را به منظور شمارش تعداد پيغام ­های تکراری دريافت شده فعال می­کند و به مدت زمان RAD (که بصورت تصادفی بين 0 تا   انتخاب می­شود) منتظر می­ماند. بعد از به پايان رسيدن اين زمان اگر تعداد پيغامهای تکراری c به مقدار حد آستانه C رسيده باشد، پيغام را به صورت احتمالی با مقدار احتمال P بازپخش می­کند. مقدار احتمال را نيز ثابت و برابر P=0.65 در نظر گرفته است.

ما در کار قبلی خود [19]، الگوريتم DAPF را به عنوان راهکاری برای بهبود عملکرد الگوريتم سيل­آسا پيشنهاد داده­ايم. اين الگوريتم بازپخشی پيغام­ها را با استفاده از تابع احتمال پيشنهاد شده انجام می­دهد. احتمال بازپخشی پيغام توسط هر گره تابعی از زمان و مشاهدات محلی است. مبنای کار اين روش بر اين اساس است که هر گره، ابتدا کار را به اطرافيان واگذار می­کند و خود از بازپخش کردن امتناع می­کند. بنابراين هر گره ابتدا سعی می­کند که با کمترين احتمال ممکن پيغام را بازپخش کند. ولی با گذشت زمان اگر متوجه شود که ديگران بازپخش نکرده­اند احتمال بازپخشی را افزايش می­دهد.

 

3-       انگيزه طرح پيشنهادی:

نتايج شبيه­سازی الگوريتم مبتنی بر شمارش [5] نشان می­دهد که اين الگوريتم ضمن اينکه مقدار پوشش شبکه الگوريتم سيل­آسای کلاسيک را حفظ می­کند، توانسته است سربار ناشی از پيغام­های سيل­آسای الگوريتم سيل­آسای کلاسيک را به طور قابل توجهی کاهش می­دهد.

ولی خود الگوريتم مبتنی بر شمارش نيز دارای نقايص و مشکلات جدی است که در ادامه اين بخش به آن­ها می‌پردازيم:

الگوريتم مبتنی بر شمارش به علت اينکه در هر بار بازپخشی پيغام به مدت زمان  (که بصورت تصادفی و بين 0 تا   انتخاب می­شود) صبر می­کند، تأخير بالايي را به کل الگوريتم تحميل می­کند. اين تأخير بالا باعث ناکارآمدی الگوريتم بويژه در کاربردهای بلادرنگ می­شود. الگوريتم­هايي که تا کنون برای بهبود عملکرد الگوريتم مبتنی بر شمارش ارائه شده­اند، به مسئله پوشش شبکه و کاهش هرچه بيشتر سربار پرداخته­اند و مشکل تأخير اين الگوريتم را مورد بررسی قرار نداده­اند. در الگوريتم پيشنهادی به منظور کاهش تأخير هر گره لازم نيست که به مدت زمان  صبر کند و سپس در مورد بازپخش کردن پيغام تصميم بگيرد بلکه بلافاصله پس از دريافت پيغام به صورت احتمالی به بازپخش کردن پيغام اقدام کند.

از جمله الگوريتم­هايي که برای بهبود عملکرد الگوريتم مبتنی بر شمارش ارائه شده­اند الگوريتم ECS [18] است که از ترکيب الگوريتم مبتنی بر احتمال و مبتنی بر شمارش بهره می­گيرد. ولی اين الگوريتم مقدار احتمال را در همه جای شبکه و نيز در طول اجرای شبيه­سازی يک مقدار ثابت می­گيرد. از آن جايي که شبکه­های موردی سيار شبکه­هايي هستند که توپولوژی شبکه بطور مرتب در حال تغيير است، ثابت بودن مقدار احتمال به دلايل زير مطلوب نيست:

1.  همه گره­ها صرف نظر از وضعيت محلی توپولوژی شبکه با يک مقدار ثابت و يکسان اقدام به بازپخش کردن پيغام می­کنند. در نتيجه در قسمت­هايي از شبکه که چگالی گره­ها بالاست با افزونگی پيغام­های تکراری مواجه خواهيم شد و در قسمت­هايي که شبکه تنک است و چگالی گره­ها پايين است نمی توانيم پوشش مناسبی بدهيم. بنابراين بايد مقدار احتمال را به گونه­ای به چگالی محلی شبکه وابسته کنيم. ما در الگوريتم پيشنهادی خود مقدار احتمال را به درجه گره ­ها که همان تعداد همسايگان مرتبه اول است وابسته کرده­ايم. در واقع مقدار احتمال تعيين شده رابطه معکوس با تعداد همسايگان مرتبه اول دارد (). زيرا هرچه تعداد گره­های همسايه بيشتر باشد، احتمال اين­که آن­ها هم پيغام را بازپخش کنند بيشتر است، بنابراين گره تصميم گيرنده با احتمال کمتری به بازپخش کردن پيغام اقدام می­کند.

2. تعداد پيغام­های تکراری دريافت شده جزء اطلاعاتی است که از شبکه در اختيار داريم، ولی در الگوريتم ECS گره­ها بدون اين­که از اين اطلاعات برای تنظيم مقدار احتمال بازپخشی استفاده کنند، مقدار احتمال را ثابت در نظر گرفته­اند. ما در الگوريتم خود سعی کرده­ايم که مقدار احتمال را در هر مرحله با توجه به تعداد پيغام­های تکراری دريافتی و نيز مقدار حد آستانه شمارشگر (C) تغيير دهيم.

 

4-       روش پيشنهادی

ايده اصلی روش پيشنهادی اين است که هر گره پس از دريافت يک پيغام جديد با يک احتمال بازپخشی را انجام دهد و يا منتظر دريافت اين پيغام از گره­های ديگر بماند. بعد از هر مرحله زمانی، بر مبنای مشاهدات خود مشابه روش مبتنی بر شمارش اگر تعداد پيغام­های دريافت شده برابر و بيشتر از C باشد، از بازپخشی منصرف شده در غير اينصورت با محاسبه احتمال جديد تصميم به بازپخشی می­گيرد و يا تا مرحله زمانی بعد منتظر می­ماند. اين عمل آنقدر تکرار خواهد شد که يا گره اين پيغام را بازپخش کند و يا با دريافت برابر يا بيشتر از C پيغام از بازپخش کردن منصرف شود.

 بنابراين روش پيشنهادی به هيچ وجه مشکل die out را مشابه روش­های مبتنی بر احتمال ندارد و اگر ميزان احتمال بازپخشی در هر مرحله بطور مناسب تنظيم شود، علاوه بر اينکه تأخير ارسال می­تواند کاهش پيدا کند، تعداد پيغام های بازپخش شده نيز کنترل خواهد شد. در مرحله اول، گره­ها پيغام را با مقدار احتمال  بازپخش می­کنند. زيرا بهترين حالت اين است که بطور متوسط   گره­ها بدون هيچ معطلی پيغام را بازپخش کنند. بنابراين در مرحله اول گره­ها پيغام را با مقدار احتمال  بازپخش می­کند. در نتيجه بطور متوسط  گره بدون منتظر ماندن پيغام را ارسال می­کنند.

بعد از به پايان رسيدن مدت زمان  (شکل 2)، گره­هايي که موفق به ارسال پيغام نشده­اند به مشاهدات خود رجوع می­کنند و تعداد پيغام­های تکراری را که در طی اين مدت زمان دريافت کرده­اند می­شمارند(). اگر <C باشد، آنگاه مقدار تابع احتمال را بصورت  دوباره محاسبه کرده و پيغام را با اين مقدار احتمال جديد بازپخش می­کند. اگر >C باشد، p=0 که به معنی منصرف شدن از بازپخشی می­باشد.

img0 

شکل 2: تغيير مقدار احتمال بازپخشی در زمان­های مختلف.

 

بنابراين می­توان رابطه کلی زير را برای محاسبه احتمال معرفی نمود:

       (1)

که  تعداد پیغام­های تکراری دریافت شده تا مرحله زمانی  ام است،  حد آستانه شمارشگر و  تعداد همسایگان مرتبه اول است.

با توجه به تابع احتمال پيشنهاد شده نحوه عملکرد اين الگوريتم به گونه­ای است که سعی مي‌کند در کمترين زمان ممکن بيشترين ميزان بازپخشی را انجام دهد و پوشش کامل در شبکه ايجاد کند. به همين علت هم هست که ميزان تأخير الگوريتم را به طرز قابل توجهی کاهش می­دهد. گره A در شکل 3، در منطقه­ای قرار گرفته که 9 همسايه مرتبه اول دارد. با دريافت هر پيغام تکراری مساحت پوشش اضافی مورد انتظار گره A کاهش می­يابد. در بدترين حالت، اگر گره فرستنده B در دورترين فاصله ممکن از A قرار گرفته باشد،  از محدوده ارسال گره A را پوشش می­دهد. لذا لزومی ندارد که گره A مانند مرحله قبل با مقدار احتمال بالا بازپخش کند. بلکه با دخالت دادن مشاهدات خود در اين بازه زمانی ميزان احتمال را کاهش می­دهد. اگر 3 گره از 9 گره پيغام را بازپش کنند محدوده ارسال A کاملاً پوشش داده می­شود. لذا A ديگر پيغام را بازپخش نمی­کند.

در الگوريتم سيل­آسای کلاسيک در شرايط مشابه، هر 9 گره همسايه و نيز گره A پيغام را بازپخش می­کنند. بنابراين در يک محدوده ارسال کوچک 10 پيغام را تقريباً بصورت همزمان ارسال می­کند. الگوريتم مبتنی بر شمارش، در اين شرايط تقريباً مانند الگوريتم پيشنهادی ما عمل می­کند با اين تفاوت که به ازای کاهش سربار پيغام تأخير بالايي را به الگوريتم تحميل می‌کند.

sample.jpg 

شکل 3: مثالی از کاهش تعداد پيغام­های بازپخشی توسط الگوريتم Effective-CB.

 

4-1-                      مقدار حد آستانه شمارشگر (C):

مقدار حد آستانه شمارشگر به گونه­ای انتخاب شده است که هم افزونگی پيغام را کاهش می­دهد و هم پوشش شبکه کافی ايجاد می­کند. ما در [20] طی شبيه­سازيهايي که انجام داديم به اين نتيجه رسيديم که C=2 اگر چه در شبکه­های متوسط و چگال افزونگی پيغام را بطور قابل توجهی کاهش می­دهد ولی نمی تواند پوشش شبکه کافی ايجاد کند. مقادير C>4 نيز اگر چه پوشش مناسبی دارند ولی تعداد پيغام­های بازپخش شده آن­ها بالاست. به گونه­ای که C>6 رفتاری شبيه الگوريتم سيل­آسا دارد. با توجه به نتايج بدست آمده مقادير C=3 و C=4 مقادير مناسبی هستند.

سوالی که ممکن است در این­جا به ذهن برسد این است که اگر موقعیتی پیش آید که در آن  شود الگوریتم چگونه عمل می­کند؟ پاسخ این است که این مورد زمانی اتفاق می­افتد که  عدد کوچکی باشد. بنابراین این شرایط در نواحی تنک شبکه که تعداد گره­ها کم است و فاصله بین آن­ها زیاد است پیش می­آید و الگوریتم برای اطمینان از حفظ پوشش کامل شبکه با  پیغام را بازپخش می­کند.

 

4-2-                      مقدار حد آستانه مدت زمان انتظار:

در الگوریتم مبتنی بر شمارش،  مدت زمان انتظار()، از بازه 0 تا  بصورت یکپارچه و تصادفی انتخاب می­شود.  ماکزیمم تأخیر ممکن در بازپخشی است که بهتر است مقدار آن را به چگالی شبکه وابسته کنیم. زیرا در شبکه­های با چگالی بالا تعداد همسایگان مرتبه اول زیاد است و گره­ها به یکدیگر نزدیکترند. بنابراین مقدار شمارشگر زودتر به حد آستانه خود می­رسد. لذا بهتر است که مقدار   را کوچکتر انتخاب کنیم. ولی در شبکه­های تنک، از آن­جایی که تعداد همسایگان مرتبه اول کم است و فاصله گره­ها از هم زیاد است باید مدت زمان بیشتری را منتظر بمانیم تا بتوانیم اطلاعات دقیق­تری راجع به تعداد پیغام­های بازپخشی کسب کرده و پیغام را با دقت بیشتری بازپخش کرده ویا از بازپخشی آن منصرف شویم.

 

5-                       ارزيابی روش پيشنهادی

کارايي الگوريتم­های سيل­آسا را با معيارهای مختلفی می­توان سنجيد. يکی از مهم­ترين معيارها، تعداد پيغام­های بازپخش شده است. ما در اين مقاله، مکمل اين معيار يعنی تعداد پيغام­های صرفه جويي شده(Saved ReBroadcast) را استفاده کرده­ايم. معيار مهم ديگری که استفاده کرده­ايم، پوشش شبکه(REachability) است که برابر است با نسبت تعداد گره­هايي که پيغام را دريافت کرده­اند به تعداد کل گره­های موجود در شبکه. سومين معياری که برای ما اهميت دارد اين است که چه مدت زمان طول می­کشد که هر الگوريتم يک پيغام همه پخشی را به کل شبکه ارسال کند. بنابراين، معيارهای کارايي در نظر گرفته شده عبارتند از:

·       پيغام­های صرفه­جويي شده(SavedReBroadcast):

 برابر  است که r تعداد گره­هايي است که پيغام را دريافت می­کنند و t تعداد گره­هايي است که پيغام را واقعاً بازپخش می­کنند.

·       پوشش شبکه(REachability): تعداد گره­هايي که پيغام را دريافت کرده‌اند، تقسيم بر کل گره‌هايي که توسط گره مبدأ، به طور مستقيم يا غيرمستقيم در دسترس هستند.

·       متوسط تأخير(Average Latency): مدت زمان سپری شده از لحظه­ای که ارسال همه­پخشی آغاز شده تا لحظه­ای که آخرين گره عمل بازپخشی را تمام کند.

ما ارزيابی روش پيشنهادی خود را با استفاده از شبيه­ساز شبکة Glomosim [21] انجام داده­ايم. پارامترهای ثابت شبيه­سازی در جدول 1 آمده است و سعی شده است با مشخصات يک گرة واقعی شبکه­های موردی سيار مطابقت داشته باشد.

 

جدول 1: پارامترهای شبيه­سازی

Value

Parameter

250m

Transmission range

50

Number of nodes

2Mbps

Bandwidth

CBR

Traffic Type

10 pkts per second

Packet rate

Random waypoint

Mobility model

IEEE 802.11

MAC Protocol

120s

Simulation time

10

Trails

با ثابت بودن تعداد گره­های شبکه اندازه شبکه در طول شبيه سازی از 600*600 تا 1300*1300 متغير در نظر گرفته­ شده است. لذا چگالی گره­ها نيز در اين سناريوها متفاوت خواهد بود:

جدول 2: مشخصات سناريوها.

میانگین تعداد همسایگان

اندازه شبکه

شماره سناریو

26

600x600

Scenario1

19

700x700

Scenario2

14

800x800

Scenario3

11

900x900

Scenario4

9

1000x1000

Scenario5

8

1100x1100

Scenario6

7

1200x1200

Scenario7

5

1300x1300

Scenario8

 

روش پيشنهادی با سه الگوريتم مبتنی بر شمارش، الگوريتم ECS و الگوريتم DAPF مقايسه شده است. . شکل 4، نمودار تأخير متوسط الگوريتم­های مورد مقايسه را نشان می­دهد. همانطور که از نمودارها پيداست الگوريتم پيشنهادی ميزان متوسط تأخير را بطور قابل توجهی کاهش داده است به­گونه­ای که اين الگوريتم تقريباً تأخيری معادل تأخير الگوريتم کلاسيک سيل آسا دارد. به عبارت بهتر می­توانيم بگوييم که الگوريتم Effective-CB مشکل تأخير الگوريتم مبتنی بر شمارش را برطرف کرده است.

 

latency.jpg 

شکل 4: متوسط تأخير الگوريتم­ها در شبکه­های با چگالی زياد، متوسط وکم.

نتايج شبيه سازی ما در شکل 5 نشان می­دهد که الگوريتم پيشنهادی ما ضمن کاهش ميزان تأخير الگوريتم مبتنی بر شمارش نرخ بالای پوشش شبکه­ای را که الگوريتم مبتنی بر شمارش ايجاد می­کند حفظ نمايد. الگوريتم­های مورد مقايسه ECS و DAPF پوشش شبکه مناسبی بويژه در شبکه­های با چگالی پايين ندارند و البته اين مشکل يکی از نقاط ضعف جدی آن­ها به شمار می­رود.

re1.jpg 

شکل 5: نمودار پوشش شبکة الگوريتم­ها در شبکه­های با چگالی کم، متوسط و زياد.

 

معيار سومی که ما به کمک آن عملکرد الگوريتم خود را ارزيابی کرده­ايم تعداد پيغام­های صرفه­ جويي­شده توسط الگوريتم­هاست. همانطور که نمودارها نشان می­دهند الگوريتم­های ECS و DAPF تعداد پيغام­های بيشتری را نسبت به الگوريتم ما صرفه­جويي کرده­اند. ولی بايد توجه داشته باشيم که اين موفقيت با هزينه از دست دادن پوشش شبکه کامل و نيز افزايش تأخير الگوريتم به دست آمده است. بنابراين اگر نتايج اين سه معيار ارزيابی را در نظر بگيريم نتيجه می­گيريم که الگوريتم پيشنهادی ما عملکرد بهتری نسبت به سه الگوريتم مورد مقايسه دارد.

 

SRB2.jpg 

شکل 6: نمودار درصد پيغام­های بازپخشی صرفه­جويي شده در شبکه­های با چگالی زياد، متوسط و کم.

 

5-1-تأثیر مقادیر متفاوت حد آستانه مدت زمان انتظار بر عملکرد الگوریتم:

در این بخش از مقاله نشان خواهیم داد که با تغییر مدت زمان انتظار گره­ها عملکرد الگوریتم چگونه تغییر می­کند. ما مقدار آستانه مدت زمان انتظار را از 12 میلی ثانیه تا 160 میلی ثانیه تغییر دادیم و رفتار الگوریتم­ را مطالعه کردیم. شکل 7 تأثیر این تغییرات را بر میزان پوشش شبکه الگوریتم­ نشان می­دهد. همانگونه که نمودارها نشان می­دهند این تغییرات بر میزان پوشش شبکه الگوریتم­ بی­تأثیر است. در شکل­های 7 تا 9 “d” نشان­دهنده مقدار متوسط چگالی شبکه است.

شکل 8 بیان می­کند که هر چه مقدار حد آستانه را بزرگتر در نظر بگیریم، الگوریتم تمایل به ذخیره پیغام بیشتری دارد. تعداد پیغام­های بازپخش شده در  نسبت به  حدود 15-20% کاهش نشان می­دهد. نتایج نشان داده شده در شبکه­های با چگالی بالا و متوسط به دست آمده است. نتایج شبیه­سازی­ها در شبکه­های تنک نشان می­دهد که تغییرات مقادیر  تأثیر قطعی و قابل توجیهی بر رفتار الگوریتم ندارد.

retime2.jpg 

شکل 7: تأثیر تغییرات مدت زمان انتظار بر پوشش شبکه.

savedtime.jpg 

شکل8: تأثیر تغییرات مدت زمان انتظار بر تعداد پیغام­های بازپخشی.

 

در نهایت، تأثیر این تغییرات را بر مقدار متوسط تأخیر الگوریتم بررسی کردیم. همانطور که شکل 9 نشان می­دهد در تمام سناریوها با اقزایش مقدار حد آستانه متوسط تآخیر نیز افزایش می­یابد. مقایسه نمودارها نشان می­دهد که تأثیر افزایش مقدار آستانه بر روی الگوریتم­های با C=3 بیشتر از C=4 است. همچنین، در سناریوهای با چگالی بالا (d=26 و d=9) با افزایش مقدار آستانه، الگوریتم کارایی خود را از دست می­دهد. زیرا در این شبکه­ها با توجه به نزدیکی گره­ها به یکدیگر و تعداد زیاد آن­ها الگوریتم به طور طبیعی تمایل دارد که عمل بازپخشی را در زمان کمی انجام دهد و لذا انتخاب مقادیر بزرگ Tmax نه تنها کمکی به کمتر کردن میزان تأخیر نمی­کند بلکه نتیجه عکس نیز دارد.

با مقایسه نمودارهای شکل 8 و 9 می­توان نتیجه گرفت که باید میان معیارهای متوسط تأخیر و تعداد پیغام­های بازپخشی یکی را برگزینیم. در برنامه­های کاربردی بی درنگ که متوسط تأخیر اهمیت زیادی دارد، باید مقدار Tmax را کوچک در نظر گرفته تعداد پیغام­های بازپخشی بالا را نادیده بگیریم. اما اگر کمتر بازپخش کردن پیغام­ها برای ما اهمیت دارد باید مقدار Tmax را بزرگ انتخاب کنیم تا در نهایت به نتیجه مطلوب خود برسیم.

latencytime.jpg 

شکل 9: تأثیر تغییرات مدت زمان انتظار بر متوسط تأخیر.

6-                      نتيجه گيری و کارهای آينده

در اين مقاله، يک روش جديد برای بهبود عملکرد الگوريتم سيل­آسا پيشنهاد شده است. اساس کار اين روش بازپخش کردن پيغام­ها بصورت احتمالی و بر مبنای مشاهدات محلی است. به منظور بازپخش آگاهانه و مناسب پيغام­ها، يک تابع احتمال تعريف شده است که گره­ها پيغام­های دريافتی را بر مبنای آن بازپخش می­کنند. تابع احتمال پيشنهاد شده يک تابع احتمال تطبيقی است که مقدار آن را با آگاهی از چگالی محلی شبکه (تعداد همسايگان مرتبه اول) و تصميم گره­های اطراف (تعداد پيغام­های تکراری دريافت شده) با گذشت زمان بصورت متناوب تغيير داده و با شرايط شبکه وفق می­دهد. روش پيشنهادی به کمک شبيه­سازی مورد ارزيابی قرار گرفت. نتايج نشان می­دهد که اين روش ضمن کاهش قابل توجه تأخير الگوريتم، پوشش شبکه کاملی را ايجاد می­کند و سربار پيغام قابل قبولی دارد. همچنین، تأثیر مقادیر متفاوت حد آستانه مدت زمان انتظار بر کارایی الگوریتم را بررسی کردیم. این تغییرات بر پوشش شبکه تأثیری نداشته اما با افزایش مقدار حد آستانه انتظار متوسط تأخیر الگوریتم و نیز تعداد پیغام­های بازپخش نشده افزایش یافت.

يکی از نقاط قوت الگوريتم پيشنهادی اين است که نسبت به روش­های مشابه تأخير بسيار کمی (تقريباً برابر با تأخير الگوريتم سيل­آسا) دارد. به ويژه در شبکه­های با چگالی متوسط و پايين که سه الگوريتم ديگر تأخير بالايي دارند، الگوريتم Effective-CB عملکرد بسيار رضايتبخشی دارد. بنابراين می­تواند جايگزين روش­های پيشين در چنين شبکه­هايي شود. مخصوصاً در کاربردهای بلادرنگ که تأخير تحويل بسته­ها بايد کم باشد، اين روش بر روش­های مشابه ارجحيت دارد.

در کارهای آتی خود سعی می­کنیم که رابطه تأثیر مقدار حد آستانه مدت زمان انتظار را که در این مقاله بررسی کردیم، بصورت تابع ریاضی بیان کنیم. همچنین با دخالت دادن فاصله میان گره­های فرستنده و گیرنده در این رابطه بر دقت آن بیفزاییم. شبیه­سازی­های اولیه نشان می­دهد که دخیل کردن فاکتور فاصله باعث بهبود کارایی الگوریتم می­شود.

مراجع:

[1]       Johnson, D. B., Maltz, D. A., Broch, J., “The dynamicsource routing protocol for multihop wireless ad hoc networks(DSR)”, In Ad Hoc Networking, edited by Charles E. Perkins, chapter 5, PP. 139-172. Addison-Wesley, 2001.

[2]       Perkins, C., Royer, E., “Ad-hoc On-Demand Distance Vector Routing”, Proc. of 2ndIEEE Workshop on Mobile Computing Systems and Applications, 1999.

[3]       Haas, Z., Pearlman, M., “ZRP: a hybrid framework for routing in Ad Hoc networks”, IETF MANET. Internet Draft, Dec 1997.

[4]       Ko, Y., Vaidya, N., “Location‐Aided Routing (LAR) in mobile ad hoc networks”, Wireless Networks journal, Vol.6, No.4, 2000.

[5]       Ni, S., Tseng, Y., Chen, Y. and Sheu, J., “The Broadcast Storm Problem in a Mobile Ad Hoc Network”, Proc. 5th ACM/IEEE Int Conference on Mobile Computing and Networking (MOBICOM), pp. 151-162, New York, NY, USA, 1999.

[6]       Wu, J., Dai, F., “Broadcasting in Ad Hoc Networks Based on Self-Pruning”, Proc. INFOCOM ‘3, vol. 3, pp. 2240-2250, 2003.

[7]       Qayyum, A., Viennot, L., Laouiti, A., “Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks”, Proc. 35th annual Hawaii International Conference, pp.3866- 3875, 2002.

[8]       Calinescu, G., Mandoiu, I. I., Wan, P., Zelikovsky, A. Z.,“Selecting forwarding neighbors in wireless ad hoc networks,” Mob. Netw. Appl., vol. 9, no. 2, pp. 101–111, 2004.

[9]       Stojmenovic, I., Seddigh, M., Zonic, J., “Domonating Sets and Neighbor Elimination-based Broadcasting Algorithms in Wireless Networks”, IEEE Trans, Parallel Distrib. Syst., vol. 13, no. 1, pp. 14-25, 2002.

[10]       Stojmenovic, I., “Comments and Corrections to’ Domonating Sets and Neighbor Elimination-based Broadcasting Algorithms in Wireless Networks’”, IEEE Trans, Parallel Distrib. Syst., vol. 15, no. 11, pp. 1054-1055, 2004.

[11]       Lou, W., Wu, J., “A cluster-based backbone infrastructure for broadcasting in manets,” Proc. International Parallel and Distributed Processing Simposium, IEEE Computer Society, pp. 221.1, 2003.

[12]       Tseng, Y., Ni, S. and Shih, E. Y., "Adaptive Approaches to Relieving Broadcast Storms in a Wireless Multihop Mobile Ad Hoc Network", IEEE Trans. on Computers, vol. 52, 2003.

[13]       Pleisch, S., Balakrishnan, M., Birman, K. and Renesse, R., “Mistral: Efficient Flooding in Mobile Ad-hoc Networks”, Proc. 7th ACM Int. symposium on Mobile Ad Hoc Networking andComputing, pp. 1-12, Florence, Italy, 2006.

[14]       Keshavarz-Haddad, A., Riberio, V., “Color-Based Broadcasting for Ad Hoc Networks”, Proc. International Symposium in modeling and optimization in mobile, ad hoc and wireless networks, pp1-10, April 2006.

[15]       Chen, C., Hsu, C., Wang, H., "A distance-aware counter-based broadcast scheme for wireless ad hoc networks," Military Communications Conference. IEEE, vol. 2, pp. 1052- 1058, 2005.

[16]       Al-Humoud, O. S., Mackenzie, L., Ould-Khaoua, M. and Abdulai, J., “A Mobility Analysis of Adjusted Counter-Based Broadcast in MANET’s”, In The 9th annual PostGraduate Symposium on the Convergence of Telecommunications, Networking and Broadcasting (PGTNET), Liverpool, England, 23-24 June 2008,.

[17]       Izumi, Sh., Takeuchi, T., Matsuda, T., Kawaguchi, H., Ohta, C., Yoshimoto, M., “Counter-Based Broadcasting with Hop Count Aware Random Assessment Delay Extension for Wireless Sensor Networks”, IEICE Trans, COMMUN, vol E91-B, no 11,pp. 3489-3498, 2008.

[18]       Mohammed, A., Ould-Khaoua, M. and Mackenzie, L., “An Efficient Counter-Based Broadcast Scheme for Mobile Ad Hoc Networks”, Proc. 4th European Performance Engineering Workshop (EPEW 2007), Lecture Notes in Computing Science, vol. 4748, K. Wolter, Ed. Berlin, Germany: Springer-Verlag, pp. 275-283, 2007.

[19]       Nourazar, F., Sabaei, M., “DAPF: An Efficient Flooding Algorithm for Mobile Ad-hoc Networks”, Proc. International Conference on Signal Processing Systems, pp. 594-598, Singapore, 2009.

[20]       Nourazar, F., Sabaei, M.,”Adjusting threshold in Counter-Based algorithm”, “Technical Report”, Qazvin Azad University, 2009.

[21]       UCLA Parallel Computing Laboratory and Wireless Adaptive Mobility Laboratory. GloMosim:. A scalable simulation environment for wireless and wired network systems http:/pcl.cs.ucla.edu/.

 

[1]  . Broadcasting.

[2]  . Broadcast storm.

[3]  .Expected Additional Coverage.

[4]  . Random Access Delay.


Related articles

The rights to this website are owned by the Raimag Press Management System.
Copyright © 2017-2024

Home| Login| About Rimag| Contact Us|
[فارسی] [العربية] [fa] [ar]