基于BWAS的無線傳感器網絡靜態分簇路由算法

(1.重慶理工大學 遠程測試與控制技術研究所,重慶 400050；2.重慶三峽學院,重慶 404000；3.電子科技大學,成都 610054)

1 引 言

無線傳感器網絡(Wireless Sensor Network,WSN)的路由協議設計[1-2]是自組網中的一個核心環節，路由協議負責尋找源節點和目的節點間的優化路徑并沿此優化路徑正確轉發數據包。因網絡節點能量有限、動態拓撲結構和數據融合處理等特征，其路由協議設計在兼顧其它設計指標的同時，需首要考慮能量有限和能量均衡等問題，以提高整個網絡的生存期和魯棒性。

蟻群算法(ACS)因其具有自組織、自動尋優和動態特性,較廣泛地應用于無線傳感器網絡路由設計中[3-7]。但蟻群系統在較大數量節點網絡中存在路徑搜索效率和收斂速度相對偏低的缺陷。BWAS算法是對蟻群算法的改進[8]，在路徑搜尋過程中評價出最優最差螞蟻，引入獎懲機制，加強了搜尋過程的指導性，加快了路徑搜索速度，減少了路徑尋優能量消耗，表現出了較好的特性。但因動態分簇仍消耗了不少能量。

因此，本文在對蟻群算法進行改進，引入BWAS算法的同時，對動態分簇方式做了改進，靜態分簇并在簇內動態選取簇頭，以避免動態分簇消耗更多的能量。提出的基于最優-最差螞蟻系統(Best-Worst Ant System,BWAS)的無線傳感器網絡靜態分簇路由算法，可用于解決蟻群算法搜索效率相對偏低、能量消耗均衡和動態分簇帶來較多的能量消耗等方面的問題。

2 基于能量均衡的網絡節點靜態分簇

2.1 靜態分簇基本思想

根據基本分簇思想[9]，采用層次型拓撲結構，進行網絡節點靜態分簇和按條件在子簇內周期性選擇簇頭節點。通過概率隨機確定普通節點和高級節點，通過簇頭選取算法選取簇頭，以距離因子確定每個節點的子簇歸屬。簇頭負責簇內數據融合[10]并協調子簇所屬節點工作。子簇內定期根據剩余能量輪換選取簇頭，直到整個網絡中有高級節點的能量消耗達到其預設值時，進行新一輪的各子簇內簇頭選舉、路徑尋優和數據傳遞。在簇頭間運用BWAS算法搜尋從簇頭節點到匯聚節點的多跳最優路徑，采用多跳接力方式將數據發送至sink節點，實現無線傳感器網絡節點能量均衡管理。

2.2 靜態分簇步驟描述

第一步：初始化參數。確定節點數量、普通節點與高級節點的選取、選舉成簇的概率、初始化能量、傳輸有效距離和最大迭代次數等，接收sink節點的廣播讓sink節點知道網絡基本情況；

第二步：確定能耗模型。能耗模型定義為：Eelec=Etx=Erx。其中，Erx為接收能耗，Etx為傳輸能耗，Eelec為選舉成簇的能耗。節點向距離d發送kbit數據時，數據融合消耗能量Efuse(k) =Efuse×k，發送消耗能量Etx(k,d)=Eelec×k+εamp×k×d2；接收消耗能量Erx(k)=Eelec×k。無線發射模塊可以根據節點死亡情況和距離遠近控制發送功率大小或者關閉以避免接收到不需要的數據。發送數據的能耗取決于數據大小和傳輸距離，接收數據的能耗只取決于數據大小[9-10]；

第三步：根據節點數量和選舉簇頭概率確定簇頭，一般設定選舉簇頭概率p∈[0.1，0.15]；

第四步：根據節點位置信息和距離啟發因子，計算所有普通節點的歸屬并確定子簇。

定義1：普通節點(i，j)兩點的歐式距離：

Distance(i,j)=

(1)

普通節點與簇頭節點(i,c)兩點的歐式距離：

