李雷雷，何剑辉，张勇刚

(1.广播电视规划院无线所，北京 100045;2.哈尔滨工程大学，哈尔滨 150001)

分布式无线网络中的仿射投影自适应算法

李雷雷1，何剑辉1，张勇刚2

(1.广播电视规划院无线所，北京 100045;2.哈尔滨工程大学，哈尔滨 150001)

本文对分布式无线网络中的仿射投影自适应算法(APA)进行研究。分布式网络的工作原理是利用网络的通信合作和节点输入数据的空间域-时域特性来提高估算结果的鲁棒性，各节点通过与其通信组节点的信息交流来实现空间域演进，同时通过本地迭代来实现时域演进。此外，我们根据Newton公式的最小代价函数推导出适用于不同拓扑结构分布式网络的放射投影自适应算法，并通过仿真验证了网络节点间的通信合作对于整体网络性能的改善。

分布式无线网络;仿射投影算法;自适应算法;递增式网络;扩散式网络;概率扩散式网络

1 背景

近几年来，我国的“三网融合”已成为技术发展和业务发展的必然趋势，并将给广播电视行业带来巨大变革，只有创新发展模式和研发新技术，才能更好地应对融合带来的机遇和挑战。而下一代广播网络(NGB)是“三网融合”大背景下的必然选择，也将是广播电视网络发展进程中革命性里程碑。其中，NGB无线通信系统结构的一种重要设想即为对各种新老交替的无线通信接入手段，以及通信网、计算机网与广播电视网这“三网”的逐步有机融合。因此，为应对融合竞争，广播电视行业应开展对无线通信网络的研究，并为未来广电业务发展和技术标准规划奠定坚实的技术基础。采用自适应滤波分布式联合算法的无线通信网络，因其具有良好的开放性、灵活性、和扩展性，最近几年逐渐成为无线通信应用领域的研究热点［1-3］，同时也将成为未来NGB无线通信网络架构的重要组成部分。

分布式网络通过链接计算机、笔记本、无线电话、传感器和激励器构成了未来数据通信和控制网络的主体框架，其构成的感应网络具有广泛的应用，包括精密农业、环境监控、智能空间、目标定位和医疗应用等。在这些应用中，由于节点分布在不同的空间位置中，同时考虑其空间域与时域可增强计算工作的鲁棒性并提高信号估计的概率［1］。分布式网络的节点分布在一个地理环境中，其根据节点采集的数据进行信息处理。例如，网路中的各节点采集受到噪声干扰的数据，该数据与所求参数相关。节点以某种方式与其他节点通信从而得到参数的估计值，该通信方式由网络的拓扑结构决定。其目的是在各节点可获得整个网络信息的条件下，得到尽可能准确的估计值［2］。与传统的集中式算法相比较，分布式算法降低了节点之间的通信流量和对性能强大的处理芯片的需求。

1.1 递增式和发散式网络

分布式算法的系统性能与其节点间的通信方式，即网络拓扑结构密切相关，目前典型的拓扑结构有三种:递增式、扩散式和概率性扩散式，如图1所示。

图1 网络拓扑结构

在递增式网络中，信息流以连续的方式在节点间逐步传递。该模式需要各节点在网络中组成一个闭合环，即汉密尔顿环(Hamiltonian cycle)，其所需的通信量和功耗最低［4、5］。另一方面，在扩散式网络中的各节点与其通信组内的所有节点都进行信息交换，其中各节点的通信组由网络拓扑结构所决定。因此，其通信量要远远大于递增式网络，但网络中各节点会从其通信组内的节点获得的更多信息量。此外，通过减少节点通信组内的数量，可以降低扩散式网络的通信量。而概率性扩散式网络中的各节点仅以一定概率与相邻的节点通信。在概率扩散式网络中，各节点在某些环境条件下，仅与其通信组内的节点以某一概率保持成功通信，即在某些时刻内节点间通信失败。

1.2 分布式算法

