黃　煒　李　強　陳媛媛

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

?

220D無線自組網(wǎng)路由拓撲更新分析與優(yōu)化

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

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

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

無線自組網(wǎng)路由協(xié)議拓撲更新220D

0　引　言

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

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

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

1　220D路由拓撲更新分析

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

1.1最小網(wǎng)絡(luò)拓撲更新時間間隔

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

1.2源定向路由

源定向中繼方式為一種簡單地從源節(jié)點到目的節(jié)點的非動態(tài)的中繼過程。源節(jié)點需要發(fā)送分組時，首先從自己的路由表中查找、計算出經(jīng)過內(nèi)部網(wǎng)到達目的節(jié)點的路徑，然后將路由信息編碼進內(nèi)部網(wǎng)報頭，這就是表驅(qū)動路由協(xié)議的特點。其優(yōu)點是節(jié)點發(fā)送報文時可以獲得準確度較高的路由，能避免路由環(huán)路的發(fā)生，時延較小。

1.3拓撲更新

220D網(wǎng)絡(luò)依靠節(jié)點間積極地交換拓撲信息來保證網(wǎng)絡(luò)的正常通信。為此，220D協(xié)議專門定義了其拓撲更新數(shù)據(jù)結(jié)構(gòu)，如圖1所示。其中節(jié)點1的狀態(tài)字節(jié)描述的是節(jié)點1的前驅(qū)節(jié)點和源節(jié)點之間的鏈路狀態(tài)。

圖1　拓撲更新數(shù)據(jù)結(jié)構(gòu)

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

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

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

假設(shè)兩相鄰兩節(jié)點A與C的路由樹如圖2所示。如果節(jié)點A與C之間交換完整的路由樹，節(jié)點A就會把節(jié)點C的路由樹保存到其自己的路由樹里，如圖3所示。如果按照220D規(guī)定的交互規(guī)則，A與C之間只交換完整路由樹的較小副本，那么交互后節(jié)點A的路由樹如圖4所示?？梢钥闯鱿噜徆?jié)點之間交換稀疏路由樹可以減少節(jié)點存儲的路由樹的數(shù)據(jù)量。

圖2　節(jié)點A與C的路由樹

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

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

2　基于NS2的220D路由協(xié)議擴展

2.1NS2仿真器介紹

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

2.2220D路由協(xié)議擴展

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

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代表生成和消耗網(wǎng)絡(luò)層數(shù)據(jù)分組的端點，同時被用于實現(xiàn)不同網(wǎng)絡(luò)層次的協(xié)議[4]，其主要功能是在源節(jié)點與目的節(jié)點之間創(chuàng)建一條端到端的連接。其他路由協(xié)議Agent類的實現(xiàn)要繼承父Agent類。220D路由協(xié)議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路由協(xié)議性能分析

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

3.1仿真場景

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

3.2CBR發(fā)送速率對220D網(wǎng)絡(luò)性能影響

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

圖5　cbr發(fā)送速率對網(wǎng)絡(luò)分組傳輸成功率的影響

從圖5中可以看出，cbr發(fā)送速率不變時，網(wǎng)絡(luò)分組傳輸成功率大致隨節(jié)點停留時間的增加而增大；節(jié)點停留時間不變時，網(wǎng)絡(luò)分組傳輸成功率大致隨cbr發(fā)送速率的增大而減少。

4　220D路由拓撲更新優(yōu)化

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

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

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

圖6　優(yōu)化前后網(wǎng)絡(luò)分組傳輸成功率對比圖

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

5　結(jié)　語

本文主要在分析220D無線自組網(wǎng)路由拓撲更新的基礎(chǔ)上，針對拓撲更新參數(shù)“最小網(wǎng)絡(luò)拓撲更新時間間隔”設(shè)置不合適時，會影響網(wǎng)絡(luò)性能的問題，提出了一種自適應(yīng)改變最小時間間隔的220D路由拓撲更新優(yōu)化方法?；贜S2仿真平臺對優(yōu)化前后的網(wǎng)絡(luò)進行了仿真對比，結(jié)果顯示該方法可以改善220D網(wǎng)絡(luò)性能。本文可為研究其他無線自組網(wǎng)路由拓撲更新或220D路由協(xié)議提供一定的參考價值。

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

[2] 劉軍,孫茜,王英梅.支持網(wǎng)絡(luò)編碼的認知無線自組網(wǎng)拓撲控制算法[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與網(wǎng)絡(luò)模擬[M].北京:人民郵電出版社,2007.

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

[8] 牛秋娜,王美琴,王英龍.基于NS-2的MANET路由協(xié)議仿真及性能評估[J].計算機應(yīng)用研究,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。黃煒，教授，主研領(lǐng)域：移動通信。李強，碩士。陳媛媛，碩士。

TP391.9

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