信息工程外文翻譯--一種對(duì)于移動(dòng)無(wú)線網(wǎng)絡(luò)高度自適應(yīng)的分布式路由算法（節(jié)選）

1、<p>　　2000單詞，10900英文字符，3712漢字</p><p>　　畢業(yè)設(shè)計(jì)（論文）外文文獻(xiàn)翻譯</p><p><b>　　英文原文</b></p><p>　　A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks[1]&

2、lt;/p><p>　　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

3、for mobile, multihop, 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 computat

4、ions; each computation 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 prot

5、ocol’</p><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

6、wireless receiver/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

7、 patterns, cochannel 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 algorithm

8、s [3-9] are not particularly 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 netw

9、ork is sufficiently 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>&l

10、t;p>　　Some existing 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-Sequenc

11、ed Distance Vector (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 d

12、rawbacks.</p><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

13、control packets and 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

14、 wireless network.</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

15、 routes through “false 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.&l

16、t;/p><p>　　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 updat

17、e interval, maximum 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

18、 parameters will have 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 multi

19、path routing. However, 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

20、 node which includes 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

21、amended to support 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 n

22、ode visited) and message 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 routin

23、g algorithm well-suited for operation in this environment should possess the following properties:? Executes distributedly? Provides loop-free routes? Provides multiple routes (to alleviate congestion)? Establishes r

24、outes quickly (so 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 sca

25、lability)</p><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

26、 times. The overhead 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>

27、;　　We have developed 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 the

28、ir undesirable characteristics 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-

29、reaching control message 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

30、 all routes are loop-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 destin

31、ation only when desired. 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

32、 Assumptions</p><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)

33、, and each link (i, 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

34、with time (i.e. new 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

35、is run for each destination 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

36、basic functions: creating 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 destinat

37、ion. This function 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 port

38、ion of the network.</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 ro

39、utes, UPD packets are used for both creating and maintaining routes, and CLR packets are used for erasing routes.</p><p>　　一種對(duì)于移動(dòng)無(wú)線網(wǎng)絡(luò)高度自適應(yīng)的分布式路由算法</p><p>　　摘要：我們提出了一種對(duì)于移動(dòng)，多跳，無(wú)線網(wǎng)絡(luò)的新的分布式路由協(xié)議。該協(xié)議屬于

40、我們所說(shuō)的“鏈接逆轉(zhuǎn)”算法族中的一個(gè)。協(xié)議反應(yīng)被構(gòu)造為在時(shí)間上排序的擴(kuò)散計(jì)算的序列；每個(gè)運(yùn)算包括有向連接反轉(zhuǎn)的序列。這種協(xié)議具有很強(qiáng)的適應(yīng)性，高效性和可擴(kuò)展性；從而很適合使用于大型，密集的移動(dòng)網(wǎng)絡(luò)環(huán)境。在這樣的網(wǎng)絡(luò)中，協(xié)議對(duì)于鏈路故障做出的反應(yīng)是通常只會(huì)涉及到局部的“單通過(guò)分布式算法”。這種獨(dú)特的能力在面對(duì)穩(wěn)定的網(wǎng)絡(luò)分區(qū)時(shí)，使得該協(xié)議具有很高的自適應(yīng)程度。這個(gè)所期望的行為是通過(guò)對(duì)“物理或邏輯時(shí)鐘”的新用途的取得以建立其用于結(jié)構(gòu)（或順序）

41、的算法的反應(yīng)拓?fù)渥兓瘡亩淖兪录摹皶r(shí)間順序”。我們將這種協(xié)議成為臨時(shí)預(yù)定路由算法（TORA）。</p><p><b>　　1.0介紹</b></p><p>　　我們認(rèn)為在移動(dòng)無(wú)線網(wǎng)絡(luò)中的路由問(wèn)題正如[1]中所描述的那樣，這樣的一個(gè)網(wǎng)絡(luò)可以設(shè)想為路由裝置（配有無(wú)線接收器/發(fā)射器）的集合，它可以自由移動(dòng)至約任意。路由器之間的通信鏈路的狀態(tài)，在任何特定時(shí)間，都是關(guān)于它

42、們的位置，發(fā)射功率電平，天線模式，同信道干擾的水平等等的一個(gè)函數(shù)。路由器的移動(dòng)性和其他連接因素的可變性導(dǎo)致具有一種潛在的快速和不可預(yù)知的改變拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)。擁堵的鏈接也期望特性的這樣一個(gè)網(wǎng)絡(luò)作為無(wú)線鏈路本身比硬鏈接顯著較低的能力，因此更容易發(fā)生擁堵。</p><p>　　現(xiàn)有的最短路徑算法和自適應(yīng)的最短路徑算法不是特別適合于運(yùn)行在這樣一個(gè)網(wǎng)絡(luò)環(huán)境下。這些算法被設(shè)計(jì)為在靜態(tài)或準(zhǔn)靜態(tài)網(wǎng)絡(luò)的硬連線鏈路時(shí)運(yùn)行，如果在網(wǎng)絡(luò)