［6］-［8］提出的一致性算法属于分布式算法，其计算过程如下。首先，假设在一个指定的网络中去估计某个参数(例如:信号强度)。网络中的各个节点在一个时段内收集观测数据并对参数进行独立的估计。在这个时段内，各节点间仅进行有限的通信，换句话说，各节点更趋向于独立工作。完成这个初级步骤后，节点通过一致性迭代汇总估计结果，该结果近似收敛于所求参数的整体估计值，见图2。

我们可以通过另一个一致性算法例子来阐明自适应分布式算法的意义。假设一个节点网络，其中每个节点获取数据向量yk和数据矩阵Xk，其中yk是在干扰条件下对未知向量wo的测量值，并满足

各节点基于其本地数据{yk，Xk}来对ω0进行最小平方估计。因此，各节点需要先估计其本地交叉相关向量θk=ωo和其自相关矩阵Rk=Xk。向量ωo的本地估算值为=θk，该算法需要各节点采集充足的数据yk和Xk。当各节点独立估算出本地参量{θk，Rk}，并 采用一致性迭代可得到收敛的平均参量［9］

图2 一致性算法的运算步骤

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

在实际应用中，基于最小平方的一致性算法属于非迭代算法，即非自适应算法。例如，当网络中的某一个节点采集到一个额外yk的数据和一个额外的Xk向量时，一致性迭代需要进行重新计算而不是逐步迭代计算。此外，平均估算的方法限制了一致性算法追踪快速变化环境的能力，尤其是在一个拥有有限通信资源的网络中。

1.3 自适应网络

因此，［10］-［12］提出了分布式自适应算法，使得网络中的节点可进行自适应运算。为了更加明确的阐明自适应网络，让我们首先回顾一下一个传统的自适应滤波器，其根据激励信号和参考信号来实时调整其内部结构参数。在每一时刻，滤波器对比其计算结果和参考信号，并获得误差信号。无论该误差信号大或小，滤波器都根据其来校正结构参数。因而，我们注意到一个关键点，一个标准的自适应滤波器在实际时刻中根据其输入数据和该数据统计特性的变化来调整。我们可以将该能力扩展到网络中，使得其各节点滤波器的结构参数随着时间演进而调整并追踪输入数据统计特性的变化。因此，在一个自适应网络中，当信息被某个特定的节点采集时，该信息会对整个网络产生涟漪效应并根据网络的通信拓扑结构对相关节点的性能产生影响。我们也可通过对比图2中的示例来说明自适应网络。

再次假设一个网络中的节点需要估计某个参量，见图3。在自适应网络中，各节点采集本地数据并同时与其通信组内节点交换信息。在每个时刻，本地节点通过本地数据和交换信息的联合运算来提高本地的估算结果。通过重复同步采集和运算的步骤，网络中的节点能够根据实时的观测数据而连续的得到迭代更新的估算结果。

1.4 注释

我们使用粗体字母表示随机变量并用正常体字母表示非随机变量(确定常量)。我们也用大写字母表示矩阵并用小写字母表示向量。例如，d是一个随机变量而d是其实现值或测量值，R是一个协方差矩阵而ω是一个权向量。符号*代表标量的复共轭或矩阵的复共轭置换。

2 递增式APA算法

图3 自适应网络算法的运算步骤

假设一个包含N个节点的网络，见图4。各节点k可获得时域实现值{dk(i)，uk，i}，来自均值为零的空间域数据{dk，uk}，K=1，…，N，这里 dk是标量测量值而uk是一个1×M的输入回归横向量。我们用2个整体矩阵来表示这些测量值和和输入回归数据:

图4 N个节点的分布式网络，各节点获得空间-时间结构数据

该数据是通过网络中节点采集到的。我们的目的是通过以下公式估算出M×1的向量ω

这里价值函数方程J(ω)是均方差方程:

E是期望运算符号。方程(3)的理想解ωo满足正规方程组［13］:

其中，自相关和交叉相关矩阵为:

