一種對于移動無線網(wǎng)絡高度自適應的分布式路由算法外文翻譯1218

1、<p>　　一種對于移動無線網(wǎng)絡高度自適應的分布式路由算法</p><p>　　摘要：我們提出了一種對于移動，多跳，無線網(wǎng)絡的新的分布式路由協(xié)議。該協(xié)議屬于我們所說的“鏈接逆轉”算法族中的一個。協(xié)議反應被構造為在時間上排序的擴散計算的序列；每個運算包括有向連接反轉的序列。這種協(xié)議具有很強的適應性，高效性和可擴展性；從而很適合使用于大型，密集的移動網(wǎng)絡環(huán)境。在這樣的網(wǎng)絡中，協(xié)議對于鏈路故障做出的反應是通常

2、只會涉及到局部的“單通過分布式算法”。這種獨特的能力在面對穩(wěn)定的網(wǎng)絡分區(qū)時，使得該協(xié)議具有很高的自適應程度。這個所期望的行為是通過對“物理或邏輯時鐘”的新用途的取得以建立其用于結構（或順序）的算法的反應拓撲變化從而改變事件的“時間順序”。我們將這種協(xié)議成為臨時預定路由算法（TORA）。</p><p><b>　　1.0介紹</b></p><p>　　我們認為在移動

3、無線網(wǎng)絡中的路由問題正如[1]中所描述的那樣，這樣的一個網(wǎng)絡可以設想為路由裝置（配有無線接收器/發(fā)射器）的集合，它可以自由移動至約任意。路由器之間的通信鏈路的狀態(tài)，在任何特定時間，都是關于它們的位置，發(fā)射功率電平，天線模式，同信道干擾的水平等等的一個函數(shù)。路由器的移動性和其他連接因素的可變性導致具有一種潛在的快速和不可預知的改變拓撲結構的網(wǎng)絡。擁堵的鏈接也期望特性的這樣一個網(wǎng)絡作為無線鏈路本身比硬鏈接顯著較低的能力，因此更容易發(fā)生擁堵。

4、</p><p>　　現(xiàn)有的最短路徑算法和自適應的最短路徑算法不是特別適合于運行在這樣一個網(wǎng)絡環(huán)境下。這些算法被設計為在靜態(tài)或準靜態(tài)網(wǎng)絡的硬連線鏈路時運行，如果在網(wǎng)絡中的拓撲變化率足夠高時，這些算法可能不能反應足夠快（即維護路由）導致溢出將是唯一的辦法。此外，大多數(shù)這些算法僅提供一個路徑每個給定的源/目標之間的路由這更加劇了鏈路擁塞問題。雖然鏈路狀態(tài)算法提供了多路徑路由的能力，但是在每個路由器的時間和通信開銷與維

5、護的全拓撲信息，使得他們依然不太適合這樣的環(huán)境。</p><p>　　現(xiàn)在已經(jīng)有下列一些針對這個環(huán)節(jié)的算法被開發(fā)出來了，比如：GafniBertsekas（GB）算法、輕型移動路由協(xié)議（LMR）、目標測序距離矢量路由協(xié)議（DSDV）、無線路由協(xié)議（WRP）以及動態(tài)源路由（DSR）協(xié)議 ，雖然這些算法相對傳統(tǒng)算法來說更適合于這種環(huán)境，但是它們每一個都有各自的缺點。</p><p>　　GB算

6、法在局部被分區(qū)的網(wǎng)絡區(qū)域表現(xiàn)得很不穩(wěn)定，在不穩(wěn)定的時期，節(jié)點效率將會非常低，并且同時傳輸控制報文和消息包，直至該網(wǎng)絡重新連接。這導致可用帶寬的利用效率很低，這將導致效率低下的使用帶寬是不可接受的，因為分區(qū)模式是有望在移動無線網(wǎng)絡中常見。</p><p>　　LMR協(xié)議在被分區(qū)的網(wǎng)絡區(qū)域中也表現(xiàn)出一些不必要的常見行為。該協(xié)議可能導致臨時建設的無效路由通過“假的答復”傳播。雖然它表明，所有無效路由將在網(wǎng)絡的分配部分被

