分布式無線網(wǎng)絡中的仿射投影自適應算法

李雷雷，何劍輝，張勇剛

(1.廣播電視規(guī)劃院無線所，北京 100045;2.哈爾濱工程大學，哈爾濱 150001)

分布式無線網(wǎng)絡中的仿射投影自適應算法

李雷雷1，何劍輝1，張勇剛2

(1.廣播電視規(guī)劃院無線所，北京 100045;2.哈爾濱工程大學，哈爾濱 150001)

本文對分布式無線網(wǎng)絡中的仿射投影自適應算法(APA)進行研究。分布式網(wǎng)絡的工作原理是利用網(wǎng)絡的通信合作和節(jié)點輸入數(shù)據(jù)的空間域-時域特性來提高估算結(jié)果的魯棒性，各節(jié)點通過與其通信組節(jié)點的信息交流來實現(xiàn)空間域演進，同時通過本地迭代來實現(xiàn)時域演進。此外，我們根據(jù)Newton公式的最小代價函數(shù)推導出適用于不同拓撲結(jié)構分布式網(wǎng)絡的放射投影自適應算法，并通過仿真驗證了網(wǎng)絡節(jié)點間的通信合作對于整體網(wǎng)絡性能的改善。

分布式無線網(wǎng)絡;仿射投影算法;自適應算法;遞增式網(wǎng)絡;擴散式網(wǎng)絡;概率擴散式網(wǎng)絡

1 背景

近幾年來，我國的“三網(wǎng)融合”已成為技術發(fā)展和業(yè)務發(fā)展的必然趨勢，并將給廣播電視行業(yè)帶來巨大變革，只有創(chuàng)新發(fā)展模式和研發(fā)新技術，才能更好地應對融合帶來的機遇和挑戰(zhàn)。而下一代廣播網(wǎng)絡(NGB)是“三網(wǎng)融合”大背景下的必然選擇，也將是廣播電視網(wǎng)絡發(fā)展進程中革命性里程碑。其中，NGB無線通信系統(tǒng)結(jié)構的一種重要設想即為對各種新老交替的無線通信接入手段，以及通信網(wǎng)、計算機網(wǎng)與廣播電視網(wǎng)這“三網(wǎng)”的逐步有機融合。因此，為應對融合競爭，廣播電視行業(yè)應開展對無線通信網(wǎng)絡的研究，并為未來廣電業(yè)務發(fā)展和技術標準規(guī)劃奠定堅實的技術基礎。采用自適應濾波分布式聯(lián)合算法的無線通信網(wǎng)絡，因其具有良好的開放性、靈活性、和擴展性，最近幾年逐漸成為無線通信應用領域的研究熱點［1-3］，同時也將成為未來NGB無線通信網(wǎng)絡架構的重要組成部分。

分布式網(wǎng)絡通過鏈接計算機、筆記本、無線電話、傳感器和激勵器構成了未來數(shù)據(jù)通信和控制網(wǎng)絡的主體框架，其構成的感應網(wǎng)絡具有廣泛的應用，包括精密農(nóng)業(yè)、環(huán)境監(jiān)控、智能空間、目標定位和醫(yī)療應用等。在這些應用中，由于節(jié)點分布在不同的空間位置中，同時考慮其空間域與時域可增強計算工作的魯棒性并提高信號估計的概率［1］。分布式網(wǎng)絡的節(jié)點分布在一個地理環(huán)境中，其根據(jù)節(jié)點采集的數(shù)據(jù)進行信息處理。例如，網(wǎng)路中的各節(jié)點采集受到噪聲干擾的數(shù)據(jù)，該數(shù)據(jù)與所求參數(shù)相關。節(jié)點以某種方式與其他節(jié)點通信從而得到參數(shù)的估計值，該通信方式由網(wǎng)絡的拓撲結(jié)構決定。其目的是在各節(jié)點可獲得整個網(wǎng)絡信息的條件下，得到盡可能準確的估計值［2］。與傳統(tǒng)的集中式算法相比較，分布式算法降低了節(jié)點之間的通信流量和對性能強大的處理芯片的需求。

1.1 遞增式和發(fā)散式網(wǎng)絡

