在機會網路上實現行動代理人之搜尋機制

Mobile Agent Tracking Technology over Opportunistic Network



林怡萱

在機會網路上,傳遞資料遠比一般網路困難。運用行動代理人於機會網路上,可大幅提升機會網路的功能,而其中的行動代理人平台,則需要一個代理人的搜尋機制,方能實現代理人之控制,例如︰暫停、恢復、終止代理人的行為。本篇論文以「山文誌登山資訊系統」為背景,探討行動代理人在機會網路上的應用。在此系統中,每個登山客都攜帶一個配備有GPS功能的小型設備,此設備會在登山客的移動過程中,自動收集位置資訊,並使用短程無線連線來和鄰近的登山客交換彼此的移動資訊。由於行動代理人是附屬於登山客所攜帶的設備上,又當兩個設備(登山客)互相接近時,行動代理人才可以從其中一個設備轉移到另一個設備,故其行動力受制於登山客的移動行為。因登山客行走速率差異不大、所在位置分佈不均,使得行動代理人的轉移極為緩慢且需仰賴不確定的碰面機會,導致行動代理人之搜尋效率極低,無法支援緊急任務,例如︰通知一個團隊成員惡劣天氣的變化。為此,我們提出建置控制點網路的方法,讓行動代理人能透過此高速網路來快速移動,以提高行動代理人的搜尋效率。在不同的考量及目標下,我們提出幾個控制點網路的建置模型。在證明其為NP-complete問題後,我們提出一個有效率的啟發式演算法,來解決此控制點網路的建置問題。我們也提供一個簡單的搜尋演算法,讓搜尋代理人能利用控制點網路,來快速搜尋到目標代理人。

Transmitting data on an opportunistic network is much more difficult than that on a general network. The capability of an opportunistic network can be greatly enhanced if it is equipped with mobile agent functionality. A mobile agent platform that can support the execution of mobile agents requires a search mechanism for the platform to control its agents, such as suspension, resuming, and termination of agents. In this thesis, we investigate the application of mobile agent on an opportunistic network based on "CenWits System". In this system, each hiker carries a GPS enabled sensor node to collect and exchange movement statistics with its fellow hikers using a short range wireless links. Since the mobile agents are attached to the sensor nodes that hikers carry with, their mobility is constrained by the moving behavior of hikers since mobile agents can hop from one host to another only when two hosts (hikers) meet together. The little difference in walking speed and the uneven distribution of hikers make the hopping of mobile agents extremely slow and opportunistic. As a consequence, the search of mobile agents is slow and inefficient such that it is not acceptable for urgent agent functionality such as informing a team member of severe weather change. Therefore, we propose to construct a control point network using high speed network for search agents to travel in high speed. Under different objectives and constraints, we propose several placement models for control point network construction. After proving them to be NP-Complete, we propose an efficient heuristic algorithm to solve the placement problem. We also propose a simple search algorithm for search agent to search target agents quickly by using a control point network.