用于WSNs的間歇型參數(shù)估計算法

李 林

(天津商業(yè)大學(xué) 信息工程學(xué)院，天津 300134)

0 引 言

在無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)用于目標定位與追蹤、頻譜感知、自動雷達、導(dǎo)航及機器視覺等領(lǐng)域時，常常需要節(jié)點協(xié)同估計同一個未知參數(shù)。WSNs中的每個節(jié)點用一組輸入觀測未知參數(shù)，由于環(huán)境復(fù)雜這些觀測值是未知目標參數(shù)受多元噪聲如環(huán)境或測量噪聲干擾后的觀測值，由這些觀測數(shù)據(jù)所得到的參數(shù)與原始目標參數(shù)相去甚遠。所以，如何從噪聲干擾中精確地估計出原始目標參數(shù)是一個重要的問題[1]。參數(shù)估計算法已經(jīng)有了大量的研究，通常會選用一些自適應(yīng)算法作為參數(shù)估計算法，如線性預(yù)測算法、最速下降算法、遞歸最小二乘算法、平方根自適應(yīng)算法和最小均方(least mean square,LMS)自適應(yīng)等。

近些年來，解決WSNs中的參數(shù)估計問題一般有兩種不同類型的算法：一種是集中式的參數(shù)估計算法，另一種是分布式的參數(shù)估計算法。集中式估計算法是每一輪所有節(jié)點將自己的本地估計值傳輸給網(wǎng)關(guān)，網(wǎng)關(guān)收集網(wǎng)絡(luò)的全部信息后計算出全局的估計值，再發(fā)還給傳感器節(jié)點。由于每一輪的估計都獲取了網(wǎng)絡(luò)的全局信息，這種方法做出的參數(shù)估計非常精確。但是WSNs中節(jié)點的能量有限，這類算法用于WSNs中，每一輪估計時網(wǎng)關(guān)都需要與節(jié)點進行信息交互。特別地，當(dāng)網(wǎng)絡(luò)是多跳網(wǎng)絡(luò)時，能量消耗巨大，網(wǎng)絡(luò)的生存時間堪憂，無法在實際中應(yīng)用。分布式估計算法中每個節(jié)點對參數(shù)的估計無需網(wǎng)關(guān)參與，節(jié)點僅與部分其他節(jié)點交換自己計算出的本地估計信息，大大地降低了通信量，WSNs更適合分布式估計算法。

常見的分布式估計算法分為分布式增量[2,3]、擴散[4～6]和共識三種類型。分布式增量算法中，每個節(jié)點接收前一個節(jié)點的估計與自己的信息結(jié)合來進行下一時刻的估計，隨后再將自身的估計發(fā)送給下一節(jié)點。這種算法在節(jié)點數(shù)目較多和拓撲復(fù)雜時魯棒性較差。分布分布式共識和擴散算法中，節(jié)點每輪僅與其鄰居節(jié)點交換信息，將這些信息融合后，通過參數(shù)估計算法遞歸計算下一時刻的估計值[4]。分布式共識估計算法在于增加了一個強制鄰居節(jié)點合作的過程。文獻[7]指出，采用分布式擴散算法的網(wǎng)絡(luò)其估計性能優(yōu)于分布式共識算法，收斂速度更快而且均方偏差(mean square deviation,MSD)更小。與其他算法相比，分布式擴散算法有著更好的估計性能、更好的可擴展性和魯棒性。

為降低WSNs用于參數(shù)估計時的整體通信負載，本文提出了一種間歇型LMS參數(shù)估計算法。算法中，節(jié)點是否傳輸自身的估計值取決于一個交替參數(shù)，節(jié)點僅僅被間歇參數(shù)選中的時刻與鄰居節(jié)點交換估計值。有信息交換時，節(jié)點通過鄰居節(jié)點和自身的估計值加權(quán)做和，作為下一時刻估計值的更新依據(jù)；無信息交換時，節(jié)點僅用自身的本地估計值作為下一時刻估計值的更新依據(jù)。最后節(jié)點根據(jù)得到的自適應(yīng)歸一化步長，計算出下一時刻的估計值。通過該算法，可在損失少許估計性能的情況下大大降低網(wǎng)絡(luò)通信負載。

