یک الگوریتم سیل‌آسای مبتنی بر احتمال تطابقی برای شبکههای موردی سیار
محورهای موضوعی : فناوری اطلاعات و ارتباطاتفاطمه نورآذر 1 , مسعود صبائی 2
1 - دانشگاه آزاد اسلامی واحد قزوين
2 -
کلید واژه: شبکههای موردی سیار, الگوریتم سیل‌آسا, الگوریتم مبتنی بر شمارش, احتمال بازپخشی,
چکیده مقاله :
الگوریتم سیل‌آسا، یکی از مهمترین عملیات اولیه و زیربنایی برای پروتکلهای مسیریابی در شبکههای موردی سیار است. اما، از آنجایی که این الگوریتم پیغامهای اضافی زیادی تولید میکند، بسیار پرهزینه بوده، باعث اتلاف پهنای باند شبکه، مصرف بیش از نیاز انرژی گرهها شده که در نهایت ممکن است موجب طوفان همه پخشی شود. روشهای زیادی برای بهبود الگوریتم سیل‌آسا پیشنهاد شده است که عمدتاً به دو دسته روشهای قطعی و احتمالی تقسیم میشوند که دسته دوم بیشتر مورد توجه قرار گرفته است. اما این روشها عمدتاً باعث افزایش تأخیر و عدم پوشش کامل میشوند. در این مقاله، ما یک روش جدید برای بهبود عملکرد الگوریتم سیل‌آسا پیشنهاد کرده‌ایم. اساس کار این روش بازپخش احتمالی بر مبنای مشاهدات محلی میباشد. در این روش جدید احتمال بازپخش پیغام توسط هر گره، تابعی از مشاهدات محلی میباشد. نتایج شبیه‌سازی نشان داده است که روش پیشنهادی در مقایسه با روشهای مشابه ضمن کاهش قابل توجه تأخیر تحویل بستهها با سربار پیغام قابل قبول پوشش کامل شبکه را فراهم میکند.
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.
فصلنامه علمي- پژوهشي فناوري اطلاعات و ارتباطات ایران | سال دوم، شماره‌هاي5و6، پاييز و زمستان 1389 صص: 35- 27 |
|
یک الگوریتم سیل‌آسای مبتنی بر احتمال تطابقی برای شبکههای موردی سیار
فاطمه نورآذر▪ * مسعود صبائی **
* کارشناس ارشد، دانشکده مهندسی برق، رايانه و فناوری اطلاعات، دانشگاه آزاد اسلامی واحد قزوين
** استادیار، دانشکده مهندسی کامپيوتر و فناوری اطلاعات، دانشگاه صنعتی اميرکبير
تاريخ دريافت: 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 است.
شکل 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 که به معنی منصرف شدن از بازپخشی میباشد.
شکل 2: تغيير مقدار احتمال بازپخشی در زمانهای مختلف.
بنابراين میتوان رابطه کلی زير را برای محاسبه احتمال معرفی نمود:
(1)
که 
تعداد پیغامهای تکراری دریافت شده تا مرحله زمانی 
ام است، 
حد آستانه شمارشگر و 
تعداد همسایگان مرتبه اول است.
با توجه به تابع احتمال پيشنهاد شده نحوه عملکرد اين الگوريتم به گونهای است که سعی مي‌کند در کمترين زمان ممکن بيشترين ميزان بازپخشی را انجام دهد و پوشش کامل در شبکه ايجاد کند. به همين علت هم هست که ميزان تأخير الگوريتم را به طرز قابل توجهی کاهش میدهد. گره A در شکل 3، در منطقهای قرار گرفته که 9 همسايه مرتبه اول دارد. با دريافت هر پيغام تکراری مساحت پوشش اضافی مورد انتظار گره A کاهش میيابد. در بدترين حالت، اگر گره فرستنده B در دورترين فاصله ممکن از A قرار گرفته باشد، 
از محدوده ارسال گره A را پوشش میدهد. لذا لزومی ندارد که گره A مانند مرحله قبل با مقدار احتمال بالا بازپخش کند. بلکه با دخالت دادن مشاهدات خود در اين بازه زمانی ميزان احتمال را کاهش میدهد. اگر 3 گره از 9 گره پيغام را بازپش کنند محدوده ارسال A کاملاً پوشش داده میشود. لذا A ديگر پيغام را بازپخش نمیکند.
در الگوريتم سيلآسای کلاسيک در شرايط مشابه، هر 9 گره همسايه و نيز گره A پيغام را بازپخش میکنند. بنابراين در يک محدوده ارسال کوچک 10 پيغام را تقريباً بصورت همزمان ارسال میکند. الگوريتم مبتنی بر شمارش، در اين شرايط تقريباً مانند الگوريتم پيشنهادی ما عمل میکند با اين تفاوت که به ازای کاهش سربار پيغام تأخير بالايي را به الگوريتم تحميل میکند.
شکل 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 مشکل تأخير الگوريتم مبتنی بر شمارش را برطرف کرده است.
شکل 4: متوسط تأخير الگوريتمها در شبکههای با چگالی زياد، متوسط وکم.
نتايج شبيه سازی ما در شکل 5 نشان میدهد که الگوريتم پيشنهادی ما ضمن کاهش ميزان تأخير الگوريتم مبتنی بر شمارش نرخ بالای پوشش شبکهای را که الگوريتم مبتنی بر شمارش ايجاد میکند حفظ نمايد. الگوريتمهای مورد مقايسه ECS و DAPF پوشش شبکه مناسبی بويژه در شبکههای با چگالی پايين ندارند و البته اين مشکل يکی از نقاط ضعف جدی آنها به شمار میرود.
شکل 5: نمودار پوشش شبکة الگوريتمها در شبکههای با چگالی کم، متوسط و زياد.
معيار سومی که ما به کمک آن عملکرد الگوريتم خود را ارزيابی کردهايم تعداد پيغامهای صرفه جوييشده توسط الگوريتمهاست. همانطور که نمودارها نشان میدهند الگوريتمهای ECS و DAPF تعداد پيغامهای بيشتری را نسبت به الگوريتم ما صرفهجويي کردهاند. ولی بايد توجه داشته باشيم که اين موفقيت با هزينه از دست دادن پوشش شبکه کامل و نيز افزايش تأخير الگوريتم به دست آمده است. بنابراين اگر نتايج اين سه معيار ارزيابی را در نظر بگيريم نتيجه میگيريم که الگوريتم پيشنهادی ما عملکرد بهتری نسبت به سه الگوريتم مورد مقايسه دارد.
شکل 6: نمودار درصد پيغامهای بازپخشی صرفهجويي شده در شبکههای با چگالی زياد، متوسط و کم.
5-1-تأثیر مقادیر متفاوت حد آستانه مدت زمان انتظار بر عملکرد الگوریتم:
در این بخش از مقاله نشان خواهیم داد که با تغییر مدت زمان انتظار گرهها عملکرد الگوریتم چگونه تغییر میکند. ما مقدار آستانه مدت زمان انتظار را از 12 میلی ثانیه تا 160 میلی ثانیه تغییر دادیم و رفتار الگوریتم را مطالعه کردیم. شکل 7 تأثیر این تغییرات را بر میزان پوشش شبکه الگوریتم نشان میدهد. همانگونه که نمودارها نشان میدهند این تغییرات بر میزان پوشش شبکه الگوریتم بیتأثیر است. در شکلهای 7 تا 9 “d” نشاندهنده مقدار متوسط چگالی شبکه است.
شکل 8 بیان میکند که هر چه مقدار حد آستانه را بزرگتر در نظر بگیریم، الگوریتم تمایل به ذخیره پیغام بیشتری دارد. تعداد پیغامهای بازپخش شده در 
نسبت به 
حدود 15-20% کاهش نشان میدهد. نتایج نشان داده شده در شبکههای با چگالی بالا و متوسط به دست آمده است. نتایج شبیهسازیها در شبکههای تنک نشان میدهد که تغییرات مقادیر 
تأثیر قطعی و قابل توجیهی بر رفتار الگوریتم ندارد.
شکل 7: تأثیر تغییرات مدت زمان انتظار بر پوشش شبکه.
شکل8: تأثیر تغییرات مدت زمان انتظار بر تعداد پیغامهای بازپخشی.
در نهایت، تأثیر این تغییرات را بر مقدار متوسط تأخیر الگوریتم بررسی کردیم. همانطور که شکل 9 نشان میدهد در تمام سناریوها با اقزایش مقدار حد آستانه متوسط تآخیر نیز افزایش مییابد. مقایسه نمودارها نشان میدهد که تأثیر افزایش مقدار آستانه بر روی الگوریتمهای با C=3 بیشتر از C=4 است. همچنین، در سناریوهای با چگالی بالا (d=26 و d=9) با افزایش مقدار آستانه، الگوریتم کارایی خود را از دست میدهد. زیرا در این شبکهها با توجه به نزدیکی گرهها به یکدیگر و تعداد زیاد آنها الگوریتم به طور طبیعی تمایل دارد که عمل بازپخشی را در زمان کمی انجام دهد و لذا انتخاب مقادیر بزرگ Tmax نه تنها کمکی به کمتر کردن میزان تأخیر نمیکند بلکه نتیجه عکس نیز دارد.
با مقایسه نمودارهای شکل 8 و 9 میتوان نتیجه گرفت که باید میان معیارهای متوسط تأخیر و تعداد پیغامهای بازپخشی یکی را برگزینیم. در برنامههای کاربردی بی درنگ که متوسط تأخیر اهمیت زیادی دارد، باید مقدار Tmax را کوچک در نظر گرفته تعداد پیغامهای بازپخشی بالا را نادیده بگیریم. اما اگر کمتر بازپخش کردن پیغامها برای ما اهمیت دارد باید مقدار Tmax را بزرگ انتخاب کنیم تا در نهایت به نتیجه مطلوب خود برسیم.
شکل 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.