分布式算法的系統(tǒng)性能與其節(jié)點間的通信方式，即網(wǎng)絡拓撲結(jié)構密切相關，目前典型的拓撲結(jié)構有三種:遞增式、擴散式和概率性擴散式，如圖1所示。

圖1 網(wǎng)絡拓撲結(jié)構

在遞增式網(wǎng)絡中，信息流以連續(xù)的方式在節(jié)點間逐步傳遞。該模式需要各節(jié)點在網(wǎng)絡中組成一個閉合環(huán)，即漢密爾頓環(huán)(Hamiltonian cycle)，其所需的通信量和功耗最低［4、5］。另一方面，在擴散式網(wǎng)絡中的各節(jié)點與其通信組內(nèi)的所有節(jié)點都進行信息交換，其中各節(jié)點的通信組由網(wǎng)絡拓撲結(jié)構所決定。因此，其通信量要遠遠大于遞增式網(wǎng)絡，但網(wǎng)絡中各節(jié)點會從其通信組內(nèi)的節(jié)點獲得的更多信息量。此外，通過減少節(jié)點通信組內(nèi)的數(shù)量，可以降低擴散式網(wǎng)絡的通信量。而概率性擴散式網(wǎng)絡中的各節(jié)點僅以一定概率與相鄰的節(jié)點通信。在概率擴散式網(wǎng)絡中，各節(jié)點在某些環(huán)境條件下，僅與其通信組內(nèi)的節(jié)點以某一概率保持成功通信，即在某些時刻內(nèi)節(jié)點間通信失敗。

1.2 分布式算法

［6］-［8］提出的一致性算法屬于分布式算法，其計算過程如下。首先，假設在一個指定的網(wǎng)絡中去估計某個參數(shù)(例如:信號強度)。網(wǎng)絡中的各個節(jié)點在一個時段內(nèi)收集觀測數(shù)據(jù)并對參數(shù)進行獨立的估計。在這個時段內(nèi)，各節(jié)點間僅進行有限的通信，換句話說，各節(jié)點更趨向于獨立工作。完成這個初級步驟后，節(jié)點通過一致性迭代匯總估計結(jié)果，該結(jié)果近似收斂于所求參數(shù)的整體估計值，見圖2。

我們可以通過另一個一致性算法例子來闡明自適應分布式算法的意義。假設一個節(jié)點網(wǎng)絡，其中每個節(jié)點獲取數(shù)據(jù)向量yk和數(shù)據(jù)矩陣Xk，其中yk是在干擾條件下對未知向量wo的測量值，并滿足

各節(jié)點基于其本地數(shù)據(jù){yk，Xk}來對ω0進行最小平方估計。因此，各節(jié)點需要先估計其本地交叉相關向量θk=ωo和其自相關矩陣Rk=Xk。向量ωo的本地估算值為=θk，該算法需要各節(jié)點采集充足的數(shù)據(jù)yk和Xk。當各節(jié)點獨立估算出本地參量{θk，Rk}，并 采用一致性迭代可得到收斂的平均參量［9］

圖2 一致性算法的運算步驟

由此得到向量ωo的整體估算值。

在實際應用中，基于最小平方的一致性算法屬于非迭代算法，即非自適應算法。例如，當網(wǎng)絡中的某一個節(jié)點采集到一個額外yk的數(shù)據(jù)和一個額外的Xk向量時，一致性迭代需要進行重新計算而不是逐步迭代計算。此外，平均估算的方法限制了一致性算法追蹤快速變化環(huán)境的能力，尤其是在一個擁有有限通信資源的網(wǎng)絡中。

1.3 自適應網(wǎng)絡

