楊小琴，朱玉全

(1.南京工業(yè)大學浦江學院，江蘇 南京 210000；2.江蘇大學計算機科學與通信工程學院，江蘇 鎮(zhèn)江 212013)

無線傳感器網(wǎng)絡實質(zhì)上是由帶有計算、通信及存儲功能傳感器節(jié)點構成的分布式感知網(wǎng)絡[1-2]。在信息技術日益完善的同時，計算機無論在生活中還是工作中都占據(jù)著不可或缺的地位，大量數(shù)據(jù)被保存到無線傳感器網(wǎng)絡中，這種保存方法雖然有著方便快捷的特點，但是當網(wǎng)絡空間不足時，會導致部分數(shù)據(jù)被誤刪[3]，且這種問題是不可避免的，因此急需要一種對網(wǎng)絡誤刪數(shù)據(jù)進行恢復的方法。

文獻[4]提出了基于學習矩陣補全框架的無線傳感器網(wǎng)絡中魯棒數(shù)據(jù)恢復方法。 采集無線傳感器網(wǎng)絡數(shù)據(jù)，使用少量接收測量的同時，恢復整個數(shù)據(jù)矩陣。 基于矩陣完成方法的新技術，接收到的讀取矩陣包含與非活動節(jié)點相對應的多個缺失行，考慮節(jié)點間相關性的聚類技術，基于互補極小化問題的插值技術，保證了非活動節(jié)點讀數(shù)的恢復。 通過實驗驗證了該方法具有一定的有效性。 文獻[5]提出了改進壓縮感知算法的WSN 數(shù)據(jù)恢復方法。 首先通過壓縮感知算法，對無線傳感網(wǎng)絡中部分誤刪數(shù)據(jù)的節(jié)點進行恢復，利用原始數(shù)據(jù)節(jié)點以及恢復節(jié)點聯(lián)合網(wǎng)絡拓撲和數(shù)據(jù)騾子，將所有誤刪數(shù)據(jù)進行恢復，其次利用二次規(guī)劃對訪問失效傳感器的鄰居節(jié)點進行重構，實現(xiàn)無線傳感器網(wǎng)絡誤刪數(shù)據(jù)恢復。該方法的數(shù)據(jù)恢復所用成本較低。

雖然以上兩種方法均能夠有效實現(xiàn)數(shù)據(jù)恢復，但在對誤刪數(shù)據(jù)恢復過程中沒有對誤刪數(shù)據(jù)進行定位處理，使得在恢復數(shù)據(jù)過程中加大計算量，導致出現(xiàn)數(shù)據(jù)恢復耗時長、數(shù)據(jù)恢復成功率低和特征擬合程度低的問題。 為了解決上述方法中存在的問題，提出基于匹配追蹤的無線傳感器網(wǎng)絡誤刪數(shù)據(jù)恢復算法。

1 誤刪數(shù)據(jù)的迭代定位計算

由于無線傳感網(wǎng)絡會出現(xiàn)數(shù)據(jù)被誤刪的情況[6]，因此，為了精確恢復誤刪數(shù)據(jù)，首先設計匹配跟蹤算法，對誤刪數(shù)據(jù)進行迭代定位計算，利用Gram-Schmidt 正交化方法，通過迭代生成新原子正交化，預測誤刪數(shù)據(jù)位置。

匹配跟蹤算法[7-9]主要根據(jù)數(shù)據(jù)的稀疏度進行定位，匹配追蹤算法是連續(xù)迭代的計算，每次迭代時原子字典D 會自動查找和殘缺信號關聯(lián)度最大的原子，經(jīng)過不斷地迭代，殘缺信號的能量會漸漸下降，匹配追蹤算法的特點就是每次迭代過程中都會選擇和原始字典中殘缺信號最接近的殘缺信號，進而最大程度降低殘缺信號的能量。

正交追蹤算法主要利用Gram-Schmidt 正交化實現(xiàn)的，假設匹配算法中感知信號矢量為z，每次迭代計算時感知信號的正交投影過程[10]，即標準正交匹配過程的表達式為:

