基于模糊規(guī)劃的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)選擇方法

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

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

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

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

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

1 公式化誤差約束條件

1.1 誤差約束

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

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

(1)

式中，yk,n表示第n個(gè)傳感器k時(shí)刻的真實(shí)值。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個(gè)傳感器K時(shí)刻的真實(shí)值，采樣值和誤差。根據(jù)上述公式可以把測量模型簡化表示為

y=f+e

(5)

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

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

(6)

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

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

(7)

(8)

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

(9)

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

(10)

展開可表示為

(11)

式(11)中，J(w)表示誤差精度，接下來需要對(duì)該公式進(jìn)行簡化。由于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è)：兩個(gè)物體相似性隨他們之間的距離增大而減少。它以插值點(diǎn)與控制點(diǎn)間的距離為權(quán)重進(jìn)行加權(quán)平均。插值過程主要包括3個(gè)步驟：

(1)計(jì)算插值點(diǎn)到所有控制點(diǎn)的距離

(16)

式(16)中，(x,y)表示插值點(diǎn)的坐標(biāo)，(xi,yi)表示控制點(diǎn)的坐標(biāo)；

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

(17)

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

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

(18)

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

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

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

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

(19)

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

(20)

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

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

(21)

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

3 模糊規(guī)劃

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

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

min‖wn‖0,1

(22)

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

(23)

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

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

為了更具一般性，算法將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稱為伸縮指標(biāo)，當(dāng)di=0時(shí)，模糊規(guī)劃就退化成線性規(guī)劃。當(dāng)di>0時(shí)，ti(s)取[bi-di,bi+di]內(nèi)的某一個(gè)值。最終，可將節(jié)點(diǎn)選擇問題轉(zhuǎn)化為模糊規(guī)劃求解。

(26)

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

圖3 伸縮指標(biāo)對(duì)節(jié)點(diǎn)數(shù)量的影響

5 結(jié)束語

本文提出了一種基于模糊規(guī)劃的節(jié)點(diǎn)選擇算法。以誤差精度和工作概率作為約束條件，以最小化所選的節(jié)點(diǎn)數(shù)量為目標(biāo)，將節(jié)點(diǎn)選擇問題轉(zhuǎn)化為0-1整數(shù)規(guī)劃求解，并且將0-1整數(shù)規(guī)劃進(jìn)行一般性推廣，轉(zhuǎn)化為模糊規(guī)劃。最后，利用溫度數(shù)據(jù)集對(duì)提出的兩種方法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果顯示兩種方法能明顯減少所選的節(jié)點(diǎn)數(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ò)分布式多傳感器目標(biāo)檢測[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.