本文首先探討在網際網路與環境無關（context-free）的應用系統中派送行動代理人（mobile agent）至網際網路中大量的資訊源（data source）時，不同的派送排程（dispatch schedule）在相異的網路狀況下，所呈現的效能差異。本文希望了解是否有一種派送排程能夠在各種網路狀況下均能以最短的時間完成所有行動代理人的派送。

為了產生各種分派排程以滿足不同的網路狀況，我們以Prim的最小展開樹演算法（minimum spanning tree）為基礎，設計了Reweight演算法。接著在J-Sim網路模擬器之中，設計了MAPNet多重代理人系統；並以BRITE網路拓樸產生器（topology generator）產生的多個網路拓樸進行模擬。結果顯示：沒有任何派送排程能夠在各種網路狀況下均有最佳效能。派送排程的執行效能與分派排程本身的形狀、當時的網路狀況、甚至於排程起始點的位置均有密切關係。

因此選擇適當的派送排程是使行動代理人系統能夠儘快完成派送工作的一項重要因素。本文利用圖形理論（graph theory）中的居間-中心性（betweenness-centrality）發展出選擇指標（selector index）以區分不同結構的排程，並證明了其相關特性；針對具有相同結構卻有不同形狀的排程，我們設計了擴充選擇指標（extended selector index）對其做出區別。

最後本文對我們的MAPNet多重代理人系統進行說明。MAPNet是一個以事件驅動及任務導向的系統，具有相當的彈性以模擬行動代理人在不同的網路拓樸及網路狀況中的派送過程。在此系統的幫助下，我們能夠在類似網際網路的環境中進行本文中所需的各種模擬。

In this dissertation, we firstly explore efficiency differences between different schedules of dispatching mobile agent to a large number of data sources spread over the Internet and various network conditions in Internet context-free applications. We wish to know that there is a kind of dispatch schedules that can complete the dispatch of every mobile agent in the shortest time under all network conditions.

To generate every dispatch schedule to meet possible network conditions, we design the Reweight algorithm from Prim’'s minimum spanning tree algorithm. Then, in J-Sim network simulator, we design a multi-agent system called MAPNet and run simulations under several network topologies generated by BRITE network topology generator. The simulation results show that no single dispatch schedule can have the best efficiency under all network conditions. The efficiency of the dispatch schedule is closely determined by the shape itself, the network conditions it works under and even the location from which the schedule starts.

Therefore, to select a suitable dispatch schedule is an important factor for a mobile agent system to complete its dispatch task as soon as possible. In this dissertation, based on the betweenness-centrality concept in graph theory, we proposed a selector index to differentiate dispatch schedules with different structures and we also proved the related properties. For those schedules with the same structure but with different shapes we developed an extended selector index to discriminate between them.

Finally, we describe the design of our MAPNet multi-agent system. MAPNet is a state-driven and mission-based system that is flexible enough to simulate the mobile agent dispatch process under various network topologies and networking conditions. With the help of this system, we can run simulations required in this dissertation in an Internet-like environment.

