仿血管路径的无线传感器网络故障容错路由算法❋

李洪兵，余成波，全晓莉，刘峪王宣

仿血管路径的无线传感器网络故障容错路由算法❋

李洪兵1，2，余成波1，全晓莉1，刘峪王宣1

（1.重庆理工大学远程测试与控制技术研究所，重庆400054；2.重庆三峡学院，重庆404000）

为提高无线传感器网络故障容错性和传输稳定性，实现网络负载均衡，提出了一种仿血管路径的无线传感器网络故障容错路由算法。研究了人体血管路径特性及属性关联，对网络节点分区域等级标定并以不同概率值进行静态分簇，运用改进的蚁群算法BWAS（最优最差蚂蚁系统）生成节点路径，以路径信息素值作为传输路径的选择概率建立仿血管拓扑结构路由。因具有多条传输路径并选择最高概率作为传输路由，避免了因节点或链路故障导致数据的延迟或丢失，提高了网络故障容错性和传输稳定性，实现了网络能耗均衡。理论分析和仿真结果表明此算法具有良好性能。

无线传感器网络；故障容错；路由协议；血管路径；BWAS算法

1 引言

因拓扑动态变化、能量约束和传输受限等特性，无线传感器网络（Wireless Sensor Network，WSN）易出现多种网路故障，如节点失效、链路质量差、数据碰撞厉害、能耗不均和网络鲁棒性差等。无线传感器网络自身的健康状态对于获取准确的数据极为重要，病态的无线传感器网络较难协调处理和获取可靠的数据。故障容错是无线传感器网络面临着的一个共性的、亟待解决的关键性技术问题。无线传感器自身故障容错研究尚处于初始阶段，研究其容错路由算法、提高无线传感器网络运行的稳定性是非常必要的。

国内外对无线传感器网路自身故障诊断与容错作了一定的研究，提出的较典型的容错路由协议和算法有：引入故障节点绕行机制实时容错路由协议FT－SPEED［1］；具有多拓扑路由的入侵容错路由协议SEIF［2］；具有负载均衡的延迟容错跨层数据传输协议LOFT［3］；动态分布式簇头选举故障容错算法FTEP［4］；基于TDMA协议同步并提供数据在传输过程中首位相连的保证机制FlexiTP［5］；前向错误纠正编码算法［6］；FTPASC算法［7］；延长射频传输范围的平面路由［8］和故障容错动态分簇协议FT－DSC［9］等。它们在无线传感器网络故障容错方面取得了较好的效果，但以增加算法复杂度、增加能量消耗、降低灵活性及稳定性的某些方面为代价。

本文根据人体血管路径分布特征以及对无线传感器网络故障容错的启示，基于特性条件约束，赋予人为定义并优化，拟采用改进的蚁群算法仿真人体血管拓扑结构路由，开展能故障容错的无线传感器网络仿人体血管拓扑结构路由算法研究。

2 WSN仿血管拓扑结构路由的属性关联与特征

2.1 WSN仿血管拓扑结构路由的属性关联分析

人体血管路径与血流流动具有如下特性：（1）血管具有相对稳定和局部弹性，主要血流量沿着动脉血管路径流动，血液在局部范围可绕行流动；（2）血管路径具有空间连通性，具有实际流动路径和可被选流动路径，某处血管发生病变，血液会选择合适的路径绕行流动；（3）血管交叉点的血压大小不一，血液根据血流流变学原理沿血管路径定向流动；（4）血液流量、流速和血管截面与血压参数间有着定量的关系。

无线传感器网络与人体血管血流的特征关联：（1）心脏搏跳过程与汇聚节点广播消息、采集、汇集和传输数据的周期性工作机制与时间同步性；（2）血液携带营养物质沿体动脉到毛细血管流动过程与汇聚节点沿着一定路径广播消息给各传感器节点；（3）静脉血液回流至右心房过程与传感器节点收集信息传输至汇聚节点过程；（4）血液在血管交叉处汇集与无线传感器数据聚集或融合等。

人体血管血流特性对建立无线传感器网络故障容错路由的启示：（1）所建立的仿血管拓扑结构路由应具有多路径连通性；（2）建立有等级区别的节点以保证数据的有向传输；（3）用蚁群算法在路径寻优中的信息素值确定数据传输时最优路径的选择问题；（4）不同等级节点采用不同概率分簇，避免无线传感器网络热点问题。

2.2 WSN仿血管拓扑结构路由特征

根据人体血管路径特征所建立的仿血管拓扑结构路由示意图如图1所示。其中，图1（a）为仿血管路由逻辑拓扑结构，图1（b）为仿血管路由物理拓扑结构，图1（c）为传统树型路由结构，节点0为网络汇聚节点，节点1～10为网络簇头节点。

在仿血管路由逻辑拓扑结构中，一个节点不与同级节点建立路径，只与邻级簇头节点建立传输路径，且与在其发射功率覆盖范围的每个邻级节点都建立传输路径。节点1～5为第一级，负责簇内数据融合和接收并转发来自第二级簇头节点的数据至汇聚节点。节点6～8为第二级，负责簇内数据融合并转发来自第三级簇头节点数据至第一级节点。节点9和节点10为第三级，只负责簇内数据融合并将数据转发至第二级节点。

在仿血管路由物理拓扑结构中，数据传输和消息广播都具有方向性，簇头节点与在其发射功率覆盖范围的所有邻级节点都建立了路径关系，各路径信息素值大小不一，将其归一化后数值作为数据传输的路径选择概率，选取最大概率值链路作为传输路径。当传输路径发生故障时，节点选择次概率值链路作为传输路径并依此类推。信息素是蚁群在搜寻最优路径过程中在各路径上留下的信息素浓度，是反映最优路径的一个重要参数，如图1（b）所示，不同颜色和线状的路径代表不同的信息素值，节点7选择信息素值最大链路经节点3后传至汇聚节点；若节点3发生故障，会选择到节点2和4中较大信息素值链路作为传输路径。

在传统树型路由结构中，树结构中的节点只能向自身的父节点进行数据传输，存在较大节点风险问题。如节点3发生故障，则节点7、9、10的数据都将丢失，对整个网络的数据准确性产生较大的影响。

3 WSN仿血管拓扑结构路由生成

3.1 基于等级区域划分的静态分簇

条件假设：（1）网络节点是静止的；（2）各节点的地理位置已知；（3）分簇前各传感器节点地位平等，拥有相同的参数和初始能量；（4）网络节点数量较大，都是全双工工作模式；（5）节点随机均匀分布在矩形区域内，汇聚节点位于外侧。

分簇原理：为实现无线传感器网络能量均衡，避免距离汇聚节点近的簇头节点因转发数据负荷量大而提前死亡的热点问题，通过与汇聚节点的距离将网络节点分成不同等级区域，并将网络节点进行等级标定，不同等级区域采用不同的簇头选举概率进行静态分簇，构建大小不同的簇。簇内根据剩余能量动态轮换选举簇头，以实现能耗均衡。

分簇过程及特征：节点位置已知的无线传感器网络，以汇聚节点为中心，以半径n·R（n∈1，2，…）将WSN划分为不同的环状区域，并将同一环状区域的无线传感器节点标定为同一等级。簇头节点只能建立到邻级节点的路由，不能与同级节点建立路由。每个区域以不同的概率选举簇头。靠近汇聚节点的区域为第一等级，以较大概率选取簇头，各等级依次减小，并最终形成距离汇聚节点越近的区域，簇头数量较多、簇规模较小的格局，如图2所示。距离汇聚节点较近的区域，形成的簇的规模较小，簇头消耗在簇内通信和数据聚合上的能量较少，以补偿转发其它区域簇头节点数据包的能量消耗。距离汇聚节点较远区域，形成的簇的规模较大，簇内通信和数据聚合上的能耗增大，以抵消转发较少的数据包而节省的能量，最终实现能耗均衡［10］。

簇头选取概率确定：网络能耗参考文献［11］，当分成n个区域时，每个区域半径为n·R，传感器节点总数为Nn·R。从半径为R区域开始每个区域簇头选取概率为pn（n∈1，2…），则每个区域簇头数为，一个簇内非簇头节点总数－1。现假设每个节点只发送k bit数据，则在半径为R等级区域内，一个簇头节点能耗：

簇内非簇头节点能耗：

一个簇的总能耗：

要使得总能耗最小，有：

得p1。根据能耗均衡要求，ER·total＝E2R·total，故能求得p2，并依此类推。

3.2 基于BWAS的路径信息素值的计算

最优最差蚂蚁系统（Best-worst Ant system，BWAS）［12］是对蚁群算法的改进，引入对最差蚂蚁惩罚机制，在所有蚂蚁完成一次循环后，对最差蚂蚁所经过的且非最优蚂蚁路径的路径信息素进行更新，进一步增大最优与最差蚂蚁的信息素，增强了最优路径搜索过程指导，加快收敛速度。假设在每个簇头节点置放一定数量人工蚂蚁，定义每只蚂蚁的任务是搜寻从所在簇头节点到汇聚节点的一条路径，蚂蚁完成任务时立即死亡。蚂蚁具有记忆所走过路径信息素值的功能。算法基本步骤如下：

第一步初始化参数。确定簇头节点信息，设定每个簇头节点的人工蚂蚁数量、定义其属性等。

第二步根据式（5）和式（6）为每只蚂蚁选择路径：

第三步每只蚂蚁完成任务后，网络对其生成的路径按式（9）进行一次局部更新；

式中，τ（r，s）表示节点r到节点s之间的信息素轨迹量，ρ为一个参数，0＜ρ＜1，n为节点数量，Lnn为最近的领域启发产生的一个路径长度。

第四步循环执行第二步、第三步直到簇头节点中的每只蚂蚁都生成—条路径。

第五步根据所在簇头节点的每只蚂蚁经历路径的长度，评选出最优蚂蚁和最差蚂蚁。

第六步对最优蚂蚁按式（11）执行全局更新规则：

其中：

第七步对最差蚂蚁按式（13）执行全局更新规则：

式中，ε为该算法中引入的一个参数，Lworst为当前循环中最差蚂蚁的路径长度，Lbest为当前循环中最优蚂蚁的路径长度，τ（r，s）为节点r和节点s之间的信息素轨迹量，Lgb为当前循环中找出的全局最优路径，α为信息素挥发参数，0＜α＜1。

第八步分别对其余簇头节点中的蚂蚁执行第2～7步，直到所有簇头节点的蚂蚁运行完毕，记录出各路径信息素值。图3所示为BW AS算法步骤流程。

3.3 建立传输路由与工作机制

仿血管拓扑结构路由主要在于提高链路质量和容错性，提高数据传输的稳定性。对于能量有限的网络，提高能量利用效率是其关键技术。在等级标定、静态分簇、运用BWAS算法计算出各路径的信息素值后，将各路径信息素值归一化，作为建立传输路径的选择概率。在此仿血管拓扑结构路由中，当某簇头节点能量消耗达到一定阈值时，主动沿原路径报告信息，以减少信息广播传输能耗。等待传输周期完毕，簇内根据能量均衡原则动态轮换选举能量较高的节点担当簇头节点，整个网络运用BWAS算法进行新一轮的路径信息素的计算，以建立新的拓扑结构路由。

4 仿血管拓扑结构路由仿真与性能评价

4.1 仿血管拓扑结构路由仿真

基于Matlab平台仿真，首先随机生成分区域等级标定的无线传感器节点，静态分簇后每个簇头节点置放10只蚂蚁，按照BWAS算法步骤对传感器节点进行仿真。当所有节点的蚂蚁都到达汇聚节点完成任务时，各路径信息素进行全局更新，BWAS算法循环结束，各路径信息素停止挥发，记录各路径信息素值。路径仿真结果如图4和图5所示。

图4和图5分别为仿血管路由的物理拓扑结构和逻辑拓扑结构。由图4和图5可知，蚂蚁在BWAS算法下走过的路径，记录下各路径信息素值，并记录在传感器节点上。蚂蚁所走过的路径是没有分等级节点的，是在所有节点平等的地位上展开的群体智能搜索。根据蚁群算法基本原理，信息素的浓度反映了蚁群搜索最优路径的结果。根据仿血管拓扑结构特征，即有等级区别的、簇头节点只和邻级簇头节点建立传输路径的特征，建立了整个网络传输的拓扑结构路由。

4.2 仿血管拓扑结构路由性能评价

4.2.1 BWAS算法收敛速度

BWAS算法对蚁群算法的改进，是在蚁群搜寻最优路径过程中，引入对最优最差蚂蚁惩罚机制，增强了搜索过程指导，对最差蚂蚁所经过的且非最优蚂蚁路径的路径信息素进行更新，进一步增大最优与最差蚂蚁的信息素，加快收敛速度，提高了计算效率，节约了路径寻优能耗。

4.2.2 能耗均衡性

根据距离汇聚节点远近，将无线传感器网络分成具有等级的区域，不同等级区域的节点以不同的概率分簇，保证不同等级区域的传感器节点总体能耗均衡，避免了距离汇集节点近的节点因转发大量数据而提前耗尽能量。簇内根据能量高低动态轮换选举簇头，有效保证了同一区域内各节点的能耗均衡。

取Ei，j（i＝1，2，3；j为数据传输轮数）为第i等级区域第j轮数据传输时总的剩余能量，ΔEi，j＝Ei，j－Ei，j＋100表示第i等级区域第j轮后的100轮的数据传输所消耗的能量，其能量消耗如图6所示。

由图6可知，当无线传感器网络数据传输轮数在300～700之间，第1、2、3等级区域的总能耗值在［495，520］之间，不同等级区域总体能耗均衡，避免了无线传感器网络热点问题。

4.2.3 路由容错性

任一簇头节点都与在其发射功率覆盖范围的邻级簇头节点建立了路径，只选择其最大概率值路径作为传输路径。一旦发生节点或链路故障，网络会选择次概率值路径进行传输。在图1中以节点7为例，节点7建立起到邻级节点1～5的路径pathi（i＝1，2，…，5），但这5条路径对应的选择概率pi≠pj（i≠j；i、j＝1，2，…，5）。建立的实际传输路径为pathj→max（pi），i＝1，2，…，5，但当此链路发生故障时，实际传输路径就改为pathk→max（pi），i≠j，i＝1，2，…，5，并以此类推。因此，任何一个等级区域的节点都能按照概率建立到汇聚节点的最优路径，提高了链路容错性，保证了数据传输的稳定性，降低了数据在传统树结构路由中传输的风险。

5 结论

根据血管路径具有的相对稳定性、局部弹性、空间连通性及血液定向流动特性，对网络节点分区域等级标定，以不同概率值进行静态分簇，运用改进的蚁群算法BWAS生成节点路径，将路径信息素归一化后作为实际传输路径的选择概率而建立仿血管拓扑结构路由。此算法提高了网络故障容错性和数据传输稳定性，均衡了网络负载，延长了网络生命期。

此算法是在前期BW AS算法优化研究基础之上开展的无线传感器网络的路由研究，但在概率分簇和路由算法设计时是基于血管路径特性。对于传感器节点数量较大的网络，此算法在能效均衡和容错稳定等方面具有较好的性能，这在实际应用中具有重要的意义。作为一种新颖的路由算法，在理论分析、体系完善并得到实际应用的过程中还有诸多方面值得深入研究，如在不同情况下等级分簇的能效性判定、数据传输的有效性以及数据传输工作机制等。

［1］Lei Zhao，Baoqiang Kan，Yongjun Xu，et al.FT-SPEED：A Fault-Tolerant，Real-Time Routing Protocol for Wireless Sensor Networks［C］／／Proceedings of 2007 International Conference on Wireless Communications，Networking and Mobile Computing.［S.l.］：IEEE，2007：2531－2534.

［2］Ouadjaout A，Challal Y，Lasla N，et al.SEIF：Secure and Efficient Intrusion-Fault Tolerant Routing Protocol for Wireless Sensor Networks［C］／／Proceedings of 2008 3th International Conference on Availability，Reliability and Security.［S.l.］：IEEE，2008：503－508.

［3］Ngai E C－H，Zhou Yangfan，Lyu M R，et al.LOFT：A Latency-Oriented Fault Tolerant Transport Protocol for Wireless Sensor-Actuator Networks［C］／／Proceedings of 2007 Global Telecommunications Conference.Washington，DC：IEEE，2007：1318－1323.

［4］Bansal N，Sharma T P，Misra M，et al.FTEP：A fault tolerant election protocol for multi-level clustering in homogeneous wireless sensor networks［C］／／Proceedings of 16th International Conference on Networks.New Delhi：IEEE，2008：1－6.

［5］Lee W L，Datta A，Cardell-Oliver R.FlexiTP：A Flexible-Schedule-Based TDMA Protocol for Fault-Tolerant and Energy-Efficient Wireless Sensor Networks［J］.Transactions on Parallel and Distributed Systems，2008，19（6）：851－864.

［6］Zhiqiang Xiong，ZongkaiYang，WeiLiu，etal.A Lightweight FEC Algorithm for Fault Tolerant Routing in Wireless Sensor Networks［C］／／Proceedings of 2006 International Conference on Wireless Communications，Networking and Mobile Computing.Wuhan：IEEE，2006：1－4.

［7］Khadivi A，Shiva M.FTPASC：A Fault Tolerant Power Aware Protocol with Static Clustering for Wireless Sensor Networks［C］／／Proceedings of 2006 IEEE International Conference on Wireless and Mobile Computing，Networking and Communications.Montreal，Que：IEEE，2006：397－401.

［8］Xin-Ming Huang，Jing Deng，Jing M，et al.Fault tolerant routing for wireless sensor grid networks［C］／／Proceedings of 2006 IEEE Sensors Applications Symposium.Luoyang：IEEE，2006：66－70.

［9］Karim Lutful，Nasser Nidal，Sheltami Tarek.A Fault Tolerant Dynamic Clustering Protocol of Wireless Sensor Networks［C］／／Proceedings of 2009 IEEE International Conference on Global Telecommunications.Honolulu，HI：IEEE，2009：1－6.

