移動自組織網絡中基于鏈路預測的多路徑路由協議研究

黃錢飛萬 俊邱海燕

(1.江西現代職業技術學院，江西 南昌 330000；2.重慶郵電大學，重慶 404100)

1.引言

移動自組織網絡(MANET)[1]是由多個具有收發功能的移動終端組成的一個多跳的網絡。它不像傳統的無線網絡需要固定的基礎通信設施，也沒有控制節點，抗毀滅性非常強，適合于許多網絡布線困難的環境。隨著該類網絡的發展，像多媒體實時業務以及大流量的視頻業務也開始在該類網絡上應用，然而移動自組織網絡自身帶寬以及延時方面的局限性也成為了該類業務發展的瓶頸，本文將從多路徑并發路由協議著手解決這些業務瓶頸。

2.AOMDV協議

AOMDV[2]是按需多路徑距離矢量路由協議，是在AODV單路徑路由協議的基礎上擴展的多路徑路由協議，因此保留了AODV的許多特性，兩者最主要的區別在于AOMDV在路由發現過程中建立了多條可用的路徑。因此AOMDV在移動自組織網絡中有較強的適應性和較好的可擴展性。

3.AOMDV路由改進及實現

3.1 改進思路

目前AOMDV路由協議仍有不足之處：第一，AOMDV路由協議中使用最短路徑作為路徑選擇的依據，但是在移動自組織網絡中節點運動頻繁，網絡拓撲變化快，鏈路斷鏈的可能性大大增加，顯然最短路徑的穩定度不足，路徑斷鏈的肯定性也增加了；第二，AOMDV使用一條路徑作為主路徑，其他路徑作為備用路徑，然而當主路徑失效的時候，才使用備用的路徑，但是在移動自組織網絡的拓撲變化快，可能當主路徑失效后切換到備用路徑時，備用路徑已經失效，從而增加了端到端的時延；第三，AOMDV只使用一條主路徑進行數據傳輸，不能滿足大數據量業務的需求。本文針對以上不足之處，提出了AOMDV-SPC路由協議進行了以下兩點改進：

(1)在路徑選擇時，選擇路徑穩定性高的路徑進行數據傳輸，可以降低數據轉發期間路徑中斷的概率，減小網絡重建和修復開銷、提高網絡的性能。

(2)提出了多條路徑并行傳輸的數據傳輸機制，充分利用網絡資源，并使用基于路徑持續時間的流量分配機制。

3.2 改進協議描述

3.2.1 算法模型

根據Two Ray Ground Reflection無線傳播模型來計算鏈路危險閾值，設定鏈路危險閾值功率Pthreshold，如圖1所示，在圖中節點b以vmax的相對速度移動，虛線圓表示路徑危險的無線覆蓋范圍d，當節點a在虛線圓與實線圓之間時表示鏈路處于危險狀態，而鏈路危險閾值功率Pthreshold為圖中虛線圓的接收到的節點a的功率。

圖1 鏈路危險閾值模型

常用的WaveLAN的無線網卡的最低接收的功率和無線傳輸半徑的取值分別為3.65×10-10W和250m。設定節點最大速度為vmax，路由警告分組或錯誤分組在移動自組織網絡中傳輸的最久時間為tmax，則危險閾值Pthreshold是當兩節點間在相距(250－vmax×tmax)M時的接收到的功率，可以得到公式：

在網絡中的某個節點接收到的分組的能量小于某一危險閾值，節點就需要啟動鏈路持續時間預測機制來預測該節點與前驅節點鏈路的持續時間。所以危險閾值直接關系到是否啟動預測機制。在鏈路持續時間預測機制中，節點路由表中保存三組前驅值，即在最近三個時刻t1、t2、t3時刻接收到的三個前驅節點數據的能量值P1、P2、P3，當收到新的分組時需要更新以上數據。假定網絡中兩個可以直接通信的節點A、B，設A為B的前驅節點，PAB(current)表示節點B當前接收到前驅節點A的分組信號的能量值，PAB(ave)表示為節點B的最近三次接收到節點A的分組信號的能量值的平均值，用△PAB表示節點B接收到的分組的能量變化率：

如果△PAB大于0時，說明節點B接收到節點A的能量在增強，不用考慮進入危險狀態，如果△PAB小于0時，說明節點的節點B接收到節點A的能量在減弱，通過以下公式計算鏈路持續時間tLC的值：

設路徑持續時間為PSF，定義為路徑中所有鏈路的持續時間的最小值。

3.2.2 協議實現

AOMDV-SPC的路由發現過程是在AOMDV路由協議的基礎上擴展的，在RREQ RREP分組以及路由表結構在加入路徑持續時間因子PSF，RREQ具體更改如表1：

表1 RREQ分組結構

當源節點需要發送數據給目的節點時：源節點查看自己的路由表中是否包含到達目的節點的路由，如果有就根據路徑穩定因子選擇一組路徑進行傳輸，沒有的話就啟動路由發現過程，在全網洪泛改進后的RREQ分組，當某個節點i接收到RREQ分組時，就根據分組來創建或更新到源節點的反向路由，特別是會根據RREQ分組更新反向路由中的路徑持續時間因子PSF，節點i判斷是否有到目的節點的有效路由，如果存在就回復源節點RREP分組，若不存在就判斷節點是否收到過相同的RREQ分組，若收到則不轉發，若未收到則繼續廣播路徑持續時間因子PSF更新后的RREQ分組。當目的節點或還有到目的節點路徑的中間節點收到RREQ分組時，目的節點回復RREQ時，路徑穩定因子初始化為1，如果是中間節點回復RREQ分組，則分組的路徑持續時間因子PSF為中間節點到目的節點路徑的路徑持續時間因子PSF。當節點收到RREQ，確定節點i是否有到目的節點的前向路由表項，如果有則根據路由更新規則創建和更新前向路徑并更新前向路徑的路徑持續時間因子PSF，如果沒有就創建路由表項并添加和更新前向路徑并更新路徑持續時間因子PSF。