[1] W. C. Cheng, C.-F. Chou, L. Golubchik, S. Khuller, and Y.-C.Wan, "Large-scale
data collection: a coordinated approach," in INFOCOM 2003, vol. 1, pp. 218-
228, Twenty-Second Annual Joint Conference of the IEEE Computer and Com-
munication Societies, (2003).
[2] D. Schoder and T. Eymann, "The real challenges of mobile agents," Commnica-
tions of the ACM, vol. 43, pp. 111-112, June (2001).
[3] A. Medina, I. Matta, and J. Byers, "On the origin of power-laws in internet
topologies," ACM SIGCOMM Computer Communication Review, vol. 30, pp. 18-
28, April (2000).
[4] B. Hu aker, M. Fomenkov, D. Moore, and kc cla y, "Macroscopic analyses of
the infrastructure: measurement and visualization of internet connectivity and
performance," in PAM'2001 (Passive and Active Measurements) workshop, (Am-
sterdam, The Netherlands), (2001).
[5] V. E. Paxson, "Measurements and Analysis of End-to-End Internet Dynamics".
PhD thesis, Information and Computing Sciences Division, University of Cali-
fornia at Berkeley, April (1997).
[6] B.-H. Yuan and C. C. Yang, "Exploiting the e ciency of proactive scheduling
of dispatching mobile agents in context-free internet applications," submitted to
Journal of Internet Technology.
[7] B.-H. Yuan, H.-Y. Chou, and C. C. Yang, "A selector index for mobile agent
dispatch schedules in context-free internet applications," International Journal
of Innovative Computing, Information and Control (IJICIC), vol. 6, pp. 2319-
2330, May (2010).
[8] A. Carzaniga, G. P. Picco, and G. Vigna, "Is code still moving around? looking
back at a decade of code mobility," in Proceedings of the 29th International
Conference on Software Engineering, IEEE Computer Society, (2007).
[9] S. S. Manvi and P. Venkataram, "Applications of agent technology in commu-
nications: a review," Computer Communications, vol. 27, pp. 1493-1508, June
(2004).
[10] R. H. Glitho, E. Olougouna, and S. Pierre, "Mobile agents and their use for infor-
mation retrieval: a brief overview and an elaborate case study," IEEE Network,
vol. 16, pp. 34-41, January / Faburary (2002).
[11] A. L. G. P. G. Knight, G. Pavlou, and G. Knight, "Exploiting agent mobility
for large-scale network monitoring," IEEE Network, vol. 16, pp. 7-15, May/June
(2002).
[12] T. Schlegel, P. Braun, and R. Kowalczyk, "Towards autonomous mobile agents
with emergent migration behaviour," in Proceedings of the fth international joint
conference on Autonomous agents and multiagent systems, (Hakodate, Japan),
ACM, (2006).
[13] J.-W. Baek, J.-H. Yeo, G.-T. Kim, and H.-Y. Yeom, "Cost e ective mobile agent
planning for distributed information retrieval," in 21st International Conference
on Distributed Computing Systems (ICDCS'01), pp. 65-72, IEEE Computer So-
ciety, (2001).
[14] J. Baek and H. Yeom, "d-agent: An approach to mobile agent planning for
distributed information retrieval," IEEE Transaction on Consumer Electronics,
vol. 49, pp. 115-122, February (2003).
[15] B. Brewington, R. Gray, K. Moizumi, D. Kota, G. Cybenko, and D. Rus, "Mobile
agents in distributed information retrieval," in Intelligent Information Agents
(M. Klusch, ed.), pp. 355-395, Springer-Verlag, (1999).
[16] K. Moizumi, The Mobile Agent Planning Problem. PhD thesis, Thayer School of
Engineering, Dartmouth College, Hanover, New Hampshire, October (1998).
[17] W. Theilmann and K. Rothermel, "Optimizing the dissemination of mobile
agents for distributed information ltering," IEEE Concurrency, vol. 8, pp. 53-
61, April (2000).
[18] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algo-
rithms. The MIT Press, Second ed., (2001).
[19] R. Agrawal, T. Lmielinski, and A. Swami, "Mining association rules between
sets of items in large databases," in International Conference on Management
of Data, Proceedings of the 1993 ACM SIGMOD international conference on
Management of data, pp. 207-216, May (1993).
[20] Y. Chi, Y. Yang, and R. r. Muntz, "Mining frequent rooted trees and free trees
using canonical forms," Technical Report, UCLA Computer Science Department,
(2004).
[21] M. Kuramochi and G. Karypis, "Frequent subgraph discovery," in First IEEE
International Conference on Data Mining (ICDM'01), Proceedings of the 2001
IEEE International Conference on Data Mining, pp. 313-320, IEEE Computer
Society, (2001).
[22] N. LI, Q. Li, and L. Wang, "Canonicalization of graph database records using
similarity measures," in Proceedings of the 2nd international conference on Ubiq-
uitous information management and communication (ACM, ed.), pp. 278-283,
(2008).
[23] A. Ohno and H. Murao, "Measuring source code similarity using reference vec-
tors," International Journal of Innovative Computing, Information and Control
(IJICIC), vol. 3, pp. 525-537, June (2007).
[24] D. Shasha and K. Zhang, "Fast algorithms for the unit cost editing distance
between trees," Journal of Algorithms, vol. 11, pp. 581-621, (1990).
[25] A. Nierman and H. V. Jagadish, "Evaluating structural similarity in xml doc-
uments," in Proceedings of the Fifth International Workshop on the Web and
Databases (WebDB 2002), pp. 61-66, June (2002).
[26] T. Sager, A. Bernstein, M. Pinzger, and C. Kiefer, "Detecting similar java classes
using tree algorithms," in Proceedings of the 2006 International Workshop on
Mining Software Repositories, MSR 2006, pp. 65-71, ACM, (2006).
[27] D. B. West, Introduction to Graph Theory. Prentice-Hall, Second ed., (2001).
[28] J. Dilley, B. Maggs, J. Parikh, H. Prokop, R. sitaraman, and B. Weihl, "Glob-
ally distributed content delivery," IEEE Internet Computing, vol. 6, pp. 50-58,
Sept/Oct (2002).
[29] A. Medina, A. Lakhina, I. Matta, and J. Byers, "Brite: An approach to universal
topology generation," in Proceedings of the International Workshop on Modeling,
Analysis and Simulation of Computer and Telecommunications Systems (MAS-
COTS 2001), pp. 346-356, August (2002).
[30] H. ying Tyan, Design, realization and evaluation of a component-based compo-
sitional software architecture for network simulation. PhD thesis, Ohio State
University, (2002).
[31] U. Brandes, "A faster algorithm for betweenness centrality," Journal of Mathe-
matical Sociology, vol. 25, no. 2, pp. 163-177, (2001).
[32] M. Barth elemy, "Betweenness centrality in large complex networks," The Euro-
pean Physical Journal, vol. 38, pp. 163-168, March (2004).
[33] L. Breslau, D. Estrin, K. Fall, S. Floyd, J. Heidemann, A. Helmy, P. Huang,
S. McCanne, K. Varadhan, Y. Xu, and H. Yu, "Advances in network simulation,"
IEEE Computer, vol. 33, pp. 59-67, May (2000).