窄帶無線網(wǎng)絡(luò)中基于WRP路由算法的優(yōu)化設(shè)計與仿真

孫小薇，邱宏燕，李勇

窄帶無線網(wǎng)絡(luò)中基于WRP路由算法的優(yōu)化設(shè)計與仿真

孫小薇，邱宏燕，李勇

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

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

窄帶無線網(wǎng)絡(luò) 路由協(xié)議 WRP OPNET

1 引言

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

2 WRP路由算法優(yōu)化設(shè)計

2.1 WRP協(xié)議

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

2.2 改進(jìn)的WRP協(xié)議

在特定的窄帶無線網(wǎng)絡(luò)中，節(jié)點帶寬、計算等資源受限，需要路由算法簡潔有效、開銷低。考慮到適用的特定環(huán)境的節(jié)點在拓?fù)錁?gòu)建完成后拓?fù)渥兓粍×遥砷L時間地保持在穩(wěn)定狀態(tài)。因此在保證WRP的快速消除環(huán)路算法具有較快收斂性的特點下，取消ACK機制，改進(jìn)HELLO機制，采用校驗和來保證路由數(shù)據(jù)的完整性和準(zhǔn)確性。改進(jìn)HELLO機制，在穩(wěn)定狀態(tài)時，發(fā)送簡化的HELLO報文維持鄰居間的連通性，改進(jìn)WRP協(xié)議為A-WRP協(xié)議。

（1）校驗和機制

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

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

圖1 校驗和機制示意圖

（2）簡化HELLO機制

A-WRP主動式路由協(xié)議在網(wǎng)絡(luò)拓?fù)涮幱诜€(wěn)定狀態(tài)時，只發(fā)送HELLO分組。此時節(jié)點處于相對靜態(tài)的狀態(tài)，即網(wǎng)絡(luò)拓?fù)錈o變化，相鄰節(jié)點間的路由信息同步后，發(fā)送的簡化HELLO報文中不再攜帶有鄰居信息，只需本節(jié)點自身信息和校驗值即可，可大大節(jié)省穩(wěn)定狀態(tài)下的路由報文開銷。

HELLO報文分為兩種，一種是完全HELLO報文，另一種是簡化HELLO報文。發(fā)送哪種報文由HELLO報文當(dāng)前時刻的HELLO報文發(fā)送狀態(tài)來決定，HELLO報文發(fā)送狀態(tài)如圖2所示，它有對應(yīng)的兩種狀態(tài)。

HELLO_init：初始態(tài)HELLO；

HELLO_stable：穩(wěn)定態(tài)HELLO。

系統(tǒng)初始化時，將HELLO報文發(fā)送狀態(tài)定為HELLO_init。若在定時器T1時間內(nèi)只收到雙向鄰居的HELLO報文，則跳轉(zhuǎn)到HELLO_stable狀態(tài)。

處于HELLO_stable跳轉(zhuǎn)到HELLO_init的條件是：若收到新鄰居的HELLO包，且該鄰居的鄰居表內(nèi)不含有本節(jié)點，則跳轉(zhuǎn)到HELLO_init狀態(tài)；或者收到非HELLO報文。

圖2 HELLO報文發(fā)送狀態(tài)機

（3）快速收斂機制

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

3 基于OPNET的仿真平臺設(shè)計

3.1 窄帶無線網(wǎng)絡(luò)

在特定環(huán)境下的窄帶無線移動自組網(wǎng)的網(wǎng)絡(luò)帶寬比較小，數(shù)據(jù)傳輸率較低。以典型的超短波電臺的信道帶寬9.6kb/s為例，設(shè)置了基本通信網(wǎng)絡(luò)參數(shù)，并在此基礎(chǔ)上，根據(jù)應(yīng)用的具體需求，同時對網(wǎng)絡(luò)節(jié)點相關(guān)參數(shù)進(jìn)行了適當(dāng)?shù)呐渲茫渌鼰o線網(wǎng)絡(luò)參數(shù)如表1所示。

表1 窄帶無線網(wǎng)絡(luò)參數(shù)

針對特定的窄帶無線網(wǎng)絡(luò)，構(gòu)建OPNET仿真平臺下的網(wǎng)絡(luò)拓?fù)淙鐖D3所示。16個節(jié)點的多跳窄帶無線自組網(wǎng)根據(jù)表1的參數(shù)，需要對全部節(jié)點進(jìn)行配置。

圖3 仿真網(wǎng)絡(luò)拓?fù)鋱D

3.2 基于OPNET的平臺設(shè)計

A-WRP路由協(xié)議的實現(xiàn)需要嵌入到IP模塊中，OPNET系統(tǒng)自帶的MANET模塊位于IP模塊進(jìn)程模型ip_dispatch的子進(jìn)程manet_mgr中，系統(tǒng)自帶的根據(jù)RFC標(biāo)準(zhǔn)實現(xiàn)的有DSR、AODV、TORA、GRP等協(xié)議。DSR、AODV、TORA、GRP等都是以manet_mgr的子進(jìn)程形式來實現(xiàn)具體協(xié)議細(xì)節(jié)的。同樣的A-WRP模塊也可以在MANET模塊下添加一個新的子進(jìn)程來實現(xiàn)路由協(xié)議，如圖4所示：

圖4 manet_mgr子進(jìn)程下增加路由協(xié)議子進(jìn)程awrp_rte

awrp_rte與manet_mgr進(jìn)程接口部分處理完成后，即可設(shè)計awrp_rte路由協(xié)議模型的具體細(xì)節(jié)，如圖5所示，在進(jìn)程模型中：

