1 動態(tài)源路由
　　路由算法是移動自組網(wǎng)絡研究的關(guān)鍵技術(shù)之一,。在移動自組網(wǎng)絡中，任何2個非鄰節(jié)點傳遞數(shù)據(jù),，必須經(jīng)過其他中間節(jié)點中繼,，而中間節(jié)點的可移動性時常導致路由失效。因此,，路由協(xié)議直接影響網(wǎng)絡運行,。路由維護是路由的一個組成部分。傳統(tǒng)網(wǎng)絡的路由維護需要周期發(fā)送路由信息,、分析路況和更新路由,。這種路由表維護機制不適合有限的帶寬、能源及處理能力的移動自組網(wǎng)絡,。研究者們提出了許多針對移動自組網(wǎng)絡的路由協(xié)議,。其中，比較公認的是DSDV,、AODV,、ZRP和DSR等路由協(xié)議。按需路由算法已經(jīng)成為當前路由算法的一個基礎(chǔ),，其目的是減少路由建立過程中不必要的控制包數(shù)量,。動態(tài)源路由^[1]DSR(Dynamic Source Route)是典型的按需路由協(xié)議，它不需要全程(從網(wǎng)絡建立到網(wǎng)絡解體)維護路由,，只有當某節(jié)點有數(shù)據(jù)需要傳送時,，才進行路由發(fā)現(xiàn)、路由維護和路由釋放三個過程,。該協(xié)議的路由發(fā)現(xiàn)過程被證明是有效的^[2],，也因此使DSR協(xié)議成為IETF的研究重點之一。然而，該協(xié)議的路由維護過程卻會消耗許多控制帶寬和能源,。首先,，當原路由失效時，DSR將失效信息反饋給源節(jié)點,，再由源節(jié)點重新發(fā)現(xiàn)路由,，這個過程將消耗許多網(wǎng)絡資源；其次,，已被激活的數(shù)據(jù)因路由斷開而必須重傳,，無疑又浪費前次使用過的資源。為此,，DSR算法又提出優(yōu)化措施,，即首先在斷點處查找是否有到達目標的路由，若有,，則選擇這條路由,；否則，將斷開消息反饋給源節(jié)點,，并重新發(fā)現(xiàn)路由,。但是，該方法需要看網(wǎng)絡建立的時間長短,。若網(wǎng)絡建立時間較長,，網(wǎng)絡上曾經(jīng)有過多次信息交換，則節(jié)點存儲路由的可能性大,；反之,，這種可能性較小，就必須回到源節(jié)點重新發(fā)現(xiàn)路由,，浪費有限資源,。
2 相關(guān)工作
　　為解決資源浪費問題，許多新算法被提出,。多路徑路由算法是其中之一,。算法RBMR^[3]提出一種冗余路由算法,，根據(jù)節(jié)點冗余度選擇路由,。算法NDMR^[4]建立多條沒有交叉節(jié)點的路由擔任備份路由，以避免路由斷開時對其他備用路由的影響,。其不足在于源節(jié)點擁有全部路由信息,，斷點必須反饋一個RERR(Route Error)包給源節(jié)點，由源節(jié)點再選擇一條新路由重新發(fā)送數(shù)據(jù),。由于被激活的數(shù)據(jù)流已發(fā)送到中途,，再進行第二次重傳，會造成能量和帶寬的浪費。因此,，本文提出路由快速切換算法QSRA(Quickly Switching Routing Algorithm),。這是一個完全的分布式算法，具有快速切換路由能力,。QSRA算法不是將全部路由信息存儲在源節(jié)點,，而是僅在主節(jié)點上存儲其下游節(jié)點。這個下游節(jié)點包括下游主節(jié)點以及下游切換節(jié)點信息,。正常數(shù)據(jù)傳輸時使用下游主節(jié)點,；當主路由斷開時，斷點首先檢查本身是否有下游切換節(jié)點,，若有,，則選擇其繼續(xù)傳輸數(shù)據(jù)；否則,，斷點將向其上游節(jié)點報告斷開信息，上游節(jié)點繼續(xù)查找有無下游切換節(jié)點,。如此下去,，直到一個上游節(jié)點擁有下游切換節(jié)點繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)為止。該算法適合大型非稀疏網(wǎng)絡,。例如,，當人們在機場候機時接收共享娛樂節(jié)目等。
3 QSRA算法描述
　　實現(xiàn)算法QSRA有二個目的：(1)在路由斷開之前盡快地將數(shù)據(jù)包傳送到目標節(jié)點,；(2)若路由斷開,，則盡快切換到另一路由上繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)。為此,，構(gòu)造路由結(jié)構(gòu),，其路由發(fā)現(xiàn)過程如圖1所示,。算法在路由發(fā)現(xiàn)過程中，完成二項工作：建立主路由和切換路由,。圖1所示的節(jié)點S是源節(jié)點，節(jié)點D是目標節(jié)點,，節(jié)點A，B,，……L是中間節(jié)點。圖1中帶箭頭的粗實線連接部分是主路由，如從S到D的主路由是S-A-B-C-D,。主路由上的點為主節(jié)點，即 A,、B、C為主節(jié)點,。圖1中的虛線部分如S-E-F-G-H-D 和S-I-J-K-L-D是切換路由。相應的E,、F、……L是切換節(jié)點,。在構(gòu)造這樣一個路由結(jié)構(gòu)的過程中，為了清晰,，假定每個主節(jié)點都有下游切換節(jié)點。請注意,，在實際情況中，不一定每個主節(jié)點都有下游切換節(jié)點,，特別是在稀疏網(wǎng)絡中。所以,，QSRA算法更適合大型非稀疏網(wǎng)絡環(huán)境。下面將詳細描述路由發(fā)現(xiàn)和路由維護過程,。

