涂偉健，徐向華，程宗毛，王 然

(1.杭州電子科技大學(xué) 計算機學(xué)院，浙江 杭州 310018；2.杭州電子科技大學(xué) 理學(xué)院，浙江 杭州 310018)

無線傳感器網(wǎng)絡(luò)由許多小型傳感器節(jié)點組成，每個傳感器節(jié)點具有采集、處理和轉(zhuǎn)發(fā)數(shù)據(jù)的功能，采集的數(shù)據(jù)包括溫度、濕度、光照強度、電壓等。并以其低廉、小型、功能強大的特點被廣泛應(yīng)用于多種場合，比如震動監(jiān)控[1-3]，精準農(nóng)業(yè)[4-6]、目標檢測[7-8]和區(qū)域重構(gòu)[9-11]等。

在針對節(jié)點選擇問題時，文獻[12]設(shè)計了一種稀疏選擇向量選擇最有益的傳感器集合來滿足克拉美羅界，而克拉美羅界被解釋為誤差約束。而文獻[13]通過將區(qū)域網(wǎng)格化，選擇滿足誤差要求的網(wǎng)格點作為節(jié)點的部署點。文獻[12～13]雖然都考慮了誤差精度，將傳感器選擇問題轉(zhuǎn)化為最優(yōu)化問題求解，但在選擇節(jié)點時并有沒考慮所選傳感器是否能夠正常工作，若所選傳感器處于故障狀態(tài)，那么選擇的節(jié)點子集就不能正常工作。文獻[14]針對節(jié)點選擇問題設(shè)計了一種稀疏促進罰函數(shù)避免重復(fù)選擇相同傳感器節(jié)點，將問題公式化為凸二次規(guī)劃求解，從而達到網(wǎng)絡(luò)中傳感器節(jié)點負載均衡的目的。但是將誤差精度作為凸二次規(guī)劃的目標，會使得最終選擇的傳感器子集可能出現(xiàn)誤差較大的情況。

因此，在節(jié)點選擇的過程中，節(jié)點不僅要滿足誤差約束要求，而且為了避免選擇處于故障狀態(tài)的節(jié)點，還需要考慮節(jié)點處于工作狀態(tài)的概率。在誤差約束方面，模糊規(guī)劃算法選用反距離加權(quán)插法對插值點數(shù)據(jù)進行預(yù)測，并利用均方誤差評價插值效果。在正常工作概率方面，通過節(jié)點采樣的歷史數(shù)據(jù)，計算每個節(jié)點處于工作狀態(tài)的概率，在最終選擇節(jié)點子集的時候，子集中的節(jié)點處于正常工作的概率要滿足給定的閾值要求。

1 公式化誤差約束條件

1.1 誤差約束

假設(shè)f(tk,sn)表示位置sn上的節(jié)點k時刻的采樣值。由于采樣的過程中會產(chǎn)生誤差，表示為ek,n。那么，測量模型公式化為

yk,n=f(tk,sn)+ek,n

(1)

式中，yk,n表示第n個傳感器k時刻的真實值。k=1，2，…,k,n=1,2,…,n。ek,n服從正態(tài)分布，即ek,n～N(0,σ2)，期望為0，方差為σ2，σ2是噪音的協(xié)方差矩陣。令

y=[y1,1,…,yK,1,…,y1,N,…,yK,N]T

(2)

f=[f(t1,s1),…,f(tK,s1),…,f(t1,sN),…,f(tK,sN)]T

(3)

e=[e1,1,…,eK,1,…,e1,N,…,eK,N]T

(4)

分別表示第N個傳感器K時刻的真實值，采樣值和誤差。根據(jù)上述公式可以把測量模型簡化表示為

y=f+e

(5)

由于目標是區(qū)域重構(gòu)，需要通過控制點對插值點的數(shù)據(jù)進行插值預(yù)測。假設(shè)插值點的采樣值為θ，坐標為δ。那么插值點的測量模型可以公式化為

θ={f(t1,δ),f(t2,δ),…,f(tk,δ)}

(6)

式(6)中，θ表示坐標δ的傳感器節(jié)點K時刻測量數(shù)據(jù)的真實值，f(tk,δ)表示坐標δ的傳感器節(jié)點在tk時刻的采樣值。

由于反距離加權(quán)插值是利用控制點和插值點之間的距離來確定權(quán)值，特別適合于對溫度數(shù)據(jù)的預(yù)測。因此，基于反距離加權(quán)插值模型，插值點的測量模型可以公式化為

(7)

(8)

根據(jù)均方誤差公式

(9)

再聯(lián)立插值模型，可得誤差公式為

(10)

展開可表示為

(11)

式(11)中，J(w)表示誤差精度，接下來需要對該公式進行簡化。由于y=f+e，令

E(F(y)F(y)T)=E[F(y+e)F(f+e)T]=P

(12)

E(F(y)θ)=E[F(f+e)θ]=E[F(f)×f(tk,δ)]=q

(13)

(14)

(15)

1.2 反距離加權(quán)插值

反距離加權(quán)插值法是基于基本假設(shè)：兩個物體相似性隨他們之間的距離增大而減少。它以插值點與控制點間的距離為權(quán)重進行加權(quán)平均。插值過程主要包括3個步驟：

(1)計算插值點到所有控制點的距離

(16)

式(16)中，(x,y)表示插值點的坐標，(xi,yi)表示控制點的坐標；

(2)計算每個點的權(quán)重。權(quán)重是距離的倒數(shù)的函數(shù)，表示為

(17)

λi表示第i個節(jié)點的權(quán)重，n為控制點數(shù)量。p是一個任意正整數(shù)，一般令p=2；

(3)計算預(yù)測值

(18)

2 公式化節(jié)點正常工作概率

在現(xiàn)實情況中，無論是確定性部署還是隨機部署，傳感器節(jié)點會因為各種各樣的軟件因素或者硬件因素而故障，從而造成節(jié)點不能工作。因此在傳感器選擇問題中需要同時考慮所選傳感器盡可能多的處于能夠工作的狀態(tài)。

從歷史采樣數(shù)據(jù)中可以得知，傳感器節(jié)點在當前工作時長中正常工作所占的時間比。假設(shè)隨機變量s表示節(jié)點正常工作的時間，從歷史采樣數(shù)據(jù)中可知，s是一個服從幾何分布的隨機變量，從而可以得到特定傳感器的正常工作的概率。

令傳感器節(jié)點正常工作概率表示為P(si)，P(si)是單個節(jié)點正常工作的概率。假設(shè)si節(jié)點的當前工作總時長為Ta，當前工作總時長中正常工作的時間為Tn，那么P(si)可以表示為

(19)

如果所選的傳感器是以集合的形式，那么可以根據(jù)容斥公式，多個節(jié)點組合的概率可以表示為

(20)

容斥原理是一種組合數(shù)學(xué)方法，可以計算復(fù)合事件的概率。然而，所選的節(jié)點是多個節(jié)點的集合，希望集合中至少有傳感器節(jié)點能夠正常工作，而容斥公式正是描述這樣一個事件發(fā)生的概率。例如，假設(shè)選擇了節(jié)點s1和s2，且s1與s2是相互獨立的事件，那么根據(jù)容斥公式，其組合概率可以表示為

P(s1+s2)=P(s1)+P(s2)-P(s1)P(s2)

(21)

若所選傳感器節(jié)點增加，組合概率計算方法可通過式(20)計算。

3 模糊規(guī)劃

本文算法將誤差精度和工作概率公式化為約束條件，將最小化選擇的傳感器數(shù)量作為目標函數(shù)，把傳感器選擇問題首先轉(zhuǎn)化為0-1整數(shù)規(guī)劃問題求解。

令布爾變量wn表示第n個傳感器節(jié)點，當wn=1時表示選擇第n個傳感器節(jié)點，反之，當wn=0時表示不選擇。那么根據(jù)最小化選擇的傳感器數(shù)量的目標，可以得到目標函數(shù)為

min‖wn‖0,1

(22)

另外，根據(jù)上述公式化的約束條件，將節(jié)點選擇問題轉(zhuǎn)化為0-1整數(shù)規(guī)劃問題求解。

(23)

式(23)中，ε和p分別為給定的誤差精度閾值和節(jié)點正常工作的概率閾值。

普通線性規(guī)劃的約束條件都是確定的，但在一些實際問題中，約束條件可能帶有彈性，必須借助模糊集的方法來處理。

為了更具一般性，算法將0-1整數(shù)規(guī)劃推廣到模糊線性規(guī)劃。普通線性規(guī)劃的約束條件表示為

ti(x)=bi

(24)

式(24)中，x=[x1,x2,…,xn]，ti=ai1x1+ai2x2+…+ainxn，bi為常數(shù)閾值。若將約束條件轉(zhuǎn)換為模糊函數(shù)，則表示成

ti(x)=[bi,di]

(25)

式(25)中，di稱為伸縮指標，當di=0時，模糊規(guī)劃就退化成線性規(guī)劃。當di>0時，ti(s)取[bi-di,bi+di]內(nèi)的某一個值。最終，可將節(jié)點選擇問題轉(zhuǎn)化為模糊規(guī)劃求解。

(26)

式(26)中，α、β為相應(yīng)的伸縮指標。

4 仿真實驗