（1）只有來自父進(jìn)程的激發(fā)（傳遞數(shù)據(jù)包）和自己定義的自中斷兩種事件需要處理。

（2）不論向上層還是下層發(fā)送數(shù)據(jù)，都需要激發(fā)父進(jìn)程，通過父進(jìn)程轉(zhuǎn)發(fā)，數(shù)據(jù)包是激發(fā)的參數(shù)。

圖5 awrp_rte進(jìn)程模塊

接收數(shù)據(jù)包處理步驟包含在wait狀態(tài)機執(zhí)行以下包處理過程：

（1）底層來的路由控制包：IP會判斷該包是否來自底層，并將對應(yīng)路由協(xié)議的控制包發(fā)到對應(yīng)的子進(jìn)程進(jìn)行處理。

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

（3）高層來的數(shù)據(jù)業(yè)務(wù)包：高層將業(yè)務(wù)包發(fā)到IP進(jìn)行IP路由處理。1）若在IP路由表能找到相應(yīng)路由，則將包通過輸出接口output interface發(fā)送到底層。2）若在IP路由表中找不到對應(yīng)路由，則將包發(fā)到manet_ mgr對應(yīng)的awrp_rte路由子進(jìn)程進(jìn)行查找路由處理，若找到路由，則將包發(fā)給IP轉(zhuǎn)發(fā)出去，若沒有找到路由，丟棄該包。

4 仿真結(jié)果與分析

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

4.1 固定拓?fù)浣Y(jié)構(gòu)

基于圖3的固定拓?fù)浣Y(jié)構(gòu)，A-WRP協(xié)議包括了校驗和機制，避免了ACK機制的復(fù)雜性，簡化節(jié)點的處理方式，所有報文都無需對方反饋ACK標(biāo)志，節(jié)點可以節(jié)約大量緩存空間。圖6為A-WRP四種報文的發(fā)送個數(shù)統(tǒng)計示意圖，可見通過增加兩種報文的少量的發(fā)送，可取代ACK機制的復(fù)雜處理過程。

圖6 A-WRP四種報文發(fā)送統(tǒng)計顯示

在校驗和機制的基礎(chǔ)上，為進(jìn)一步降低路由算法的帶寬占用率，針對網(wǎng)絡(luò)拓?fù)涞奶囟☉?yīng)用場景，采用簡化的HELLO協(xié)議。圖7對比了A-WRP協(xié)議采用簡化HELLO的前后對比，為global統(tǒng)計變量HELLO報文的發(fā)送總bits。根據(jù)統(tǒng)計結(jié)果顯示，采用簡化的HELLO協(xié)議后，HELLO報文占據(jù)的開銷降低了55.2%。

圖7 HELLO報文發(fā)送全局統(tǒng)計

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

圖8 同步請求報文發(fā)送全部統(tǒng)計

查看統(tǒng)計量，計算的路由全網(wǎng)收斂的時間和路由開銷如表2所示。其中，初始態(tài)路由開銷代表仿真初始路由開始全網(wǎng)收斂達(dá)到所有節(jié)點形成完整路由表后計算所得。穩(wěn)定路由開銷則為路由表收斂完成后，只需要周期性地發(fā)送HELLO包后的開銷。

表2 全網(wǎng)收斂時間和路由開銷

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

4.2 移動拓?fù)浣Y(jié)構(gòu)

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

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

表3 重收斂和開銷

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

圖9 移動拓?fù)渌姆N報文發(fā)送統(tǒng)計顯示

5 結(jié)束語

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

[1] 王金龍. Ad Hoc移動無線網(wǎng)絡(luò)[M]. 北京: 國防工業(yè)出版社, 2004.

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

[3] 鄭少仁. Ad Hoc網(wǎng)絡(luò)技術(shù)[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的無線自組網(wǎng)路由協(xié)議研究[D].大連: 大連海事大學(xué), 2008.

[7] 文小琪. 基于OPNET的無線Mesh網(wǎng)絡(luò)路由協(xié)議的研究與仿真[D]. 西安: 西安電子科技大學(xué), 2010.

[8] 張旭. 無線自組織網(wǎng)絡(luò)路由算法及相關(guān)技術(shù)研究[D]. 長春: 吉林大學(xué), 2013.

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

[10] 盧詩堯,曾桂根. 一種基于Ad Hoc網(wǎng)絡(luò)的協(xié)作MAC方案[J]. 電視技術(shù), 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

孫小薇：工程師，碩士研究生畢業(yè)于桂林電子科技大學(xué)信息與通信學(xué)院，現(xiàn)任職于中國電子科技集團(tuán)公司第七研究所，主要研究方向為路由與交換技術(shù)、軍用通信系統(tǒng)仿真。

邱宏燕：高級工程師，碩士研究生畢業(yè)于華南理工大學(xué)電子與信息學(xué)院，現(xiàn)任職于中國電子科技集團(tuán)公司第七研究所，主要研究方向為無線網(wǎng)絡(luò)的總體設(shè)計、原型系統(tǒng)和仿真評估等。

李勇：高級工程師，學(xué)士畢業(yè)于哈爾濱工業(yè)大學(xué)通信工程專業(yè)，現(xiàn)任職于中國電子科技集團(tuán)公司第七研究所，主要研究方向為通信系統(tǒng)和網(wǎng)絡(luò)設(shè)計。

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

T P 316.2

A

1006-1010(2017)12-0075-06

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

2017-03-09

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