4.數據發送及流量分配

在多路徑并行傳送數據時應該考慮如何將數據分組以合理的方式分配到不同的路徑中去，充分利用網絡資源，選擇合理的數據顆粒度能夠提高網絡數據分組分發效率。本文采用基于每分組分配粒度方式[4]。

與AOMDV協議中采用的備用路由的數據發送方式不同，AOMDV-SPC協議采用的是在不同路徑上同時發送數據，在AOMDV-SPC路由協議中主要分兩種情況進行數據的發送：

(1)當發送的是多種不同類型業務時，AOMDV-SPC協議采用不同的傳輸路徑發送不同的業務流量。

(2)當發送的某一種業務流量很大、某一條鏈路不能夠滿足其業務需求時，AOMDV-SPC協議使用不用路徑同時發送該業務的流量。

情況一中，當數據分組從源節點的應用層傳到路由層時，協議根據分組中的IP頭的ToS（type of service）字段對分組進行分類，我們可以把流量類型分為兩類，一類是盡力而為的數據業務，另一類是對流量需求較大的實時業務。根據相關的多路徑路由的文獻[5，6]，多路徑的數目不是越多越好，因為隨著路徑的增加，路由開銷增加較大。本文中選取的是最大路徑數目是3條。因此，當源節點有分組需要發送時，如果是實時業務分組，則從路由列表中選擇路徑穩定因子較高的路徑進行發送，而盡力而為的數據業務則用路徑穩定因子較小的路徑進行發送。

每條路徑上需要分配多少數據流量，主要根據數據流量的實際大小和業務類型。像數據量小的業務如果采用多路徑傳輸就顯得不合適了，可以選擇一條路徑穩定度高的路徑進行傳輸，這樣降低整個網絡的路由開銷，提高路徑的使用效率。由于小的數據流只使用一條路徑傳輸而其他的鏈路就可以更多的傳輸其它的數據流，從而提高網絡利用率。針對數據流量較大的業務，將一個很大的數據流量分成小塊，然后再分配到多條路徑上進行傳輸，可以明顯的降低端到端的延時，增加網絡的吞吐量。我們需要確定每條路徑需要分配多少的流量。

本文采用路徑穩定度權值分配流量，同時需要避免穩定度大的路徑分配流量過大，穩定度小的路徑分配流量過小，下面給出了每條路徑流量分配的公式，fk為路徑k上的流量，F為總流量：

5.仿真結果及分析

本文模擬環境采用自由空間移動模型，網絡節點隨機分布在1000*1000的矩形范圍內。所有節點的無線傳輸半徑為250m，網絡中的路由請求和相應的目的節點隨機產生，各節點發送緩存長度為50個分組，每個分組是512字節的長度，實驗使用CBR流作為數據源，使用IEEE802.11的DCF作為媒體接入控制協議，通過暫停時間來設定網絡的移動性，節點的移動速度為2-20m/s。

圖2 不同數據分組發送速率下的吞吐量

圖3 不同數據發送速率下的端到端延時

圖2、圖3、圖4中分別給出了改進后協議AOMDV-SPC在不同數據發送速率下的吞吐量、端到端延時以及分組到達率，從圖中可以看出改進后協議AOMDV-SPC在CBR不斷增加過程中，吞吐量一直高于AOMDV、AODV，端到端延時一直低于AOMDV、AODV，分組到達率一直高于AOMDV、AODV，這是由于AOMDV-SPC協議中源節點到目的節點采用的是3條路徑并行傳輸方式，在帶寬方面充分保證了數據傳輸，充分利用了網絡傳輸資源，降低了某些路徑的擁塞程度，提高了吞吐量，降低了端到端延時，而AODV和AOMDV協議都是使用一條路徑進行數據傳輸，限制了數據傳輸速度，而且AOMDV-SPC在路由選擇上使用的路徑的路徑持續時間因子較高的路徑，降低了鏈路斷裂的幾率，因此就提高吞吐量及分組到達率，降低了延時。

圖4 不同數據發送速率下的分組到達率

6.結語

仿真結果顯示，AOMDV-SPC在一定程度上增加了路由控制包數量，提高了網絡的吞吐量、時延以及分組到達率的性能，使得AOMDV-SPC能夠在一定程度上滿足移動Ad hoc網絡的多媒體實時業務以及大流量傳輸要求。參考文獻：

[1]鄭少仁，王海濤，趙志峰等.Ad hoc網絡技術[M].北京：人民郵電出版社，2005：1-13.

[2]毛靖添.Ad Hoc網絡按需多徑路由協議的研究[D].哈爾濱工程大學.2007.

[3]Illya Stepanov，Kurt Rothermel.On the impact of amore realistic physical layer on MANET simulations results.Ad Hoc Networks.2006.6 (1)：61-78.

[4]楊俊麗，劉明等.基于相關因子的節點不相交的ad hoc多路徑路由算法[J].小型微型計算機系統，2006，27(9)：1669-1672.

[5]Li Li，Ram jee，R，Buddhikot M.，M iller，S..Network Coding-Based Broadcast in Mobile Ad-hoc Networks.IEEE.INFOCOM 2007.26th IEEE International Conference on Computer Communications.2007：1739-1747.

[6][Nasipuri A，Castaneda R，Das S.R.Performance of M ultipath Routing for On-Demand Protocols in Mobile Ad hoc Networks[J]，Mobile Networksand Applications.2001，V6：339-349.