移動Ａｄ ｈｏｃ網絡多徑數據傳輸

(南京理工大學計算機科學與技術學院，南京 210094)



摘 要：

針對移動Ad hoc網路數據傳輸可靠性低下問題，建立移動Ad hoc網絡數據傳輸數學模型，提出了通過多路同時傳輸數據以提高傳輸可靠性的方法，并基于傳輸模型對方法進行了分析，得出需要采用多播多路徑方式傳輸數據的結論。實驗與單路數據傳輸方法進行比較，結果表明在節點數較多時傳輸可靠性得到了提高。

關鍵詞：數據傳輸； 多路徑； 移動自組網

中圖分類號：TN915.04 文獻標志碼：A

文章編號：1001-3695(2009)02-0683-03



Data transmission in MANETby multi-path



MA Chi， XU Jia， ZHANG Hong， LIU Feng-yu

(College of ComputerScience Technology，Nanjing University of Science Technology， Nanjing 210094， China)



Abstract:To solve the problemof low performance on data transmission in Ad hoc network， this paper established a model of data transmission in mobile Ad hoc network， and found a way to improve transmission reliability by sending data on multi-path at the same time. After the analysis of the model， it appeared that transmitting databy multi-path multicast could improve the reliability of data transmission. Simulationresult indicatesthatthe reliability of data transmission has been improvedcompared with uni-path method when there are many nodes in the network.

Key words：data transmission; multi-path; MANET



0 引言 

移動多跳Ad hoc[1]網絡（MANET）是一種自組織、自管理并且不需要其他基礎設施支持的無中心網絡，在軍事、救災等場合應用廣泛。一直以來研究主要集中在如何建立和維持一條有效的路由來傳輸數據，如按需路由協議[2]（Ad hoc on-demand distance vector routing， AODV）。但研究發現，在網絡節點快速運動時這些協議的路由有效時間會大大降低，因此研究人員開始研究路由備份和修復算法。國內如肖百龍等人[3]提出了路由的局部修復算法；國外，S. J. Lee等人[4]提出了按需備份路由協議（Ad hoc on-demand distance vector-backup routing， AODV-BR），他們[5]還提出了SMR（split multi-path routing）協議，希望找到最多的互相獨立的多條路由。比較著名的是按需多路徑路由協議[6]（Ad hoc on demand multipath distance vector routing， AOMDV），它維護了多條到達目的節點的路由，當一條路由失效后，立刻用備份的路由進行數據傳輸，這降低了路由發現頻率和數據傳輸的反應時間。A. Tsirigos等人[7]對多條路徑進行數據傳輸做了一些分析，他們的工作著眼于如何將數據分別發送到多條路徑上來保證數據傳輸的成功。但這些研究的前提是每次數據通過一路傳輸，也就是單播傳輸數據，沒有考慮同時將數據發送到多條路徑上的情況。對于軍事應用場合，特別在高毀傷強干擾情況下，路由建立后的有效時間較短，在網絡被打擊后可能出現分割，從根本上失去了重傳數據的可能。因此，希望數據在較短時間一次傳輸就可以保證到達目的端，避免重傳。為了實現這一要求，必須充分利用多路徑的優勢。本文的思想是，在一次路由發現成功之后，不是將數據通過一條或多條備份路徑依次發送，而是向多條路徑同時發送多個相同數據塊。這樣，即使Ad hoc網絡的變化比較劇烈，只要有部分路徑有效就可以使數據完整傳達。

1 MANET多徑數據傳輸數學分析

由于目前國內外對Ad hoc網絡多徑數據傳輸研究較少，且缺乏較為精細的數學模型，本章將首先建立基于時間的多徑數據傳輸數學模型，以便于數學分析和今后進一步研究。

1. 1 模型總體假設

a)網絡存在從源到目的節點的多條路徑，并且路徑是互相獨立的。目前AOMDV協議可以保證實現這一點。

