一種改進(jìn)跨層擁塞控制的無線傳感網(wǎng)絡(luò)蟻群路由算法

胡國偉

（寧波職業(yè)技術(shù)學(xué)院，浙江 寧波 315800）

1 問題提出

蟻群算法因其具有的自組織、分布式和自動尋優(yōu)特性，尤其適合應(yīng)用于同樣具有動態(tài)、自組織特點(diǎn)的無線傳感網(wǎng)絡(luò) （Wireless Sensor Networks，簡稱WSNs），近年來引起中外研究人員的廣泛興趣。文獻(xiàn)[1]提出了一種典型的基于蟻群算法的能量高效路由協(xié)議IEEABR，IEEABR 通過使用固定大小的螞蟻代理以及把能量和跳數(shù)這兩個度量引入到信息素更新機(jī)制中，來建立能量有效的路徑，達(dá)到減少在路由發(fā)現(xiàn)時的通信開銷來延長網(wǎng)絡(luò)的壽命的目標(biāo)。文獻(xiàn)[2]針對IEEABR 蟻群路由算法能量分布不夠均勻問題，提出了改進(jìn)的網(wǎng)絡(luò)均衡算法EEIABR。但是IEEABR 和EEIABR 路由算法都未考慮網(wǎng)絡(luò)擁塞的問題，而網(wǎng)絡(luò)擁塞容易引起丟包，降低網(wǎng)絡(luò)性能。本文針對上述路由算法的不足，提出了一種改進(jìn)跨層擁塞控制的WSNs 蟻群路由算法CCIEEABR。主要做出如下改進(jìn)：（1）利用跨層聯(lián)合優(yōu)化機(jī)制，允許層間交互，多層共享數(shù)據(jù)及本地信息，從整體上提高網(wǎng)絡(luò)性能；（2）針對單一緩存占用率或隊(duì)列長度無法精確度量網(wǎng)絡(luò)擁塞的不足，引人指數(shù)加權(quán)移動平均法計(jì)算節(jié)點(diǎn)平均隊(duì)列長度；（3）當(dāng)檢測到節(jié)點(diǎn)發(fā)生擁塞時，提出一種帶懲罰機(jī)制的信息素更新機(jī)制，調(diào)整節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包的概率，有效緩解網(wǎng)絡(luò)擁塞。

2 改進(jìn)的網(wǎng)絡(luò)跨層擁塞控制算法

蟻群路由算法采用啟發(fā)式策略來選擇最優(yōu)下一跳節(jié)點(diǎn)，大量報(bào)文會被轉(zhuǎn)發(fā)至那些信息素值較高的節(jié)點(diǎn)，當(dāng)報(bào)文接收速率遠(yuǎn)大于報(bào)文離開速率時，這些節(jié)點(diǎn)的剩余緩存空間不斷減小，直至溢出，這就形成了節(jié)點(diǎn)的擁塞。本文提出的改進(jìn)擁塞控制機(jī)制由兩部分組成：擁塞檢測和擁塞解除。擁塞檢測是擁塞解除的前提。擁塞控制算法的具體實(shí)施如下。

2.1 CCIEEABR 跨層優(yōu)化機(jī)制

跨層優(yōu)化機(jī)制是以Media Access Control，即802.11MAC 為媒介，網(wǎng)絡(luò)層可以實(shí)施獲取數(shù)據(jù)鏈路層（logic link layer，簡稱LL）的緩沖隊(duì)列信息。首先通過添加和修改MAC 層的函數(shù)，達(dá)到在MAC 層中可以調(diào)用LL 層中隊(duì)列長度值；其次，在保留MAC層和路由層結(jié)構(gòu)分離的基礎(chǔ)上，允許路由層訪問MAC 層從LL 層中獲得的緩存隊(duì)列長度信息，通過MAC 層和路由層的信息交互、協(xié)同優(yōu)化網(wǎng)絡(luò)性能[3]。該機(jī)制具有簡單高效、隊(duì)列信息實(shí)時性高等優(yōu)點(diǎn)。

2.2 擁塞檢測機(jī)制

