Computing mobile agent routes with node-wise constraints in distributed communication systems

Amir Elalouf, Eugene Levner, Edwin Tai Chiu Cheng

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

4 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationAdvances in Artificial Intelligence - 10th Mexican International Conference on Artificial Intelligence, MICAI 2011, Proceedings
Pages76-87
Number of pages12
EditionPART 1
DOIs
Publication statusPublished - 6 Dec 2011
Event10th Mexican International Conference on Artificial Intelligence, MICAI 2011 - Puebla, Mexico
Duration: 26 Nov 20114 Dec 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7094 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th Mexican International Conference on Artificial Intelligence, MICAI 2011
CountryMexico
CityPuebla
Period26/11/114/12/11

Keywords

  • Acceleration technique
  • Agent routing
  • FPTAS
  • Mobile agent
  • Multi-agent distributed systems
  • Routing algorithm

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this