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

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

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

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

4.2 結果分析
　　平均端到端延遲是指包從源節點到目標節點的平均時間延遲。圖3中QSRA算法的時間延遲遠低于DSR和NDMR算法，且曲線比較平穩。這主要是因為當主路由失效時，QSRA有切換路由，可以立即切換，所以時延較低。而DSR算法在主路由斷開時，需要重新發現新路由，所以占用時間多。NDMR算法也回到源節點，但它不是重新發現路由，而是取已經存儲在源節點的路由，所以它的延遲比DSR低，比QSRA高。從曲線整體看，隨著移動速度的增加，3條曲線都有上升趨勢。這主要是由于移動速度的增加加速了鏈路斷開的概率。QSRA增加了切換次數；NDMR需要頻繁地回到源節點去路由；DSR需要不斷地回到源節點重新發現路由，因此總的時延增加。但是，即使如此，QSRA的表現仍然比較平穩，比DSR和NDMR好許多。
　　圖4中總的控制包數量包括RREQ、RREP以及ERROR包的總和。從整體看，隨著移動速度的增加，曲線上升。因為移動速度加快，增加了鏈路斷開的頻率，無論是切換還是回到源節點或是重新發現路由都會增加控制包數量。但是相對來看，QSRA曲線要好于DSR和NDMR曲線。這是因為前者是及時切換到其他路由，它僅需要較少的控制包就能進入正常續傳軌道，曲線較穩定；而后二種算法需要回到源節點去路由或重新找路由，這無疑增加了控制包數量，特別是DSR的曲線。
　　圖5中，QSRA算法的包接收率表現得很平穩，受移動速度的影響比較小；而NDMR的包接收率比較低，DSR算法最低。包接收率低的現象，主要受移動速度的影響。當移動速度增加，加快鏈路斷開的頻率，DSR算法必須重新發現路由，傳送到中途的數據包被丟棄，總的包接收率低；NDMR算法也一樣有棄包操作，只是相對于DSR，它重新發現路由的概率低，棄包現象不嚴重，但當存儲的多路由用盡后，重演DSR過程；而QSRQ算法因為有切換路由，直接將數據包切換到備用路由繼續傳輸，故接收率相對較好。從整體曲線看，隨著移動速度的增加，曲線均有下降趨勢。分析原因主要是移動速度增加，鏈路斷開的概率增加，都有棄包操作，再加上傳輸時間延長，重傳操作頻繁，加重網絡負載，丟包現象嚴重，總的包接收率隨移動速度增加而下降。
　　多路由機制已經不是新設想，但是每種多路由算法各有不同。QSRA算法主要從快速切換路由的角度考慮。因為移動自組網絡的節點移動時常導致數據傳輸到中途時，路徑失效，傳輸被迫中斷。于是，一些算法提出回到源節點取備用路由，重新傳輸。而QSRA算法采用就地取材的辦法，在斷點或其附近迅速切換到預備路由上，保證最快時間繼續傳遞數據。它在路由發現過程中，備份其他能夠到達目標節點的節點，當路由失效時選擇這些備用點。不僅如此，當一個備用點失效時，QSRA算法還可以繼續取備用點傳輸，避免回頭去重新取路由而造成的浪費。算法分析和仿真表明相對于DSR算法和NDMR算法，QSRA算法在平均端到端延遲、控制包數量、包接收率方面都有不同程度的改進。
參考文獻
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，Florida，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，Florida，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