窄帶無線網絡中基于WRP路由算法的優化設計與仿真

孫小薇，邱宏燕，李勇

窄帶無線網絡中基于WRP路由算法的優化設計與仿真

孫小薇，邱宏燕，李勇

（中國電子科技集團公司第七研究所，廣東 廣州 510310）

針對窄帶無線自組網絡環境，設計了一種基于WRP的改進路由算法。該路由算法沿用WRP的倒數第二跳節點避免環路現象，特別是采用了報文中攜帶校驗值取代更新消息的序列號、ACK標志等復雜操作，并提出簡化的HELLO報文來維護與鄰居節點的連通性。根據設定的窄帶無線網絡參數配置，使用OPNET仿真工具對該路由協議進行了仿真和評估。

窄帶無線網絡 路由協議 WRP OPNET

1 引言

窄帶無線網絡中由于帶寬窄，網絡數據傳輸率很低，不同移動速度和帶寬等特殊環境因素對路由算法的選取至關重要，因為它對提高特定環境中無線自組網的通信性能有很大作用。窄帶無線自組網絡中使用的路由算法要求占據較小的開銷達到降低傳輸延時、提高包到達率、提高網絡傳輸性能的目標。而在無線自組網中，沒有最優的算法，網絡規模、節點特性的不同，都會使路由算法的表現千差萬別。針對特定的窄帶無線網絡，考慮設計一種基于WRP（Wireless Routing Protocol，無線路由協議）的路由算法，對該路由算法存在的問題進行優化和改進。根據特定的窄帶無線網絡環境，基于OPNET構建優化后的WRP路由協議，以仿真結果說明路由協議的有效性，并對其關鍵性能進行比較。

2 WRP路由算法優化設計

2.1 WRP協議

WRP是主動式距離矢量的協議，它利用去往目標節點的路徑跳數和相應路徑的倒數第二跳節點信息，基于PFA（Path Finding Aglorithm，路徑發現算法）計算無環路的目標路徑。WRP通過ACK機制實現可靠傳輸，維護動態信息包括距離表、路由表、消息重發表等。其中消息重發表包括多個重發表項，每個表項包括更新消息的序號、重發技術、ACK標志、更新消息列表等。WRP通過周期性地發送HELLO報文來探測鄰居間的連通性信息。每個節點通過其鄰居節點的SST（Shortpath Spanning Tree，最短路徑生成樹）生成自己的SST后，再向鄰節點傳遞更新消息。WRP算法的特點是當檢測到任意相鄰節點變化時，則檢查保存的所有相鄰節點的距離表，進行新的路徑計算并根據每條路徑記錄的倒數第二跳信息消除環路現象，具有較快的收斂性，缺點是開銷較大。

2.2 改進的WRP協議

在特定的窄帶無線網絡中，節點帶寬、計算等資源受限，需要路由算法簡潔有效、開銷低。考慮到適用的特定環境的節點在拓撲構建完成后拓撲變化不劇烈，可長時間地保持在穩定狀態。因此在保證WRP的快速消除環路算法具有較快收斂性的特點下，取消ACK機制，改進HELLO機制，采用校驗和來保證路由數據的完整性和準確性。改進HELLO機制，在穩定狀態時，發送簡化的HELLO報文維持鄰居間的連通性，改進WRP協議為A-WRP協議。

（1）校驗和機制

校驗和機制采用的數據項是每個節點的路由表數據項的排列組合，按照路由表項節點號的順序排列作為輸入計算得出校驗和的值。該值在發送路由報文時攜帶在報文頭部，用于收方節點比較自身保存的鄰居距離表計算得出的校驗和是否和對方鄰居發送的校驗和一致，如果相同，則認為和鄰居達到路由的同步；如果不同，則判斷為不同步，需要對不同步的節點進行同步請求。進行同步請求只需要增加一種短的同步請求報文發送到目標節點，目標節點收到報文后則將路由表項通過路由報文發送出去。源節點可以快速地更新該鄰居節點的距離表，并更新計算自身的路由表。該機制增加了一種短報文，但是無需采用序號、重發、ACK標志、消息重發表等復雜處理過程。

