基于WiFi的自組織網絡路由協議算法研究

畢海霞 魏志強 薛廣然 貫林林

(1.西安電子工程研究所 西安 710100;2.92995部隊 青島 266100)

0 引言

自組織網絡是近年來無線移動通信網絡發展的一個熱點，其主要特征是無中心、自組織、多跳路由和動態拓撲，具有網絡快速部署、抗毀性強和組網靈活等優點。網絡中的節點具有雙重角色，既是普通移動終端，又具有路由器的功能。當通信的源節點和目的節點無法直接通信時，可通過中間節點進行報文轉發［1］，實現多跳無線通信的功能［2］。然而，在實際應用中，通常存在無線信道傳輸速率低的瓶頸，這成為制約自組網發展的重要因素。WiFi(Wireless Fidelity)，又稱802.11標準，由IEEE工作組于1999年9月提出，其最大特點即傳輸速度高，其中，802.11b的速率可達到11Mbps［3］。近年來，WiFi業務呈現爆炸式增長，新的WiFi標準相繼出臺，802.11n的速度最大可至300Mbps，WiFi技術及產品亦日臻成熟。

將WiFi技術應用于自組織網絡，建立高速的自組網移動網絡，能夠提高數據傳輸速率，充分發揮兩種技術的優勢，具有非常廣闊的應用前景，可用于戰場上部隊的快速部署和推進，地震或水災后的搶險救災，以及其他臨時組網應用等。近年來，各國軍方都在積極論證將WiFi應用于戰場車載自組織網系統。因為將基于WiFi的自組織網絡應用于實際軍事，可以帶來很多突出優點。比如，可提高戰術互聯網的無縫鏈接，提高數據傳輸和態勢感知能力。另外，其通信距離小，可提高系統的抗截獲能力等。路由算法是自組織網絡中最重要的一部分，其設計的高效與否直接影響到網絡性能。本文通過對典型的自組網路由協議進行仿真實驗分析，并針對戰場環境下的大規模組網以及火控數據傳輸需求，并提出了一種新的路由算法。

1 基于WiFi的自組網路由算法

按照自組網路由發現策略的方式，可將自組織無線網絡路由協議分為先應式路由與反應式路由。先應式路由又稱為表驅動路由協議，在這種路由協議中，無論是否有通信需求，每個節點周期性的廣播路由分組，交換路由信息，維護到達其他節點的路由信息。當檢測到網絡拓撲結構發生變化時，節點在網絡中發送更新消息。收到更新消息的節點將更新自己的路由表，以維護準確的路由信息。常用的先應式路由算法包括 DSDV［4］、WRP、OLSR、FSR 等。反應式路由協議又稱為按需路由協議，它根據網絡分組的傳輸請求，被動地搜索從源節點到目的節點的路由，當沒有分組傳遞請求時，節點處于靜默狀態，并不需要交換路由信息。典型的反應式路由算法包括 DSR［5］、AODV［6］、LAR［7］等。

根據IETF RFC2501，自組網網絡的仿真參數主要有端到端吞吐量和時延、尋由時延、分組投遞率、尋由開銷與效率以及平均跳數等。由于WiFi網絡的傳輸速率較高，路由開銷及尋由時延對網絡效率影響不大，分析中不考慮這兩個因素，而選擇端到端時延、報文投遞率和端到端吞吐量三個指標作為主要評價參數。

a.報文投遞率(packet delivery ratio)，即目的節點接收到的數據包個數與源節點發送的數據包個數的比值，反映了網絡傳輸的可靠性，報文投遞率越高，可靠性越大。

b.端到端時延(end-to-end data delay)，即報文從源節點到目的節點的平均延遲，反映了應用層中分組的時間特性。它包括路由發現和端口排隊時分組在緩沖區中的延時，也包括MAC層進行重傳以及分組傳播的時間。

c.端到端吞吐量(throughput)，在較大程度上可反映應用層數據的傳遞速率。

針對以上三個性能指標，本文選用OPNET仿真平臺分別對AODV、DSR、LAR和OLSR路由協議進行分析比較。節點移動方式選取組移動模型(Group Mobility Model)，節點個數為50個，節點移動速度從1m/s到25m/s，范圍是10km×10km的區域。MAC層采用IEEE802.11協議，網絡帶寬為5.5Mbps，每個數據包大小為500bytes。

1.1 節點移動速度的影響分析

節點移動速度的不同反映了網絡拓撲結構變化的快慢。節點移動速度越快，則網絡的拓撲結構變化越快。對基于 WiFi的自組織網絡而言，由于WiFi無線信號覆蓋的范圍較小，節點間的通信距離較短，因此，網絡拓撲結構的變化對于系統的影響較大。下面分析平均報文傳遞率、平均端到端時延和平均端到端吞吐量與節點移動速度的性能關系。