3.1 路由發(fā)現(xiàn)
3.1.1 路由請求過程
　　一個源節(jié)點依靠洪泛方式發(fā)出一個路由請求RREQ(Route Request)，如圖1所示,。請求包結(jié)構(gòu)主要包括源節(jié)點地址、目標節(jié)點地址,、路由信息,、跳數(shù)以及包序列號。收到RREQ包的每個節(jié)點記錄如下信息在緩存中：源節(jié)點地址、目標節(jié)點地址,、上游節(jié)點地址、下游節(jié)點地址(不是下游切換節(jié)點地址),、跳數(shù)和包序列號。如果節(jié)點二次收到同一序列號或大于該序列號的RREQ包,，則丟棄該包；否則,，節(jié)點除記錄上述有關(guān)信息外，將序列號加1,，并洪泛該包,。根據(jù)無線通信原理,，當下游節(jié)點洪泛時,，其上游節(jié)點也能夠收到此信息,。利用該原理，讓上游節(jié)點記錄比自己收到的包序列號大1的包的地址,，也就是其下游節(jié)點地址。直到目標節(jié)點收到RREQ包后,，停止洪泛。為獲得多條路由,，QSRA算法為目標節(jié)點設置一時間段,，以等待RREQ包從多條路由到達目標節(jié)點。根據(jù)到達先后,，QSRA算法選擇最早到達的路由為主路由,，選擇相繼到達的幾個路由作為切換路由,。之后，目標節(jié)點沿主路由返回主路由信息和切換路由信息,。當這些信息經(jīng)過每個主節(jié)點時,，主節(jié)點將緩存中記錄的下游節(jié)點信息與切換路由信息作比較，也就是進行節(jié)點比較,，保留相同的節(jié)點,。其目的是使主節(jié)點擁有切換路由上的切換點。QSRA算法選擇花費時間相對少的路由作為切換路由,。一個RREQ包如果在一條路由上花費的時間比其他路由少,，則說明該路由沒有擁塞(或擁塞較少),，有充足的帶寬，或者路由較近,，這樣能使一個包較快到達目的地；否則,，路由須排隊等待帶寬，擁塞較重,，或跳數(shù)較多，都不能使RREQ包較快到達目標,。因而選擇較早到達目標節(jié)點的路由作為切換路由。
　　下面以圖1為例,，說明QSRA的路由發(fā)現(xiàn)過程。源節(jié)點S向其鄰節(jié)點發(fā)送一個RREQ包,，其鄰節(jié)點A、E和I收到此信息包后,，首先記錄上游節(jié)點S,、路由和跳數(shù)等信息，并將包序列號加1后,，繼續(xù)向其各自的鄰節(jié)點發(fā)送此包,。如上所述,，節(jié)點S收到此包后,，記錄節(jié)點A,、E、I為其下游節(jié)點,；同時，A的下游節(jié)點B,、E,、I也收到加1后的請求包，并分別記錄A為它們的上游節(jié)點,。如此傳輸,，每個中間節(jié)點都記錄其上、下游節(jié)點,。表1列出主節(jié)點擁有的下游節(jié)點,。當節(jié)點E分別從S和A收到RREQ請求時，節(jié)點E自動放棄從A收到的RREQ包,，以避免路由環(huán),。當目標節(jié)點D從不同路由收到該請求包后，根據(jù)到達D點的先后,，選擇最早到達的路由為主路由,，圖1中設S-A-B-C-D為主路由(假定該路由最先到達)，主路由上的節(jié)點為主節(jié)點,；再依次選擇S-E-F-G-H-D和S-I-J-K-L-D為切換路由,，切換路由上的節(jié)點為切換點。