式中:Ds代表原子字典的系數(shù)向量，Ws代表相應支持集中的系數(shù)向量。

標準正交匹配算法[11]中需要對其中的最小二乘問題進行求解，因此需提前計算出向量Ds的偽逆進而得出式(1)的解，現(xiàn)已知當矩陣維度增加，偽逆的計算難度也會加強，為降低計算難度，需要使用QR 因子分解子字典，假設原子字典D中原子的QR 因子分解公式為:

式中:Dk代表原子字典D的列正交，Rk代表主對角線中存在正對角線因子的上三角矩陣，k代表迭代次數(shù)，λk代表正交矩陣。

令在迭代過程中選取的第i個原子為di，根據(jù)式(1)和式(2)更新出正交投影過程的計算表達式為:

根據(jù)Dk和λk的空間等價的特點得出RkWs＝ak，則式(3)變?yōu)槿缦鹿?

根據(jù)QR 分解因子的特點得出的表達式為:

進而加快的求解速度，得出迭代后的最優(yōu)解。

盡管不斷降低計算復雜度，但是在不斷更新正交矩陣λk以及Rk的過程中，迭代次數(shù)增加的同時三角矩陣的代價也會增加，所以需要通過正交化不斷更新正交矩陣λk以此降低計算復雜度，因為原子字典中只有前k列才具有QR 分解，所以只有前k列才能分解λkRk，只需利用匹配算法過程查詢λk的最后一列即可，進而得出λk，其表達式為:

式中:λk+1的計算公式為:

式中:λk代表λk匹配運算投影到張成空間(包含所有向量的線性組合所構成的空間)，dk+1代表原子字典中的原子，(ξ-λk)代表λk匹配運算投影到張成空間的正交補空間的分量，Pk+1代表原子的空間分量。

同理，根據(jù)正交標準化即可更新出三角矩陣Rk+1，矩陣的更新公式為:

式中:v和χ的公式分別為:

式中:v代表三角矩陣中的原子向量參數(shù)，χ代表常數(shù)項參數(shù)。

同理可知，計算出后，即可根據(jù)矩陣分塊得出偽逆的三角矩陣的更新表達式:

利用匹配追蹤算法，在誤刪數(shù)據(jù)定位的過程中不需要計算三角矩陣Rk，只需對λk和R-1k更新即可。 在定位過程中目標對象可能不在中心位置，這種情況下誤刪數(shù)據(jù)的相對稀疏信號為近似稀疏信號[12]，其中帶有少量的非零元素，為了加強誤刪數(shù)據(jù)定位精度，利用質(zhì)心算法[13]對稀疏向量w中的非零元素的目標信息進行處理。 假設第l個誤刪數(shù)據(jù)周圍有e個點相應的值wl(i)，且每個誤刪數(shù)據(jù)相應的值必須大于閾值?，進而得出所有格點的集合，其表達式為:

式中:i代表個點坐標的對應點。

所以利用集合sl的質(zhì)心即可預測誤刪數(shù)據(jù)的位置，則誤刪數(shù)據(jù)的預測位置為:

式中:(xi，yi)表示第i個誤刪數(shù)據(jù)的位置坐標。

2 誤刪傳感數(shù)據(jù)恢復問題轉(zhuǎn)化計算

在通過迭代定位計算誤刪數(shù)據(jù)，預測到誤刪數(shù)據(jù)位置后，為了進一步加強數(shù)據(jù)恢復的準確性，基于時間穩(wěn)定性的線性差值模型，估算出無線傳感器網(wǎng)絡中的誤刪數(shù)據(jù)值，將無線傳感網(wǎng)絡誤刪數(shù)據(jù)恢復問題轉(zhuǎn)化為二次規(guī)劃問題，通過迭代得出最終解，以此實現(xiàn)誤刪數(shù)據(jù)恢復。

假設在t個時間間隙的周期中，某個無線傳感器收集到的感知屬性為Gj＝((y1j，T1)，…，(ytj，Tt))，任意時間的誤刪感知值為ymj，當估算值與ymj之差最小，即可確定為最佳誤差估計值。