當節點移動速度的增大時，四種協議的報文傳遞率均出現下降的趨勢，如圖1所示。三種反應式路由算法AODV、DSR和LAR的報文傳遞率相差不大，而先應式路由算法OLSR的報文傳遞率明顯低于三種反應式路由算法，尤其是當移動速度大于5m/s時，OLSR的報文傳遞率下降迅速。這是因為，隨著節點移動速度的加快，網絡拓撲變化頻繁，OLSR作為先應式路由算法，其維護路由信息的開銷迅速增長，導致報文傳遞率的下降。

端到端的時延受節點移動速度影響。節點移動速度增大，時延亦隨著增加，如圖2所示。OLSR作為先應式路由，由于周期性地維護最新的路由信息，在報文傳遞時，無需重新尋由，因此，其端到端時延的性能指標優于其他三種反應式算法。反應式路由DSR和LAR的端到端時延隨移動速度的增長呈現明顯的增長趨勢。這是由于隨著節點移動速度的增大，網絡拓撲變化增快，反應式路由協議需不斷重新尋找路由及建立連接，從而導致報文傳輸的端到端時延增大。AODV雖然也是反應式路由，但它維護了到目的節點的多條路由，即具有冗余路由的特性，當網絡拓撲變化頻繁且原路由失效時，該算法可迅速切換至其他活躍路徑上的路由。該特性使得AODV算法較其他反應式路由在端到端時延性能上表現優異。需注意的是，LAR算法的端到端時延性能曲線呈現出不穩定增長的特征，這是由于LAR根據節點位置信息不斷變換查詢范圍所致。

圖1 平均報文傳遞率與移動速度的關系

圖2 平均端到端時延與移動速度的關系

端到端吞吐量隨著節點移動速度的增大而呈下降趨勢，如圖3所示。三種反應式路由算法的吞吐量性能優于先應式算法OLSR，這是因為作為先應式算法，為使得路由信息及時更新，OLSR需要周期性地向其他節點發送路由信息，導致路由開銷花費較大。在三種先應式路由算法中，LAR的性能略優于AODV和DSR，這是由于LAR利用地理位置信息，縮小了搜索范圍，尋由開銷更小。

圖3 平均吞吐量與移動速度的關系

1.2 包發送間隔的影響分析

網絡負載是評估算法性能的重要因素，本文用報文的發送間隔的變化模擬網絡負載的變化，對三個性能指標與報文發送間隔的關系進行了仿真，節點移動速度設為10m/s。

三種反應式路由算法AODV、DSR和LAR的平均報文傳遞率隨包發送間隔的增大呈現先減小后增大的趨勢，如圖4所示。網絡負載初始增大時，網絡逐漸變得擁塞，所以，報文傳遞率下降。當包發送間隔較小時，由于節點在持續移動，網絡拓撲在不停地變化，導致反應式路由算法需重新尋由。而當包發送間隔的增大到一定程度時，路由在兩次包發送間隔之間變化較小，使得之前的路由可被重用，因此，報文傳遞率曲線重新上揚，AODV的增長趨勢尤其明顯。隨著網絡負載的增大，先應式路由算法OLSR的維護路由的開銷持續增大，加劇了網絡負載的增長，報文傳遞率呈現下降趨勢。

隨網絡負載的增大，四種算法的端到端時延總體呈現上升趨勢，如圖5所示。其中，AODV和OLSR的延時明顯低于反應式路由LAR和DSR，這是由于OLSR為先應式路由，發送數據時無需重新尋由，而AODV則具有鏈路快速切換機制。

隨著網絡負載的增大，吞吐量總體呈現減小趨勢，如圖6所示。由于維護路由的開銷較大，OLSR的吞吐量較其他三種反應式路由算法小。三種反應式路由算法AODV、DSR和LAR的吞吐量性能相差不大，但當負荷持續變大時，AODV的吞吐量性能略優于其他兩種算法。

圖4 報文傳遞率與包發送間隔的關系

圖5 端到端時延與包發送間隔的關系

圖6 平均吞吐量與包發送間隔的關系曲線

從上述分析結果看，在基于WiFi的自組織網絡中，反應式路由的性能優于先應式路由的性能。由于WiFi節點間的通信距離有限，當節點處于移動速度狀態時，拓撲結構變化頻繁，路由失效的幾率變大，先應式路由算法維護路由的開銷也會增大，因此，反應式路由的性能更強大。而AODV協議由于具有鏈路快速連接機制以及快速切換至活躍路徑的特性，在高節點移動速度及高負載的網絡中性能優異，具有優良的吞吐量和報文傳遞率，更小的端到端延時，以及高穩定性。

2 分簇網絡路由算法

