معرفي مورچه‌هاي به روزرسان جدول‌هاي مسيريابی گرههای مجاور در الگوريتم مسيريابي AntNet
محورهای موضوعی : مهندسی برق و کامپیوتر
آزاده سلطانی
1
(دانشگاه بجنورد)
محمدرضا اکبرزاده توتونچی
2
(دانشگاه فردوسی مشهد)
محمود نقيب‌زاده
3
(دانشگاه فردوسی مشهد)
کلید واژه: AntNetعامل‌هاي متحركمسيريابي شبكه,
چکیده مقاله :
مسيريابي كارا در شبکه تأثير مهمي در انتقال درست و سريع داده‌هاي الكترونيكي و بالابردن بهره‌وری شبکه از جمله ايجاد تأخير كم و گذردهي بالا دارد. در دهه اخير الگوريتم‌هاي مسيريابي جديدي بر اساس مفاهيم سيستمهاي چندعامله، پيشنهاد شده‌اند. يکي از اين الگوريتم‌ها، AntNet است که در مقايسه با روشهاي قبلي داراي کارايي بهتري در واكنش نسبت به تغييرات شبكه ميباشد. اما الگوريتم AntNet نيز دارای نقطه‌ضعف‌هايي مانند همگرايي نسبي ديرهنگام است. در اين مقاله سعي شده است اين مشكل تا حدي رفع شود. پيشنهاد ما افزودن نوعي مورچه کمکي برای افزايش همکاري بين گرههاست تا زمان رسيدن به همگرايي در شبکه و واکنش نسبت به تغييرات شبکه سريعتر گردد. اين روش تعميمي از روش پيشنهادي قبلي است كه مورچه‌هاي كمكي در نودهاي مياني نيز ايجاد مي‌شوند. به منظور ارزيابي كارايي، الگوريتم در محيط 2NS پياده‌سازي شده و آزمايش‌هاي متعددي در شبكه‌هاي NSFNet و NTTNet انجام گرديده است. تحليل آماري نتايج اين آزمايش‌ها، نشان ميدهد استفاده از روش جديد رسيدن به همگرايي را در اكثر مواقع سريعتر ساخته است. در اين آزمايش‌ها، تأخير تا 5% و تغييرات تأخير تا 6% كاهش پيدا كرده است. اين در حالي است كه حتي با كاهش آهنگ توليد عامل‌ها، الگوريتم جديد با سربار كمتر نيز، كارايي بهتري نسبت به الگوريتم اصلي دارد.
Appropriate routing in data transfer is a challenging problem that can lead to improved performance of networks in terms of lower delay in delivery of packets and higher throughput. Considering the highly distributed nature of networks, several multi-agent based algorithms, and in particular ant colony based algorithms, have been suggested in recent years. However, considering the need for quick optimization and adaptation to network changes, improving the relative slow convergence of these algorithms remains an elusive challenge. Our goal here is to reduce the time needed for convergence and to accelerate the routing algorithm’s response to network failures and/or changes by imitating pheromone propagation in natural ant colonies. More specifically, information exchange among neighboring nodes is facilitated by proposing a new type of ant (assistant ants) to the AntNet algorithm. This method is an extension of authors’ earlier work by allowing intermediate nodes, in addition to destination nodes, to produce assistant ants. The resulting algorithm, the “modified AntNet,” is then simulated via NS2 on NSF and NttNet network topologies. The network performance is evaluated under various conditions. Statistical analysis of results confirms that the new method can significantly reduce the average packet delivery time and rate of convergence to the optimal route when compared with standard AntNet. Index Terms: AntNet, mobile agent, network routing, assistant ants. Nashriyyah -i Muhandisi -i Barq va Muhandisi -i Kampyutar -i Iran, vol. 5, no. 1, pp. 41-46, Spring 2007. * Corresponding author’s address: Dept. of Electrical Engineering, Birjand University, P. O. Box 97175-376, Birjand, I. R. Iran. Solving Multi-Criteria Decision Making Problems Using Artificial Neural Networks M. Abdoos* and N. Mozayani Abstract: Decision making is finding the best compromised solution from all feasible alternatives. Multi-criteria decision making is one of the most applied branches of decision making. Many methods have been presented for solving MCDM problems ever since. Among these methods, simple additive weighting, SAW, is the most commonly used method. In this paper, two methods are proposed for solving MCDM problems based on artificial neural networks. This paper shows an application of soft computing techniques in classic problems, such as decision making. Herein, two methods are presented based on both supervised and unsupervised neural networks. The results of the methods have been compared with SAW. Index Terms: Multi-criteria decision making, simple additive weighting method, perceptron network, artificial neural network, Kohonen network. Nashriyyah -i Muhandisi -i Barq va Muhandisi -i Kampyutar -i Iran, vol. 5, no. 1, pp. 47-52, Spring 2007. * Corresponding author’s address: Dept. of Computer Eng., Iran University of Science and Technology, Narmak, Tehran, 16845, I. R. Iran. Appropriate routing in data transfer is a challenging problem that can lead to improved performance of networks in terms of lower delay in delivery of packets and higher throughput. Considering the highly distributed nature of networks, several multi-agent based algorithms, and in particular ant colony based algorithms, have been suggested in recent years. However, considering the need for quick optimization and adaptation to network changes, improving the relative slow convergence of these algorithms remains an elusive challenge. Our goal here is to reduce the time needed for convergence and to accelerate the routing algorithm’s response to network failures and/or changes by imitating pheromone propagation in natural ant colonies. More specifically, information exchange among neighboring nodes is facilitated by proposing a new type of ant (assistant ants) to the AntNet algorithm. This method is an extension of authors’ earlier work by allowing intermediate nodes, in addition to destination nodes, to produce assistant ants. The resulting algorithm, the “modified AntNet,” is then simulated via NS2 on NSF and NttNet network topologies. The network performance is evaluated under various conditions. Statistical analysis of results confirms that the new method can significantly reduce the average packet delivery time and rate of convergence to the optimal route when compared with standard AntNet. Index Terms: AntNet, mobile agent, network routing, assistant ants. Nashriyyah -i Muhandisi -i Barq va Muhandisi -i Kampyutar -i Iran, vol. 5, no. 1, pp. 41-46, Spring 2007. * Corresponding author’s address: Dept. of Electrical Engineering, Birjand University, P. O. Box 97175-376, Birjand, I. R. Iran. Solving Multi-Criteria Decision Making Problems Using Artificial Neural Networks M. Abdoos* and N. Mozayani Abstract: Decision making is finding the best compromised solution from all feasible alternatives. Multi-criteria decision making is one of the most applied branches of decision making. Many methods have been presented for solving MCDM problems ever since. Among these methods, simple additive weighting, SAW, is the most commonly used method. In this paper, two methods are proposed for solving MCDM problems based on artificial neural networks. This paper shows an application of soft computing techniques in classic problems, such as decision making. Herein, two methods are presented based on both supervised and unsupervised neural networks. The results of the methods have been compared with SAW. Index Terms: Multi-criteria decision making, simple additive weighting method, perceptron network, artificial neural network, Kohonen network. Nashriyyah -i Muhandisi -i Barq va Muhandisi -i Kampyutar -i Iran, vol. 5, no. 1, pp. 47-52, Spring 2007. * Corresponding author’s address: Dept. of Computer Eng., Iran University of Science and Technology, Narmak, Tehran, 16845, I. R. Iran. Appropriate routing in data transfer is a challenging problem that can lead to improved performance of networks in terms of lower delay in delivery of packets and higher throughput. Considering the highly distributed nature of networks, several multi-agent based algorithms, and in particular ant colony based algorithms, have been suggested in recent years. However, considering the need for quick optimization and adaptation to network changes, improving the relative slow convergence of these algorithms remains an elusive challenge. Our goal here is to reduce the time needed for convergence and to accelerate the routing algorithm’s response to network failures and/or changes by imitating pheromone propagation in natural ant colonies. More specifically, information exchange among neighboring nodes is facilitated by proposing a new type of ant (assistant ants) to the AntNet algorithm. This method is an extension of authors’ earlier work by allowing intermediate nodes, in addition to destination nodes, to produce assistant ants. The resulting algorithm, the “modified AntNet,” is then simulated via NS2 on NSF and NttNet network topologies. The network performance is evaluated under various conditions. Statistical analysis of results confirms that the new method can significantly reduce the average packet delivery time and rate of convergence to the optimal route when compared with standard AntNet. Index Terms: AntNet, mobile agent, network routing, assistant ants. Nashriyyah -i Muhandisi -i Barq va Muhandisi -i Kampyutar -i Iran, vol. 5, no. 1, pp. 41-46, Spring 2007. * Corresponding author’s address: Dept. of Electrical Engineering, Birjand University, P. O. Box 97175-376, Birjand, I. R. Iran. Solving Multi-Criteria Decision Making Problems Using Artificial Neural Networks M. Abdoos* and N. Mozayani Abstract: Decision making is finding the best compromised solution from all feasible alternatives. Multi-criteria decision making is one of the most applied branches of decision making. Many methods have been presented for solving MCDM problems ever since. Among these methods, simple additive weighting, SAW, is the most commonly used method. In this paper, two methods are proposed for solving MCDM problems based on artificial neural networks. This paper shows an application of soft computing techniques in classic problems, such as decision making. Herein, two methods are presented based on both supervised and unsupervised neural networks. The results of the methods have been compared with SAW. Index Terms: Multi-criteria decision making, simple additive weighting method, perceptron network, artificial neural network, Kohonen network. Nashriyyah -i Muhandisi -i Barq va Muhandisi -i Kampyutar -i Iran, vol. 5, no. 1, pp. 47-52, Spring 2007. * Corresponding author’s address: Dept. of Computer Eng., Iran University of Science and Technology, Narmak, Tehran, 16845, I. R. Iran. Appropriate routing in data transfer is a challenging problem that can lead to improved performance of networks in terms of lower delay in delivery of packets and higher throughput. Considering the highly distributed nature of networks, several multi-agent based algorithms, and in particular ant colony based algorithms, have been suggested in recent years. However, considering the need for quick optimization and adaptation to network changes, improving the relative slow convergence of these algorithms remains an elusive challenge. Our goal here is to reduce the time needed for convergence and to accelerate the routing algorithm’s response to network failures and/or changes by imitating pheromone propagation in natural ant colonies. More specifically, information exchange among neighboring nodes is facilitated by proposing a new type of ant (assistant ants) to the AntNet algorithm. This method is an extension of authors’ earlier work by allowing intermediate nodes, in addition to destination nodes, to produce assistant ants. The resulting algorithm, the “modified AntNet,” is then simulated via NS2 on NSF and NttNet network topologies. The network performance is evaluated under various conditions. Statistical analysis of results confirms that the new method can significantly reduce the average packet delivery time and rate of convergence to the optimal route when compared with standard AntNet.
[1] C. Hedrick, Routing Information Protocol, RFC 1058, Jun. 1998.
[2] J. Moy, OSPF Version 2, RFC 1247, Jul. 1991.
[3] A. Amin, J. T. Mayes, and A. R. Mikler, "Agent-based distance vector routing," in Proc. 3rd Int. Workshop MATA, pp.41-50, 2001.
[4] R. Schoonderwoerd, O. Holland, and J. Bruten, "Ant-like agent for load balancing in telecommunications network," in Proc. of the 1st Int. Conf. on Autonomous Agents, pp. 209-216, 1997.
[5] G. D. Caro and M. Dorigo, "Mobile agent for adaptive routing," in Proc. 31st Hawaii Int. Conf. on System Science, 1998.
[6] G. D. Caro and M. Dorigo, "AntNet: distributed stigmergetic control for communications networks," J. of Artificial Intelligence Research,vol. 9, pp. 317-365, 1998.
[7] B. Baran and R. Sosa, "AntNet routing algorithm for data networks based on mobile agents," Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial, vol. 12, pp. 75-84, 2001.
[8] I. Kassabalidis, M. A. El-Sharkawi, R. J. Marks, P. Arabshahi, and A. A. Gray, "Adaptive-SDR: adaptive swarm-based distributed routing," in Proc. of Int. Joint Conf. on Neural Networks, IJCNN'02,vol. 1, pp. 351-354, 2002.
[9] S. Marwaha, C. khong Tham, and D. Serinvasan, A Novel Routing Protocol Using Mobile Agents and Reactive Rout Discovery for Ad hoc Wireless Networks, http://citeseer.nj.nec.com/534795.html
[10] Z. Subing and L. Zemin, "A qos routing algorithm based on ant algorithm," in Proc. 25th Annual IEEE Conf. on Local Computer Networks, LCN 2000, pp. 574-578, 2000.
[11] A. Soltani, M. R. Akbarzadeh, and M. Naghibzadeh, "Introducing helping ant in AntNet application to NSFNet," in Proc. of the Iranian Conf. Electrical Eng., ICEE2004, pp. 56-61, Mashhad, Iran,May 2004.
[12] A. Soltani, M. R. Akbarzadeh, and M. Naghibzadeh, "Helping ants for adaptive network routing," Accepted for Publication at the J. of Franklin Institute, vol. 343, no. 4-5 ,pp. 389-403, Jan. 2006.
[13] C. Spatz and J. O. Johnston, Basic Statistics, Books/Cole Publishing Company, Pacific Grove, California.
[14] G. D. Caro and M. Dorigo, "AntNet: distributed stigmergic control for communications networks," J. of Artificial Intelligence Research,vol. 9, pp. 317-365, 1998.