New analysis on mobile agents based network routing

Abstract

In this paper, we consider the problem of mobile agent based network routing. We analyze the probability of success (the probability that an agent can find the destination) and the population growth of mobile agents under an ant-routing algorithm. First, We give an estimation on the probability of success, P(d), than an agent can find the destination in d jumps as P(d) ≤ /1n(1-/1n)d (σ1-1/σ1)d-1, n is the number of nodes in the network, and σ1, σn, are the largest and smallest degrees of nodes in the network respectively. The probability of success that k agents can find the destination in d jumps is estimated as P*(d) ≤ 1 - (n-1/n+σ1-1)k, where k is the number of agents generated per request. Second, the distribution of mobile agents in the network is analyzed, p→(t) = (I + A + ... + At-1)km e→ when 0 < t ≤ d and p→ = (I + A + .... + Ad-1)kme→ when t > d, where A is a matrix derived from the connectivity matrix. We further estimate that the number of agents running in the network is less than n2 σ1 km/n+σ1-1, and the populaUon of mobile agents running in each host, pj(t), satisfies: km + (1 -ξd-1)[1 - 1/n(1-ξ)](Dj - 1)km ≤ pj(t) ≤ km + (1 - ζd-1)[1 - 1/n(1-ζ)](Dj - 1)km, where ξ = ||A||1 = max1≤j≤n||aj||1, ζ = min1≤j≤n ||aj||1, aj is the jth column of matrix A, and Dj is the degree of the jth host.