无线传感器网络节点定位算法研究概要

江苏大学硕士学位论文无线传感器网络节点定位算法研究姓名：王伟申请学位级别：硕士专业：计算机应用技术指导教师：鲍可进20100603江苏大学硕士学位论文摘要无线传感器网络集中了微机电技术、感知技术、嵌入式计算技术、分布式信息处理技术和无线通信技术，孕育出一种全新的信息获取和处理模式，能够广泛应用在国防军事、环境监测、医疗卫生、空间探索及反恐抗灾等许多领域，被认为是二十一世纪最重要的技术之一。而对于多数应用来说，没有位置标识的数据是没有意义的。所以定位技术已经成为无线传感器网络必不可少的关键技术之一，受到了国内外学者的广泛关注。现有的定位算法大致可以分为两类：基于测距的定位算法和非测距的定位算法，由于传感器节点能量、成本以及体积等因素的限制，非测距的定位算法具有更高的实用性。本文主要研究了无线传感器网络的节点定位算法。文章首先叙述了无线传感器网络的相关概念和国内外的研究现状，然后详细分析了定位算法的分类、评价标准和节点坐标的计算方法。本论文介绍了基于非测距的定位算法，分析比较了几种典型的非测距定位算法的性能。现有的非测距定位算法大都对锚节点的分布比率有较高的要求，这样会造成网络成本的提高、通信竞争和冲突的加剧，因此本文在研究现有算法的基础上，提出了两种非测距的定位算法，这两种算法都不需要密集部署锚节点。第一种算法利用功率控制实现节点定位，该算法用可以发射不同功率信号的锚节点以不同功率广播信号，未知节点根据是否收到信号来估计未知节点到锚节点的距离，当未知节点得到足够多的距离信息时，就可以实现未知节点坐标的计算。这种算法无需测距设备即可现实定位，并且为提供更高的定位精度，引入了ＲＳＳＩ测距修正了定位算法中距离估算的方法，只要锚节点的发射功率足够大，三个锚节点就可以实现整个传感器分布区域的节点定位。另一种算法是利用一个移动锚节点实现定位的定位算法，该算法使用一个可移动的带有ＧＰＳ的锚节点以规划好的路径遍历整个网络，并以一定的时间间隔广播自身的坐标信息，未知节点在收到特定位置的锚节点广播的坐标信息后，就可以实现节点的定位。本文提出的两种算法在算法复杂性和覆盖率方面都有很好的表现，并且都不需要太多的锚节点，在成本方面也较有优势。仿真结果表明，两种算法都有较高江苏大学硕士学位论文的定位精度，算法的复杂度也较低，是行之有效的定位算法。关键词：无线传感器网络，节点定位，距离无关，功率控制，移动锚节点Ⅱ江苏大学硕士学位论文ＡｂｓｔｒａｃｔＷｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ，ｗｈｉｃｈｉｎｔｅｇｒａｔｅｔｅｃｈｎｏｌｏｇｉｅｓｏｆｍｉｃｒｏ－ｅｌｅｃｔｒｏｍｅｃｈａｎｉｓｍｓｅｎｓｉｎｇ，ｅｍｂｅｄｄｅｄｃｏｍｐｕｔｉｎｇ，ｄｉｓｔｒｉｂｕｔｅｄｉｎｆｏｒｍａｔｉｏｎｐｒｏｃｅｓｓｉｎｇａｎｄｗｉｒｅｌｅｓｓｃｏｍｍｕｎｉｃａｔｉｏｎ，ｌｅａｄｔｏａｎｅｗｐａｔｔｅｒｎｏｆｉｎｆｏｒｍａｔｉｏｎｇａｔｈｅｒｉｎｇａｎｄｐｒｏｃｅｓｓｉｎｇ，ｃａｎｂｅｗｉｌｄｌｙｕｓｅｄｉｎｍａｎｙａｒｅａｓｓｕｃｈａｓｎａｔｉｏｎａｌｄｅｆｅｎｓｅ，ｅｎｖｉｒｏｎｍｅｎｔａｌｓｕｐｅｒｖｉｓｉｏｎ，ｍｅｄｉｃａｌｔｒｅａｔｍｅｎｔ，ｏｕｔｅｒｓｐａｃｅｅｘｐｌｏｒａｔｉｏｎ，ｃｏｕｎｔｅｒ－ｔｅｒｒｏｒｉｓｍａｎｄｄｉｓａｓｔｅｒｒｅｔｒｉｖａｌ．Ｉｔｉｓｃｏｎｓｉｄｅｒｅｄａｓｏｎｅｏｆｔｈｅｍｏｓｔｉｍｐｏｒｔａｎｔｔｅｃｈｎｉｕｅｓｏｆｔｈｅ２１ｎｃｅｎｔｕｒｙ．Ｂｕｔｆｏｒｍｏｓｔａｐｐｌｉｃａｔｉｏｎｓ，ｄａｔａｗｉｔｈｏｕｔｌｏｃａｔｉｏｎｉｎｆｏｒｍａｔｉｏｎｈａｓｌｉｍｉｔｅｄｕｓｅ．Ｌｏｃａｌｉｚａｔｉｏｎｈａｓｂｅｃｏｍｅｏｎｅｏｆｔｈｅｉｎｄｉｓｐｅｎｓａｂｌｅｓｕｐｐｏｒｔｉｎｇｔｅｃｈｎｉｑｕｅｓｉｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ，ａｎｄｈａｓｗｉｄｅｌｙｄｒａｗｎａｔｔｅｎｔｉｏｎｏｆｄｏｍｅｓｔｉｃａｎｄｆｏｒｅｉｇｎｓｃｈｏｌａｒｓ．Ｅｘｉｓｔｉｎｇｌｏｃａｌｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｃａｎｂｅｒｏｕｇｈｌｙｄｉｖｉｄｅｄｉｎｔｏｔｗｏｃａｔｅｇｏｒｉｅｓ：ｒａｎｇｅ－ｂａｓｅｄｌｏｃａｌｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄｒａｎｇｅ－ｆｒｅｅｌｏｃａｌｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ．Ｆｏｒｔｈｅｌｉｍｉｔａｔｉｏｎｓｏｆｂａｔｔｅｒｙ，ｃｏｓｔａｎｄｖｏｌｕｍｅｉｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ，ｔｈｅｒａｎｇｅ－ｆｒｅｅｌｏｃａｌｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｈａｓｈｉｇｈｅｒｐｒａｃｔｉｃａｂｉｌｉｔｙ．ＴｈｉｓｐａｐｅｒｍａｉｎｌｙｆｏｕｓｅｓｏｎｔｈｅｌｏｃａｌｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｆｏｒＷＳＮ．Ｆｉｒｓｔｏｆａｌｌ，ｔｈｅｒｅｓｅａｒｃｈｓｉｇｎｉｆｉｃａｎｃｅａｎｄｒｅｓｅａｒｃｈｓｔａｔｕｓｏｆｔａｒｇｅｔｌｏｃａｌｉｚａｔｉｏｎａｌｅｐｒｅｓｅｎｔｅｄ；ｔｈｅｎ，ｔｈｅｔｙｐｅｏｆｔｈｅｌｏｃａｌｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓ，ｔｈｅｃｒｉｔｅｒｉｏｎｏｆｐｅｒｆｏｒｍａｎｃｅｅｖａｌｕａｔｉｏｎａｎｄｔｈｅｍｅｔｈｏｄｏｆｃｏｍｐｕｔｉｎｇｃｏｏｒｄｉｎａｔｅ．Ｉｎｔｈｉｓａｒｔｉｃｌｅｗｅｉｎｔｒｏｄｕｃｅｔｈｅｒａｎｇｅ—ｆｒｅｅｌｏｃａｌｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓ，ａｎｄａｎａｌｙｉｚｅｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｓｏｍｅｋｉｎｄｓｏｆｔｙｐｉｃａｌｒａｎｇｅ—ｆｒｅｅａｌｇｏｒｉｔｈｍｓ．Ｔｈｅｍｏｓｔｅｘｉｓｔｉｎｇｒａｎｇｅ－ｆｒｅｅｌｏｃａｌｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｒｅｑｕｉｒｅｈｉｇｈｒａｔｉｏｂｅａｃｏｎｓ．Ｉｔｗｉｌｌｅｎｈａｎｃｅｔｈｅｃｏｓｔｏｆｎｅｔｗｏｒｋ，ａｎｄｍａｋｅｔｈｅｃｏｍｍｕｎｉｃａｔｉｏｎｃｏｌｌｉｓｉｏｎｓｅｒｉｏｕｓｌｙ．Ｓｏｗｅｉｎｔｒｏｄｕｃｅｔｗｏｔｙｐｅｓｏｆｒａｎｇｅ－ｆｒｅｅｌｏｃａｌｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｂａｓｅｏｎｓｔｕｄｙｉｎｇｅｘｉｓｔｉｎｇａｌｇｏｒｉｔｈｍｓ．Ｔｈｅｔｗｏａｌｇｏｒｉｔｈｍｓａｌｅｎｏｔｒｅｑｕｉｒｅｄｅｐｌｏｙｍａｎｙｂｅａｃｏｎｓ．Ｔｈｅｏｎｅａｌｇｏｒｉｔｈｍｏｆｗｅｉｎｔｒｏｄｕｃｅｃａｎａｃｈｉｅｖｅｌｏｃａｌｉｚａｔｉｏｎｔｈａｔｍａｋｅｕｓｅｏｆｐｏｗｅｒｃｏｎｔｒ０１．Ｉｎｔｈｉｓａｌｇｏｒｉｔｈｍ，ｔｈｅｂｅａｃｏｎｓｗｈｉｃｈＣａｌｌｂｒｏａｄｃａｓｔｓｉｎｇｌｅｗｉｔｈｄｉｆｆｅｒｅｎｔｐｏｗｅｒ．Ｔｈｅｕｎｋｏｗｎｎｏｄｅｅｓｔｉｍａｔｅｄｉｓｔａｎｃｅｂｅｔｗｅｅｎｔｈｅｂｅａｃｏｎａｎｄｔｈｅｕｎｌ（Ｉｌｏｗｎｏｄｅｂａｓｅｏｎｗｈｅｔｈｅｒｔｈｅｓｉｎｇｌｅｗｈｉｃｈｂｒｏａｄｃａｓｔｂｙｔｈｅｂｅａｃｏｎｗａｓｒｅｃｅｉｖｅｄ．Ｔｈｅｕｎｋｎｏｗｎｏｄｅｃａｌｃｕｌａｔｅｉｔ’ＳＩＩＩ江苏大学硕士学位论文ｃｏｏｒｄｉｎａｔｅｗｈｅｎｔｈｅｙｇｅｔｅｎｏｕｇｈｄｉｓｔａｎｃｅ．Ｔｈｅａｌｇｏｒｉｔｈｍｃａｎｃａｌｃｕｌａｔｅｔｈｅｃｏｏｒｄｉｎａｔｅｗｉｔｈｏｕｔｍｅａｓｕｒｅｅｑｕｉｐｍｅｎｔ．Ｂｕｔｆｏｒｍａｋｉｎｇｔｈｅｒｅｓｕｌｔｍｏｒｅｐｒｅｃｉｓｅ，ｗｅａｍｅｎｄｔｈｅｄｉｓｔａｎｃｅｂｅｔｗｅｅｎｔｈｅｂｅａｃｏ．ｎａｎｄｕｎｋｎｏｗｎｏｄｅｕｓｅＲＳＳＩ．Ｉｆｔｈｅｐｏｗｅｒｏｆｔｈｅｂｅａｃｏｎｉｓｅｎｏｕｇｈ，ｔｈｉｓａｌｇｏｒｉｔｈｍｃｏｕｌｄｆｉｎｉｓｈｔｈｅｌｏｃａｌｉｚａｔｉｏｎｕｓｅｏｎｌｙｔｈｒｅｅｂｅａｃｏｎｓ．Ｆｏｒｔｈｅｒｍｏｒｅ，ｗｅａｌｓｏｉｎｔｒｏｄｕｃｅａａｌｇｏｒｉｔｈｍｆｉｎｉｓｈｌｏｃａｌｉｚａｔｉｏｎｕｓｅａｍｏｂｉｌｅｂｅａｃｏｎ．ＡｍｏｂｉｌｅｂｅａｃｏｎｗｉｔｈＧＰＳｍｏｖｅｉｎｔｈｅｄｅｐｌｏｙａｒｅａ，ａｎｄｂｒｏａｄｃａｓｔｔｈｅｉｒ’Ｓｃｏｏｒｄｉｎａｔｅｗｉｔｈｆｉｘｅｄｉｎｔｅｒｖａｌ．ＴｈｅｌｏｃａｌｉｚａｔｉｏｎｗｉｌｌｆｉｎｉｓｈｗｈｅｎｔｈｅｕｎｋｎｏｗｎｏｄｅｒｅｃｅｉｖｅｅｎｏｕｇｈｃｏＯｒｄｉｎａｔｅ．Ｔｈｅｔｗｏａｌｇｏｒｉｔｈｍｓｗｈｉｃｈｉｎｔｒｏｄｕｃｅｄｉｎｔｈｉｓｐａｐｅｒｈａｖｅｇｏｏｄｐｅｒｆｏｒｍａｎｃｅｉｎａｌｇｏｒｉｔｈｍｃｏｍｐｌｉｃａｔｉｏｎａｎｄｒａｔｉｏｏｆｃｏｖｅｔｉｎｇｗｉｔｈｏｕｔｍｏｒｅｂｅａｃｏｎｓ．Ｓｏｔｈｅｃｏｓｔｏｆｔｈｅａｌｇｏｒｉｔｈｍｉｓｌｏｗｅｒ．Ｔｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｓｈａｖｅｇｏｏｄｐｅｒｆｏｒｍａｎｃｅｉｎｐｒｅｃｉｓｅａｎｄｃｏｍｐｌｅｘ．Ｋｅｙｗｏｒｄ：ＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｓ，ＮｏｄｅＬｏｃａｌｉｚａｔｉｏｎ，Ｒａｎｇｅ－ｆｒｅｅ，ＰｏｗｅｒＣｏｎｔｒｏｌ，ＭｏｂｉｌｅＢｅａｃｏｎＩＶ学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于保密口，在年解密后适用本授权书。不保密囱。学位论文作者签名：王谚移指导教师签名：幽ｆ护年多，Ｅｊ值日扣。红泳年６砂日独创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：０２。汐年∥月互佛江苏大学硕士学位论文１．１课题研究背景第一章绪论随着微机电系统（ＭＥＭＳ，Ｍｉｃｒｏ．Ｅｌｅｃｔｒｏ．ＭｅｃｈａｎｉｓｍＳｙｓｔｅｍ）、片上系统（ＳＯＣ，ＳｙｓｔｅｍｏｎＣｈｉｐ）和无线通信技术的发展，使得制造大量价格低廉、体积小、功耗低，同时具有感知能力、计算存储能力和通信能力的微型传感器成为可能，无线网络传感器是集传感器执行器、控制器和通信装置于一体，集传感与驱动控制能力、通信能力、计算能力于一身的资源受限的嵌入式设备１１】【２】。由这些微型传感器构成的网络称之为无线传感器网络。这种传感器网络综合了传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术，能够协作地实时监测、感知和采集网络分布区域内的各种环境或监测对象的信息，并对这些信息进行处理，获得详尽而准确的信息，传送到需要这些信息的用户。无线传感器网络作为一种全新的研究技术，在基础理论和工程技术两个层面向科技工作者提出了大量的挑战性研究课题。美国商业周刊在预测未来技术发展的报告中，将无线传感器网络列为２１世纪最有影响力的２１项技术之一。麻省理工学院的《技术评论》杂志评出了对人类未来生活产生深远影响的十大新兴技术，无线传感器网络位于这十种新技术之首。无线传感器网络的灵活性、容错性、高感知能力、低费用以及快速布局等特点，使其广泛应用在国防军事、环境监测和预报、医疗卫生、空间探索、反恐抗灾、交通管理、智能家居、建筑物状态控制、复杂机械监控、大型车间和仓库管理等领域。很多国家都对其进行了广泛而深入的研究。这方面美国、日本等发达国家则是走在了世界的前列。但是目前的研究成果大部分处于起步阶段，距离实际需求还相差甚远。我国在传感器网络方面的研究相对较少，但近年来，国内一些高等院校和研究机构也开始展开了无线传感器网络的理论和应用的研究工作。１．２无线传感器网络的概述无线传感器网络通过各类集成化的微型传感器协作地实时监测、感知和采集各种环境或监测对象的信息，通过嵌入式系统对信息进行处理，然后通过组织网江苏大学硕士学位论文络以多跳的方式所传感器收集到的信息传到用户终端。第一代传感器网络产生于２０世纪７０年代，传输方式主要是点对点的传输方式，第二代传感器网络采用串口与传感控制器相联，具有获取多种信息的综