A-WRP路由協議的每種報文的報文頭都會攜帶校驗和值，如圖1所示。發送端的校驗和計算是根據發端的路由表按照一定規則排序而成的數據，而收端則是根據查找距離表中發送節點的路由表按照同樣規則排序后進行計算的結果。若一致，則說明收端保存的該節點的路由表是和發端一致的；若不一致，則觸發請求路由同步的短報文將其發送出去。節點若收到路由同步請求報文，發現有鄰居節點請求發送路由表項信息，則使用“完全轉存”路由更新報文進行發送，即通過校驗和機制使報文確定被接收到。

圖1 校驗和機制示意圖

（2）簡化HELLO機制

A-WRP主動式路由協議在網絡拓撲處于穩定狀態時，只發送HELLO分組。此時節點處于相對靜態的狀態，即網絡拓撲無變化，相鄰節點間的路由信息同步后，發送的簡化HELLO報文中不再攜帶有鄰居信息，只需本節點自身信息和校驗值即可，可大大節省穩定狀態下的路由報文開銷。

HELLO報文分為兩種，一種是完全HELLO報文，另一種是簡化HELLO報文。發送哪種報文由HELLO報文當前時刻的HELLO報文發送狀態來決定，HELLO報文發送狀態如圖2所示，它有對應的兩種狀態。

HELLO_init：初始態HELLO；

HELLO_stable：穩定態HELLO。

系統初始化時，將HELLO報文發送狀態定為HELLO_init。若在定時器T1時間內只收到雙向鄰居的HELLO報文，則跳轉到HELLO_stable狀態。

處于HELLO_stable跳轉到HELLO_init的條件是：若收到新鄰居的HELLO包，且該鄰居的鄰居表內不含有本節點，則跳轉到HELLO_init狀態；或者收到非HELLO報文。

圖2 HELLO報文發送狀態機

（3）快速收斂機制

改進后的WRP協議采用了路由的增量更新機制，節點根據路由表項的變化程度決定是否進行“增量更新”路由報文的發送。如果鏈路中斷導致拓撲發生變化，A-WRP路由協議在一段時間內不能收到鄰居的任何節點信息，推測出鏈路斷。該路由算法中，鏈路斷的度量值設定為最大值0xff，并通過路由更新報文攜帶該信息發送出去，并且度量值為最大值的路由表項觸發立即發送的“增量更新”報文立即發送出去。上述過程可以在較短的時間內完成，鏈路的變化及路由的更新將通告在網絡中的各個節點。

3 基于OPNET的仿真平臺設計

3.1 窄帶無線網絡

在特定環境下的窄帶無線移動自組網的網絡帶寬比較小，數據傳輸率較低。以典型的超短波電臺的信道帶寬9.6kb/s為例，設置了基本通信網絡參數，并在此基礎上，根據應用的具體需求，同時對網絡節點相關參數進行了適當的配置，其它無線網絡參數如表1所示。

表1 窄帶無線網絡參數

針對特定的窄帶無線網絡，構建OPNET仿真平臺下的網絡拓撲如圖3所示。16個節點的多跳窄帶無線自組網根據表1的參數，需要對全部節點進行配置。

圖3 仿真網絡拓撲圖

3.2 基于OPNET的平臺設計

A-WRP路由協議的實現需要嵌入到IP模塊中，OPNET系統自帶的MANET模塊位于IP模塊進程模型ip_dispatch的子進程manet_mgr中，系統自帶的根據RFC標準實現的有DSR、AODV、TORA、GRP等協議。DSR、AODV、TORA、GRP等都是以manet_mgr的子進程形式來實現具體協議細節的。同樣的A-WRP模塊也可以在MANET模塊下添加一個新的子進程來實現路由協議，如圖4所示：

圖4 manet_mgr子進程下增加路由協議子進程awrp_rte

awrp_rte與manet_mgr進程接口部分處理完成后，即可設計awrp_rte路由協議模型的具體細節，如圖5所示，在進程模型中：

（1）只有來自父進程的激發（傳遞數據包）和自己定義的自中斷兩種事件需要處理。

（2）不論向上層還是下層發送數據，都需要激發父進程，通過父進程轉發，數據包是激發的參數。

圖5 awrp_rte進程模塊

