行動隨意網路拓樸資訊收集之分析

Abstract

拓樸資訊經常被使用在網路常見的功能如廣播、繞徑等。單一跳躍鄰居列表資訊是拓樸資訊的基本單元，用以得知更多的拓樸資訊。此種資訊可由在整個網路上的所有節點交換一次招呼封包取得。然而，行動隨意網路可移動的特性使得單一跳躍鄰居列表隨著時間不同而頻繁地改變，並且使得鄰居列表資訊產生錯誤。在本論文中，我們將推導節點在一段時間內，離開原來的傳輸範圍的機率，以分析移動的程度將對此資訊錯誤率的關係，並驗證此錯誤率對網路效能產生的影響以決定招呼封包的傳送週期，藉由此機率模型，推導鏈結變化率，以得知適當的傳送週期。為了取得正確的單一跳躍鄰居列表，招呼封包必須週期性的發送。然而，資訊的精確度與傳送週期的關係是密不可分的，這意味著高精確度往往會伴隨著大量的招呼封包產生，其結果將導致可觀的成本。許多的研究假設單一跳躍鄰居列表是已知的，因此這項成本就可以被忽略。當實作在真實世界時，這是不合理的，我們將透過模擬來說明此問題。最後利用ns2來比較分析結果與模擬測試是否符合。

Topology information is frequently used in many network functions such as broadcast, route discovery, etc. One-hop neighbor lists are the basic of topology information and used for complicated topology information. The lists can be obtained by all nodes of the network exchanging hello packets exactly once. However, the mobility feature of the wireless Mobile Ad Hoc Networks (MANETs) causes the list different frequently. It also causes the error of the 1-hop neighbor lists. In this paper, we analyze the relationship between the degree of mobility and neighbor information error rate by deriving the probability that a node leaves its original transmission range. We also verify the influence of neighbor information error rate on network performance so as to determine the transmission period of hello packets. According to the probability model, we can deduce the link change rate. The proper hello period can also be obtained by the value of link change rate. In order to obtain accurate 1-hop neighbor information, the hello packets must be sent periodically. However, the accuracy is highly related with the hello transmission period. It means that a large number of hello packets are needed to maintain high accuracy, and consequently a considerable overhead follows. Many researches make an assumption that 1-hop neighbor lists are already known, thereby neglecting the overheads stem from hello messages. It is not reasonable when it comes to real world implementation. We demonstrate the problem through a series of simulations. Hello packet period is also in connection with mobility model. The mobility model dominates the variation speed of topology information. Therefore, the accuracy of topology information is also affected. In this paper, we analyze the relationship between hello packet period, mobility model and the accuracy of topology information. We also derive the probability that a node leaves its original transmission in certain time. The probability can be used to determine proper hello packet period. Last, the ns2 simulator was adopted to compare the results of the analysis and simulation.