220D無線自組網路由拓撲更新分析與優化

黃　煒　李　強　陳媛媛

1(電子科技大學通信與信息工程學院　四川 成都 611731)2(通信網信息傳輸和分發技術國家重點實驗室　河北 石家莊 050000)

?

220D無線自組網路由拓撲更新分析與優化

黃煒1,2李強1陳媛媛1

1(電子科技大學通信與信息工程學院四川 成都 611731)2(通信網信息傳輸和分發技術國家重點實驗室河北 石家莊 050000)

拓撲更新是無線自組網路由協議的重要組成部分，是影響網絡性能的關鍵因素。220D無線自組網路由協議規定其節點在每個最小時間間隔內最多發送一次拓撲更新消息。針對最小時間間隔值設置不合理時，會影響網絡性能的問題，提出一種自適應改變最小時間間隔值的路由拓撲更新優化方法，仿真結果顯示該方法可以改善網絡性能。

無線自組網路由協議拓撲更新220D

0　引　言

路由拓撲更新是設計無線自組織網絡時的重要考慮因素[1,2]。由于頻繁變化的無線自組織網拓撲結構需要有效的路由協議支持，所以對無線自組網路由協議拓撲更新規則的研究是很有必要的。文獻[3]分析了路由拓撲更新策略對MANET路由協議性能的影響。文獻[4]分析了AODV協議在不同節點移動速度下的路由性能。

MIL-STD-188-220D協議標準(簡稱220D協議)是無線自組網絡技術的典型應用成果。它是美軍CNR(戰斗網無線電臺)的標準的最新版，我國高端軍用和民用電臺設計時也參考了220系列協議。因此，對220D無線自組網路由拓撲更新的分析與優化具有廣泛的意義。

220D路由協議采用的是源路由選擇算法，使用稀疏路由樹來交換拓撲結構信息，并定義了“最小網絡拓撲更新時間間隔”(簡稱最小時間間隔)來防止節點過于頻繁地發送拓撲更新消息，以節約無線頻率資源。但當“最小網絡拓撲更新時間間隔”設置較大時，會使拓撲更新消息得不到及時發送；設置較小時，則使拓撲更新消息與數據分組競爭無線信道導致數據因碰撞而丟失，進而影響網絡性能。針對此問題，本文提出一種自適應改變最小時間間隔的路由拓撲更新優化方法。仿真結果顯示該方法可以改善220D及同類自組織網絡性能。

1　220D路由拓撲更新分析

220D無線自組網協議采用的是源定向路由選擇算法，節點入網時就要維護一張到網內其他節點的路由表，由事件觸發拓撲更新。每個節點周期性地向鄰居節點廣播拓撲更新包，用于交互拓撲信息。

1.1最小網絡拓撲更新時間間隔

為了防止網絡拓撲劇烈變化時拓撲信息交換過于頻繁，減小路由對無線信道的競爭，220D協議圍為0～255，且只能取整數，單位為分鐘。220D規定拓撲更新消息在每個最小時間間隔內發送不得超過一次，拓撲更新請求消息在每MIN_UPDATE_PER/2內最多發送一次。將其置0則可以禁止拓撲更新消息的發送與傳輸，即使網絡中某個節點不移動也不能將其MIN_UPDATE_PER設置為0。因為當其檢測到其他節點移動導致鏈路變化時也要發送拓撲更新消息。

1.2源定向路由

源定向中繼方式為一種簡單地從源節點到目的節點的非動態的中繼過程。源節點需要發送分組時，首先從自己的路由表中查找、計算出經過內部網到達目的節點的路徑，然后將路由信息編碼進內部網報頭，這就是表驅動路由協議的特點。其優點是節點發送報文時可以獲得準確度較高的路由，能避免路由環路的發生，時延較小。

1.3拓撲更新

220D網絡依靠節點間積極地交換拓撲信息來保證網絡的正常通信。為此，220D協議專門定義了其拓撲更新數據結構，如圖1所示。其中節點1的狀態字節描述的是節點1的前驅節點和源節點之間的鏈路狀態。

圖1　拓撲更新數據結構

如果網絡在拓撲更新時，交換的是完整路由表，就會產生數據量很大的拓撲更新包，交互時就會占用很大的帶寬，不適用于資源有限的adhoc網絡。因此，220D協議規定，只在相鄰兩個節點之間傳遞完整路由樹的較小副本，即稀疏路由樹。220D協議根據以下規則刪除節點間的重復路徑：

1) 只保留從根節點到其他節點的最短路徑；

2) 根節點到另一節點之間長度相同的路徑，最多保留兩條。

假設兩相鄰兩節點A與C的路由樹如圖2所示。如果節點A與C之間交換完整的路由樹，節點A就會把節點C的路由樹保存到其自己的路由樹里，如圖3所示。如果按照220D規定的交互規則，A與C之間只交換完整路由樹的較小副本，那么交互后節點A的路由樹如圖4所示。可以看出相鄰節點之間交換稀疏路由樹可以減少節點存儲的路由樹的數據量。

圖2　節點A與C的路由樹

