research-article

A state-dependent time evolving multi-constraint routing algorithm

Authors:

Abdelhamid Mellouk,

Sherali ZeadallyAuthors Info & Claims

ACM Transactions on Autonomous and Adaptive Systems (TAAS), Volume 8, Issue 1

Article No.: 6, Pages 1 - 21

https://doi.org/10.1145/2451248.2451254

Published: 19 April 2013 Publication History

Abstract

This article proposes a state-dependent routing algorithm based on a global optimization cost function whose parameters are learned from the real-time state of the network with no a priori model. The proposed approach samples, estimates, and builds the model of pertinent and important aspects of the network environment such as type of traffic, QoS policies, resources, etc. It is based on the trial/error paradigm combined with swarm-adaptive approaches. The global system uses a model that combines both a stochastic planned prenavigation for the exploration phase with a deterministic approach for the backward phase. We conducted a performance analysis of the proposed algorithm using OPNET based on several topologies such as the Nippon telephone and telegraph network. The simulation results obtained demonstrate substantial performance improvements over traditional routing approaches as well as the benefits of learning approaches for networks with dynamically changing traffic.

References

[1]

Babaoglu, O., Canright, G., Deutsch, A., Di Caro, G. A., Ducatelle, F., et al. 2006. Design pattern from biology for distributed computing. ACM Trans. Auton. Adapt. Syst. 1, 1, 26--66.

Digital Library

[2]

