無線傳感器網絡中基于功率控制的蟻群路由算法*

何建強 滕志軍 張 帆 劉 皎

（1.商洛學院電子信息與電氣工程學院 商洛 726000）（2.東北電力大學信息工程學院 吉林 132012）

1 引言

無線傳感器網絡的功率控制技術主要指網絡節點在無線通信過程中選擇合適的功率發送分組以達到優化網絡性能的目的［1]。控制節點的發射功率對提升無線傳感器網絡的性能具有較大意義，它既可以提升網絡能量的有效性，又能增加網絡并發吞吐量。目前，無線傳感器網絡路由節點能量的研究已取得一些成果。文獻［2]中Camilo等提出了一種基于蟻群的能量有效性路由算法，即EEABR（Energy-efficient ant-based routing）路由算法，EEABR算法提升了收發螞蟻包時的能量使用效率，即減小了發送螞蟻包時的能量消耗，但沒有考慮螞蟻環路效應。文獻［3]在EEABR算法的基礎上提出一種EEABR改進算法，即EEIABR（Energy-efficient improved ant-based routing）路由算法。該算法通過在螞蟻包中增加螞蟻包序列號sq_num，有效削弱螞蟻環路，同時修正信息素更新公式，將路由跳數修正為多跳消耗的能量值，并在信息素更新公式中引入節點能量與路徑平均能量的偏離值，使全網節點的能量消耗更加平均，延長網絡的生存周期。

本文在EEIABR路由算法的基礎上，提出帶有發射功率控制的PCABR算法。該算法通過提取接收hello分組的接收信號強度，并通過文獻［4]中Friss公式推導出合適的發送功率級，并將該功率級存儲在節點的鄰居列表中。節點以概率公式選擇下一跳路由發送前向螞蟻分組時，會將綜合考慮下一跳節點的剩余能量和自身的發送功率級，通過對節點發射功率級的控制，減小螞蟻尋優過程和信息發送過程中的能量消耗，提升路徑的優化程度，進一步增加網絡生存周期。

2 EEIABR算法簡介

EEIABR算法采用EEABR算法的螞蟻包分類，分為Hello包和螞蟻包兩類［5]。節點通過廣播Hello包來維護鄰居列表，通過發送螞蟻包來優化路徑和傳輸信息。針對算法中容易形成環路和節點能量分布不均的缺點，在Hello包、螞蟻包、節點鄰居表中增添pkt_src（發送螞蟻包的源地址）和sq_num（螞蟻包序列號）的組合項，在發送螞蟻包時，在螞蟻包頭中添加下一跳節點地址naddr以及＜pkt_src，sq_num＞。節點在廣播Hello包時，除了要廣播自己節點地址和能量，還應該廣播路鄰居列表中的＜pkt_src，sq_num＞，這樣接收節點就會“知道”自己的鄰居節點轉發過的螞蟻包，避免不必要的回傳，改善螞蟻的環路效應［6]。同時修正了后向螞蟻包的信息素更新公式，并引入了能量差異因子，平衡了全網能量，提升能量分布均勻性。

3 PCABR算法的結構模型

3.1 Hello分組結構

PCABR采用與EEIABR算法相同的Hello分組結構，同樣采用＜pkt_src，sq_num＞螞蟻分組標識組合項，削弱環路效應。圖1為PCABR算法的Hello分組結構圖。

圖1 PCABR Hello分組結構

其中，Type為分組類型，Hello_pkt_src為Hello分組的源地址，Energy為廣播該Hello分組的節點的剩余能量，Phero為該條路徑上的信息素濃度。

3.2 概率選擇公式

PCABR算法在螞蟻能見度函數中引入了節點發送功率作為前向螞蟻概率選擇下一跳節點的參考因子，因此其能見度函數E（s）需要重新定義，PCABR算法的概率選擇式如（1）所示。能見度函數E（s）如式（2）所示。

式中T（r，s）、T（r，u）函數指螞蟻轉移路徑的信息素濃度；α和β為參數，分別表征螞蟻在概率選擇過程中，信息素濃度和啟發式信息的重要程度。

式中Prs為節點r向節點s的發送分組的發送功率。由已知參數可計算出節點所需要發送的最小功率值Prs。將該最小功率存儲到如表1所示的鄰居列表中。

表1 PCABR節點鄰居列表

表 1 中，NeighbourAddr、NeighbourEng、Pheromone分別表示鄰居節點地址、鄰居節點能量以及該一跳路徑上的信息素濃度。由于PCABR需要根據節點間距離而調節發射功率，因此，PCABR的鄰居列表中需要加入＜NeighbourAddr，Pm＞的組合項，當前向螞蟻分組從鄰居列表中選取下一跳節點時，根據式（1）求出選擇下一跳的概率值。

3.3 前向螞蟻分組結構

PCABR采用與EEIABR相同的前向螞蟻分組結構，如圖2所示。

圖2 前向螞蟻包結構

其中Type為分組類型，這里標識為螞蟻分組。Pkt_src為螞蟻分組的源地址，Daddr為螞蟻分組下一跳地址，由式（1）得出。Saddr為螞蟻分組上一跳的節點地址。Energy_sum為前向螞蟻分組到達當前節點時，所有訪問過的節點的剩余能量總和。Energy_min為前向螞蟻分組到達當前節點時，所有訪問過的剩余能量最小節點的能量值。toSintNode為布爾型變量，表明螞蟻分組方向。hops為螞蟻經過的節點數。

