諸震亞 邵方明

關鍵詞： 結(jié)構(gòu)健康監(jiān)測; 點失效模型; 無線傳感器網(wǎng)絡; 網(wǎng)絡性能; 優(yōu)化策略; 可靠性

中圖分類號： 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; reliability

0 ?引 ?言

結(jié)構(gòu)健康監(jiān)測（Structural Health Monitoring， SHM）定期從傳感器采集動態(tài)響應數(shù)據(jù)，以此數(shù)據(jù)分析觀察該結(jié)構(gòu)體系隨時間變化的情況，用傳感器采集的數(shù)據(jù)特征反映結(jié)構(gòu)的健康狀況，并用這些動態(tài)響應數(shù)據(jù)評估系統(tǒng)對結(jié)構(gòu)損傷的敏感性以及對異常事件的快速分析能力。對于長期服役的建筑（如高樓、橋梁），監(jiān)測其關鍵部位的安全情況對本身以及社會安全都有著重大意義[1?3]。

傳感器技術(shù)在連接計算機世界和物理世界有著關鍵作用，而對比有線傳感器來說，無線傳感器需要低功耗、易于部署、探測精度高、容錯性好，且可以遠程監(jiān)控，所以無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）在系統(tǒng)應用中比有線網(wǎng)絡更常見、實用。在實際應用中，監(jiān)測系統(tǒng)的重要參考指標有：監(jiān)測系統(tǒng)的經(jīng)濟性、可靠性以及有效性等。而從可靠性角度考慮監(jiān)測系統(tǒng)的性能時，其基本要求之一便是傳感器位置優(yōu)化，使得部署在系統(tǒng)中的無線傳感器網(wǎng)絡可以對結(jié)構(gòu)性能得到最佳估計[4?5]。因此，需要對結(jié)構(gòu)中傳感器的部署位置進行設計和優(yōu)化。對于傳感器的位置優(yōu)化，Kim等人首先通過有效獨立值（EFI）來確定主要傳感器的位置[4，6?7]。其中EFI使用模態(tài)振型和噪聲測量，然后提供Fisher信息矩陣（FIM）行列式來計算EFI值。該值被稱為部署質(zhì)量指標。結(jié)構(gòu)中每個位置都對應著特定的EFI值，這是確定結(jié)構(gòu)中主要傳感器位置的有效方法，EFI值越大，表示在該放置越好。文獻[3，8]中便是基于EFI值來優(yōu)化無線傳感器的部署。Bhuiyan等人在文獻[9]提出了基于WSN的SHM需要保證一定的容錯能力，使得在網(wǎng)絡出現(xiàn)故障時，網(wǎng)絡依然處于正常工作狀態(tài);并提出了BSP算法來部署備份傳感器，以提高網(wǎng)絡的容錯性。

本文首次將網(wǎng)絡可靠性定義應用在結(jié)構(gòu)健康監(jiān)測系統(tǒng)中，并在原網(wǎng)絡基礎上增加備份節(jié)點來提高網(wǎng)絡的可靠性，使得結(jié)構(gòu)健康監(jiān)測系統(tǒng)更穩(wěn)定和全面地監(jiān)測整個建筑系統(tǒng)。

1 ?系統(tǒng)模型和問題形成

網(wǎng)絡可靠性是衡量網(wǎng)絡性能的一個重要指標。網(wǎng)絡可靠性模型通常分為：點失效模型、邊失效模型、點邊失效模型。在結(jié)構(gòu)健康監(jiān)測系統(tǒng)中，傳感器的主要位置可通過EFI值確定，因此本文基于點失效模型僅研究備份傳感器的部署問題。

1.1 ?系統(tǒng)模型

考慮有M個候選位置（可部署傳感器位置）和N1個主要傳感器，且每個位置只能部署一個傳感器的SHM系統(tǒng)。通常根據(jù)EFI值將N1個主要傳感器部署在N1個候選位置上。

在SHM系統(tǒng)中，傳感器的位置狀態(tài)矩陣為：

