一種改進跨層擁塞控制的無線傳感網絡蟻群路由算法

胡國偉

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

1 問題提出

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

2 改進的網絡跨層擁塞控制算法

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

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

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

2.2 擁塞檢測機制

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

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

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

2.3 防擁塞控制機制

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

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

3 仿真實驗及結果分析

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

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

3.2 仿真結果

3.2.1 分組丟包率

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

圖1 網絡丟包率

圖2 平均端到端時

3.2.2 平均端到端時延

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

3.2.3 網絡吞吐量

網絡吞吐量是單位時間內sink 節(jié)點接收到的數據包數量。由圖3可知，本文提出的算法在不同閥值系數下，相比于IEEABR 算法能夠獲得較好的網絡吞吐量，這是因為擁塞控制的路由能夠獲得較高的數據成功傳輸概率。從而使得CIEEABR 算法節(jié)點成功接收的數據包數量顯著增加。

圖3 網絡吞吐量

4 結束語

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