b)至少在一個較短的時間段內，由AOMDV等多徑路由協議產生的多條路由中部分路由是有效的。如果即使在一個較短的時間段內所有路由都無法保證有效，那么數據傳輸根本無法實現。

c)本文研究的移動自組網節點數據傳輸能力完全一樣，即每兩個節點之間的數據傳輸帶寬是相等的。

1. 2 單徑數據傳輸的數學模型

1. 2. 1 傳輸時間的分析

圖1是從源節點到目的節點通過一條路徑發送數據所需時間的抽象模型。其中：ts為數據發送到傳輸路徑上所需時間；tt為兩節點間無線信號傳輸時間；tp為數據包在節點中轉發時間；ta為總時間。由圖可知，ta=ts+n×tt+(n-1)tp。由于節點間距離不太長，傳輸時間ts可以忽略；另外假設數據包轉發處理時間tp相對于發送時間可以忽略。上式可簡化為ta≈ts，即數據在一條路徑上的傳輸時間主要取決于數據發送到這條路徑上所需的時間。不失一般性，假設數據量為x(bit)，節點間傳輸帶寬為w(ps)，則數據發送到路徑上所需的時間ts=X/W。所以通過單條路徑傳輸總時間為ta≈ts=X/W。

1. 2. 2 傳輸成功概率公式的假設

先給出單條路徑數據傳輸失敗概率公式的假設。

在無線自組網中，由于節點隨機移動和毀傷，路由會失效，根據這一特性可知：

a)在單條路徑上，數據傳輸所需時間越長，則數據傳輸過程中路徑失效的概率就越大，即傳輸失敗的概率越大。如果數據需要無限長時間傳輸，則數據傳輸肯定在某個時間失敗。

b)由于網絡的變化是隨機的，數據傳輸失敗的時間是一個隨機變量。

基于這兩點，本文假設數據在單條鏈路上傳輸失敗時間的概率密度函數滿足指數分布，即f(t)=1/θ e-t/θt＞00t≤0。其中：t為數據傳輸失敗的時間；θ>0是一個常數。通過簡單積分可得傳輸失敗時間的概率分布函數F(t)=1-e-t/θ t＞00t≤0。因此，一條路徑傳輸數據成功的概率函數p(t)=1-F(t)=e-t/θ，t>0。根據1.2.1節可知單徑數據傳輸成功的概率P=e-X/(wθ)。其中：θ是一個正常數，代表網絡變化特性。

如圖2所示，觀察傳輸失敗概率分布函數F(t)，發現：

a)當時間趨于零，路徑失效的概率F(t)也趨于零。其含義是，如果數據包從源發送到目的節點所需時間為零，則傳輸數據時路徑失效的概率為零。這個假設顯然是合理的。另外，當時間增大，路徑失效的概率會不斷增加，如果時間趨于無窮，則路徑失效概率必會趨于1。這與前面兩點分析相吻合。

b)指數分布具有無記憶性的特點。即從0到t′時刻路徑失效的概率與已知過了s時刻，從s到s+t′時刻路徑失效的概率是一樣的。證明如下：

P{T＞s+t′|T＞s}=P{(T＞s+t′)∩(T＞s)}/P{T＞s}=

P{T＞s+t′}/P{T＞s}=[1-F(s+t′)]/[1-F(s)]=

e-(s+t′)/θ/e-s/θ=e-t′/θ=P{T＞t′}



這符合無線自組網絡的特點。因為節點的移動對路由的影響是不可知的，不論先后，相同一段時間內數據發送失敗的概率相同才比較合理。

圖2中各有三條曲線，它們分別對應θ取不同值的情況。根據概率知識可知，θ是數學期望值，它在這里的意義是數據傳輸失敗的平均時間，這個值越大，意味著網絡的穩定性越高，則相同時間數據傳輸失敗的概率越低。通過對節點移動模型的研究可以得出θ的取值公式，這里不再詳述。

1. 3 多徑數據傳輸的數學模型