43、中的拓?fù)渥兓首銐蚋邥r(shí)，這些算法可能不能反應(yīng)足夠快（即維護(hù)路由）導(dǎo)致溢出將是唯一的辦法。此外，大多數(shù)這些算法僅提供一個(gè)路徑每個(gè)給定的源/目標(biāo)之間的路由這更加劇了鏈路擁塞問(wèn)題。雖然鏈路狀態(tài)算法提供了多路徑路由的能力，但是在每個(gè)路由器的時(shí)間和通信開銷與維護(hù)的全拓?fù)湫畔?，使得他們依然不太適合這樣的環(huán)境。</p><p>　　現(xiàn)在已經(jīng)有下列一些針對(duì)這個(gè)環(huán)節(jié)的算法被開發(fā)出來(lái)了，比如：GafniBertsekas（GB）算法

44、、輕型移動(dòng)路由協(xié)議（LMR）、目標(biāo)測(cè)序距離矢量路由協(xié)議（DSDV）、無(wú)線路由協(xié)議（WRP）以及動(dòng)態(tài)源路由（DSR）協(xié)議 ，雖然這些算法相對(duì)傳統(tǒng)算法來(lái)說(shuō)更適合于這種環(huán)境，但是它們每一個(gè)都有各自的缺點(diǎn)。</p><p>　　GB算法在局部被分區(qū)的網(wǎng)絡(luò)區(qū)域表現(xiàn)得很不穩(wěn)定，在不穩(wěn)定的時(shí)期，節(jié)點(diǎn)效率將會(huì)非常低，并且同時(shí)傳輸控制報(bào)文和消息包，直至該網(wǎng)絡(luò)重新連接。這導(dǎo)致可用帶寬的利用效率很低，這將導(dǎo)致效率低下的使用帶寬是不可接

45、受的，因?yàn)榉謪^(qū)模式是有望在移動(dòng)無(wú)線網(wǎng)絡(luò)中常見(jiàn)。</p><p>　　LMR協(xié)議在被分區(qū)的網(wǎng)絡(luò)區(qū)域中也表現(xiàn)出一些不必要的常見(jiàn)行為。該協(xié)議可能導(dǎo)致臨時(shí)建設(shè)的無(wú)效路由通過(guò)“假的答復(fù)”傳播。雖然它表明，所有無(wú)效路由將在網(wǎng)絡(luò)的分配部分被刪除（以概率1），沒(méi)有有限的約束可以放置在所需要的時(shí)間。</p><p>　　DSDV協(xié)議是很受限制的，它只提供了單路徑路由之間的每一個(gè)給定的源/目的地址對(duì)。此外，該

46、協(xié)議還需要選擇以下參數(shù)：周期更新間隔，“設(shè)置時(shí)間”的最大值用來(lái)確定一些更新間隔可能發(fā)生在一個(gè)路由被認(rèn)為是“過(guò)時(shí)”。評(píng)估這些參數(shù)對(duì)性能上的影響是十分復(fù)雜困難的，但我們相信良好的參數(shù)選擇可能是至關(guān)重要的。這些參數(shù)可能代表一個(gè)有效的路由信息的延遲和過(guò)多的通信開銷之間的權(quán)衡。再進(jìn)一步復(fù)雜化考慮的問(wèn)題的話，良好的參數(shù)選擇很可能會(huì)取決于于網(wǎng)絡(luò)環(huán)境（即網(wǎng)絡(luò)的規(guī)模、拓?fù)渥兓实龋?lt;/p><p>　　雖然WRP協(xié)議被描述為只提

47、供單一路徑路由，節(jié)點(diǎn)保持足夠的信息來(lái)執(zhí)行多路徑路由。然而,有一個(gè)潛在的大量的開銷保持最短路徑生成樹的每個(gè)鄰居和對(duì)失敗的反應(yīng)可能會(huì)影響廣泛的（即每個(gè)節(jié)點(diǎn)，其中包括在其最短路徑生成樹故障鏈路必須參加的失敗反應(yīng)）。</p><p>　　DSR協(xié)議也被描述為僅提供單路徑路由；雖然,它可以被修改以支持多路徑路由。更重要的是,它遭受由于自然源路由的可伸縮性問(wèn)題。雖然,它可以被修改以支持多路徑路由。但更重要的是,它一直飽受自然

