یک الگوریتم سیلآسای مبتنی بر احتمال تطابقی برای شبکههای موردی سیار
محورهای موضوعی : عمومىفاطمه نورآذر 1 * , مسعود صبائی 2
1 - دانشگاه آزاد اسلامی واحد قزوين
2 - صنعتی امیر کبیر
کلید واژه: شبکه¬های موردی سيار, الگوريتم سيل¬آسا, الگوريتم مبتنی بر شمارش, احتمال بازپخشی,
چکیده مقاله :
الگوريتم سيل آسا، يکی از مهمترين عمليات اوليه و زيربنايي برای پروتکل های مسيريابی در شبکه های موردی سيار است. اما، از آن جايي که اين الگوريتم پيغام های اضافی زيادی توليد می کند، بسيار پرهزينه بوده، باعث اتلاف پهنای باند شبکه، مصرف بيش از نياز انرژی گره ها شده که در نهايت ممکن است موجب طوفان همه پخشی شود. روش های زيادی برای بهبود الگوريتم سيل آسا پيشنهاد شده است که عمدتاً به دو دسته روش های قطعی و احتمالی تقسيم می شوند که دستة دوم بيشتر مورد توجه قرار گرفته است. اما اين روش ها عمدتاً باعث افزايش تأخير و عدم پوشش کامل می شوند. در اين مقاله، ما يک روش جديد برای بهبود عملکرد الگوريتم سيل-آسا پيشنهاد کرده ايم. اساس کار اين روش بازپخش احتمالی بر مبنای مشاهدات محلی می باشد. در اين روش جديد احتمال بازپخش پيغام توسط هر گره، تابعی از مشاهدات محلی می-باشد. نتايج شبيه سازی نشان داده است که روش پيشنهادی در مقايسه با روش های مشابه ضمن کاهش قابل توجه تأخير تحويل بسته ها با سربار پيغام قابل قبول پوشش کامل شبکه را فراهم می کند
The flood algorithm is one of the most important primary operations and infrastructure for routing protocols in mobile ad hoc networks. However, since this algorithm generates many additional messages, it is very costly, it has caused a waste of network bandwidth, consuming more energy than the nodes need, which may eventually cause an all-broadcast storm. Many methods have been proposed to improve the flood algorithm, which are mainly divided into two categories of deterministic and probabilistic methods, and the second category has received more attention. But these methods mainly cause delay and lack of complete coverage. In this paper, we have proposed a new method to improve the performance of SIL-ASA algorithm. The basis of this probabilistic replay method is based on local observations. In this new method, the probability of message replay by each node is a function of local observations. The results of the simulation have shown that the proposed method provides complete network coverage in comparison with similar methods while significantly reducing the packet delivery delay with an acceptable message overhead.
[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/.