當(dāng)網(wǎng)絡(luò)出現(xiàn)擁塞后，傳感器節(jié)點(diǎn)采取合理方法及時檢測到網(wǎng)絡(luò)的隊(duì)列緩存狀況，準(zhǔn)確判斷是否出現(xiàn)網(wǎng)絡(luò)擁塞是實(shí)現(xiàn)擁塞解除的前提。本研究基于對傳感器節(jié)點(diǎn)緩沖隊(duì)列長度的判斷來檢測，不占用額外的網(wǎng)絡(luò)資源，簡單快鍵。為了準(zhǔn)確度量節(jié)點(diǎn)當(dāng)前緩存隊(duì)列長度信息，引人指數(shù)加權(quán)移動平均（EWMA）算法來更新節(jié)點(diǎn)的平均隊(duì)列長度。

式中：avgnew為節(jié)點(diǎn)緩沖區(qū)更新后的平均隊(duì)列長度；為節(jié)點(diǎn)自己保存的平均隊(duì)列長度；q_w 為節(jié)點(diǎn)緩存占用率，0≤q_w≤1，表示某一時刻節(jié)點(diǎn)數(shù)據(jù)緩存已被使用的比例；cur_que 為當(dāng)前節(jié)點(diǎn)的隊(duì)列長度的采樣值，即

其中，q_w 值越小說明節(jié)點(diǎn)的緩存被占用的就越少。Q0表示節(jié)點(diǎn)允許的最大緩存隊(duì)列長度，網(wǎng)絡(luò)中每個節(jié)點(diǎn)的最大緩存一致。由式（2）可知，q_w 與cur_que的值成正比。如果當(dāng)前節(jié)點(diǎn)的緩存占用率很高，即q_w 值很大，在更新avgnew的過程中的比重較小，即avgnew的值更多的依賴于當(dāng)前隊(duì)列長度cur_que。反之，q_w 很小，avgnew更多的取決于因此avgnew能夠直觀的反映當(dāng)前節(jié)點(diǎn)的擁塞狀況。

2.3 防擁塞控制機(jī)制

在算法的搜索過程中，若所有螞蟻都采用最優(yōu)路徑的進(jìn)行路徑搜索，網(wǎng)絡(luò)中的部分節(jié)點(diǎn)就會由于螞蟻數(shù)量過多而導(dǎo)致節(jié)點(diǎn)擁塞現(xiàn)象的出現(xiàn)，使得大量的數(shù)據(jù)只通過少量的節(jié)點(diǎn)進(jìn)行傳輸，這必然會導(dǎo)致網(wǎng)絡(luò)出現(xiàn)擁塞。為了解決上述問題，本文預(yù)先設(shè)置一個節(jié)點(diǎn)緩沖隊(duì)列長度閥值Thr，當(dāng)avgnew＞Thr時，則認(rèn)定為節(jié)點(diǎn)擁塞現(xiàn)象的發(fā)生，需要對當(dāng)前節(jié)點(diǎn)引人懲罰機(jī)制。即對文獻(xiàn)[1]中的信息素?fù)]發(fā)式（3）進(jìn)行修正：

其中μ 為懲罰因子。這樣處理的好處是可以提前預(yù)測擁塞節(jié)點(diǎn)，加強(qiáng)算法對最優(yōu)路徑以外路徑進(jìn)行搜索，便于緩解最優(yōu)路徑的負(fù)載壓力，實(shí)現(xiàn)流量的分散，減緩擁塞狀態(tài)。

3 仿真實(shí)驗(yàn)及結(jié)果分析

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

本文采用NS2.35 環(huán)境構(gòu)建無線傳感器網(wǎng)絡(luò)的模擬環(huán)境，在1100 m×1100 m 的區(qū)域內(nèi)隨機(jī)部署80個傳感器節(jié)點(diǎn)（包含1 個Sink 節(jié)點(diǎn)），其通信范圍為250 m。源節(jié)點(diǎn)由25 個發(fā)送CBR 流節(jié)點(diǎn)組成，每個包的大小為512bytes，數(shù)據(jù)包的發(fā)包速率為5byte/s。仿真時間設(shè)置為100 s。設(shè)置初始條件α=1，β=1，C=20J，ρ=0.1，Q0=50，Thr={38，40，42}。從網(wǎng)絡(luò)的丟包率、端到端平均時延以及吞吐量方面，將提出的CIEEABR 路由算法與IEEABR 路由算法進(jìn)行性能比較和分析。