從上文的仿真結果看，AODV算法在基于WiFi的自組織網絡中性能較其他三種算法優異，但對于戰場應用環境，仍不滿足要求。首先，AODV算法是針對平面式拓撲結構而設計的，而在戰場環境下，存在按照部隊編制進行擴展的需求，對網絡的擴展性要求較高，因此，需要將路由算法設計為分層路由算法;再次，火控數據對端到端時延要求較高，一般要求控制在一百毫秒以內，而AODV路由算法在節點移動速度較高時，無法滿足該要求。為滿足戰場環境下的上述需求，結合AODV算法的優勢，本文引入建立分簇結構的思想，提出了一種新的分簇路由算法CRP(Cluster Route Protocol)。

該算法包括分簇算法和路由協議兩部分。分簇算法描述如下:

CRP對節點進行傳輸功率的判別，只有滿足一定傳輸功率的節點才能參與簇頭的選舉。簇頭選舉算法設計的原則為選擇節點密度大處的節點作為簇頭，綜合考慮節點度數以及與鄰居節點的距離和。對每個滿足功率約束的節點，進行綜合權值結算，選擇權值最小的節點作為簇頭。權值計算公式如下:

其中，Wi代表節點 i的權值，w(j=1，2，3)代表不同影響因素的權值系數;N為節點i的鄰居節點個數，D為該節點與其鄰居節點的距離和。從該權值判斷規則可知，若某節點的鄰居節點個數越多，與其鄰居節點距離越近，則其更適合成為簇頭。

網絡初始化流程如下:所有的節點廣播自己的ID，其輻射范圍內的節點收到此廣播后，記錄此ID，之后，兩者互發消息，告知對方節點自己的發射功率，通常發射功率的衰減與距離的四次方成正比，因此，通過對發射功率衰減的測量，可估算出兩節點間的距離。這樣，所有的節點均維護了其鄰居節點的ID以及它們之間的相對距離。此時，根據上文提出的分簇算法，每個節點進行權值計算，權值最小的節點成為簇頭。但是，簇不可無限制地增大，因為如果簇的節點過多，則分簇路由的性能得不到體現，會導致整個網絡吞吐量的降低。本文利用跳數限定簇的大小，簇頭與簇內節點之間的跳數必須小于兩跳。分簇結束后，簇內非簇頭節點需維護自己所在簇ID以及其簇頭節點的信息。

簇的維護流程如下:簇頭與簇內每個普通節點定期進行心跳包交互。當簇頭在一定時間段內未收到某節點的心跳包時，則認為該節點已離開該簇，將該節點從簇內成員列表中刪除;當收到新的節點的入網申請時，則判斷該節點是否滿足入簇條件，比如與簇頭節點是否兩跳內可達，該簇的節點數是否超出限制等，若滿足入簇條件，則將該節點加入本簇;若不滿足條件，則通知該節點繼續尋找新的簇頭，若尋找不到，則自立新簇。當移動的兩簇之間的距離小于等于某一規定要求，且滿足簇合并條件時，需對其進行合并。

CRP路由協議部分描述如下:

a.協議幀的結構與AODV路由協議的幀結構類似，只是在協議頭中新增2個bit，一個bit用于標識本節點的角色，即本節點是否為簇頭、普通節點或者網關節點，另一個bit用于標識節點所在簇的簇ID。因此，當傳輸的源節點和目的節點在同一個簇內時，則直接在簇內進行轉發;若源節點和目的節點不在同一個簇內，則通過簇頭節點或者網關節點進行轉發，以至到達目的簇中的目的節點。

b.當源節點需要和目的節點通信時，如果在路由表中可查詢到對應的路由時，不進行任何操作。當源節點需要和新的目的通信時，就會發起路由發現過程，通過廣播RREQ信息來查找相應路由。當這個RREQ到達目的節點本身，或者是一個擁有足夠新的到目的節點路由的中間節點時，路由確定。目的節點或中間節點通過原路返回一個RREP信息來向源節點確定路由的可用性。轉發RREQ的節點將根據RREQ是否設置了快速轉發標記來決定采用快速路由查找或與AODV相同的普通路由查找。快速路由查找是按簇ID和簇節點ID的方式實施的。如在規定的時間內未找到路由，再采用普通的路由查找方法。

c.AODV采用的是超時刪除路由機制，因此即使路由未失效，在超時時限后也將被刪除。CRP將路由超時刪除機制修改如下:若路由超過時限，則判斷路由是否有效，若有效，則此路由繼續保持;若無效，則刪除。

d.當鏈路破壞時，節點并不立即發送RERR給源節點，而由其下游節點嘗試進行局部路由修復。若局部路由可成功修復，則可將網絡的鏈路壞區局限在一個小的范圍內，避免了大規模的網絡重構，提高了網絡修復效率。如果路由局部修復不成功，再向源節點發送RERR信息。

