基于因子图和联合消息传递的无线网络协作定位算法

崔建华，王忠勇，张传宗，张园园

(1.国家数字交换系统工程技术研究中心，郑州 450002； 2.洛阳师范学院 物理与电子信息学院，河南 洛阳 471934；3.郑州大学 信息工程学院，郑州 450001)

基于因子图和联合消息传递的无线网络协作定位算法

崔建华1,2，王忠勇3*，张传宗3，张园园3

(1.国家数字交换系统工程技术研究中心，郑州 450002； 2.洛阳师范学院 物理与电子信息学院，河南 洛阳 471934；3.郑州大学 信息工程学院，郑州 450001)

(*通信作者电子邮箱zywangzzu@gmail.com)

针对现有基于消息传递算法的无线网络节点定位算法复杂度和通信开销过高的问题，提出一种基于测距的、低复杂度低协作开销的联合消息传递节点定位算法。所提算法考虑参考节点位置的不确定性以减少误差累积，并将消息约束为高斯函数以降低通信开销。首先，根据系统的概率模型和因子分解设计因子图；然后，根据状态转移模型和测距模型的特点，分别使用置信传播和平均场方法计算预测消息和协作消息；最后，在每次迭代过程中，通过非线性项的泰勒展开将非高斯置信消息近似为高斯函数。仿真分析表明，所提算法的定位性能与基于粒子的SPAWN算法接近，但节点间传输的信息由大量粒子变为均值向量和协方差矩阵，同时计算复杂度也大幅降低。

近似贝叶斯推理；因子图；置信传播；平均场方法；无线传感器网络；协作定位

0 引言

在基于无线传感器网络(Wireless Sensor Network, WSN)的应用中，传感器节点检测到的信息若没有准确的位置信息将变得毫无价值[1]。但考虑到成本和能量限制，一般只有少数参考节点的位置是已知的，其他大部分节点(称为待定位节点)通过邻近的参考节点的位置和与其之间的距离等观测信息确定自己的位置，参考节点较少时定位误差较大。近年来出现的协作定位技术中，待定位节点之间也进行通信，从而可有效提高定位精度，引起国内外学者的广泛关注，并提出了许多协作定位算法，如最小二乘(Least Square, LS)[2]、最大似然(Maximum Likelihood, ML)[3]、多维尺度MAP(MultiDimensional Scaling MAP, MDS-MAP)[4]以及卡尔曼滤波[5]和粒子滤波[6]等。

在近似贝叶斯推理的实现方法中，基于因子图的消息传递算法特别适用于大规模概率模型和分布式运算[7]，其中置信传播(Belief Propagation, BP)方法在树图下可得到精确的边缘概率密度分布函数，在有环图下也常常能获得较好的性能。近年有学者将BP应用于无线网络协作定位中，但非线性测距模型会导致消息计算非常复杂。一种解决方法是使用非参数化消息。Ihler等[8]将非参数化置信传播(Nonparametric Belief Propagation, NBP)用于静态无线传感器网络节点定位，Wymeersch等[9]进一步提出了适用于动态网络的SPAWN(Sum-Product Algorithm over a Wireless Network)算法。基于NBP的定位算法使用大量粒子表示消息，能灵活表示多种形式的消息，当粒子数足够多时可获得很高的定位精度，但计算复杂度和通信开销非常高[10]。Li等[11]提出一种基于序贯粒子的BP算法，利用吉布斯采样对消息进行粒子化，有效降低了计算复杂度，但通信负载依然较高。另一种解决方法是将测距模型线性化并采用参数化消息。北京理工大学武楠等利用一阶泰勒展开将测距模型线性化，提出了高斯BP节点定位算法[12-13]。相对于BP方法，平均场(Mean Field, MF)方法更适用于指数型消息，消息更新规则更加简单。Pedersen等[14]提出一种基于MF的静态网络节点定位算法，该算法采用高斯型消息，并使用最小化KL散度(Kullback-Leibler Divergence, KLD)将非高斯消息近似为高斯消息，但近似过程中出现了第一类合流超几何函数，致使计算复杂度非常高，且估计性能与基于BP的算法相比有所下降。

针对上述问题，本文将高性能的BP方法和低复杂度的MF方法结合起来，提出一种低复杂度低通信开销的协作定位算法，并考虑参考节点位置可能存在误差，以避免误差累积引起的定位精度下降问题。

1 系统模型与因子图

假设节点i∈M的状态转移模型为：

(1)

(2)

(3)

(4)

k时刻，所有节点位置变量和测量距离的集合分别记作Xk:i∈A∪M}和Dk:∀i∈M,}，并将0时刻到K时刻所有节点位置变量和测量距离的集合分别记作X0:K{X0,X1,…,XK}和D1:K{D1,D2,…,DK}。根据贝叶斯准则，从0时刻到K时刻节点位置变量的联合后验PDF可表示为：