3.2 仿真結(jié)果

3.2.1 分組丟包率

分組丟包率是是網(wǎng)絡(luò)丟棄的數(shù)據(jù)包數(shù)目與源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包數(shù)據(jù)之比，反映了網(wǎng)絡(luò)的可靠性，分組丟包率越低，網(wǎng)絡(luò)可靠性越高。本研究分別選取3組不同的隊(duì)列擁塞檢測閥值系數(shù)的CIEEABR 路由算法與IEEABR 路由算法進(jìn)行比較。由圖1可知，不同閥值系數(shù)下，本研究算法所測得的丟包率始終低于IEEABR 算法，由于IEEABR 路由算法缺乏擁塞機(jī)制，會由于最優(yōu)路徑節(jié)點(diǎn)數(shù)據(jù)傳輸過于集中而出現(xiàn)擁塞現(xiàn)象，從而出現(xiàn)了大量的丟包。而本文提出的防擁塞懲罰機(jī)制能夠緩解最優(yōu)路徑上節(jié)點(diǎn)的負(fù)載壓力，將一部分?jǐn)?shù)據(jù)轉(zhuǎn)發(fā)壓力依概率轉(zhuǎn)移到次優(yōu)路徑節(jié)點(diǎn)，減少了丟包現(xiàn)象。

圖1 網(wǎng)絡(luò)丟包率

圖2 平均端到端時

3.2.2 平均端到端時延

平均端到端時延是指數(shù)據(jù)包從源節(jié)點(diǎn)成功到達(dá)目的節(jié)點(diǎn)對應(yīng)的投遞時延之和與數(shù)據(jù)包數(shù)量的比值。由圖2可知，隨著網(wǎng)絡(luò)仿真時間的增加，CIEEABR 算法在3 組不同閥值系數(shù)下測得的平均端到端時延均小于IEEABR，平均端到端時延分別下降了18%，21%，20%。分析其主要原因有以下兩點(diǎn)：（1） CIEEABR 路由算法在螞蟻搜素最優(yōu)路徑中考慮了節(jié)點(diǎn)的緩存占用率，最大化地降低了數(shù)據(jù)包的排隊(duì)時延；（2）通過網(wǎng)絡(luò)擁塞懲罰機(jī)制，能夠有效緩解最優(yōu)路徑節(jié)點(diǎn)的網(wǎng)絡(luò)擁塞，從而減少了網(wǎng)絡(luò)擁塞緩解的時間。

3.2.3 網(wǎng)絡(luò)吞吐量

網(wǎng)絡(luò)吞吐量是單位時間內(nèi)sink 節(jié)點(diǎn)接收到的數(shù)據(jù)包數(shù)量。由圖3可知，本文提出的算法在不同閥值系數(shù)下，相比于IEEABR 算法能夠獲得較好的網(wǎng)絡(luò)吞吐量，這是因?yàn)閾砣刂频穆酚赡軌颢@得較高的數(shù)據(jù)成功傳輸概率。從而使得CIEEABR 算法節(jié)點(diǎn)成功接收的數(shù)據(jù)包數(shù)量顯著增加。

圖3 網(wǎng)絡(luò)吞吐量

4 結(jié)束語

本文基于能量高效蟻群路由算法（IEEABR），提出了一種改進(jìn)跨層擁塞控制蟻群路由算法。實(shí)現(xiàn)了網(wǎng)絡(luò)的擁塞檢測和擁塞緩解。仿真結(jié)果表明，該算法在數(shù)據(jù)包傳輸時延和網(wǎng)絡(luò)丟包率性能上，比現(xiàn)有的路由算法具有明顯的優(yōu)越性。