朱翠濤,瞿 毅

(中南民族大學(xué)電子信息工程學(xué)院,武漢430074)

基于壓縮感知的稀疏事件檢測

朱翠濤,瞿 毅

(中南民族大學(xué)電子信息工程學(xué)院,武漢430074)

為了提高無線傳感器網(wǎng)絡(luò)中稀疏事件的檢測概率,利用壓縮感知技術(shù),提出了一種改進(jìn)的下降迭代檢測算法.該算法通過動態(tài)調(diào)節(jié)參數(shù),改變迭代權(quán)值,加快了算法收斂速度.實(shí)驗(yàn)結(jié)果表明:在相同條件下,改進(jìn)算法的成功檢測概率比貝葉斯算法平均提高了13%.

壓縮感知;稀疏事件檢測;無線傳感器網(wǎng)絡(luò)

在大規(guī)模無線傳感器網(wǎng)絡(luò)中,由于電池耗盡、傳感器節(jié)點(diǎn)休眠、人為或自然損壞等原因,常常有大量傳感器節(jié)點(diǎn)處于非正常工作狀態(tài).為了維護(hù)無線傳感器網(wǎng)絡(luò)的正常運(yùn)行,及時、準(zhǔn)確地了解無線傳感器網(wǎng)絡(luò)的運(yùn)行狀況,是十分必要的.為此,人們做了大量的研究工作.文獻(xiàn)[1]提出了一種改進(jìn)的權(quán)值信任評估檢測算法.算法規(guī)定每一個父節(jié)點(diǎn)為其子節(jié)點(diǎn)分配一個權(quán)值,子節(jié)點(diǎn)向父節(jié)點(diǎn)發(fā)送數(shù)據(jù),對應(yīng)的父節(jié)點(diǎn)將接收的數(shù)據(jù)與對應(yīng)子節(jié)點(diǎn)的權(quán)值相乘相加,得到一個融合值.當(dāng)發(fā)現(xiàn)本次的融合值與上次的值不一致時,就減小相應(yīng)子節(jié)點(diǎn)的權(quán)值,如此循環(huán)檢測.但是權(quán)值的閾值很難確定,容易造成誤檢.文獻(xiàn)[2]提出一種基于心跳機(jī)制的節(jié)點(diǎn)亞死亡狀態(tài)檢測方法.采用鄰居檢測方法檢測節(jié)點(diǎn)是否處于沉默期,并參考節(jié)點(diǎn)自測電壓值與重啟現(xiàn)象判斷是否進(jìn)入了亞死亡狀態(tài).但是用于判斷HTO的經(jīng)驗(yàn)值一般難以確定,需要考慮通信丟包與回電周期,影響節(jié)點(diǎn)工作狀態(tài)的檢測.文獻(xiàn)[3]提出一種將壓縮感知與貝葉斯結(jié)合的算法.用觀測點(diǎn)采集的無線傳感器網(wǎng)絡(luò)中處于工作狀態(tài)的傳感器節(jié)點(diǎn),根據(jù)觀測得到的值,使用邊際似然最大和迭代逼近方法求出超參數(shù),以及稀疏信號的先驗(yàn)概率.由于稀疏信號服從多元高斯分布,通過貝葉斯定理求解稀疏信號的后驗(yàn)概率和概率密度函數(shù),然后取后驗(yàn)估計(jì)的均值作為稀疏信號的點(diǎn)估計(jì).但是用最大似然求先驗(yàn)概率容易造成過學(xué)習(xí),影響稀疏信號的點(diǎn)估計(jì),導(dǎo)致稀疏事件的檢測概率減小.

為了提高檢測算法的自適應(yīng)能力、穩(wěn)健性和檢測的準(zhǔn)確性,本文利用壓縮感知技術(shù),并提出了一種改進(jìn)的下降迭代檢測算法.通過動態(tài)調(diào)節(jié)參數(shù)來改變權(quán)值,加快算法的收斂速度.實(shí)驗(yàn)結(jié)果表明,該算法與貝葉斯檢測算法相比,明顯提高了稀疏事件的檢測概率.

1 系統(tǒng)模型

系統(tǒng)模型如圖1所示.在一定區(qū)域內(nèi),隨機(jī)分布個傳感器.在某時刻有K(K?N)個傳感器處于工作狀態(tài),用黑色實(shí)心圓表示.N-K個處于非正常工作狀態(tài),用空心圓表示.觀測節(jié)點(diǎn)有M(M?N)個,用雙圓表示.處于工作狀態(tài)的傳感器將測到的信號發(fā)給觀測節(jié)點(diǎn),經(jīng)觀測節(jié)點(diǎn)處理后,將網(wǎng)絡(luò)的工作情況發(fā)給監(jiān)控中心.

圖1 系統(tǒng)模型Fig.1 System Model

設(shè)第m個觀測節(jié)點(diǎn)(1≤m≤M)與第n個傳感器(1≤n≤N)之間的傳播距離為dm,n,α是衰減因子,信號的衰減量為(dm,n)-α.由于多徑傳播的影響,第m個觀測節(jié)點(diǎn)接收的多徑信號為rm,n.其包絡(luò)｜rm,n｜服從瑞利分布.第m個觀測節(jié)點(diǎn)檢測到第n個傳感器的信號為:

在整個無線傳感器網(wǎng)絡(luò)中,M個觀測點(diǎn)與N個傳感器節(jié)點(diǎn)之間的傳輸矩陣如下:

令XN×1為一個稀疏信號向量,其中每一個元素的取值為0或1.元素值為0表示傳感器節(jié)點(diǎn)處于非工作狀態(tài),元素值為1表示傳感器節(jié)點(diǎn)處于工作狀態(tài).所以M個觀測點(diǎn)檢測的信號表示為GM×NXN×1.設(shè)噪聲為高斯噪聲,均值為0,方差為σ2,用向量∈M×1表示.觀測到的信號為:

2 問題描述

在無線傳感器網(wǎng)絡(luò)中,用M個觀測點(diǎn)檢測N個傳感器節(jié)點(diǎn)產(chǎn)生K事件,這三者之間關(guān)系滿足:K≤M≤N.當(dāng)有多個傳感器節(jié)點(diǎn)同時給一個觀測點(diǎn)發(fā)送信息,信息之間相互疊加,并且信號在傳播過程中存在衰減.那么在這些情況的干擾下,如何使用較少的觀測點(diǎn)仍能以較大的概率檢測稀疏事件.由文獻(xiàn)[4]可知,要用較少的觀測點(diǎn)檢測出無線傳感器網(wǎng)絡(luò)中的稀疏事件,必須存在如下關(guān)系:M≥cKlog2(N/K),其中c是一個小常數(shù).當(dāng)K減小時,cKlog2(N/K)減小,觀測點(diǎn)M的下限值也相應(yīng)減小,于是在檢測過程中就可以使用更少的觀測點(diǎn)檢測稀疏事件.

因此,問題的數(shù)學(xué)模型如下:

0范數(shù)不是一個凸優(yōu)化問題,一般很難求解.文獻(xiàn)[5-6]提出,在凸優(yōu)化問題中,只有1范數(shù)的解才是最接近0范數(shù)的最優(yōu)解.兩者的稀疏解近似等價,于是將0范數(shù)問題轉(zhuǎn)化為求解1范數(shù)問題.對于式(3)求解,常用的辦法就是基追蹤,匹配追蹤,正交匹配追蹤等等.為了提高式(3)中稀疏信號的檢測概率,本文在目標(biāo)函數(shù)中引入權(quán)值,提出一種改進(jìn)的下降迭代檢測算法.因?yàn)樗詫?范數(shù)轉(zhuǎn)換為如下形式:

在YM×1=GM×NXN×1約束條件下,目標(biāo)函數(shù)m in可以取得近似稀疏解. 現(xiàn)在令λM×1是一個M維的向量因子,由歐拉—拉格朗日定理得到:

對式(5)兩邊求導(dǎo),得:

令式(6)等于零,得:

3 檢測算法實(shí)現(xiàn)

根據(jù)以上的推導(dǎo)過程,得到整個檢測算法的具體實(shí)現(xiàn)步驟如下.

(1)初始化迭代次數(shù)l(0≤l≤lmax),w(0)i=1,(i=1,2,…,n),參數(shù)α和αmin,向量XN×1;

(2)若迭代次數(shù)l大于lmax,則停止迭代,返回主程序.否則轉(zhuǎn)到第3步;

(3)更新權(quán)值.對于每一個i=1,2,…,n,有

(5)將α參數(shù)縮小1 0倍,跳轉(zhuǎn)到第2步繼續(xù)執(zhí)行.

改進(jìn)的下降迭代檢測算法流程如圖2所示.

4 試驗(yàn)仿真與結(jié)果分析

利用MA TLAB 7.0軟件對改進(jìn)的下降迭代檢測算法進(jìn)行仿真.環(huán)境參數(shù)設(shè)置如下:在一個300×300m2方形區(qū)域中,隨機(jī)分布128個傳感器節(jié)點(diǎn),其中有5個傳感器節(jié)點(diǎn)處于工作狀態(tài),123個傳感器節(jié)點(diǎn)處于非工作狀態(tài).并且信號在傳輸過程中的衰減因子為2.

在相同條件下,比較了改進(jìn)的下降迭代算法與貝葉斯算法的檢測概率.首先,兩種算法在每一個觀測點(diǎn)處各自完成100次仿真檢測.其次,每完成一次檢測,計(jì)算出檢測的信號與原始信號之間的相對誤差.如果相對誤差值小于閾值0.05,就認(rèn)為檢測成功.否則認(rèn)為檢測失敗.然后得到成功檢測的次數(shù)占總次數(shù)的百分比.圖3,圖4分別是用20個和50個觀測點(diǎn)比較兩種算法的檢測概率與觀測點(diǎn)之間的關(guān)系.

由圖3和4可以看出,當(dāng)觀測節(jié)點(diǎn)數(shù)小于12時,兩種算法的檢測概率基本都為0.主要原因是觀測點(diǎn)得到的數(shù)據(jù)丟掉了較多有用信息,導(dǎo)致兩種檢測算法都不能通過觀測數(shù)據(jù)恢復(fù)原始信號,不能檢測到稀疏事件.隨著觀測點(diǎn)數(shù)的增多,改進(jìn)的下降迭代算法與貝葉斯算法的檢測概率都變大.在觀測點(diǎn)數(shù)為50個情況下,改進(jìn)的下降迭代算法的平均檢測概率比貝葉斯算法提高約13%.同時可以看出,在相同的檢測概率下,改進(jìn)的下降迭代算法比貝葉斯算法使用更少的觀測點(diǎn).另外,隨著觀測點(diǎn)數(shù)的增多,改進(jìn)的下降迭代算法的曲線趨于平緩,表明該算法具有較好的穩(wěn)健性.

圖4 50個觀測點(diǎn)的兩種算法檢測概率Fig.4 50 observation ponits for two algorithm s detection probablity

5 結(jié)語

本文將壓縮感知技術(shù)應(yīng)用于無線傳感器網(wǎng)絡(luò)中,在其基礎(chǔ)上提出了一種改進(jìn)的下降迭代檢測算法.試驗(yàn)結(jié)果表明,該算法與貝葉斯檢測算法相比,檢測概率提高了13%.目前,該算法只能檢測出無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的工作狀態(tài).不能夠恢復(fù)工作傳感器檢測的實(shí)際環(huán)境信號.另外在性噪比比較小的情況下,成功檢測概率會減小.因此,這些方面的改進(jìn)將是下一步研究的重點(diǎn).

[1] A takli IdrisM,Hu Hongbing,Chen Yu,et al.M alicious node detection in w ireless sensor networks using weighted trust evaluation[C]//ACM.The 2008 Spring S imulation M ulticonference,SanD iego:ACM Press,2008:836-843.

[2] 胡立瓊,舒 堅(jiān),吳振華,等.應(yīng)用于事件檢測的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)死活狀態(tài)的研究[J].計(jì)算機(jī)科學(xué),2009,36(9):39-43.

[3] M eng Jia,L iHusheng,Han Zhu.Sparse event detection in w ireless sensor networks using compressive sensing[C]//Barbara A Sullivan.The 43rd A nnual Conference on Information Sciences and System s.Jeff Sooknarine:Johns-Hopkins U niversity,2009: 181-185.

[4] Candes E J,Tao T.N ear-opt imal signal recovery from random projections: U niversal encoding strategies[J].IEEE T rans Inform Theory,2006,52(12):5406-5425.

[5] Bruckstein A,Donoho D L,Elad M.From sparse solutions of system s of equations to sparse modeling of signals and images[J].SI AM Review,2007,51(1):34-81.

[6] Donoho D L,EladM.Opt imally sparse representation in general(non-orthogonal)dictionaries via L 1 m in im ization[J].Proc N atl A cad Sci,2003,100(5):2197-2202.

[7] Rao B D,KreutzD K.A n affine scaling methodology for best basis selection[J]. IEEE T ransactions on Signal Processing,1999,47(1):187-200.

Sparse EventDetection Based on Compressive Sensing

Zhu Cuitao,Q u Y i
(College of Electronics and Information Engineering,South-CentralU niversity for N ationalities,W uhan 430074,China)

In the w ireless sensor networks,to improve detection probability,a modified descent iterative algorithm is proposed based on compressive sensing,which could adjust the parameter dynam ically,and then change the value of weight.A s a result,the speed of algorithm′s convergence can be accelerated.Exper imental results show that,other things being equal,comparing w ith the bayesion algorithm,the detection probability of modified descent iterative algorithm is improved averagely by 13%.

compressive sensing;sparse event detection;w ireless sensor networks

TP393.17

A

1672-4321(2011)01-0080-04

2010-12-10

朱翠濤(1967-),男,博士,教授,研究方向:認(rèn)知無線電網(wǎng)絡(luò)及分布式計(jì)算,E-mail:zhucuitao@gmail.com

國家自然科學(xué)基金資助項(xiàng)目(61072075)