[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 部署傳感器的位置數(shù)為：

[S（X）=injmxij] ? ? ? ? ? ? （2）

部署備份傳感器數(shù)為：

[BX=SX-SX0] （3）

式中，[X0]表示SHM系統(tǒng)的初始位置狀態(tài)矩陣。

當兩個傳感器之間的距離小于通信半徑rs時，它們在網(wǎng)絡中形成一條邊。這些傳感器節(jié)點和邊就組成了WSN網(wǎng)絡G。在點失效模型中，網(wǎng)絡G的邊不失效，節(jié)點正常運行的概率為p，其可靠性為：

[RG，p=r=1nSr（G）prqn-r=r=1n（Crn-Cr（G））prqn-r] （4）

式中：[Sr（G）]為網(wǎng)絡G中包含r個節(jié)點的誘導子圖的個數(shù)[10];[Cr（G）]在網(wǎng)絡G中刪除r個節(jié)點導致網(wǎng)絡不連通的誘導子圖的個數(shù)。

定義2 傳感器網(wǎng)絡G的可靠性函數(shù)為：

[f（X，p）=rnSr（G）prqn-r] ? ? ?（5）

一般地，對任意一個連通圖G，圖的點連通度κ（G）就是該圖的最小點割集的數(shù)目[10]。對任意屬于類Ω（n，m）的圖G，都有：

[κ（G）≤2mn] ? ? ? ? ? ? （6）

如果G是完全圖，則有[κ（G）=n-1]，其中Ω（n，m）表示一類包括n個點m條邊的圖簇。而一致最優(yōu)圖是類Ω（n，m）中不論節(jié)點運行的概率取何值時，可靠性始終最大的圖。而在實際生活中，傳感器節(jié)點成功通信的概率通常比較高，所以只需考慮某個范圍內(nèi)的概率，即考慮局部最優(yōu)圖。

定義3 局部最優(yōu)圖是指在類Ω（n，m）中，節(jié)點運行的概率大于或等于某定值時，可靠性始終最大。

對于備份傳感器部署問題，將位置拓撲轉(zhuǎn)換為WSN拓撲同時保持其可靠性具有重要實際意義。通過數(shù)學描述和定義，使用網(wǎng)絡可靠性優(yōu)化替代傳感器位置優(yōu)化可以較容易理解。

1.2 ?數(shù)學描述

每個候選位置處最多只能部署一個傳感器，考慮這樣一個優(yōu)化問題：在保證網(wǎng)絡的可靠性R大于給定閾值R0前提下，添加最少的備份傳感器數(shù)量。那么，在SHM系統(tǒng)中，對給定的M個候選位置，N1個主要傳感器和傳感器成功運行概率p，上述優(yōu)化問題可以描述為：

[minxBXs.t. ? ?fX，p≥R0 ? ? ?BX≤M-N1] （7）

這里傳感器的位置狀態(tài)矩陣X的數(shù)量至多2M個。

為了解決式（7）的優(yōu)化問題，首先利用位置狀態(tài)矩陣X將位置拓撲轉(zhuǎn)化成網(wǎng)絡結(jié)構(gòu)G。由于網(wǎng)絡G的規(guī)模會隨著候選位置的數(shù)量M成指數(shù)增長，所以枚舉法所消耗的時間也會成指數(shù)級增長，因而實際生活中的應用意義不大。針對此問題，本文首先給出增加一個備份節(jié)點后網(wǎng)絡可靠性的一個上界;然后利用降序度序列來布控備份傳感器，給出網(wǎng)絡可靠性增強（Increase the Reliability of Network）算法：INR?R0。

2 ?INR?R0算法

本節(jié)對備份傳感器有效位置和可靠性上界進行理論分析，并設計確定最少備份傳感器的INR?R0算法。

2.1 ?理論分析

首先利用定理1確定部署備份傳感器的有效位置。

定理1 令網(wǎng)絡G屬于類Ω（n，m），G′是在G中添加一個點y，當d（y）=n時，有R（G′） ≥ R（G），且R（G′）=p + qR（G）。

證明：將網(wǎng)絡G看作概率為[R（G）=rnSr（G）prqn-r]的節(jié)點，那么網(wǎng)絡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給出了一種增加備份節(jié)點后提高網(wǎng)絡可靠性的方法。接下來，將給出類Ω（n，m）可靠性的一個上界。

定理2 在圖G ? Ω（n，m）中添加一個節(jié)點后，當其成功運行的概率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*），即非正則圖的點連通度小于擬正則二部圖的點連通度。

然后證明當節(jié)點成功運行的概率p趨近1時，類Ω（n，m）中局部最優(yōu)圖的度序列均勻。由割集的定義可知κ（G*）=α，且C1（G*）=C2（G*）= …=Cα?1（G*）=0。又因為κ（G）≤d1<α，Cα-1（G）>0，則當p趨于1時，有R（G，p）<R（G*，p），即度序列不均勻的圖不是局部最優(yōu)圖。

最后證明添加一個節(jié)點后圖的可靠性上界為[R] = min{p+qR（G），Rn+1}。當[n≤m≤n24]時，擬正則二部圖是其類里的局部最優(yōu)圖[11]，那么含有n個節(jié)點的圖G上界為：

[Rn=1-i>2n2Cin2+Cin2piqn-i+pn2qn-n2]

結(jié)合定理1，在圖1 G中添加一個節(jié)點后，圖的可靠性上界為：

[R=minp+qRG，Rn+1]

2.2 ?算法設計與分析

一種提高網(wǎng)絡容錯能力的方法是在原來的主要位置處添加備份節(jié)點[9]。該方法能提高單個節(jié)點成功運行的概率，然而有時并不能提高該網(wǎng)絡的可靠性。因此本節(jié)提出了一種在節(jié)點成功運行概率較高時，提高網(wǎng)絡可靠性的INR?R0算法。

首先，從G（V，E）中得到節(jié)點的度序列[DN1]，其中G（V，E）表示以V為點集，E為邊集的網(wǎng)絡，[V=N1=n，][E=m]。并利用定理2得到當網(wǎng)絡可靠性高于某個閾值R0時，所需要添加最少的節(jié)點數(shù)a。

然后，在點集V的通信半徑rs內(nèi)，求出M-N1個備份位置處l的點度dl，進而得到度序列[DM-N1]。接著，根據(jù)定理1找到滿足dl≥N1的集合S。

最后，在備份位置處添加節(jié)點;當a ≤[S]時，從[S]選a個位置添加節(jié)點;當[S]<a≤M-N1時，先部署S中的節(jié)點，然后在剩下[a-S]個位置部署備份傳感器，其原則為：先找到[DN1]中最小點度的位置ldmin，然后在[DM-N1]中靠近ldmin處最大點度位置部署節(jié)點。從M-N1中選擇a個位置部署節(jié)點后計算R（Ga），遞歸執(zhí)行上述操作直到R≥R0或者a>M-N1，輸出最少備份節(jié)點數(shù)B（X）=a。其具體算法如下。

算法：INR?R0（M，N1，G，p，rs）

輸入：網(wǎng)絡G（V，E），候選位置數(shù)M，主要傳感器數(shù)N1，定值R0，點正常通信概率p，連通半徑rs。

在INR?R0算法中，確定最少節(jié)點數(shù)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），備份位置數(shù)為M-N1。對于給定的R0=0.95，通信半徑[rs=5]和節(jié)點正常運行的概率p=0.8，仿真結(jié)果如表1所示。

表1給出了在原網(wǎng)絡中加入備份節(jié)點之后網(wǎng)絡的可靠性，圖G1的可靠性為R（G1，p）=0.552 4<R0。根據(jù)INR?R0算法，在圖中添加一個備份節(jié)點后，網(wǎng)絡可靠性上界為：[R]=min{p+qR（G1，p），R7}=0.910 5<R0。添加備份節(jié)點后，其可靠性上界為：[R]= 0.982 1>R0。得到網(wǎng)絡的度序列為[DM?N1]=[2，2，2，2，3，4，3，3，4，6，3，2，3，3，3，2， 2，3，1]，集合S={10}。首先在網(wǎng)絡G1中的位置10處添加節(jié)點得到網(wǎng)絡G2，R（G2，p）=p+qR（G1，p）= 0.910 5<R0，需要繼續(xù)添加節(jié)點;由于dmax=max[{DM?N1d10}=d6]，接著在G2中的位置6處添加節(jié)點得到網(wǎng)絡G3，R（G3，p） = 0.951 4>R0，所以B（X）=2。因此，對于給定R0=0.95，最少需要添加兩個備份節(jié)點就可使得網(wǎng)絡可靠性大于R0。

3.2 ?仿真2

利用文獻[9]中一個位于中國香港的建筑（Lee Shao Kee， LSK）作為測試網(wǎng)絡。根據(jù)算法INR?R0確定部署備份傳感器的位置，結(jié)果如圖3所示。

圖中，G5，G6，G7中黑點分別是通過算法INR?R0，BSP[9]，F(xiàn)EM[4]確定的備份傳感器部署的位置。

從圖4和表2中可以看出，當傳感器節(jié)點成功運行的概率p=0.8，R0=0.7時，INR?R0需要添加2個備份傳感器，BSP和FEM算法分別需要添加6和大于6個備份傳感器;當0.5<R0 <0.65時，INR?R0，BSP，F(xiàn)EM算法分別需要添加2，5，4個備份傳感器;當0.4<R0<0.5時，INR?R0，BSP，F(xiàn)EM算法分別需要添加1，1，3個備份傳感器。與BSP算法和FEM算法相比，INR?R0算法需要添加更少的備份傳感器就可使得網(wǎng)絡的可靠性大于確定閾值R0，表明了算法的有效性。

4 ?結(jié) ?論

本文將SHM系統(tǒng)中傳感器部署策略轉(zhuǎn)化為無線傳感器網(wǎng)絡的可靠性優(yōu)化問題。為了解決可靠性優(yōu)化問題，本文提出一種新的提高網(wǎng)絡可靠性的方法，并給出一類圖的可靠性上界，進而提出一種新的無線傳感器節(jié)點部署的INR?R0算法。仿真結(jié)果表明，與BSP和FEM算法相比，INR?R0算法只需添加更少的備份傳感器就可使得網(wǎng)絡的可靠性大于確定閾值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] 孫小猛，馮新，周晶.基于損傷可識別性的傳感器優(yōu)化布置方法[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] 張國柱，張文川，潘寶志，等.隧道無線健康監(jiān)測系統(tǒng)環(huán)境敏感性分析[J].公路交通技術(shù)，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.