接收數據包處理步驟包含在wait狀態機執行以下包處理過程：

（1）底層來的路由控制包：IP會判斷該包是否來自底層，并將對應路由協議的控制包發到對應的子進程進行處理。

（2）底層來的數據業務包：MAC層先將包發到IP進行IP路由處理。1）若不是本機的數據業務包且在IP路由表中有路由地址的話，則將包處理后通過輸出接口output interface通過無線通信鏈路發送到另外一臺目的節點處。2）若不是本機的數據業務包且IP路由表中找不到路由地址，則將該包發到manet_mgr中對應的wrp_rte路由子進程進行查找路由處理。若找到路由，則將該包發給IP轉發出去，若沒有找到路由，丟棄該包。3）若是本機的數據業務，則通過IP層直接將包發給應用層。

（3）高層來的數據業務包：高層將業務包發到IP進行IP路由處理。1）若在IP路由表能找到相應路由，則將包通過輸出接口output interface發送到底層。2）若在IP路由表中找不到對應路由，則將包發到manet_ mgr對應的awrp_rte路由子進程進行查找路由處理，若找到路由，則將包發給IP轉發出去，若沒有找到路由，丟棄該包。

4 仿真結果與分析

仿真中利用OPNET的統計功能，增加相關local和global統計量，例如各種報文的發送統計、MAC層幀擁塞情況統計等，并可以生成excel數據報表對路由協議占據的帶寬開銷進行統計，對路由協議的性能進行詳細的分析。

4.1 固定拓撲結構

基于圖3的固定拓撲結構，A-WRP協議包括了校驗和機制，避免了ACK機制的復雜性，簡化節點的處理方式，所有報文都無需對方反饋ACK標志，節點可以節約大量緩存空間。圖6為A-WRP四種報文的發送個數統計示意圖，可見通過增加兩種報文的少量的發送，可取代ACK機制的復雜處理過程。

圖6 A-WRP四種報文發送統計顯示

在校驗和機制的基礎上，為進一步降低路由算法的帶寬占用率，針對網絡拓撲的特定應用場景，采用簡化的HELLO協議。圖7對比了A-WRP協議采用簡化HELLO的前后對比，為global統計變量HELLO報文的發送總bits。根據統計結果顯示，采用簡化的HELLO協議后，HELLO報文占據的開銷降低了55.2%。

圖7 HELLO報文發送全局統計

圖8為校驗和機制中增加的同步請求短報文的發送情況，可見短報文只在網絡收斂的初始階段發送，網絡平穩后，是不需要發送該短報文的。網絡平穩后，只發送周期較長簡化的HELLO報文，以降低路由報文開銷。

圖8 同步請求報文發送全部統計

查看統計量，計算的路由全網收斂的時間和路由開銷如表2所示。其中，初始態路由開銷代表仿真初始路由開始全網收斂達到所有節點形成完整路由表后計算所得。穩定路由開銷則為路由表收斂完成后，只需要周期性地發送HELLO包后的開銷。

表2 全網收斂時間和路由開銷

可見路由初建，HELLO包和路由更新包比較多，所以開銷比較大。待路由建立完成后，只需要周期性地發送HELLO包，開銷較小，目前配置穩定狀態后HELLO周期為25s。

4.2 移動拓撲結構

設置移動拓撲場景（如圖3所示），節點16以60km/s的移動速度沿途中所示方向移動，直到移出其它節點的天線覆蓋范圍。在移動過程中，因節點16逐漸與其它節點鏈路斷開，并不會立即與所有節點都斷開鄰居關系，故路由收斂處于振蕩過程中，直到節點16與最近的節點都無法進行通信。查看路由協議的報文發送情況，如圖9所示，與固定場景的圖6對比，可見移動場景下，在第6分鐘時，還有除HELLO報文外的其它三種報文在完成路由表項的發送處理過程。

路由重收斂時間的計算方式為，從IP路由表中刪除某條目的地址的路由，重新計算出該目的地址的路由并加入IP路由表的時間。查看仿真結果，得出該場景下的路由重收斂時間和開銷如表3所示：

表3 重收斂和開銷

