无线传感网络节点定位算法的研究
|
摘要
无线传感网络由大量带有无线通讯功能的微型传感设备组成。近年来,出现了众多的基于无线传感网络的应用系统。因为大多数无线传感网络应用系统需要传感器节点的位置信息,定位已经成为无线传感网络中的一个重要问题。目前,已经开发出多种确实有效的面向无线传感网络应用的定位系统和定位算法。以上所有这些无线传感网络节点的定位系统和定位算法面临的关键问题依然是如何在特定的部署场景中关于节点定位的效率和精度的问题。本文在现有的无线传感网络定位系统和定位算法研究的基础上,结合考虑干扰或非干扰的模式,考虑在三种典型的应用场景下定位算法。这三种典型的应用场景分别是移动信标辅助和连接性观察条件下的非测距定位场景,高密度锚节点辅助和连接性观察条件下的非测距监控场景以及二阶锥形规划辅助条件下的测距定位场景。
在第一种场景下,第二章提出了一种非测距,分布式和概率性的MBL定位算法,以及它的更新版本A-MBL定位算法,提高了MBL定位算法的精度和效率。在静态传感网络中,MSL和ADO定位算法都采用单一移动信标辅助的定位策略时,MBL定位算法要优于MSL和ADO这两种定位算法。
第三章给出理论分析与实验评估,以解释为何采用某个特定的动态模型以提高预测阶段的效率。然后,给出了未知节点是否使用来自邻居节点的观察以提高定位精度的条件。最后,为移动信标定位算法提出了一种自适应的机制。
第四章提出一种在静态无线传感网络中分布式的具有特定轨迹的移动信标辅助的,基于接收信号强度和连接性观察的MRC定位算法。接着,提出了改进的MRC Centroid定位算法,以考虑在噪声环境下不规则的无线传输场景。第四章中提出的轻量级的MRC算法具有有限的计算和存储开销,更加适合于低计算能力的,只能够执行基本的算术操作的传感器节点。
在第二种场景下,第五章提出了一个通过压缩采样的非测距定位方法RF-CS,该算法在较高的锚节点密度部署的条件下,定位稀疏的未知节点时具有更高精度,其扩展的方法RF-CS*可以在定位稠密的未知节点中表现良好。评估结果显示,该方法不论未知节点密度的稀疏还是稠密的情形下,利用较为稠密的信标节点,提高未知节点的精度达50%-80%。
在第三种场景下,第六章提出了一种高效的二阶锥形规划公式化,通过最小化辅助变量的数量,在解决传感网络定位问题中,以减少舒尔补矩阵稀疏部分的大小。相比在先前文献中提出的具有更大的稀疏模式的舒尔补矩阵的二阶锥形规划松弛的方法,该章中提出的二阶锥形规划公式化能够被更快的执行。同时,数值评估显示,该章中提出的二阶锥形规划松弛方法在不失定位精度的情况下提高了计算的效率。
Wireless Sensor Networks (WSNs) are composed of large numbers of tiny sensor devices with wireless communication capabilities. WSN systems have been developed recently for numerous applications. Because many of them require sensor position information, localization has been an important problem in WSNs and several localization systems and algorithms have been proposed in the past. The key issues are how to improve the efficiency and precision of sensor node localization problem in the particular deployment scenario. Considered the ideal and irregular radio pattern, this thesis discusses some localization approaches in three different scenarios. These three typical application scenarios are range-free localization scenario under mobile-beacon and connectivity assisted, range-free localization scenario under higher dense beacons and connectivity assisted, and range-based localization scenario under Second-Order Cone Programming (SOCP) assisted.
In the first scenario, Section 2 proposes a range-free, distributed and probabilistic Mobile Beacon-assisted Localization (MBL) approach, and its update version Adapting MBL (A-MBL), to increase the efficiency and accuracy of MBL. Evaluation results show that the accuracy of MBL and A-MBL outperform both Mobile and Static sensor network Localization (MSL) and Arrival and Departure Overlap (ADO) when both of them use only a single mobile beacon for localization in static WSNs.
Section 3 gives the theoretical analysis and experimental evaluations to suggest which probability distribution in the dynamic model should be adopted to improve the efficiency in the prediction stage. Section 3 also gives the condition for whether the unknown node should use the observations from its neighbors to improve the accuracy. Finally, Section 3 proposes a Self-Adapting Mobile Beacon-assisted Localization (SA-MBL) approach to achieve more flexibility and achieve almost the same performance with A-MBL.
Section 4 proposes a distributed Mobile beacon-assisted localization scheme based on RSS and Connectivity observations (MRC) with a specific trajectory. Section 4 proposes two improved approaches based on MRC to consider irregular radio scenario in the noisy environment. Compared the performance with three typical range-free localization methods in static WSNs, our lightweight MRC algorithm with limited computation and storage overhead is more suitable for very low-computing power sensor nodes
In the second scenario, Section 5 proposes a Range-Free localization via Compressive Sampling (RF-CS). Section 5 shows that the RF-CS scheme performs better than previous classical range-free localization algorithms when locating sparse unknown nodes with higher dense beacons random deployed in sensor networks. In addition, Section 5 proposes an expansion method, called RF-CS* which is workable in locating dense unknown nodes. On the whole, the approaches improve the accuracy of nearly 50%-80% with higher beacons regardless of unknown node density.
In the third scenario, Section 6 proposes an efficient SOCP formulation by minimizing the number of auxiliary variable to reduce the size of spare part of Schur complement matrix in solving sensor network localization problem. Compared to the previous SOCP relaxation with larger Schur complement matrix of sparse pattern, the SOCP formulation proposed in Section 6 can be solved faster after the splitting. Also, this SOCP relaxation increases computational efficiency without losing accuracy.
在第一种场景下,第二章提出了一种非测距,分布式和概率性的MBL定位算法,以及它的更新版本A-MBL定位算法,提高了MBL定位算法的精度和效率。在静态传感网络中,MSL和ADO定位算法都采用单一移动信标辅助的定位策略时,MBL定位算法要优于MSL和ADO这两种定位算法。
第三章给出理论分析与实验评估,以解释为何采用某个特定的动态模型以提高预测阶段的效率。然后,给出了未知节点是否使用来自邻居节点的观察以提高定位精度的条件。最后,为移动信标定位算法提出了一种自适应的机制。
第四章提出一种在静态无线传感网络中分布式的具有特定轨迹的移动信标辅助的,基于接收信号强度和连接性观察的MRC定位算法。接着,提出了改进的MRC Centroid定位算法,以考虑在噪声环境下不规则的无线传输场景。第四章中提出的轻量级的MRC算法具有有限的计算和存储开销,更加适合于低计算能力的,只能够执行基本的算术操作的传感器节点。
在第二种场景下,第五章提出了一个通过压缩采样的非测距定位方法RF-CS,该算法在较高的锚节点密度部署的条件下,定位稀疏的未知节点时具有更高精度,其扩展的方法RF-CS*可以在定位稠密的未知节点中表现良好。评估结果显示,该方法不论未知节点密度的稀疏还是稠密的情形下,利用较为稠密的信标节点,提高未知节点的精度达50%-80%。
在第三种场景下,第六章提出了一种高效的二阶锥形规划公式化,通过最小化辅助变量的数量,在解决传感网络定位问题中,以减少舒尔补矩阵稀疏部分的大小。相比在先前文献中提出的具有更大的稀疏模式的舒尔补矩阵的二阶锥形规划松弛的方法,该章中提出的二阶锥形规划公式化能够被更快的执行。同时,数值评估显示,该章中提出的二阶锥形规划松弛方法在不失定位精度的情况下提高了计算的效率。
Wireless Sensor Networks (WSNs) are composed of large numbers of tiny sensor devices with wireless communication capabilities. WSN systems have been developed recently for numerous applications. Because many of them require sensor position information, localization has been an important problem in WSNs and several localization systems and algorithms have been proposed in the past. The key issues are how to improve the efficiency and precision of sensor node localization problem in the particular deployment scenario. Considered the ideal and irregular radio pattern, this thesis discusses some localization approaches in three different scenarios. These three typical application scenarios are range-free localization scenario under mobile-beacon and connectivity assisted, range-free localization scenario under higher dense beacons and connectivity assisted, and range-based localization scenario under Second-Order Cone Programming (SOCP) assisted.
In the first scenario, Section 2 proposes a range-free, distributed and probabilistic Mobile Beacon-assisted Localization (MBL) approach, and its update version Adapting MBL (A-MBL), to increase the efficiency and accuracy of MBL. Evaluation results show that the accuracy of MBL and A-MBL outperform both Mobile and Static sensor network Localization (MSL) and Arrival and Departure Overlap (ADO) when both of them use only a single mobile beacon for localization in static WSNs.
Section 3 gives the theoretical analysis and experimental evaluations to suggest which probability distribution in the dynamic model should be adopted to improve the efficiency in the prediction stage. Section 3 also gives the condition for whether the unknown node should use the observations from its neighbors to improve the accuracy. Finally, Section 3 proposes a Self-Adapting Mobile Beacon-assisted Localization (SA-MBL) approach to achieve more flexibility and achieve almost the same performance with A-MBL.
Section 4 proposes a distributed Mobile beacon-assisted localization scheme based on RSS and Connectivity observations (MRC) with a specific trajectory. Section 4 proposes two improved approaches based on MRC to consider irregular radio scenario in the noisy environment. Compared the performance with three typical range-free localization methods in static WSNs, our lightweight MRC algorithm with limited computation and storage overhead is more suitable for very low-computing power sensor nodes
In the second scenario, Section 5 proposes a Range-Free localization via Compressive Sampling (RF-CS). Section 5 shows that the RF-CS scheme performs better than previous classical range-free localization algorithms when locating sparse unknown nodes with higher dense beacons random deployed in sensor networks. In addition, Section 5 proposes an expansion method, called RF-CS* which is workable in locating dense unknown nodes. On the whole, the approaches improve the accuracy of nearly 50%-80% with higher beacons regardless of unknown node density.
In the third scenario, Section 6 proposes an efficient SOCP formulation by minimizing the number of auxiliary variable to reduce the size of spare part of Schur complement matrix in solving sensor network localization problem. Compared to the previous SOCP relaxation with larger Schur complement matrix of sparse pattern, the SOCP formulation proposed in Section 6 can be solved faster after the splitting. Also, this SOCP relaxation increases computational efficiency without losing accuracy.
引文
[1]YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey [J]. COMPUT NETW,2008,52(12): 2292-2330.
[2]STOJMENOVIC I. Handbook of Sensor Networks:Algorithms and Architectures [M]. New Jersey:Wiley, 2005.
[3]ZHONG Z, HE T. Achieving Range-Free Localization Beyond Connectivity [C]//Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, November 4-6,2009, Berkeley, CA, USA:ACM,2009: 281-294.
[4]YOUNGMIN K, GUL A. Passive Localization:Large Size Sensor Network Localization Based on Environmental Events [C]//Proceedings of the 7th international conference on Information processing in sensor networks, April 22-24,2008, St. Louis, Missouri, USA:IEEE Computer Society,2008:3-14.
[5]RUDAFSHANI M, DATTA S. Localization in wireless sensor networks [C]//Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27,2007, Cambridge, Massachusetts, USA:ACM,2007:51-60.
[6]HUANG R, ZRUBA G V. Monte carlo localization of wireless sensor networks with a single mobile beacon [J]. Wirel Netw,2009,15(8):978-990.
[7]PENG R, SICHITIU M L. Robust, probabilistic, constraint-based localization for wireless sensor networks [C]//Proceedings of the 2nd Annual IEEE Sensor and Ad Hoc Communications and Networks, September, 26-29,2005, Santa Clara, California, USA:[s.n.],2005:541-550.
[8]SICHITIU M L, RAMADURAI V. Localization of Wireless Sensor Networks with a Mobile Beacon [C]// Proceedings of the First IEEE Conference on Mobile Ad-hoc and Sensor Systems, October 25-27,2004, Philadelphia, USA:[s.n.],2004:174-183.
[9]XIAO B, CHEN H, S. Z. A Walking Beacon-Assisted Localization in Wireless Sensor Networks [C]// Proceedings of the IEEE International Conference on Communications, June 24-28,2007, Glasgow, Scotland: [s.n.],2007:3070-3075.
[10]BEESON P, MURARKA A, KUIPERS B. Adapting proposal distributions for accurate, efficient mobile robot localization [C]//Proceedings of the In IEEE International Conference on Robotics and Automation, May 15-19,2006, Orlando, Florida, USA:[s.n.],2006:49-55.
[11]FOX D. Adapting the sample size in particle filters through KLD-sampling [J]. Int J Rob Res,2003,22(12): 985-1003.
[12]CEVHER V, DUARTE M F, BARANIUK R G. Distributed target localization via spatial sparsity [C]// Proceedings of the 16th European Signal Processing Conference, August 25-29,2008, Lausanne, Switzerland: EURASIP,2008:
[13]BULUSU N, HEIDEMANN J, ESTRIN D. GPS-less Low Cost Outdoor Localization For Very Small Devices [J]. IEEE PERS COMMUN,2000,7(5):28-34.
[14]NICULESCU D, B. N. DV Based Positioning in Ad Hoc Networks [J]. TELECOMMUN SYST,2003,22(1): 267-280.
[15]SHANG Y, RUML W. Improved MDS-based localization [C]//Proceedings of the 23th Annual Joint Conference of the IEEE Computer and Communications Societies, March 7-11,2004, Hong Kong, China: [s.n.],2004:2640-2651.
[16]SHI Q, HE C. A SDP Approach for Range-Free Localization in Wireless Sensor Networks [C]//Proceedings of the IEEE International Conference on Communication, May 19-23,2008, Beijing, China:[s.n.],2008: 4214-4218.
[17]F.STURM J. Using SeDuMi 1.02, A Matlab ToolBox for Optimization over Symmetric cones (Updated for Version 1.05) [J/OL] 2001, http://www.optim.ization-online.org/DB HTML/2001/10/395.html.
[18]TSENG P. Second-Order Cone Programming Relaxation of Sensor Network Localization [J]. SI AM Journal on Optimization 2007,18(1):156-185.
[19]KAZUHIRO; K, SUNYOUNG; K, MASAKAZU K. Sparse Second Order Cone Programming Formulations For Convex Optimization Problems [J]. Journal of the Operations Research Society of Japan 2008,51(3): 241-264.
[20]VOLGYESI P, BALOGH G, NADAS A, et al. Shooter localization and weapon classification with soldier-wearable networked sensors [C]//Proceedings of the 5th International Conference on Mobile Systems, Applications and Services, June 11-13,2007, San Juan, Puerto Rico:ACM,2007:113-126.
[21]MECHITOV K, SUNDRESH S, KWON Y, et al. Poster abstract:cooperative tracking with binarydetection sensor networks [C]//Proceedings of the In The 1st International ACM Conference on Embedded Networked Sensor Systems, November 5-7,2003, Los Angeles, California, USA:ACM,2003:332-333.
[22]WANG X, WANG S, MA J J. An improved particle filter for target tracking in sensor systems [J]. Sensors, 2007,7(1):144-156.
[23]SZEWCZYK R, MAINWARING A, POLASTRE J, et al. An analysis of a large scale habitat monitoring application [C]//Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, November 3-5,2004, Baltimore, MD, USA:ACM,2004:214-226.
[24]MECHITOV K, KIM W, AGHA G, et al. High-frequency distributed sensing for structure monitoring [J]. Trans of the Society of Instrument and Control Engineers (SICE),2006, E-S-1(1):109-114.
[25]KIM K,LEE W. MBAL:A Mobile Beacon-Assisted Localization Scheme for Wireless Sensor Networks [C]// Proceedings of the 16th International Conference on Computer Communications and Networks, August 13-16, 2007, Honolulu, Hawaii USA:[s.n.],2007:57-62.
[26]PRIYANTHA N B, BALAKRISHNAN H, DEMAINE E D, et al. Mobile-assisted localization in wireless sensor networks [C]//Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, March 13-17,2005, Miami, FL, USA:IEEE Computer and Communications Societies,2005:172-183.
[27]CABALLERO F, MERINO L, MAZA I, et al. A Particle Filtering method for Wireless Sensor Network Localization with an Aerial Robot Beacon [C]//Proceedings of the IEEE International Conference on Robotics and Automation, May 19-23,2008, Pasadena, CA, USA:[s.n.],2008:596-601.
[28]MARINAKIS D, MEGER D, REKLEITIS I, et al. Hybrid Inference for Sensor Network Localization using a Mobile Robot [C]//Proceedings of the 22nd AAAI Conference on Artificial Intelligence, July 22-26,2007, Vancouver, British Columbia, Canada:AAAI Press,2007:1089-1094.
[29]IHLER A T, FISHER J W, MOSES R L, et al. Nonparametric Belief Propagation for Self-Localization of Sensor Networks [J]. IEEE J Sel Area Comm,2005,23(4):809-819.
[30]MO L, YUNHAO L. Rendered path:range-free localization in anisotropic sensor networks with holes [C]// Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 9-14,2007, Montreal, Quebec, Canada:ACM,2007:51-62.
[31]STOLERU R, HE T, STANKOVIC J A. Walking GPS:A Practical Solution for Localization in Manually Deployed Wireless Sensor Networks [C]//Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks, Novermber 16-18,2004, Tampa, FL, USA:IEEE Computer Society,2004:480-489.
[32]COATES M. Distributed Particle Filters for Sensor Networks [C]//Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks, April 26-27,2004, Berkeley, CA, USA:ACM, 2004:99-107.
[33]HU L, EVANS D. Localization for mobile sensor networks [C]//Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 1,2004, Philadelphia, PA, USA: ACM,2004:45-57.
[34]ARULAMPALAM S, MASKELL S, GORDON N. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking [J]. IEEE Trans Signal Process,2002,50(2):174-188.
[35]KITAGAWA G. Monte carlo filter and smoother for non-gaussian nonlinear state space models [J]. J Comput Graph Stat,1996,5(1):1-25.
[36]TENG G, ZHENG K, DONG W. SDMA:A Simulation-Driven Dynamic Memory Allocator for Wireless Sensor Network [C]//Proceedings of the 2nd International Conference on Sensor Technologies and Applications, Auguest,25-31,2008, Cap Esterel, France:IEEE Computer Society Washington, DC, USA, 2008:462-467.
[37]FOX D, BURGARD W, DELLAERT F. Monte carlo localization:Efficient position estimation for mobile robots [C]//Proceedings of the 6th National Conference on Artificial Intelligence, July 18-22,1999, Orlando, Florida, USA:AAAI Press,1999:343-349.
[38]TENG G, ZHENG K, DONG W. A Survey of Available Tools for Developing Wireless Sensor Networks [C]// Proceedings of the 3rd International Conference on Systems and Networks Communications, October 26-31, 2008, Sliema:IEEE Computer Society,2008:139-144
[39]AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks [J]. IEEE Commun Mag,2002,40(8):102-114.
[40]HIGHTOWER J, BORRIELLO G. Location Systems for Ubiquitous Computing [J]. IEEE Computer,2001, 34(8):57-66.
[41]TENG G, ZHENG K, DONG W. Adapting mobile beacon-assisted localization in wireless sensor networks [J]. Sensors,2009,9(4):2760-2779.
[42]WOO A, TONG T, CULLER D. Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks [C]//Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, November 5-7,2003, Los Angeles, CA, USA:ACM,2003:14-27.
[43]TENG G, ZHENG K, DONG W. MA-MCL:Mobile-Assisted Monte Carlo Localization for Wireless Sensor Networks [C]//Proceedings of the 4th Int'l Symp on Innovations and Real-time Applications of Distributed Sensor Networks,2009, Hangzhou, China:[s.n.],2009:148-155.
[44]ROSS S M. Introduction to Probability Models [M]. Burlington, MA, USA:Academic Press,2006.
[45]NAGPAL R, SHROBE H, BACHRACH J. Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network [C]//Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks, April 22-23,2003, Palo Alto, CA, USA:Springer,2003:333-348.
[46]GUO Z, GUO Y, HONG F, et al. Perpendicular Intersection:Locating Wireless Sensors with Mobile Beacon [C]//Proceedings of the 29th IEEE Real-Time Systems Symposium, November 30-December 3,2008, Barcelona, Spain:IEEE Computer Society 2008:93-102.
[47]HOFMANN-WELLENHOF B, LICHTENEGGER H, COLLINS J. Global Positioning System:Theory and Practice [M].4th Rev. ed. Verlag Berlin, Heidelberg:Springer,1997.
[48]LANZISERA S, LIN D T, PISTER K S J. RF Time of Flight Ranging for Wireless Sensor Network Localization [C]//Proceedings of the International Workshop on Intelligent Solutions in Embedded Systems, June 30-30,2006, Vienna, Austria:IEEE,2006:1-12.
[49]PRIYANTHA N B, CHAKRABORTY A, BALAKRISHNAN H. The Cricket Location-Support System [C]// Proceedings of the 6th annual international conference on Mobile computing and networking, August 6-11, 2000, Boston, Massachusetts, USA:ACM,2000:32-43.
[50]SAVVIDES A, HAN C C, STRIVASTAVA M B. Dynamic Fine-grained Localization in Ad-hoc Networks of Sensors [C]//Proceedings of the 7th annual international conference on Mobile computing and networking, 2001, Rome, Italy:ACM,2001:166-179.
[51]CHENG X, THAELER A, XUE G, et al. TPS:A Time-Based Positioning Scheme for Outdoor Wireless Sensor Networks. [C]//Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, March 7-11,2004, Hong Kong, China:[s.n.],2004:2685-2696.
[52]NICULESCU D, NATH B. Ad Hoc Positioning System (APS) using AOA. [C]//Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications, March 30-April 3 2003, San Francisco, California,USA:[s.n.],2003:1734-1743.
[53]CHANG H, TIAN J, LAI T, et al. Spinning Beacons for Precise Indoor Localization [C]//Proceedings of the Proceedings of the 6th ACM conference on Embedded network sensor systems, November 5-7,2008, Raleigh, NC, USA:ACM,2008:127-140.
[54]BAHL P, PADMANABHAN. V N. RADAR:An In-Building RF-based User Location and Tracking System. [C]//Proceedings of the The Fourteenth Annual Joint Conference of the IEEE Computer and Communications Societies, March 26-30,2000, Tel Aviv, Israel:[s.n.],2000:775-784.
[55]COSTA J A, PATWARI N, ALFRED O. HERO I. Distributed Weighted-Multidimensional Scaling for Node Localization in Sensor Networks. [J]. ACM TRANS SENS NETW,2006,2(1):39-64.
[56]VARSHAVSKY A, LARA E D, HIGHTOWER J, et al. GSM Indoor Localization [J]. Pervasive and Mobile Computing,2007,3(6):698-720.
[57]YEDAVALLI K, KRISHNAMACHARI B. Sequence-Based Localization in Wireless Sensor Networks [J]. IEEE T MOBILE COMPUT,2008,7(1):81-94.
[58]ZHANG Y, ZHANG L, SHAN X. Ranking-Based Statistical Localization for Wireless Sensor Networks [C]// Proceedings of the Wireless Communications and Networking Conference, March 31-April 3 2008, Las Vegas, USA:[s.n.],2008:2561-2566.
[59]HE T, HUANG C, BLUM B M, et al. Range-free localization schemes for large scale sensor networks [C]// Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19,2003, San Diego, CA, USA:ACM,2003:81-95.
[60]R MER K. The Lighthouse Location System for Smart Dust. [C]//Proceedings of the 1st international conference on Mobile systems, applications and services May 5-8,2003, San Francisco, California, USA: ACM,2003:15-30.
[61]STOLERU R, HE T, STANKOVIC J A, et al. A High-accuracy, Low-cost Localization System for Wireless Sensor Networks. [C]//Proceedings of the The Proceedings of the 3rd international conference on Embedded networked sensor systems, November 2-4,2005, San Diego, California, USA:ACM,2005:13-26.
[62]GRANT M, BOYD S. CVX:Matlab Software for Disciplined Convex Programming [J/OL] 2009, http://www.stanford.edu/～bovd/cvx/.
[63]DONOHO D L. Compressed Sensing [J]. IEEE Trans on Information Theory,2006,52(4):1289-1306.
[64]CAND S E J. Compressive sampling [C]//Proceedings of the International Congress of Mathematicians,2008, Madrid, Spain:2008:1433-1452.
[65]CANDES E J, WAKIN M B. An Introduction To Compressive Sampling [J]. IEEE Signal Processing Magazine,2008,25(2):21-30.
[66]CEVHER V, BOUFOUNOS P T, BARANIUK R G, et al. Near-Optimal Bayesian Localization via Incoherence and Sparsity [C]//Proceedings of the The 8th ACM/IEEE International Conference on Information Processing in Sensor Networks, April 13-16,2009, San Francisco, USA:IEEE Computer Society, 2009:205-216.
[67]CHANDAR V. A negative result concerning explicit matrices with the restricted isometry property [J/OL] 2008, http://www.dsp.ece.rice.edu/cs/Venkat_CS.pdf.
[68]NOWAK W G. Lattice points in a circle and divisors in arithmetic progressions [J]. manuscripta mathematica, 1984,49(2):195-205.
[69]SESHAN S, H. T A, ZHI-QUAN L. Distributed Sensor Network Localization Using SOCP Relaxation [J]. IEEE transactions on wireless communications,2008,7(12):4886-4895.
[70]BISWAS P, LIAN T-C, WANG T-C, et al. Semidefinite programming based algorithms for sensor network localization.[J]. ACM Transactions on Sensor Networks 2006,2(2):188-220.
[71]SAXE J B. Embeddability of Weighted Graphs in k-Space is Strongly NP-Hard [C]//Proceedings of the 17th Allerton Conference in Communications, Control, and Computing,1979, Monticello, IL, USA:[s.n.],1979: 480-489.
[72]DOHERTY L, PISTER K S J. Convex position estimation in wireless sensor networks [C]//Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies, April 22-26 2001, Anchorage, Alaska, USA:[s.n.],2001:1655-1663.
[73]KIM S, KOJIMA M, WAKI H. Exploiting Sparsity in SDP Relaxation for Sensor Network Localization [J]. SIAM J Optim,2009,20(1):192-215.
[74]WANG Z, ZHENG S, BOYD S, et al. Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization [J]. SIAM Journal on Optimization,2008,19(2):655-673.
[75]BOYD S, VANDENBERGHE L. Convex Optimization [M]. Cambridge:Cambridge University Press,2009.
[76]GOLDFARB D, SCHEINBERG K. Product-form Cholesky factorization in interior point methods for second-order cone programming [J]. Mathematical Programming,2004,103(1):153-179.
[77]KOBAYASHI K, KIM S, KOJIMA1 M. Correlative Sparsity in Primal-Dual Interior-Point Methods for LP, SDP, and SOCP [J]. Applied Mathematics and Optimization,2007,58(1):69-88.
[2]STOJMENOVIC I. Handbook of Sensor Networks:Algorithms and Architectures [M]. New Jersey:Wiley, 2005.
[3]ZHONG Z, HE T. Achieving Range-Free Localization Beyond Connectivity [C]//Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, November 4-6,2009, Berkeley, CA, USA:ACM,2009: 281-294.
[4]YOUNGMIN K, GUL A. Passive Localization:Large Size Sensor Network Localization Based on Environmental Events [C]//Proceedings of the 7th international conference on Information processing in sensor networks, April 22-24,2008, St. Louis, Missouri, USA:IEEE Computer Society,2008:3-14.
[5]RUDAFSHANI M, DATTA S. Localization in wireless sensor networks [C]//Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27,2007, Cambridge, Massachusetts, USA:ACM,2007:51-60.
[6]HUANG R, ZRUBA G V. Monte carlo localization of wireless sensor networks with a single mobile beacon [J]. Wirel Netw,2009,15(8):978-990.
[7]PENG R, SICHITIU M L. Robust, probabilistic, constraint-based localization for wireless sensor networks [C]//Proceedings of the 2nd Annual IEEE Sensor and Ad Hoc Communications and Networks, September, 26-29,2005, Santa Clara, California, USA:[s.n.],2005:541-550.
[8]SICHITIU M L, RAMADURAI V. Localization of Wireless Sensor Networks with a Mobile Beacon [C]// Proceedings of the First IEEE Conference on Mobile Ad-hoc and Sensor Systems, October 25-27,2004, Philadelphia, USA:[s.n.],2004:174-183.
[9]XIAO B, CHEN H, S. Z. A Walking Beacon-Assisted Localization in Wireless Sensor Networks [C]// Proceedings of the IEEE International Conference on Communications, June 24-28,2007, Glasgow, Scotland: [s.n.],2007:3070-3075.
[10]BEESON P, MURARKA A, KUIPERS B. Adapting proposal distributions for accurate, efficient mobile robot localization [C]//Proceedings of the In IEEE International Conference on Robotics and Automation, May 15-19,2006, Orlando, Florida, USA:[s.n.],2006:49-55.
[11]FOX D. Adapting the sample size in particle filters through KLD-sampling [J]. Int J Rob Res,2003,22(12): 985-1003.
[12]CEVHER V, DUARTE M F, BARANIUK R G. Distributed target localization via spatial sparsity [C]// Proceedings of the 16th European Signal Processing Conference, August 25-29,2008, Lausanne, Switzerland: EURASIP,2008:
[13]BULUSU N, HEIDEMANN J, ESTRIN D. GPS-less Low Cost Outdoor Localization For Very Small Devices [J]. IEEE PERS COMMUN,2000,7(5):28-34.
[14]NICULESCU D, B. N. DV Based Positioning in Ad Hoc Networks [J]. TELECOMMUN SYST,2003,22(1): 267-280.
[15]SHANG Y, RUML W. Improved MDS-based localization [C]//Proceedings of the 23th Annual Joint Conference of the IEEE Computer and Communications Societies, March 7-11,2004, Hong Kong, China: [s.n.],2004:2640-2651.
[16]SHI Q, HE C. A SDP Approach for Range-Free Localization in Wireless Sensor Networks [C]//Proceedings of the IEEE International Conference on Communication, May 19-23,2008, Beijing, China:[s.n.],2008: 4214-4218.
[17]F.STURM J. Using SeDuMi 1.02, A Matlab ToolBox for Optimization over Symmetric cones (Updated for Version 1.05) [J/OL] 2001, http://www.optim.ization-online.org/DB HTML/2001/10/395.html.
[18]TSENG P. Second-Order Cone Programming Relaxation of Sensor Network Localization [J]. SI AM Journal on Optimization 2007,18(1):156-185.
[19]KAZUHIRO; K, SUNYOUNG; K, MASAKAZU K. Sparse Second Order Cone Programming Formulations For Convex Optimization Problems [J]. Journal of the Operations Research Society of Japan 2008,51(3): 241-264.
[20]VOLGYESI P, BALOGH G, NADAS A, et al. Shooter localization and weapon classification with soldier-wearable networked sensors [C]//Proceedings of the 5th International Conference on Mobile Systems, Applications and Services, June 11-13,2007, San Juan, Puerto Rico:ACM,2007:113-126.
[21]MECHITOV K, SUNDRESH S, KWON Y, et al. Poster abstract:cooperative tracking with binarydetection sensor networks [C]//Proceedings of the In The 1st International ACM Conference on Embedded Networked Sensor Systems, November 5-7,2003, Los Angeles, California, USA:ACM,2003:332-333.
[22]WANG X, WANG S, MA J J. An improved particle filter for target tracking in sensor systems [J]. Sensors, 2007,7(1):144-156.
[23]SZEWCZYK R, MAINWARING A, POLASTRE J, et al. An analysis of a large scale habitat monitoring application [C]//Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, November 3-5,2004, Baltimore, MD, USA:ACM,2004:214-226.
[24]MECHITOV K, KIM W, AGHA G, et al. High-frequency distributed sensing for structure monitoring [J]. Trans of the Society of Instrument and Control Engineers (SICE),2006, E-S-1(1):109-114.
[25]KIM K,LEE W. MBAL:A Mobile Beacon-Assisted Localization Scheme for Wireless Sensor Networks [C]// Proceedings of the 16th International Conference on Computer Communications and Networks, August 13-16, 2007, Honolulu, Hawaii USA:[s.n.],2007:57-62.
[26]PRIYANTHA N B, BALAKRISHNAN H, DEMAINE E D, et al. Mobile-assisted localization in wireless sensor networks [C]//Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, March 13-17,2005, Miami, FL, USA:IEEE Computer and Communications Societies,2005:172-183.
[27]CABALLERO F, MERINO L, MAZA I, et al. A Particle Filtering method for Wireless Sensor Network Localization with an Aerial Robot Beacon [C]//Proceedings of the IEEE International Conference on Robotics and Automation, May 19-23,2008, Pasadena, CA, USA:[s.n.],2008:596-601.
[28]MARINAKIS D, MEGER D, REKLEITIS I, et al. Hybrid Inference for Sensor Network Localization using a Mobile Robot [C]//Proceedings of the 22nd AAAI Conference on Artificial Intelligence, July 22-26,2007, Vancouver, British Columbia, Canada:AAAI Press,2007:1089-1094.
[29]IHLER A T, FISHER J W, MOSES R L, et al. Nonparametric Belief Propagation for Self-Localization of Sensor Networks [J]. IEEE J Sel Area Comm,2005,23(4):809-819.
[30]MO L, YUNHAO L. Rendered path:range-free localization in anisotropic sensor networks with holes [C]// Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 9-14,2007, Montreal, Quebec, Canada:ACM,2007:51-62.
[31]STOLERU R, HE T, STANKOVIC J A. Walking GPS:A Practical Solution for Localization in Manually Deployed Wireless Sensor Networks [C]//Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks, Novermber 16-18,2004, Tampa, FL, USA:IEEE Computer Society,2004:480-489.
[32]COATES M. Distributed Particle Filters for Sensor Networks [C]//Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks, April 26-27,2004, Berkeley, CA, USA:ACM, 2004:99-107.
[33]HU L, EVANS D. Localization for mobile sensor networks [C]//Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 1,2004, Philadelphia, PA, USA: ACM,2004:45-57.
[34]ARULAMPALAM S, MASKELL S, GORDON N. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking [J]. IEEE Trans Signal Process,2002,50(2):174-188.
[35]KITAGAWA G. Monte carlo filter and smoother for non-gaussian nonlinear state space models [J]. J Comput Graph Stat,1996,5(1):1-25.
[36]TENG G, ZHENG K, DONG W. SDMA:A Simulation-Driven Dynamic Memory Allocator for Wireless Sensor Network [C]//Proceedings of the 2nd International Conference on Sensor Technologies and Applications, Auguest,25-31,2008, Cap Esterel, France:IEEE Computer Society Washington, DC, USA, 2008:462-467.
[37]FOX D, BURGARD W, DELLAERT F. Monte carlo localization:Efficient position estimation for mobile robots [C]//Proceedings of the 6th National Conference on Artificial Intelligence, July 18-22,1999, Orlando, Florida, USA:AAAI Press,1999:343-349.
[38]TENG G, ZHENG K, DONG W. A Survey of Available Tools for Developing Wireless Sensor Networks [C]// Proceedings of the 3rd International Conference on Systems and Networks Communications, October 26-31, 2008, Sliema:IEEE Computer Society,2008:139-144
[39]AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks [J]. IEEE Commun Mag,2002,40(8):102-114.
[40]HIGHTOWER J, BORRIELLO G. Location Systems for Ubiquitous Computing [J]. IEEE Computer,2001, 34(8):57-66.
[41]TENG G, ZHENG K, DONG W. Adapting mobile beacon-assisted localization in wireless sensor networks [J]. Sensors,2009,9(4):2760-2779.
[42]WOO A, TONG T, CULLER D. Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks [C]//Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, November 5-7,2003, Los Angeles, CA, USA:ACM,2003:14-27.
[43]TENG G, ZHENG K, DONG W. MA-MCL:Mobile-Assisted Monte Carlo Localization for Wireless Sensor Networks [C]//Proceedings of the 4th Int'l Symp on Innovations and Real-time Applications of Distributed Sensor Networks,2009, Hangzhou, China:[s.n.],2009:148-155.
[44]ROSS S M. Introduction to Probability Models [M]. Burlington, MA, USA:Academic Press,2006.
[45]NAGPAL R, SHROBE H, BACHRACH J. Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network [C]//Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks, April 22-23,2003, Palo Alto, CA, USA:Springer,2003:333-348.
[46]GUO Z, GUO Y, HONG F, et al. Perpendicular Intersection:Locating Wireless Sensors with Mobile Beacon [C]//Proceedings of the 29th IEEE Real-Time Systems Symposium, November 30-December 3,2008, Barcelona, Spain:IEEE Computer Society 2008:93-102.
[47]HOFMANN-WELLENHOF B, LICHTENEGGER H, COLLINS J. Global Positioning System:Theory and Practice [M].4th Rev. ed. Verlag Berlin, Heidelberg:Springer,1997.
[48]LANZISERA S, LIN D T, PISTER K S J. RF Time of Flight Ranging for Wireless Sensor Network Localization [C]//Proceedings of the International Workshop on Intelligent Solutions in Embedded Systems, June 30-30,2006, Vienna, Austria:IEEE,2006:1-12.
[49]PRIYANTHA N B, CHAKRABORTY A, BALAKRISHNAN H. The Cricket Location-Support System [C]// Proceedings of the 6th annual international conference on Mobile computing and networking, August 6-11, 2000, Boston, Massachusetts, USA:ACM,2000:32-43.
[50]SAVVIDES A, HAN C C, STRIVASTAVA M B. Dynamic Fine-grained Localization in Ad-hoc Networks of Sensors [C]//Proceedings of the 7th annual international conference on Mobile computing and networking, 2001, Rome, Italy:ACM,2001:166-179.
[51]CHENG X, THAELER A, XUE G, et al. TPS:A Time-Based Positioning Scheme for Outdoor Wireless Sensor Networks. [C]//Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, March 7-11,2004, Hong Kong, China:[s.n.],2004:2685-2696.
[52]NICULESCU D, NATH B. Ad Hoc Positioning System (APS) using AOA. [C]//Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications, March 30-April 3 2003, San Francisco, California,USA:[s.n.],2003:1734-1743.
[53]CHANG H, TIAN J, LAI T, et al. Spinning Beacons for Precise Indoor Localization [C]//Proceedings of the Proceedings of the 6th ACM conference on Embedded network sensor systems, November 5-7,2008, Raleigh, NC, USA:ACM,2008:127-140.
[54]BAHL P, PADMANABHAN. V N. RADAR:An In-Building RF-based User Location and Tracking System. [C]//Proceedings of the The Fourteenth Annual Joint Conference of the IEEE Computer and Communications Societies, March 26-30,2000, Tel Aviv, Israel:[s.n.],2000:775-784.
[55]COSTA J A, PATWARI N, ALFRED O. HERO I. Distributed Weighted-Multidimensional Scaling for Node Localization in Sensor Networks. [J]. ACM TRANS SENS NETW,2006,2(1):39-64.
[56]VARSHAVSKY A, LARA E D, HIGHTOWER J, et al. GSM Indoor Localization [J]. Pervasive and Mobile Computing,2007,3(6):698-720.
[57]YEDAVALLI K, KRISHNAMACHARI B. Sequence-Based Localization in Wireless Sensor Networks [J]. IEEE T MOBILE COMPUT,2008,7(1):81-94.
[58]ZHANG Y, ZHANG L, SHAN X. Ranking-Based Statistical Localization for Wireless Sensor Networks [C]// Proceedings of the Wireless Communications and Networking Conference, March 31-April 3 2008, Las Vegas, USA:[s.n.],2008:2561-2566.
[59]HE T, HUANG C, BLUM B M, et al. Range-free localization schemes for large scale sensor networks [C]// Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19,2003, San Diego, CA, USA:ACM,2003:81-95.
[60]R MER K. The Lighthouse Location System for Smart Dust. [C]//Proceedings of the 1st international conference on Mobile systems, applications and services May 5-8,2003, San Francisco, California, USA: ACM,2003:15-30.
[61]STOLERU R, HE T, STANKOVIC J A, et al. A High-accuracy, Low-cost Localization System for Wireless Sensor Networks. [C]//Proceedings of the The Proceedings of the 3rd international conference on Embedded networked sensor systems, November 2-4,2005, San Diego, California, USA:ACM,2005:13-26.
[62]GRANT M, BOYD S. CVX:Matlab Software for Disciplined Convex Programming [J/OL] 2009, http://www.stanford.edu/～bovd/cvx/.
[63]DONOHO D L. Compressed Sensing [J]. IEEE Trans on Information Theory,2006,52(4):1289-1306.
[64]CAND S E J. Compressive sampling [C]//Proceedings of the International Congress of Mathematicians,2008, Madrid, Spain:2008:1433-1452.
[65]CANDES E J, WAKIN M B. An Introduction To Compressive Sampling [J]. IEEE Signal Processing Magazine,2008,25(2):21-30.
[66]CEVHER V, BOUFOUNOS P T, BARANIUK R G, et al. Near-Optimal Bayesian Localization via Incoherence and Sparsity [C]//Proceedings of the The 8th ACM/IEEE International Conference on Information Processing in Sensor Networks, April 13-16,2009, San Francisco, USA:IEEE Computer Society, 2009:205-216.
[67]CHANDAR V. A negative result concerning explicit matrices with the restricted isometry property [J/OL] 2008, http://www.dsp.ece.rice.edu/cs/Venkat_CS.pdf.
[68]NOWAK W G. Lattice points in a circle and divisors in arithmetic progressions [J]. manuscripta mathematica, 1984,49(2):195-205.
[69]SESHAN S, H. T A, ZHI-QUAN L. Distributed Sensor Network Localization Using SOCP Relaxation [J]. IEEE transactions on wireless communications,2008,7(12):4886-4895.
[70]BISWAS P, LIAN T-C, WANG T-C, et al. Semidefinite programming based algorithms for sensor network localization.[J]. ACM Transactions on Sensor Networks 2006,2(2):188-220.
[71]SAXE J B. Embeddability of Weighted Graphs in k-Space is Strongly NP-Hard [C]//Proceedings of the 17th Allerton Conference in Communications, Control, and Computing,1979, Monticello, IL, USA:[s.n.],1979: 480-489.
[72]DOHERTY L, PISTER K S J. Convex position estimation in wireless sensor networks [C]//Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies, April 22-26 2001, Anchorage, Alaska, USA:[s.n.],2001:1655-1663.
[73]KIM S, KOJIMA M, WAKI H. Exploiting Sparsity in SDP Relaxation for Sensor Network Localization [J]. SIAM J Optim,2009,20(1):192-215.
[74]WANG Z, ZHENG S, BOYD S, et al. Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization [J]. SIAM Journal on Optimization,2008,19(2):655-673.
[75]BOYD S, VANDENBERGHE L. Convex Optimization [M]. Cambridge:Cambridge University Press,2009.
[76]GOLDFARB D, SCHEINBERG K. Product-form Cholesky factorization in interior point methods for second-order cone programming [J]. Mathematical Programming,2004,103(1):153-179.
[77]KOBAYASHI K, KIM S, KOJIMA1 M. Correlative Sparsity in Primal-Dual Interior-Point Methods for LP, SDP, and SOCP [J]. Applied Mathematics and Optimization,2007,58(1):69-88.