假设我们通过公式(5)来计算理想解ωo，则网络中的每个节点都需要获得整体统计信息{Ru，Rdu}。另一种方法是采用集中算法求解ωo，再将结果返还给网络中各节点。这两种方法都需要网络提供相当大的通信量和计算量，并且无法使得网络获得所需的自适应性来处理数据统计特性的变化。因此，自适应分布式算法的提出，不但使得各节点在有限的通信中联合计算并且整个网络具有自适应能力［10-12］。

2.1 递增式Newton算法

根据表达式(4)和(6)，价值函数方程J(ω)可分解为

其中，Jk(ω)由以下表达式给出

换句话说，J(ω)能够表示为N个独立的价值函数方程Jk(ω)的和。目前，关于利用递增式方法计算分布式网络的最优解，已经开展了广泛的研究［2］、［4］、［14］、［15］。本质上，当一个价值函数可被分解为独立的价值函数的和时，通过递增式方法可最小化价值函数并推导出分布式算法。我们可以通过以下的最小方差估计方法来解释该过程。

我们首先回顾采用传统的最陡下降法求解单点滤波器的最优解ωo:

此处，μ＞0是一个选择适当的迭代步长，ωi是在i时刻对于ωo的估计，▽J(ωi-1)是关于ω在估计ωi-1时J(ω)的梯度向量。众所周知，当输入数据具有高相关性时，采用Newton方法可得到更优化的解［13］。因此，我们采用Newton方法对价值函数方程(7)求解，我们可以得到

其中∈是极小值的标准化正参数，确保Ru，k矩阵的可逆性，其具体实现步骤如下。

首先定义一个汉密尔顿通信环，即在每个时刻通过网络拓扑仅访问各节点一次。因此在通信环中，每个节点仅与其相邻的结点连通，并用表明对于ωo在k节点时时刻的本地估计。假设k节点可获得，该参量为通信环中相邻k-1节点上对于ωo的估计值。在每个i时刻，我们把第一节点的初始条件设为=ωi-1(即对于ωo的当前整体估计ωi-1)，循环通过网络中各节点并在本地迭代，最终在第N节点(通信环中最后一个节点)上的本地估计值会等效于公式(12)中 ωi，即= ωi，公式(12)步骤的具体实现步骤如下:

因此，在Newton方法中，φik的空间域演进通过指针k实现。

虽然在迭代步骤(14)中，各节点通过其相邻节点获取信息(表示为)，但在各节点上还是需要整体信息ωi-1来计算▽Jk(ωi-1)和▽2J(ωi-1)。为了解决该问题并实现真正的分布式计算过程，我们可采用递增式方法。如果各节点在估计梯度▽Jk(■)和二次▽2Jk(■)时，采用代替 ωi-1，我们就可以得到算法(14)的递增式表达式，

算法(15)依靠本地信息，从而实现了真正的分布式计算。此外，该算法中各节点仅需与其相邻节点通信，因而节约了通信和能量资源［2］、［4］。

2.2 递增式APA算法

递增式算法(15)需要求解二次矩 Ru，k和 Rdu，k来计算本地梯度▽Jk()和二次梯度，▽2J()在具体应用中，我们可以采用采样平滑窗口，取代(15)中的 Ru，k和 Rdu，k来实现自适应递增式算法，

T是回归参数的数量，而uk，j和dk(j)代表在j时刻k节点处的本地输入向量和本地期望响应。把表达式(16)和(17)代入(15)，得到一个新的自适应递增式算法，即递增式 APA 算法［12］:

其中{Uk，i，dk，i}分别为本地 T×M 数据块矩阵和 T×1数据向量

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

当分布式网络具有更多通信资源时，我们可以根据网络的拓扑结构来设计更加复杂的点对点合作方式。这里我们把该方法叫做扩散式算法，见图5。网络中各节点的通信组定义为与其相通信交流的全部节点(包括其本身)。网络中，k节点通过与其通信组内节点通信交流而获得估计值组{φi-1l，l∈Nk(i-1)}，并将该向量值组与k节点的本地估计φi-1k合并，其中Nk(i-1)代表i-1时刻k节点的通信组。节点获得合成估计θi-1k，并将其输入给本地滤波器。基于APA迭代算法的表达式如下:

fk(■)代表本地合成函数。该合成函数可以是非线性，或者随时间变化，例如根据网络拓扑结构变化或非稳态环境变化。此时，我们把该类型算法称作概率扩散式APA算法。如果合成函数是线性并不随时间变化，则该类型算法为扩散式APA算法。我们

可以采用均值函数来实现扩散式APA算法，即

其中a(k，l)=1/deg(k)，deg(k)代表 k节点的等级，即与其通信的节点总数，包括其本身。这个算法充分利用了网络的连通性，并使得算法具有更好的鲁棒性。如果节点通信失败，自适应算法则依靠现有的网络拓扑结构工作。甚至在网络不连通的情况下，自适应算法也可以依靠各自独立的节点工作。此外，由于本地自适应滤波器迭代引入更多的信息，如果恰当设计的合成函数fk(■)，与非合作网络相比各节点能够获得更好的性能。而在概率扩散式APA算法中，各节点仅以某一概率与其通信组保持成功通信，即其通信成功率 ρk，l＜ 1，l∈Nk(i-1)。此时，概率扩散式APA算法的表达式为:

其中 ai(k，l)=1/deg(k，i)，deg(k，i)代表 k 节点在 i时刻的通信总量，包括其本身。

图5 扩散式APA算法

4 仿真实验

在本节内，我们通过模拟仿真来验证不同APA算法在分布式网络中的性能。分布式APA算法中的合成函数均采用均值函数。在第一个仿真实验中使用的是一个8个节点的网络，各节点的输入数据回归量满足一阶马克夫过程，其自相关系数为 αk，背景噪声功率，见图6。算法所求的6×1未知向量为，迭代步长 μk=0.2。此外，概率 ρ= ρk，l=0.1定义为概率分布式算法中节点间的通信概率。

图7展示了三种不同算法的整体性能，采样时间为［1，200］。其中，NLMS算法为T=1的APA算法，而非合作算法(noncooperative)中网络各节点相互之间不连通。图中MSD和EMSE分别为整个网络的整体均方偏差和额外均方误差，

第二个仿真实验采用一个较大的网络进行算法对比，总共21个节点并且迭代步长，μk=0.1其拓扑结构见图8。图9 a)为网络中各节点的数据统计特性;图9 b)为ρ=0.1的概率扩散式算法的网络通信量统计，其中网络最大容量(network maximum capacity)代表图8中网络节点间的通信全部成功，网络使用(network usage)代表ρ=0.1的概率扩散式算法的实际通信量，网络平均使用(network mean usage)代表ρ=0.1的概率扩散式算法的平均通信量。从图10中我们可以观察到，尽管概率扩散式算法中的ρ=0.01很小，与非合作算法相比，其性能也有较大提高。

5 总结

本论文中，我们描述了几种分布式合作算法。这几种算法使得分布式网络具有自适应能力，并可以用于解决各种应用领域内出现的分布式估计课题，例如环境监测、目标定位和传感网络等［1］、［16］。

应用于低能源环境时，递增式类型的算法能够很好地工作。当可用的资源增加并且网络的规模扩大时，汉密尔顿通信环的设置变得复杂了。为了避免网络拓扑的限制和更加充分的利用网络间的通信合作，我们引入扩散式算法。与非合作算法相比，该算法通过点与点之间的合成估计函数获得空间域的多样性，并提高了鲁棒性。此外，考虑到网络中节点间通信的可靠性，我们还引入了概率扩散式算法，并通过仿真证明其对整体网络性能的提高。

关于未来分布式无线网络的研究，我们可以考虑引入凸联合滤波算法来提高整体网络的工作性能。

［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，France，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-)，男，北京人，广播电视规划院无线所工程师.

(责任编辑

:宋金宝)