基于BWAS的無線傳感器網(wǎng)絡(luò)靜態(tài)分簇路由算法

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

1 引 言

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

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

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

2 基于能量均衡的網(wǎng)絡(luò)節(jié)點靜態(tài)分簇

2.1 靜態(tài)分簇基本思想

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

2.2 靜態(tài)分簇步驟描述

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

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

第三步：根據(jù)節(jié)點數(shù)量和選舉簇頭概率確定簇頭，一般設(shè)定選舉簇頭概率p∈[0.1，0.15]；

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

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

Distance(i,j)=

(1)

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

Distance(i,c)=

(2)

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

定義2：如果

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

…，Distance(i,cn))

(3)

則節(jié)點i屬于c1子簇，假設(shè)共有n個簇頭。

普通傳感器節(jié)點探尋到最近簇頭節(jié)點并發(fā)送加簇消息，sink節(jié)點接收到普通傳感器節(jié)點請求并給予響應(yīng)，子簇建立；

第五步：根據(jù)sink節(jié)點廣播信息，將子簇內(nèi)各節(jié)點的數(shù)據(jù)傳輸?shù)酱仡^，簇頭進行數(shù)據(jù)融合，并根據(jù)BWAS算法，搜尋最優(yōu)路徑，將簇頭融合后的數(shù)據(jù)以多跳接力方式傳輸?shù)絪ink節(jié)點。簇頭控制簇內(nèi)節(jié)點的工作與休眠狀態(tài)；

第六步：計算子簇內(nèi)包括簇頭的所有節(jié)點的消耗能量和剩余能量，確定是否具有死亡節(jié)點。根據(jù)一定規(guī)則確定新的簇頭，并調(diào)整發(fā)送功率大小等參數(shù)。

根據(jù)sink節(jié)點廣播要求，循環(huán)第二步至第六步到最大迭代次數(shù)或死亡節(jié)點接近于最初設(shè)定值。圖1所示為基于能量均衡的網(wǎng)絡(luò)節(jié)點靜態(tài)分簇流程。

圖1 基于能量均衡的網(wǎng)絡(luò)節(jié)點靜態(tài)分簇流程

3 基于BWAS的無線傳感器網(wǎng)絡(luò)路由算法

3.1 BWAS算法的基本思想

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

3.2 BWAS算法基本步驟描述

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

第一步：初始化參數(shù)；

第二步：根據(jù)式(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)表示節(jié)點r到節(jié)點s之間的信息素軌跡量；ρ為一個參數(shù)，0<ρ<1；n為節(jié)點數(shù)量；Lnn為最近的領(lǐng)域啟發(fā)產(chǎn)生的一個路徑長度；

第四步：循環(huán)執(zhí)行第二步、第三步直到每只螞蟻都生成—條路徑；

第五步：根據(jù)當前循環(huán)中每只螞蟻經(jīng)歷路徑的長度，評選出最優(yōu)螞蟻和最差螞蟻；

第六步：對最優(yōu)螞蟻按式(10)執(zhí)行全局更新規(guī)則；

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

(10)

其中：

(11)

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

(12)

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

循環(huán)執(zhí)行第二步至第七步，直到執(zhí)行次數(shù)達到指定數(shù)目或連續(xù)若干代內(nèi)沒有更好的解出現(xiàn)為止。

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

圖2 BWAS算法步驟流程

4 實驗結(jié)果及仿真分析

4.1 初始化實驗參數(shù)，生成網(wǎng)絡(luò)節(jié)點

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

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

圖3 隨機生成的無線傳感器網(wǎng)絡(luò)節(jié)點Fig.3 The WSN nodes generated randomly

4.2 確定簇頭分布和靜態(tài)網(wǎng)絡(luò)分簇

圖4為生成的分簇模式。簇頭節(jié)點是由高級節(jié)點產(chǎn)生，在所有節(jié)點中按照p概率選擇。實驗中在不同的循環(huán)次數(shù)里，各子簇內(nèi)因各節(jié)點能量高低輪換選舉簇頭。此方式均衡了靜態(tài)分簇模式下的網(wǎng)絡(luò)節(jié)點能量消耗。

圖4 無線傳感器網(wǎng)絡(luò)分簇Fig.4 Clustering in WSN

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

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

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

圖6 基于BWAS動態(tài)分簇的簇頭最佳路徑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靜態(tài)分簇、動態(tài)分簇和基于ACS的無線傳感器網(wǎng)絡(luò)魯棒性分析

4.4.13種方法分別在3次循環(huán)次數(shù)時的死亡節(jié)點情況比較

表1 3種方法在3次循環(huán)次數(shù)時的死亡節(jié)點數(shù)對比

由表1可知：基于BWAS靜態(tài)分簇的無線傳感器網(wǎng)絡(luò)在循環(huán)至第1 200、1 800和2 500次時，其死亡節(jié)點比基于BWAS動態(tài)分簇和基于ACS算法的無線傳感器網(wǎng)絡(luò)死亡節(jié)點數(shù)要少。

4.4.23種方法的網(wǎng)絡(luò)節(jié)點死亡對比分析

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

圖8 基于BWAS和ACS的網(wǎng)絡(luò)死亡節(jié)點數(shù)對比Fig.8 Comparison of the dead nodes based on BWAS and ACS

5 結(jié) 論

基于BWAS的無線傳感器網(wǎng)絡(luò)靜態(tài)分簇路由算法是基于靜態(tài)分簇，在簇頭節(jié)點間運用BWAS算法搜尋從簇頭節(jié)點到匯聚節(jié)點的多跳最優(yōu)路徑的一種優(yōu)化算法，在簇頭間采用多跳接力方式將數(shù)據(jù)發(fā)送至sink節(jié)點。

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

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

參考文獻：

[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] 蘇淼,錢海,王煦法.基于蟻群的無線傳感器網(wǎng)絡(luò)雙簇頭算法[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] 梁華為,陳萬明,李帥,等.一種無線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算法[J].傳感技術(shù)學報,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] 楊靖,熊偉麗,徐保國.無線傳感器網(wǎng)絡(luò)中基于蟻群算法的路由算法[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] 任秀麗，梁紅偉，汪宇．基于多路徑蟻群算法的無線傳感器網(wǎng)絡(luò)的路由[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] 王結(jié)太，許家棟，徐建城．基于蟻群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]．系統(tǒng)仿真學報，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] 馮躍喜,金心宇,蔡文郁. 基于改進型蟻群算法的無線傳感路由協(xié)議[J].傳感技術(shù)學報,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.