7、刪除（以概率1），沒有有限的約束可以放置在所需要的時間。</p><p>　　DSDV協(xié)議是很受限制的，它只提供了單路徑路由之間的每一個給定的源/目的地址對。此外，該協(xié)議還需要選擇以下參數(shù)：周期更新間隔，“設置時間”的最大值用來確定一些更新間隔可能發(fā)生在一個路由被認為是“過時”。評估這些參數(shù)對性能上的影響是十分復雜困難的，但我們相信良好的參數(shù)選擇可能是至關重要的。這些參數(shù)可能代表一個有效的路由信息的延遲和過多的通

8、信開銷之間的權衡。再進一步復雜化考慮的問題的話，良好的參數(shù)選擇很可能會取決于于網(wǎng)絡環(huán)境（即網(wǎng)絡的規(guī)模、拓撲變化率等）。</p><p>　　雖然WRP協(xié)議被描述為只提供單一路徑路由，節(jié)點保持足夠的信息來執(zhí)行多路徑路由。然而,有一個潛在的大量的開銷保持最短路徑生成樹的每個鄰居和對失敗的反應可能會影響廣泛的（即每個節(jié)點，其中包括在其最短路徑生成樹故障鏈路必須參加的失敗反應）。</p><p>

9、　　DSR協(xié)議也被描述為僅提供單路徑路由；雖然,它可以被修改以支持多路徑路由。更重要的是,它遭受由于自然源路由的可伸縮性問題。雖然,它可以被修改以支持多路徑路由。但更重要的是,它一直飽受自然源路由的可伸縮性問題苦惱。由于網(wǎng)絡變大，控制數(shù)據(jù)包（收集節(jié)點的地址，為每個節(jié)點訪問）和消息數(shù)據(jù)包（包含完整的源路由信息）也變得更大。很明顯，這具有由于可用帶寬受限而產(chǎn)生負面影響。</p><p>　　在我們看來，非常適合在這種

10、環(huán)境下操作的路由算法應具備以下特性：</p><p><b>　　(1)分布執(zhí)行；</b></p><p>　　(2)提供無環(huán)路的路由；</p><p>　　(3)提供多條路由路徑（用來緩解擁堵）；</p><p>　　(4)快速地建立路由（這樣它們就可以在拓撲更改前使用）；</p><p>　　

11、(5)在拓撲環(huán)境發(fā)生可能發(fā)生變化時通過定位算法迅速反應以最小化通信開銷（以節(jié)省可用帶寬和提高可擴展性）；</p><p>　　(6)路由最優(yōu)（即判定所述最短路徑的）顯得并不是最重要的，在任何時間的每一個源/目的地對之間的路線也并不是必要的（甚至是不可取的）。如果在源對目的有需要之前就建立路由，那么如果拓撲結構發(fā)生變化，這部分的通信開銷將會浪費。</p><p>　　我們已經(jīng)專門開發(fā)出一種針

12、對這種動態(tài)性較高的網(wǎng)絡環(huán)境的路由算法，該算法基于或部分基于和中的成果；然而，它沒有繼承與網(wǎng)絡分區(qū)相關的不良特性。該協(xié)議的目的是最大限度地減少對拓撲變化的反應。它設計的一個關鍵概念是，它能夠從拓撲的變化率中，消除潛在的深遠控制消息傳播的產(chǎn)生。這樣的信息通常定位于一個非常小的集合附近的變化的節(jié)點，而不必傳播到整個動態(tài)網(wǎng)絡，以及伴隨而來的復雜的分層路由解決方案。一種可能增強的協(xié)議（將在后面討論）是將嵌入深遠控制消息傳播到協(xié)議作為次要機制。這種

