摘要
在无线传感器网络的诸多应用领域里,需要对监测区域中的目标或所发生事件的区域进行定位,而节点自身的正确坐标信息是提供被监测目标位置信息的前提,并且无线传感器网络的某些路由机制和拓扑控制等也依赖于网络中传感器节点的位置信息。定位是无线传感器网络的重要支撑技术之一。随着无线传感器网络应用范围的扩大,传感器节点的布置不可避免的会出现非均匀分布状态,而一般的节点定位算法均基于均匀分布的网络进行分析。
本文首先分析了无线传感器网络中,非基于距离的节点自定位算法,其次介绍了传统DV-Hop算法的实现机理,分析了其应用于非均匀分布网络时,未知节点在计算到锚节点距离和计算锚节点平均跳距时的不足。最后在其理论基础之上,分别利用RBF神经网络和差分定位思想,修正锚节点的平均跳距,提出两种适用于非均匀分布的定位算法:RBF-DV-Hop算法和D-DV-Hop算法;利用加权平均的思想重新计算网络的平均每跳距离,并结合一定的消息转发策略提出了W-DV-Hop算法。为了验证算法性能,利用计算机仿真实现了原算法和改进算法。通过与DV-Hop算法以及Hop-count method算法进行比较,实验证明,在未增加节点的额外配置的情况下,改进算法有效地提高了节点在非均匀分布状态下的定位精度。
In wireless sensor networks where many applications will normally need to locate the target or events, while the coordinates of the node's own right to provide monitoring information is the premise of the event location information, and wireless sensor networks, some of the routing mechanism and topology control, also depends on the sensor nodes in the network location information. The localization is one of the important support technologies for wireless sensor networks.Along with the wireless sensor network application scope's expansion, the sensor node's arrangement inevitable will have the asymmetry distribution condition, but the general node localization algorithm will carry on the analysis based on uniform distribution's network.
First, this article main researched the Range-Free localization algorithms; Second, emphatically introduced the realized mechanism for the traditional DV-Hop algorithm, and has analyzed when it be applied in the asymmetry distributed networks, the anchor node calculates their average hop distance and the unknown nodes in calculating the distance to anchor node insufficiency;At last, above its rationale, separately used the radial direction base (RBF) neural network and the differential localization thought to revise the average hop distance and the distance between the unknown nodes and the anchor nodes, proposed two kinds of localization algorithms and they are suitable for the asymmetry distributed networks, which named: RBF-DV-Hop algorithm and D-DV-Hop algorithm; Used weighted average thought to recomputate the networks’average hop distance, and with some repeater strategy to propose the W-DV-Hop algorithm. In order to confirm the algorithms’performance, has realized the original algorithm and the improvement algorithms. Through algorithm carries on the comparison with the DV-Hop algorithm as well as Hop-count the method algorithm, the experiment proved that the improved algorithms without increased the nodes’extra disposition, and the improvement algorithms enhanced the positioning accuracy effectively under the asymmetry distribution networks.
引文
1任丰原,黄海宁,林闯.无线传感器网络.软件学报, 2003,14(2):1717-1727
2 LJ. Guibas Sensing, Tracking and Reasoning with Relations. IEEE Signal Processing Magazine, 2002,19(2):73-85
3 B Warneke, M Last, B Liebowitz, et al. Smart dust: Communicating with a Cubic- millimeter Computer. IEEE Computer, 2001,34(1):44-51
4 N Bulusu, J Heidemann, D Estrin. GPS-Less Low Cost outdoor Localization for very small Devices. IEEE Personal Communications, 2000,7(5):28-34
5 C Savarese, JM Rabaey, J Beutel. Locationing in Distributed Ad-Hoc Wireless Sensor Network. In: Proc. of the 2001 IEEE Int’l Conf. on Acoustics, Speech, and Signal. Salt Lake: IEEE Signal Processing Society, 2001,4:2037?2040
6崔莉,鞠海玲,苗勇,等.无线传感器网络研究进展.计算机研究与发展, 2005,42(l): 163-174
7孙利民,李建中,陈渝,等.无线传感器网络.北京:清华大学出版社, 2005:136-157
8 J Hightower, G Boriello. Location Systems for Ubiquitous Computing. Computer, 2001,34(8):57-66
9于海滨,曾鹏.分布式无线传感器网络协议研究.通信学报, 2004,25(10):102-110
10陈利虎.无线传感器网络实验平台的研究. [国防科技大学硕士论文], 2005:4-25
11马祖长,孙怡宁,梅涛.无线传感器网络综述.通信学报, 2004,25(4):114-124
12 A Harter, A Hopper. A Distributed Location System for the Active Office. IEEE Network, 1994,8(1):62-70
13 JJ Rabacy, MJ Ammer, D Patel, et al. Picorodio Supports Ad hoc Ultra-low Power Wireless Networking. Computer, 2000,33(7):42-48
14 T He, CD Huang, BM Blum, et al. Range-Free Localization Schemes in Large Scale Sensor Networks. In: Proc. of the 9th Annual Int’l Conf. on Mobile Computing andNetworking. San Diego: ACM Press, 2003:81-95
15 Alberto Cerpa, Deborah Estrin. Ascent: Adaptive Self-configuring Sensor Network Topologies. ACM SIGCOMM Computer Communication Review, 2002,32(1):62-66
16李建中,李金宝,石胜飞.传感器网络及其数据管理的概念问题与进展.软件学报, 2003,14(10):1717-1727
17 Yi Shang, R. Wheeler, Ying. Zhang. Localization from Mere Connectivity. In: Proceeding of the Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing. 2003: 201-212
18 Jan Blumenthal, Ralf Grossmann, Frank Golatowski, et al. Weighted Centroid Localization in Zigbee-based Sensor Networks. In IEEE International Symposium on Intelligent Signal Processing, WISP 2007, Madrid, October 2007:10-16
19 Azzdine Boukerch, HoraeioA.B. F.Olibera, Eduardo F. Nakamura, et al. Location systems for Wireless Sensor Networks,IEEE Wireless Communication, Dec. 2007,14:6-12
20 F. Benbadis, T. Friedman. GPS-Free Positioning System for Wireless Sensor Networks. In: IEEE International Conference on Wireless and Optical Communications Networks. 2005: 541-545
21 Z. Chaczko, R. Klempous, J. Nilodem. Methods of Sensors Localization in Wireless Sensor Networks. In:Proceedings of the International Symposium and Workshop on Engineering of Computer Based Systems, 2007: 145-152
22 K Langendoen, N Reijers. Distributed Localization in Wireless Sensor Networks: A Quantitative Comparison. The Int’l Journal of Computer and Telecommunications Networking, 2003,43(4):499-518
23 IF Akyildiz, W Su, Y Sankarasubramaniam, et al. A Survey on Sensor Networks. IEEE Communications Magazine, 2002,40(8):102-114
24 Ainwaring, J. Polastre, R. Szewczyk, et al. Wireless Sensor Networks for Habitat Monitoring. In: Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, 2002:88-97
25 P. Enge, P. Misra. Special Issue on GPS: The Global positioning System.Proc. of the IEEE January 1999:163-172
26 Tia Gao, Dan Greenspan, Matt Welsh. Vital Signs Monitoring and Patient Tracking Over a Wireless Network. In: Proceedings of the 27th IEEE EMBS Annual International Conference, September 2005:51-55
27 L Doherty, KSJ Pister, LE Ghaoui. Convex Position Estimation in Wireless Sensor Networks. In: Proc. of the IEEE INFOCOM 2001.Anchorage: IEEE Computer and Communications Societies, 2001,3:1655-1663
28 D Nicolescu, B Nath. Ad-Hoc positioning systems (APS). In: Proc. of the 2001 IEEE Global Telecommunications Conf. San Antonio: IEEE Communications Society, 2001,5:2926-2931
29嵇玮玮,刘中. DV-Hop定位算法在随机传感器网络中的应用研究.电子与信息学报, 2008,30 (4):970-974
30刘锋,张翰,杨骥.一种基于加权处理的无线传感器网络平均跳距离估计算法.电子与信息学报, 2008,30(5):1222-1226
31 Y. Shang, W Ruml. Improved MDS-based Localization. Proc. of the IEEE Infocom, Hong Kong, 2004: 264-2651
32马震,刘云,沈波.分布式无线传感器网络定位算法MDS-MAP(D).通信学报2008,29(6):57-62
33肖玲,李仁发,罗娟.基于非度量多维标度的无传感器网络节点定位算法.计算机研究与发展, 2007,44(3):399-405
34 M Hazas, A Ward. A novel Broadband Ultrasonic Location System. In: Borriello G, Holmquist LE, eds. Proc. of the 4th Int’l Conf. on Ubiquitous Computing. Goteborg: Springer-Verlag, 2002:264-280
35 J Hightower, G Boriello. Location Systems for Ubiquitous Computing. Computer, 2001,34(8):57-66
36 R Want, A Hopper, V Falcao, J Gibbons. The Active Badge Location System. ACM Trans. on Information Systems, 1992,10(1): 91?102
37王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法.软件学报,2005,16(5):857-868
38 A Harter, A Jones, A Hopper. A New Location Technique for the Active Office. IEEE Personal Communications, 1997,4(5):42-47
39 K. Lorincz .Sensor Networks for Emergency Response: Challenges and Opportunities, IEEE Pervasive Computing, IEEE Press, 2004:16-23
40 L Girod, V Bychovskiy, J Elson, et al. Locating Tiny Sensors in Time and Space: A Case Study. In: Werner B, ed. Proc. of the 2002 IEEE Int’l Conf. on Computer Design: VLSI in Computers and Processors. Freiburg: IEEE Computer Society, 2002:214-219
41陈维克,李文锋,首晰,等.基于RSSI的无线传感器网络加权质心定位算法.武汉理工大学学报(交通科学与工程版), 2006,30(2):265-268
42王珊珊,殷建平,蔡志平,等.基于RSSI的无线传感器网络节点自身定位算法.计算机研究与发展, 2008,S1:385-388
43 S Tilak, NB Abu-Ghazaleh, W Heinzelinan. A taxonomy of Wireless Micro-sensor network models. Mobile Computing and Communications Review, 2002,1(2):1-8
44 M.Guerriero, S. Marano, V. Matta, et al. Some aspects of DOA Estimation Using a Network of Blind Sensors. Elsevier B.V., 2008,88(11): 2640-2650
45李静,刘琚.用卡尔曼滤波器消除TOA中NLOS误差的三种方法.通信学报, 2005,26(1):130-141
46陈鸿龙,李鸿斌,王智.基于TDoA测距的传感器网络安全定位研究.通信学报, 2008,29(8):11-21
47 D Niculescu, B Nath. Ad hoc Positioning System (APS) using AoA. In: Proc. of the IEEE INFOCOM 2003. San Francisco: IEEE Computer and Communications Societies, 2003,3:1734-1743
48 S Capkun, M Hamdi, J-P Hubaux. GPS-Free Positioning in Mobile Ad-hoc Networks. Cluster Computing, 2002,5(2):157-167
49 R Iyengar, B Sikdar. Scalable and Distributed GPS Free Positioning for Sensor Networks. In: Proc. of IEEE Int’l Conf. on Communications 2003. Anchorage: IEEE Communications Society, 2003,1:338?342
50 A Savvides, C-C Han, MB Srivastava. Dynamic Fine-grained Localization in Ad-hocNetworks of Sensors. In: Proc. of the 7th Annual Int’l Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001,1:166-179
51 L Doherty. Algorithms for Position and Data Recovery in Wireless Sensor Networks. Berkeley: University of California, 2000,2:5-45
52 E Charles., Perkins, Elizabeth M. Ad hoc On Demand Distance Vector(AODV) Routing. IETF RFC 3561, 2003,2:10-21
53张晓龙,解慧英,赵小建.无线传感器网络中一种改进的DV-Hop定位算法.计算机应用, 2007,27:2672-2674
54 P Bahl, VN Padmanabhan. RADAR: an In-Building RF-Based User Location and Tracking System.Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2000,2:775-784
55 A. Cichocki , R. Unbehauen. Neural Networks for Optimization and Signal Processing. New York. Wiley, 1993:50-75
56 S. Amari. Mathematical Theory of Neural Learning. New Generation Computing. 1991,8:281-294
57 Jeff Hum. Differential GPS Explained: an Expose of the Surprisingly Simple Principles Behind Today’s Most Advanced Positioning Technology, Trade Trimble Navigation, Sunnyale, CA, 1993:147-168
58 Dmitri Perkins, Ranesh Tumati. Reducing Localization Errors in Sensor Ad hoc Networks. IEEE Int. Conf. on Performance, Computing, and Communications (IPCCC 2004). Phoenix, Arizona, 2004,1: 723-729