无线传感器网络中分布式定位算法的研究与实现
|
摘要
许多无线传感器网络的协议和应用都需要知道网络中节点的地理位置。节点随机部署的传感器网络具有与ad-hoc网络类似的特点，其分布式和高自由度的网络环境对定位算法提出了很高的要求。由于能量，代价，或视野条件等因素，我们不可能为网络中的每个节点装配GPS设备。在这种情况下，如何依靠少量配有自定位设备的节点来确定全网中每个节点的位置就显得尤为重要。
无线传感器网络中定位有两个主要的挑战：锚节点稀疏和测距误差问题。利用冗余和超解方程组可减少测距值的误差对位置估值的影响，而通过节点间协作和在网络内反复传播信息的分布式算法则可以有效地解决锚节点稀疏问题。但是并没有一种方法能够同时解决这两个问题。为此，本文提出了一种分步定位算法：在算法建立阶段，通过计算到锚节点的扩展距离可以获得节点的初始位置估值；在求精阶段，利用相邻节点的位置信息来修正和约束位置估值，使之不断逼近真实值。同时，为了克服单纯求精算法的弊端，引入了信赖度量值和弱连接节点，进一步改善了求精过程。
论文主要分析对比了两种典型的分布式算法，为了保证算法的稳定性，选择了基于跳数的dv-hop算法作为建立阶段算法的基础，然后详细阐述了整个分步(建立和求精)算法的设计和具体实现过程，并从计算复杂度、能耗和时延等方面深入分析了分步算法的代价，并通过仿真测试验证了算法优异的稳定性和加入求精阶段后对精确度的提高。最后，文章进一步权衡了几种算法的利弊，讨论存在的问题，并指出将来可能的工作方向。
Many wireless sensor network protocols and applications assume the knowledge of geographic location of nodes. The absolute location of each networked node is an assumed fact by most sensor networks which can then present the sensed information on a geographical map. Finding location for all nodes in a network where only a limited fraction of nodes have self location capability is important since it is not practical to equip each node with GPS due to power, cost, form factor or line of sight condition. Wireless sensor networks, where the nodes are randomly deployed, resemble an ad-hoc network environment with high degrees of freedom and distributed composition, and thus pose significant challenges on positioning algorithms.
There are two major classes of problems that make positioning within an wireless sensor network challenging: the range error problem, and the sparse anchor node problem. We can answer the range error problem with redundancy and over-determined systems of equations. The distributed algorithm, which works through collaborations between nodes and iterative delivery of message across the network, provides a clean solution to the sparse anchor node problem. The difficulty, however, is that neither solution works in the presence of both problems, because redundancy calls for high density. To answer the orthogonality of these two separate and conflicting solutions, a two-stage algorithm is proposed. At the starting phase, we compute the extended ranges to the anchor node so as to derive the initial estimated position; at the refinement phase, the constraints imposed by the distances to the direct (one-hop) neighbors of a node will force the new position towards the true position after a number of refinement iterations. To overcome the two important limitations of the pure refinement algorithm, we introduce the concept of confidence metrics and ill-connected nodes to improve the refinement process.
First, the paper analyses and compares two typical distributed algorithms. To ensure the consistency of the algorithms, we developed a hop-based distributed positioning method for the starting phase based on the algorithm DV-hop. Then the paper explains in detail the design and implementation of the whole two-phase algorithm. Further, the paper also analyzes the cost for implementing the algorithm in terms of computation, power and time. Experimentation is then performed to verify the consistency and enhanced accuracy of the algorithms after introducing the refinement phase. In the end, we will discuss the algorithms on a more qualitative level, looking at the tradeoff between various algorithms, possible sources of error, and areas for improvement and future growth.
无线传感器网络中定位有两个主要的挑战：锚节点稀疏和测距误差问题。利用冗余和超解方程组可减少测距值的误差对位置估值的影响，而通过节点间协作和在网络内反复传播信息的分布式算法则可以有效地解决锚节点稀疏问题。但是并没有一种方法能够同时解决这两个问题。为此，本文提出了一种分步定位算法：在算法建立阶段，通过计算到锚节点的扩展距离可以获得节点的初始位置估值；在求精阶段，利用相邻节点的位置信息来修正和约束位置估值，使之不断逼近真实值。同时，为了克服单纯求精算法的弊端，引入了信赖度量值和弱连接节点，进一步改善了求精过程。
论文主要分析对比了两种典型的分布式算法，为了保证算法的稳定性，选择了基于跳数的dv-hop算法作为建立阶段算法的基础，然后详细阐述了整个分步(建立和求精)算法的设计和具体实现过程，并从计算复杂度、能耗和时延等方面深入分析了分步算法的代价，并通过仿真测试验证了算法优异的稳定性和加入求精阶段后对精确度的提高。最后，文章进一步权衡了几种算法的利弊，讨论存在的问题，并指出将来可能的工作方向。
Many wireless sensor network protocols and applications assume the knowledge of geographic location of nodes. The absolute location of each networked node is an assumed fact by most sensor networks which can then present the sensed information on a geographical map. Finding location for all nodes in a network where only a limited fraction of nodes have self location capability is important since it is not practical to equip each node with GPS due to power, cost, form factor or line of sight condition. Wireless sensor networks, where the nodes are randomly deployed, resemble an ad-hoc network environment with high degrees of freedom and distributed composition, and thus pose significant challenges on positioning algorithms.
There are two major classes of problems that make positioning within an wireless sensor network challenging: the range error problem, and the sparse anchor node problem. We can answer the range error problem with redundancy and over-determined systems of equations. The distributed algorithm, which works through collaborations between nodes and iterative delivery of message across the network, provides a clean solution to the sparse anchor node problem. The difficulty, however, is that neither solution works in the presence of both problems, because redundancy calls for high density. To answer the orthogonality of these two separate and conflicting solutions, a two-stage algorithm is proposed. At the starting phase, we compute the extended ranges to the anchor node so as to derive the initial estimated position; at the refinement phase, the constraints imposed by the distances to the direct (one-hop) neighbors of a node will force the new position towards the true position after a number of refinement iterations. To overcome the two important limitations of the pure refinement algorithm, we introduce the concept of confidence metrics and ill-connected nodes to improve the refinement process.
First, the paper analyses and compares two typical distributed algorithms. To ensure the consistency of the algorithms, we developed a hop-based distributed positioning method for the starting phase based on the algorithm DV-hop. Then the paper explains in detail the design and implementation of the whole two-phase algorithm. Further, the paper also analyzes the cost for implementing the algorithm in terms of computation, power and time. Experimentation is then performed to verify the consistency and enhanced accuracy of the algorithms after introducing the refinement phase. In the end, we will discuss the algorithms on a more qualitative level, looking at the tradeoff between various algorithms, possible sources of error, and areas for improvement and future growth.
引文
[1] Ren FY, Huang HN, Lin C. Wireless sensor networks. Journal of Software, 2003,14(2):1148-1157(in Chinese with English abstract).
[2] Rabacy JJ, Ammer MJ, da Silva Jr. JL, Patel D, Roundy S. Picorodio supports ad hoc ultra-low power wireless networking. Computer, 2000,33(7):42-48
[3] Beutel J. Geolocation in a PicoRadio environment [MS. Thesis]. Berkeley: UC Berkeley, 1999.
[4] Harter A, Hopper A, Steggles P, Ward A, Webster P. The anatomy of a context-aware application. In: Proc, of the 5th Annual ACM/IEEE Int'l Conf. on Mobile Computing and Networking. Seattle: ACM Press, 1999. 59-68.
[5] Chang J-H, Tassiulas L. Energy conserving routing in wireless ad-hoc networking. In: Proc, of the IEEE INFOCOM 2000. Tel Aviv: IEEE Computer and Communications Societies, 2000,1:22-31.
[6] Xu Y, Heidemann J, Estrin D. Geography-Informed energy conservation for ad hoc routing. In: Proc, of the 7th Annual Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 70-84.
[7] Hightower J, Boriello G Location systems for ubiquitous computing. Computer, 2001,34(8):5766.
[8] Harter A, Hopper A. A distributed location system for the active office. IEEE Network, 1994,8(1):6270.
[9] M.Satyanarayanan. Pervasive Computing:vison and challenges. IEEE Personal Communications, 2001
[10] Anind K.Dey, Masayasu Futakawa, Daniel Salber, Gregory D.Abowd. An architecture to support context-aware applications. Technical Report GIT-GVU-99-23, Georgia Institute of Technology, College of Computing, June 1999.
[11] J. Juang, On GPS Positioning and Integrity Monitoring. IEEE Transactions on Aerospace and Electronic Systems, Vol. 36, No. 1, January 2000.
[12] Beutel J. Geolocation in a PicoRadio environment [MS. Thesis]. Berkeley: UC Berkeley, 1999.
[13] G. Golub, Matrix Computations, 3rd Edition, The Johns Hopkins University Press,1996.
[14] Bulusu N, Heidemann J, Estrin D. GPS-Less low cost outdoor localization for very small devices. IEEE Personal Communications, 2000,7(5):2834.
[15] Doherty L, Pister KSJ, Ghaoui LE. Convex position estimation in wireless sensor networks. In: Proc, of the IEEE INFOCOM 2001. Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001. 1655-1663.
【16】 Nicolescu D, Nath B. Ad-Hoc positioning systems (APS). In: Proc. of the 2001 IEEE Global Telecommunications Conf. Vol. 5, San Antonio: IEEE Communications Society, 2001. 2926-2931.
【17】 Niculescu D, Nath B. DV based positioning in ad hoc networks. Journal of Telecommunication Systems, 2003, 22(1/4): 267-280.
【18】 Savvides A, Hart C-C, Srivastava MB. Dynamic fine-grained localization in ad-hoc networks of sensors. In: Proc. of the 7th Annual Int'l Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 166-179.
【19】 Avvides A, Park H, Srivastava MB. The bits and flops of the N-hop multilateration primitive for node localization problems. In: Proc. of the 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications. Atlanta: ACM Press, 2002. 112-121.
【20】 Savarese C, Rabay J, Langendoen K. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In: Ellis CS, ed. Proc. of the USENIX Technical Annual Conf. Monterey: USENIX Press, 2002. 317-327.
【21】 Savarese C, Rabaey JM, Beutel J. Locationing in distributed ad-hoc wireless sensor network. In: Proc. of the 2001 IEEE Int'l Conf. on Acoustics, Speech, and Signal. Vol. 4, Salt Lake: IEEE Signal Processing Society, 2001. 2037-2040.
【22】 Capkun S, Hamdi M, Hubaux J-P. GPS-Free positioning in mobile ad-hoc networks. Cluster Computing, 2002, 5(2): 157-167.
【23】 Lance Doherty. Algorithms for position and data recovery in wireless sensor networks, master's report, University of California, Berkeley, June, 2000.
【24】 A. Varga. The OMNeT++ Discrete Event Simulation System, in European Simulation Multiconference(ESM' 2001), Prague, Czech Republic, June 2001.
[2] Rabacy JJ, Ammer MJ, da Silva Jr. JL, Patel D, Roundy S. Picorodio supports ad hoc ultra-low power wireless networking. Computer, 2000,33(7):42-48
[3] Beutel J. Geolocation in a PicoRadio environment [MS. Thesis]. Berkeley: UC Berkeley, 1999.
[4] Harter A, Hopper A, Steggles P, Ward A, Webster P. The anatomy of a context-aware application. In: Proc, of the 5th Annual ACM/IEEE Int'l Conf. on Mobile Computing and Networking. Seattle: ACM Press, 1999. 59-68.
[5] Chang J-H, Tassiulas L. Energy conserving routing in wireless ad-hoc networking. In: Proc, of the IEEE INFOCOM 2000. Tel Aviv: IEEE Computer and Communications Societies, 2000,1:22-31.
[6] Xu Y, Heidemann J, Estrin D. Geography-Informed energy conservation for ad hoc routing. In: Proc, of the 7th Annual Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 70-84.
[7] Hightower J, Boriello G Location systems for ubiquitous computing. Computer, 2001,34(8):5766.
[8] Harter A, Hopper A. A distributed location system for the active office. IEEE Network, 1994,8(1):6270.
[9] M.Satyanarayanan. Pervasive Computing:vison and challenges. IEEE Personal Communications, 2001
[10] Anind K.Dey, Masayasu Futakawa, Daniel Salber, Gregory D.Abowd. An architecture to support context-aware applications. Technical Report GIT-GVU-99-23, Georgia Institute of Technology, College of Computing, June 1999.
[11] J. Juang, On GPS Positioning and Integrity Monitoring. IEEE Transactions on Aerospace and Electronic Systems, Vol. 36, No. 1, January 2000.
[12] Beutel J. Geolocation in a PicoRadio environment [MS. Thesis]. Berkeley: UC Berkeley, 1999.
[13] G. Golub, Matrix Computations, 3rd Edition, The Johns Hopkins University Press,1996.
[14] Bulusu N, Heidemann J, Estrin D. GPS-Less low cost outdoor localization for very small devices. IEEE Personal Communications, 2000,7(5):2834.
[15] Doherty L, Pister KSJ, Ghaoui LE. Convex position estimation in wireless sensor networks. In: Proc, of the IEEE INFOCOM 2001. Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001. 1655-1663.
【16】 Nicolescu D, Nath B. Ad-Hoc positioning systems (APS). In: Proc. of the 2001 IEEE Global Telecommunications Conf. Vol. 5, San Antonio: IEEE Communications Society, 2001. 2926-2931.
【17】 Niculescu D, Nath B. DV based positioning in ad hoc networks. Journal of Telecommunication Systems, 2003, 22(1/4): 267-280.
【18】 Savvides A, Hart C-C, Srivastava MB. Dynamic fine-grained localization in ad-hoc networks of sensors. In: Proc. of the 7th Annual Int'l Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 166-179.
【19】 Avvides A, Park H, Srivastava MB. The bits and flops of the N-hop multilateration primitive for node localization problems. In: Proc. of the 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications. Atlanta: ACM Press, 2002. 112-121.
【20】 Savarese C, Rabay J, Langendoen K. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In: Ellis CS, ed. Proc. of the USENIX Technical Annual Conf. Monterey: USENIX Press, 2002. 317-327.
【21】 Savarese C, Rabaey JM, Beutel J. Locationing in distributed ad-hoc wireless sensor network. In: Proc. of the 2001 IEEE Int'l Conf. on Acoustics, Speech, and Signal. Vol. 4, Salt Lake: IEEE Signal Processing Society, 2001. 2037-2040.
【22】 Capkun S, Hamdi M, Hubaux J-P. GPS-Free positioning in mobile ad-hoc networks. Cluster Computing, 2002, 5(2): 157-167.
【23】 Lance Doherty. Algorithms for position and data recovery in wireless sensor networks, master's report, University of California, Berkeley, June, 2000.
【24】 A. Varga. The OMNeT++ Discrete Event Simulation System, in European Simulation Multiconference(ESM' 2001), Prague, Czech Republic, June 2001.