Distance(i,c)=

(2)

式中，S(i).xd，S(j).yd分別表示節點i與節點j的橫坐標和縱坐標，C(c).xd表示簇頭節點的橫坐標。

定義2：如果

Distance(i,c1)=Min(Distance(i,c1),Distance(i,c2),

…，Distance(i,cn))

(3)

則節點i屬于c1子簇，假設共有n個簇頭。

普通傳感器節點探尋到最近簇頭節點并發送加簇消息，sink節點接收到普通傳感器節點請求并給予響應，子簇建立；

第五步：根據sink節點廣播信息，將子簇內各節點的數據傳輸到簇頭，簇頭進行數據融合，并根據BWAS算法，搜尋最優路徑，將簇頭融合后的數據以多跳接力方式傳輸到sink節點。簇頭控制簇內節點的工作與休眠狀態；

第六步：計算子簇內包括簇頭的所有節點的消耗能量和剩余能量，確定是否具有死亡節點。根據一定規則確定新的簇頭，并調整發送功率大小等參數。

根據sink節點廣播要求，循環第二步至第六步到最大迭代次數或死亡節點接近于最初設定值。圖1所示為基于能量均衡的網絡節點靜態分簇流程。

圖1 基于能量均衡的網絡節點靜態分簇流程

3 基于BWAS的無線傳感器網絡路由算法

3.1 BWAS算法的基本思想

BWAS算法是在蟻群搜尋最優路徑過程中增強了搜索過程的指導性，引入對最差螞蟻懲罰機制，通過修改蟻群系統中的全局更新公式，對所有螞蟻完成一次循環后，對最差螞蟻所經過的且非最優螞蟻路徑的路徑信息素進行更新，即對最優螞蟻進行信息素增強的同時，對最差螞蟻路徑的信息素進行削弱，進一步增大最優與最差螞蟻的信息素，加快收斂速度，使得螞蟻的搜索更集中于到當前循環為止所找出的最好路徑的鄰域內。

3.2 BWAS算法基本步驟描述

該算法主要對蟻群系統中的全局更新公式進行了改進。當所有螞蟻完成一次循環后，增加對最差螞蟻所經過的且不是最優螞蟻路徑的信息素的更新。該算法是在上步已產生的簇頭間進行最優路徑選取，其具體步驟如下：

第一步：初始化參數；

第二步：根據式(4)、(5)為每只螞蟻選擇路徑；

(4)

τij(t+n)=ρ1·τij(t)+Δτij(t,t+n)

(5)

(6)

(7)

第三步：每生成一只螞蟻的路徑就按式(8)進行一次局部更新；

τ(r,s)←(1-ρ)·τ(r,s)+ρ·Δτ(r,s)

(8)

Δτ(r,s)=(nLnn)-1

(9)

式中，τ(r,s)表示節點r到節點s之間的信息素軌跡量；ρ為一個參數，0<ρ<1；n為節點數量；Lnn為最近的領域啟發產生的一個路徑長度；

第四步：循環執行第二步、第三步直到每只螞蟻都生成—條路徑；

第五步：根據當前循環中每只螞蟻經歷路徑的長度，評選出最優螞蟻和最差螞蟻；

第六步：對最優螞蟻按式(10)執行全局更新規則；

τ(r,s)←(1-α)·τ(r,s)+α·Δτ(r,s)

(10)

其中：

(11)

第七步：對最差螞蟻按式(12)執行全局更新規則：

(12)

式中，ε為該算法中引入的一個參數；Lworst為當前循環中最差螞蟻的路徑長度；Lbest為當前循環中最優螞蟻的路徑長度，τ(r,s)為節點r和節點s之間的信息素軌跡量；Lgb為當前循環中找出的全局最優路徑；α為信息素揮發參數，0<α<1。

循環執行第二步至第七步，直到執行次數達到指定數目或連續若干代內沒有更好的解出現為止。

圖2所示為BWAS算法步驟流程。

圖2 BWAS算法步驟流程

