无线传感器网络节点自定位技术研究概要

电子科技大学硕士学位论文无线传感器网络节点自定位技术研究姓名：江斌申请学位级别：硕士专业：信号与信息处理指导教师：万群20070501摘要摘要节点的自定位技术是传感器网络的关键技术之一。大量随机布放的传感器节点无法事先知道自身位置，因此必须能够在布放后进行定位。无论是否已知节点间的距离信息，基于多维标度的传感器网络定位算法都能实现定位，因此本文将重点研究基于多维标度的无线传感器网络定位算法。首先，本文在查阅大量相关文献的基础上，介绍了无线传感器网络定位技术的研究背景及国内外现状，综述了无线传感器网络定位系统和算法的性能评价标准、分类方法，着重描述了近年来在该领域具有代表性的算法的原理和特点。其次，本文介绍基于经典多维标度的传感器网络定位技术。在深入分析基于质心参考点情况下经典多维标度算法的基础上，给出了基于节点参考点的经典多维标度算法的公式推导，并比较了两者的定位效果。仿真表明，基于质心参考点的经典多维标度算法具有更好的定位性能。然后，本文提出了迭代多维标度算法的改进形式。它利用节点的通信半径和节点间的跳段数信息，应用经典多维标度方法计算得到节点初始位置矩阵，并且改进了目标函数的形式。仿真实验表明，本文改进的迭代多维标度算法比原方法有更好的定位性能。最后，本文将松弛解法引入到节点的位置估计中，提出了一种快速算法。该方法的每一步不期望使整个目标函数最小化，而只要求使其中的某一项取最小。仿真表明，本文的快速算法有效地节约了计算量，提高了计算效率。关键词：无线传感器网络；定位技术；多维标度；改进迭代多维标度；快速算法ＡＢＳＴＲＡＣＴＡＢＳＴＲＡＣＴＡｕｔｏｍａｔｉｃｌｏｃａｌｉｚａｔｉｏｎｏｆｅｖｅｒｙｓｅｎｓｏｒｉｓａｋｅｙｅｎａｂｌｉｎｇｔｅｃｈｎｏｌｏｇｙｏｆｗｉｒｅｌｅｓｓｓｅｅｔｌｓｏｒｎｅｔｗｏｒｋｓ．Ｗｉｔｈａｎｅｔｗｏｒｋｏｆｔｈｏｕｓａｎｄｓｏｆｎｏｄｅｓ，ｉｔｉｓｕｎｌｉｋｅｌｙｔｈａｔｔｈｅｐｏｓｉｔｉｏｎｏｆｅａｃｈｎｏｄｅｃ距ｂｅｐｒｅ—ｄｃｔｅｒｍｉｎｃｄ．Ｔｈｕｓ，ｅｓｔｉｍａｔｉｎｇｎｏｄｅｓ’ｐｏｓｉｔｉｏｎｉｓｎｅｅｄｅｄａｆｔｅｒｄｅｐｌｏｙｉｎｇ．ＬｏｃａｌｉｚａｔｉｏｎａｐｐｒｏａｃｈｅｓｂａｓｅｄｏｎＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＳｃａｌｅｉｎｇｃｏｕｌｄｗｏｒｋｅｆｆｉｃｉｅｎｔｌｙｏｎｒａｎｇｅ－ｂａｓｅｄＯｒｒａｎｇｅ－ｆｒｅｅ，ＳＯｔｈｉｓｐａｐｅｒｗｉｌｌｂｅｆｏｃｕｓｅｄｏｎｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓｌｏｃａｌｉｚａｔｉｏｎａｐｐｒｏａｃｈｅｓｂａｓｅｄｏｎＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＳｃａｌｉｎｇ．Ｆｉｒｓｔｏｆａｌｌ，ｔｈｅｒｅｓｅａｒｃｈｓｔａｔｕｓｏｆｗｉｒｅｌｅｓｓｌｏｃａｔｉｏｎｔｅｃｈｎｉｑｕｅｓａｎｄｐｏｓｉｔｉｏｎｉｎｇｓｙｓｔｅｍｓｆｏｒｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓａｒｅｓｕｍｍａｒｉｚｅｄｂａｓｅｄｏｎｔｈｅｓｔｕｄｙｏｆｐｌｅｎｔｙｏｆｒｅｌａｔｅｄｌｉｔｅｒａｔｕｒｅｓ．Ｔｈｅｃｒｉｔｅｒｉｏｎｏｆｐｅｒｆｏｒｍａｎｃｅｅｖａｌｕａｔｉｏｎａｎｄｔｈｅｔａｘｏｎｏｍｙｆｏｒｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓｌｏｃａｌｉｚａｔｉｏｎｓｙｓｔｅｍｓａｎｄａｌｇｏｒｉｔｈｓｍｓａｒｅｄｅｓｃｒｉｂｅｄ．Ｔｈｅｐｒｉｎｃｉｐｌｅｓａｎｄｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｒｅｃｅｎｔｒｅｐｒｅｓｅｎｔａｔｉｖｅｌｏｃａｌｉｚａｔｉｏｎａｐｐｒｏａｃｈｅｓａｒｅａｌｓｏｄｉｓｃｕｓｓｅｄａｎｄｐｒｅｓｅｎｔｅｄ．Ｔｈｅｎ，ｔｈｉｓｐａｐｅｒｉｎ仃ｏｄｕｃｅｄｓａｉｓｏｒｎｅｔｗｏｒｋｓｌｏｃａｌｉｚａｔｉｏｎｔｅｃｈｎｏｌｏｇｙｂａｓｅｄｏｎｃｌａｓｓｉｃａｌＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＳｃａｌｉｎｇ．ＯｎｔｈｅｂａｓｉｓｏｆａｎａｌｙｓｅｓｏｎｃｌａｓｓｉｃａｌＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌｓｃａｌｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｃｅｎ自ｒｏｉｄｒｅｆｅｒｅｎｃｅｐｏｉｎｔ，ｔｈｉｓｐａｐｅｒｄｅｒｉｖｅｓｔｈｅＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＳｃａｌｉｎｇａｌｇｏｒｉｔｈｍｗｈｉｃｈｕｓｉｎｇｎｅｔｗｏｒｋｎｏｄｅｓａｓｒｅｆｅｒｅｎｃｅｐｏｉｎｔ．ＳｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｈｏｗｓｔｈａｔｃｌａｓｓｉｃａｌＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＳｃａｌｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｃｏｎｔｒｏｉｄｒｅｆｅｒｅｎｃｅｐｏ衄ｉｓｍｏｒｅｐｒｅｃｉｓｅｔｈａｎｏｔｈｅｒｏｎｅ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄｍｏｄｉｆｉｅｄｉｔｅｒａｔｉｏｎＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＳｃａｌｉｎｇａｌｇｏｒｉｔｈｍ．Ｉｔｕｔｉｌｉｚｅｄｎｏｄｅ’ｓｃｏｍｍｕｎｉｃａｔｉｏｎｒａｄｉｕｓａｎｄｈｏｐｃｏｕｎｔｉｎｆｏｒｍａｔｉｏｎｂｅｔｗｅｅｎｎｏｄｅｓ．Ｎｏｄｅ＇ｓｉｎｉｔｉａｌｐｏｓｉｔｉｏｎｍａｔｒｉｘｉｓｃｏｍｐｕｔｅｄｂｙｃｌａｓｓｉｃａｌＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＳｃａｌｉｎｇａｎｄｃｏｓｔｆｕｎｃｔｉｏｎ’Ｓｆｏｒｍ．ｉｓａｌｓｏｉｍｐｒｏｖｅｄ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｐｒｏｖｅｓｔｈａｔｔｈｅｍｏｄｉｆｉｅｄａｐｐｒｏａｃｈｉｓｅｆｆｅｃｔｉｖｅａｎｄｈａｓｂｅｔｔｅｒｐｅｒｆｏｒｍａｎｃｅｔｈａｎｃｏｎｖｅｎｔｉｏｎａｌｏｎｅ．Ａｔｌａｓｔ，ｔｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｄｒｅｌａｘａｔｉｏｎｓｏｌｕｔｉｏｎｉｎｔｏｎｏｄｅｐｏｓｉｔｉｏｎｅｓｔｉｍａｔｉｏｎａｎｄｐｒｏｐｏｓｅｓａｆａｓｔａｌｇｏｒｉｔｈｍ．Ｔｈｉｓａｌｇｏｆｉｔｔｎｎｄｉｄｎｏｔｅｘｐｅｃｔｍｉｎｉｍｉｚｉｎｇｗｈｏｌｅｃｏｓｔｆｕｎｃｔｉｏｎｏｎｅａｃｈｓｔｅｐａｎｄｍｉｎｉｍｉｚｅｄｏｎｅｔｅｒｍｏｎｅａｃｈｓｔｅｐ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｈｏｗｓｔｈａｔｔｈｅｆａｓｔａｌｇｏｒｉｔｈｍｅｆｆｉｃｉｅｎｔｌｙｒｅｄｕｃｅｄｃｏｍｐｕｔａｔｉｏｎｃｏｍｐｌｅｘｉｔｙａｎｄｉｍｐｒｏｖｅｄｃｏｍｐｕｔｉｎｇｅｆｆｉｃｉｅｎｃｙ．ｎＡＢＳＴＲＡＣｒＫｅｙｗｏｒｄｓ：Ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ；Ｌｏｃａｌｉｚａｔｉｏｎｔｅｃｈｎｏｌｏｇｙ；ＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＳｃａｌｉｎｇ；ＭｏｄｉｆｉｅｄｉｔｅｒａｆｉｖｅＭｕｌｔｉｄｉｍｅｎｓｉｏｎａｌＳｃａｌｉｎｇ；ＦａｓｔａｌｇｏｒｉｔｈｍｌＩＩ独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名：；三邈日期：２。。７年，月厶日关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）日期：乞哆罗年●月ｒ舻Ｅｌ第一章绪论１．１研究背景及意义第一章绪论更小、更廉价的低功率计算设备代表的“后ＰＣ时代”冲破了传统台式计算机和高性能服务器的设计模式：普遍的网络化带来的计算处理能力是难以估量的；微机电系统（Ｍｉｃｒｏ－ｅｌｅｃｔｒｏ－ｍｅｃｈａｎｉｓｍＳｙｓｔｅｍ，简称ＭＥＭＳ）的迅速发展奠定了设计和实现片上系统（ＳｙｓｔｅｍＯｎＣｈｉｐ，简称ｓｏｃ）的基础，以上３方面的高度集成又孕育出很多新的信息获取和处理模式，无线传感器网络就是其中一例。无线传感器网络（ＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｓ，简称ＷＳＮ）就是由布置在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织网络系统，其目的是协作地感知、采集和处理网络覆盖区域中对象的信息。微电子、网络和无线通信等技术的进步，推动了低功率、多功能传感器的快速发展，使其在微小体积内能够集成信息采集、数据处理和无线通信等多种功能。传感器网络具有广阔的应用前景，能广泛用于军事、环境监测和预报、城市交通、建筑物状态监控以及医疗护理等领域【１】【２】【３】。通过布置大量传感器节点于监测区域，传感器网络将改变我们与客观世界的交互方式。但是位置信息是传感器节点采集信息中不可缺少的部分，没有位置信息的监测信息通常是无意义。因此，确定获取信息的节点位置是传感器网络最基本的功能之一，对传感器网络应用的有效性起着关键的作用ｆ４】ＩＳ］。如在环境监测应用中需要知道采集的环境信息所对应的具体区域；对于突发事件，如需要知道森林火灾的现场位置，战场上敌我车辆运动的区域，化工管道泄漏的具体地点等。对于这些问题，传感器节点必须首先知道自身的地理位置，这是进一步采取措施的基础【６】。另一方面，传感器节点位置信息的获得又可以优化网络在其它方面的应用，比如提高网络路由效率、向布置者报告网络的覆盖质量、实现网络的负载均衡和网络拓扑的自配置等。在传感器网络中，传感器节点存在着能量有限、可靠性差、节点规模大且随机布放、无线模块的通信距离有限等特点，传统的定位技术无法很好得适用于传感器网络。全球定位系统（ＧｌｏｂａｌＰｏｓｉｔｉｏｎＳｙｓｔｅｍ，简称ＧＰＳ）成本和能耗高，限制电子科技大学硕士学位论文了它在无线传感器网络中的应用。局部定位系统（ＬｏｃａｌＰｏｓｉｔｉｏｎＳｙｓｔｅｍ，简称ＬＰＳ）需建立高性能的基站设施，这对大多数低配置的传感器网络来说无疑是昂贵的负担。因此，必须针对无线传感器网络节点的低成本、低能耗和通信能力有限的特点设计有效的定位算法。１．２国内外研究现状传感器网络的研究起步于２０世纪９０年代。从２１世纪开始，传感器网络技术引起了学术界、军界和工业界的极大关注。美国所有著名院校几乎都有研究小组在从事传感器网络相关技术的研究，欧洲和日本等国家的研究机构也加入到传感器网络的研究之中。在传感器网络中，传感器节点自身的正确位置是提供监测事件位置信息的前提。定位技术作为传感器网络应用的关键技术之一，同样引起了各国研究者的关注。随着传感器网络研究的深入开展，已经有一些应用于无线传感器网络的定位系统被提出，其中比较有代表性的定位系统有ＡｃｔｉｖｅＢａｄｇｅ系统【７１，ＡｃｔｉｖｅＢａｔ系纠８】，ＲＡＤＡＲ系纠９１，Ｃｒｉｃｋｅｔ系冽１０】【ｎ】，Ｍｅｄｕｓａ系统‘１２１等。ＡＴ＆ＴＣａｍｂｒｉｄｇｅ的ＡｃｔｉｖｅＢａｄｇｅ系统是最早的室内定位系统，它是由在建筑物内布置一个通过以太网连接的红外线传感器节点组成的网络，系统的定位精度以房间为单位。但是由于红外线在阳光下无法正常工作，所以该系统的应用区域受到限制。同时，红外信号传播距离短，使系统在建筑物内不得不安装许多传感器，导致系统扩展能力很差，需要巨额的安装、配置和维护费用。ＡｃｔｉｖｅＢａｔ系统是在Ｂａｄｇｅ系统上的优化，它使用了超声波测距技术提供了比Ｂａｄｇｅ更精确的定位功能。但是，ＡｃｔｉｖｅＢａｔ系统同样存在着可扩展性差、布置代价和总体成本高的缺点。ＲＡＤＡＲ系统是微软公司基于ＩＥＥＥ８０２．１１无线网络标准设计的一种室内定位系统。在ＲＡＤＡＲ系统中，主要考虑建筑物的墙壁对信号传播的影响，建立信号衰落和传播距离间的关系。虽然在试验环境中ＲＡＤＡＲ系统表现出良好的特性，但是在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，使得该技术在实际应用中仍然存在很多困难。Ｃｒｉｃｋｅｔ系统是麻省理工学院的Ｏｘｙｇｅｎ项目的一部分，用来确定移动或静止节点在建筑物内的具体房间位置。该系统利用无线射频信号和超声波信号到达时间间隔计算出未知节点到该发信号节点的距离。然后通过比较到各个邻近发信号节２第一章绪论点的距离，选择出离自己最近的发信号节点，从而确定自身的房问位置。Ｃｒｉ