諸震亞 邵方明

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

中圖分類號： TN929.5?34 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： 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）定期從傳感器采集動(dòng)態(tài)響應(yīng)數(shù)據(jù)，以此數(shù)據(jù)分析觀察該結(jié)構(gòu)體系隨時(shí)間變化的情況，用傳感器采集的數(shù)據(jù)特征反映結(jié)構(gòu)的健康狀況，并用這些動(dòng)態(tài)響應(yīng)數(shù)據(jù)評估系統(tǒng)對結(jié)構(gòu)損傷的敏感性以及對異常事件的快速分析能力。對于長期服役的建筑（如高樓、橋梁），監(jiān)測其關(guān)鍵部位的安全情況對本身以及社會(huì)安全都有著重大意義[1?3]。

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

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

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

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

1.1 ?系統(tǒng)模型

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

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

[X=x11x12…x1mx21x22…x2m????xn1xn2…xnm] ? ? ? ? ?（1）

式中，xij（1≤i≤n，1≤j≤m）表示位置（i，j）處是否部署傳感器。當(dāng)xij=0時(shí)，表示位置（i，j）未布控傳感器;當(dāng)xij=1時(shí)，表示位置（i，j）已布控傳感器。

定義1 部署傳感器的位置數(shù)為：

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

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

[BX=SX-SX0] （3）

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

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

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

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

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

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

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

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

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

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

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

1.2 ?數(shù)學(xué)描述

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

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

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

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

2 ?INR?R0算法

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

2.1 ?理論分析

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

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

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

定理2 在圖G ? Ω（n，m）中添加一個(gè)節(jié)點(diǎn)后，當(dāng)其成功運(yùn)行的概率p趨近1時(shí)，此時(shí)圖的可靠性上界為：

[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）中，非正則圖的點(diǎn)連通度小于擬正則二部圖的點(diǎn)連通度。在類Ω（n，m）中，任意非正則圖G的度序列為[d1，d2，…，dn]。其中d1 ≤d2 ≤…≤dn;擬正則二部圖G*的度序列為[d1，d2，…，dn]=[α，α，…，α，α+1，…，α+1]。由割集的定義可知κ（G）≤d1，κ（G*）=α。而在非正則圖中必存在d1<α和dn>α+1，所以κ（G）<κ（G*），即非正則圖的點(diǎn)連通度小于擬正則二部圖的點(diǎn)連通度。

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

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

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

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

[R=minp+qRG，Rn+1]

2.2 ?算法設(shè)計(jì)與分析

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

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

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

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

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

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

在INR?R0算法中，確定最少節(jié)點(diǎn)數(shù)a，度序列[DN1，DM-N1]以及集合S的復(fù)雜度均為O（n）;同時(shí)由于計(jì)算R（G）是一個(gè)NP?難問題，所以該算法的復(fù)雜度也是源于R（G）的計(jì)算復(fù)雜度。

3 ?實(shí)驗(yàn)仿真

3.1 ?仿真1

INR?R0示例如圖2所示，虛線交點(diǎn)為候選位置（M=25）。v1，v2，v3，v4，v5，v6是主要位置（N1=6），備份位置數(shù)為M-N1。對于給定的R0=0.95，通信半徑[rs=5]和節(jié)點(diǎn)正常運(yùn)行的概率p=0.8，仿真結(jié)果如表1所示。

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

3.2 ?仿真2

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

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

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

4 ?結(jié) ?論

本文將SHM系統(tǒng)中傳感器部署策略轉(zhuǎn)化為無線傳感器網(wǎng)絡(luò)的可靠性優(yōu)化問題。為了解決可靠性優(yōu)化問題，本文提出一種新的提高網(wǎng)絡(luò)可靠性的方法，并給出一類圖的可靠性上界，進(jìn)而提出一種新的無線傳感器節(jié)點(diǎn)部署的INR?R0算法。仿真結(jié)果表明，與BSP和FEM算法相比，INR?R0算法只需添加更少的備份傳感器就可使得網(wǎng)絡(luò)的可靠性大于確定閾值R0，表明了算法的有效性。

注：本文通訊作者為邵方明。

參考文獻(xiàn)

[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] 孫小猛，馮新，周晶.基于損傷可識(shí)別性的傳感器優(yōu)化布置方法[J].大連理工大學(xué)學(xué)報(bào)，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.