1 問題描述

本文所考慮的問題是一個有N個節(jié)點的WSNs，典型的N=10的用于參數(shù)估計的WSNs如圖1所示。

圖1 N=0的用于參數(shù)估計的WSNs模型

其中，圓圈表示節(jié)點，箭頭表示節(jié)點之間的通信鏈路，WSNs參數(shù)估計的線性回歸模型可表示為

(1)

2 分布式LMS擴散算法

集中式LMS算法中，網(wǎng)關(guān)需要收集整個WSNs的全局信息，集中地處理這些信息。傳感器節(jié)點需要每輪將信息發(fā)送或者轉(zhuǎn)發(fā)給Sink節(jié)點，每輪的估計都會產(chǎn)生很大的通信負載[8]。在WSNs中，節(jié)點通常由電池供電，能量非常寶貴，而節(jié)點的能量大部分由通信模塊消耗。由于通信量太大，集中式LMS算法很難用于實際的WSNs。當(dāng)網(wǎng)絡(luò)拓撲變化或者通信鏈路改變時，集中式LMS算法的估計性能也會變得很差。為了克服集中式LMS算法的缺陷，本文采用分布式LMS擴散算法。

在分布式共識和擴散LMS算法中，每個節(jié)點只需要與鄰居節(jié)點交換估計信息來獲取估計值，如圖2所示。

如果兩個節(jié)點可以直接通信，則定義這兩個節(jié)點互為鄰居節(jié)點[9]。例如，節(jié)點7的鄰居節(jié)點定義為Ω7，其中，Ω7包含節(jié)點7本身。每個節(jié)點需要計算其本地估計值，并從鄰居節(jié)點中獲取鄰居節(jié)點的本地估計。如圖2中，箭頭表示節(jié)點之間的通信鏈路，節(jié)點7的鄰居節(jié)點集合Ω7為節(jié)點3,5,6,7,8。這些節(jié)點可以與節(jié)點7直接通信。由于網(wǎng)絡(luò)采用分布式共識和擴散算法，當(dāng)網(wǎng)絡(luò)中一些節(jié)點無法正常通信，整個網(wǎng)絡(luò)仍能繼續(xù)工作。

圖2 分布式LMS擴散算法中用于參數(shù)估計的WSNs模型

分布式擴散LMS參數(shù)估計算法可以分為3個階段，分別是信息交換階段、適應(yīng)階段和融合階段。根據(jù)網(wǎng)絡(luò)的拓撲，節(jié)點i賦予不同的融合系數(shù)來融合每個鄰居的估計值

(2)

式中γii為節(jié)點i自身估計值的融合系數(shù)，γij為其鄰居節(jié)點j在節(jié)點i的融合階段的融合系數(shù)，融合系數(shù)需要滿足式(2)。融合系數(shù)的計算多種規(guī)則，如Metropolis,Laplacian和最大度規(guī)則，本文中選用的Metropolis規(guī)則如式(3)所示

(3)

分布式共識算法與擴散LMS算法的主要區(qū)別是，共識算法在適應(yīng)階段用加權(quán)融合后的估計值和本地估計值結(jié)合用來計算下一時刻的估計值，擴散算法在數(shù)據(jù)融合后，適應(yīng)階段僅用融合后的估計值計算下一時刻估計值。文獻[3]指出，分布式擴散算法的網(wǎng)絡(luò)估計性能都優(yōu)于分布式共識算法，收斂速度更快而且MSD更小。這里選用分布式擴散LMS算法，并給出推導(dǎo)過程。

