| 摘要: | 在「無線隨意行動網路」(mobile ad hoc network, MANET) 中，行動主機的通訊完全不依賴基地台。基於無線電功率的限制、電源的消耗和頻道的使用率，有時候行動主機相互間的通訊需要經過中間的主機幫忙傳送。這種「無線隨意行動網路」可以運用在戰場或重大災難的現場上，因為這些地方都是無法佈置基地台。在本篇論文中，我們研究如何在無線行動隨建即連網路中進行有效率的繞徑和具有服務品質路徑。 目前已有許多相關於MANET的繞徑協定，然而他們是以圖論模型(graph model)來得知其與鄰居的連接關係。由於 MANET 是在真實的二度或三度空間中運作，所以本篇論文以幾何模型(geographic model)為基礎，發展出“GRID” 繞徑協定。我們將無線網路圖形區域分割成平面邏輯的方格，每個方格為正方形邊長為d x d，方格以傳統x y座標軸命名成(x , y)，每個節點仍具有唯一的IP位址，為了獲得位置資訊，每個行動節點都配備一個定位系統如GPS來讀取目前的位置，給定任一位址，都應位於事先訂定的格子座標區域。繞徑是以方格間的遞送為原則，每個格子中都必須有一個節點選為閘道，而閘道節點必須負責:(1)轉達路徑搜尋需求到鄰居格子、(2)轉達資料需求封包到鄰居格子、(3)維護經過這個格子的路徑，所有非閘道節點不需要負責這些工作直到成為情形(1)或(2)的目的端或情形(3)的來源端或接收端，為了維護路徑的品質，我們以選取越靠近方格中心位址的節點為閘道節點。另外我們以“GRID”為基礎，發展出「地理區域的廣播協定」(Geocast) 。我們試圖不去事先建立路徑，而是用 connectionless 來傳送資料。我們提出兩個方法，第一種是用“氾濫” (flooding-based)，每一個在傳送範圍的閘道節點將要繼續廣播。第二種是用“票” (ticket-based)，每一個擁有票的閘道節點將要繼續廣播。 本篇論文另一個主題是探討具有服務品質(QoS)的繞徑問題。現存的繞徑協定大多探討如何找出從來源端到目的端的uni-path。我們提出藉由on-demand協定找出從來源端到目的端具有服務品質的多重路徑(multi-path)。基本的想法是從來源端發出一些tickets，每一張ticket負責找出從來源端到目的端符合頻寬要求的路徑。當ticket遇到只走一條link無法滿足服務品質時，將被分割成數張sub-tickets，分送到不同的link，用來幫助找出滿足服務品質的多重路徑。由模擬的結果，我們可以證實多重路徑協定具有以下的優點：(1)當網路的頻寬比較小時，多重路徑(multi-path)比uni-path獲得較高的成功機率找到符合服務品質的路徑。(2)當網路的頻寬足夠時，多重路徑(multi-path)的效能與uni-path的方法是差不多的。另外我們也探討頻寬保留的問題，在現有的研究中，有些論文假設每個主機有多個天線，每個 link 上的頻寬與鄰居主機的傳送或接收是無關的。有些論文假設在 CDMA-over-TDMA 的模型下，每個 link 上的頻寬只與距離一步的鄰居主機有關。我們在此篇論文中，提出一個比較實際而且低成本的 TDMA 模型。我們提出一個新的方法去保留頻寬，而且可以解決 hidden-terminal 和 exposed-terminal 的問題，這個方法在尋找路徑的時候可以準確的計算出頻寬。 The advancement in wireless communication and economical, portable computing devices have made mobile computing possible. One research issue that has attracted a lot of attention recently is the design of mobile ad hoc network (MANET). A MANET is one consisting of a set of mobile hosts which can communicate with one another and roam around at their will. No base stations are supported in such an environment. Due to considerations such as radio power limitation, power consumption, and channel utilization, a mobile host may not be able to communicate directly with other hosts in a single-hop fashion. In this case, a multi-hop scenario occurs, where the packets sent by the source host are relayed by several intermediate hosts before reaching the destination host. Applications of MANETs occur in situations like battlefields or major disaster areas, where networks need to be deployed immediately but base stations or fixed network infrastructures are not available. Multi-hop poses several new challenges in the design of MANET. This dissertation mainly covers four areas: (1) GRID: a fully location-aware routing protocol; (2) GeoGRID: a geocasting protocol based on GRID; (3) A multi-path QoS routing protocol; (4) A TDMA-based bandwidth reservation protocol for QoS routing. First, we propose a routing protocol called“GRID”, which tries to exploit location Information in route discovery, packet relay, and route maintenance. Existing protocols, as compared to ours, are either not location-aware or partially location-aware in that location knowledge is not fully exploited in all these three aspects. One attractive feature of our protocol is its strong route maintenance capability — the intermediate hosts of a route can perform a “handoff” operation similar to that in cellular systems when it roams away to keep a route alive. This makes routes in the MANET more stable and insensitive to host mobility. Second, we propose a “GeoGRID”geocast protocol. The GeoGRID protocol, a modification of the GRID protocol, does not try to establish a spanning tree or routing path prior to geocasting. Instead, the protocol adopts a connectionless mode. GeoGRID uses two methods for distributing geocast messages. Flooding-based geocasting allows any grid leader in the forwarding zone to rebroadcast the messages. Ticket-based geocasting allows only ticket-holding grid leaders to rebroadcast. Issuing tickets avoids blind flooding. Third, we propose a multi-path QoS routing protocol that is an on-demand protocol for searching for a multi-path QoS route from a source host to a destination host in a MANET, where a multi-path is a network with a source and a sink satisfying certain bandwidth requirement. Existing works all try to find a uni-path to the destination. The basic idea is to distribute a number of tickets from the source, which can be further partitioned into subtickets to search for a satisfactory multi-path. Through simulations, we justify that the value of our multi-path protocol is on its flexibility: (i) when the network bandwidth is very limited, it can offer a higher success rate to find a satisfactory QoS route than those protocols which try to find a uni-path, and (ii) when the network bandwidth is suffcient, it can perform almost the same as those protocols which try to find a uni-path (in both routing overhead and success rate). Finally, we propose a TDMA-based bandwidth reservation protocol. This protocol considers the bandwidth reservation problem in a MANET to support QoS routing. We approach this problem by assuming a common channel shared by all hosts under a TDMA (Time Division Multiple Access) channel model. Existing solutions have addressed this problem by assuming a stronger multi-antenna model, where the bandwidth of a link is independent of the transmitting/receiving activities of its neighboring links, or a less stronger CDMA-over- TDMA channel model, where the use of a time slot on a link is only dependent of the status of its one-hop neighboring links. While more practical and less costly, using a TDMA model needs to face the challenge of radio interference problems. Our protocol can reserve routes by addressing both the hidden-terminal and exposed-terminal problems. The protocol can conduct accurate bandwidth calculation while performing route discovery. |