因此，［10］-［12］提出了分布式自適應算法，使得網(wǎng)絡中的節(jié)點可進行自適應運算。為了更加明確的闡明自適應網(wǎng)絡，讓我們首先回顧一下一個傳統(tǒng)的自適應濾波器，其根據(jù)激勵信號和參考信號來實時調(diào)整其內(nèi)部結(jié)構參數(shù)。在每一時刻，濾波器對比其計算結(jié)果和參考信號，并獲得誤差信號。無論該誤差信號大或小，濾波器都根據(jù)其來校正結(jié)構參數(shù)。因而，我們注意到一個關鍵點，一個標準的自適應濾波器在實際時刻中根據(jù)其輸入數(shù)據(jù)和該數(shù)據(jù)統(tǒng)計特性的變化來調(diào)整。我們可以將該能力擴展到網(wǎng)絡中，使得其各節(jié)點濾波器的結(jié)構參數(shù)隨著時間演進而調(diào)整并追蹤輸入數(shù)據(jù)統(tǒng)計特性的變化。因此，在一個自適應網(wǎng)絡中，當信息被某個特定的節(jié)點采集時，該信息會對整個網(wǎng)絡產(chǎn)生漣漪效應并根據(jù)網(wǎng)絡的通信拓撲結(jié)構對相關節(jié)點的性能產(chǎn)生影響。我們也可通過對比圖2中的示例來說明自適應網(wǎng)絡。

再次假設一個網(wǎng)絡中的節(jié)點需要估計某個參量，見圖3。在自適應網(wǎng)絡中，各節(jié)點采集本地數(shù)據(jù)并同時與其通信組內(nèi)節(jié)點交換信息。在每個時刻，本地節(jié)點通過本地數(shù)據(jù)和交換信息的聯(lián)合運算來提高本地的估算結(jié)果。通過重復同步采集和運算的步驟，網(wǎng)絡中的節(jié)點能夠根據(jù)實時的觀測數(shù)據(jù)而連續(xù)的得到迭代更新的估算結(jié)果。

1.4 注釋

我們使用粗體字母表示隨機變量并用正常體字母表示非隨機變量(確定常量)。我們也用大寫字母表示矩陣并用小寫字母表示向量。例如，d是一個隨機變量而d是其實現(xiàn)值或測量值，R是一個協(xié)方差矩陣而ω是一個權向量。符號*代表標量的復共軛或矩陣的復共軛置換。

2 遞增式APA算法

圖3 自適應網(wǎng)絡算法的運算步驟

假設一個包含N個節(jié)點的網(wǎng)絡，見圖4。各節(jié)點k可獲得時域?qū)崿F(xiàn)值{dk(i)，uk，i}，來自均值為零的空間域數(shù)據(jù){dk，uk}，K=1，…，N，這里 dk是標量測量值而uk是一個1×M的輸入回歸橫向量。我們用2個整體矩陣來表示這些測量值和和輸入回歸數(shù)據(jù):

圖4 N個節(jié)點的分布式網(wǎng)絡，各節(jié)點獲得空間-時間結(jié)構數(shù)據(jù)

該數(shù)據(jù)是通過網(wǎng)絡中節(jié)點采集到的。我們的目的是通過以下公式估算出M×1的向量ω

這里價值函數(shù)方程J(ω)是均方差方程:

E是期望運算符號。方程(3)的理想解ωo滿足正規(guī)方程組［13］:

其中，自相關和交叉相關矩陣為:

假設我們通過公式(5)來計算理想解ωo，則網(wǎng)絡中的每個節(jié)點都需要獲得整體統(tǒng)計信息{Ru，Rdu}。另一種方法是采用集中算法求解ωo，再將結(jié)果返還給網(wǎng)絡中各節(jié)點。這兩種方法都需要網(wǎng)絡提供相當大的通信量和計算量，并且無法使得網(wǎng)絡獲得所需的自適應性來處理數(shù)據(jù)統(tǒng)計特性的變化。因此，自適應分布式算法的提出，不但使得各節(jié)點在有限的通信中聯(lián)合計算并且整個網(wǎng)絡具有自適應能力［10-12］。

2.1 遞增式Newton算法

根據(jù)表達式(4)和(6)，價值函數(shù)方程J(ω)可分解為

其中，Jk(ω)由以下表達式給出

換句話說，J(ω)能夠表示為N個獨立的價值函數(shù)方程Jk(ω)的和。目前，關于利用遞增式方法計算分布式網(wǎng)絡的最優(yōu)解，已經(jīng)開展了廣泛的研究［2］、［4］、［14］、［15］。本質(zhì)上，當一個價值函數(shù)可被分解為獨立的價值函數(shù)的和時，通過遞增式方法可最小化價值函數(shù)并推導出分布式算法。我們可以通過以下的最小方差估計方法來解釋該過程。

