分布式无线传感器网络定位算法MDS-MAP(D).doc

第6期马震等：分布式无线传感器网络定位算法MDS-MAP(D)63分布式无线传感器网络定位算法MDS-MAP(D)马震，刘云，沈波（北京交通大学 通信与信息系统北京市重点实验室，北京 100044）摘 要：针对无线传感器网络的定位问题，提出了一种分布式的算法MDS-MAP(D)，明确给出了节点相对坐标计算和局部网络融合的过程，并对算法进行了计算复杂性分析和仿真。MDS-MAP(D)以分布式节点分簇为基础，利用网络的连接关系，在不需要高精度测距技术支持的条件下对节点坐标进行估计，减小了节点定位的计算复杂度和能量消耗。分析与仿真结果表明，算法的计算复杂度由下降到，并且定位精度提高了1%3%。关键词：无线传感器网络；定位；多维标度；分布式中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)06-0057-06Distributed locating algorithm for wireless sensor networks- MDS-MAP(D)MA Zhen, LIU Yun, SHEN Bo(Key Laboratory of Communication & Information Systems, Beijing Jiaotong University, Beijing Municipal Commission of Education, Beijing 100044, China)Abstract: A new distributed locating algorithm MDS-MAP(D) was proposed, which attempted to improve the performance of node localization in wireless sensor networks. The process of the computation about node relative coordinates and the aggregation from local network to global network are introduced explicitly. Further, the analyses to computational complexity and the simulations of the algorithm are also present. MDS-MAP(D), which is based on node clustering mechanism and uses connectivity of nodes to estimate the coordinates of nodes, reduces the complexity and energy consumption of node localization on the absence of distance measurement with high precision. The simulation and analysis results indicate that the complexity of node localization algorithm falls to from and the accuracy is improved 1%3%.Key words: wireless networks; location; multidimensional scaling; distribution1 引言收稿日期：2008-02-18；修回日期：2008-05-06基金项目：国家自然科学基金资助项目(60572035)Foundation Item: The National Natural Science Foundation of China (60572035)无线传感器网络(WSN, wireless sensor network)技术在最近几年得到了迅速发展，正逐渐被广泛用于军事、交通、环境和工业生产等领域，完成对温度、湿度、压力和速度等许多物理量的测量1。对于大多数被测物理量来说，人们不但需要掌握物理量的准确测量数值，还需要知道所测量物理量产生的区域或地理位置。然而WSN中的传感器节点一般都是批量部署的，如空中播撒等，并且各个节点都具有完全相同的结构和功能，无法对每一个节点进行单独的标识。因此，要获得测量值的位置信息，传感器节点必须能够明确自身的位置2,3。了解传感器节点的位置信息还可以提高WSN的路由效率、覆盖质量，实现网络的负载均衡和拓扑自配置等2。如何获得节点位置信息的问题称为传感器节点的定位问题25。目前这一问题已成为WSN领域中人们关注的热点问题之一212。本文针对WSN的传感器节点定位问题，提出了一种新的分布式节点定位方法，并给出了节点分簇算法和具体的局部网络融合成整体网络的算法。本文提出的方法有以下特点：1)使用节点连接关系计算节点位置，不需要高精度的测距方法支持；2)不需要全部节点都进行局部网络内的最短路径计算和节点坐标计算；3)降低了所构建的局部网络的数量，减小了融合局部网络的计算复杂度和能量消耗，并且定位精度有所提高；4)明确给出了融合局部网络的方法。2 相关工作对节点进行定位的最直接方法是给节点提供GPS定位功能，但使用GPS定位，节点的费用会增加2个数量级2。因此GPS定位功能通常只用在WSN中的锚节点(anchor node)上，以便计算出各个节点的绝对位置信息。当前，根据测量方式的不同，主要的传感器节点定位方法可分为Range-Based方法和Range-Free方法两大类25。Range-Based方法使用RSSI10、TDOA11和AOA12等测距技术，获得节点间的距离或角度等信息，再利用三角关系计算或估计节点的位置。Range-Free方法通过测量节点间的连接关系，获得网络连通性信息，进而计算节点的位置。综述文献25对相关方法做了全面的介绍和分析。Range-Based方法受到测距技术的限制，存在许多问题，如RSSI产生的测量误差较大，可达50%；TDOA需要节点具有超声波发送与接收功能；AOA容易受到环境影响，功耗较大等。因此，目前Range-Free方法受到更多的关注2，其中基于数学心理学的数据分析技术-多维定标(MDS, multidimensional scaling)13技术的系列方法69是能够工作在Range-Free环境下的一类有效的节点定位方法。MDS-MAP6是最早被提出的基于古典MDS的集中式定位算法，可以同时在Range-Based和Range-Free环境下计算节点位置信息，并且在Range-Based环境下能够达到很高的精度。但由于采用了集中式计算的模式，MDS-MAP需要网络中存在能够进行高强度计算的节点，并且当WSN覆盖区域不规则时，会产生很大误差。改进的MDS-MAP方法7构建了一种分布式的计算模式，降低了对节点计算能力的要求，但仍是一种基于Classical MDS的方法，在Range-Free环境下的计算精度不高。为此文献8提出了一种基于Ordinal MDS的分布式节点定位方法，提高了Range-Free环境下的节点定位精度。但该方法仍需要各个节点在自身的2跳邻居组成的局部网络中进行最短路径计算，并都要运行Ordinal MDS算法，计算复杂度高，节点能量消耗大。3 分布式定位算法MDS-MAP(D)针对上述问题，下面给出一种新的基于Ordinal MDS的分布式WSN节点定位方法，称为MDS-MAP(D)。与其他基于MDS的方法相比，该方法只需要每个局部网络的簇头中计算局部网络内各节点间的最短路径，进而计算节点坐标，降低了局部网络中的计算复杂度，同时也减少了局部网络的数量，进而减小了融合局部网络的计算复杂度和能量消耗。3.1 算法描述考虑一组传感器节点工作在一个二维平面上，节点按随机均匀的方式部署，且足够密集；节点间的最大通信半径为。在网络的初始化阶段，各个节点首先以半径广播探寻消息，消息中包含一个节点标识ID和一个跳数字段hop，并令hop=1。收到探寻消息的节点首先判断消息的hop是否为1。如果hop=1，节点把消息中的ID和hop存储到自己的邻居列表中令hop加1，并以半径转发；如果hop=2，节点对消息中的ID和hop进行存储，并丢弃该消息。这样，通过发送和接收探寻消息，每个节点就在自己的邻居列表中缓存了距离自己小于2跳距离的邻居节点，称为2跳邻居。设表示节点的邻居节点集合，且中也包含该节点。在定位过程中，节点执行MDS-MAP(D)算法，步骤如下：1) 节点首先执行分簇算法，每一个簇称为一个局部网络，其中仅包含簇头及其2跳邻居，过程见3.2节。成为簇头的节点运行Dijkstra算法，获得局部网络的最短路径序列 ；2) 各簇头节点使用Ordinal MDS算法计算局部网络中节点的相对坐标，算法见3.3节；3) 由某一簇头节点(见3.2节)执行融合算法，见3.4节，得到整个网络中各节点的相对坐标；4) 由执行融合的簇头节点利用锚点坐标计算整个网络中各节点的绝对坐标。3.2 分簇过程分簇过程中，每个节点按照以下过程决定自己是否成为簇头。设节点ID为i：1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 19) 20) 21) 22) 23) 24) 25) 26)27)28) 29) 30) 31) 32) 每个节点首先随机选择2个等待时间和，清空自己的所属簇头列表，并启动两个定时器(14行)；在定时器1结束时，如果没有收到邻居列表中的节点发出的竞争消息，节点广播一个竞争消息，消息中包含竞争消息标识、节点标识ID和跳数字段hop，并令hop=1(59行)。当收到一个消息，节点首先判断发送消息的节点是否在自己的邻居列表中，节点只对邻居节点发送的消息做出处理(11行)。如果收到的消息的类型是，并且定时器1还未超时，节点取消定时器1(1216行)；如果收到的消息类型是节点取消定时器2(1719行)；接着判断发送该消息的源节点是否已在所属簇头列表中，如果不在，把源节点加入列表，并判断hop的值，如果小于2，令hop加1，转发该竞争消息(2026行)。当定时器2超时，节点判断自己属于几个簇。如果只属于一个簇，并且据簇头的距离是2，节点广播再次竞争消息(2731行)。再次竞争的方法保证了簇之间有充分的重叠，以便增加融合算法的精度。分簇结束后，同时属于多个簇的节点起到了簇头间的连接作用。使用与上述分簇过程相同的机制，簇头间可以指派一个簇头来执行融合算法，其他簇头只需提供自己2跳邻居节点坐标。3.3 局部网络节点定位考虑局部网络l，由3.1节步骤1得到的最短路径序列为，其中。设。Ordinal MDS算法如下13：1) 设定中各节点的初始坐标为任意值，即，其中表示节点在中的行向量。2) 计算每一对节点间的距离(1)3) 用PAV算法和计算与对应的差异值。4) 求Stress1(2)如果，算法结束，即为局部网络l的节点坐标集合，否则执行5)。5) 根据下式计算各节点的新坐标(3)其中，为步长因子，为的节点个数。6) 更新，即令，转到2)。3.4 融合算法与绝对坐标设为两个局部网络，如果包含3个以上的节点，使用下式的变换把中的节点坐标变换到r的坐标系统中去(4)其中，s为缩放因子，为旋转变换，为平移变换。以下利用文献14中给出的方法分别求出s、和，从而把局部网络融合到中。设E为中的节点在中的坐标矩阵(每行一个节点)，其第i个行向量用表示；为中的节点在l中的坐标矩阵，为第个节点的行向量；D为中的节点在中的坐标矩阵。假设E与S中分别有个节点。首先将r与l中节点的坐标扩展到3维空间，并使第3维的坐标值全部为1。令r与l的中心点分别为(5)设，s由下式给出(6)E与S的协方差矩阵可表示为(7)其中，。由C计算矩阵U(8)计算U的最大特征值对应的特征向量则旋转变换矩阵可由下式计算(9)平移变换为(10)由式(4)、式(6)、式(9)、式(10)，就可以把D变换到r的坐标系中，如式(11)所示。(11)其中，I为与D具有相同行数的全1列矢量。当一个WSN中有3个以上的锚点时，用上述方法可以将WSN的相对坐标转换到锚点所在的绝对坐标系统中去。此外，融合后不再需要对节点的坐标进行优化调整。4 分析与仿真结果为了便于把本文提出的MDS-MAP(D)方法与 文献6,8中给出的基于MDS的定位方法比较，这里把工作在Range-Free环境下的基于Ordinal MDS的MDS-MAP称为MDS-MAP(O)6，把在此基础上的改进方法称为MDS-MAP(P,O,R)8。设具有个节点的WSN，可以分为个局部网络，平均每个局部网络中有个节点，2个重叠的局部网络的共同节点数为，差异节点数为。3.3节给出的局部网络节点定位方法中，一次迭代的步骤1)和6)的计算复杂度为，步骤2)5)的复杂度为。整个算法的多次迭代的计算复杂度为。3.4节给出的融合算法中，式(5)式(7)的复杂度为；式(8)和式(9)的复杂度为；求最大特征值的乘幂法计算时间为，这里U矩阵是固定的44矩阵，因此复杂度为；式(11)的复杂度为，由于，因此最坏情况下，一个局部网络融合到另一个的复杂度为。综合以上分析，MDS-MAP(D)方法的步骤1)(3.1节)的计算复杂度为；步骤2)的复杂度为；最坏情况下，步骤3)的复杂度为；步骤4)的复杂度为。由于MDS-MAP(D)把一个WSN分成多个局部网络，与MDS-MAP(O)和MDS-MAP(P,O,R)中每个节点都需要计算最短路径相比，计算复杂度由下降到了，这里m比N小很多。在局部网络融合方面，MDS-MAP(D)最坏情况下的计算复杂度为，优于MDS-MAP(P,O,R)的，其中为节点的平均邻居数量。本文结合GlomoSim和matlab对MDS-MAP(D)以及MDS-MAP(O)和MAP(P,O,R)进行了仿真。仿真区域为一个10m10m的矩形区域，随机均匀部署100个传感器节点。为比较通信障碍对算法的影响，还对C型网络进行了仿真。图1给出的是平均连接度为10时的矩形网络和C型网络的连接图。图1 仿真中的网络结构表1给出了不同的节点通信半径条件下，分簇算法对上述矩形网络进行局部网络划分的结果。从结果可知，分簇算法显著减少了局部网络的数量。令表示节点的直接邻居的平均数量，由分簇算法可知，在分簇阶段，最坏的情况下一个节点需要发送（包括转发）条消息。由文献8可知，在没有分簇机制的条件下，为完成局部网络融合，每个节点至少需要发送（包括转发）条包含局部网络信息的消息。分簇算法的通信能耗与不包含分簇机制的局部网络融合过程的通信能耗大体相当。但由上述对算法复杂性的讨论可知，分簇算法的引入降低了节点定位的计算复杂度，因而减少了定位计算的能耗。表1分簇算法的仿真结果通信半径/m2.02.42.63.03.43.8局部网络数765433图2所示为矩形网络中各算法的仿真结果。从结果可以看出，MDS-MAP(D)在网络连接度大于10时，定位误差下降较快，定位精度优于MDS-MAP(O)方法。此外，随着锚点数量的增加，MDS-MAP(D)比MDS-MAP(P,O,R)的定位精度有小幅度提高，约为1%3%。图3给出了C型网络上的仿真结果。结果显示网络中存在障碍时，MDS-MAP(D)的定位误差明显小于MDS-MAP(O)方法，在不同环境下的误差平均值与MDS-MAP(P,O,R)方法相当。图2 矩形网络中不同定位方法的比较图3 C形网络中不同定位方法的比较图4所示为算法对节点位置的估计，其中表示估计位置，线段指向节点的实际位置，表示锚点位置。从图中可以看出位置估计误差分布与锚点位置无关，这与文献8的结论一致。图4 算法对节点位置的估计5 结束语本文针对WSN节点的定位问题，提出了一种分布式的算法MDS-MAP(D)，并明确给出了局部网络融合的方法。该方法可以有效降低节点定位的计算复杂度，减少节点定位计算的能耗，能适应网络中障碍物的干扰，并提供较高的定位精度。致谢：感谢张振江老师参与讨论，并给出具有建设性的建议。特别向对本文提出宝贵意见和建议的审稿专家表示衷心感谢。参考文献：1任丰源, 黄海宁, 林闯. 无线传感器网络J. 软件学报, 2003, 14(7): 1282-1291.REN F Y, HUANG H N, LIN C. Wireless sensor networkJ. Journal of Software, 2003, l4(7): l282-l291.2MAO G, FIDAN B, ANDERSON B. Wireless sensor network localization techniquesJ. Computer Networks, 2007,51(10): 2529-2553.3王福豹, 史龙, 任丰原. 无线传感器网络中的自身定位系统和算法J. 软件学报, 2005,16(5): 857-868.WANG F B, SHI L, REN F Y. Self-Localization systems and algorithms for wireless sensor networksJ. Journal of Software, 2005, 16(5): 857-868.4BACHRACH J, TAYLOR C. Localization in Sensor Networks in Handbook of Sensor Networks: Algorithms and ArchitecturesM. USA: Wiley, 2005.5SAYED A, TARIGHAT A, KHAJEHNOURI N. Network-based wireless location: challenges faced in developing techniques for accurate wireless location informationJ. IEEE Signal Processing Magazine, 2005, 22(4): 24-40.6SHANG Y, RUML W, ZHANG Y, et al. Localization from mere connectivityA. Proc of ACM MobiHocC. Annapolis, MD, NY, 2003. 201-212.7SHANG Y, RUML W, ZHANG Y. Improved MDS-based localizationA. Proc of IEEE InfocomC. Hong Kong, China, 2004. 2640-2651.8VIVEKANANDAN V, WONG V. Ordinal MDS-based localization for wireless sensor networksA. Vehicular Technology Conference (VTC-2006 Fall)C. Canada: VTC, 2006.1-5.9COSTA J, PATWARI N. Distributed weighted-multidimensional scaling for node localization in sensor networksJ. ACM Trans Sen. Netw. 2006,2(1):39-64.10GI