摘要
本文重点研究了基于时间测量的无线传感器网络定位算法,与其它定位算法相比,基于时间测量的定位算法定位精度高,虽然对硬件要求较高,但是随着技术的进步,硬件成本的降低,它们的应用势必越来越广泛。因此,对基于时间测量的定位算法进行研究意义重大。论文的主要工作如下：
1.在查阅大量相关文献的基础上,总结了无线传感器网络定位技术在国内外的研究现状,介绍了无线传感器网络定位算法的性能评价标准和分类方法,综述了近年来该领域代表性算法的原理和特点。
2.针对二阶Taylor级数展开法计算量过大的问题,给出了一种改进算法,该算法在计算量和定位成功率之间进行了折中,有效降低了算法的计算量。针对现有的TDOA算法需要参考节点之间时间同步,易受多径传播和噪声干扰等缺点,给出了一种改进算法,该算法消除了节点间时间同步的要求,提高了定位性能,具有较好的实用性。
3.分别推导了TOA、RT-TOA和TDOA定位误差的Cramer-Rao下界,并对TDOA的Cramer-Rao下界进行了修正,讨论了影响Cramer-Rao下界的因素。这对定位无偏估计子性能的评估具有重要意义。
4.研究了定位误差与参考节点布放方式的关系。通过对定位不确定区域的分析,构造出参考节点组成的拓扑结构内的平均定位误差函数,对平均定位误差函数的研究结果表明：当三个参考节点组成等边三角形时,定位性能最佳,这对定位参考节点的布放和选择具有较好的指导意义。
5.设计并实现了一种类似于RT-TOA的定位算法,该算法采用双向测距保证了测距的准确性,达到了提高定位精度的目的。室内和室外环境下的测试结果表明：系统具有良好的定位性能。
最后,论文对已经完成的工作进行了总结,并对以后的研究方向做出了展望。
This thesis focuses on time-measurement-based positioning algorithm, which compared with other positioning algorithm, has more accurate positioning accuracy. Higher though the hardware requirements are, with the advancement of technology, hardware costs will be reduced, time-measurement-based positioning algorithm must be applied more and more widely, therefore, it's significant for us to study it. Main tasks are as follows:
1. On the basis of reading a large amount of related articles, the research status quo of WSN positioning techniques at home and abroad is introduced. The criterions of performance evaluation and the classification methods for WSN positioning techniques are also discussed. The principles and characteristics of recent representative positioning approaches are summarized.
2. Aimed at the disadvantage that the calculation of two stage Taylor series expansion method is too large, a modified method is proposed, which makes a tradeoff between calculation and positioning success rate. Simulation confirms that the calculation is reduced obviously. Aimed at avoiding the drawbacks of current TDOA positioning algorithm, an improved method is proposed, in which the time synchronization is free. The improved method performs more accurate and possesses better practicability.
3. The Cramer-Rao bounds of TO A, RT-TOA and TDOA are deduced and the factors related to those bounds are discussed. Given the bounds properly is of great significance for unbiased estimator evaluation.
4. For the positioning error is related to the topology composed by anchor nodes, it is necessary to study the relationship between anchor nodes' deployment and positioning error. Based on the analysis of positioning fuzzy region, the function of average positioning error is constructed which is the emphasis of following discussion. The discussion achieves that when the topology shaped by anchor nodes is an equilateral triangle, the average positioning error is minimized. This criterion can work as a guide for the depolyment and choice of anchor nodes.
5. A positioning algorithm similar to RT-TOA has been realized on nanoLOC nodes. To achieve a high accuracy, ranging is taken at both sides, so that high location performance is guaranteed. Under indoor and outdoor environment, the system has been tested, result shows a good positioning performance.
Finally, the thesis summarizes all the completed work and gives out the prospect of future work.
引文
[1]Akyildiz. I. F, Weilian Su, Sankarasubramaniam. Y and Cayirci. E. A Survey on Sensor Networks[J]. IEEE Communication Magazine,2002,40(8):102-104.
[2]于宏毅,李鸥,张效义.无线传感器网络理论、技术与实现[M].北京：国防工业出版社,2008：6-7,258-261.
[3]孙利民,李建中等.无线传感器网络[M].北京：清华大学出版社,2005：7-8,136-140.
[4]Asis Nasipuri, Kai Li. A Directionality based Location Discovery Scheme for Wireless Sensor Networks[A]. In:Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications (WSNA'02). Location Discovery and Network Management [C]. New York:ACM,2002:105-111.
[5]J. Li, J. Jannotti, D. S. J. De Couto, D. R. Karger, and R. Morris. A scalable location service for geographic ad hoc routing [A]. In:Proceedings of ACM MOBICOM[C]. New York:ACM,2000:120-130.
[6]B. Karp and H. T. Kung. GPSR:Greedy perimeter stateless routing for wireless networks [A]. In:ACM/IEEE International Conference on Mobile Computing and Networking[C]. New York:ACM,2002:243-254.
[7]S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad hoc sensor networks[A]. In:Proceedings of INFOCOM[C]. New York:IEEE Press,2001:1380-1387.
[8]J. Heidemann. Using geospatial information in sensor networks[A]. In:ACM/IEEE International Conference on Mobile Computing and Networking[C]. New York:ACM, 2000:1-5.
[9]H.Gupta, Zhou Zongheng, S. R. Das, Q. Gu. Connected Sensor Cover:Self-Organization of Sensor Networks for Efficient Query Execution[J]. IEEE/ACM Transactions on Networking,2006,14(1):55-67.
[10]S. Meguerdichian, F. Koushanfar, M. Potkonjak, M. B. Srivastava. Coverage Problems in Wireless Ad-hoc Sensor Networks[A]. In:Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2001). Proceedings of IEEE[C]. Alaska,2001:1380-1387.
[11]N. Bulusu, J. Heidemann, D. Estrin. GPS-less Low Cost Outdoor Localization for very Small Devices[J]. IEEE Personal Communications,2000,7(5):28-34.
[12]P. Bahl, V. N. Padmanabhan. RADAR:An in-building RF-based user location and tracking sensor networks[A]. In:Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies[C]. Tel Aviv, Israel,2000:775-784.
[13]L. Doherty. Algorithms for Position and Data Recovery in Wireless Sensor Networks[D]. California:University of California Berkeley,2000.
[14]Girod L, Estrin D. Robust range estimation using acoustic and multimodal sensing[A]. In: Proceedings of the 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems[C]. Hawaii,2001:1312-1320.
[15]Nissanka B. Priyantha, Anit Chakraborty, Hari Balakrishnan. The cricket location-support system[A]. In:Proceedings of the 6th annual international conference on Moblie computing and networking. International Conference on Moblie Computing and Networking[C]. Boston, MA:ACM,2000:32-43.
[16]Savvides A, Han C C, Srivastava M B. Dynamic fine-grained location in ad-hoc networks of sensors[A]. In:Proceedings of the 7th annual international conference on Moblie computing and networking. International Conference on Moblie Computing and Networking[C]. Rome, Italy:ACM,2001:166-179.
[17]He T, Huang CD, Blum BM, Stankovic JA, Abdelzaher T. Range-Free localization schemes in large scale sensor networks[A]. In:Proceedings of the 9th annual international conference on Moblie computing and networking. International Conference on Moblie Computing and Networking[C]. San Diego, CA:ACM,2003:81-95.
[18]Dragos Niculescu, Badri Nath. Ad Hoc Positioning System (APS) using AOA[A]. In: Proceedings of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies[C]. San Francisco,2003:1734-1743.
[19]Nisanka B. Priyantha, Hari Balakrishnan, Erik Demaine, Seth Teller. Anchor-Free Distributed Localization in Sensor Networks[A]. In:Proceedings of the 1st international conference on Embedded networked sensor systems. Conference on Emedded Networked Sensor Systems[C]. Los Angeles:ACM,2003:340-341.
[20]A. Galstyan, B. Krishnamachari, K. Lerman, and S. Pattern. Distributed online localization in sensor networks using a moving target[A]. In:Proceedings of the third international symposium on Information processing in sensor networks[C]. ACM/IEEE IPSN'04, 2004:61-70.
[21]S. Datta, C. Klinowski, M. Rudafshani, S. Khaleque. Distributed localization in static and mobile sensor networks[A]. In:Proceedings of Wireless and Mobile Computing, Networking and Communications[C]. Montreal,2006:69-76.
[22]马祖长,孙怡宁.无线传感器网络节点的定位算法[J].计算机工程,2005,30(7)：13-14.
[23]赵军,裴庆祺,徐展琦.无线传感器网络近似三角形内点测试定位算法[J].计算机工程,2007,33(3)：109-111.
[24]王永才,赵千川,郑大钟.传感器网络自身定位算法的设计与实现[J].计算机工程与应用,2005,41(13)：4-6.
[25]孙学斌,周正.无线传感器网络中目标定位算法的研究[J].计算机工程与应用,2004,40(3)： 132-134.
[26]刘林,范平志.一种降低定位误差的无线传感器网络节点定位改进算法[J].电路与系统学报,2007,12(2),1-4.
[27]范平志,邓平,刘林.蜂窝网无线定位[M].北京电子工业出版社,2002：48-50,62.
[28]刘影,基于TDOA的无线传感器网络节点定位技术研究[D].吉林：吉林大学,2008.
[29]J. Jr. Caffery, G. L. Stuber. Subscriber Location in CDMA Cellular Networks[J]. IEEE Transactions on Vehicular Technology,1998,47(2):406-416.
[30]Pi Chun Chen. A non-line-of-sight error mitigation algorithm[A]. In:Proceedings of IEEE Wireless Communications and Networking Conference[C]. New Orleans, LA, USA:IEEE Computer and Communications Societies,1999:316-320.
[31]M. P. Wylie, J. Holtzman. The non-line-of-sight problem in mobile location estimation[A]. In:Proceedings of the 5th IEEE International Conference on Universal Personal Communications[C]. Cambridge, MA, USA:IEEE Communications Society,1996: 827-831.
[32]杨强.大规模无线传感器网络定位算法研究[D].上海：同济大学,2007.
[33]Laurence Mailaender. On the Geolocation Bounds for Round-Trip Time-of-Arrival and All Non-Line-of-Sight Channels[J]. EURASIP Journal on Advances in Signal Processing, 2007,2008:1-10.
[34]Y. T. Chan, K. C. Ho. A Simple and Efficient Estimator for Hyperbolic Location[J]. IEEE Transactions on Signal Processing,1994,42(8):1905-1915.
[35]W. H. Foy. Position Location Solutions by Taylor Series EstimationfJ]. IEEE Transactions on Aerospace and Electronic Systems,1976,12(2):187-194.
[36]Kegen Yu, Y. Jay Guo and Ian Oppermann. Modified Taylor Series Expansion Based Positioning Algorithms[A]. IEEE vehicular technology conference[C]. Marina Bay, Singapore,2008:2656-2660.
[37]Chen Hongyang, Deng Ping, Xu Yongjun, Li Xiaowei. A Robust Location Algorithm with Biased Extended Kalman Filtering of TDOA Data for Wireless Sensor Networks[A]. In: IEEE International Conference on Wireless Communications, Networking and Mobile Computing[C]. Wuhan China,2005:883-886.
[38]Xiao Jun, Ren Lirong, Tan Jindong. Research of TDOA Based Self-localization Approach in Wireless Sensor Network[A]. In:Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and System[C]. Beijing, China:IEEE Robotics and Automation Society,2006:2035-2040.
[39]张贤达.现代信号处理[M].北京：清华大学出版社,2002：42-45.
[40]邱天爽,唐洪等译.无线传感器网络协议与体系结构[M].北京：电子工业出版社,2006：212-213.
[41]韩光洁.普适计算中定位服务的参考点选择问题[D].辽宁：东北大学,2004.
[42]孙佩刚,赵海等.普适计算中定位服务的参考点布置与选择算法[J].电子学报,2006,8(8)：1456-1463.
[43]盛骤,谢式千,潘承毅.概率论与数理统计[M].北京：高等教育出版社,2001：60.
[44]黄廷祝.线性代数与空间解析几何[M],北京：高等教育出版社,2003.
[45]吴光磊.解析几何简明教程[M].北京：高等教育出版社,2003.
[46]施妙根,顾丽珍.科学和工程计算基础[M].北京：清华大学出版社,1999：277-278.