我們首先回顧采用傳統(tǒng)的最陡下降法求解單點濾波器的最優(yōu)解ωo:

此處，μ＞0是一個選擇適當?shù)牡介L，ωi是在i時刻對于ωo的估計，▽J(ωi-1)是關于ω在估計ωi-1時J(ω)的梯度向量。眾所周知，當輸入數(shù)據(jù)具有高相關性時，采用Newton方法可得到更優(yōu)化的解［13］。因此，我們采用Newton方法對價值函數(shù)方程(7)求解，我們可以得到

其中∈是極小值的標準化正參數(shù)，確保Ru，k矩陣的可逆性，其具體實現(xiàn)步驟如下。

首先定義一個漢密爾頓通信環(huán)，即在每個時刻通過網(wǎng)絡拓撲僅訪問各節(jié)點一次。因此在通信環(huán)中，每個節(jié)點僅與其相鄰的結(jié)點連通，并用表明對于ωo在k節(jié)點時時刻的本地估計。假設k節(jié)點可獲得，該參量為通信環(huán)中相鄰k-1節(jié)點上對于ωo的估計值。在每個i時刻，我們把第一節(jié)點的初始條件設為=ωi-1(即對于ωo的當前整體估計ωi-1)，循環(huán)通過網(wǎng)絡中各節(jié)點并在本地迭代，最終在第N節(jié)點(通信環(huán)中最后一個節(jié)點)上的本地估計值會等效于公式(12)中 ωi，即= ωi，公式(12)步驟的具體實現(xiàn)步驟如下:

因此，在Newton方法中，φik的空間域演進通過指針k實現(xiàn)。

雖然在迭代步驟(14)中，各節(jié)點通過其相鄰節(jié)點獲取信息(表示為)，但在各節(jié)點上還是需要整體信息ωi-1來計算▽Jk(ωi-1)和▽2J(ωi-1)。為了解決該問題并實現(xiàn)真正的分布式計算過程，我們可采用遞增式方法。如果各節(jié)點在估計梯度▽Jk(■)和二次▽2Jk(■)時，采用代替 ωi-1，我們就可以得到算法(14)的遞增式表達式，

算法(15)依靠本地信息，從而實現(xiàn)了真正的分布式計算。此外，該算法中各節(jié)點僅需與其相鄰節(jié)點通信，因而節(jié)約了通信和能量資源［2］、［4］。

2.2 遞增式APA算法

遞增式算法(15)需要求解二次矩 Ru，k和 Rdu，k來計算本地梯度▽Jk()和二次梯度，▽2J()在具體應用中，我們可以采用采樣平滑窗口，取代(15)中的 Ru，k和 Rdu，k來實現(xiàn)自適應遞增式算法，

T是回歸參數(shù)的數(shù)量，而uk，j和dk(j)代表在j時刻k節(jié)點處的本地輸入向量和本地期望響應。把表達式(16)和(17)代入(15)，得到一個新的自適應遞增式算法，即遞增式 APA 算法［12］:

其中{Uk，i，dk，i}分別為本地 T×M 數(shù)據(jù)塊矩陣和 T×1數(shù)據(jù)向量

3 擴散式APA算法和概率擴散式APA算法

當分布式網(wǎng)絡具有更多通信資源時，我們可以根據(jù)網(wǎng)絡的拓撲結(jié)構來設計更加復雜的點對點合作方式。這里我們把該方法叫做擴散式算法，見圖5。網(wǎng)絡中各節(jié)點的通信組定義為與其相通信交流的全部節(jié)點(包括其本身)。網(wǎng)絡中，k節(jié)點通過與其通信組內(nèi)節(jié)點通信交流而獲得估計值組{φi-1l，l∈Nk(i-1)}，并將該向量值組與k節(jié)點的本地估計φi-1k合并，其中Nk(i-1)代表i-1時刻k節(jié)點的通信組。節(jié)點獲得合成估計θi-1k，并將其輸入給本地濾波器。基于APA迭代算法的表達式如下:

fk(■)代表本地合成函數(shù)。該合成函數(shù)可以是非線性，或者隨時間變化，例如根據(jù)網(wǎng)絡拓撲結(jié)構變化或非穩(wěn)態(tài)環(huán)境變化。此時，我們把該類型算法稱作概率擴散式APA算法。如果合成函數(shù)是線性并不隨時間變化，則該類型算法為擴散式APA算法。我們

