基于RSSI的无线传感器网络多边定位算法研究
|
摘要
无线传感器网络是近年发展起来的一种新型数据获取技术,是现代传感器技术、MEMS、通信技术、嵌入式计算技术和分布式信息处理技术等综合交叉起来的一个研究领域,在军事侦察、环境监测、医疗和建筑物监测等领域有着广阔的应用前景。
定位作为WSN的重要支撑技术之一,成为该领域的一个研究热点。虽然出现了接收信号角度定位、DV-hop定位、质心定位和近似三角形内点测试法定位等多种定位算法,但总体而言,由于定位是一个不适定问题,目前的算法普遍存在定位精度不高的问题,本文针对无线传感器网络中的平面定位和空间定位问题,提出利用Tikhonov正则化方法和迭代Tikhonov正则化方法解决多边定位中的不适定问题。研究了定位模型的建立、信道衰减指数的确定、定位最优参考点数的选取、正则化参数的选取、迭代终止原则的确定等问题。
研究结果表明,在室外平面定位时,当RSSI测距的对数距离路径损耗模型信道衰减指数为4时测距误差最小,当定位参考点数为5时可获得最优定位结果。采用Tikhonov正则化方法,正则化参数α取400,迭代Tikhonov正则化方法正则化参数α取700,迭代终止原则取Δ≤3时,这两种方法均可取得最优的定位结果,最小可使误差降低到1m以内且迭代法在5步左右收敛。在室内空间定位时,针对有障碍物阻挡的情况,将对数距离路径损耗模型的信道衰减指数修正为6时可获得最佳测量距离。Tikhonov正则化方法参数α取50,迭代Tikhonov正则化方法参数α取100,迭代终止原则取Δ=‖X_(α,δ)~(i+1)-X_(α,δ)~i‖、Δ≤1时,正则化方法的定位结果各自达到最优且迭代法在5步左右收敛,定位误差普遍降低到2m左右,定位结果要明显优于经典的极大似然法定位结果。
Wireless sensor network(WSN) is a new data acquisition technology developed in the recent years which includes modern sensor technology,MEMS, communication technology,embedded compute technology,distributed information processing technology,etc.WSN has broad application fields such as military reconnaissance,environmental monitoring,medical monitoring and building monitoring,etc.
As the important support technologies of WSN,localization becomes a key problem.Although some kinds of localization algorithms are proposed,such as Received Signal Angle Localization,DV-hop Localization,Centroid Localization and APIT,etc,low localization accuracy is widespread in the current localization algorithms as localization is an ill-posed problem in the reason of ranging error.In this paper,based on Tikhonov regularization and Tikhonov iteration regularization methods two localization algorithms are proposed for the ill-posed problem in the multilateral localization.The location model based on RSSI,the channel attenuation index n,the optimal reference node number,the regularization parameterαand the corresponding stopping rule of iteration are studied.
Research results show that the best localization results can be acquired while the Log-distance Path Loss Model channel attenuation index n is 4 and the reference node number is 5 in the plane localization.The minimum localization errors can be to less than 1 meter while the Tikhonov regularization parameterαis 400,the Tikhonov iteration regularization parameterαis 700 and the correspond stopping rule of iteration is△≤3.The iteration convergence needs about 5 steps.In the spatial localization,the optimal measuring distances can be acquired while the Log-distance Path Loss Model channel attenuation index n is modified as 6 to cope with the obstruction.The localization errors can be generally reduced to about 2 meters while the Tikhonov regularization parameterαis 50,the Tikhonov iteration regularization parameterαis 100 and the correspond stopping rule of iteration is△=‖X_(α,δ)~(i+1)-X_(α,δ)~i‖&△≤1.The iteration convergence needs about 5 steps.These results are significantly better than those of the Maximum Likelihood Estimation (MLE) method.
定位作为WSN的重要支撑技术之一,成为该领域的一个研究热点。虽然出现了接收信号角度定位、DV-hop定位、质心定位和近似三角形内点测试法定位等多种定位算法,但总体而言,由于定位是一个不适定问题,目前的算法普遍存在定位精度不高的问题,本文针对无线传感器网络中的平面定位和空间定位问题,提出利用Tikhonov正则化方法和迭代Tikhonov正则化方法解决多边定位中的不适定问题。研究了定位模型的建立、信道衰减指数的确定、定位最优参考点数的选取、正则化参数的选取、迭代终止原则的确定等问题。
研究结果表明,在室外平面定位时,当RSSI测距的对数距离路径损耗模型信道衰减指数为4时测距误差最小,当定位参考点数为5时可获得最优定位结果。采用Tikhonov正则化方法,正则化参数α取400,迭代Tikhonov正则化方法正则化参数α取700,迭代终止原则取Δ≤3时,这两种方法均可取得最优的定位结果,最小可使误差降低到1m以内且迭代法在5步左右收敛。在室内空间定位时,针对有障碍物阻挡的情况,将对数距离路径损耗模型的信道衰减指数修正为6时可获得最佳测量距离。Tikhonov正则化方法参数α取50,迭代Tikhonov正则化方法参数α取100,迭代终止原则取Δ=‖X_(α,δ)~(i+1)-X_(α,δ)~i‖、Δ≤1时,正则化方法的定位结果各自达到最优且迭代法在5步左右收敛,定位误差普遍降低到2m左右,定位结果要明显优于经典的极大似然法定位结果。
Wireless sensor network(WSN) is a new data acquisition technology developed in the recent years which includes modern sensor technology,MEMS, communication technology,embedded compute technology,distributed information processing technology,etc.WSN has broad application fields such as military reconnaissance,environmental monitoring,medical monitoring and building monitoring,etc.
As the important support technologies of WSN,localization becomes a key problem.Although some kinds of localization algorithms are proposed,such as Received Signal Angle Localization,DV-hop Localization,Centroid Localization and APIT,etc,low localization accuracy is widespread in the current localization algorithms as localization is an ill-posed problem in the reason of ranging error.In this paper,based on Tikhonov regularization and Tikhonov iteration regularization methods two localization algorithms are proposed for the ill-posed problem in the multilateral localization.The location model based on RSSI,the channel attenuation index n,the optimal reference node number,the regularization parameterαand the corresponding stopping rule of iteration are studied.
Research results show that the best localization results can be acquired while the Log-distance Path Loss Model channel attenuation index n is 4 and the reference node number is 5 in the plane localization.The minimum localization errors can be to less than 1 meter while the Tikhonov regularization parameterαis 400,the Tikhonov iteration regularization parameterαis 700 and the correspond stopping rule of iteration is△≤3.The iteration convergence needs about 5 steps.In the spatial localization,the optimal measuring distances can be acquired while the Log-distance Path Loss Model channel attenuation index n is modified as 6 to cope with the obstruction.The localization errors can be generally reduced to about 2 meters while the Tikhonov regularization parameterαis 50,the Tikhonov iteration regularization parameterαis 100 and the correspond stopping rule of iteration is△=‖X_(α,δ)~(i+1)-X_(α,δ)~i‖&△≤1.The iteration convergence needs about 5 steps.These results are significantly better than those of the Maximum Likelihood Estimation (MLE) method.
引文
[1]孙利民.无线传感器网络.北京:清华大学出版社,2005:3-4,135-155.
[2]任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003.7,Vol,14(N o2):1148-1157
[3]汪炀.无线传感器网络定位技术研究.中国科学技术大学博士论文,2007:1-20.
[4]李晓维.无线传感器网络技术.北京:北京理工大学出版社,2007:191-219.
[5]Holger Karl,Andreas Willig.无线传感器网络协议与体系结构.北京:电子工业出版社,2007:198-214.
[6]J.Hightower,G.Borriello.Location systems for ubiquitous computing.IEEE Computer,2001,34(8):57-66.
[7]J.Hightower,G.Borriello.A survey and taxonomy of location systems for ubiquitous computing.Technical Report UW-CSE 2001-08-03,U.of Washington,Computer Science and Engineering,Seattle,WA,2001.
[8]Theodore S.Rappaport.Wireless communications principles and practice.Publishing House of Electronics Industry,2004:69-138.
[9]Niculescu D,Nath B.Ad hoc positioning system(APS) using AOA.In:Proc 22~(nd) Annual Joint Conf of the IEEE Computer and Communications Societies (INFOCOM'2003).IEEE,Vol.3,2003.
[10]D.Niculescu,B.Nath.Ad hoc Positioning System(APS).Proceedings of IEEE Globecom 2001:2886-2931.
[11]D.Niculescu,B.Nath.DV-based Positioning in Ad Hoc Networks.Kluwer Journal of Telecommunication Systems,Vol.22,No.1,2003:267-280.
[12]Bulusu B,Heidemann J,Estrin D.Density adaptive algorithms for beacon placement in wireless sensor networks.In:IEEE ICDCS'01,Phoenix,AZ.April 2001.
[13]T.He,C.Huang,B.M.Blum,J.A.Stankovic,and T.Abdelzaher.Range-free localization schemes for large scale sensor networks.In Proc.9th Ann.Intl.Conf.on Mobile Computing and Networking,pages 81-95.ACM Press,2003.
[14]Nagpal R. Organizing a global coordinate system from local information on an amorphous computer. AI Memo 1666, MIT AI Laboratory, August 1999.
[15]Radhika Nagpal, Howard Shrobe, Jonathan Bachrach. Organizing a global coordinate system from local information on an Ad Hoc Sensor Network. In: 2nd Int'l Workshop on Information Processing in Sensor Networks (IPSN'03), Palo Alto, April 2003.
[16]P.Bahl, V.N.Padmanabhan. RADAR: an in-building RF-based user location and tracking system. In: IEEE INFOCOM, 2000: 2, 775-784.
[17] Hightower J, BorielloG, Want R. SpotON: An indoor 3D location sensing technology based on RF signal strength. Technical Report UW CSE 2000-02-02, Seattle: Department of Computer Science and Engineering, University of Washington, 2000.
[18] Jeffrey Hightower. SpotON: Ad hoc Location Sensing using Radio Signal Strength. Feb. 2001.
[19]K. Whitehouse. The design of calamari: an ad-hoc localization system for sensor networks. Master's thesis, University of California at Berkeley, 2002.
[20]A. Savvides, C. C. Han, M. B. Srivastava, "Dynamic Fine-Grained Localization in Ad-Hoc Wireless Sensor Networks", in the proceedings ofthe International Conference on Mobile Computing andNetworking (MobiCom) 2001, Rome, Italy, July 2001 (also NESL technical reportTM-UCLA-NESL-2001-01-01, January 2001).
[21] A. Savvides, H. Park and M. B. Srivastava, "The N-Hop MultilaterationPrimitive for Node Localization Problems", to appear in MONET Special Issue on Sensor Networks and Applications, June 2003.
[22] Want R, Hopper A, FalcaoV, Gibbons J. The active badge location system. ACM Trans, on Information Systems, 10(1), 1992: 91-102.
[23]Harter A, Hopper A. A distributed location system for the active office. IEEE Network, 8(1)1994:62-70.
[24] SonghwaiOh, Phoebus Chen, Michael Manzo, and ShankarSastry, "InstrumentingWireless Sensor Networks for Real-time Surveillance," in Proc. of the International Conference on Robotics and Automation(ICRA),Orlando,FL,May 2006.
[25]李明峰,冯宝红,刘三枝.GPS定位技术及其应用.北京:国防工业出版社,2006:1,63-85
[26]王雪.无线传感器网络测量系统.北京:机械工业出版社,2007:327-360
[27]詹姆士.普雷斯.贝叶斯统计学-原理、模型及应用.北京:中国统计出版社,1992:23-69
[28]Najar M,Vidal J.Kalman tracking based on TDOA for UMTS mobile location,12th IEEE International Symposium on Personal,Indoor and Mobile Radio Communications,1(30),2001:B -45 - B-49.
[29]L.Cong,W.Zhuang," TDOA/AOA mobile user location for wide band CDMA cellular systems",IEEE Transactions on Wireless Communications,vol.1,no.3,2002:439-447.
[30]Thomas N.J,Cruickshank D.G.M,Laurenson D.I.A robust location estimator architecture with biased Kalman filtering of TOA data for wireless systems,IEEE Sixth International Symposium on Spread Spectrum Techniques and Applications,2000:296-300.
[31]Najar M,Vidal J,Kjellstrom A.Kalman tracking for UMTS mobile location IST Mobile Summit 2001,Sitges,Spain,September,9- 12,2001
[32]Najar M.,Vidal J,Kalman tracking for mobile location in NLOS situations,14th IEEE Proceedings on Personal,Indoor and Mobile Radio Communications,2003:2203-2207.
[33]Gordon N,Salmond D.Novel approach to non-linear and non-Gaussian Bayesian state estimation[J].Proc.of Institute Electric Engineering,140(2),1993:107-113
[34]Doucet A,Gordon N.Sequential Monte Carlo Methods in Practice[M].New York:Springer-Verlag,2001.
[35]http://en.wikipedia.org/wiki/Particle_filter
[36]吉洪诺夫,阿尔先宁.不适定问题的解法.北京:地质出版社,979:5-7,34-37.
[37]王彦飞.反演问题的计算方法及其应用.北京:高等教育出版社,2007:76-77
[38]肖庭延,于慎根,王彦飞。反问题的数值解法.北京:科学出版社,2003:120-126.
[39]康行健.天线原理与设计.北京:北京理工大学出版社,1993:1-50,287-320.
[40]Warren L.Stutzman,Gary A.Thiele.天线理论与设计.北京:人民邮电出版社,2006:1-46,197-203.
[41]范平志,邓平,刘林.蜂窝网无线定位.北京:电子工业出版社,2002:1-50.
[2]任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003.7,Vol,14(N o2):1148-1157
[3]汪炀.无线传感器网络定位技术研究.中国科学技术大学博士论文,2007:1-20.
[4]李晓维.无线传感器网络技术.北京:北京理工大学出版社,2007:191-219.
[5]Holger Karl,Andreas Willig.无线传感器网络协议与体系结构.北京:电子工业出版社,2007:198-214.
[6]J.Hightower,G.Borriello.Location systems for ubiquitous computing.IEEE Computer,2001,34(8):57-66.
[7]J.Hightower,G.Borriello.A survey and taxonomy of location systems for ubiquitous computing.Technical Report UW-CSE 2001-08-03,U.of Washington,Computer Science and Engineering,Seattle,WA,2001.
[8]Theodore S.Rappaport.Wireless communications principles and practice.Publishing House of Electronics Industry,2004:69-138.
[9]Niculescu D,Nath B.Ad hoc positioning system(APS) using AOA.In:Proc 22~(nd) Annual Joint Conf of the IEEE Computer and Communications Societies (INFOCOM'2003).IEEE,Vol.3,2003.
[10]D.Niculescu,B.Nath.Ad hoc Positioning System(APS).Proceedings of IEEE Globecom 2001:2886-2931.
[11]D.Niculescu,B.Nath.DV-based Positioning in Ad Hoc Networks.Kluwer Journal of Telecommunication Systems,Vol.22,No.1,2003:267-280.
[12]Bulusu B,Heidemann J,Estrin D.Density adaptive algorithms for beacon placement in wireless sensor networks.In:IEEE ICDCS'01,Phoenix,AZ.April 2001.
[13]T.He,C.Huang,B.M.Blum,J.A.Stankovic,and T.Abdelzaher.Range-free localization schemes for large scale sensor networks.In Proc.9th Ann.Intl.Conf.on Mobile Computing and Networking,pages 81-95.ACM Press,2003.
[14]Nagpal R. Organizing a global coordinate system from local information on an amorphous computer. AI Memo 1666, MIT AI Laboratory, August 1999.
[15]Radhika Nagpal, Howard Shrobe, Jonathan Bachrach. Organizing a global coordinate system from local information on an Ad Hoc Sensor Network. In: 2nd Int'l Workshop on Information Processing in Sensor Networks (IPSN'03), Palo Alto, April 2003.
[16]P.Bahl, V.N.Padmanabhan. RADAR: an in-building RF-based user location and tracking system. In: IEEE INFOCOM, 2000: 2, 775-784.
[17] Hightower J, BorielloG, Want R. SpotON: An indoor 3D location sensing technology based on RF signal strength. Technical Report UW CSE 2000-02-02, Seattle: Department of Computer Science and Engineering, University of Washington, 2000.
[18] Jeffrey Hightower. SpotON: Ad hoc Location Sensing using Radio Signal Strength. Feb. 2001.
[19]K. Whitehouse. The design of calamari: an ad-hoc localization system for sensor networks. Master's thesis, University of California at Berkeley, 2002.
[20]A. Savvides, C. C. Han, M. B. Srivastava, "Dynamic Fine-Grained Localization in Ad-Hoc Wireless Sensor Networks", in the proceedings ofthe International Conference on Mobile Computing andNetworking (MobiCom) 2001, Rome, Italy, July 2001 (also NESL technical reportTM-UCLA-NESL-2001-01-01, January 2001).
[21] A. Savvides, H. Park and M. B. Srivastava, "The N-Hop MultilaterationPrimitive for Node Localization Problems", to appear in MONET Special Issue on Sensor Networks and Applications, June 2003.
[22] Want R, Hopper A, FalcaoV, Gibbons J. The active badge location system. ACM Trans, on Information Systems, 10(1), 1992: 91-102.
[23]Harter A, Hopper A. A distributed location system for the active office. IEEE Network, 8(1)1994:62-70.
[24] SonghwaiOh, Phoebus Chen, Michael Manzo, and ShankarSastry, "InstrumentingWireless Sensor Networks for Real-time Surveillance," in Proc. of the International Conference on Robotics and Automation(ICRA),Orlando,FL,May 2006.
[25]李明峰,冯宝红,刘三枝.GPS定位技术及其应用.北京:国防工业出版社,2006:1,63-85
[26]王雪.无线传感器网络测量系统.北京:机械工业出版社,2007:327-360
[27]詹姆士.普雷斯.贝叶斯统计学-原理、模型及应用.北京:中国统计出版社,1992:23-69
[28]Najar M,Vidal J.Kalman tracking based on TDOA for UMTS mobile location,12th IEEE International Symposium on Personal,Indoor and Mobile Radio Communications,1(30),2001:B -45 - B-49.
[29]L.Cong,W.Zhuang," TDOA/AOA mobile user location for wide band CDMA cellular systems",IEEE Transactions on Wireless Communications,vol.1,no.3,2002:439-447.
[30]Thomas N.J,Cruickshank D.G.M,Laurenson D.I.A robust location estimator architecture with biased Kalman filtering of TOA data for wireless systems,IEEE Sixth International Symposium on Spread Spectrum Techniques and Applications,2000:296-300.
[31]Najar M,Vidal J,Kjellstrom A.Kalman tracking for UMTS mobile location IST Mobile Summit 2001,Sitges,Spain,September,9- 12,2001
[32]Najar M.,Vidal J,Kalman tracking for mobile location in NLOS situations,14th IEEE Proceedings on Personal,Indoor and Mobile Radio Communications,2003:2203-2207.
[33]Gordon N,Salmond D.Novel approach to non-linear and non-Gaussian Bayesian state estimation[J].Proc.of Institute Electric Engineering,140(2),1993:107-113
[34]Doucet A,Gordon N.Sequential Monte Carlo Methods in Practice[M].New York:Springer-Verlag,2001.
[35]http://en.wikipedia.org/wiki/Particle_filter
[36]吉洪诺夫,阿尔先宁.不适定问题的解法.北京:地质出版社,979:5-7,34-37.
[37]王彦飞.反演问题的计算方法及其应用.北京:高等教育出版社,2007:76-77
[38]肖庭延,于慎根,王彦飞。反问题的数值解法.北京:科学出版社,2003:120-126.
[39]康行健.天线原理与设计.北京:北京理工大学出版社,1993:1-50,287-320.
[40]Warren L.Stutzman,Gary A.Thiele.天线理论与设计.北京:人民邮电出版社,2006:1-46,197-203.
[41]范平志,邓平,刘林.蜂窝网无线定位.北京:电子工业出版社,2002:1-50.