利用Intel Berkeley 實驗室的數(shù)據(jù)集[15]對0-1整數(shù)規(guī)劃和模糊規(guī)劃分別進行實驗對比。數(shù)據(jù)集記錄了從2004年2月28日～4月5日的溫度、濕度、光照強度和電壓的數(shù)據(jù)，區(qū)域中共部署了54個傳感器節(jié)點，隨機選取8個節(jié)點的溫度數(shù)據(jù)對算法模擬實驗。實驗平臺為Microsoft Visual Studio 2010。

圖1 模糊規(guī)劃與0-1整數(shù)規(guī)劃對比

圖2和圖3分別顯示了概率閾值和伸縮指標對選擇的節(jié)點的數(shù)量的影響。從圖2中可以看到，隨著概率閾值的提高，算法需要選擇更多的傳感器節(jié)點來增加正常工作概率，所以傳感器節(jié)點數(shù)量隨概率閾值的增加而增加。另外，誤差閾值越小，需要選擇的傳感器節(jié)點數(shù)量越多。

在圖3中，由于伸縮指標是作為誤差閾值的一部分，伸縮指標的放大，相當于增加了誤差閾值，因此選擇較少的節(jié)點數(shù)量既能滿足閾值要求。所以在圖3中，傳感器節(jié)點數(shù)量隨伸縮指標的增加而減少；另一方面，概率閾值越大，選擇的傳感器節(jié)點數(shù)量也越多。

圖2 概率閾值對節(jié)點數(shù)量的影響

圖3 伸縮指標對節(jié)點數(shù)量的影響

5 結(jié)束語

本文提出了一種基于模糊規(guī)劃的節(jié)點選擇算法。以誤差精度和工作概率作為約束條件，以最小化所選的節(jié)點數(shù)量為目標，將節(jié)點選擇問題轉(zhuǎn)化為0-1整數(shù)規(guī)劃求解，并且將0-1整數(shù)規(guī)劃進行一般性推廣，轉(zhuǎn)化為模糊規(guī)劃。最后，利用溫度數(shù)據(jù)集對提出的兩種方法進行仿真實驗，結(jié)果顯示兩種方法能明顯減少所選的節(jié)點數(shù)量，并且模糊規(guī)劃要優(yōu)于0-1整數(shù)規(guī)劃。

[1] Barooah P,Chenji H,Stoleru R,et al.Investigation of wireless sensor networks for structural health monitoring[J].Journal of Sensors,2012,2012(1):276-283.

[2] Gao S,Yuan S,Qiu L,et al. A high-throughput multi-hop WSN for structural health monitoring[J].Journal of Vibroengineering,2016,18(2):781-800.

[3] Hackmann G,Guo W,Yan G,et al. Cyber-physical codesign of distributed structural health monitoring with wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(1):63-72.

[4] Wang B,Deng X,Liu W,et al.Confident information coverage in sensor networks for field reconstruction[J].IEEE Wireless Communications,2013,20(6):74-81.

[5] Brinis N,Saidane L A.A wireless sensor network in precision agriculture[J].Wireless Sensor Network,2016,8(1):1-12.

[6] Anisi M H,Abdul-Salaam G,Abdullah A H. A survey of wireless sensor network approaches and their energy consumption for monitoring farm fields in precision agriculture[J].Precision Agriculture,2015,16(2):216-238.

[7] 魏鵬,路贊贊.無線傳感器網(wǎng)絡(luò)分布式多傳感器目標檢測[J].電子科技,2014,27(3):143-146.

[8] Shahbazian R,Ghorashi S A.Distributed cooperative target detection and localization in decentralized wireless sensor networks[J].Journal of Supercomputing,2016(8):1-18.

[9] Sijia Liu,Vempaty A,Fardad M,et al. Energy-aware sensor selection in field reconstruction[J].IEEE Signal Processing Letters,2014,21(12):1476-1480.

[10] Santini S,Colesanti U.Adaptive random sensor selection for field reconstruction in wireless sensor networks[C].Lyon:The Workshop on Data Management for Sensor Networks, in Conjunction with Vldb,2009.

[11] Joshi S,Boyd S.Sensor selection via convex optimization[J].IEEE Transactions on Signal Processing,2009,57(2):451-462.

[12] Chepuri S P,Leus G.Continuous sensor placement[J].IEEE Signal Processing Letters,2015,22(5):544-548.

[13] Chepuri S P,Leus G.Sparsity-promoting adaptive sensor selection for non-linear filtering[C].MA,USA:IEEE International Conference on Acoustics, Speech and Signal Processing,2014.

[14] Liu S,Masazade E,Fardad M,et al. Sparsity-aware field estimation via ordinary Kriging[C].CA,USA:IEEE International Conference on Acoustics, Speech & Signal Processing,2014.

[15] Madden S.Intel lab data[EB/OL]. (2004-01-02) [2015-12-18] http://db.csail.mit.edu/labdata/labdata.html.