崔建華，王忠勇，張傳宗，張園園

(1.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002； 2.洛陽師范學(xué)院 物理與電子信息學(xué)院，河南 洛陽 471934；3.鄭州大學(xué) 信息工程學(xué)院，鄭州 450001)

基于因子圖和聯(lián)合消息傳遞的無線網(wǎng)絡(luò)協(xié)作定位算法

崔建華1,2，王忠勇3*，張傳宗3，張園園3

(1.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 450002； 2.洛陽師范學(xué)院 物理與電子信息學(xué)院，河南 洛陽 471934；3.鄭州大學(xué) 信息工程學(xué)院，鄭州 450001)

(*通信作者電子郵箱zywangzzu@gmail.com)

針對現(xiàn)有基于消息傳遞算法的無線網(wǎng)絡(luò)節(jié)點定位算法復(fù)雜度和通信開銷過高的問題，提出一種基于測距的、低復(fù)雜度低協(xié)作開銷的聯(lián)合消息傳遞節(jié)點定位算法。所提算法考慮參考節(jié)點位置的不確定性以減少誤差累積，并將消息約束為高斯函數(shù)以降低通信開銷。首先，根據(jù)系統(tǒng)的概率模型和因子分解設(shè)計因子圖；然后，根據(jù)狀態(tài)轉(zhuǎn)移模型和測距模型的特點，分別使用置信傳播和平均場方法計算預(yù)測消息和協(xié)作消息；最后，在每次迭代過程中，通過非線性項的泰勒展開將非高斯置信消息近似為高斯函數(shù)。仿真分析表明，所提算法的定位性能與基于粒子的SPAWN算法接近，但節(jié)點間傳輸?shù)男畔⒂纱罅苛Ｗ幼優(yōu)榫迪蛄亢蛥f(xié)方差矩陣，同時計算復(fù)雜度也大幅降低。

近似貝葉斯推理；因子圖；置信傳播；平均場方法；無線傳感器網(wǎng)絡(luò)；協(xié)作定位

0 引言

在基于無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)的應(yīng)用中，傳感器節(jié)點檢測到的信息若沒有準(zhǔn)確的位置信息將變得毫無價值[1]。但考慮到成本和能量限制，一般只有少數(shù)參考節(jié)點的位置是已知的，其他大部分節(jié)點(稱為待定位節(jié)點)通過鄰近的參考節(jié)點的位置和與其之間的距離等觀測信息確定自己的位置，參考節(jié)點較少時定位誤差較大。近年來出現(xiàn)的協(xié)作定位技術(shù)中，待定位節(jié)點之間也進行通信，從而可有效提高定位精度，引起國內(nèi)外學(xué)者的廣泛關(guān)注，并提出了許多協(xié)作定位算法，如最小二乘(Least Square, LS)[2]、最大似然(Maximum Likelihood, ML)[3]、多維尺度MAP(MultiDimensional Scaling MAP, MDS-MAP)[4]以及卡爾曼濾波[5]和粒子濾波[6]等。

在近似貝葉斯推理的實現(xiàn)方法中，基于因子圖的消息傳遞算法特別適用于大規(guī)模概率模型和分布式運算[7]，其中置信傳播(Belief Propagation, BP)方法在樹圖下可得到精確的邊緣概率密度分布函數(shù)，在有環(huán)圖下也常常能獲得較好的性能。近年有學(xué)者將BP應(yīng)用于無線網(wǎng)絡(luò)協(xié)作定位中，但非線性測距模型會導(dǎo)致消息計算非常復(fù)雜。一種解決方法是使用非參數(shù)化消息。Ihler等[8]將非參數(shù)化置信傳播(Nonparametric Belief Propagation, NBP)用于靜態(tài)無線傳感器網(wǎng)絡(luò)節(jié)點定位，Wymeersch等[9]進一步提出了適用于動態(tài)網(wǎng)絡(luò)的SPAWN(Sum-Product Algorithm over a Wireless Network)算法?；贜BP的定位算法使用大量粒子表示消息，能靈活表示多種形式的消息，當(dāng)粒子數(shù)足夠多時可獲得很高的定位精度，但計算復(fù)雜度和通信開銷非常高[10]。Li等[11]提出一種基于序貫粒子的BP算法，利用吉布斯采樣對消息進行粒子化，有效降低了計算復(fù)雜度，但通信負(fù)載依然較高。另一種解決方法是將測距模型線性化并采用參數(shù)化消息。北京理工大學(xué)武楠等利用一階泰勒展開將測距模型線性化，提出了高斯BP節(jié)點定位算法[12-13]。相對于BP方法，平均場(Mean Field, MF)方法更適用于指數(shù)型消息，消息更新規(guī)則更加簡單。Pedersen等[14]提出一種基于MF的靜態(tài)網(wǎng)絡(luò)節(jié)點定位算法，該算法采用高斯型消息，并使用最小化KL散度(Kullback-Leibler Divergence, KLD)將非高斯消息近似為高斯消息，但近似過程中出現(xiàn)了第一類合流超幾何函數(shù)，致使計算復(fù)雜度非常高，且估計性能與基于BP的算法相比有所下降。

針對上述問題，本文將高性能的BP方法和低復(fù)雜度的MF方法結(jié)合起來，提出一種低復(fù)雜度低通信開銷的協(xié)作定位算法，并考慮參考節(jié)點位置可能存在誤差，以避免誤差累積引起的定位精度下降問題。

