59基于无线传感器网络的一种可扩 展的定位技术

1、基于无线传感器网络的一种可扩基于无线传感器网络的一种可扩 展的定位技术展的定位技术 scalable localization in wireless sensor networksmuralidhar medidi, roger a. slaaen, yuanyuan zhou, christopher j. mallery,and sirisha medidischool of electrical engineering and computer sciencewashington state universitypullman, wa 99164-2752logo摘要abstract：

2、localization, an important challenge in wireless sensor networks,is the process of sensor nodes self-determining their position. the diculty encountered is in cost-eectively providing acceptable accuracy in localization. the potential for the deployment of high density networks in the near future ma

3、kes scalability a critical issue in localization.in this paper we propose cluster-based localization , which provides eective localization suitable for large and highly-dense networks. cbl utilizes both a computationally-intensive localization technique( multidimensional scaling (mds) and a less int

4、ensivetrilateration to achieve balance between performance and cost. 定位作为无线传感器网络的重要技术挑战之一，它由传感器节点间的自我处理来定位的。它的难点就是要在低功耗的基础上实现准确定位，可扩展的高密度传感器网络的能耗调节是未来研究的重点。在本文中，我们提出了cluster-based localization (cbl)基于簇的定位方法，这种定位方法能够有效地应用于大规模且高密度的传感器网络。cbl综合利用了多边精确测算技术（如mds）和三边侧量技术两者的优点，来实现性能和功耗之间的平衡，它能通过扩展簇类来克服传感器网络

5、的局部故障。仿真结果显示，cbl减少了节点的计算量和通信量，但是节点的位置准确度却没减少。 logo本文的结构本文的结构 第一部分：引言。第二部分是讲目前无线传感器网络定位的相关技术与研究。第三部分主要介绍了本文提出的cbl定位技术的构造和特点。第四部分：对cbl的性能评估及与以往定位技术的比较。第五部分是本文的结论。 logo引言 无线传感器网络(wsn)因具有高的鲁棒性、准确性、灵活性及智能化等优点，被认为是未来恶劣战场环境中监控敌我双方兵力、装备和物资状态以及完成目标协同检测等关键应用技术之一，已得到国内外研究者的高度重视。随着无线传感器规模越来越大，传感器网络的密度能达到每平方米有几百

6、个节点，高密度的wsn中的节点位置需要可扩展的定位方法来实现。 logo引言v in this paper we propose a scalable hop-based localization technique called cluster-based localization (cbl). cbls use of clustering is motivated by the need for scalability and eciency. scalability is gained by, rst using an expensive but accurate localizatio

7、n technique on a small subset of the nodes in the，this work was supported in part by nsf grant network. the derived position estimates for the chosen subset will be used as referenceswhen localizing the remaining nodes. this approach leads to a signicant reduction in the computation required to loca

8、lize the entire network. 在本文中我们提出了一种基于跳数的可扩展的定位技术cbl。在cbl中，使用簇类可以使得整个网络可扩展且效率高。可扩展是指，首先在一小块区域的节点里使用一种能耗高但定位精确度高的技术来定位，接着其临近区域节点的位置就其已经定位好的节点来作参考以确定自己的位置，整个网络就是这样逐层逼近来定位的。logo2. 相关的定位技术相关的定位技术 这一部分主要是罗列了目前几种典型的无线传感器网络定位的相关技术。定位技术通常分为两大类：（1）基于测距的定位技术：通过测量邻居节点间的距离来确定节点的位置。（2）基于跳数的定位技术：无需用专门的测量设备来测得节点间的

9、距离，它认为节点间的距离近似等于其在最短传输路径上的跳数。 基于测距的定位技术有以下几种：gps全球定位系统、aps定位（一种分布式定位技术）、loran（long range navigation）是一种地区导航系统、rss方式定位系统（如radar定位系统利用指纹识别技术来进行定位，从而解决了定位移动计算设备的问题），使用toa/tdoa方式定位的系统（bat system和cricket）、混合定位系统（如calamari 和ahlos）。logo3. cbl定位技术定位技术 to localize all sensor nodes accurately, the localizatio

10、n process usually involves computationally-intensive procedures, e.g., mds that has o(n3) computational complexity .since sensor nodes are expected to be resource-constrained and networks to be large and dense, light-weight localization algorithms that achieve decent accuracy and high scalability ar

11、e desirable. therefore, we attempt to address the trade-os between accuracy and scalability, so as to make our localization algorithm, cbl, a practical solution for sensor network applications. 为了能准确定位整个传感器网络的节点，定位过程通常需要经过精密的计算。因为传感器节点希望被设计成资源消耗低且网络规模要求越来越大且密度也越来越高，所有具有高定准确度且高可扩展性的低负载的定位算法值得我们研究。因此，

12、我们设计了cbl算法，这种定位算法能有效应用于无线传感器网络中。 logo3. cbl定位技术定位技术 cbl adopts a hierarchical idea to perform the whole localization procedure,i.e., instead of regarding the whole network as a at topology in which all nodes share the same localization procedure as in most existing localization algorithms,we deliber

13、ately separate the nodes into two types, and apply dierent localization approaches on them to improve scalability as well as ensure accuracy. the rst type of nodes are representatives that account for a small portion of the nodes in the whole network. cbl采用了一种逐级定位的思想来实现整个网络的定位过程，以代替以往算法的所有节点都是同一定位过程

14、。我们把节点分成两类，并且运用不同的定位逼近法来改进这两类节点的可扩展性和准确性。第一种节点类型是代表一小块区域节点的簇头节点，簇头节点是被选取出来的能正确反映网络性能的节点，其定位采用复杂但准确的定位算法，这种定位算法能从根本上改进整个网络定位的准确性。除了簇头节点剩下来的节点就是另一种节点类型，这类大众节点以簇头节点为参考，采用低负载的定位过程。使用这些机制，cbl定位算法准确度相当好，且计算量少，通信量也少。 logo3.1 簇头选取簇头选取 因为簇头节点最先被定位并给剩余簇内节点做定位参考，所以它们必须是网络中性能好的节点。还有，簇头选取过程要低负载以确保整个网络的可扩展性。因此，cb

15、l算法中，我们应用了一种简单的单跳的小范围簇类算法来选取簇头。这种算法运用单跳确保了算法的低功耗，同时小范围性使每一个簇节点都能公平地被选取为簇头。 我们假设每一个节点都有一个唯一的id号，为了进行簇的分类，开始时每一个节点都同邻居节点进行通信以得到节点的单跳距离。接着，假定在邻居节点中其id号最大的节点中的任一节点为簇头，或者等待其比较完整个簇的节点来选取id号最大的那个节点为簇头。只要选取出了簇头节点，其将同邻居节点通信以建立自己的簇。 logo3.1 簇头选取簇头选取 图1.a描述了随机的无线传感器网络拓扑结构，节点间相互连接。图1.b表示簇类网络结构。图1.c表示了各簇群之间的网络连接

16、。 logo3.2 cluster head localization 簇头定位簇头定位 chs are taken as representatives and their localization accuracies have great impact on the overall localization accuracy. since chs usually account for a small portion of the whole network, it is aordable to apply complex localization algorithms to estim

17、ate chs positions. further, we want to apply a hop-based algorithm to localize chs so as to improve cbls applicability. 簇头能影响整个网络定位的准确度，因此，簇头通常是在一小块区域网络中使用复杂并精确的定位算法来确定簇头的节点位置。还有，我们想用一种基于单跳的定位算法来定位簇头节点以便能改进cbl算法的适用性。基于这些考虑，我们选择mds技术来定位簇头，因为基于单跳的mds定位算法mds-map被证明它的定位准确度非常高。cbl使用类似逼近算法的方法来定位簇头节点，然而在cb

18、l算法中，只有簇头定位才用到mds计算，因此计算量不是很大。 logo3.3 cluster member localization 簇成员定位簇成员定位 after determining each chs coordinates, we will take chs as reference nodes to estimate the remaining nodes, or cms, positions. we choose the least-square triangulation technique for cms localization to obtain decent accur

19、acy with low computation overhead. in particular, each ch rst calculates the euclidean distances to the chs in its neighboring clusters, then estimates the average hopdistance by using these euclidean distances and corresponding hop length. 当簇头节点的位置已经确定下来后，我们就能用簇头节点做为簇成员节点的参考定位点。我们采用最小二乘三边定位法来准确得到簇成

20、员节点的位置信息。特别要注意的，每一个簇头首先要计算出其与邻居簇头节点的几何距离，然后计算其单跳距离。接着，每一个簇头广播一个定位信息给它的簇内成员节点，这个定位信息包括个跳数（用来评价信息量和定位准确度之间的平衡关系），每一个簇类节点至少要接到三个不同簇头节点发来的定位信息才能通过三边定位法来确定自己的节点位置。如果一个簇内成员节点接收到超过三个簇头节点发来的定位信息的话，就使用最小方差法来定位。 logo4 performance evaluation 性能评价 cbl was implemented in ns-2 26, and our main goals when evaluati

21、ng its performance were to determine the accuracy, scalability, and how irregularities in a network topology will aect performance. the simulation environment parameters are: area = 100 100m2; 100 nodes; transmission range = 15m and cluster size varied from 1 to 10. 这里，我们主要对cbl定位算法的准确度、可扩展性和不规则的网络拓扑

22、结构将会怎样影响其定位效果这三项性能进行评估。仿真环境是：网络面积是100*100平方米、100个节点，节点发送信息的范围为15米、簇的大小从1到10不等。我们使用常见的以米制单位来衡量定位精确度。logo4.1 随机网络拓扑结构的性能随机网络拓扑结构的性能 图2描述了随机拓扑网络结构的定位准确度，图2.a是簇头的定位准确度，图b是整个网络节点定位的准确度。结果显示随着簇大小的增加，网络节点的定位准确度并没有明显的减少。logo4.2 基于簇类的网络结构基于簇类的网络结构 图3显示了，同随机拓扑网络一样，改变簇的大小对定位的准确性影响不大。另外，和mds-map相比，cbl的准确度稍微低点，但是其计算量少。同dv-hop相比，cbl在不规则的网络拓扑结构中定位准确度比其高。这就是为什么dv-hop通常只应用于均匀且规则的网络定位。logo4.3 节点密度不规则的网络节点密度不规则的网络 这里我们使用