13、傳播會周期性地出現(xiàn)在一個非常低的速度獨立于網(wǎng)絡拓撲的動態(tài)，可以作為罕見的路由優(yōu)化和軟狀態(tài)路由驗證手段。</p><p>　　這種算法是分布式的，只需要維護節(jié)點（即一跳的信息）的節(jié)點上的信息。它保證所有路由都無環(huán)路，通常為任何源/目的地對需要路由的多條路由提供多條路由。像LMR，協(xié)議是“源”，當需要到指定的目的地時快速創(chuàng)建一套路由。由于同時建立好了多個路由，許多拓撲結構的變化在單個路徑足夠使用時無需再做反應。隨著拓

14、撲變化過多，這確實需要反應，但該協(xié)議很快就能重新建立有效的路由。這種減少啟動和反應的能力，使得通信開銷能夠大大降低。最后，在一個網(wǎng)絡分區(qū)時，分區(qū)的協(xié)議能夠在一個有限的時間內(nèi)檢測并刪除所有無效的路徑。</p><p><b>　　2.0 協(xié)議</b></p><p>　　2.1 參數(shù)符號和假設</p><p>　　我們假設一個網(wǎng)絡結構G =（N，

15、L），其中N是一個有限節(jié)點集合和L是一組最初無向鏈路。每個節(jié)點i∈N被假定為具有唯一的節(jié)點標識符（ID），并且每個鏈路（I，J）∈L被假定以允許雙向通信（即，通過一個鏈路連接的節(jié)點可以彼此在任一方向進行通信）。由于節(jié)點的移動性，該組的鏈路L會隨著時間改變。（即新的鏈接可以建立和現(xiàn)有的鏈接可被切斷）從鄰近節(jié)點的角度來看,一個節(jié)點故障相當于切斷所有連接到該節(jié)點的鏈路。每個最初無向鏈路（I，J）∈L可以隨后被分配的三種狀態(tài)之一; （1）無向，

16、（2）從節(jié)點引向i到節(jié)點j，或（3）從節(jié)點j指向節(jié)點i。如果一個鏈路（I，J）∈L從節(jié)點引向i到節(jié)點j，那么節(jié)點i對于j來說就是“上游”，節(jié)點j對于節(jié)點i來說就是“上游”，對于每個節(jié)點i，我們定義節(jié)點i的鄰居節(jié)點Ni ∈ N，成為集合的節(jié)點?使得（i，j）的∈L。對于隨后的討論中，我們假設一個鏈路級協(xié)議，該協(xié)議確保每個節(jié)點i是始終知道它自己在該組的鄰居集合Ni的存在；雖然這是邏輯的協(xié)議仍然是相同的，如果這是不是的情況下，即有可能是一個任

17、意的延遲時間之間的鏈路狀態(tài)變化和隨后的協(xié)議通知的變化。我們還假設所有發(fā)送的數(shù)據(jù)包被正確地</p><p>　　2.2 基礎和基本結構</p><p>　　為了使運行每個路由都能運行到其目的地，一個邏輯上的獨立版本協(xié)議是必需的。對于下面的介紹中，我們將重點放在運行給定目標的單一版本。該協(xié)議可以被分為三個基本功能：路由創(chuàng)建，路由維護，路由刪除。創(chuàng)建從一個給定節(jié)點到目的地的路徑，需要建立定向鏈路

18、從節(jié)點到目的地引導的一個序列，只有當沒有能到達這個節(jié)點的有向鏈路時該功能才能啟動。因此，創(chuàng)建路由基本上對應于在無向網(wǎng)絡或網(wǎng)絡的一部分中方向的分配。用于完成這一點的方法是在中描述的查詢/回答過程，它建立一個有向非循環(huán)圖（DAG）基于目的地的適應（即目的地是與沒有下游鏈路的唯一節(jié)點），這樣的DAG被稱為“目的導向DAG”。維護路由指的是在網(wǎng)絡拓撲結構發(fā)生變化時，在有限時間內(nèi)重新建立到達目的地的工作方式。這就意味著其中一部分在一個有限的時間內(nèi)