通常情況下，在一個時間間隙中，感知數(shù)據(jù)[14]均是平穩(wěn)的，可通過感知數(shù)據(jù)的時間穩(wěn)定性建立分段線性函數(shù)，根據(jù)現(xiàn)有的數(shù)據(jù)點開展線性插值，進而估算誤刪數(shù)據(jù)。 令無線傳感器網(wǎng)絡中的某個節(jié)點為ni，當t時刻無線傳感器網(wǎng)絡出現(xiàn)誤刪數(shù)據(jù)時，根據(jù)其相近時刻Tiu的感知數(shù)據(jù)yiu和Tiv時刻的感知數(shù)據(jù)yiv建立出線性分段函數(shù)，其表達式為:

進而得出t時刻的誤刪數(shù)據(jù)估算值，其表達式為:

基于估算的誤刪數(shù)據(jù)進行數(shù)據(jù)恢復，通常情況下在誤刪數(shù)據(jù)恢復過程中會將其轉(zhuǎn)換成1 范數(shù)最小化問題，但會在一定程度上忽略部分誤刪數(shù)據(jù)，所以需要將1 范數(shù)最小化問題再次轉(zhuǎn)化成二次規(guī)劃問題更加合理[15-16]，根據(jù)線性規(guī)劃理論可知，當閾值κ≥0，此時的1 范數(shù)最小化問題的解為:

式中:τ代表偽隨機序列構成的矩陣，y代表無線傳感器節(jié)點收集數(shù)據(jù)與接收數(shù)據(jù)之間的聯(lián)系，x代表無線傳感器網(wǎng)絡的數(shù)據(jù)變量。

假設變量分為正負兩部分，將正變量標記為α，負變量為β，且兩變量均大于等于0，則有界約束的二次規(guī)劃問題的表達式為:

式中:I代表1 范元素集合，N代表元素數(shù)量，T代表誤刪數(shù)據(jù)監(jiān)測的時刻。

表1 無線傳感器網(wǎng)絡硬件參數(shù)

進而得出無線傳感器誤刪數(shù)據(jù)恢復問題轉(zhuǎn)化成二次規(guī)劃問題的標準公式:

式中:A代表偽隨機序列集合。

運用阿米霍步長準則對式(17)進行求解即可得到誤刪數(shù)據(jù)。 即根據(jù)誤刪數(shù)據(jù)的定位和估算值計算出標量的初始值，其表達式為:

式中:g(k)代表定義向量。

通過初始化標量η0和參數(shù)φ構建出序列ι元素，其中參數(shù)φ∈(0，1)，憑借阿米霍步長準則的回溯線搜索將ι元素中的每種元素進行迭代到達標量η(k)的位置，直至最終的原子di+1大于前一個原子di，此時將標量η(k)的值進行記載。

完成上述操作后需要斷定是否停止迭代，若迭代條件滿足下列不等式，則停止迭代，并輸出最終解:

式中:?F(z)代表梯度方向。

則誤刪數(shù)據(jù)的最終解為:

若不滿足，則重新計算標量的初始值，再以此進行迭代直至得出最終結(jié)果。

3 仿真結(jié)果與分析

為了驗證基于匹配追蹤的無線傳感器網(wǎng)絡誤刪數(shù)據(jù)恢復算法的有效性，利用MATLAB 軟件對所提方法、文獻[4]方法和文獻[5]方法進行仿真，仿真結(jié)果如下所示。 為了證明所提方法的可行性，需要選取硬件數(shù)據(jù)支持，無線傳感器網(wǎng)絡硬件參數(shù)如表1所示。

3.1 數(shù)據(jù)恢復耗時

誤刪數(shù)據(jù)恢復對時效性的要求較高，部分數(shù)據(jù)僅在某一時刻時被利用，所以必須在最快時間內(nèi)完成恢復，且保證恢復質(zhì)量。

在上述仿真環(huán)境下利用三種方法對RAMCloud數(shù)據(jù)集群的誤刪數(shù)據(jù)進行恢復，設置不同成功率，判斷每種方法恢復數(shù)據(jù)所需的耗時，對比結(jié)果如圖1所示。