4 實驗結果及仿真分析

4.1 初始化實驗參數，生成網絡節點

本算法采用Matlab進行仿真。實驗中，設定傳感器節點區域大小為[100,100]，sink節點坐標為(100,100)，隨機生成網絡節點數為200。初始化網絡節點能量、傳輸數據類型與數據聚合能量消耗，并設定選舉成簇的概率p=0.1，最大迭代次數n=200。

圖3為隨機生成的傳感器網絡節點，其中，“o”表示普通節點，“+”表示高級節點，高級節點被首先選為簇頭節點而進行分簇。

圖3 隨機生成的無線傳感器網絡節點Fig.3 The WSN nodes generated randomly

4.2 確定簇頭分布和靜態網絡分簇

圖4為生成的分簇模式。簇頭節點是由高級節點產生，在所有節點中按照p概率選擇。實驗中在不同的循環次數里，各子簇內因各節點能量高低輪換選舉簇頭。此方式均衡了靜態分簇模式下的網絡節點能量消耗。

圖4 無線傳感器網絡分簇Fig.4 Clustering in WSN

4.3 基于BWAS靜態分簇、基于BWAS動態分簇和基于ACS算法的簇頭最佳路徑

圖5、圖6和圖7分別為基于BWAS靜態分簇、BWAS動態分簇和ACS算法所形成的傳輸路徑，三者均為相同簇頭而由不同的算法所形成的路由。從圖5、圖6和圖7對比可知：在相同簇頭分布中采用這兩種算法所形成的路徑一致，路徑長度相等。這是因為：所選取簇頭數量較少，三者算法在最終路徑的形成上路徑是一樣的。BWAS算法和ACS算法在數量較大的節點網絡搜尋優化路由中才能體現優越性。在簇頭數量相對較少，或在螞蟻數量和循環次數一定的情況下兩者形成的路由沒有差別。但是如果增大選取的概率p值，簇頭數量增多，會增加計算復雜度，消耗較多的能量。

圖5 基于BWAS靜態分簇的簇頭最佳路徑Fig.5 The optimal path of the cluster heads based on BWAS with static clustering

圖6 基于BWAS動態分簇的簇頭最佳路徑Fig.6 The optimal path of the cluster heads based on BWAS with dynamic clustering

圖7 基于ACS算法的簇頭最佳路徑Fig.7 The optimal path of the cluster heads based on ACS algorithm

4.4 基于BWAS靜態分簇、動態分簇和基于ACS的無線傳感器網絡魯棒性分析

4.4.13種方法分別在3次循環次數時的死亡節點情況比較

表1 3種方法在3次循環次數時的死亡節點數對比

由表1可知：基于BWAS靜態分簇的無線傳感器網絡在循環至第1 200、1 800和2 500次時，其死亡節點比基于BWAS動態分簇和基于ACS算法的無線傳感器網絡死亡節點數要少。

4.4.23種方法的網絡節點死亡對比分析

圖8為基于BWAS靜態分簇、BWAS動態分簇和ACS的網絡節點死亡對比。由圖8可知：基于BWAS靜態分簇路由比基于BWAS動態分簇和ACS的效果較好。在循環次數[0,800]之間，基于BWAS靜態分簇的網絡耗能與其余兩者相差不大，基于BWAS動態分簇的網絡耗能約偏大，因為在網絡動態分簇，使節點和sink節點之間存在大量的廣播信息傳輸而耗能相對較多。在循環次數[800,2 200]之間，BWAS靜態分簇方法有相對較好的優勢。在循環次數[2 200,2 500]之間，兩者死亡節點數差不多，是因為在整個網絡中剩余節點數較少，兩種路由算法效率相當。因此，基于BWAS靜態分簇路由算法的無線傳感器網絡具有更長壽命和較好的魯棒性。

圖8 基于BWAS和ACS的網絡死亡節點數對比Fig.8 Comparison of the dead nodes based on BWAS and ACS

5 結 論