48、源路由的可伸縮性問(wèn)題苦惱。由于網(wǎng)絡(luò)變大，控制數(shù)據(jù)包（收集節(jié)點(diǎn)的地址，為每個(gè)節(jié)點(diǎn)訪問(wèn)）和消息數(shù)據(jù)包（包含完整的源路由信息）也變得更大。很明顯，這具有由于可用帶寬受限而產(chǎn)生負(fù)面影響。</p><p>　　在我們看來(lái)，非常適合在這種環(huán)境下操作的路由算法應(yīng)具備以下特性：</p><p><b>　　(1)分布執(zhí)行；</b></p><p>　　(2)提

49、供無(wú)環(huán)路的路由；</p><p>　　(3)提供多條路由路徑（用來(lái)緩解擁堵）；</p><p>　　(4)快速地建立路由（這樣它們就可以在拓?fù)涓那笆褂茫?lt;/p><p>　　(5)在拓?fù)洵h(huán)境發(fā)生可能發(fā)生變化時(shí)通過(guò)定位算法迅速反應(yīng)以最小化通信開銷（以節(jié)省可用帶寬和提高可擴(kuò)展性）；</p><p>　　(6)路由最優(yōu)（即判定所述最短路徑的）顯

50、得并不是最重要的，在任何時(shí)間的每一個(gè)源/目的地對(duì)之間的路線也并不是必要的（甚至是不可取的）。如果在源對(duì)目的有需要之前就建立路由，那么如果拓?fù)浣Y(jié)構(gòu)發(fā)生變化，這部分的通信開銷將會(huì)浪費(fèi)。</p><p>　　我們已經(jīng)專門開發(fā)出一種針對(duì)這種動(dòng)態(tài)性較高的網(wǎng)絡(luò)環(huán)境的路由算法，該算法基于或部分基于和中的成果；然而，它沒(méi)有繼承與網(wǎng)絡(luò)分區(qū)相關(guān)的不良特性。該協(xié)議的目的是最大限度地減少對(duì)拓?fù)渥兓姆磻?yīng)。它設(shè)計(jì)的一個(gè)關(guān)鍵概念是，它能夠從

51、拓?fù)涞淖兓手?，消除潛在的深遠(yuǎn)控制消息傳播的產(chǎn)生。這樣的信息通常定位于一個(gè)非常小的集合附近的變化的節(jié)點(diǎn)，而不必傳播到整個(gè)動(dòng)態(tài)網(wǎng)絡(luò)，以及伴隨而來(lái)的復(fù)雜的分層路由解決方案。一種可能增強(qiáng)的協(xié)議（將在后面討論）是將嵌入深遠(yuǎn)控制消息傳播到協(xié)議作為次要機(jī)制。這種傳播會(huì)周期性地出現(xiàn)在一個(gè)非常低的速度獨(dú)立于網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)，可以作為罕見(jiàn)的路由優(yōu)化和軟狀態(tài)路由驗(yàn)證手段。</p><p>　　這種算法是分布式的，只需要維護(hù)節(jié)點(diǎn)（即一跳

52、的信息）的節(jié)點(diǎn)上的信息。它保證所有路由都無(wú)環(huán)路，通常為任何源/目的地對(duì)需要路由的多條路由提供多條路由。像LMR，協(xié)議是“源”，當(dāng)需要到指定的目的地時(shí)快速創(chuàng)建一套路由。由于同時(shí)建立好了多個(gè)路由，許多拓?fù)浣Y(jié)構(gòu)的變化在單個(gè)路徑足夠使用時(shí)無(wú)需再做反應(yīng)。隨著拓?fù)渥兓^(guò)多，這確實(shí)需要反應(yīng)，但該協(xié)議很快就能重新建立有效的路由。這種減少啟動(dòng)和反應(yīng)的能力，使得通信開銷能夠大大降低。最后，在一個(gè)網(wǎng)絡(luò)分區(qū)時(shí)，分區(qū)的協(xié)議能夠在一個(gè)有限的時(shí)間內(nèi)檢測(cè)并刪除所有無(wú)效