3.4 信息素更新公式

當前向螞蟻分組到達Sink節點時，需要轉化成后向螞蟻分組，沿原路徑返回，再返回之前，需要由Sink節點根據前向螞蟻分組攜帶的路徑信息，即前向螞蟻分組的中攜帶的信息計算該路徑上的信息更新量。PCABR信息素更新公式如式（3）、（4）、（5）所示。

式（3）所示為節點r到節點s路徑上的的信息素更新規則，其中ρ為信息素蒸發系數，防止信息素濃度的無限制累積。ΔTk為后向螞蟻k攜帶的更新該條路徑的信息素增量。由式（4）所示。

其中EAvgk為前向螞蟻分組k訪問過節點的平均剩余能量，如式（5）所示。

Energy_sum為前向路徑上剩余能量的總和，Fdk為訪問過的節點數，由圖1中的hops得出。

從PCABR算法的信息素更新公式中可以得出，剩余能量較大，路由跳數較少，能量分布較為平均的路徑信息素增加較多，后續螞蟻分組選擇該條路徑的概率增大。

3.5 后向螞蟻分組結構

PCABR后向螞蟻分組負責更新前向路徑上的信息素濃度，后向螞蟻分組結構如圖3所示。

圖3 后向螞蟻分組結構

其中Type為分組類型，Pkt_src為后向螞蟻分組的最終目的地址，Daddr為后向螞蟻分組下一跳地址，Saddr為后向螞蟻上一跳的節點地址。Pheromone為信息素增量，toSinkNode為布爾型變量，與前向螞蟻分組相對應，定義為false，Energy_avg為該條路徑上的平均能量。

4 PCABR路由算法流程

4.1 Hello分組收發流程

如圖4所示節點周期性的發送Hello分組與鄰節點建立聯系，節點在收到Hello分組后更新自己的鄰居節點列表。與EEIABR算法不同之處在于，接收節點除了提取Hello信息中的鄰節點地址，鄰節點剩余能量和該一跳路徑的信息素之外，還需要提取RSSI，得出發送給該跳節點的最優發射功率，存儲在相應的鄰居列表當中。

圖4 PCABR Hello分組收發流程

4.2 PCABR螞蟻分組收發流程圖

如圖5所示，節點每隔一段時間發送前向螞蟻分組尋找通往Sink節點的路徑。首先源節點查詢鄰居列表是否存在Sink節點，若存在則直接向Sink節點發送前向螞蟻分組；若不存，則按式（1）概率選擇下一跳分組轉發節點。

當Sink節點收到前向螞蟻分組之后，隨即生成后向螞蟻分組，按原路徑返回至源節點并更新路徑上信息素。首先，Sink節點查詢鄰居列表是否存在源節點，若存在則直接向源節點發送后向螞蟻分組，若不存在則需要根據當前節點的路由表按原路徑轉發后向螞蟻分組，并通過式（3）更新該跳路徑上的信息素濃度。如此循環，直到源節點收到后向螞蟻分組，該輪螞蟻收發結束。

圖5 PCABR螞蟻分組收發流程

5 實驗仿真及結果對比

為了驗證PCABR、EEIABR和EEABR算法在多節點無線傳感器網絡中能量使用效率和能量均衡性上的優劣程度。通過Vmware9.0虛擬機下Ubuntu10.04+NS2.35平臺對上述三種算法進行仿真。移動場景參數表如表2所示。CBR數據流參數表如表3所示。傳感器節點參數如表4所示。

表2 移動場景參數表

表3 CBR數據流參數表

表4 傳感器節點參數

除此之外，設定三種算法的節點的初始發送功率（txPower）為 0.6W，初始接收功率（rxPower）為0.3W，空閑能量消耗（idlePower）為0.06W，仿真時間為100s［7]。圖6為節點平均剩余能量隨節點數目變化，圖7為節點最小剩余能量隨節點數目變化。

圖6 節點剩余能量隨節點數目變化

如圖6與圖7所示，隨著節點的不斷增加，PCABR算法通過動態調整發射分組的功率，在節點平均剩余能量和節點最小剩余能量均優于EEABR和EEIABR算法［8]，表明PCABR算法在多節點的無線傳感器網絡對能量的使用效率的提升較為明顯。

圖7 節點最小剩余能量隨節點數目變化

為了進一步驗證PCABR算法在多節點時的能量均衡性，保持100*100m2不變，節點數目為65個，仿真時間為50s～100s［9]。圖8為節點平均剩余能量隨時間變化曲線，圖9為節點最小剩余能量隨時間變化曲線。

如圖8與圖9所示，在節點數目為65個時，隨著時間的不斷增加，PCABR算法在能量使用效率和能量均衡性方面相較于EEABR算法和EEIABR算法均有一定的提升。

圖8 節點平均剩余能量隨時間變化

圖9 節點最小剩余能量隨時間變化

6 結語

本文以EEIABR算法為基礎，提出一種基于功率控制的蟻群路由算法PCABR。該算法通過提取鄰節點Hello分組的接收信號強度，推導出對鄰節點的最優功率級，達到對節點發送端功率控制的目的［10]。同時，PCABR對EEIABR算法的鄰居節點列表，概率選擇公式，信息素更新公式作進一步改進，使路徑信息素更新更為準確，提高螞蟻的搜索效率，仿真表明PCABR算法相較于EEIABR和EEABR算法在能量使用效率和網絡節點均衡性方面均有一定的提升，更適用于節點數目較多的無線傳感器網絡。