基于BWAS的無線傳感器網絡靜態分簇路由算法是基于靜態分簇，在簇頭節點間運用BWAS算法搜尋從簇頭節點到匯聚節點的多跳最優路徑的一種優化算法，在簇頭間采用多跳接力方式將數據發送至sink節點。

BWAS算法修改了蟻群系統中的全局更新公式，引入對最差螞蟻懲罰機制，加強搜索過程的指導。因此，在路徑搜尋過程中，加快了路徑搜索速度，降低了路徑尋優能量消耗，使螞蟻的搜索行為更集中于最優解的附近。

實驗中通過與基于BWAS動態分簇和基于ACS路由算法的死亡節點數對比，表明本文提出的算法在相同運行條件下具有較少的死亡節點，死亡速度較緩慢，均衡了網絡節點能量消耗，延長了網絡壽命，優化了網絡節點路由，具有較強的魯棒性。

參考文獻：

[1] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.[S.l.]:IEEE,2000:3005-3014.

[2] Manjeshwar A,Agrawal D P. TEEN: a routing protocol for enhanced efficiency in wireless sensor networks[C]//Proceedings of the 15th International Symposium on Parallel and Distributed Processing. [S.l.]:IEEE,2001:2009-2015.

[3] 蘇淼,錢海,王煦法.基于蟻群的無線傳感器網絡雙簇頭算法[J].計算機工程,2008,34(13):174-176,192.

SU Miao, QIAN Hai,WANG Xu-fa. Ant Colony-based Double Cluster-heads Algorithm for Wireless Sensor Networks[J].Computer Engineering, 2008,34(13):174-176,192.(in Chinese)

[4] 梁華為,陳萬明,李帥,等.一種無線傳感器網絡蟻群優化路由算法[J].傳感技術學報,2007,20(11):2450-2455.

LIANG Hua-wei1, CHEN Wan-ming, LI Shuai, et al. ACO-Based Routing Algorithm for Wireless Sensor Networks(ARAWSN)[J]. Chinese Journal of Sensors and Actuators, 2007,20(11):2450-2455. (in Chinese)

[5] 楊靖,熊偉麗,徐保國.無線傳感器網絡中基于蟻群算法的路由算法[J].計算機工程,2009,35(6):4-6.

YANG Jing, XIONG Wei-li,XU Bao-guo. Routing Algorithm Based on Ant Colony Algorithm in Wireless Sensor Networks[J].Computer Engineering, 2009,35(6):4-6. (in Chinese)

[6] 任秀麗，梁紅偉，汪宇．基于多路徑蟻群算法的無線傳感器網絡的路由[J]．計算機科學，2009，36(4):116-118．

REN Xiu-li, LIANG Hong-wei, WANG Yu. Multipath Routing of Ant Colony System in Wireless Sensor Networks[J].Computer Science, 2009, 36(4):116-118．(in Chinese)

[7] 王結太，許家棟，徐建城．基于蟻群優化算法的無線傳感器網絡路由協議[J]．系統仿真學報，2008，20(18)：4898-4901．

WANG Jie-tai, XU Jia-dong, XU Jian-cheng. Wireless Sensor Networks Routing Protocol Based on Ant Colony Optimized Algorithm[J].Journal of System Simulation, 2008, 20(18): 4898-4901．(in Chinese)

[8] 馮躍喜,金心宇,蔡文郁. 基于改進型蟻群算法的無線傳感路由協議[J].傳感技術學報,2007,20(11):2461-2464.

FENG Yue-xi, JIN Xin-yu, CAI Wen-yu. Wireless Sensor Network Routing Protocol Based on Improved Ant Colony Algorithm[J].Chinese Journal of Sensors and Actuators, 2007,20(11):2461-2464. (in Chinese)

[9] Heinzelman W B, Chandrakasan A P, Balakrishnan H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[10]Stephanie Lindsey, Cauligi Raghavendra. Data Gathering Algorithms in Sensor Networks Using Energy Metrics [J].IEEE Transactions on Parallel and Distributed Systems, 2002(9):924-935.