1 系統(tǒng)模型與因子圖

假設(shè)節(jié)點i∈M的狀態(tài)轉(zhuǎn)移模型為：

(1)

(2)

(3)

(4)

k時刻，所有節(jié)點位置變量和測量距離的集合分別記作Xk:i∈A∪M}和Dk:?i∈M,}，并將0時刻到K時刻所有節(jié)點位置變量和測量距離的集合分別記作X0:K{X0,X1,…,XK}和D1:K{D1,D2,…,DK}。根據(jù)貝葉斯準(zhǔn)則，從0時刻到K時刻節(jié)點位置變量的聯(lián)合后驗PDF可表示為：

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

(5)

通常情況下因子圖是無向圖，但由于網(wǎng)絡(luò)中節(jié)點間的連通關(guān)系會隨時間變化，因此不計算從當(dāng)前時刻到過去時刻的消息。此外，本算法考慮參考節(jié)點的位置可能有一定誤差的情況，將其看作變量。在各時刻的迭代計算中，參考節(jié)點的位置也可以更新。

圖1 式(5)的因子分解所對應(yīng)的因子圖Fig. 1 Factor graph corresponding to factorization in equation (5)

2 基于BP-MF的協(xié)作定位算法

2.1 基于BP方法的預(yù)測消息計算

(6)

(7)

(8)

2.2 基于MF方法的協(xié)作消息計算

(9)

將式(4)帶入式(9)可得：

(10)

同理可得：

(11)

2.3 置信的計算和近似

(12)

(13)

(14)

(15)

2.4 算法執(zhí)行流程

基于BP方法的預(yù)測過程是無環(huán)圖，因此預(yù)測消息不進行迭代更新，基于MF方法的協(xié)作消息以及每個節(jié)點位置變量的置信需要進行迭代計算。MF方法總是保證良好的收斂性能[15]，本文算法在先驗較好的情況下收斂較快，先驗較差時收斂較慢。

本文算法的執(zhí)行流程如下所示。

3) 迭代開始，各節(jié)點并行執(zhí)行：

a) 廣播自己的位置和測量距離并接收鄰居點的信息；

4) 迭代終止。

5) 各節(jié)點根據(jù)最大后驗估計準(zhǔn)則確定估計位置。

6) 算法結(jié)束。

3 仿真分析

當(dāng)σa,k=1 m時，即參考節(jié)點位置的誤差在0～1 m時，考慮其不確定性與不考慮其不確定性兩種情況下的CDF曲線如圖2所示?？梢钥闯?，考慮參考節(jié)點位置可能存在的誤差能夠避免誤差累積，從而獲得更好的定位精度。

圖2 是否考慮參考節(jié)點位置的不確定性對定位性能的影響Fig. 2 Impact of considering anchors’ uncertainty on positioning performance

不同σa,k下定位誤差累積分布函數(shù)如圖3所示。

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

由圖3可知，σa,k越小，即參考節(jié)點測量位置的誤差越小，定位性能越好。此外，隨著定位時刻k的增加，定位精度有所提高，這是因為隨著k的增加待定位節(jié)點的先驗信息(即預(yù)測信息)準(zhǔn)確度提高。但當(dāng)k大于一定值時(實驗中k>10)，定位精度基本穩(wěn)定，不會有大幅度提高。

圖4 本文算法與SPAWN算法的定位性能對比Fig. 4 Performance comparison of the proposed algorithm and SPAWN

4 結(jié)語

本文針對參考節(jié)點位置存在一定模糊性的無線傳感器網(wǎng)絡(luò)，提出一種基于BP和MF的聯(lián)合消息傳遞協(xié)作定位算法。仿真結(jié)果和分析表明，其估計性能與基于粒子的SPAWN接近，并避免了通信開銷和計算復(fù)雜度過大的問題。在本文基礎(chǔ)上，下一步將研究基于消息傳遞算法的目標(biāo)跟蹤算法。

References)

[1] 武曉琳, 單志龍, 曹樹林，等. 基于接收信號強度指示測距的蒙特卡羅盒移動節(jié)點定位算法[J]. 計算機應(yīng)用, 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] 肖如良, 李奕如, 江少華, 等. 基于卡爾曼濾波與中位加權(quán)的定位算法[J]. 計算機應(yīng)用, 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] 羅元, 龐冬雪, 張毅, 等. 基于自適應(yīng)多提議分布粒子濾波的蒙特卡洛定位算法[J]. 計算機應(yīng)用, 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] 李彬. 無線網(wǎng)絡(luò)中的分布式定位算法研究 [D]. 北京: 北京理工大學(xué), 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。 基金項目:國家自然科學(xué)基金資助項目(61571402，61401401)。

崔建華(1981—)，女，河南新鄉(xiāng)人，講師，博士研究生，主要研究方向：信號與信息處理、無線網(wǎng)絡(luò)定位與跟蹤； 王忠勇(1965—)，男，江西吉安人，教授，博士，主要研究方向：通信信號處理、嵌入式系統(tǒng)設(shè)計； 張傳宗(1982—)，男，河南南陽人，博士研究生，主要研究方向：信號檢測與估計、迭代接收機設(shè)計； 張園園(1990—)，女，河南平頂山人，博士研究生，主要研究方向：通信信號處理、干擾抑制與消除。

1001-9081(2017)05-1306-05

10.11772/j.issn.1001-9081.2017.05.1306

TN911.23

A