3.1.2 路由反饋過程
　　目標節(jié)點選擇好主路由和切換路由后,，將沿不同路徑返回不同路由反饋包RREP(Route Reply),。沿主路由返回的RREP包,，內(nèi)容包括主節(jié)點信息和切換點信息,。返回主節(jié)點信息主要是使主路由上的節(jié)點知道自己及其上下游節(jié)點,。同樣，沿主路由返回切換節(jié)點信息以使主節(jié)點知道存儲在緩存中的哪一個下游節(jié)點是切換節(jié)點,，以備必要時切換,。當切換節(jié)點到達主節(jié)點時，主節(jié)點將記錄的下游節(jié)點與切換節(jié)點比較,，留下相同的節(jié)點,。由此得到主節(jié)點在切換路由上的切換點；沿切換路由返回的RREP包攜帶切換節(jié)點信息,，以便讓切換路由知道目標節(jié)點選擇自己為切換路由,。這里假定每個節(jié)點自愿擔當路由器，除非該節(jié)點離開,。例如,，圖1中，目標節(jié)點D返回到主路由上的信息包括節(jié)點D,、C,、B、A,、S以及節(jié)點信息D、L,、K、J,、I,、S和D、H,、G,、F、E,、S,。對于節(jié)點C，當它接收到這些節(jié)點信息后,，除標記D是其下游節(jié)點外,，還留下節(jié)點K和G作為它的切換節(jié)點。
3.2 路由維護
3.2.1 路由維護模型
　　一些原有算法[2～5]的路由模型如圖2(a)所示,。它形成從源節(jié)點到目標節(jié)點多條非耦合結(jié)構(gòu)(或者說是并聯(lián)結(jié)構(gòu)),。該結(jié)構(gòu)的優(yōu)點在于一條路由失效時不會影響其他路由,，缺點是增加控制包，每次路由失效,，都需要回到源節(jié)點取其他路由,。QSRA算法的路由模型如圖2(b)所示。它像一片葉脈形狀,，當主路由失效時,，這種結(jié)構(gòu)能夠迅速切換到其他路由。QSRA除了包含這種非耦合結(jié)構(gòu)外,，還具有另外的結(jié)構(gòu),，即主節(jié)點與切換路由有鏈接,。這實際上是一種串并聯(lián)兼有的結(jié)構(gòu),。它的優(yōu)點在于，當主路由失效時,，斷點可以迅速切換到備用路由上,。當一條切換路由失效時，還可以切換到另一條切換路由上繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù),。而且這種結(jié)構(gòu)占據(jù)的節(jié)點個數(shù)相對于MRODP^[2]的第2個算法少,。這里參照多路由算法AMR^[6]，選擇3~4條切換路由,。

