| 摘要: | 在「無線行動隨建即連網路」(wireless mobile ad hoc network, MANET) 中，行動主機的通訊完全不依賴基地台。在此網路中，每個行動主機必須扮演繞徑器 (router) 的角色，與其他行動主機合作，以多段通訊 (multihop communication) 的方式來達成在行動主機間傳遞訊息的目的。在本篇論文中，我們研究如何在無線行動隨建即連網路中進行有效率的廣播及繞徑，並在Linux系統中實作和測試一個隨建即連繞徑協定。 在無線行動隨建即連網路中，由於沒有整個網路拓撲 (network topology) 的資訊，通常廣播都是以簡單的訊息氾濫法 (flooding) 來完成。根據本論文的分析及模擬，我們點出訊息氾濫的三大問題，也就是：「重複性」(redundancy) 、「競爭性」 (contention)、以及「衝撞」(collision) ；我們統稱之為「廣播風暴問題」 (broadcast storm problem) 。為了減緩廣播風暴問題，我們建議兩個方向：其一，減低無用重播 (redundant rebroadcast) 的機率；其二，將重播的時機錯開。根據這兩個方向，我們提出了五個重播法 (rebroadcast scheme) ，分別為：機率法 (probabilistic)、計數法 (counter-based)、距離法 (distance-based) 、位址法 (location-based) ，及群集法 (cluster-based) ，來進行無線行動隨建即連網路中的廣播。這些重播方法各自使用了不同的臨界值機制 (threshold mechanism) 來降低無用的重播。模擬結果的數據顯示，這些重播法皆遠比氾濫法有效率。此外我們也提出三個根據行動主機的鄰居狀態，來動態的調整臨界值的方式，在不犧牲可靠性 (reliability) 的前提下，更進一步的提升廣播的效率。 隨建即連網路中，如果不知道到某個行動主機的路徑，為了傳遞訊息給這個目的主機，一個行動主機必須發起路徑搜尋 (route discovery)。在現存的隨建即連繞徑協定 (ad hoc routing protocol) 中，路徑搜尋通常是以把一個繞徑要求 (route request) 氾濫到整個網路來達成，對無線網路有限的頻寬而言相當浪費。這些繞徑協定採取不同的策略來保存和修護路徑以降低這種浪費。在本篇論文中，我們探討「路徑維護」(route maintenance) 中「路徑退化」問題與「路徑斷裂」問題。我們提出了通用的「路徑最佳化」 (route optimization) 以及「當地路徑修復」 (local route recovery) 兩個方法來改善幾個現存繞徑協定的效率。我們舉出如何以此二法加強DSR、SSA、AODV及ZRP這幾個繞徑協定。模擬的結果顯示，同時使用此二法，控制封包的花費 (control packet overhead) 降低了，整體資料頻寬也改善了。 在無線行動隨建即連網路中，有可能在要送訊息給某個主機時，不知道到此主機的路徑，或先前的路徑已經過期。為了支援在隨建即連網路中的網路運作，一個作業系統 (operating system) 必須能夠處理這種情況，不讓網路應用程式意識到ㄧ個路徑暫時不存在。在我們的實作中，我們加強了Linux作業系統核心 (kernel) 中的TCP/IP層，以支援封包暫存 (packet buffering) 、錯誤掩飾 (error hiding)、以與一個支援類似DSR繞徑協定的繞徑精靈 (routing daemon) 合作。我們達到讓現存的網路應用程式不經修改，而能正常在隨建即連網路中執行的目標。利用此平台，我們也測試了路徑搜尋延遲 (route discovery delay) 與資料傳輸容量 (data throughput) ，並評估以氾濫方式傳播繞徑要求時封包衝撞的情形。 Conventional wireless network relies on base stations or access points relaying messages between mobile units and to/from wired infrastructure. The mobile ad hoc network (MANET) distinguishes itself from the conventional wireless network by eliminating the dependence on base stations for relaying messages. In a MANET, a mobile host has to play the role of a router and cooperate with others to exploits the multihop communication ability for delivering messages among mobile hosts. Due to the mobility and the unreliable nature of wireless transmission, supporting even the most primitive broadcast and unicast operations represents a great challenge in the mobile ad hoc network. In this dissertation, we address the issues of broadcast storm problem, route maintenance problem, and implementing an ad hoc routing protocol in a MANET. The broadcast operation is very useful for route discovery, naming, addressing, and helping multicast operations in all kinds of networks. In a MANET, without the knowledge of the network topology, a broadcast is often accomplished by straightforward flooding. Through analyses and simulations, three major problems associated with flooding are identified, that is, redundancy, contention, and collision. Collectively we refer to these problems as the broadcast storm problem. Two directions are suggested to alleviate the problem, that is, to reduce the possibility of redundant rebroadcasts, and to differentiate the timing of rebroadcasts. Following these directions, we develop five rebroadcast schemes, called probabilistic, counter-based, distance-based, location-based, and cluster-based schemes, to facilitate MANET broadcasting. In these schemes, various threshold mechanisms are used to intelligently reduce the number of redundant rebroadcasts. Simulation results show great improvement of efficiency as compared with the flooding scheme. In addition, adaptive schemes are developed, which dynamically adjust thresholds according to hosts' neighborhood states, to achieve better efficiency without sacrificing reliability. To deliver a message, a mobile host in a MANET must initiate a route discovery procedure if the route to the destination does not exist or is broken. In existing routing protocols, the route discovery is often achieved by flooding route request packets throughout the network, which often incurs high overhead. Different strategies are used in these protocols to preserve and fix a route when a link breakage occurs for reducing the re-route overhead. We address two issues, route deterioration and route breakage, of the route maintenance problem. Generic route optimization and local route recovery schemes are proposed to improvement the performance of existing routing protocols. Specifically, we show how to apply the schemes to DSR, SSA, AODV, and ZRP routing protocols. Simulation results show that the control packet overhead is reduced, and the data packet bandwidth is improved. Since a route to some destination may be unavailable or broken at the time when the route is needed, an operation system that supports networking in a MANET environment must be capable of dealing with such conditions and hiding temporary network jitters from applications. In our implementation work, the original TCP/IP layer of Linux operation system is enhanced to support packet buffering, error hiding, and to cooperate with a routing daemon implementing a DSR-like routing protocol. We achieve the goal to allow existing network applications to run smoothly in a MANET without modifying the applications. With our implementation, we perform tests on multi-hop routing to measure the route discovery delay and data throughput, and to evaluate the collision caused by the flooding of route request packets. |