19、回歸到一個目的地面向DAG。兩個GB算法，這是一般的類的設計來完成這一任務的算法的成員，呈現(xiàn)在[10]中。然而，GB算法是設計用來連接網(wǎng)絡的操作的。由于這些算法在分區(qū)網(wǎng)絡中表現(xiàn)出的不穩(wěn)定性，使得它們被認為對于實時任務來說是不可取的。我們已經(jīng)設計了一個新的算法，在類似算法中，這是更有效的反應拓撲變化，并能夠檢測網(wǎng)絡分區(qū)。這</p><p>　　該協(xié)議通過使用三個不同的控制數(shù)據(jù)包來實現(xiàn)這三個功能：（QRY），更新（U

20、PD），并清除（CLR）。QRY分組用于創(chuàng)建路徑，UPD數(shù)據(jù)包用于創(chuàng)建和維護路由，和CLR包用于清除路由。</p><p><b>　　英文原文</b></p><p>　　A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks[1]</p><p&g

21、t;　　Vincent D. Parka and M. Scott Corsonb</p><p>　　aNaval Research Laboratory, USAbUniversity of Maryland, USA</p><p>　　Abstract：We present a new distributed routing protocol for mobile, multih

22、op, wireless networks. The protocol is one of a family of protocols which we term “l(fā)ink reversal” algorithms. The protocol’s reaction is structured as a temporally-ordered sequence of diffusing computations; each computa

23、tion consisting of a sequence of directed link reversals. The protocol is highly adaptive, efficient and scalable; being best-suited for use in large, dense, mobile networks. In these networks, the protocol’</p>&

24、lt;p>　　Introduction</p><p>　　We consider the problem of routing in a mobile wireless network as described in . Such a network can be envisioned as a collection of routers (equipped with wireless receiver/

25、transmitters) which are free to move about arbitrarily. The status of the communication links between the routers, at any given time, is a function of their positions, transmission power levels, antenna patterns, cochann

26、el interference levels, etc. The mobility of the routers and the variability of other connectivity factor</p><p>　　Existing shortest-path algorithms [2] and adaptive shortest-path algorithms [3-9] are not pa

27、rticularly well suited for operation in such a network. These algorithms are designed for operation in static or quasi-static networks with hardwired links. If the rate of topological change in the network is sufficientl

28、y high, these algorithms may not be able to react fast enough (i.e. to maintain routing) and flooding will be the only recourse. Furthermore, most of these algorithms provide only one path</p><p>　　Some exis

29、ting algorithms which have been developed for this environment include the following: the GafniBertsekas (GB) algorithms [10], the Lightweight Mobile Routing (LMR) protocol [11], the Destination-Sequenced Distance Vector

30、 (DSDV) routing protocol [12], the Wireless Routing Protocol (WRP) [13], and the Dynamic Source Routing (DSR) protocol [14]. While these algorithms are better suited for this environment, each has its drawbacks.</p>

31、;<p>　　The GB algorithms exhibit instability in portions of the network which become partitioned from the destination. During the period of instability, nodes will non-productively transmit both control packets an

32、d message packets until such time that the network is reconnected. This results in inefficient use of the available bandwidth and is unacceptable, since partitioning is expected to be common in a mobile wireless network.

33、</p><p>　　The LMR protocol also exhibits some unwanted behavior which is most prevalent in partitioned portions of the networks. The protocol can result in temporary construction of invalid routes through “f

34、alse reply” propagation. While it as shown that all invalid routes would be erased in a partitioned portion of the network (with probability one), no finite bound could be placed on the time required.</p><p>

