Abstract
A basic problem in the quality-of-service (QoS) analysis of multiagent distributed systems is to find optimal routes for the mobile agents that incrementally fuse the data as they visit hosts in the distributed system. The system is modeled as a directed acyclic graph in which the nodes represent hosts and the edges represent links between them. Each edge is assigned a cost (or benefit) and weights that represent link delay, reliability, or other QoS parameters. The agent scheduling problem is viewed as a constrained routing problem in which a maximum-benefit (or minimum-cost) route connecting the source and the destination subject to QoS constraints is to be found. We study approximation algorithms called ‘fully polynomial time approximation schemes’ (FPTAS) for solving the problem. We suggest an accelerating technique that improves known FPTAS, e.g., Hassin’s (1992); Camponogara & Shima’s (2010); and Elalouf et al. (2011) algorithms, and present new FPTASs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Guilfoyle, C., Warner, E.: Intelligent Agents: New Revolution in Software, p. 214. Ovum Ltd. Publisher, London (1994)
Torsun, I.S.: Foundations of Intelligent Knowledge-Based Systems, p. 507. Academic Press, London (1995)
Jennings, N.R., Wooldridge, M.J.: Applications of Intelligent Agents. In: Jennings, N.R., Wooldridge, M.J. (eds.) Agent Technology: Foundations, Applications and Markets, pp. 3–28. Springer, Heidelberg (1998)
Shen, W., Norrie, D.H., Barthes, J.-P.: Multi-Agent Systems for Concurrent Intelligent Design and Manufacturing, p. 386. Taylor and Francis, London (2001)
White, J.E.: Telescript Technology: The Foundation for the Electronic Marketplace, White Paper. General Magic, Inc., USA (1994)
Tsichritzis, D.: Objectworld, Office Automation. Springer, Heidelberg (1985)
Elalouf, A., Levner, E., Cheng, T.C.E.: Efficient Routing of Mobile Agents for Agent-based Integrated Enterprise Management: A General Acceleration Technique. LNBIP, vol. 88, pp. 1–20. Springer, Berlin (2011)
Papaioannou, T.: Using Mobile Agents to Improve the Alignment between Manufacturing and its IT Support Systems. In: Robotics and Autonomous Systems. Elsevier (1999)
Peng, Y., Finin, T., Labrou, Y., Chu, B., Long, J., Tolone, X., Boughannam, A.: A Multi-Agent System for Enterprise Integration. In: Proceedings of PAAM 1998, London, UK, pp. 155–169 (1998)
Qi, H., Iyengar, S.S., Chakrabarty, K.: Multi-Resolution Data Integration Using Mobile Agents in Distributed Sensor Networks. IEEE Trans. Systems, Man, and Cybernetics Part C: Applications and Rev. 31(3), 383–391 (2001)
Wu, Q., Rao, N.S.V., Barhen, J., Iyengar, S.S., Vaishnavi, V.K., Qi, H., Chakrabarty, K.: On Computing Mobile Agent Routes for Data Fusion in Distributed Sensor Networks. IEEE Transactions on Knowledge and Data Engineering 16(6), 740–753 (2004)
Gens, G.V., Levner, E.V.: Fast Approximation Algorithms for Job Sequencing with Deadlines. Discrete Applied Mathematics 3, 313–318 (1981)
Gens, G.V., Levner, E.V.: Fast Approximation Algorithms for Knapsack Type Problems. LNCIS, vol. 23. Springer, Berlin (1980)
Hassin, R.: Approximation Schemes for the Restricted Shortest Path Problem. Mathematics of Operations Research 17(1), 36–42 (1992)
Goel, A., Ramakrishnan, K.G., Kataria, D., Logothetis, D.: Efficient Computation of Delay-sensitive Routes from One Source to All Destinations. In: IEEE Infocom 2001, pp. 854–858. IEEE Press (2001)
Xue, G., Sen, A., Zhang, W., Tang, J., Thulasiraman, K.: Finding a Path Subject to Many Additive QoS Constraints. IEEE Transactions on Networking 15, 201–211 (2007)
Lorenz, D.H., Raz, D.: A Simple Efficient Approximation Scheme for the Restricted Shortest Path problem. Operations Research Letters 28(5), 213–219 (2001)
Ergun, F., Sinha, R., Zhang, L.: An Improved FPTAS for Restricted Shortest Path. Information Processing Letters 83(5), 287–291 (2002)
Camponogara, E., Shima, R.B.: Mobile Agent Routing with Time Constraints: A Resource Constrained Longest-Path Approach. Journal of Universal Computer Science 16(3), 372–401 (2010)
Sahni, S.: Algorithms for Scheduling Independent Tasks. Journal of the ACM 23(1), 116–127 (1976)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, ch. 24.2. MIT Press (2001)
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall, New Jersey (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Elalouf, A., Levner, E., Cheng, T.C.E. (2011). Computing Mobile Agent Routes with Node-Wise Constraints in Distributed Communication Systems. In: Batyrshin, I., Sidorov, G. (eds) Advances in Artificial Intelligence. MICAI 2011. Lecture Notes in Computer Science(), vol 7094. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25324-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-25324-9_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25323-2
Online ISBN: 978-3-642-25324-9
eBook Packages: Computer ScienceComputer Science (R0)