分布式擴散LMS算法中，節(jié)點需要從自身以及鄰居節(jié)點的估計值中尋求對未知參數(shù)wo的估計。在每個t時刻，節(jié)點i對的估計值為wi(t)，則下一時刻t+1的估計值的更新方程的遞歸表達式為

(4)

式中μi為節(jié)點i的LMS算法步長。

(wi-wj(t))+o‖wi‖2

(5)

同樣的，可以將其在wi(t)處也用泰勒級數(shù)展開，可得

(wi-wj(t))+o‖wi‖2

(6)

隨后，將式(5)和式(6)都代入式(4)中，因為融合系數(shù)滿足式(2)，則式(4)可以轉(zhuǎn)換為式(7)

(7)

式中 大括號內(nèi)部的式子是一個關(guān)于wi的函數(shù)f(wi)。為了得到wi(t+1)，則需要求出使得f(wi)最小的wi

f′(wi)=0

(8)

則求解關(guān)于wi的方程(8)，可得出wi(t+1)的分布式更新函數(shù)為

(9)

(10)

式(9)為適應(yīng)階段，式(10)為融合階段，分布式擴散LMS算法可表示為圖3。

圖3 分布式擴散LMS算法架構(gòu)

3 間歇型參數(shù)估計算法

對于WSNs，第2章中的標準分布式擴散LMS的網(wǎng)絡(luò)負載依然很高。而如果節(jié)點僅僅用自身估計值而不與鄰居節(jié)點合作，計算出的下一時刻估計值精確度不夠，整體網(wǎng)絡(luò)估計性能較差，很難滿足需求。本文提出的一種用于WSNs參數(shù)估計的分布式間歇型參數(shù)估計算法，該算法可根據(jù)網(wǎng)絡(luò)的估計精度需求，降低網(wǎng)絡(luò)整體通信負載。

為進一步降低通信負載進而降低網(wǎng)絡(luò)的能量消耗，間歇型參數(shù)估計算法中節(jié)點不需要在每個時刻t都進行信息交換。間歇型參數(shù)估計中引入了一個間歇參數(shù)P來決定節(jié)點是否在此時刻發(fā)送自身的本地估計值。網(wǎng)絡(luò)正常工作時P個單位時刻作為一個單位循環(huán)。在一個循環(huán)中，前P-1個時刻節(jié)點只有適應(yīng)過程，僅用自身估計值更新下一時刻的估計值，最后一個時刻與鄰居之間交換信息，觸發(fā)融合階段，用融合后的估計值用來更新。

簡單的說，節(jié)點僅僅在時刻“tmodP=0”時為選中狀態(tài)，與鄰居節(jié)點交換自身的估計信息。通過間歇型參數(shù)估計算法，通信負載降低至標準擴散算法的1/P。為了提高網(wǎng)絡(luò)的估計性能，這里提出的間歇型參數(shù)估計算法將步長μ歸一化處理，用μ′代替標準擴散算法中μ，μ′用式(11)計算

(11)

算法步驟如算法1。

算法1間歇式參數(shù)估計算法

Initialize:

Set the alternative parameter P;

Foreach node iWi(0)=0 for whereWiisMx 1 estimation vector

end

Running:

Foreach time instant t=1,2,...,T

Foreach node i=1,2,…,N

IftmodP=0

Combination:

elseφi(t+1)=wi(t)

end

Adaptation:

end

end

4 實 驗

為了與標準LMS算法對比，考慮網(wǎng)絡(luò)拓撲較為復(fù)雜的情況，仿真中采用的WSNs有N=50個節(jié)點，拓撲為隨機生成，具體圖4所示。

圖4 仿真拓撲圖

