1 |
在機會網路上實現行動代理人之搜尋機制 / Mobile agent tracking technology over opportunistic network林怡萱, Lin, Yi Shiuan Unknown Date (has links)
在機會網路上,傳遞資料遠比一般網路困難。運用行動代理人於機會網路上,
可大幅提升機會網路的功能,其中的行動代理人平台,需要一個代理人的搜尋
機制,方能實現對代理人的控制。本篇論文以「山文誌登山資訊系統」為背景,探討行動代理人在機會網路上的應用。在此登山客追蹤與環境監控系統中,每個登山客都攜帶一個配備有 GPS 功能的小型設備,此設備會在登山客的移動過程中,自動收集位置資訊,並使用短程無線電來和鄰近的登山客交換彼此的資訊。由於行動代理人是附屬於登山客所攜帶的設備上,而且當靠近其他登山客時,才可藉此轉移到另一個設備,故其行動力受制於登山客的移動行為。因登山客行走速率差異不大、所在位置分佈不均,使得行動代理人的轉移極為緩慢且需仰賴不確定的碰面機會,導致行動代理人之搜尋效率極低,無法支援緊急任務。為此,我們提出控制網路的方法,及一個簡單的搜尋演算法,讓搜尋代理人藉此高速網路來快速移動,以提高目標代理人的搜尋效率。在不同的考量及目標下,我們提出幾個控制網路的建置模型,並在證明其為 NP-complete問題後,提出有效的啟發式演算法來解決此控制點選擇問題。 / Transmitting data on an opportunistic network is much more difficult than that on a general network. The communication capability of an opportunistic network can be greatly enhanced via mobile agent functionality. A mobile agent platform demands a search mechanism to locate and control its agents. In this thesis, we investigate the adoption of mobile agent to opportunistic networks using "CenWits" system as reference model. In CenWits 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 mobile agents will be attached to the sensor nodes that hikers carry with, mobile agents can hop from one host to another only when two hosts (hikers) meet together such that their mobility is restrained by the moving behavior of hikers. 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 crippling agility of urgent agent functionality. Therefore, we propose to construct a control network using high speed network for search agents to travel in high speed. Under different objectives and constraints, we propose several control point placement models. After proving them to be NP-Complete, we propose few efficient heuristic algorithms to solve the placement problem. We also propose a simple search algorithm for search agents to search target agents quickly by using a control network.
|
2 |
在機會網路上使用機率預測法搜尋行動代理人 之機制 / Using probabilistic prediction method in the search of mobile agents over opportunistic network游筱慈, You, Hsiao Tzu Unknown Date (has links)
在機會網路上,訊息的遞送遠比一般網路來得困難許多,溝通交換資訊效率很低。本篇論文以山文誌資訊系統為背景,假設在山區中已佈建完成控制節點並組成控制網路,以及行動代理人機制已導入在控制網路上用來搜尋移動的目標節點。其中行動代理人附屬於登山客所攜帶的設備上,欲搜尋的目標節點會沿著登山路徑不斷移動造成搜尋上的困難,若搜尋失敗不只拉長延後了搜尋時間,也可能錯失黃金救難時間造成極大的損失,如何增進搜尋效率是機會網路上相當重要的議題。為此,本文提出一個搜尋方法,在任意的時間點計算目標行動節點落在每個控制節點之間路段的機率,預測目標代理人的位置,就可依機率高低逐次搜尋各路段,以提高搜尋效率。我們以山文誌登山資訊系統,作為參考的機會網路,提出兩個模型,使用機率預測搜尋法,預測行動節點可能所在位置優先搜尋此路段來降低整體搜尋時間,透過一連串的實驗驗證機率模型之準確度,並評估本法之搜尋效率以及當各路段花費時間的機率分佈假設有誤時,搜尋效率的受損程度。在我們的實驗中,機率模型之準確度極高,誤差不超過7.59%,搜尋效率都在44.44以上,即使機率分佈錯誤,搜尋效能仍高於二分搜尋法約2倍。 / Since transmitting data on an opportunistic network is more difficult than that on a general network, information exchanging is less efficient. Based on “CenWits” system, we assume that control point has entirely construed all over the mountains and a control network has completed altogether; meanwhile, the mobile agent mechanism has applied in the searching of mobile target nodes. With mobile agent attached on the equipment of hikers, the target agent moving constantly along the hiking path grows the difficulties in searching. The failure in locating the mobile agent possibly not only prolongs the searching time, but also misses the golden time of life saving, and causes enormously damages eventually. Therefore, figuring that “improving the efficiency of searching” is a major issue in opportunistic network, in this thesis we develop a searching method which enables us to calculate the probability where a mobile target agent locates in every edge between control points in any arbitrary time point. Through forecasting the location of the target agent, we can start searching from the edge with the highest probability, thus enhance the efficiency of searching. Using “CenWits” system as reference opportunistic network, we designed two probability models as well as associated search methods. We conducted a series of experiments to evaluate the accuracy of probabilistic models and the performance of the proposed search methods. In our experiments, the error of probability models is no more than 7.59%. Our proposed methods out perform Basic Binary Search by 44.44 in average. Furthermore, assuming that there is a discrepancy between the probability assumptions and the real distribution of the traveling time spent on each edge, we evaluate the performance degradation too. The experimental results show that under such circumstance, our Probabilistic Prediction Method can even outperform Basic Binary Search by approximately 200%.
|
Page generated in 0.0208 seconds