無線傳感網(wǎng)絡(luò)誤刪數(shù)據(jù)匹配追蹤恢復(fù)方法設(shè)計(jì)*

楊小琴，朱玉全

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

盡管不斷降低計(jì)算復(fù)雜度，但是在不斷更新正交矩陣λk以及Rk的過程中，迭代次數(shù)增加的同時(shí)三角矩陣的代價(jià)也會(huì)增加，所以需要通過正交化不斷更新正交矩陣λk以此降低計(jì)算復(fù)雜度，因?yàn)樵幼值渲兄挥星発列才具有QR 分解，所以只有前k列才能分解λkRk，只需利用匹配算法過程查詢?chǔ)薻的最后一列即可，進(jìn)而得出λk，其表達(dá)式為:

式中:λk+1的計(jì)算公式為:

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

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

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

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

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

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

式中:i代表個(gè)點(diǎn)坐標(biāo)的對應(yīng)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

式中:A代表偽隨機(jī)序列集合。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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