可以采用均值函數(shù)來實現(xiàn)擴散式APA算法，即

其中a(k，l)=1/deg(k)，deg(k)代表 k節(jié)點的等級，即與其通信的節(jié)點總數(shù)，包括其本身。這個算法充分利用了網(wǎng)絡的連通性，并使得算法具有更好的魯棒性。如果節(jié)點通信失敗，自適應算法則依靠現(xiàn)有的網(wǎng)絡拓撲結(jié)構工作。甚至在網(wǎng)絡不連通的情況下，自適應算法也可以依靠各自獨立的節(jié)點工作。此外，由于本地自適應濾波器迭代引入更多的信息，如果恰當設計的合成函數(shù)fk(■)，與非合作網(wǎng)絡相比各節(jié)點能夠獲得更好的性能。而在概率擴散式APA算法中，各節(jié)點僅以某一概率與其通信組保持成功通信，即其通信成功率 ρk，l＜ 1，l∈Nk(i-1)。此時，概率擴散式APA算法的表達式為:

其中 ai(k，l)=1/deg(k，i)，deg(k，i)代表 k 節(jié)點在 i時刻的通信總量，包括其本身。

圖5 擴散式APA算法

4 仿真實驗

在本節(jié)內(nèi)，我們通過模擬仿真來驗證不同APA算法在分布式網(wǎng)絡中的性能。分布式APA算法中的合成函數(shù)均采用均值函數(shù)。在第一個仿真實驗中使用的是一個8個節(jié)點的網(wǎng)絡，各節(jié)點的輸入數(shù)據(jù)回歸量滿足一階馬克夫過程，其自相關系數(shù)為 αk，背景噪聲功率，見圖6。算法所求的6×1未知向量為，迭代步長 μk=0.2。此外，概率 ρ= ρk，l=0.1定義為概率分布式算法中節(jié)點間的通信概率。

圖7展示了三種不同算法的整體性能，采樣時間為［1，200］。其中，NLMS算法為T=1的APA算法，而非合作算法(noncooperative)中網(wǎng)絡各節(jié)點相互之間不連通。圖中MSD和EMSE分別為整個網(wǎng)絡的整體均方偏差和額外均方誤差，

第二個仿真實驗采用一個較大的網(wǎng)絡進行算法對比，總共21個節(jié)點并且迭代步長，μk=0.1其拓撲結(jié)構見圖8。圖9 a)為網(wǎng)絡中各節(jié)點的數(shù)據(jù)統(tǒng)計特性;圖9 b)為ρ=0.1的概率擴散式算法的網(wǎng)絡通信量統(tǒng)計，其中網(wǎng)絡最大容量(network maximum capacity)代表圖8中網(wǎng)絡節(jié)點間的通信全部成功，網(wǎng)絡使用(network usage)代表ρ=0.1的概率擴散式算法的實際通信量，網(wǎng)絡平均使用(network mean usage)代表ρ=0.1的概率擴散式算法的平均通信量。從圖10中我們可以觀察到，盡管概率擴散式算法中的ρ=0.01很小，與非合作算法相比，其性能也有較大提高。

5 總結(jié)

本論文中，我們描述了幾種分布式合作算法。這幾種算法使得分布式網(wǎng)絡具有自適應能力，并可以用于解決各種應用領域內(nèi)出現(xiàn)的分布式估計課題，例如環(huán)境監(jiān)測、目標定位和傳感網(wǎng)絡等［1］、［16］。

應用于低能源環(huán)境時，遞增式類型的算法能夠很好地工作。當可用的資源增加并且網(wǎng)絡的規(guī)模擴大時，漢密爾頓通信環(huán)的設置變得復雜了。為了避免網(wǎng)絡拓撲的限制和更加充分的利用網(wǎng)絡間的通信合作，我們引入擴散式算法。與非合作算法相比，該算法通過點與點之間的合成估計函數(shù)獲得空間域的多樣性，并提高了魯棒性。此外，考慮到網(wǎng)絡中節(jié)點間通信的可靠性，我們還引入了概率擴散式算法，并通過仿真證明其對整體網(wǎng)絡性能的提高。