35、;　　DSDV is limited in that it provides only a single path for routing between each given source/destination pair. Furthermore, the protocol requires selection of the following parameters: periodic update interval, maximu

36、m value of the “settling time” for a destination and the number of update intervals which may transpire before a route is considered “stale”. It is difficult to assess the impact that selection of these parameters will h

37、ave on performance, but we believe good parameter selection may</p><p>　　While WRP is described as providing only single path routing, nodes maintain sufficient information to perform multipath routing. Howe

38、ver, there is potentially a significant amount of overhead associated with maintaining the shortest-path spanning tree reported by each neighbor and reactions to failures may be far-reaching (i.e. every node which includ

39、es the failed link in its shortest-path spanning tree must participate in the failure reaction).</p><p>　　DSR is also described as providing only single path routing; although, it could be amended to support

40、 multipath routing. More significantly, it suffers from a scalability problem due to the nature of source routing. As the network becomes larger, control packets (which collect node addresses for each node visited) and m

41、essage packets (which contain full source routing information) also become larger. Clearly, this has a negative impact due to the limited available bandwidth.</p><p>　　In our view, a routing algorithm well-s

42、uited for operation in this environment should possess the following properties:? Executes distributedly? Provides loop-free routes? Provides multiple routes (to alleviate congestion)? Establishes routes quickly (so

43、they may be usedbefore the topology changes)? Minimizes communication overhead by localizing algorithmic reaction to topological changes when possible (to conserve available bandwidth and increase scalability)</p>

44、;<p>　　Routing optimality (i.e. determination of the shortest-path) is of less importance. It is also not necessary (nor desirable) to maintain routes between every source/destination pair at all times. The overhe

45、ad expended to establish a route between a given source/destination pair will be wasted if the source does not require the route prior to its invalidation due to topological changes.</p><p>　　We have develop

46、ed a routing algorithm which is tailored for operation in this highly dynamic network environment. The algorithm is based, in part, on the work presented in [10] and [11]; however, it does not share their undesirable cha

47、racteristics associated with network partitions. The protocol is designed to minimize reaction to topological changes. A key concept in its design is that it decouples the generation of potentially far-reaching control m

48、essage propagation from the rate of topologic</p><p>　　The algorithm is distributed in that nodes need only maintain information about adjacent nodes (i.e. one hopknowledge). It guarantees all routes are lo

49、op-free, and typically provides multiple routes for any source/destination pair which requires a route. Like LMR, the protocol is “source initiated” and quickly creates a set of routes to a given destination only when de

50、sired. Since multiple routes are typically established, many topological changes require no reaction at all as having a single r</p><p>　　The Protocol</p><p>　　2.1 Notation and Assumptions</p

51、><p>　　We model a network as a graph G = (N, L), where N is a finite set of nodes and L is a set of initially undirected links. Each node i ∈ N is assumed to have a unique node identifier (ID), and each link (i

52、, j) ∈ L is assumed to allow two-way communication (i.e. nodes connected by a link can communicate with each other in either direction). Due to the mobility of the nodes, the set of links L is changing with time (i.e. ne

53、w links can be established and existing links can be severed). From the persp</p><p>　　2.2 Foundation and Basic Structure</p><p>　　A logically separate version of the protocol is run for each de

54、stination to which routing is required. For the following presentation, we will focus on a single version running for a given destination.</p><p>　　The protocol can be separated into three basic functions: c

55、reating routes, maintaining routes, and erasing routes. Creating a route from a given node to the destination requires establishment of a sequence of directed links leading from the node to the destination. This function

56、 is only initiated when a node with no directed links requires a route to the destination. Thus, creating routes essentially corresponds to assigning directions to links in an undirected network or portion of the network

57、.</p><p>　　The protocol accomplishes these three functions through the use of three distinct control packets: query(QRY), update (UPD), and clear (CLR). QRY packets are used for creating routes, UPD packets