Baguenine, F. and Mellouk, A. 2009. QoS swarm state dependent routing for irregular traffic in telecommunication networks. In Proceedings of the IEEE International Conference on Communications (ICC'09). 1482--1486.

Digital Library

[3]

Bottou, L. 2004. Stochastic Learning, Advanced Lectures on Machine Learning. Lecture Notes in Artificial Intelligence, vol. 3176., Springer, 146--168.

[4]

Boyan, J. A. and Littman, M. L. 1994. Packet routing in dynamically changing networks: A reinforcement learning approach. In Proceedings of the 7^th Conference on Advances in Neural Information Processing Systems 6 (NIPS'94). J. D. Cowan, G. Tesauro and J. Alspector, Eds., Morgan Kaufmann, San Fransisco, CA, 671--678.

[5]

Chakeres, I. and Perkins, C. 2009. Dynamic manet on-demand (dymo), routing draft-ietf-manet-dymo-17, dynamic manet on-demand (dymo) routing draft-ietf-manet-dymo-17. Internet Engineering Task Force. http://tools.ietf.org/html/draft-ietf-manet-dymo-17

[6]

Correia, S., Junior, J., and Cherkaoui, O. 2011. Mobility-Aware ant colony optimization routing for vehicular ad hoc networks. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC). 1125--1130.

[7]

Di Caro, G. and Dorigo, M. 1998. AntNet: Distributed stigmergetic control for communication networks. J. Artif. Intell. Res. 9, 317--365.

[8]

Di Caro, G., Ducatelle F., and Gambardella, L. M. 2005. AntHocNet: An adaptive nature-inspired algorithm for routing in mobile ad hoc networks. Euro. Trans. Telecomm. 16, 5, 443--455.

[9]

Dobson, S., Denazis, S., Fernandez, A., Gaiti, D., Gelenbe, E., et al. 2006. A survey of autonomic communications. ACM Trans. Auton. Adapt. Syst. 1, 2, 223--259.

Digital Library

[10]

Dorigo, M. and Stuzle, T. 2004. Ant Colony Optimization. MIT Press, Cambridge, MA.

Digital Library

[11]

Dorigo, M. and Blum, C. 2005. Ant colony optimization theory: A survey. Theor. Comput. Sci. 344, 2--3, 243--278.

Digital Library

[12]

Dressler, F. 2007. Self-Organized network security facilities based on bio-inspired promoters and inhibitors. In Advances in Biologically Inspired Information Systems - Models, Methods, and Tools, Studies in Computational Intelligence (SCI). F. Dressler and I. Carreras, Eds., Vol. 69, 81--98.

[13]

Dressler, F. and Akan, O. 2010. Bio-Inspired networking: From theory to practice. IEEE Comm. Mag. 48, 11, 176--183.

Digital Library

[14]

Ducatelle, F. 2007. Adaptive routing in ad hoc wireless multi-hop networks. Ph.D. thesis, Università della Svizzera Italiana, Istituto Dalle Molle di Studi sull´ Intelligenza Artificiale, Italy.

[15]

Eppstein, D. 1999. Finding the k shortest paths. SIAM J. Comput. 28, 2, 652--673.

Digital Library

[16]

Garey, M. R. and Jhonson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA.

Digital Library

[17]

Gelenbe, E. and Lent, R. 2004. Ad hoc power aware cognitive packet networks. Ad Hoc Netw. J. 2, 3, 205--216.

[18]

Goetz, P., Kumar, S., and Miikkulainen, R. 1996. On-Line adaptation of a signal predistorter through dual reinforcement learning. In Proceedings of the 13^th Annual Conference on Machine Learning.

[19]

Haykin, S. 1998. Neural Networks- A Comprehensive Foundation. Macmillan College Publishing Company.

Digital Library

[20]

Henig, M. 1983.Vector-Valued dynamic programming. SIAM J. Control Optim. 3, 490--499.

[21]

Kaelbling, L. P., Littman, M. L., and Moore, A. W. 1996. Reinforcement learning: A survey. J. Artif. Intell. Res. 4, 237--285.

[22]

Kuipers, F. and Van Mieghem, P. 2005. Conditions that impact the complexity of qos routing. IEEE/ACM Trans. Netw. 13, 4, 717--730.

Digital Library

[23]

Labella, T. and Dressler, F. 2006. A bio-inspired architecture for division of labour in sanets. In Proceedings of the 1^st International Conference on Bio Inspired Models of Network, Information and Computing Systems (BIONETICS'06).

Digital Library

[24]

Leibnitz, K., Wakamiya, N., and Murata, M. 2007. A bio-inspired robust routing protocol for mobile ad hoc networks. In Proceedings of 16^th International Conference on Computer Communications and Networks (ICCCN'07). 321--326.

[25]

Manish, J. and Dovrolis, C. 2002. Pathload: A measurement tool for end-to-end available bandwidth. In Proceedings of the Passive and Active Measurements Workshop. 14--25.

[26]

Martins, J., Correia, S., and Celestino, J. 2010. Ant-DYMO: A bio-inspired algorithm for manets. In Proceedings of the 17^th IEEE International Conference on Telecommunication (ICT). 748--754.

[27]

Mellouk, A., Hoceini, S., and Zeadally, S. 2009. Design and performance analysis of an inductive qos routing algorithm. Comput. Comm. 32, 12, 1371--1376.

Digital Library

[28]

Mellouk, A., Hoceini, S., and Zeadally, S. 2011. A bio-inspired quality of service (qos) routing algorithm. IEEE Comm. Lett. 15, 9, 1016--1018.

[29]

Ortega, C. and Tyrrell, A. 1999. Biologically inspired fault-tolerant architectures for real-time control applications. Control Engin. Pract. 7, 5, 673--678.

[30]

Ribeiro, V. J., Riedi, R. H., Baraniuk, R. G., Navratil, J., and Cottrell, L. 2003. PathChirp: Efficient available bandwidth estimation for network paths. In Proceedings of the Passive and Active Measurement Workshop.

[31]

Sahni, S. 2005. Data Structures, Algorithms, and Applications in C++, 2^nd ed. Silicon Press.

Digital Library

[32]

Saleem, K., Fisal, N., Hafizah, S., Kamilah, S., and Rashid, R. 2009. Biological inspired self-optimized routing algorithm for wireless sensor networks. In Proceedings of the 9^th IEEE Malaysia International Conference on Communications (MICC). 305--309.

[33]

Sutton, R. S. and Barto, A. G. 1997. Reinforcement Learning. MIT Press.

Digital Library

[34]

Tsypkin, Y. 1973. Foundations of the Theory of Learning Systems. Academic Press, New York.

[35]

Villalba, L., Canas, D., and Orozco, A. 2010. Bio-Inspired routing protocol for mobile ad hoc networks. IET Comm. 4, 18, 2187--2195.

[36]

Wang, Z. and Crowcroft, J. 1995. Bandwidth-Delay based routing algorithms. In Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM'95). Vol. 3, 2129--2133.

[37]

Waxman, B. M. 1991. Routing of multipoint connections. In Broadband Switching, C. Chas, V. K. Konangi, and M. Sreetharan, Eds., IEEE Computer Society Press, Los Alamitos, CA, 347--352.

Digital Library

[38]

Wedde, H. F., Farooq, M., Pannenbaecker, T., Vogel, B., Mueller, C., et al. 2005. BeeAdHoc: An energy efficient routing algorithm for mobile ad hoc networks inspired by bee behavior. In Proceedings of the Genetic and Evolutionary Computation Conference. 153--160.

Digital Library

Cited By

Bitam SMellouk AZeadally S(2015)Bio-Inspired Routing Algorithms Survey for Vehicular Ad Hoc NetworksIEEE Communications Surveys & Tutorials10.1109/COMST.2014.237182817:2(843-867)Online publication date: Oct-2016
https://doi.org/10.1109/COMST.2014.2371828
Sun YSun JZhao FHu Z(2014)Delay constraint multipath routing for wireless multimedia ad hoc networksInternational Journal of Communication Systems10.1002/dac.281429:1(210-225)Online publication date: 12-May-2014
https://doi.org/10.1002/dac.2814
Bitam SMellouk ABitam SMellouk A(2014)Bio‐Inspired Routing Protocols for VANETsBio‐Inspired Routing Protocols for Vehicular Ad Hoc Networks10.1002/9781119004967.ch4(79-119)Online publication date: 12-Sep-2014
https://doi.org/10.1002/9781119004967.ch4
Show More Cited By

Index Terms

A state-dependent time evolving multi-constraint routing algorithm
1. Networks
  1. Network protocols

Recommendations

A delay tolerant network routing algorithm based on multi‐step double Q‐learning
Abstract
Delay tolerant networks (DTNs) refer to a kind of novel wireless mobile network, where there is no constant end‐to‐end connection between network nodes due to frequent movement, sparse distribution and limited communication range of nodes. ...
The system model of k‐step double Q‐learning routing (K‐DQLR) combines the multi‐step and double Q‐learning algorithms. According to k‐step future rewards and double Q‐values, K‐DQLR can make an unbiased, accurate and efficient routing decision in DTNs. ...
Multi-constraint Multipath QoS Routing Using Swarm Intelligence
CICN '14: Proceedings of the 2014 International Conference on Computational Intelligence and Communication Networks

It is essential for a network to support guaranteed quality-of-service (QoS) for some applications on Internet. Robustness of the network plays an important role to achieve the basic QoS requirements to support real-time applications. Though it has been ...
Latency‐aware reinforced routing for opportunistic networks

In opportunistic networks, the path connecting two nodes is not continuous at any time instant. In such an environment, routing is an extremely taxing word owing to the ever‐changing nature of the network and random connections between nodes. Routing in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Autonomous and Adaptive Systems

ACM Transactions on Autonomous and Adaptive Systems Volume 8, Issue 1

April 2013

126 pages

ISSN:1556-4665

EISSN:1556-4703

DOI:10.1145/2451248

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 April 2013

Accepted: 01 June 2012

Revised: 01 May 2012

Received: 01 August 2011

Published in TAAS Volume 8, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Celtic and EUREKA initiative IPNQSIS (IP Network Monitoring for Quality of Service Intelligent Support)
Visiting Professorship Award from the University of Paris Est Creteil
Direction Générale de la Compétitivité, de l'Industrie et des Services
District of Columbia NASA Space Grant

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
341
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bitam SMellouk AZeadally S(2015)Bio-Inspired Routing Algorithms Survey for Vehicular Ad Hoc NetworksIEEE Communications Surveys & Tutorials10.1109/COMST.2014.237182817:2(843-867)Online publication date: Oct-2016
https://doi.org/10.1109/COMST.2014.2371828
Sun YSun JZhao FHu Z(2014)Delay constraint multipath routing for wireless multimedia ad hoc networksInternational Journal of Communication Systems10.1002/dac.281429:1(210-225)Online publication date: 12-May-2014
https://doi.org/10.1002/dac.2814
Bitam SMellouk ABitam SMellouk A(2014)Bio‐Inspired Routing Protocols for VANETsBio‐Inspired Routing Protocols for Vehicular Ad Hoc Networks10.1002/9781119004967.ch4(79-119)Online publication date: 12-Sep-2014
https://doi.org/10.1002/9781119004967.ch4
Mellouk AHoceini STran H(2013)BibliographyQuality of Experience for Multimedia10.1002/9781118649367.biblio(141-153)Online publication date: 6-Dec-2013
https://doi.org/10.1002/9781118649367.biblio

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents