改進壓縮感知算法的WSN數(shù)據(jù)恢復方法

陳 雪，胡玉平

(1.廣州工商學院 計算機科學與工程系，廣東 廣州 510850；2.廣東財經(jīng)大學 信息學院，廣東 廣州 510320)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)[1]是人們采集數(shù)據(jù)、重建數(shù)據(jù)的重要工具。但是由于環(huán)境的影響，利用WSN采集數(shù)據(jù)時很容易產(chǎn)生數(shù)據(jù)丟失[2,3]。因此，針對WSN中丟失數(shù)據(jù)的恢復研究很顯得至關(guān)重要。

常用的數(shù)據(jù)恢復算法有以下幾種：K-最近鄰(K-nearest neighbors，KNN)算法[4]。該算法首先給定K的值，找到分布在丟失數(shù)據(jù)節(jié)點附近的K個相鄰節(jié)點，利用這些相鄰節(jié)點攜帶的數(shù)據(jù)信息值，結(jié)合加權(quán)平均算法或者線性擬合方法估算出丟失的數(shù)據(jù)。多通道奇異頻譜分析(multi-channel singular spectrum analysis，MSSA)[5]是一種插值算法，它是一種自適應的基于非參數(shù)的算法，在氣象或者地理等領(lǐng)域中應用廣泛。壓縮感知(compressive sensing，CS)是一種新型的數(shù)據(jù)恢復算法，該算法可以根據(jù)少量的已知數(shù)據(jù)實現(xiàn)丟失數(shù)據(jù)的恢復[6,7]。

近年來，在傳統(tǒng)WSN數(shù)據(jù)恢復算法的基礎(chǔ)上，學者們相繼提出許多新型的算法。例如，文獻[8]提出一種基于多屬性協(xié)助和壓縮感知的數(shù)據(jù)恢復精度優(yōu)化算法(MACS)，大大降低了數(shù)據(jù)恢復中的差錯率，然而，該方法中的多屬性協(xié)助需要準備的前期工作較多，不利于實際應用。文獻[9]為解決數(shù)據(jù)丟失問題，利用線性預測編碼進行稀疏化變換，采用正交匹配追蹤(OMP)算法進行數(shù)據(jù)恢復，一定程度上提高了數(shù)據(jù)恢復精度，然而，該方法僅適用于小規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的恢復。文獻[10]設(shè)計一種用于無線傳感網(wǎng)絡(luò)的離散拉普拉斯算子(DLO-WSN)，提出基于該算子的數(shù)據(jù)選擇算法(LDS)，可適用于較大規(guī)模的數(shù)據(jù)恢復，然而，該方法具有較高的計算開銷。

在保證數(shù)據(jù)恢復成功率的情況下，為了更好地降低所耗費的成本，提出了一種基于改進壓縮感知算法和單位圓盤圖模型的WSN數(shù)據(jù)恢復方法。主要創(chuàng)新點如下：①根據(jù)改進的壓縮感知算法，估算出部分丟失數(shù)據(jù)的傳感器節(jié)點數(shù)據(jù)信息，并把這些估算出信息的傳感器節(jié)點當作已知節(jié)點，從而更好地估算其它丟失信息節(jié)點；②通過二次規(guī)劃實現(xiàn)數(shù)據(jù)的重構(gòu)，并采用一組具有先進移動能力的移動傳感器來訪問失效傳感器的鄰居節(jié)點，重新獲取丟失數(shù)據(jù)，有助于提升數(shù)據(jù)恢復的精度；③通過構(gòu)建最優(yōu)匯聚樹和查找不同網(wǎng)絡(luò)結(jié)構(gòu)(如線性圖和網(wǎng)格)中的最優(yōu)節(jié)點位置，有效降低了數(shù)據(jù)恢復的成本。

1 改進壓縮感知算法

