基于限制廣播域和節(jié)點剩余能量的按需路由算法研究

高媛

（徐州工業(yè)職業(yè)技術(shù)學(xué)院，江蘇徐州，221008）

基于限制廣播域和節(jié)點剩余能量的按需路由算法研究

高媛

（徐州工業(yè)職業(yè)技術(shù)學(xué)院，江蘇徐州，221008）

按需路由協(xié)議AODV的路由發(fā)現(xiàn)使用洪泛方式的擴(kuò)散法，導(dǎo)致網(wǎng)絡(luò)超負(fù)荷運(yùn)行和擁塞，而且在選擇轉(zhuǎn)發(fā)路由時，總是選擇最少跳數(shù)的路由，造成無線傳感網(wǎng)絡(luò)中節(jié)點能量不均，減少網(wǎng)絡(luò)壽命。本文提出了AODV-DE算法，該算法引入廣播域的概念，限制RREQ分組的轉(zhuǎn)發(fā)范圍，同時避免使用剩余能量低的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)分組，選擇路由路徑時選擇總剩余能量最多的路徑進(jìn)行信息的傳送。仿真結(jié)果表明，AODV-DE協(xié)議在路由開銷、網(wǎng)絡(luò)壽命和端到端的延遲這三個方面表現(xiàn)出了優(yōu)勢。

AODV；廣播域；剩余能量

0 引言

AODV協(xié)議是一種經(jīng)典按需路由協(xié)議，算法簡單且擴(kuò)展性好[1]。當(dāng)源節(jié)點需要與目標(biāo)節(jié)點進(jìn)行通信而路由表中沒有相應(yīng)表項時開始路由發(fā)現(xiàn)的過程，AODV的路由發(fā)現(xiàn)本質(zhì)上還是使用洪泛方式的擴(kuò)散法[2]，當(dāng)網(wǎng)絡(luò)規(guī)模增大，節(jié)點數(shù)較多時，RREQ等路由控制報文迅速增加，導(dǎo)致網(wǎng)絡(luò)超負(fù)荷運(yùn)行和擁塞，大大降低了網(wǎng)絡(luò)的性能[3]。另外，AODV協(xié)議在選擇轉(zhuǎn)發(fā)路由時，總是選擇最少跳數(shù)的路由[4]。這就使得最短路徑中的某些節(jié)點由于頻繁使用而提前耗盡能量，造成無線傳感網(wǎng)絡(luò)中節(jié)點能量的不均衡。

針對上述不足，本文提出一種改進(jìn)協(xié)議AODV-DE（routing algorithm based on restricted broadcast domain and node surplus energy），該協(xié)議綜合考慮RREQ分組的廣播范圍以及路由節(jié)點的剩余能量。在進(jìn)行RREQ分組的轉(zhuǎn)發(fā)時，引入廣播域的概念，限制RREQ分組的轉(zhuǎn)發(fā)范圍；為了使路由節(jié)點的能量能夠均衡地消耗，AODV-DE協(xié)議避免使用剩余能量低的節(jié)點進(jìn)行轉(zhuǎn)發(fā)數(shù)據(jù)，而是選擇發(fā)現(xiàn)的路由路徑中所有節(jié)點剩余總能量最多的路徑進(jìn)行信息的傳送，從而延長網(wǎng)絡(luò)壽命。實驗表明，該改進(jìn)協(xié)議在路由開銷、網(wǎng)絡(luò)壽命方面都有所改善。

1 AODV-DE路由算法

1.1 基于廣播域的改進(jìn)

為了限制RREQ消息的廣播范圍，在RREQ消息的幀結(jié)構(gòu)中增加了節(jié)點的坐標(biāo)信息，用來存儲RREQ發(fā)送到本節(jié)點的前一跳節(jié)點的坐標(biāo)，在泛洪的過程中節(jié)點的坐標(biāo)信息會擴(kuò)散到整個網(wǎng)絡(luò)。當(dāng)源節(jié)點進(jìn)行一次新的路由發(fā)現(xiàn)時，源節(jié)點會按照改進(jìn)的RREQ消息結(jié)構(gòu)產(chǎn)生一個攜帶有本節(jié)點坐標(biāo)信息的RREQ消息，并對此RREQ消息進(jìn)行廣播。在廣播時每個中間節(jié)點要進(jìn)行判斷，在廣播域中繼續(xù)轉(zhuǎn)發(fā)RREQ消息，避免向?qū)REQ消息轉(zhuǎn)發(fā)至本節(jié)點的上一跳節(jié)點重復(fù)轉(zhuǎn)發(fā)。

1.2 廣播域模型的建立

