(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.