Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (5): 1306-1310.DOI: 10.11772/j.issn.1001-9081.2017.05.1306

Previous Articles     Next Articles

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

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

  1. 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).


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

  1. 1. 国家数字交换系统工程技术研究中心, 郑州 450002;
    2. 洛阳师范学院 物理与电子信息学院, 河南 洛阳 471934;
    3. 郑州大学 信息工程学院, 郑州 450001
  • 通讯作者: 王忠勇
  • 作者简介:崔建华(1981-),女,河南新乡人,讲师,博士研究生,主要研究方向:信号与信息处理、无线网络定位与跟踪;王忠勇(1965-),男,江西吉安人,教授,博士,主要研究方向:通信信号处理、嵌入式系统设计;张传宗(1982-),男,河南南阳人,博士研究生,主要研究方向:信号检测与估计、迭代接收机设计;张园园(1990-),女,河南平顶山人,博士研究生,主要研究方向:通信信号处理、干扰抑制与消除。
  • 基金资助:

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

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

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

CLC Number: