基于可靠性在结构健康监测系统中的备份点布控研究
诸震亚 邵方明
关键词： 结构健康监测; 点失效模型; 无线传感器网络; 网络性能; 优化策略; 可靠性
中图分类号： TN929.5?34 ? ? ? ? ? ? ? ? ?文献标识码： A ? ? ? ? ? ? ? ? ? ? ? ? ? 文章编号： 1004?373X（2019）04?0148?05
Research on reliability?based backup node deployment in
structural health monitoring system
ZHU Zhenya， SHAO Fangming
（East China University of Science and Technology， Shanghai 200237， China）
Abstract： In order to optimize the deployment of backup sensors in the structural health monitoring system， the node failure model reliability approach is introduced to evaluate network performance. An optimization problem is considered that how to make the network reliability determine the threshold R0 ?with the fewest backup sensors deployed. The location topology is converted to the wireless sensor network topology while preserving the network reliability. A method of improving network reliability is proposed， and the upper bound for the reliability of the class Ω（n，m） is proved. The optimization strategy of backup sensors is given， which is called the INR?R0 algorithm. The results of the simulation experiment show that in comparison with the BSP and FEM algorithms， the INR?R0 algorithm can ensure that the network reliability exceeds the threshold R0 when only a few backup sensors are added in the actual building network structure.
Keywords： structural health monitoring; node failure model; wireless sensor network; network performance; optimization strategy; reliability0 ?引 ?言
结构健康监测（Structural Health Monitoring， SHM）定期从传感器采集动态响应数据，以此数据分析观察该结构体系随时间变化的情况，用传感器采集的数据特征反映结构的健康状况，并用这些动态响应数据评估系统对结构损伤的敏感性以及对异常事件的快速分析能力。对于长期服役的建筑（如高楼、桥梁），监测其关键部位的安全情况对本身以及社会安全都有着重大意义[1?3]。
传感器技术在连接计算机世界和物理世界有着关键作用，而对比有线传感器来说，无线传感器需要低功耗、易于部署、探测精度高、容错性好，且可以远程监控，所以无线传感器网络（Wireless Sensor Network，WSN）在系统应用中比有线网络更常见、实用。在实际应用中，监测系统的重要参考指标有：监测系统的经济性、可靠性以及有效性等。而从可靠性角度考虑监测系统的性能时，其基本要求之一便是传感器位置优化，使得部署在系统中的无线传感器网络可以对结构性能得到最佳估计[4?5]。因此，需要对结构中传感器的部署位置进行设计和优化。对于传感器的位置优化，Kim等人首先通过有效独立值（EFI）来确定主要传感器的位置[4，6?7]。其中EFI使用模态振型和噪声测量，然后提供Fisher信息矩阵（FIM）行列式来计算EFI值。该值被称为部署质量指标。结构中每个位置都对应着特定的EFI值，这是确定结构中主要传感器位置的有效方法，EFI值越大，表示在该放置越好。文献[3，8]中便是基于EFI值来优化无线传感器的部署。Bhuiyan等人在文献[9]提出了基于WSN的SHM需要保证一定的容错能力，使得在网络出现故障时，网络依然处于正常工作状态;并提出了BSP算法来部署备份传感器，以提高网络的容错性。
本文首次将网络可靠性定义应用在结构健康监测系统中，并在原网络基础上增加备份节点来提高网络的可靠性，使得结构健康监测系统更稳定和全面地监测整个建筑系统。1 ?系统模型和问题形成
网络可靠性是衡量网络性能的一个重要指标。网络可靠性模型通常分为：点失效模型、边失效模型、点边失效模型。在结构健康监测系统中，传感器的主要位置可通过EFI值确定，因此本文基于点失效模型仅研究备份传感器的部署问题。
1.1 ?系统模型
考虑有M个候选位置（可部署传感器位置）和N1个主要传感器，且每个位置只能部署一个传感器的SHM系统。通常根据EFI值将N1个主要传感器部署在N1个候选位置上。
在SHM系统中，传感器的位置状态矩阵为：
[X=x11x12…x1mx21x22…x2m????xn1xn2…xnm] ? ? ? ? ?（1）
式中，xij（1≤i≤n，1≤j≤m）表示位置（i，j）处是否部署传感器。当xij=0时，表示位置（i，j）未布控传感器;当xij=1时，表示位置（i，j）已布控传感器。
定义1 部署传感器的位置数为：
[S（X）=injmxij] ? ? ? ? ? ? （2）
部署备份传感器数为：
[BX=SX-SX0] （3）
式中，[X0]表示SHM系统的初始位置状态矩阵。
当两个传感器之间的距离小于通信半径rs时，它们在网络中形成一条边。这些传感器节点和边就组成了WSN网络G。在点失效模型中，网络G的边不失效，节点正常运行的概率为p，其可靠性为：
[RG，p=r=1nSr（G）prqn-r=r=1n（Crn-Cr（G））prqn-r] （4）
式中：[Sr（G）]为网络G中包含r个节点的诱导子图的个数[10];[Cr（G）]在网络G中删除r个节点导致网络不连通的诱导子图的个数。
定义2 传感器网络G的可靠性函数为：
[f（X，p）=rnSr（G）prqn-r] ? ? ?（5）
一般地，对任意一个连通图G，图的点连通度κ（G）就是该图的最小点割集的数目[10]。对任意属于类Ω（n，m）的图G，都有：
[κ（G）≤2mn] ? ? ? ? ? ? （6）
如果G是完全图，则有[κ（G）=n-1]，其中Ω（n，m）表示一类包括n个点m条边的图簇。而一致最优图是类Ω（n，m）中不论节点运行的概率取何值时，可靠性始终最大的图。而在实际生活中，传感器节点成功通信的概率通常比较高，所以只需考虑某个范围内的概率，即考虑局部最优图。
定义3 局部最优图是指在类Ω（n，m）中，节点运行的概率大于或等于某定值时，可靠性始终最大。
对于备份传感器部署问题，将位置拓扑转换为WSN拓扑同时保持其可靠性具有重要实际意义。通过数学描述和定义，使用网络可靠性优化替代传感器位置优化可以较容易理解。
1.2 ?数学描述
每个候选位置处最多只能部署一个传感器，考虑这样一个优化问题：在保证网络的可靠性R大于给定阈值R0前提下，添加最少的备份传感器数量。那么，在SHM系统中，对给定的M个候选位置，N1个主要传感器和传感器成功运行概率p，上述优化问题可以描述为：
[minxBXs.t. ? ?fX，p≥R0 ? ? ?BX≤M-N1] （7）
这里传感器的位置状态矩阵X的数量至多2M个。
为了解决式（7）的优化问题，首先利用位置状态矩阵X将位置拓扑转化成网络结构G。由于网络G的规模会随着候选位置的数量M成指数增长，所以枚举法所消耗的时间也会成指数级增长，因而实际生活中的应用意义不大。针对此问题，本文首先给出增加一个备份节点后网络可靠性的一个上界;然后利用降序度序列来布控备份传感器，给出网络可靠性增强（Increase the Reliability of Network）算法：INR?R0。
2 ?INR?R0算法
本节对备份传感器有效位置和可靠性上界进行理论分析，并设计确定最少备份传感器的INR?R0算法。
2.1 ?理论分析
首先利用定理1确定部署备份传感器的有效位置。
定理1 令网络G属于类Ω（n，m），G′是在G中添加一个点y，当d（y）=n时，有R（G′） ≥ R（G），且R（G′）=p + qR（G）。
证明：将网络G看作概率为[R（G）=rnSr（G）prqn-r]的节点，那么网络G′的可靠性为：
[R（G′）=p1-r=1nSr（G）prqn-r+r=1nSr（G）prqn-rq+pr=1nSr（G）prqn-r=p+qr=1nSr（G）prqn-r=p+qR（G）]
则
[R（G′）-R（G）=p+qr=1nSr（G）prqn-r-r=1nSr（G）prqn-r ? ? ? ? ? ? ? ? ? ? ? ? ? ?=p+qR（G）-R（G）=p-pR（G） ? ? ? ? ? ? ? ? ? ? ? ? ? ?=p（1-R（G））]
由于R（G）?（0，1），所以R（G′）≥R（G）。
定理1给出了一种增加备份节点后提高网络可靠性的方法。接下来，将给出类Ω（n，m）可靠性的一个上界。
定理2 在图G ? Ω（n，m）中添加一个节点后，当其成功运行的概率p趋近1时，此时图的可靠性上界为：
[R=minp+qRG，Rn+1] （8）
式中：R（G）为图G的可靠性;[n≤m≤n24];
[Rn+1=1-i>2n+12Cin+12+Cin+12piqn-i+1+pn+12qn-n+12+1]
证明：首先证明在类Ω（n，m）中，非正则图的点连通度小于拟正则二部图的点连通度。在类Ω（n，m）中，任意非正则图G的度序列为[d1，d2，…，dn]。其中d1 ≤d2 ≤…≤dn;拟正则二部图G*的度序列为[d1，d2，…，dn]=[α，α，…，α，α+1，…，α+1]。由割集的定义可知κ（G）≤d1，κ（G*）=α。而在非正则图中必存在d1<α和dn>α+1，所以κ（G）<κ（G*），即非正则图的点连通度小于拟正则二部图的点连通度。
然后证明当节点成功运行的概率p趋近1时，类Ω（n，m）中局部最优图的度序列均匀。由割集的定义可知κ（G*）=α，且C1（G*）=C2（G*）= …=Cα?1（G*）=0。又因为κ（G）≤d1<α，Cα-1（G）>0，则当p趋于1时，有R（G，p）<R（G*，p），即度序列不均匀的图不是局部最优图。
最后证明添加一个节点后图的可靠性上界为[R] = min{p+qR（G），Rn+1}。当[n≤m≤n24]时，拟正则二部图是其类里的局部最优图[11]，那么含有n个节点的图G上界为：
[Rn=1-i>2n2Cin2+Cin2piqn-i+pn2qn-n2]
结合定理1，在图1 G中添加一个节点后，图的可靠性上界为：
[R=minp+qRG，Rn+1]
2.2 ?算法设计与分析
一种提高网络容错能力的方法是在原来的主要位置处添加备份节点[9]。该方法能提高单个节点成功运行的概率，然而有时并不能提高该网络的可靠性。因此本节提出了一种在节点成功运行概率较高时，提高网络可靠性的INR?R0算法。
首先，从G（V，E）中得到节点的度序列[DN1]，其中G（V，E）表示以V为点集，E为边集的网络，[V=N1=n，][E=m]。并利用定理2得到当网络可靠性高于某个阈值R0时，所需要添加最少的节点数a。
然后，在点集V的通信半径rs内，求出M-N1个备份位置处l的点度dl，进而得到度序列[DM-N1]。接着，根据定理1找到满足dl≥N1的集合S。最后，在備份位置处添加节点;当a ≤[S]时，从[S]选a个位置添加节点;当[S]<a≤M-N1时，先部署S中的节点，然后在剩下[a-S]个位置部署备份传感器，其原则为：先找到[DN1]中最小点度的位置ldmin，然后在[DM-N1]中靠近ldmin处最大点度位置部署节点。从M-N1中选择a个位置部署节点后计算R（Ga），递归执行上述操作直到R≥R0或者a>M-N1，输出最少备份节点数B（X）=a。其具体算法如下。
算法：INR?R0（M，N1，G，p，rs）
输入：网络G（V，E），候选位置数M，主要传感器数N1，定值R0，点正常通信概率p，连通半径rs。
在INR?R0算法中，确定最少节点数a，度序列[DN1，DM-N1]以及集合S的复杂度均为O（n）;同时由于计算R（G）是一个NP?难问题，所以该算法的复杂度也是源于R（G）的计算复杂度。3 ?实验仿真
3.1 ?仿真1
INR?R0示例如图2所示，虚线交点为候选位置（M=25）。v1，v2，v3，v4，v5，v6是主要位置（N1=6），备份位置数为M-N1。对于给定的R0=0.95，通信半径[rs=5]和节点正常运行的概率p=0.8，仿真结果如表1所示。
表1给出了在原网络中加入备份节点之后网络的可靠性，图G1的可靠性为R（G1，p）=0.552 4<R0。根据INR?R0算法，在图中添加一个备份节点后，网络可靠性上界为：[R]=min{p+qR（G1，p），R7}=0.910 5<R0。添加备份节点后，其可靠性上界为：[R]= 0.982 1>R0。得到网络的度序列为[DM?N1]=[2，2，2，2，3，4，3，3，4，6，3，2，3，3，3，2， 2，3，1]，集合S={10}。首先在网络G1中的位置10处添加节点得到网络G2，R（G2，p）=p+qR（G1，p）= 0.910 5<R0，需要继续添加节点;由于dmax=max[{DM?N1d10}=d6]，接着在G2中的位置6处添加节点得到网络G3，R（G3，p） = 0.951 4>R0，所以B（X）=2。因此，对于给定R0=0.95，最少需要添加两个备份节点就可使得网络可靠性大于R0。
3.2 ?仿真2
利用文献[9]中一个位于中国香港的建筑（Lee Shao Kee， LSK）作为测试网络。根据算法INR?R0确定部署备份传感器的位置，结果如图3所示。图中，G5，G6，G7中黑点分别是通过算法INR?R0，BSP[9]，FEM[4]确定的备份传感器部署的位置。
从图4和表2中可以看出，当传感器节点成功运行的概率p=0.8，R0=0.7时，INR?R0需要添加2个备份传感器，BSP和FEM算法分别需要添加6和大于6个备份传感器;当0.5<R0 <0.65时，INR?R0，BSP，FEM算法分别需要添加2，5，4个备份传感器;当0.4<R0<0.5时，INR?R0，BSP，FEM算法分别需要添加1，1，3个备份传感器。与BSP算法和FEM算法相比，INR?R0算法需要添加更少的备份传感器就可使得网络的可靠性大于确定阈值R0，表明了算法的有效性。4 ?结 ?论
本文将SHM系统中传感器部署策略转化为无线传感器网络的可靠性优化问题。为了解决可靠性优化问题，本文提出一种新的提高网络可靠性的方法，并给出一类图的可靠性上界，进而提出一种新的无线传感器节点部署的INR?R0算法。仿真结果表明，与BSP和FEM算法相比，INR?R0算法只需添加更少的备份传感器就可使得网络的可靠性大于确定阈值R0，表明了算法的有效性。
注：本文通讯作者为邵方明。
参考文献
[1] CHEN Z， QIAO C， QIU Y， et al. Dynamics stability in wireless sensor networks active defense model [J]. Journal of computer & system sciences， 2014， 80（8）： 1534?1548.
[2] 孙小猛，冯新，周晶.基于损伤可识别性的传感器优化布置方法[J].大连理工大学学报，2010，50（2）：264?270.
SUN Xiaomeng， FENG Xin， ZHOU Jing. A method for optimum sensor placement based on damage identifiability [J]. Journal of Dalian University of Technology， 2010， 50（2）： 264?270.
[3] 张国柱，张文川，潘宝志，等.隧道无线健康监测系统环境敏感性分析[J].公路交通技术，2014（3）：109?112.
ZHANG Guozhu， ZHANG Wenchuan， PAN Baozhi， et al. Analysis for environmental sensitivity of tunnel wireless health monitoring system [J]. Technology of highway and transport， 2014（3）： 109?112.
[4] KIM S， PAKZAD S， CULLER D， et al. Health monitoring of civil infrastructures using wireless sensor networks [C]// Proceedings of 6th International Symposium on Information Processing in Sensor Networks. Cambridge： IEEE， 2007： 254?263.
[5] HACKMANN G， SUN F， CASTANEDA N， et al. A holistic approach to decentralized structural damage localization using wireless sensor networks [J]. Computer communications， 2012， 36（1）： 29?41.
[6] CHEBROLU K， RAMAN B， MISHRA N， et al. Brimon： a sensor network system for railway bridge monitoring [C]// Proceedings of the 6th International Conference on Mobile Systems， Applications and Services. Breckenridge： DBLP， 2008： 2?14.
[7] LI B， WANG D， WANG F， et al. High quality sensor placement for SHM systems： refocusing on application demands [C]// Proceedings of IEEE International Conference on Computer Communications. San Diego： IEEE， 2010： 650?658.
[8] MEO M， ZUMPANO G. On the optimal sensor placement techniques for a bridge structure [J]. Engineering structures， 2005， 27（10）： 1488?1497.
[9] BHUIYAN M Z A， CAO J， WANG G. Deploying wireless sensor networks with fault tolerance for structural health monitoring [C]// Proceedings of IEEE 8th International Conference on Distributed Computing in Sensor Systems. Hangzhou： IEEE， 2012： 194?202.
[10] YU S， SHAO F， MENG H， et al. Uniformly optimal graphs in some classes of graphs with node failures [J]. Discrete mathematics， 2010， 310（1）： 159?166.
[11] ZHANG Z， AN W， SHAO F. Cascading failures on reliability in cyber?physical system [J]. IEEE transactions on reliability， 2016， 65（4）： 1745?1754.
[12] ZHU Z， SHAO F， ZHAN Z. Research on node deployment in structural health monitoring based on reliability [C]// Proceedings of the 7th International Conference on Computer Engineering and Networks. Shanghai： [s.n.]， 2017： 1?7.
关键词： 结构健康监测; 点失效模型; 无线传感器网络; 网络性能; 优化策略; 可靠性
中图分类号： TN929.5?34 ? ? ? ? ? ? ? ? ?文献标识码： A ? ? ? ? ? ? ? ? ? ? ? ? ? 文章编号： 1004?373X（2019）04?0148?05
Research on reliability?based backup node deployment in
structural health monitoring system
ZHU Zhenya， SHAO Fangming
（East China University of Science and Technology， Shanghai 200237， China）
Abstract： In order to optimize the deployment of backup sensors in the structural health monitoring system， the node failure model reliability approach is introduced to evaluate network performance. An optimization problem is considered that how to make the network reliability determine the threshold R0 ?with the fewest backup sensors deployed. The location topology is converted to the wireless sensor network topology while preserving the network reliability. A method of improving network reliability is proposed， and the upper bound for the reliability of the class Ω（n，m） is proved. The optimization strategy of backup sensors is given， which is called the INR?R0 algorithm. The results of the simulation experiment show that in comparison with the BSP and FEM algorithms， the INR?R0 algorithm can ensure that the network reliability exceeds the threshold R0 when only a few backup sensors are added in the actual building network structure.
Keywords： structural health monitoring; node failure model; wireless sensor network; network performance; optimization strategy; reliability0 ?引 ?言
结构健康监测（Structural Health Monitoring， SHM）定期从传感器采集动态响应数据，以此数据分析观察该结构体系随时间变化的情况，用传感器采集的数据特征反映结构的健康状况，并用这些动态响应数据评估系统对结构损伤的敏感性以及对异常事件的快速分析能力。对于长期服役的建筑（如高楼、桥梁），监测其关键部位的安全情况对本身以及社会安全都有着重大意义[1?3]。
传感器技术在连接计算机世界和物理世界有着关键作用，而对比有线传感器来说，无线传感器需要低功耗、易于部署、探测精度高、容错性好，且可以远程监控，所以无线传感器网络（Wireless Sensor Network，WSN）在系统应用中比有线网络更常见、实用。在实际应用中，监测系统的重要参考指标有：监测系统的经济性、可靠性以及有效性等。而从可靠性角度考虑监测系统的性能时，其基本要求之一便是传感器位置优化，使得部署在系统中的无线传感器网络可以对结构性能得到最佳估计[4?5]。因此，需要对结构中传感器的部署位置进行设计和优化。对于传感器的位置优化，Kim等人首先通过有效独立值（EFI）来确定主要传感器的位置[4，6?7]。其中EFI使用模态振型和噪声测量，然后提供Fisher信息矩阵（FIM）行列式来计算EFI值。该值被称为部署质量指标。结构中每个位置都对应着特定的EFI值，这是确定结构中主要传感器位置的有效方法，EFI值越大，表示在该放置越好。文献[3，8]中便是基于EFI值来优化无线传感器的部署。Bhuiyan等人在文献[9]提出了基于WSN的SHM需要保证一定的容错能力，使得在网络出现故障时，网络依然处于正常工作状态;并提出了BSP算法来部署备份传感器，以提高网络的容错性。
本文首次将网络可靠性定义应用在结构健康监测系统中，并在原网络基础上增加备份节点来提高网络的可靠性，使得结构健康监测系统更稳定和全面地监测整个建筑系统。1 ?系统模型和问题形成
网络可靠性是衡量网络性能的一个重要指标。网络可靠性模型通常分为：点失效模型、边失效模型、点边失效模型。在结构健康监测系统中，传感器的主要位置可通过EFI值确定，因此本文基于点失效模型仅研究备份传感器的部署问题。
1.1 ?系统模型
考虑有M个候选位置（可部署传感器位置）和N1个主要传感器，且每个位置只能部署一个传感器的SHM系统。通常根据EFI值将N1个主要传感器部署在N1个候选位置上。
在SHM系统中，传感器的位置状态矩阵为：
[X=x11x12…x1mx21x22…x2m????xn1xn2…xnm] ? ? ? ? ?（1）
式中，xij（1≤i≤n，1≤j≤m）表示位置（i，j）处是否部署传感器。当xij=0时，表示位置（i，j）未布控传感器;当xij=1时，表示位置（i，j）已布控传感器。
定义1 部署传感器的位置数为：
[S（X）=injmxij] ? ? ? ? ? ? （2）
部署备份传感器数为：
[BX=SX-SX0] （3）
式中，[X0]表示SHM系统的初始位置状态矩阵。
当两个传感器之间的距离小于通信半径rs时，它们在网络中形成一条边。这些传感器节点和边就组成了WSN网络G。在点失效模型中，网络G的边不失效，节点正常运行的概率为p，其可靠性为：
[RG，p=r=1nSr（G）prqn-r=r=1n（Crn-Cr（G））prqn-r] （4）
式中：[Sr（G）]为网络G中包含r个节点的诱导子图的个数[10];[Cr（G）]在网络G中删除r个节点导致网络不连通的诱导子图的个数。
定义2 传感器网络G的可靠性函数为：
[f（X，p）=rnSr（G）prqn-r] ? ? ?（5）
一般地，对任意一个连通图G，图的点连通度κ（G）就是该图的最小点割集的数目[10]。对任意属于类Ω（n，m）的图G，都有：
[κ（G）≤2mn] ? ? ? ? ? ? （6）
如果G是完全图，则有[κ（G）=n-1]，其中Ω（n，m）表示一类包括n个点m条边的图簇。而一致最优图是类Ω（n，m）中不论节点运行的概率取何值时，可靠性始终最大的图。而在实际生活中，传感器节点成功通信的概率通常比较高，所以只需考虑某个范围内的概率，即考虑局部最优图。
定义3 局部最优图是指在类Ω（n，m）中，节点运行的概率大于或等于某定值时，可靠性始终最大。
对于备份传感器部署问题，将位置拓扑转换为WSN拓扑同时保持其可靠性具有重要实际意义。通过数学描述和定义，使用网络可靠性优化替代传感器位置优化可以较容易理解。
1.2 ?数学描述
每个候选位置处最多只能部署一个传感器，考虑这样一个优化问题：在保证网络的可靠性R大于给定阈值R0前提下，添加最少的备份传感器数量。那么，在SHM系统中，对给定的M个候选位置，N1个主要传感器和传感器成功运行概率p，上述优化问题可以描述为：
[minxBXs.t. ? ?fX，p≥R0 ? ? ?BX≤M-N1] （7）
这里传感器的位置状态矩阵X的数量至多2M个。
为了解决式（7）的优化问题，首先利用位置状态矩阵X将位置拓扑转化成网络结构G。由于网络G的规模会随着候选位置的数量M成指数增长，所以枚举法所消耗的时间也会成指数级增长，因而实际生活中的应用意义不大。针对此问题，本文首先给出增加一个备份节点后网络可靠性的一个上界;然后利用降序度序列来布控备份传感器，给出网络可靠性增强（Increase the Reliability of Network）算法：INR?R0。
2 ?INR?R0算法
本节对备份传感器有效位置和可靠性上界进行理论分析，并设计确定最少备份传感器的INR?R0算法。
2.1 ?理论分析
首先利用定理1确定部署备份传感器的有效位置。
定理1 令网络G属于类Ω（n，m），G′是在G中添加一个点y，当d（y）=n时，有R（G′） ≥ R（G），且R（G′）=p + qR（G）。
证明：将网络G看作概率为[R（G）=rnSr（G）prqn-r]的节点，那么网络G′的可靠性为：
[R（G′）=p1-r=1nSr（G）prqn-r+r=1nSr（G）prqn-rq+pr=1nSr（G）prqn-r=p+qr=1nSr（G）prqn-r=p+qR（G）]
则
[R（G′）-R（G）=p+qr=1nSr（G）prqn-r-r=1nSr（G）prqn-r ? ? ? ? ? ? ? ? ? ? ? ? ? ?=p+qR（G）-R（G）=p-pR（G） ? ? ? ? ? ? ? ? ? ? ? ? ? ?=p（1-R（G））]
由于R（G）?（0，1），所以R（G′）≥R（G）。
定理1给出了一种增加备份节点后提高网络可靠性的方法。接下来，将给出类Ω（n，m）可靠性的一个上界。
定理2 在图G ? Ω（n，m）中添加一个节点后，当其成功运行的概率p趋近1时，此时图的可靠性上界为：
[R=minp+qRG，Rn+1] （8）
式中：R（G）为图G的可靠性;[n≤m≤n24];
[Rn+1=1-i>2n+12Cin+12+Cin+12piqn-i+1+pn+12qn-n+12+1]
证明：首先证明在类Ω（n，m）中，非正则图的点连通度小于拟正则二部图的点连通度。在类Ω（n，m）中，任意非正则图G的度序列为[d1，d2，…，dn]。其中d1 ≤d2 ≤…≤dn;拟正则二部图G*的度序列为[d1，d2，…，dn]=[α，α，…，α，α+1，…，α+1]。由割集的定义可知κ（G）≤d1，κ（G*）=α。而在非正则图中必存在d1<α和dn>α+1，所以κ（G）<κ（G*），即非正则图的点连通度小于拟正则二部图的点连通度。
然后证明当节点成功运行的概率p趋近1时，类Ω（n，m）中局部最优图的度序列均匀。由割集的定义可知κ（G*）=α，且C1（G*）=C2（G*）= …=Cα?1（G*）=0。又因为κ（G）≤d1<α，Cα-1（G）>0，则当p趋于1时，有R（G，p）<R（G*，p），即度序列不均匀的图不是局部最优图。
最后证明添加一个节点后图的可靠性上界为[R] = min{p+qR（G），Rn+1}。当[n≤m≤n24]时，拟正则二部图是其类里的局部最优图[11]，那么含有n个节点的图G上界为：
[Rn=1-i>2n2Cin2+Cin2piqn-i+pn2qn-n2]
结合定理1，在图1 G中添加一个节点后，图的可靠性上界为：
[R=minp+qRG，Rn+1]
2.2 ?算法设计与分析
一种提高网络容错能力的方法是在原来的主要位置处添加备份节点[9]。该方法能提高单个节点成功运行的概率，然而有时并不能提高该网络的可靠性。因此本节提出了一种在节点成功运行概率较高时，提高网络可靠性的INR?R0算法。
首先，从G（V，E）中得到节点的度序列[DN1]，其中G（V，E）表示以V为点集，E为边集的网络，[V=N1=n，][E=m]。并利用定理2得到当网络可靠性高于某个阈值R0时，所需要添加最少的节点数a。
然后，在点集V的通信半径rs内，求出M-N1个备份位置处l的点度dl，进而得到度序列[DM-N1]。接着，根据定理1找到满足dl≥N1的集合S。
最后，在備份位置处添加节点;当a ≤[S]时，从[S]选a个位置添加节点;当[S]<a≤M-N1时，先部署S中的节点，然后在剩下[a-S]个位置部署备份传感器，其原则为：先找到[DN1]中最小点度的位置ldmin，然后在[DM-N1]中靠近ldmin处最大点度位置部署节点。从M-N1中选择a个位置部署节点后计算R（Ga），递归执行上述操作直到R≥R0或者a>M-N1，输出最少备份节点数B（X）=a。其具体算法如下。算法：INR?R0（M，N1，G，p，rs）
输入：网络G（V，E），候选位置数M，主要传感器数N1，定值R0，点正常通信概率p，连通半径rs。
在INR?R0算法中，确定最少节点数a，度序列[DN1，DM-N1]以及集合S的复杂度均为O（n）;同时由于计算R（G）是一个NP?难问题，所以该算法的复杂度也是源于R（G）的计算复杂度。3 ?实验仿真
3.1 ?仿真1
INR?R0示例如图2所示，虚线交点为候选位置（M=25）。v1，v2，v3，v4，v5，v6是主要位置（N1=6），备份位置数为M-N1。对于给定的R0=0.95，通信半径[rs=5]和节点正常运行的概率p=0.8，仿真结果如表1所示。
表1给出了在原网络中加入备份节点之后网络的可靠性，图G1的可靠性为R（G1，p）=0.552 4<R0。根据INR?R0算法，在图中添加一个备份节点后，网络可靠性上界为：[R]=min{p+qR（G1，p），R7}=0.910 5<R0。添加备份节点后，其可靠性上界为：[R]= 0.982 1>R0。得到网络的度序列为[DM?N1]=[2，2，2，2，3，4，3，3，4，6，3，2，3，3，3，2， 2，3，1]，集合S={10}。首先在网络G1中的位置10处添加节点得到网络G2，R（G2，p）=p+qR（G1，p）= 0.910 5<R0，需要继续添加节点;由于dmax=max[{DM?N1d10}=d6]，接着在G2中的位置6处添加节点得到网络G3，R（G3，p） = 0.951 4>R0，所以B（X）=2。因此，对于给定R0=0.95，最少需要添加两个备份节点就可使得网络可靠性大于R0。
3.2 ?仿真2
利用文献[9]中一个位于中国香港的建筑（Lee Shao Kee， LSK）作为测试网络。根据算法INR?R0确定部署备份传感器的位置，结果如图3所示。
图中，G5，G6，G7中黑点分别是通过算法INR?R0，BSP[9]，FEM[4]确定的备份传感器部署的位置。从图4和表2中可以看出，当传感器节点成功运行的概率p=0.8，R0=0.7时，INR?R0需要添加2个备份传感器，BSP和FEM算法分别需要添加6和大于6个备份传感器;当0.5<R0 <0.65时，INR?R0，BSP，FEM算法分别需要添加2，5，4个备份传感器;当0.4<R0<0.5时，INR?R0，BSP，FEM算法分别需要添加1，1，3个备份传感器。与BSP算法和FEM算法相比，INR?R0算法需要添加更少的备份传感器就可使得网络的可靠性大于确定阈值R0，表明了算法的有效性。4 ?结 ?论
本文将SHM系统中传感器部署策略转化为无线传感器网络的可靠性优化问题。为了解决可靠性优化问题，本文提出一种新的提高网络可靠性的方法，并给出一类图的可靠性上界，进而提出一种新的无线传感器节点部署的INR?R0算法。仿真结果表明，与BSP和FEM算法相比，INR?R0算法只需添加更少的备份传感器就可使得网络的可靠性大于确定阈值R0，表明了算法的有效性。
注：本文通讯作者为邵方明。
参考文献
[1] CHEN Z， QIAO C， QIU Y， et al. Dynamics stability in wireless sensor networks active defense model [J]. Journal of computer & system sciences， 2014， 80（8）： 1534?1548.
[2] 孙小猛，冯新，周晶.基于损伤可识别性的传感器优化布置方法[J].大连理工大学学报，2010，50（2）：264?270.
SUN Xiaomeng， FENG Xin， ZHOU Jing. A method for optimum sensor placement based on damage identifiability [J]. Journal of Dalian University of Technology， 2010， 50（2）： 264?270.
[3] 张国柱，张文川，潘宝志，等.隧道无线健康监测系统环境敏感性分析[J].公路交通技术，2014（3）：109?112.
ZHANG Guozhu， ZHANG Wenchuan， PAN Baozhi， et al. Analysis for environmental sensitivity of tunnel wireless health monitoring system [J]. Technology of highway and transport， 2014（3）： 109?112.
[4] KIM S， PAKZAD S， CULLER D， et al. Health monitoring of civil infrastructures using wireless sensor networks [C]// Proceedings of 6th International Symposium on Information Processing in Sensor Networks. Cambridge： IEEE， 2007： 254?263.
[5] HACKMANN G， SUN F， CASTANEDA N， et al. A holistic approach to decentralized structural damage localization using wireless sensor networks [J]. Computer communications， 2012， 36（1）： 29?41.
[6] CHEBROLU K， RAMAN B， MISHRA N， et al. Brimon： a sensor network system for railway bridge monitoring [C]// Proceedings of the 6th International Conference on Mobile Systems， Applications and Services. Breckenridge： DBLP， 2008： 2?14.
[7] LI B， WANG D， WANG F， et al. High quality sensor placement for SHM systems： refocusing on application demands [C]// Proceedings of IEEE International Conference on Computer Communications. San Diego： IEEE， 2010： 650?658.
[8] MEO M， ZUMPANO G. On the optimal sensor placement techniques for a bridge structure [J]. Engineering structures， 2005， 27（10）： 1488?1497.
[9] BHUIYAN M Z A， CAO J， WANG G. Deploying wireless sensor networks with fault tolerance for structural health monitoring [C]// Proceedings of IEEE 8th International Conference on Distributed Computing in Sensor Systems. Hangzhou： IEEE， 2012： 194?202.
[10] YU S， SHAO F， MENG H， et al. Uniformly optimal graphs in some classes of graphs with node failures [J]. Discrete mathematics， 2010， 310（1）： 159?166.
[11] ZHANG Z， AN W， SHAO F. Cascading failures on reliability in cyber?physical system [J]. IEEE transactions on reliability， 2016， 65（4）： 1745?1754.
[12] ZHU Z， SHAO F， ZHAN Z. Research on node deployment in structural health monitoring based on reliability [C]// Proceedings of the 7th International Conference on Computer Engineering and Networks. Shanghai： [s.n.]， 2017： 1?7.