圖3　節點A的包括冗余路徑的路由樹　圖4　節點A的稀疏路由樹

220D規定網絡拓撲更新由以下條件觸發，采用全網通播地址專門發送。① 節點A檢測到一條失敗的鏈路；② 節點A檢測到一條新的鏈路；③ 節點A檢測到一條鏈路質量發送變化的鏈路；④ 節點A收到了一條改變了其稀疏路由樹的拓撲更新消息；⑤ 節點A改變了其靜默模式，并希望通告全網這一變化；⑥ 節點A改變了其中繼能力；⑦ 節點A收到拓撲更新請求。

2　基于NS2的220D路由協議擴展

2.1NS2仿真器介紹

NS2(NetworkSimulator,version2)，是一款開源的、離散事件驅動的網絡環境模擬器，主要用于解決網絡研究方面的問題[6]。NS模擬分兩個層次：一是只需編寫Otcl腳本，利用NS已有的網絡模塊實現模擬；另一層次是基于C++和Otcl編程，對NS進行擴展，添加自己要模擬的模塊[7]。

2.2220D路由協議擴展

由于NS2現有仿真庫中不包括220D路由協議模塊，需要添加C++類以實現220D路由協議。本文在添加220D路由協議的編程過程中參考了NS2下的DSDV和DSR路由協議源代碼。為了減少拓撲更新的數據量，220D定義了稀疏路由樹，類設計代碼如下所示：

classspa_table{

public:

spa_table() {bzero(this,sizeof(spa_table));}

nsaddr_tdst;

//Destinationaddress

nsaddr_tpre_dst;

//Nodepredecessoraddress

uinthop;

//hops

uintcost;

boolnr;

boolquiet;

//Quietmode

};

NS2中的Agent代表生成和消耗網絡層數據分組的端點，同時被用于實現不同網絡層次的協議[4]，其主要功能是在源節點與目的節點之間創建一條端到端的連接。其他路由協議Agent類的實現要繼承父Agent類。220D路由協議Agent類部分代碼如下所示：

class220D_Agent:publicAgent{

public:

220D_Agent();

protected:

nsaddr_tmyaddr_;

//Nodeaddress

size_tMin_Update_Per;

//MIN_UPDATE_PER

virtualvoidrecv(Packet*,Handler*);

voidneedTriggeredUpdate(spa_table*prte,Timet);

//Triggeredupdate

Packet*makeUpdate(int&periodic);

voidupdateRoute(spa_table*old_stab,spa_table*new_stab);

};

3　220D路由協議性能分析

為了判斷和衡量某種路由協議的性能高低，需要通過定性和定量的評估指標來度量[8]。本節主要仿真220D網絡cbr流發送速率隨著節點停留時間的增大時對網絡分組傳輸成功率的影響。節點停留時間能表征網絡拓撲變化的快慢，節點停留時間越短，網絡拓撲變化越快，節點停留時間較長時，網絡拓撲變化較慢。分組傳輸成功率指目的節點成功接收到的分組數與發送節點發送的分組數的比值。當節點來不及更新變化較快的網絡拓撲時，或者網絡負載較大分組之間競爭無線信道時，分組就會丟失，所以分組傳輸成功率能反映路由協議性能的好壞。

3.1仿真場景

由于本文主要研究220D路由協議，所以在仿真時采用NS2缺省的其他各層協議。設置了如下的仿真場景：在800m×800m區域內均勻放置20個節點，業務是cbr流，每包512字節，網絡中節點的最大移動速度為20m/s，移動方向隨機，節點停留時間手動設置，仿真時間為600s。

3.2CBR發送速率對220D網絡性能影響

cbr流發送速率(單位為kbps)可以表征網絡負載，是影響網絡性能的重要因素。cbr發送速率越大，說明網絡負載越大，網絡負載過大時，會導致分組在MAC層碰撞而丟失，使網絡性能下降。圖5為cbr流發送速率分別取4、8、12和16kpbs時，網絡的分組傳輸成功率情況。

圖5　cbr發送速率對網絡分組傳輸成功率的影響

從圖5中可以看出，cbr發送速率不變時，網絡分組傳輸成功率大致隨節點停留時間的增加而增大；節點停留時間不變時，網絡分組傳輸成功率大致隨cbr發送速率的增大而減少。

4　220D路由拓撲更新優化

220D協議標準定義了最小時間間隔來減小拓撲更新頻率，但當最小時間間隔取值較小時，拓撲更新發送過于頻繁，和cbr流競爭無線信道，導致用戶數據分組因碰撞而丟失。而當其值取值太大時，節點就不能及時獲取網絡拓撲結構，使用過期的路由信息發送或傳遞分組，會使分組不可達，進而降低了220D網絡性能。對于真實的無線自組織網絡，特別是在戰術環境中，節點移動速度和網絡負載都不確定，無法根據這兩項參數設置合適的MIN_UPDATE_PER值。因此，如何在節點移動速度和網絡負載動態、無規律變化的情況下，既能及時更新網絡拓撲信息，又不會占用大量的網絡資源導致分組沖突，是220D路由協議需要解決的問題。