［10］刘志，裘正定.基于分环多跳的无线传感网分簇路由算法［J］.通信学报，2008，29（3）：104－113.

LIU Zhi，QIU Zheng－ding.Ring based multi－hop clustering routing algorithm for wireless sensor networks［J］.Journal on Communications，2008，29（3）：104－113.（in Chinese）

［11］Lindsey Stephanie，Raghavendra CauligiSivalingam，Krishna M.Data Gathering Algorithms in Sensor Networks Using Energy Metrics［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（9）：924－935.

［12］李洪兵，余成波，陈强，等.基于BW AS的无线传感器网络静态分簇路由算法［J］.电讯技术，2010，50（4）：96－101.

LI Hong-bing，YU Cheng-bo，CHEN Qiang，et al.Static Clustering Routing Algorithm Based on Best Worst Ant System for Wireless Sensor Networks［J］.Telecommunication Engineering，2010，50（4）：96－101.（in Chinese）

LI Hong－bing was born in Tongnan，Chongqing，in 1981.He is now a lecturer and also a graduate student.His research interests include intelligent signal processing and wireless sensor network.

Email：sxxylhb＠163.com

余成波（1965－），男，博士，教授，重庆理工大学硕士生导师，中北大学博士生导师，重庆市学术技术带头人。主要研究领域为信息获取与处理技术、远程测试与控制技术和车辆电子技术；

YU Cheng－bo was born in 1965.He is now a professor with the Ph.D.degree.He is master tutor of Chongqing University of Technology and also the Ph.D.supervisor of North University of China，leader of Chongqing academic and technology.His research interests include information acquisition and processing，remote testing and controlling technology and vehicle electronics.

Email：yuchengbo＠cqut.edu.cn

全晓莉（1975－），女，重庆潼南人，硕士研究生，讲师，主要研究方向为信号处理、虚拟仪器软件开发；

QUAN Xiao－li was born in Tongnan，Chongqing，in 1975. She is now a lecturer and also a graduate student.Her research interests include signal processing and virtual instrument software development.

Email：znq55555＠163.com

刘峪王宣（1986－），男，江苏仪征人，硕士研究生，主要研究方向为无线传感器网络。

LIU Yu－xuan was born in Yizheng，Jiangsu Province，in 1986.He is now a graduate student.His research direction is wireless sensor network.

Email：biergaici2025＠126.com

Fault-Tolerant Vascular Routing Algorithm for Wireless Sensor Networks

LI Hong-bing1，2，YU Cheng-bo1，QUAN Xiao-li1，LIU Yu-xuan1
（1.Research Institute of Remote Test and Control，Chongqing University of Technology，Chongqing 400054，China；2.Chongqing Three Gorges University，Chongqing 404000，China）

In order to enhance fault tolerance and transmission stability of wireless sensor networks（WSNs），as well as the network loads balance，a fault tolerant routing algorithm imitating human blood vessel is presented. The properties of human blood vessels are stndied，and static clustering is performed by using the different probabilities after the nodes of the network are marked with different grades.Best-Worst Ant System（BWAS），an improved ant colony algorithm，is used to generate the paths and calculate the paths′pheromones as to be the probability of the path selection.So the vascular routing is established.It has more than one transmission paths and chooses the path of highest probability to establish the actual transmission route.It avoids the data losses or delay caused by the failures of nodes or links，improves the fault tolerance of the network as well as the transmission stability，balances the power consumption in the whole network.Analysis and simulation show that the algorithm has good performance.

wireless sensor network（WSN）；fault tolerance；routing protocol；blood vessel；BWAS algorithm

The Natural Science Foundation of Chongqing（CSTC2007BA2023）；Science and Technology Project of Jiulongpo，Chongqing（Science and Technology Commission of Jiulongpo［2009］52）；Science and Technology Innovation Project of Chongqing（Economic and Information Technology of Chongqing［2010］9）；Science and Technology Project of Wanzhou，Chongqing（Science and Technology Commission of Wanzhou［2010］23）

TP393；TP212

A

10.3969／j.issn.1001－893x.2011.02.011

李洪兵（1981－），男，重庆潼南人，硕士研究生，讲师，主要研究方向为智能信号处理、无线传感器网络；

1001－893X（2011）02－0056－06

2010－10－21；

2010－12－08

重庆市自然科学基金重点项目（CSTC2007BA2023）；重庆市九龙坡科技计划项目（九龙坡科委发［2009］52号）；重庆市科技创新项目（渝经信科技［2010］9号）；重庆市万州科技计划项目（万州科委［2010］23号）