基于可靠性在結構健康監測系統中的備份點布控研究

諸震亞 邵方明

關鍵詞： 結構健康監測; 點失效模型; 無線傳感器網絡; 網絡性能; 優化策略; 可靠性

中圖分類號： 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 ?引 ?言

結構健康監測（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.