53、的路徑。</p><p><b>　　2.0 協(xié)議</b></p><p>　　2.1 參數(shù)符號(hào)和假設(shè)</p><p>　　我們假設(shè)一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)G =（N，L），其中N是一個(gè)有限節(jié)點(diǎn)集合和L是一組最初無(wú)向鏈路。每個(gè)節(jié)點(diǎn)i∈N被假定為具有唯一的節(jié)點(diǎn)標(biāo)識(shí)符（ID），并且每個(gè)鏈路（I，J）∈L被假定以允許雙向通信（即，通過(guò)一個(gè)鏈路連接的節(jié)點(diǎn)可以彼此在

54、任一方向進(jìn)行通信）。由于節(jié)點(diǎn)的移動(dòng)性，該組的鏈路L會(huì)隨著時(shí)間改變。（即新的鏈接可以建立和現(xiàn)有的鏈接可被切斷）從鄰近節(jié)點(diǎn)的角度來(lái)看,一個(gè)節(jié)點(diǎn)故障相當(dāng)于切斷所有連接到該節(jié)點(diǎn)的鏈路。每個(gè)最初無(wú)向鏈路（I，J）∈L可以隨后被分配的三種狀態(tài)之一; （1）無(wú)向，（2）從節(jié)點(diǎn)引向i到節(jié)點(diǎn)j，或（3）從節(jié)點(diǎn)j指向節(jié)點(diǎn)i。如果一個(gè)鏈路（I，J）∈L從節(jié)點(diǎn)引向i到節(jié)點(diǎn)j，那么節(jié)點(diǎn)i對(duì)于j來(lái)說(shuō)就是“上游”，節(jié)點(diǎn)j對(duì)于節(jié)點(diǎn)i來(lái)說(shuō)就是“上游”，對(duì)于每個(gè)節(jié)點(diǎn)i，我

55、們定義節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)Ni ∈ N，成為集合的節(jié)點(diǎn)?使得（i，j）的∈L。對(duì)于隨后的討論中，我們假設(shè)一個(gè)鏈路級(jí)協(xié)議，該協(xié)議確保每個(gè)節(jié)點(diǎn)i是始終知道它自己在該組的鄰居集合Ni的存在；雖然這是邏輯的協(xié)議仍然是相同的，如果這是不是的情況下，即有可能是一個(gè)任意的延遲時(shí)間之間的鏈路狀態(tài)變化和隨后的協(xié)議通知的變化。我們還假設(shè)所有發(fā)送的數(shù)據(jù)包被正確地</p><p>　　2.2 基礎(chǔ)和基本結(jié)構(gòu)</p><p

56、>　　為了使運(yùn)行每個(gè)路由都能運(yùn)行到其目的地，一個(gè)邏輯上的獨(dú)立版本協(xié)議是必需的。對(duì)于下面的介紹中，我們將重點(diǎn)放在運(yùn)行給定目標(biāo)的單一版本。該協(xié)議可以被分為三個(gè)基本功能：路由創(chuàng)建，路由維護(hù)，路由刪除。創(chuàng)建從一個(gè)給定節(jié)點(diǎn)到目的地的路徑，需要建立定向鏈路從節(jié)點(diǎn)到目的地引導(dǎo)的一個(gè)序列，只有當(dāng)沒(méi)有能到達(dá)這個(gè)節(jié)點(diǎn)的有向鏈路時(shí)該功能才能啟動(dòng)。因此，創(chuàng)建路由基本上對(duì)應(yīng)于在無(wú)向網(wǎng)絡(luò)或網(wǎng)絡(luò)的一部分中方向的分配。用于完成這一點(diǎn)的方法是在中描述的查詢/回答過(guò)

57、程，它建立一個(gè)有向非循環(huán)圖（DAG）基于目的地的適應(yīng)（即目的地是與沒(méi)有下游鏈路的唯一節(jié)點(diǎn)），這樣的DAG被稱為“目的導(dǎo)向DAG”。維護(hù)路由指的是在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，在有限時(shí)間內(nèi)重新建立到達(dá)目的地的工作方式。這就意味著其中一部分在一個(gè)有限的時(shí)間內(nèi)回歸到一個(gè)目的地面向DAG。兩個(gè)GB算法，這是一般的類的設(shè)計(jì)來(lái)完成這一任務(wù)的算法的成員，呈現(xiàn)在[10]中。然而，GB算法是設(shè)計(jì)用來(lái)連接網(wǎng)絡(luò)的操作的。由于這些算法在分區(qū)網(wǎng)絡(luò)中表現(xiàn)出的不穩(wěn)定性，