e.該協議兼容AODV算法。當由于節點移動等原因，使得之前的簇結構遭到破壞，無法滿足數據傳輸要求時，則不再使用分簇結構，而是利用AODV的路由進行廣播，并在此過程中重新建簇。

針對平均報文傳遞率、平均端到端時延和平均吞吐量三個性能指標，本文選用OPNET仿真平臺分別對本文提出的CRP路由算法、AODV路由算法和經典的分簇路由協議ZRP［8，9］進行仿真和比較。節點移動方式選取組移動模型(Group Mobility Model)，節點個數為50個，節點移動速度從1m/s到25m/s，范圍是10km×10km的區域。MAC層采用IEEE802.11協議，網絡帶寬為5.5Mbps，每個數據包大小為500bytes。仿真結果如圖7所示。隨著節點移動速度及網絡負載的增大，CRP協議的平均包傳送率，平均端到端時延以及平均吞吐量三個性能均優于AODV算法。

隨著節點移動速度的增大，網絡的拓撲變化加快，導致需要頻繁的重新尋找路由，所以，協議的時延會增加，而CRP協議中的節點增加了快速轉發標記，使得路由查找的速度大為提高，從而能夠更好地適應高速移動的場景;并且，在路由修復方面由于路由能夠很快被修復，大大提高了準確率，從而減少了數據包的丟失;隨著網絡負載的增大，由于CRP協議采用了分簇結構，減少了節點移動對路由算法的影響和路由發現過程中的洪泛開銷，加速了路由的查找過程，增加了網絡吞吐量，緩解了網絡局部擁塞，保證了分組傳遞的成功進行。端到端時延降低了約30%，在節點移動速度為25m/s時，仍小于100ms，滿足了火控數據的傳輸要求。

經典分簇路由協議ZRP在簇內運行先應式路由協議，需要周期性的發送廣播來維護和更新路由表;簇間運行反應式路由協議。在節點移動速度較小時，網絡拓撲變化小，路由維持開銷小，且先應式路由協議可以快速地尋由，因此，ZRP算法的性能總體優于CRP算法。但隨著節點移動速度的加快，網絡拓撲變化頻繁，簇內先應式路由協議的網絡開銷迅速增大，此外，在進行簇間路由查找時，邊界節點收到路由請求無法回應后，就需要把請求向未查找過的簇轉發，勢必會產生大量的多播或廣播數據，網絡的運行效率降低，因此，ZRP算法的性能比CRP算法差。

圖7 AODV、CRP和ZRP性能比較

3 結束語

本文利用仿真平臺OPNET對基于WiFi的自組織網絡中的AODV、DSR、LAR和OLSR四種路由協議進行了仿真比較。通過對平均包傳送率，平均端到端時延以及平均吞吐量三個性能指標的綜合比較發現，AODV協議的性能優于其他三種算法。針對戰場環境下，車載自組網網絡擴展性以及火控數據傳輸時延的要求，基于AODV算法，本文提出了一種新的分簇自組網路由算法CRP，其分簇網絡結構的設計減少了節點移動對路由算法的影響和路由發現過程中的洪泛開銷;其快速轉發機制加速了尋由過程;其局部路由修復機制限制了鏈路壞區的擴展，提高了網絡的修復速度。實驗仿真結果證明了該算法的優越性。

［1］于宏毅，無線移動自組織網［M］.北京:人民郵電出版社，2005.

［2］E.Baeeelli，C.Perkins.Multi-hop Ad Hoc Wireless Communication［OL］.IETF Internet Draft，draft-baccelli-multi-hop-wirelesscommunication-05，2010.

［3］O’Reilly.802.11無線網絡權威指南［M］.南京:東南大學出版社，2007.

［4］Perkins C E，Bhagwat P.Highly Dynamic Destination-Sequenced Distance-Vector Routing(DSDV)for Mobile Computers［OL］.ACM SIGCOMM’94 1994.

［5］David B Johnson，David A Maltz，Hu Yih-Chun.The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks(DSR)［OL］.IETF Internet Draft draft-ietf-manet-dsr-09.txt，2003.

［6］Charles E Perkins，Elizabeth M Royer.Ad Hoc On-Demand Distance Vector Routing［C］.2ndIEEE Workshop on Mobile Systems and Applications，2006.

［7］Ko Young-Bae，Nitin H.Vaidya.Location-Aided Routing(LAR)in Mobile Ad Hoc Networks［J］.Wireless Networks，2000，(6):307-321.

［8］ZygmuntJ.Haas，MareR.Pearlman，Prinee Samar.The Zone Routing Protocol for Ad Hoc NetworkS［OL］.IETF Internet Draft，draft-ietf-manet-zone-zrp-04.txt，2002.

［9］肖迎杰，肖宗水，蘇繼斌，基于工ZRP的移動Ad Hoc分級網絡管理［J］.計算機工程，2009，35(13):114-116.