在廣播的過程中，如圖1所示，當(dāng)源節(jié)點0想與節(jié)點6通信，而它的路由表中沒有相應(yīng)的路由信息，節(jié)點0將發(fā)起路由發(fā)現(xiàn)過程。節(jié)點0向周圍節(jié)點廣播RREQ分組（圖a），節(jié)點1、2、3收到RREQ分組后建立到節(jié)點0的反向路由，并繼續(xù)向周圍節(jié)點廣播RREQ分組（圖b）。從圖c中可以看到，節(jié)點4在收到了來自節(jié)點1、2、3的RREQ分組后，開始向周圍節(jié)點廣播RREQ分組，它周圍的節(jié)點有1、2、3、5、6，其中，節(jié)點1、2、3又重復(fù)收到了RREQ分組，這樣就使網(wǎng)絡(luò)中路由控制報文數(shù)量太多，有可能造成網(wǎng)絡(luò)擁塞，同時降低了網(wǎng)絡(luò)性能。為避免此種情況的發(fā)生，需確定合理有效的廣播域，即控制RREQ分組的轉(zhuǎn)發(fā)范圍，使其只能發(fā)送給未向本節(jié)點轉(zhuǎn)發(fā)過此分組的節(jié)點。

以節(jié)點4為例，如圖2，為使節(jié)點4不再將RREQ分組重復(fù)發(fā)送給節(jié)點1、2、3，節(jié)點1、2、3共同確定的灰色區(qū)域為禁止廣播區(qū)域，將此區(qū)域在數(shù)學(xué)模型中表示：A、B、C、D四點分別代表節(jié)點1、4、3、2。

圖1 AODV路由建立過程

圖2 節(jié)點4 RREQ的廣播過程

圖3 抽象出的數(shù)學(xué)模型

由圖3，假設(shè)A點坐標(biāo)為（ax，ay），B點坐標(biāo)為（bx，by），C點坐標(biāo)為（cx，cy），D點坐標(biāo)為（dx,dy），

首先比較A、C、D三點橫坐標(biāo)的大小，以此確定最大夾角。

由圖3得知，xC＞xD＞xA

，所以，A點與C點間夾角θ最大。

計算角θ的大小：

廣播域的角度γ可以通過下式求得：

擴(kuò)展至一般情況：

設(shè)將RREQ數(shù)據(jù)分組轉(zhuǎn)發(fā)給M節(jié)點的上一跳節(jié)點的集合為S[n]。當(dāng)集合中只有一個上一跳節(jié)點時，則M節(jié)點就只向集合中節(jié)點之外的節(jié)點轉(zhuǎn)發(fā)；當(dāng)集合中的上一跳節(jié)點大于一個時，首先比較這些節(jié)點的橫坐標(biāo)大小，取橫坐標(biāo)最大以及最小的節(jié)點，與本節(jié)點確定的夾角為θ，廣播域的角度即為γ=2π-θ，臨界邊即為確定γ角的兩節(jié)點各自與本節(jié)點的向量。

1.3 基于能量均衡的改進(jìn)

為了使路由節(jié)點的能量能夠均衡地消耗，本方案在LEAR協(xié)議[5]的能量門限值思想基礎(chǔ)上，再綜合考慮整條路由路徑節(jié)點剩余總能量，以延長網(wǎng)絡(luò)壽命。

算法描述如下：當(dāng)一個源節(jié)點想要到達(dá)一個目標(biāo)節(jié)點時，需在廣播域內(nèi)進(jìn)行路由發(fā)現(xiàn)，當(dāng)中間節(jié)點收到RREQ數(shù)據(jù)分組時，先將自己的剩余能量與預(yù)先規(guī)定的門限值相比較，如果剩余能量高于門限值，那么此節(jié)點就可在廣播域內(nèi)廣播請求到所有鄰節(jié)點；反之，則該節(jié)點拒絕RREQ包,并忽略請求。當(dāng)目標(biāo)節(jié)點收到第一個RREQ包時，并不馬上按此路徑回復(fù)RREP分組，而是等待少許時間，待后續(xù)的RREQ分組也都到達(dá)時，比較所有路由路徑中節(jié)點剩余的總能量大小，選取剩余能量最大的一條路徑回復(fù)RREP分組。為實現(xiàn)此算法，需對原來AODV協(xié)議RREQ分組格式進(jìn)行改進(jìn)，添加節(jié)點剩余能量。改進(jìn)后的RREQ分組格式如圖4所示。

圖4 改進(jìn)后的RREQ分組格式

2 AODV-DE協(xié)議的仿真與分析

2.1 仿真環(huán)境的參數(shù)設(shè)置

我們在NS仿真環(huán)境下進(jìn)行仿真[6]，模擬人員定位系統(tǒng)的實際應(yīng)用，設(shè)置仿真環(huán)境為400m×80m的方形區(qū)域。路由節(jié)點通信范圍設(shè)定為20m，路由節(jié)點的個數(shù)從80個一直增加到140個，每次增加10個路由節(jié)點。在仿真過程中節(jié)點或者靜止或者移動，移動時以1m/s的速度向某一目標(biāo)點勻速移動，到達(dá)目標(biāo)節(jié)點后停留一段時間，然后繼續(xù)向隨機(jī)目標(biāo)點移動，反復(fù)以上過程直至仿真結(jié)束。設(shè)最大移動速度為2m/s，停留時間為30s。

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

在仿真中加入AODV協(xié)議進(jìn)行對比。

圖5 隨節(jié)點數(shù)目增大路由開銷的變化

圖6 節(jié)點生存時間