如圖3所示，假設節點A與節點F間有四條互相獨立的路徑，A要把數據通過多條路徑傳輸到F，則首先要將數據傳輸給節點B、C、D、E，然后再傳輸到F。

由A傳輸到B、C、D、E的方法有兩種，即單播傳輸和多播傳輸。單播傳輸就是將數據依次傳給B、C、D、E轉發；而多播傳輸是將數據多播給B、C、D、E，由它們同時發送出去。下面為方便說明，假設單徑數據傳輸成功的概率為Ps(single-path);單播多徑傳輸成功概率為Pmm(unicast multi-path);多播多徑傳輸成功概率為Pu(multi-cast multi-path)。

1. 3. 1 單播多徑傳輸概率公式

假設數據長b，一路帶寬為w，考慮負載均衡，每條路發送b/4數據。由于通過路徑1、2、3、4依次傳輸，根據無線自組網單播特性可知，當A通過1號路徑給B發送數據時，C、D、E需要靜默等待。依此類推，數據傳輸總時間是4×b/（4w），即b/w，數據完整傳輸成功的概率是

Pum=e-b/(4ωθ)×e-b/(4ωθ)×e-b/(4ωθ)×-b/(4ωθ)=(e-b/(4ωθ))4=e-b/(ωθ)。

由1.2.1節可知，對b單徑數據傳輸成功的概率Ps=（-b/ewθ），可見Pum=Ps，即通過單播多徑傳輸數據和通過單徑傳輸數據成功概率是一樣的。

1. 3. 2 多播多徑傳輸概率公式

假設數據塊仍為b，一路帶寬也是w，區別是第一跳傳輸采用多播傳輸，即對A發出的數據，B、C、D、E都接收，然后再借用它們到達目的節點的路徑同時單路轉發下去。這里只有第一跳才使用多播方式，為的是防止產生洪泛。顯然，數據傳輸的總時間為b/w，這與單播傳輸時間一樣長。但是，傳輸成功的概率變成Pmm=1-(1-e-b/（wθ）)4。做個簡單計算，若單路傳輸成功概率Ps=e-b/（wθ）=0.2，則四路多播傳輸成功的概率是Pmm=0.590 4，成功的概率大大增加。

1. 3. 3 不同傳輸方式的比較

通過以上闡述可知，對于相同的數據量，單徑數據傳輸與單播多徑數據傳輸成功的概率相同。因此，只需比較單徑數據傳輸和多播多徑數據傳輸的情況。

設數據塊長b，路徑數k，多播多徑傳輸成功的概率Pmm(k)=1-(1-e-b/（wθ）)k，而單徑傳輸成功的概率為Ps=e-b/（wθ）。假設b/w=1，θ=0.5，比較兩者，如圖4所示，在路徑數為1時，單路徑和多播多路徑傳輸成功的概率相同；但當路徑個數大于1時，多徑傳輸的成功概率不斷增加。結論是，對于一塊數據，采用多播多徑方式傳輸可靠性更好。

下面分析一下θ值的影響。由上述可知，θ是一條路徑數據傳輸失敗的平均時間。不同值下概率隨路徑數的變化如圖5所示。圖5中對于成功概率0.7，θ值越小，則需要傳輸的路徑數就越多。這表明網絡變化比較劇烈且θ值較小（路由平均失效時間較短）的情況下，需要更多的路徑來同時轉發數據才可以達到較高的傳輸成功率。

2 MANET多播多徑數據傳輸算法

從上面分析可知，將數據通過多播多路徑傳輸可以有效提高數據傳輸的成功率，減少數據重傳。為了實現這一思想，本章將給出一個基于AOMDV協議的算法。

要實現數據的多路徑傳輸，需要對現有AOMDV協議進行修改。AOMDV算法是在AODV按需路由協議的基礎上發展而來的多路由協議。路由發現過程兩者類似。但AOMDV會得到并維護到達某一目的節點的多條路由。

算法描述如圖6所示。