p(X0:K|D1:K)∝p(X0:K)p(D1:K|X0:K)=

(5)

通常情况下因子图是无向图，但由于网络中节点间的连通关系会随时间变化，因此不计算从当前时刻到过去时刻的消息。此外，本算法考虑参考节点的位置可能有一定误差的情况，将其看作变量。在各时刻的迭代计算中，参考节点的位置也可以更新。

图1 式(5)的因子分解所对应的因子图Fig. 1 Factor graph corresponding to factorization in equation (5)

2 基于BP-MF的协作定位算法

2.1 基于BP方法的预测消息计算

(6)

(7)

(8)

2.2 基于MF方法的协作消息计算

(9)

将式(4)带入式(9)可得：

(10)

同理可得：

(11)

2.3 置信的计算和近似

(12)

(13)

(14)

(15)

2.4 算法执行流程

基于BP方法的预测过程是无环图，因此预测消息不进行迭代更新，基于MF方法的协作消息以及每个节点位置变量的置信需要进行迭代计算。MF方法总是保证良好的收敛性能[15]，本文算法在先验较好的情况下收敛较快，先验较差时收敛较慢。

本文算法的执行流程如下所示。

3) 迭代开始，各节点并行执行：

a) 广播自己的位置和测量距离并接收邻居点的信息；

4) 迭代终止。

5) 各节点根据最大后验估计准则确定估计位置。

6) 算法结束。

3 仿真分析

当σa,k=1 m时，即参考节点位置的误差在0～1 m时，考虑其不确定性与不考虑其不确定性两种情况下的CDF曲线如图2所示。可以看出，考虑参考节点位置可能存在的误差能够避免误差累积，从而获得更好的定位精度。

图2 是否考虑参考节点位置的不确定性对定位性能的影响Fig. 2 Impact of considering anchors’ uncertainty on positioning performance

不同σa,k下定位误差累积分布函数如图3所示。

图3 不同σa,k下的定位性能对比Fig. 3 Comparison of positioning performance with different σa,k

由图3可知，σa,k越小，即参考节点测量位置的误差越小，定位性能越好。此外，随着定位时刻k的增加，定位精度有所提高，这是因为随着k的增加待定位节点的先验信息(即预测信息)准确度提高。但当k大于一定值时(实验中k>10)，定位精度基本稳定，不会有大幅度提高。

图4 本文算法与SPAWN算法的定位性能对比Fig. 4 Performance comparison of the proposed algorithm and SPAWN

4 结语

本文针对参考节点位置存在一定模糊性的无线传感器网络，提出一种基于BP和MF的联合消息传递协作定位算法。仿真结果和分析表明，其估计性能与基于粒子的SPAWN接近，并避免了通信开销和计算复杂度过大的问题。在本文基础上，下一步将研究基于消息传递算法的目标跟踪算法。

References)

[1] 武晓琳, 单志龙, 曹树林，等. 基于接收信号强度指示测距的蒙特卡罗盒移动节点定位算法[J]. 计算机应用, 2015, 35(4): 916-920. (WU X L, SHAN Z L, CAO S L, et al. Monte Carlo boxed localization algorithm for mobile nodes based on received signal strength indication ranging [J]. Journal of Computer Applications, 2015, 35(4): 916-920.)

[2] LIN L, SO H C, CHAN F K W, et al. A new constrained weighted least squares algorithm for TDOA-based localization [J]. Signal Processing, 2013, 93(11):2872-2878.

[3] KANTAS N K, SINGH S S, DOUCET A. Distributed maximum likelihood for simultaneous self-localization and tracking in sensor networks[J]. IEEE Transactions on Signal Processing, 2012, 60(10):5038-5047.

[4] XU K, LIU Y, XU C, et al. A cluster-based and range-free multidimendional scaling-MAP localization scheme in WSN[C]// Proceedings of the 2013 International Conference on Computer Engineering and Network. Berlin: Springer-Verlag, 2014: 1253-1262.

[5] 肖如良, 李奕如, 江少华, 等. 基于卡尔曼滤波与中位加权的定位算法[J]. 计算机应用, 2014, 34(12): 3387-3390. (XIAO R L, LI Y R, JIANG S H, et al. Indoor positioning based on Kalman filter and weighted median [J]. Journal of Computer Applications, 2014, 34(12): 3387-3390.)

[6] 罗元, 庞冬雪, 张毅, 等. 基于自适应多提议分布粒子滤波的蒙特卡洛定位算法[J]. 计算机应用, 2016, 36(8): 2352-2356. (LUO Y, PANG D X, ZHANG Y, et al. Monte Carlo localization algorithm based on particle filter with adaptive multi-proposal distribution [J]. Journal of Computer Applications, 2016, 36(8): 272-276.)

[7] KSCHISCHANG F R, FREY B J, LOELIGER H A. Factor graphs and the sum-product algorithm[J]. IEEE Transactions on Information Theory, 2001, 47(2):498-519.