3.2.2 路由維護過程
　　為盡快傳送數(shù)據(jù)到目標節(jié)點,，QSRA算法建立了串并聯(lián)兼有的路由結(jié)構(gòu)。當主路由和切換路由都建立起來之后,，源節(jié)點S 能夠通過主路由發(fā)送數(shù)據(jù)到目標節(jié)點,。如果主路由上的某節(jié)點移出其鄰節(jié)點的傳輸范圍，則主路由斷開,。此時,，如果斷點有切換節(jié)點，則立即選擇該點繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)包,；否則將反饋RERR包給它的上游節(jié)點,，再由該上游節(jié)點檢查自己是否有切換節(jié)點。這樣依次向上游推進,，直到有一個上游節(jié)點具有切換節(jié)點為止,。因此，算法QSRA能夠保證將數(shù)據(jù)包盡快傳送到目標節(jié)點,。它對網(wǎng)絡的要求是節(jié)點密度不能太稀疏,，否則，不能形成串并聯(lián)結(jié)構(gòu),。如圖2(b)中,，當節(jié)點C0移出節(jié)點B0的傳輸范圍時,，主路由斷開。此時,，節(jié)點B0 檢查自己是否存儲切換節(jié)點,，若B0點存儲切換節(jié)點(B1，B2,，B3,，B4)，則選擇其中的一個繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù),。若B0節(jié)點沒有切換節(jié)點,，則向上游節(jié)點A0報告此鏈路" title="鏈路">鏈路斷開信息。A0節(jié)點再看自己是否存儲切換節(jié)點,。在整個路由發(fā)現(xiàn)和維護過程中,，算法QSRA僅在路由發(fā)現(xiàn)過程中增加了一些控制開銷，即切換節(jié)點從目標節(jié)點向源節(jié)點回傳過程,，但它屬于單播,，比DSR^[1]和MAR^[6]洪泛操作的控制包數(shù)量低得多。
4 仿真試驗及結(jié)果分析
4.1 仿真試驗
　　仿真試驗中的數(shù)據(jù)如下：節(jié)點最大移動速度16m/s,，最小移動速度1m/s,，暫停時間為0秒，50個節(jié)點隨機移動范圍為2000m×2000m,，無線傳輸頻率2.4GHz,，無線傳輸范圍250m，802.11MAC協(xié)議,，CBR10 frames/s,，總數(shù)據(jù)量10MB。用端到端" title="端到端">端到端延遲,、控制包數(shù)量以及包接收率來評價算法QSRA,，并與DSR^[1]及NDMR^[4]作比較，進行仿真,。當節(jié)點最大速率增加時,，數(shù)據(jù)包的端到端延遲、總控制包數(shù)量和包接收率分別如圖3～圖5所示,。