關于未來分布式無線網(wǎng)絡的研究，我們可以考慮引入凸聯(lián)合濾波算法來提高整體網(wǎng)絡的工作性能。

［1］D Estrin，L Girod，G Pottie，M Srivastava.Instrumenting the world with wireless sensor networks［J］.ICASSP，Salt Lake City，UT，May 2001:2033-2036.

［2］M GRabbat，R D Nowak.Quantized incremental algorithms for distributed optimization［J］.IEEE Journal on Selected Areas in Communications，April 2005，23(4):798-808.

［3］D Li，K D Wong，Y H Hu，A M Sayeed.Detection，classification，and tracking of targets［J］.IEEE signal processing Magazine，March 2002，19(2):17-29.

［4］D Bertsekas.A new class of incremental gradient methods for least square problems［J］.newblock SIAM，Nov，1997，7(4):913-926.

［5］A Nedic，D Bertsekas.Incremental subgradient methods for nondifferentiable optimization［J］.SIAM，2001，12(1):109-138.

［6］J Tsitsiklis，M Athans.Convergence and asymptotic agreement in distributed decision problems［J］.IEEE Transactions on Automatic Control，Jan，1984，29(1):42-50.

［7］R Olfati-saber，R M Murray.Consensus problems in networks of agents with switching topology and time-delays［J］.IEEE Transactions on Automatic Control，Sept，2004，49(9):1520-1533.

［8］L Xiao，S Boyd.Fast linear iterations for distributed averaging［J］.Systems and Control Letters，Sep，2004，53(1):67-78.

［9］L Xiao，S Boyd，S Lall.A scheme for robust distributed sensor fusion based on average consensus［J］.Fourth Internation Symposium on Information Processing in Sensor Network，Los Angeles，CA，2005:63-70.

［10］C Lopes，A H Sayed.Distributed adaptive incremental strategies:formulation and performance analysis［J］.ICASSP，Toulouse，F(xiàn)rance，May，2006.

［11］A H Sayed，C Lopes.Distributed recursive least-squares strategies over adaptive networks［J］.40th Asilomar Conference on Signals，Systems and Computers，Pacific Grove，CA，October，2006.

［12］L Li，J A Chambers.A new incremental affine projection based adaptive algorithm for distributed networks［J］.Fast Communications in Signal Processing，October，2008，88(10):2599-2603.

［13］A H Sayed.Fundamentals of Adaptive Filters［J］.Wiley.NJ，2003.

［14］J Tsitsiklis，D P Bertsekas，M Athans.Distributed asynchronous deterministic and stochastic gradient optimization algorithms［J］.IEEE Transactions on Automatic Control， Sept，1986，31(9):650-655.

［15］B T Poljak，Y Z Tsypkin.Pseudogradient adaptation and training algorithms［J］.Automatic and Remote Control，1973(12):83-94.

［16］R Candido，M T M Silva，V H Nascimento.Transient and steady-state analysis of the affine combination of two adaptive filters［J］.IEEE Trans Signal Process，2010，58(8):4064-4078.

Affine Projection Algorithms over Distributed Wireless Networks

LI Lei-lei1，HE Jian-hui1，ZHANG Yong-gang2

(1.Wireless Department，Academy of Broadcasting Planning，Beijing 100045;2.Harbin Engineering University，Harbin 150001)

In this paper，we study the affine projection algorithms(APA)over distributed wireless networks.Distributed networks exploit the cooperation of nodes and space-time structure of input data to improve the robustness of estimation results.Nodes evolve in the space domain by exchanging the information in neighborhoods and in the time domain by local update.Based on Least-Mean squared cost function of Newton method，we achieve the adaptive APA algorithms，which can be applied in distributed networks with different topologies.Simulations confirm the improved performance of the whole networks by nodes cooperation.

distributed wireless networks;affine projection algorithm;adaptive filters;incremental network;diffusion network;probabilistic diffusion network

TN925

1673-4793(2012)02-0034-10

2012-03-18

國家自然科學基金61001169、61001154

李雷雷(1980-)，男，北京人，廣播電視規(guī)劃院無線所工程師.

(責任編輯

:宋金寶)