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

doi:10.11772/j.issn.1001-9081.2017.05.1306

计算机应用 ›› 2017, Vol. 37 ›› Issue (5): 1306-1310.DOI: 10.11772/j.issn.1001-9081.2017.05.1306

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

崔建华^1,2, 王忠勇³, 张传宗³, 张园园³

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

收稿日期:2016-10-28 修回日期:2017-01-02 出版日期:2017-05-10 发布日期:2017-05-16
通讯作者: 王忠勇
作者简介:崔建华(1981-),女,河南新乡人,讲师,博士研究生,主要研究方向:信号与信息处理、无线网络定位与跟踪;王忠勇(1965-),男,江西吉安人,教授,博士,主要研究方向:通信信号处理、嵌入式系统设计;张传宗(1982-),男,河南南阳人,博士研究生,主要研究方向:信号检测与估计、迭代接收机设计;张园园(1990-),女,河南平顶山人,博士研究生,主要研究方向:通信信号处理、干扰抑制与消除。
基金资助:
国家自然科学基金资助项目（61571402，61401401）。

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

CUI Jianhua^1,2, WANG Zhongyong³, ZHANG Chuanzong³, ZHANG Yuanyuan³

1. National Digital Switching System Engineering & Technological Research Center, Zhengzhou Henan 450002, China;
2. School of Physics and Electronic Information, Luoyang Normal University, Luoyang Henan 471934, China;
3. School of Information Engineering, Zhengzhou University, Zhengzhou Henan 450001, China

Received:2016-10-28 Revised:2017-01-02 Online:2017-05-10 Published:2017-05-16
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61571402,61401401).

摘要/Abstract

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

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

Abstract: 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.

Key words: approximate Bayesian inference, factor graph, belief propagation, mean filed method, Wireless Sensor Network (WSN), cooperative localization

中图分类号:

TN911.23

崔建华, 王忠勇, 张传宗, 张园园. 基于因子图和联合消息传递的无线网络协作定位算法[J]. 计算机应用, 2017, 37(5): 1306-1310.

CUI Jianhua, WANG Zhongyong, ZHANG Chuanzong, ZHANG Yuanyuan. Localization algorithm based on factor graph and hybrid message passing for wireless networks[J]. Journal of Computer Applications, 2017, 37(5): 1306-1310.

参考文献

[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.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	孙环, 陈宏滨. 基于萤火虫算法的无线传感器网络节点重部署策略[J]. 计算机应用, 2021, 41(2): 492-497.
[2]	韩雨涝, 房鼎益. 基于链路交点相对位置信息的轻量级覆盖空洞检测算法[J]. 计算机应用, 2020, 40(9): 2698-2705.
[3]	胡润彦, 李翠然. 基于模糊控制的自供能无线传感器网络分簇算法[J]. 计算机应用, 2020, 40(9): 2691-2697.
[4]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.
[5]	李添正, 王春桃. 基于马尔可夫随机场的加密二值图像有损压缩算法[J]. 计算机应用, 2020, 40(5): 1354-1363.
[6]	卢光跃, 周亮, 吕少卿, 施聪, 苏可可. 基于图信号处理的无线传感器网络异常节点检测算法[J]. 计算机应用, 2020, 40(3): 783-787.
[7]	任秀丽, 陈洋. 无线传感网中数据传输延时优化的路由协议[J]. 计算机应用, 2020, 40(1): 196-201.
[8]	吴三柱, 李鹏, 吴三斌. 移动无线传感器网络中抑制病毒传播模型[J]. 计算机应用, 2020, 40(1): 129-135.
[9]	董发志, 丁洪伟, 杨志军, 熊成彪, 张颖婕. 基于遗传算法和模糊C均值聚类的WSN分簇路由算法[J]. 计算机应用, 2019, 39(8): 2359-2365.
[10]	吴婉婷, 朱燕, 黄定江. 在线投资组合选择的半指数梯度策略及实证分析[J]. 计算机应用, 2019, 39(8): 2462-2467.
[11]	何庆, 徐钦帅, 魏康园. 基于改进正弦余弦算法的无线传感器节点部署优化[J]. 计算机应用, 2019, 39(7): 2035-2043.
[12]	钱开国, 卜春芬, 王玉见, 申时凯. 基于可靠信标和节点度估计距离的无线传感器网络定位算法[J]. 计算机应用, 2019, 39(3): 817-823.
[13]	任晓奎, 李锋, 程琳. 基于动态损耗因子和权重的改进质心定位算法[J]. 计算机应用, 2019, 39(3): 824-828.
[14]	汪汉新, 洪思琴. 基于环分块的能耗均衡分簇路由算法[J]. 计算机应用, 2019, 39(1): 251-255.
[15]	党小超, 邵晨光, 郝占军. 半径可调的无线传感器网络三维覆盖算法[J]. 计算机应用, 2018, 38(9): 2581-2586.