可見，新建路由由于HELLO包和路由更新包都比較多，包也比較大，所以開銷較大。但重收斂路由時，因為A-WRP采用的增量更新方式，只發送路由表中有變化的路由條目給周圍鄰居，所以開銷比較小。因為各個節點發送HELLO包的時間不同，在重新收斂過程中會存在鄰居節點丟失的時間不同，因此各次斷鏈后重建路由的收斂時間也會不同的情況。

圖9 移動拓撲四種報文發送統計顯示

5 結束語

改進的WRP路由協議采用校驗和機制的路由協議可避免ACK機制復雜的處理流程，結合簡化HELLO報文和快速收斂等機制，能更好地在窄帶無線網絡中進行應用。通過大型仿真軟件OPNET模擬路由協議流程，對報文發送處理、路由開銷、收斂時間等關鍵仿真結果進行分析，改進后的路由協議減小了帶寬占用率，該協議的設計為實際設備開發路由算法提供了理論指導和數據支持。

[1] 王金龍. Ad Hoc移動無線網絡[M]. 北京: 國防工業出版社, 2004.

[2] 高嵩. OPNET Modeler仿真建模大解密[M]. 北京: 電子工業出版社, 2010.

[3] 鄭少仁. Ad Hoc網絡技術[M]. 北京: 人民郵電出版社, 2005.

[4] Murthy S, Barcia Lama Aceves J. An Efficient Routing Protocol (WRP) for Wireless Networks[J]. ACM Mobile Networks and Applications Journal, 1996(2): 183-193.

[5] Perkins C E. Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computer[J]. Conference on Communications Architectures, 1994(4): 234-244.

[6] 張晶晶. 基于OPNET的無線自組網路由協議研究[D].大連: 大連海事大學, 2008.

[7] 文小琪. 基于OPNET的無線Mesh網絡路由協議的研究與仿真[D]. 西安: 西安電子科技大學, 2010.

[8] 張旭. 無線自組織網絡路由算法及相關技術研究[D]. 長春: 吉林大學, 2013.

[9] 歐陽峰,劉強. 一種基于OPNET的多媒體業務半實物仿真平臺[J]. 電視技術, 2016,40(7): 76-81.

[10] 盧詩堯,曾桂根. 一種基于Ad Hoc網絡的協作MAC方案[J]. 電視技術, 2015,39(15): 64-68.★

Optimization Design and Simulation of WRP Routing Algorithm for Narrow-Band Wireless Network

SUN Xiaowei, QIU Hongyan, LI Yong
(T h e 7t h Re s e a r c h I n s t i t u t e o f C h i n a E l e c t r o n i c T e c h n o l o g y G r o u p C o r p o r a t i o n, G u a n g z h o u 510310, C h i n a)

An improved routing algorithm based on WRP was designed according to narrow-band wireless network. The improved algorithm keeps the penult node in WRP to avoid the loop. Especially, it carries the check value in the packets to replace the complex operations such as series number and ACK fl ag and uses the simple HELLO message to maintain the connectivity with the neighbor nodes. According to the parameter con fi gurations of narrow-band wireless network, OPNET is used to simulate and evaluate the improved routing algorithm.

narrow-band wireless network routing protocol WRP OPNET

孫小薇：工程師，碩士研究生畢業于桂林電子科技大學信息與通信學院，現任職于中國電子科技集團公司第七研究所，主要研究方向為路由與交換技術、軍用通信系統仿真。

邱宏燕：高級工程師，碩士研究生畢業于華南理工大學電子與信息學院，現任職于中國電子科技集團公司第七研究所，主要研究方向為無線網絡的總體設計、原型系統和仿真評估等。

李勇：高級工程師，學士畢業于哈爾濱工業大學通信工程專業，現任職于中國電子科技集團公司第七研究所，主要研究方向為通信系統和網絡設計。

10.3969/j.i s s n.1006-1010.2017.12.015

T P 316.2

A

1006-1010(2017)12-0075-06

孫小薇,邱宏燕,李勇. 窄帶無線網絡中基于WRP路由算法的優化設計與仿真[J]. 移動通信, 2017,41(12): 75-80.

2017-03-09

責任編輯：劉妙 l i u m i a o@m b c o m.c n