圖1 不同方法的數(shù)據(jù)恢復耗時對比結(jié)果

根據(jù)圖1 可知，隨著恢復成功率的增加，不同方法的誤刪數(shù)據(jù)恢復耗時逐漸增加。 當恢復成功率為90%時，文獻[4]方法和文獻[5]方法的誤刪數(shù)據(jù)恢復耗時分別為14.7 s 和27.1 s，而所提方法的誤刪數(shù)據(jù)恢復耗時僅為10.4 s。 所提方法和文獻[4]方法的耗時相近，但所提方法的用時更短，而文獻[5]方法的耗時遠遠大于其他兩種方法。 由此可知，所提方法的誤差數(shù)據(jù)恢復效率高，時效性強。 這是因為所提方法對誤刪數(shù)據(jù)的位置進行預測，可減少最終的計算量，從而加快誤刪數(shù)據(jù)恢復時間。

3.2 恢復后數(shù)據(jù)與原始數(shù)據(jù)特征向量擬合程度

無線傳感器網(wǎng)絡數(shù)據(jù)是根據(jù)網(wǎng)絡節(jié)點進行傳輸，會因為數(shù)據(jù)包所包含信息不同出現(xiàn)特征幅度值變化，以50 個節(jié)點為一個節(jié)點簇，將簇最完整的數(shù)據(jù)特征向量幅度值，與其余三種方法的復原后幅度值進行擬合，得出其中擬合程度最高的方法，即為最優(yōu)方法，對比結(jié)果如圖2 所示。

圖2 不同方法的數(shù)據(jù)恢復特征向量的擬合程度

根據(jù)圖2 可知，在700 個節(jié)點編碼中，文獻[4]方法和文獻[5]方法的數(shù)據(jù)恢復特征幅值與原始特征幅值的最大誤差分別為0.98 和0.99，而所提方法的數(shù)據(jù)恢復特征幅值與原始特征幅值的最大誤差僅為0.21。 相比文獻[4]方法和文獻[5]方法，所提方法與原始數(shù)據(jù)傳輸過程中幅度值最接近。 由此可知，所提方法的恢復后數(shù)據(jù)與原始數(shù)據(jù)特征向量擬合程度較好，能夠有效確保無線傳感器網(wǎng)絡關鍵數(shù)據(jù)的完整性。

3.3 數(shù)據(jù)恢復成功率

為了進一步驗證所提方法的有效性，盡可能降低三種方法在仿真過程中的偶然性，選取15 組完全不同的仿真樣本，并將其設置成編號1~編號15，每組編號中的刪除數(shù)據(jù)位置不同且數(shù)量也不相同，使用信息熵作為驗證指標，誤刪前每組信息熵均為1，在每組仿真下均用三種數(shù)據(jù)恢復方法對數(shù)據(jù)進行處理，對比結(jié)果如圖3 所示。

圖3 不同方法的數(shù)據(jù)恢復成功率對比結(jié)果

根據(jù)圖3 可知，當樣本編碼為15 時，文獻[4]方法和文獻[5]方法的平均數(shù)據(jù)恢復成功率為87.33%和75.93%，而所提方法的平均數(shù)據(jù)恢復成功率高達98.76%。 由此可知，所提方法的數(shù)據(jù)恢復能力較強。

4 結(jié)束語

隨著無線傳感器網(wǎng)絡大規(guī)模的普及，其中不可避免出現(xiàn)誤刪數(shù)據(jù)，為此提出基于匹配追蹤的無線傳感器網(wǎng)絡誤刪數(shù)據(jù)恢復算法，通過匹配算法對誤刪數(shù)據(jù)進行定位，并估算預測出粗略的誤刪數(shù)據(jù)，在二次規(guī)劃問題的幫助下得出誤刪數(shù)據(jù)，實現(xiàn)無線傳感器網(wǎng)絡誤刪數(shù)據(jù)恢復，解決了數(shù)據(jù)恢復耗時長、數(shù)據(jù)恢復成功率低的問題，保證網(wǎng)絡數(shù)據(jù)的時效性，也確保用戶可以獲取準確無誤的數(shù)據(jù)。