a)當源節點需要發送數據時，如果沒有到達目的節點的路徑，則進行路由發現。路由發現過程與AOMDV相同，這樣每個節點都會維護到目的節點的多條路由。

b)源節點通過廣播發送數據，將TTL（生存時間）設為1。并且將指向目的節點的多條路徑中的所有下一跳節點地址封裝在數據包中，并設置特殊控制標志。

c)接收到廣播數據包的必定是它的鄰居節點。節點接收到數據后，如果發現特殊控制標志，則檢查數據包，看自己是否在數據包的下一跳節點地址中。若在，則根據目的地址選擇多條路中的第一路轉發數據包，并且將數據包的特殊控制標志復位；否則丟棄數據包。

3 仿真實驗

本文使用NS2[8]仿真實驗平臺進行實驗。對AOMDV協議進行了修改，以實現數據第一條多播發送后由多個節點通過多路共同傳輸數據。仿真MAC協議采用802.11協議，時間60 s，網絡節點從40逐步增加到100，每進行一次實驗增加20個節點。最大路徑數設置為3，節點移動最大速度為20 m/s。選出距離較遠的兩個節點之間發送CBR數據包。節點數vs延時時間如圖7所示。節點數vs可達性如圖8所示。

從圖7可以看出，通過一條路徑發送數據和通過多條路徑發送數據的端到端時延基本上差不多，說明多路徑傳輸對于端到端時延影響不大。但是通過圖8發現，在節點數較大時（40個節點以上），通過多路發送的收包率得到了提高；并且隨著網絡規模的擴大，多路徑傳輸的收包率平穩增加而單路徑傳輸卻因為節點移動影響了收包率。但是需要注意的是，在節點數較少的情況下，如20個節點，通過多路發送的收包率反而不如通過一路發送，這說明在網絡較小的情況下，發現多條路徑是不容易的。結論是：在節點數較多的情況下多徑傳輸比單徑傳輸的可靠性高。

4 結束語

本文建立了Ad hoc網絡多路徑傳輸數據的數學模型，并對其進行了分析。通過修改AOMDV路由協議進行了實驗，得出了通過首跳多播這種特殊的多路徑數據傳輸策略可以提高數據傳輸可靠性的結論。但是，本文基于的假設是多條路徑互相獨立的，對于路徑不相獨立的情況沒有分析。另外，從實驗中可以看到，在網絡節點較少的情況下，簡單的多路傳輸效果不佳，這是由于在規模較小時網絡的多條路徑很難發現。這些問題將是今后研究的方向。

參考文獻：

[1]YIYJ， GERLA M， KWON T J. Efficient flooding in Ad hoc networks using on-demand(passive) cluster formation[C]//Proc of the 2nd Annual Mediterranean Ad hoc Networking Workshop. Lausanne， Switzerland: ACM Press， 2002:1-12.

[2]PERKINS C， BELDING-ROYER E. RFC 3561， Ad hoc on-demand distance vector (AODV) routing[S]. 2003.

[3]肖百龍，郭偉，劉軍，等.移動自組網路由局部修復算法的研究[J].計算機研究與發展， 2007，44(8):1383-1389.

[4]LEE S J， GERLA M. AODV-BR: backup routing in Ad hoc networks[C]//Proc of IEEE WCNC 2000. 2000:1311-1316.

[5]LEE S J， GERLA M. Split multipath routing with maximally disjoint paths in Ad hoc networks[C]//Proc of ICC 2001. Washington: IEEE Computer Society， 2001:3201-3205.

[6]MARINA M K， DAS S R. On demand multi-path distance vector routing in Ad hoc networks[C]//Proc of IEEE International Conference on Network Protocols. Washington: IEEE Computer Society， 2001.

[7]TSIRIGOS A， HAAS Z J. Analysis of multipath routing-part I: the effect on the packet delivery ratio[J].IEEE Trans on Wireless Commun， 2004，3(1):138-146.

[8]The network simulator-NS2[EB/OL]. http://ww.isi.edu/nsnam/ns.