（1）路由開銷分析：由圖5可以看出，在源節(jié)點數(shù)相同的情況下，兩種協(xié)議的路由開銷都隨著路由節(jié)點數(shù)的增加而增加，但是，AODV-DE協(xié)議的路由開銷要明顯低于AODV協(xié)議，這是因為，在進(jìn)行路由發(fā)現(xiàn)的時候，AODV-DE協(xié)議的RREQ分組只向廣播域內(nèi)轉(zhuǎn)發(fā)，減少了不必要的控制分組。

（2）節(jié)點的存活時間分析：設(shè)置每個節(jié)點的初始能量設(shè)為10J，節(jié)點的發(fā)送功率為0.660W，節(jié)點的接收功率為0.395W，初始能量較小，發(fā)射功率和接收功率較大，可在較短時間內(nèi)對比出兩種協(xié)議的性能。仿真時間為100s，節(jié)點數(shù)為100。仿真結(jié)果如圖6所示，AODV-DE節(jié)點的存活時間明顯要比AODV的長，這是因為對節(jié)點能量進(jìn)行了控制。原協(xié)議節(jié)點是分散死亡的，而AODV-DE協(xié)議的節(jié)點死亡時間較為統(tǒng)一，AODV-DE在進(jìn)行路由發(fā)現(xiàn)時避免使用剩余能量低的節(jié)點，固定的門限值限制了能量的減少，使大部分節(jié)點的剩余能量可以穩(wěn)定在門限值附近，節(jié)點消耗的能量都比較均衡。

圖7 隨節(jié)點數(shù)目增大端到端的延遲的變化

（3）端到端的延遲分析：由圖7可知，隨著路由節(jié)點數(shù)目的增加，AODV-DE協(xié)議比AODV協(xié)議的端到端的延遲要長，這是因為為了使路由節(jié)點能量的消耗達(dá)到均衡，AODV-DE協(xié)議要比較節(jié)點剩余能量和門限值的大小以及路徑節(jié)點總剩余能量的大小，而且如果所有的路徑中都有中間節(jié)點的剩余能量低于門限值，還需要調(diào)低門限值，重新進(jìn)行路徑的發(fā)現(xiàn)；而AODV協(xié)議不考慮能量問題，直接進(jìn)行路徑的發(fā)現(xiàn)。故AODV-DE協(xié)議比AODV協(xié)議的端到端的延遲要長。由此可以看出，AODV-DE協(xié)議網(wǎng)絡(luò)壽命的延長是以增長的端到端的延遲為代價的。

3 小結(jié)

本文提出一種按需路由協(xié)議的設(shè)計方案，此方案繼承了AODV協(xié)議的優(yōu)點：只在需要傳輸數(shù)據(jù)時才開始路由發(fā)現(xiàn)；去除了AODV協(xié)議的缺點：提出廣播域的概念，有效地控制了控制分組的轉(zhuǎn)發(fā)范圍，避免了盲目泛洪的路由發(fā)現(xiàn)方式所導(dǎo)致的網(wǎng)絡(luò)超負(fù)荷運(yùn)行和擁塞，節(jié)省了能量。并且在能量均衡方面作出了詳細(xì)的設(shè)計，延長了網(wǎng)絡(luò)的壽命。此算法可以使移動分站的電池能量均衡地消耗，避免了頻繁地更換電池，雖然端到端的延遲有所增加，但是增加的并不多，都是毫秒數(shù)量級的，在實際應(yīng)用中，基本不會有影響。

[1] 無線自組織網(wǎng)絡(luò)按需路由協(xié)議研究[J].盧山,宋志群,周凌宇,劉倩楠.無線電工程.2015(11).

[2]AODV路由協(xié)議的研究和改進(jìn)[J].何綿祿,褚偉,劉輝舟.計算機(jī)工程.2015(01).

[3]基于AODV的多度量無線路由算法研究[J].鄭碩,胡壽偉,陳佳品,李振波.半導(dǎo)體光電.2016(06).

[4]一種基于AODV的均衡優(yōu)化協(xié)議[J].賈皓強(qiáng),趙富康,楊振潔,張濤.信息通信.2017(03).

[5]于宏毅.無線移動自組織網(wǎng)[M].北京：人民郵電出版社,2005：138，176-182，267-268，277-280.

[6]謝佳，徐山峰.AODV、AOMDV和AODV-UU路由協(xié)議性能仿真與分析[J].中國電子科學(xué)研究學(xué)院學(xué)報，2011,6（6）：592-596.

Research on on-demand routing algorithm based on restricted broadcast domain and node residual energy

Gao Yuan
（Xuzhou College of Industrial Technology，Xuzhou Jiangsu，221008）

This paper presents the AODV-DE algorithm, the proposed algorithm introduces the concept of broadcast domains, RREQ forwarding, and avoid using the low residual energy of nodes forwarding the data packet transmission, routing path selection path of total residual energy of most information. Simulation results show that the AODV-DE protocol has advantages in three aspects, routing overhead, network lifetime and end-to-end delay.

AODV; broadcast domain; residual energy

江蘇省高校自然科學(xué)研究面上項目(編號:16KJB480006)