[8] IHLER A T, FISHER J W, MOSES R L, et al. Nonparametric belief propagation for self-localization of sensor networks [J]. IEEE Journal on Selected Areas in Communications, 2005, 23(4):809-819.

[9] WYMEERSCH H, LIEN J, WIN M Z. Cooperative localization in wireless networks [J]. Proceedings of the IEEE, 2009, 97(2):427-450.

[10] LIEN J, FERNER U J, SRICHAVENGSUP W, et al. A comparison of parametric and sample-based message representation in cooperative localization[EB/OL].[2016-05-20]. http://dspace.mit.edu/openaccess-disseminate/1721.1/76635.

[11] LI W, YANG Z, HU H. Sequential particle-based sum-product algorithm for distributed inference in wireless sensor networks [J]. IEEE Transactions on Vehicular Technology, 2013, 62(1):341-348.

[12] YUAN W J, WU N, WANG H, et al. Cooperative joint localization and clock synchronization based on Gaussian message passing in asynchronous wireless networks [J]. IEEE Transactions on Vehicular Technology, 2016, 65(9): 7258-7273.

[13] 李彬. 无线网络中的分布式定位算法研究 [D]. 北京: 北京理工大学, 2015:46-54. (LI B. Research on distributed localization algorithms in wireless networks [D]. Beijing: Beijing Institute of Technology, 2015:46-54.)

[14] PEDERSEN C, PEDERSEN T, FLEURY B H. A variational message passing algorithm for sensor self-localization in wireless networks[C]// Proceedings of the 2011 IEEE International Symposium on Information Theory. Piscataway, NJ: IEEE, 2011: 2158-2162.

[15] RIEGLER, E, KIRKELUND, G E, MANCHON, C N, et al. Merging belief propagation and the mean field approximation: a free energy approach [J]. IEEE Transactions on Information Theory, 2013, 59(1):588-602.

This work is partially supported by the National Natural Science Foundation of China (61571402，61401401).

CUI Jianhua, born in 1981, Ph. D. candidate, lecturer. Her research interests include signal and information processing, wireless network positioning and tracking.

WANG Zhongyong, born in 1965, Ph. D., professor. His research interests include communication signal processing, embedded system design.

ZHANG Chuanzong, born in 1982, Ph. D. candidate. His research interests include signal detection and estimation, iterative receiver design.

ZHANG Yuanyuan, born in 1990, Ph. D. candidate. Her research interests include communication signal processing, interference suppression and elimination.

Localization algorithm based on factor graph and hybrid message passing for wireless networks

CUI Jianhua1,2, WANG Zhongyong3*, ZHANG Chuanzong3, ZHANG Yuanyuan3

(1.NationalDigitalSwitchingSystemEngineering&TechnologicalResearchCenter,ZhengzhouHenan450002,China;2.SchoolofPhysicsandElectronicInformation,LuoyangNormalUniversity,LuoyangHenan471934,China;3.SchoolofInformationEngineering,ZhengzhouUniversity,ZhengzhouHenan450001,China)

Concerning the high computational complexity and communication overhead of wireless network node localization algorithm based on message passing algorithm, a ranging-based hybrid message passing node localization method with low complexity and cooperative overhead was proposed. The uncertainty of the reference nodes was taken into account to avoid error accumulation, and the messages on factor graph were restricted to be Gaussian distribution to reduce the communication overhead. Firstly, the factor graph was designed based on the system model and the Bayesian factorization. Secondly, belief propagation and mean filed methods were employed according to the linear state transition model and the nonlinear ranging model to calculate the prediction messages and the cooperation messages, respectively. Finally, in each iteration, the non-Gaussian beliefs were approximated into Gaussian distribution by Taylor expansions of the nonlinear terms. The simulation results show that the positioning accuracy of the proposed algorithm is compareable to that of Sum-Product Algorithm over a Wireless Network (SPAWN), but the information transmitted between nodes decreases from a large number of particles to mean vector and covariance matrix, and the comupational complexity is also dramatically reduced.

approximate Bayesian inference; factor graph; belief propagation; mean filed method; Wireless Sensor Network (WSN); cooperative localization

2016-10-28;

2017-01-02。 基金项目:国家自然科学基金资助项目(61571402，61401401)。

崔建华(1981—)，女，河南新乡人，讲师，博士研究生，主要研究方向：信号与信息处理、无线网络定位与跟踪； 王忠勇(1965—)，男，江西吉安人，教授，博士，主要研究方向：通信信号处理、嵌入式系统设计； 张传宗(1982—)，男，河南南阳人，博士研究生，主要研究方向：信号检测与估计、迭代接收机设计； 张园园(1990—)，女，河南平顶山人，博士研究生，主要研究方向：通信信号处理、干扰抑制与消除。

1001-9081(2017)05-1306-05

10.11772/j.issn.1001-9081.2017.05.1306

TN911.23

A