4.2 結(jié)果分析
　　平均端到端延遲是指包從源節(jié)點到目標節(jié)點的平均時間延遲,。圖3中QSRA算法的時間延遲遠低于DSR和NDMR算法，且曲線比較平穩(wěn),。這主要是因為當主路由失效時,，QSRA有切換路由，可以立即切換，所以時延較低,。而DSR算法在主路由斷開時,，需要重新發(fā)現(xiàn)新路由，所以占用時間多,。NDMR算法也回到源節(jié)點,，但它不是重新發(fā)現(xiàn)路由，而是取已經(jīng)存儲在源節(jié)點的路由,，所以它的延遲比DSR低,，比QSRA高。從曲線整體看,，隨著移動速度的增加,，3條曲線都有上升趨勢。這主要是由于移動速度的增加加速了鏈路斷開的概率,。QSRA增加了切換次數(shù),；NDMR需要頻繁地回到源節(jié)點去路由；DSR需要不斷地回到源節(jié)點重新發(fā)現(xiàn)路由,，因此總的時延增加,。但是,，即使如此,，QSRA的表現(xiàn)仍然比較平穩(wěn)，比DSR和NDMR好許多,。
　　圖4中總的控制包數(shù)量包括RREQ,、RREP以及ERROR包的總和。從整體看,，隨著移動速度的增加,，曲線上升。因為移動速度加快,，增加了鏈路斷開的頻率,，無論是切換還是回到源節(jié)點或是重新發(fā)現(xiàn)路由都會增加控制包數(shù)量。但是相對來看,，QSRA曲線要好于DSR和NDMR曲線,。這是因為前者是及時切換到其他路由，它僅需要較少的控制包就能進入正常續(xù)傳軌道,，曲線較穩(wěn)定,；而后二種算法需要回到源節(jié)點去路由或重新找路由，這無疑增加了控制包數(shù)量,，特別是DSR的曲線,。
　　圖5中，QSRA算法的包接收率表現(xiàn)得很平穩(wěn)，受移動速度的影響比較??；而NDMR的包接收率比較低，DSR算法最低,。包接收率低的現(xiàn)象,，主要受移動速度的影響。當移動速度增加,，加快鏈路斷開的頻率,，DSR算法必須重新發(fā)現(xiàn)路由，傳送到中途的數(shù)據(jù)包被丟棄,，總的包接收率低,；NDMR算法也一樣有棄包操作，只是相對于DSR,，它重新發(fā)現(xiàn)路由的概率低,，棄包現(xiàn)象不嚴重，但當存儲的多路由用盡后,，重演DSR過程,；而QSRQ算法因為有切換路由，直接將數(shù)據(jù)包切換到備用路由繼續(xù)傳輸,，故接收率相對較好,。從整體曲線看，隨著移動速度的增加,，曲線均有下降趨勢,。分析原因主要是移動速度增加，鏈路斷開的概率增加,，都有棄包操作,，再加上傳輸時間延長，重傳操作頻繁,，加重網(wǎng)絡負載,，丟包現(xiàn)象嚴重，總的包接收率隨移動速度增加而下降,。
　　多路由機制已經(jīng)不是新設想,，但是每種多路由算法各有不同。QSRA算法主要從快速切換路由的角度考慮,。因為移動自組網(wǎng)絡的節(jié)點移動時常導致數(shù)據(jù)傳輸?shù)街型緯r,，路徑失效，傳輸被迫中斷,。于是,，一些算法提出回到源節(jié)點取備用路由,，重新傳輸。而QSRA算法采用就地取材的辦法,，在斷點或其附近迅速切換到預備路由上,，保證最快時間繼續(xù)傳遞數(shù)據(jù)。它在路由發(fā)現(xiàn)過程中,，備份其他能夠到達目標節(jié)點的節(jié)點,，當路由失效時選擇這些備用點。不僅如此,，當一個備用點失效時,，QSRA算法還可以繼續(xù)取備用點傳輸，避免回頭去重新取路由而造成的浪費,。算法分析和仿真表明相對于DSR算法和NDMR算法,，QSRA算法在平均端到端延遲、控制包數(shù)量,、包接收率方面都有不同程度的改進,。
參考文獻
1 Johnson D J，Maltz D A,，Hu Y C.The dynamic source route protocol for mobile Ad Hoc networks(DSR).IETF Mobile Ad Hoc Networks working Group,，Internet Draft work in progress，2003
2 Nasipuri S,，Castaneda R.Performance of multipath routing for On-Demand porotocols in mobile Ad Hoc networks.Mobile Networks and Applications,，2001：339～349
3 Kim S K，Noh W J,，An S S.Multi-path Ad Hoc route considering path redundancy.In：Proc of the 8th IEEE International Symposium on Computers and Communication,，Antalya，Turkey,，2003
4 Li X F，Cuthbert L.On-demand node-disjoint multipath route in wireless Ad Boc networks.In：Proc of the 29th Annual IEEE International Conference on Local Computer Networks,，Tampa,，F(xiàn)lorida，USA,，2004
5 Leung R,，Liu J L，Poon D et al.MP-DSR：A QoS-awae multi-path dynamic source route protocol for wireless Ad-Hoc Networks.In：Proc of the 26th Annual IEEE Conference on Local Computer Networks,，Tampa,，F(xiàn)lorida，2001
6 Chen Y Q,，Guo X F,，Zeng Q K et al.AMR：A multipath routing algorithm based on maximum flow in Ad Hoc networks.In：ACTA ELECTRONICA SINICA，China，2004：1297～1301