針對以上問題，本文提出了一種通過自適應改變最小時間間隔來提高網絡性能的方法。對于優化前的網絡，當節點需要發送拓撲更新信息時，要等待當前的MIN_UPDATE_PER時間結束后才能發送。本文做如下優化：在每個節點上設定一個隊列緩沖區，節點需要拓撲更新時，首先檢查更改了的拓撲更新信息是否涉及正在使用的路由信息；如果是，則不需要等待當前最小時間間隔結束，而是立刻發送拓撲更新；否則將拓撲更新包緩存到緩沖區，等待新的最小時間間隔周期到來時，節點從緩存區取出第一條拓撲信息發送出去。當緩存區里的拓撲更新包大于兩條時，節點就自動將當前最小時間間隔值減1，即增大拓撲更新頻率；相反，如果緩存區里拓撲更新包為0條時，說明節點沒有檢測到鏈路變化，就不需要廣播拓撲更新包，節點就自動將當前最小時間間隔值加1。

對上述的優化，本文進行了如下仿真和比較。 對優化前的網絡將最小時間間隔值(圖中用per表示)設置為1和3分鐘(per=1或3min)；優化后的網絡最小時間間隔自適應改變，優化前后的網絡cbr流發送速率都為8kbps，仿真并統計優化前后的網絡分組傳輸成功率，仿真結果如圖6所示。

圖6　優化前后網絡分組傳輸成功率對比圖

從仿真結果可以看出，對優化前的網絡，拓撲變化較快時，最小時間間隔為1min時的網絡性能優于最小時間間隔為3min時的；拓撲變化較慢時，最小時間間隔為3min時的網絡性能稍優于最小時間間隔為1min時的。優化后的網絡分組傳輸功率跟優化前的相比較高，即網絡性能更好，且優化后的網絡分組傳輸成功率上下波動較小，即網絡性能更加穩定。

5　結　語

本文主要在分析220D無線自組網路由拓撲更新的基礎上，針對拓撲更新參數“最小網絡拓撲更新時間間隔”設置不合適時，會影響網絡性能的問題，提出了一種自適應改變最小時間間隔的220D路由拓撲更新優化方法。基于NS2仿真平臺對優化前后的網絡進行了仿真對比，結果顯示該方法可以改善220D網絡性能。本文可為研究其他無線自組網路由拓撲更新或220D路由協議提供一定的參考價值。

[1] 周鑫.自組網中一種基于能量均衡的選擇性洪泛路由算法[J].計算機應用與軟件,2014,31(7):101-104.

[2] 劉軍,孫茜,王英梅.支持網絡編碼的認知無線自組網拓撲控制算法[J].通信學報,2013,34(5):136-142.

[3]MohapatraS,KanungoP.PerformanceanalysisofAODV,DSR,OLSRandDSDVRoutingProtocolsusingNS2Simulator[J].ProcediaEngineering,2012,30(7):69-76.

[4]IsmailZ,HassanR.AperformancestudyofvariousmobilityspeedonAODVroutingprotocolinhomogeneousandheterogeneousMANET[C]//Communications(APCC),2011 17thAsia-PacificConferenceon.IEEE,2011:637-642.

[5]MIL-STD-188-220D.DepartmentofDefenseInterfaceStandardDigitalMessageTransferDEVICESubsystems[S].2005.

[6] 于斌,孫斌,溫暖,等.NS2與網絡模擬[M].北京:人民郵電出版社,2007.

[7]LiBaiping,ZhangXiaoqin.RsearchofdevelopmentinwirelesssensornetworkroutingprotocolsbasedonNS2[C]//ElectronicandMechanicalEngineeringandInformationTechnology(EMEIT),2011:1913-1916.

[8] 牛秋娜,王美琴,王英龍.基于NS-2的MANET路由協議仿真及性能評估[J].計算機應用研究,2006,23(9):242-246.

ANALYSISANDOPTIMISATIONOF220DMOBILEADHOCROUTINGTOPOLOGYUPDATES

HuangWei1,2LiQiang1ChenYuanyuan1

1(School of Communication and Information Engineering,University of Electronic Science and Technology of China,Chengdu 611731,Sichuan,China)2(Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory,Shijiazhuang 050000,Hebei,China)

Topologyupdatesisanimportantcompositionofmobileadhocnetworkroutingprotocol,andakeyfactorthataffectstheadhocnetworkperformance. 220DroutingprotocolsetsthatthetopologyupdatesinformationofnodesshouldnotbetransmittedmoreoftenthanonceeveryMIN_UPDATE_PER.SoinappropriateMIN_UPDATE_PERmayhaveanimpactonthenetworkperformance.Aimingatthisproblem,thispaperproposesaroutingtopologyupdateoptimisationmethodwhichadaptivelychangesMIN_UPDATE_PER.Resultsofsimulationshowthatthismethodcanimprovethenetworkperformance.

MobileadhocnetworkRoutingprotocolTopologyupdates220D

2014-09-10。黃煒，教授，主研領域：移動通信。李強，碩士。陳媛媛，碩士。

TP391.9

ADOI:10.3969/j.issn.1000-386x.2016.03.035