圖4中，端點表示傳感器節(jié)點，線段表示節(jié)點之間的通信鏈路。在仿真中，輸入回歸向量為AR-1[10]過程ui(t)=xi(t)+ρiui(t-1)的一個采樣ui(t)=[ui(t)ui(t-1)…ui(t-M+1)]T，相關(guān)系數(shù)ρi=0.5，xi(t)是一個σx,i=1的白噪聲過程。參數(shù)M=10，則回歸輸入向量ui(t)為10×1的向量。仿真中時間t=1,2,...,T，其中,T=2 000。每個節(jié)點的噪聲vi(t)是一個0均值的高斯過程。設(shè)每個節(jié)點的輸入回歸向量和噪聲都在時間和空間上相互獨立。

圖5 網(wǎng)絡(luò)平均MSD對比

圖5中可以看出，在時間t大于300時，幾種算法的MSD均可達到穩(wěn)定狀態(tài)。三種算法對比，本文提出的間歇型參數(shù)估計算法和NDLMS低于-40 dB，無合作NLMS算法低于-40 dB。仿真中,可以看出，NDLMS有最好的MSD性能，當(dāng)P=2時，間歇型參數(shù)估計的性能接近于NDLMS。隨著P的增大，MSD上升，節(jié)點平均估計性能降低。三種算法的收斂速度幾乎相同。

為評估穩(wěn)定狀態(tài)的估計性能，取后500個時刻的數(shù)據(jù)描述穩(wěn)定狀態(tài)，將這500個時刻的瞬時值求平均。定義節(jié)點i的穩(wěn)定狀態(tài)MSDi為：MSDi(dB)=20log(E‖w-wi(t)‖2)。圖6可以看出間歇型參數(shù)估計算法的穩(wěn)定狀態(tài)的MSD在P=2,5,8時，約在-50,-46,-44 dB。NDLMS約在-53 dB，無合作NLMS在-36 dB。三種算法的平均數(shù)值比較如表2所示，當(dāng)P=2,5,8時，間歇型參數(shù)估計算法可達到NDLMS算法MSD穩(wěn)定狀態(tài)估計性能的94.3 %，84.4 %和82 %。

圖6 各節(jié)點穩(wěn)定狀態(tài)的MSD性能對比

圖5、圖6和表1可以看出：交替系數(shù)P較小時的間歇型參數(shù)估計算法的收斂速度和MSD性能較好，可接近于NDLMS。表2為平均單位時刻傳輸?shù)臄?shù)據(jù)包數(shù)量對比，其中，NDLMS算法的數(shù)量為25 000。無合作NLMS中節(jié)點不與其他節(jié)點通信不作考慮。由于間歇型參數(shù)估計不是每時每刻都需要在鄰居節(jié)點之間交換估計值，其所需傳輸?shù)臄?shù)據(jù)包數(shù)量在P=2,5,8時分別為12 500,5 000，3 125。

表1 穩(wěn)定狀態(tài)下的平均MSD/dB對比

表2 平均通信負載對比

WSNs中NDLMS算法的通信負載較大，而無合作NLMS算法的性能又很難滿足估計性能要求，這里提出的間歇型參數(shù)估計算法在大大降低通信負載的同時，網(wǎng)絡(luò)估計性能接近于NDLMS。表2是仿真中NDLMS和間歇型參數(shù)估計的平均通信負載對比。通過間歇型參數(shù)估計，通過對特定網(wǎng)絡(luò)設(shè)置合適的交替參數(shù)，可以在網(wǎng)絡(luò)的估計性能和通信負載二者中找到平衡。

5 結(jié)束語

本文首先介紹了參數(shù)估計的背景，給出了WSNs參數(shù)估計問題的數(shù)學(xué)模型。隨后，深入地介紹了集中式LMS的算法和分布式LMS算法的優(yōu)劣，指出WSNs中更適用與分布式算法。為進一步降低網(wǎng)絡(luò)的通信負載，提出了間歇型參數(shù)估計算法，并給出間歇型參數(shù)估計算法的運行步驟。最后，仿真表明，間歇型參數(shù)估計算法對一般的參數(shù)估計可在損失少許網(wǎng)絡(luò)估計性能的情況下大大降低網(wǎng)絡(luò)通信負載。