无线传感网协作定位研究
|
摘要
在无线传感网络中,位置信息对传感器网络的监测应用非常重要,事件发生的位置或获取信息节点的位置是传感器节点监测内容中所包含的重要信息,没有位置信息的监测消息往往毫无意义。因此,对无线传感网络节点的定位成了当前无线传感网络研究领域的热点问题,解决该问题对无线传感网络的广泛应用具有重要意义。本文根据当前无线传感网的应用特点,对基于到达时间(TOA)测距方法的协作定位问题进行了研究。
无线传感网的协作定位精度和许多因素有关。本文把Cramer-Rao定理中的FIM矩阵作为分析工具,分析了在协作定位中,影响定位精度的各种因素。同时本文还从理论上证明了协作定位相对于非协作定位一定可以带来定位精度的提高。
针对无线传感网的协作定位问题,本文提出了一种分布式,高精度,低复杂度的定位算法。算法首先利用DV-hop算法的思想,通过计算到基站的跳数来估计节点的初始位置,在得到一个较好的初始位置后,开始迭代计算最优解。算法根据每个节点的CRLB和到最近基站的跳数赋予每个节点一个权重值。在计算非线性最小二乘法时,权重值越大,则该项误差将被优先最小化。仿真结果表明该算法有快速的收敛性,该算法的综合性能优于当前最好的集中式算法SDP。
Location information is critical to the surveillance of the network in wireless sensor network. The location of the event or the location of the node from which information is acquired are important information in sensor network monitoring. Monitoring without location information is usually meaningless. Therefore, estimating the location of the event or the location of the node is the fundamental function of WSN. The problem of locating nodes in sensor network has become a hot issue. TOA-based cooperative localization technique has been investigated in this work.
In WSN, the accuracy of cooperative localization is related to many factors. In this work, Fisher Information Matrix in Cramer-Rao Lower Bound has been used as tool for analysis. Several factors related to accuracy are analyzed. In addition, the benefit from cooperative localization compared with non-cooperative localization is proved.
A novel distributed, high-accurate and low complexity localization algorithm is proposed. Firstly, the thought from DV-hop is employed. By counting hop from mobile node to fixed node, approximate distance can be estimated. After distances to all fixed node are estimated, the approximate location can be calculated, which is a good initial value for iterative method. Then every node is assigned a weight value according to their CRLB and hop counts to nearest fixed node. When solving nonlinear least square, the item with the largest weight will have the highest priority to have its error minimized. Simulation shows that the algorithm converges quickly, and global optimum solution is guaranteed. In general situation, the proposed algorithm performs better than currently best SDP method.
无线传感网的协作定位精度和许多因素有关。本文把Cramer-Rao定理中的FIM矩阵作为分析工具,分析了在协作定位中,影响定位精度的各种因素。同时本文还从理论上证明了协作定位相对于非协作定位一定可以带来定位精度的提高。
针对无线传感网的协作定位问题,本文提出了一种分布式,高精度,低复杂度的定位算法。算法首先利用DV-hop算法的思想,通过计算到基站的跳数来估计节点的初始位置,在得到一个较好的初始位置后,开始迭代计算最优解。算法根据每个节点的CRLB和到最近基站的跳数赋予每个节点一个权重值。在计算非线性最小二乘法时,权重值越大,则该项误差将被优先最小化。仿真结果表明该算法有快速的收敛性,该算法的综合性能优于当前最好的集中式算法SDP。
Location information is critical to the surveillance of the network in wireless sensor network. The location of the event or the location of the node from which information is acquired are important information in sensor network monitoring. Monitoring without location information is usually meaningless. Therefore, estimating the location of the event or the location of the node is the fundamental function of WSN. The problem of locating nodes in sensor network has become a hot issue. TOA-based cooperative localization technique has been investigated in this work.
In WSN, the accuracy of cooperative localization is related to many factors. In this work, Fisher Information Matrix in Cramer-Rao Lower Bound has been used as tool for analysis. Several factors related to accuracy are analyzed. In addition, the benefit from cooperative localization compared with non-cooperative localization is proved.
A novel distributed, high-accurate and low complexity localization algorithm is proposed. Firstly, the thought from DV-hop is employed. By counting hop from mobile node to fixed node, approximate distance can be estimated. After distances to all fixed node are estimated, the approximate location can be calculated, which is a good initial value for iterative method. Then every node is assigned a weight value according to their CRLB and hop counts to nearest fixed node. When solving nonlinear least square, the item with the largest weight will have the highest priority to have its error minimized. Simulation shows that the algorithm converges quickly, and global optimum solution is guaranteed. In general situation, the proposed algorithm performs better than currently best SDP method.
引文
[1]陈林星,无线传感器网络技术与应用,电子工业出版社(北京),2009
[2]李善仓,张克旺,无线传感器网络原理与应用,机械工业出版社(北京),2008
[3]李晓维,无线传感器网络技术,北京理工大学出版社(北京),2007
[4]王雪,无线传感网络测量系统,机械工业出版社(北京),2007
[5] D. Koks, Numerical calculations for passive geolocation scenarios, Tech. Rep. DSTO‐RR‐0000, 2005.
[6] R. Klukas, M. Fattouche, Line‐of‐sight angle of arrival estimation in the outdoor multipath environment, IEEE Transactions on Vehicular Technology 47 (1) (1998) 342– 351.
[7] T. Rappaport, J. Reed, B. Woerner, Position location using wireless communications on highways of the future, IEEE Communications Magazine 34 (10) (1996) 33–41.
[8] T.E. Biedka, J.H. Reed, B.D. Woerner, Direction finding methods for CDMA systems, in: Thirteenth Asilomar Conference on Signals, Systems and Computers, vol. 1,1996, pp. 637–641.
[9] D.W. Bliss, K.W. Forsythe, Angle of arrival estimation in the presence of multiple access interference for CDMA cellular phone systems, in: Proceedings of the 2000 IEEE Sensor Array and Multichannel Signal Processing Work‐shop, 2000, pp. 408–412.
[10] I. Ziskind, M. Wax, Maximum likelihood localization of multiple sources by alternating projection, IEEE Transac‐tions on Acoustics, Speech, and Signal Processing 36 (10) (1988) 1553–1560.
[11] S.V. Schell, W.A. Gardner, High‐resolution direction finding, Handbook of Statistics 10 (1993) 755–817
[12] D. McCrady, L. Doyle, H. Forstrom, T. Dempsey, M.Martorana, Mobile ranging using low‐accuracy clocks,IEEE Transactions on Microwave Theory and Techniques 48 (6) (2000) 951–958.
[13] N.B. Priyantha, A. Chakraborty, H. Balakrishnan, The cricket location‐support system, in: Proceedings of the Sixth Annual ACM International Conference on Mobile Com‐puting and Networking, 2000, pp. 32–43.
[14] J.‐Y. Lee, R. Scholtz, Ranging in a dense multipath environment using an UWB radio link, IEEE Journal on Selected Areas in Communications 20 (9) (2002) 1677–1683.
[44] A. Savvides, H. Park,M.B. Srivastava, The bits and ops of the n‐hop multilateration primitive for node localization problems, in: International Workshop on Sensor Networks Application, 2002, pp. 112–121.
[45] K. Langendoen, N. Reijers, Distributed localization in wireless sensor networks: a quantative comparison, Computer Networks 43 (2003) 499–518.
[46] X. Ji, H. Zha, Sensor positioning in wireless ad‐hoc sensor networks using multidimensional scaling, in: IEEE INFOCOM, vol. 4, 2004, pp. 2652–2661.
[47] S. Capkun, M. Hamdi, J. Hubaux, GPS‐free positioning in mobile ad‐hoc networks, in: 34th Hawaii International Conference on System Sciences, 2001, pp. 3481–3490.
[48] C. Kwok, D. Fox, M. Meila, Real‐time particle filters, Proceedings of the IEEE 92 (3) (2004) 469–484.
[49] A. Ihler, I. Fisher, J.W. R. Moses, A. Willsky, Nonparametric belief propagation for self‐localization of sensor networks, IEEE Journal on Selected Areas in Communications 23 (4) (2005) 809–819.
[50] S.M.Kay, Fundamentals of Statistical Processing, Volume I: Estimation Theory. Englewood Cliffs, NJ: Prentice‐Hall.
[51] E.G. Larsson,“Cramer‐Rao bound analysis of distributed positioning in sensor networks,”IEEE Signal Processing Letters, Vol. 11, No. 3, pp. 334‐337, March 2004.
[52] H. L. Van Trees, Detection, Estimation and Modulation Theory.New York, NY: Wiley, 1968, vol. 1.
[53] S. Gezici et al., Localization via ultra‐wideband radios: a look at positioning aspects for future sensor networks, IEEE Signal Processing Mag., vol. 22, pp. 70–84, July 2005.
[54] M. Nicoli and D. Fontanella , Fundamental Performance Limits of TOA‐based Cooperative Localization, IEEE International Conference on Communications 2009
[55] P. Biswas and Y. Ye, Semidefinite programming for ad hoc wireless sensor network localization, in Proceedings of the Third International Symposium on Information Processing in Sensor Networks, Berkeley, CA, 2004.
[56] Boyd, S., Ghaoui, L.E., Feron, E., Balakrishnan, V., Linear matrix inequalities in system and control theory. SIAM (1994)
[57] Karmarkar, Narendra, A New Polynomial Time Algorithm for Linear Programming, Combinatorica, Vol 4, no. 4, pp. 373–395.
[58] David K. Goldenberg, Arvind Krishnamurthy, Wesley C. Maness, Robust Distributed Network Localization with Noisy Range Measurements, Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems(2005)
[59] H. Lutkepohl, Handbook of Matrices, John Wiley & Sons, 1996
[60] Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 978‐0‐521‐38632‐6
[61] W.A. Gardner, C.K. Chen, Signal‐selective time‐di erence‐of‐arrival estimation for passive location of man‐made signal sources in highly corruptive environments. I. Theory and method, IEEE Transactions on Signal Processing 40 (5) (1992) 1168–1184.
[62] B.T. Fang, Simple solutions for hyperbolic and related position fixes, IEEE Transactions on Aerospace and Electronic Systems 26 (5) (1990) 748–753.
[63] J. Smith, J. Abel, The spherical interpolation method of source localization, IEEE Journal of Oceanic Engineering 12 (1) (1987) 246–252.
[64] J.S. Abel, A divide and conquer approach to least‐squares estimation, IEEE Transactions on Aerospace and Electronic Systems 26 (2) (1990) 423–427.
[65] L.M. Ni, L. Yunhao, L. Yiu Cho, A.P. Patil, LANDM‐ARC: indoor location sensing using active RFID, in: Proceedings of the First IEEE International Conference on Pervasive Computing and Communications (PerCom2003), 2003, pp. 407–415.
[66] T. Eren, D. Goldenberg, W. Whiteley, R. Yang, A.S., Morse, B.D.O. Anderson, P. Belhumeur, Rigidity and randomness in network localization, in: IEEE INFOCOM, vol. 4, 2004, pp. 2673–2684.
[67] J. Aspnes, T. Eren, D. Goldenberg, A.S. Morse, W., Whiteley, Y. Yang, B.D.O. Anderson, P. Belhumeur, A theory of network localization, IEEE Transactions on Mobile Computing 5 (12) (2006) 1663–1678.
[68] D. Moore, J. Leonard, D. Rus, S. Teller, Robust distributed network localization with noisy range measurements, in: The 2nd ACM Conference on Embedded Networked Sensor Systems (SenSys’04), 2004, pp. 50–61.
[69] B.D.O. Anderson, P. Belhumeur, T. Eren, D. Goldenberg, A.S. Morse, W. Whiteley, R. Yang, Graphical properties of easily localizable sensor networks, Wireless Networks, submitted for publication.
[70] R. Connelly, Generic global rigidity, Discrete and Computational Geometry 33 (2005) 549–563.
[71] F. Daneshgaran, M. Laddomada, and M. Mondin,“The problem of localization in networks of randomly deployed nodes: Asymptotic and finite analysis, and thresholds,”submitted to IEEE Trans. Inform. Theory, Oct. 2007, available on ArXiv.org arXiv:0710.0531.
[72] F. Daneshgaran, M. Laddomada, and M. Mondin,“Connection between system parameters and localization probability in network of randomly distributed nodes,”IEEE Trans. Wireless Commun., vol. 6, no. 12, pp. 4383–4389, Dec. 2007.
[73] C. T. Kelley, Iterative Methods for Optimization, SIAM Frontiers in Applied Mathematics, no 18, 1999, ISBN 0‐89871‐433‐8
[74] L. Doherty, L. E. Ghaoui, and S. J. Pister. Convex position estimation in wireless sensor networks. In IEEE Infocom, volume 3, pages 1655 {1663, April 2001
[2]李善仓,张克旺,无线传感器网络原理与应用,机械工业出版社(北京),2008
[3]李晓维,无线传感器网络技术,北京理工大学出版社(北京),2007
[4]王雪,无线传感网络测量系统,机械工业出版社(北京),2007
[5] D. Koks, Numerical calculations for passive geolocation scenarios, Tech. Rep. DSTO‐RR‐0000, 2005.
[6] R. Klukas, M. Fattouche, Line‐of‐sight angle of arrival estimation in the outdoor multipath environment, IEEE Transactions on Vehicular Technology 47 (1) (1998) 342– 351.
[7] T. Rappaport, J. Reed, B. Woerner, Position location using wireless communications on highways of the future, IEEE Communications Magazine 34 (10) (1996) 33–41.
[8] T.E. Biedka, J.H. Reed, B.D. Woerner, Direction finding methods for CDMA systems, in: Thirteenth Asilomar Conference on Signals, Systems and Computers, vol. 1,1996, pp. 637–641.
[9] D.W. Bliss, K.W. Forsythe, Angle of arrival estimation in the presence of multiple access interference for CDMA cellular phone systems, in: Proceedings of the 2000 IEEE Sensor Array and Multichannel Signal Processing Work‐shop, 2000, pp. 408–412.
[10] I. Ziskind, M. Wax, Maximum likelihood localization of multiple sources by alternating projection, IEEE Transac‐tions on Acoustics, Speech, and Signal Processing 36 (10) (1988) 1553–1560.
[11] S.V. Schell, W.A. Gardner, High‐resolution direction finding, Handbook of Statistics 10 (1993) 755–817
[12] D. McCrady, L. Doyle, H. Forstrom, T. Dempsey, M.Martorana, Mobile ranging using low‐accuracy clocks,IEEE Transactions on Microwave Theory and Techniques 48 (6) (2000) 951–958.
[13] N.B. Priyantha, A. Chakraborty, H. Balakrishnan, The cricket location‐support system, in: Proceedings of the Sixth Annual ACM International Conference on Mobile Com‐puting and Networking, 2000, pp. 32–43.
[14] J.‐Y. Lee, R. Scholtz, Ranging in a dense multipath environment using an UWB radio link, IEEE Journal on Selected Areas in Communications 20 (9) (2002) 1677–1683.
[44] A. Savvides, H. Park,M.B. Srivastava, The bits and ops of the n‐hop multilateration primitive for node localization problems, in: International Workshop on Sensor Networks Application, 2002, pp. 112–121.
[45] K. Langendoen, N. Reijers, Distributed localization in wireless sensor networks: a quantative comparison, Computer Networks 43 (2003) 499–518.
[46] X. Ji, H. Zha, Sensor positioning in wireless ad‐hoc sensor networks using multidimensional scaling, in: IEEE INFOCOM, vol. 4, 2004, pp. 2652–2661.
[47] S. Capkun, M. Hamdi, J. Hubaux, GPS‐free positioning in mobile ad‐hoc networks, in: 34th Hawaii International Conference on System Sciences, 2001, pp. 3481–3490.
[48] C. Kwok, D. Fox, M. Meila, Real‐time particle filters, Proceedings of the IEEE 92 (3) (2004) 469–484.
[49] A. Ihler, I. Fisher, J.W. R. Moses, A. Willsky, Nonparametric belief propagation for self‐localization of sensor networks, IEEE Journal on Selected Areas in Communications 23 (4) (2005) 809–819.
[50] S.M.Kay, Fundamentals of Statistical Processing, Volume I: Estimation Theory. Englewood Cliffs, NJ: Prentice‐Hall.
[51] E.G. Larsson,“Cramer‐Rao bound analysis of distributed positioning in sensor networks,”IEEE Signal Processing Letters, Vol. 11, No. 3, pp. 334‐337, March 2004.
[52] H. L. Van Trees, Detection, Estimation and Modulation Theory.New York, NY: Wiley, 1968, vol. 1.
[53] S. Gezici et al., Localization via ultra‐wideband radios: a look at positioning aspects for future sensor networks, IEEE Signal Processing Mag., vol. 22, pp. 70–84, July 2005.
[54] M. Nicoli and D. Fontanella , Fundamental Performance Limits of TOA‐based Cooperative Localization, IEEE International Conference on Communications 2009
[55] P. Biswas and Y. Ye, Semidefinite programming for ad hoc wireless sensor network localization, in Proceedings of the Third International Symposium on Information Processing in Sensor Networks, Berkeley, CA, 2004.
[56] Boyd, S., Ghaoui, L.E., Feron, E., Balakrishnan, V., Linear matrix inequalities in system and control theory. SIAM (1994)
[57] Karmarkar, Narendra, A New Polynomial Time Algorithm for Linear Programming, Combinatorica, Vol 4, no. 4, pp. 373–395.
[58] David K. Goldenberg, Arvind Krishnamurthy, Wesley C. Maness, Robust Distributed Network Localization with Noisy Range Measurements, Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems(2005)
[59] H. Lutkepohl, Handbook of Matrices, John Wiley & Sons, 1996
[60] Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 978‐0‐521‐38632‐6
[61] W.A. Gardner, C.K. Chen, Signal‐selective time‐di erence‐of‐arrival estimation for passive location of man‐made signal sources in highly corruptive environments. I. Theory and method, IEEE Transactions on Signal Processing 40 (5) (1992) 1168–1184.
[62] B.T. Fang, Simple solutions for hyperbolic and related position fixes, IEEE Transactions on Aerospace and Electronic Systems 26 (5) (1990) 748–753.
[63] J. Smith, J. Abel, The spherical interpolation method of source localization, IEEE Journal of Oceanic Engineering 12 (1) (1987) 246–252.
[64] J.S. Abel, A divide and conquer approach to least‐squares estimation, IEEE Transactions on Aerospace and Electronic Systems 26 (2) (1990) 423–427.
[65] L.M. Ni, L. Yunhao, L. Yiu Cho, A.P. Patil, LANDM‐ARC: indoor location sensing using active RFID, in: Proceedings of the First IEEE International Conference on Pervasive Computing and Communications (PerCom2003), 2003, pp. 407–415.
[66] T. Eren, D. Goldenberg, W. Whiteley, R. Yang, A.S., Morse, B.D.O. Anderson, P. Belhumeur, Rigidity and randomness in network localization, in: IEEE INFOCOM, vol. 4, 2004, pp. 2673–2684.
[67] J. Aspnes, T. Eren, D. Goldenberg, A.S. Morse, W., Whiteley, Y. Yang, B.D.O. Anderson, P. Belhumeur, A theory of network localization, IEEE Transactions on Mobile Computing 5 (12) (2006) 1663–1678.
[68] D. Moore, J. Leonard, D. Rus, S. Teller, Robust distributed network localization with noisy range measurements, in: The 2nd ACM Conference on Embedded Networked Sensor Systems (SenSys’04), 2004, pp. 50–61.
[69] B.D.O. Anderson, P. Belhumeur, T. Eren, D. Goldenberg, A.S. Morse, W. Whiteley, R. Yang, Graphical properties of easily localizable sensor networks, Wireless Networks, submitted for publication.
[70] R. Connelly, Generic global rigidity, Discrete and Computational Geometry 33 (2005) 549–563.
[71] F. Daneshgaran, M. Laddomada, and M. Mondin,“The problem of localization in networks of randomly deployed nodes: Asymptotic and finite analysis, and thresholds,”submitted to IEEE Trans. Inform. Theory, Oct. 2007, available on ArXiv.org arXiv:0710.0531.
[72] F. Daneshgaran, M. Laddomada, and M. Mondin,“Connection between system parameters and localization probability in network of randomly distributed nodes,”IEEE Trans. Wireless Commun., vol. 6, no. 12, pp. 4383–4389, Dec. 2007.
[73] C. T. Kelley, Iterative Methods for Optimization, SIAM Frontiers in Applied Mathematics, no 18, 1999, ISBN 0‐89871‐433‐8
[74] L. Doherty, L. E. Ghaoui, and S. J. Pister. Convex position estimation in wireless sensor networks. In IEEE Infocom, volume 3, pages 1655 {1663, April 2001