利用該算法實現(xiàn)數(shù)據(jù)恢復，實際上就是求解一個欠定狀況下的線性方程組。由于該類方程組存在無數(shù)組解，為了得到較好的結(jié)果，有學者將該類方程組轉(zhuǎn)換成1范數(shù)最小化問題，并提出多種匹配算法，比如匹配追蹤(matching pursuit，MP)算法[11]、正交匹配追蹤(orthogonal matching pursuit，OMP)算法[12]、分段正交匹配追蹤(stage wise OMP，St OMP)算法等[13]。但以上算法對于數(shù)據(jù)恢復的效果并不是很理想。于是，本小節(jié)提出利用二次規(guī)劃的方式求解欠定狀況下的線性方程組，并結(jié)合阿米霍步長準則(Armijo rule)實現(xiàn)數(shù)據(jù)恢復。

(1)

另外，由于外界傳輸環(huán)境的影響，Sink節(jié)點[14]接收的數(shù)據(jù)和WSN節(jié)點傳輸?shù)臄?shù)據(jù)會有所差別，具體可表示為

y=φx+n

(2)

(3)

利用二次規(guī)劃的方式解決式(3)所示的1范數(shù)最小化問題。根據(jù)二次線性規(guī)劃理論，可用式(4)所示的凸優(yōu)化問題的解來代替式(3)所述問題，其中τ>0

(4)

在式(4)中，為了方便求解，可以將變量x用變量x1和x2的差值表示，則變量x可寫成如下形式

x=x1-x2(x1≥0,x2≥0)

(5)

從而有

(6)

其中，(xi)+=max{0,xi}。 綜上可得

(7)

其中，IN=[1,1,…1]T，該向量包含N個元素1。那么式(4)可表示為二次規(guī)劃的形式

(8)

其中，x1≥0,x2≥0。

將式(8)改寫成標準的二次規(guī)劃表示形式

(9)

其中

(10)

式中：e(k)>0。 令

z(k+1)=z(k)+λ(k)(w(k)-z(k))

(11)

式中：λ(k)∈[0,1]，并且

(12)

通過定義向量g(k)來估算e(k)的初始值，以便使F(z) 存在最小值，g(k)可表示為

(13)

根據(jù)式(13)求得e(k)的初始值e0為

e0=argminF(z(k)-eg(k))

(14)

綜上所述，改進算法的步驟如下：

(1)給定z(0)，參數(shù)f∈(0,1)，μ∈(0,1/2)，k=0；

(2)由式(14)得到e0的值；

(3)根據(jù)e0、f構(gòu)建序列γ=e0,fe0,f2e0,…；

若不滿足上述條件，k←k+1，返回(2)。

2 數(shù)據(jù)騾子(data mule)

數(shù)據(jù)騾子(data mule)[15]是一種通過物理方式攜帶計算機與存儲器的交通工具，它的移動性能強，可在遠程位置處創(chuàng)建有效數(shù)據(jù)通訊鏈路，進行數(shù)據(jù)的采集和監(jiān)控。

為方便描述，表1給出了本文常用的特殊符號及其含義。

表1 符號及其含義

圖1表示兩個節(jié)點失效的mule旅行示意圖。灰色表示已經(jīng)失效的傳感器節(jié)點；虛線表示mule旅行；旅行從m節(jié)點開始，結(jié)束于m節(jié)點。T是一棵基于歐式平面，根為r，具有n個無線傳感器的匯聚樹。數(shù)據(jù)從葉子節(jié)點傳播到根節(jié)點r。 文中用有向完全圖G=(V,E) 表示仿真環(huán)境，其中節(jié)點集表示無線傳感器，邊集表示傳感器間的距離或通訊時間。若傳感器v發(fā)生故障，我們并不希望丟失從其子節(jié)點T,δ(v,T) 獲取的數(shù)據(jù)。因此，mule必須穿越于δ(v,T) 間，恢復丟失的信息。文中將該問題定義為(α,β)-mule問題，其中α表示發(fā)生故障的節(jié)點數(shù)，β表示旅行的mule數(shù)。

圖1 兩個節(jié)點失效的mule旅行

3 單位圓盤圖模型

本文主要對單位圓盤圖模型進行了研究。在單位圓盤圖模型中，當且僅當d(u,v)≤1時，節(jié)點對存在有向邊。其中d(u,v) 表示節(jié)點u和v之間的歐式距離。表2所示為基于單位圓盤圖模型的4種(1,1)-Mule變異問題。其中任意兩節(jié)點u,v∈V，如果滿足d(u,v)≤1，則能互相通訊。

表2 基于單位圓盤圖模型的4種(1,1)-Mule變異問題

3.1 基于線性拓撲的(1,1)-Mule問題

假設(shè)有n個節(jié)點，它們間的距離為單位距離，分布在歐式平面上。該設(shè)置確保節(jié)點只能與相鄰節(jié)點進行通訊。對于那些基于通訊約束下的線拓撲結(jié)構(gòu)，定義樹的結(jié)構(gòu)和方向只需知道根r的位置。因此，解決方案成本由r和m的位置唯一決定。為了更清楚地表述，定義節(jié)點編號為1到n，m和r分別表示解決方案中所指的mule和根。考慮對稱性，因為c(m,r)=c(n-m+1,n-r+1)，其中c(m,r) 是最優(yōu)解決方案成本，假設(shè)r≥m。 此時mule位于m、 根位于r，解決方案由r的位置決定。圖2所示為線路拓撲圖，共包含6個節(jié)點，4種不同的情況。其中，樹T的不同解決方案有兩種情況，mule的位置選擇有兩種情況。累加和表示失效節(jié)點i,i∈{1,…,6} 對應的成本。

圖2 線路拓撲

引理1 對于線性拓撲結(jié)構(gòu)，根r的最優(yōu)位置是n-1。

證明：假設(shè)m

下文將論證當使用成本為0時 (r

3.2 基于線性拓撲的(α-1)-Mule問題

下面論證求解該問題的一種算法。

引理3 當m∈[1,n-2] 時，c(m,n-1) 存在多項式時間內(nèi)的解析解。

由引理1可知根的最優(yōu)位置為n-1。因此，為了找到最優(yōu)的解決方案，可搜索令c(m,n-1) 最小化的m值。使用動態(tài)規(guī)劃和記憶表，在O(n2) 時間內(nèi)計算c(i,j) 值總成本。因此，算法運行時間復雜度為O(n2)。

引理4 當mi時，滿足π(i,m,r)=π(i,m-1,r)。

證明：只要m≠i，則i處的mule就不改變方向。

引理5c(m+1,r)=c(m,r)+πl(wèi)(m,r)+π(m,m+1,r)-πr(m,r) 并且c(m-1,r)=c(m,r)-πl(wèi)(m,r)+π(m,m-1,r)+πr(m,r)。

引理7 當πl(wèi)(m,r) 單調(diào)遞增時，πr(m,r) 也單調(diào)遞增。

由引理4可知，無論數(shù)據(jù)騾子怎么放置，只要i>m，騾子到一個特定節(jié)點的旅行次數(shù)是不變的，由于增加m意味著有較少的節(jié)點分布在右側(cè)，相對于m而言方向不變，πl(wèi)(m,r) 的值也在增大。當在m的左側(cè)節(jié)點數(shù)目逐漸增加時，πl(wèi)(m,r) 的值會逐漸變小。

證明：基于引理6和引理7。

結(jié)合引理5和引理6，可知0≤c(m+1,n-1)-c(m,n-1)=πl(wèi)(m,n-1)-πr(m,n-1)+π(m+1,m,n-1)=πl(wèi)(m,n-1)-(πr(m,n)-Δ)+π(m+1,m,n-1)=π(m+1,m,n-1)+Δ。 0≤c(m-1,n-1)-c(m,n-1)=-πl(wèi)(m,n-1)+πr(m,n-1)+π(m-1,m,n-1)=π(m-1,m,n-1)-Δ。

綜上，結(jié)論如下：

3.3 基于隨機線性拓撲的(1,1)-Mule問題

本節(jié)將討論基于隨機直線的(1,1)-Mule問題，其中n分布于直線上，n≥L，這樣便可基于預先定義的分布函數(shù)進行取樣作為相鄰節(jié)點間的距離，最大距離為1。基于單位圓盤圖的通訊模型，只有當且僅當d(u,v)≤1時，節(jié)點u和v之間才會形成邊，這意味著該圖是連接的。然后，簡化假設(shè)，設(shè)mulem，根r為直線最左邊的節(jié)點，并且L∈N。

根據(jù)算法1構(gòu)建樹T，其中Topt為最優(yōu)樹；兩者成本分別為c(T)、c(Topt)。 定義TL為經(jīng)過L節(jié)點的樹，這樣相鄰節(jié)點間的距離正好為1；c(TL) 為對應的成本。觀察算法1可知，B為樹T中的骨干節(jié)點集，而不是葉子節(jié)點。

算法1：生成樹1

(1)V′=B=C={r}；

(2)E′=?；

(3)當|C|≠n時，

(4)令C為B中節(jié)點可到達的所有節(jié)點；

(5)找到B中節(jié)點可到達的最遠節(jié)點v；

(6)找到使得d(u,v) 最小化的u∈B；

(7)將v添加入B中；

(8)將邊e(v,u) 添加入E′；

(9)對于每個節(jié)點w∈C(〗v} 添加指向E′的有向邊；

(10)V′=V′∪C∪{v}；

(11)結(jié)束。

(12)發(fā)射T=(V′,E′)。

論述如下：

引理11c(TL)≤c(Topt)。

證明：至少需要L個節(jié)點來覆蓋長度為L的區(qū)域，并且在直線上的每個單位間隔必須包含至少一個節(jié)點。因此，可通過將區(qū)間 [i,i+1] 上的節(jié)點映射到T中i處的對應節(jié)點，并刪除區(qū)間內(nèi)多余節(jié)點，將任意樹轉(zhuǎn)換為TL樹。當m=0時，該轉(zhuǎn)換將降低解決方案的整體成本，即c(TL)≤c(Topt)。

引理12 |V(T)|≤2L。

證明：設(shè)v和l為算法1兩次迭代后得到的非葉子節(jié)點，vx和lx分別為其在x線性軸上的坐標。當lx與vx接近時，該算法以最慢速度收斂；但是，當l為區(qū)間 [vx,vx+1] 內(nèi)最遠節(jié)點時，意味著在l之后選擇的非葉子節(jié)點必定在區(qū)間 [vx+1,vx+1+λ] 內(nèi)。因此，在最壞的情況下，在兩次迭代中，算法只覆蓋了一個單位距離，這意味著至少得經(jīng)過2L步才能完成迭代。過程如圖3所示。

圖3 覆蓋長度L須放置將近2L個節(jié)點

引理

c

T

c

T

L

因此，將有：

引理14 基于算法1生成(1,1)-Mule問題的4-approximation解決方案。

3.4 基于網(wǎng)格拓撲的(1,1)-Mule問題

引理15 mule位于特定位置m處，(1,1)-mule問題中的任一顆樹的近似比不超過dmax。

證明：顯然，在任意一種算法中，mule必須訪問所有非根節(jié)點。在最壞的情況下，T中節(jié)點v只有一個子孫節(jié)點時，將會產(chǎn)生最小絕對值。那么，mule的旅行只能覆蓋一個節(jié)點。在最好的情況下，旅行包含了G中節(jié)點v的所有子孫節(jié)點，很顯然這與節(jié)點的度有關(guān)。論證結(jié)果表明，在最壞情況下節(jié)點v產(chǎn)生的成本和最優(yōu)解決方案成本的比例為dv，而在算法2中，mule必須訪問節(jié)點v的所有子孫節(jié)點(圖4)。

圖4 算法2

然后，將論述最優(yōu)旅行方案OPT的成本下邊界OPT。

圖5 鋸齒樹，成本為

接下來，利用算法2構(gòu)建一棵近似最優(yōu)成本樹。為了在每次故障時盡可能多地訪問節(jié)點，本文在多個連續(xù)星型的頂部構(gòu)建樹。

算法2：生成樹2

(1)星型：為所有節(jié)點(坐標為 (x,y)) 調(diào)整星的分布，滿足1≡ymod3(如圖4(a)所示)。

(2)指向：沿網(wǎng)格方向連接星。

設(shè)c為算法2生成樹成本，s為鋸齒樹成本。

4 實驗仿真與分析

基于不同拓撲結(jié)構(gòu)利用NS2仿真軟件[16]進行了多次實驗，每次實驗均進行了50次迭代，計算得出解決方案的平均成本。在大型網(wǎng)絡(luò)中，直接計算最短TSP問題是不可行的。因此，使用基于遺傳算法的TSP啟發(fā)式框架[17]。

為了驗證本文算法的優(yōu)勢，文中通過計算不同的拓撲設(shè)置下限，基于最優(yōu)旅行方案OPT成本的下邊界OPT比較了所提算法間的比例。

在第一次仿真結(jié)果如圖6所示，研究了算法1步驟4中選擇不同的領(lǐng)導對算法總成本的影響。文中基于不同競爭算法比較了實驗結(jié)果：隨機選擇一個節(jié)點作為領(lǐng)導者的貪婪算法1、選擇接近最右邊領(lǐng)導者的節(jié)點的貪婪算法2和改變相鄰節(jié)點到L/n的距離的最優(yōu)旅行方案算法。在仿真過程中，測試了相鄰節(jié)點距離的分布函數(shù)對算法性能的影響。圖6(a)使用了均值為0.1的指數(shù)分布；圖6(b)使用了均為值0.5的均勻分布。由實驗數(shù)據(jù)可知，指數(shù)分布的突發(fā)性導致了mule旅行距離的增加，從而導致了方案整體成本的增加。另外，算法1的實際近似比遠低于引理13中的證明。這表明，理論可能加強了近似比。

圖6 算法1與不同競爭算法間的成本比例

第二次仿真結(jié)果如圖7所示，將算法2與下述算法進行了比較：基于鋸齒樹的鋸齒算法(圖5)、基于最小平面樹的貪婪算法和最優(yōu)旅行方案算法。文中研究了兩種變化：mule置于坐標最左下角和置于中心。但值得注意的是，雖然兩個仿真中的算法保持不變，但將mule置于角落里時，成本高出許多。

圖7 算法2與不同競爭算法間的成本比例

5 結(jié)束語

該文首先利用改進壓縮感知算法，估算出部分丟失數(shù)據(jù)的傳感器節(jié)點數(shù)據(jù)信息，并把這些估算出信息的傳感器節(jié)點當作已知節(jié)點，參與到其余丟失信息節(jié)點的估算中。再利用mule來執(zhí)行關(guān)鍵任務，根據(jù)mule移動性能優(yōu)勢防止關(guān)鍵信息丟失。文中解決方案涉及構(gòu)建最優(yōu)匯聚樹和查找不同網(wǎng)絡(luò)結(jié)構(gòu)(如線性圖和網(wǎng)格)中的最優(yōu)節(jié)點位置。基于各類拓撲結(jié)構(gòu)特點，構(gòu)造了近似算法，并進行了仿真實驗，驗證了算法的性能。仿真結(jié)果表明，相比其它幾種算法，提出的算法完成數(shù)據(jù)恢復所用成本更低。

然而提出的算法也并非完美，它并沒有考慮不同硬件環(huán)境對傳感器耐久性的影響以及傳輸半徑對mule旅行的影響，下一步的工作主要集中在這兩方面上。