nbhkdz.com冰点文库

基于无线传感网络的能量有效跟踪系统关键技术研究

时间:2013-07-18


中国科学技术大学 硕士学位论文 基于无线传感网络的能量有效跟踪系统关键技术研究 姓名:徐涛 申请学位级别:硕士 专业:计算机软件与理论 指导教师:黄刘生 20090401 摘要 摘要 无线传感网络是由大量微传感节点间的相互协作来完成某一特定任务的自 组织网络。作为一种新兴技术,无线传感网络有着广泛的应用前景,而定位跟踪 正是无线传感网络的重要应用之一。 在基于无线传感网络的跟踪应用中,能量有效性与定位跟踪精度是系统的主 要衡量因素。在监测区域内没有被跟踪目标时,由于无线传感网络的节点通常是 能量受限的,因此我们希望在保证对监测区域覆盖的情况下,通过关闭节点的无 线电来节省能量,进而提高整个网络的生命周期。当目标进入监测区域时,我们 能通过有效的节点定位机制来跟踪目标,对目标进行实时定位跟踪。 针对于此,本文主要研究能量受限的定位跟踪系统中的两个关键问题:面向 跟踪应用的节点调度问题研究和面向室内环境的实时定位跟踪问题研究;最后, 在上述理论研究基础上,我们开发了基于无线传感网络的面向矿山井下矿工定位 跟踪系统。 构造无线传感网络中具有连通覆盖特性的节点子集是实现网络休眠调度、延 长网络生命周期的关键技术之一,具有重要的研究意义。已有的研究大多侧重于 k 覆盖节点子集构造问题,在一定条件下 k 覆盖子集能满足 k 连通,但通过构造 k 覆盖节点子集来实现 k 连通会耗费过多的节点,代价较大。因此,本文提出了 一个构造 k 连通 I 覆盖节点子集的算法——CPC,能够用较少的节点构造一个既 能满足网络的覆盖特性又能够满足 k 一连通特性的节点子集。本文证明了该算法 的正确性,并通过仿真实验与相关算法进行了性能比较。结果表明,与已有的 k 覆盖算法相比,CPC 算法能够节省约 55%的节点数。 在室内环境中,由于建筑结构复杂,且室内的射频传播特性受到多径干扰等 因素的影响,因此室外定位系统不能简单地移植到室内环境中,需要针对室内环 境的特点,重新设计适用于室内的定位跟踪系统。本文中,作者提出了基于 RSSI 信号的室内定位方法 AIT。该方法首先通过区域定位算法 BCA 确定移动节点处于 哪个区域,然后再通过点定位算法 SGL 对移动节点在该区域内进行精确的点定 位,确定移动节点在区域内的具体位置。一旦确定移动节点所处的区域,则点定 位时将只使用该区域内的锚节点信息进行定位,这样可以提高点定位的精度。同 时,AIT 方法适用于不同规模的区域,因此适用范围更广。实验结果表明 BCA 算 法将 MERIT 系统的区域定位准确度从 71%提高到 86%,而 SGL 算法与 Ecolocation 算法相比减少了 32%的定位误差。 基于上述理论研究的基础上,我们开发了基于无线传感网络的矿山井下定位 跟踪原型系统,本文着重介绍了系统服务器端的各功能模块的设计。目前该系统摘要 正处于验收阶段。 本文的主要贡献及创新点如下: 1、首次提出了构造覆盖保持的 k 一连通节点子集的 CPC 算法,实现了用较少

的节点便能满足网络覆盖又与 k.连通特性,从而使得网络中其他节点可以进入休 眠状态,节省整个网络的能量消耗,延长了网络寿命。 2、将室内定位划分为区域定位和点定位两个过程。其中,区域定位算法 BCA 提出了基于区域关联图的概念,设计了精确的区域判定机制;点定位算法 SGL 提 出了基于格划分的概率定位算法,有效提高了定位精度。实验结果表明该方法与 以往的系统相比,在定位精度上有较大的提高。 3、基于上述理论研究的基础上,我们研究开发了基于无线传感网络的煤矿 井下定位跟踪原型系统。目前该系统正处于验收阶段。 关键词:无线传感网络能量有效定位跟踪覆盖连通; HABSTRACT ABSTRACT Wireless sensor networks ale self-organizing network which can finish certain task by mutual collaboration between large numbers of micro—sensor nodes.As an emerging technology,wireless sensor networks have comprehensive application prospects,and location and tracking isone of important applications towireless sensor networks. In the tracking application of wireless sensor networks,energy effectiveness and accuracy of location and tracking are main factors tomeasure system.When the monitoring region has no tracking target,as aresult of the wireless sensor network nodes are usually energy constrained,we hope to ensure the coverage to monitoring region,through the closure of the nodes radio to save energy,to improve the life of the entire network. For this reason,this paper studies two key problems in the energy—constrained location and tracking system:the node scheduling problem research totracking application and the indoor real—time location tracking problem research toindoor environment;finally,based onthe above theory,we developed aminer location tracking system to underground mine based on wireless sensor networks. Constructing aconnected covering node subset isone of key technologies for enlarging lifetime and sleeping scheduling in wireless sensor networks,which isa significantly important research area.The previous researches focus on the kcovering node subset construction problem.Because kcovering subset isk—connected under certain conditions,people study the k-connected subset construction problem less. However,constructing kcovering node subset as k-connected subset will use too many nodes,the cost isgreat.Therefore,this paper proposes ak—connected and 1-covered node subset construction algorithm--CPC,which can construct anode subset that iscovering and k-connected with few nodes.This paper also proves the algorithm。S correctness,and compares the performance with related algorithm by simulation.Experimental results show that compared with previous kcovering algorithms,CPC algorithm call save about 55%of nodes. In the indoor environment,because of the complexity of building structure,and the RF propagation characteristic is influenced by multi-path interference and other factors,the outdoor location system Call not simply be transplanted tothe indoor environment,we need to re—design the indoor location tracking system according to IIIABSTRACT

the characteristics of the indoor environment.In this paper,the authors proposed RSSI—based indoor location method AIT.The method first determines which region the mobile node in by region location algorithm BCA,and then precise point location in the region which the mobile node in by point location algorithm SGL,to determine the specific location of the mobile node in the region.Once the mobile node’S region isdetermined,the point location will only use the anchor information in the region to locate,this can improve the accuracy of point location.At the same time,AIT method call be used for regions of different sizes,SO the application is broader.The evaluation results show that the BCA algorithm Can improve the precision of area decision of MERIT from 71%to 86%,and the SGL algorithm decreases 32%location error compared with Ecolocation algorithm. Based onthe above theory research,we developed aminer location tracking prototype system to underground mine based on wireless sensor networks.This paper focuses on the design of the functional modules which in the system server.At present, the system is in the acceptance phase. The contributions and novelties ofthis dissertation ale as follow in: 1.This paper proposes Coverage—Preserving k-Connected Subset construction algorithm--CPC for the first time,which can construct a node subset that iscovering and k-connected with few nodes.So that other nodes inthe network can enter sleep mode tosave energy consumption of the entire network and extend the network lifetime. 2.The indoor location isdivided into two processes region location and point location.The region algorithm BCA proposes the concept based on region incidence graph,designs aprecise mechanism to determine the region;the point location algorithm SGL proposes the probability location algorithm based on the mesh,effectively improve the location accuracy.The experiment results show that the method compared with the previous system,the location accuracy has been enhanced. 3. Based on the above theory research,we developed aminer location tracking prototype system to underground mine based on wireless sensor networks.At present,the system is in the acceptance phase. Key Words:wireness sensor networks,energy effective,location tracking,coverage, connect IV 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外,论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作了明确 的说明。 作者签名:龃 作者签名:j 亟蝎 签字吼汪墨缉一 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一,学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权,即:学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版,允许论文被查阅和借阅,可以将学位论文编入有关数据 库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人

提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 幽开 口保密(——年) 作者签名:缘谄 签字日期:L 鲤墨: ‘!f. 导师签名: 签字日期: 雄 乌到坠 地“乒第一章绪论 第一章绪论 无线传感网络作为 2l 世纪最重要的技术之一,在理论和应用上都具有重要的 研究价值。无线传感网络有着传统网络无法比拟的许多优势,现已被广泛应用于 军事战场、灾难救援、建筑监测、环境科学、医疗保健、智能家居、工业自动化 和防范恐怖袭击等方面。如今,针对无线传感网络方面的研究已经广泛开展,随 着研究的深入,涌现出了大量有价值的研究成果。 本章首先介绍了无线传感网络基本概念,包括无线传感网络的体系结构、传 感器节点的结构、无线传感网络的特点及无线传感网络的应用及未来前景;然后, 对无线传感网络的研究体系及其研究的热点问题进行了简单介绍;最后,介绍了 本文的结构安排。 1.1 引言 进入 2l 世纪以来,信息技术和网络技术的发展给人类社会的各个领域带来了 巨大而深刻的变化。以 Internet 为代表的信息网络对人们生活方式的影响越来越 巨大,并将在未来的各个领域继续持续发展而不断提高影响力。无线传感网络 (Wireless Sensor Networks,WSN)是一种集成了传感器技术、微机电系统技 术、无线通讯技术和分布式信息处理技术的新型网络技术。其通过节点间的协作, 对监测对象的信息进行实时感知、采集和处理,并将处理后的信息通过无线传感 网络传送给最终的网络终端用户。从而使 WSN 成为 Internet 从虚拟世晃到物理世 界的延伸,成为逻辑上的信息世界与真实物理世界的连接桥梁,将信息世界与物 理世界融为一体(Tilak Set a1.2002;Akyildiz Iet a1.2002:李建中等,2003:崔 莉等,2005:孙利民等,2005:毛剑琳等,2006)。 早在 1999 年,美国《商业周刊》就将无线传感网络列为 21 世纪里 21 项最重要 的技术之一。2003 年,美国《技术评论》杂志评出对人类未来生活产生深远影响 的十大新兴技术中无线传感网络排列第一(Wade Reta1.2003)。在商业界, Crossbow 等公司已经开发出了无线传感网络方面相关的产品。在学术界,美国自 然科学基金委员在 2003 年投资 3400 万美元制定了无线传感网络研究计划,支持相 关基础理论的研究。著名院校如加州大学伯克利分校、洛杉矶分校、南加州大学 等都已经设立相关研究项目,开展了关于无线传感网络方面的研究。此外,英国, 德国,芬兰,日本等国相关研究机构也已经加入到无线传感网络的研究。 无线传感网络在我国的研究虽然开展较晚,但目前国家 973 计划、国家自然 科学基金和国家 863 等均设专项资助该领域的理论、 方法和关键技术研究, 将之第一章绪论 列入了《信息产业科技发展“十一五”计划和 2020 年中长期规划(纲要)》 ,并 确定为我国需要重点突破的核心技术(毛剑琳等,2006)。目前中科院、中国 科大、哈工大、清华大学、浙江大学、上海交大等高校纷纷从不同的角度开展其 研究。因此无线传感网络的研究成为国际和国内研究热点之一,具有很强的理论

和实际应用价值。 1.2 无线传感网络概述 无线传感网络 WSN(Wireless Sensor Network)是一种自组织网络,通过大 量低成本、资源受限的传感节点间的协作感知、采集、处理和发布感知信息完成 某一特定任务。无线传感网络包括感知对象、传感器节点和观测者 3 个基本要素。 无线网络是传感器之间、传感器与观测者之间的通信方式,负责建立节点与观察 者之间的通信路径。在军事战场、灾难救援、建筑监测、环境科学、医疗保健、 智能家居、工业自动化和防范恐怖袭击等方面,无线传感网络将会是一个经济实 用的解决方案,有着广泛的应用前景(任丰原等,2003)。 1.2.1 无线传感网络体系结构 .根据节点在网络中所担当的角色不同,按照逻辑划分,得到一类典型的传感 器网络的体系结构图,如图 1.1 所示。 2 图 1.1 传感器网络的体系结构图第一章绪论 图 1.1 网络内不同类型的节点组成不同的子网,各子网之间通过网关或基站 连接。网关将无线传感网络内各相关信号通过卫星、无线网络或者 internet 等方 式传送到控制中心服务器。终端用户通过服务器查询获得相关数据,并且可以通 过服务器发送相应的下行命令到网关,再由网关发送到无线传感网络中的各节 点,节点接到命令后做出相应调整。通过上述方式,节点间协同执行,实现对监 控区域的远程监控与操作。 网关:负责无线传感网络与外部网络的连接以及不同类型无线传感网络之间 的连接,完成多种网络协议栈之间的转换,实现信息共享。同时实现发布终端用 户的管理任务、无线传感网络内部信息数据的融合等工作。 节点:相对于网关,节点的处理能力、存储能力、通信能力通常较弱,能量 有限,常采用电池供电。每个节点可以单独担当数据采集器、路由器的角色或者 几种角色的综合,完成本地数据的采集与处理、中间数据的转接并与其它节点协 作完成特定的任务。 1.2.2 传感器节点结构 一个典型的节点由传感器模块、处理器、通讯模块、能量供应模块以及其它 辅助可选功能模块如时间同步模块、定位发现模块、节点移动模块及能量再生模 块等组成(Tubaishat M et a1.2003),如图 1.2 所示。 图 1.2 传感器节点结构 根据不同的应用需要,配置不同的传感器以采集不同类型的数据如:温度、 湿度、声音能量、相对角度等。处理器是整个节点的中心,负责控制整个节点的 操作、存储和处理本节点采集的信息以及其它节点采集转发信息等。通讯模块负 责节点之间的数据、控制信息、无线通讯。能量供应模块负责整个节点运行所需第一章绪论 的能量供应(网关可能采用持续的电力供应,普通节点常采用电池供电,对于部 分重要的节点可采用能量再生设备如光电转换单元)。部分节点包含辅助模块。 1.2.3 无线传感网络的特点 无线传感网络的节点的数量巨大,而且处在随时变化的环境中,这就使它有 着独特的特点:(Tilak Set a1.2002;Akyildiz I eta1.2002;李建中等,2003:崔 莉等,2005:孙利民等,2005;毛剑琳等,2006) (1)无中心和自组网特性:在无线传感网络中,所有节点的地位都是平等的, 没有预先指定的中心,而正因为没有中心;网络便不会因为单个节点的脱离而受

到损害。 (2)自组织:节点部署后就可以快速、自动地组成一个独立的网络,节点通 过分层协议和分布式算法协调各自的行为。当旧节点失效以及新节点加入时,新 的网络拓扑需要快速形成。 (3)网络拓扑的动态变化性:网络中的节点是处于不断变化的环境中,它的 状态也在相应地发生变化,加之无线通信信道的不稳定性,网络拓扑因此也在不 断地调整变化,而这种变化方式是无人能准确预测出来的。 (4)容错性:节点可以随时加入或者离开,任何节点的失效不会影响整个网 络的运行,具有很强的容错性和鲁棒性。 (5)能量受限制性:无线传感网络中每个节点的电源是有限的,网络大多工 作在无人区或者对人体有伤害的恶劣环境中,更换电源几乎是不可能的事,这势 必要求网络功耗要小以延长网络的寿命,而且要尽最大可能的节省电源消耗。 (6)传输能力的有限性:无线传感网络通过无线电波进行数据传输,虽然省 去了布线的烦恼,但是相对于有线网络,低带宽则成为它的天生缺陷。同时,信 号之间还存在相互干扰,信号自身也在不断地衰减。因为单个节点传输的数据量 并不算大,这个缺点还是能忍受的。 (7)多跳路由:节点的通信距离有限,通常只能与它的邻居直接通信。网络 范围的数据通信需要通过中间节点进行多跳路由来完成。 (8)以数据为中心:是一种面向应用的网络,一般的数据传输网络不需要关 心所传输的数据的内容和意义。但无线传感网络必须关注所传输数据的物理特 性,才能完成用户查询物理世界信息的功能。 (9)安全性:无线信道、有限的能量、分布式控制都使得无线传感网络更容 易受到攻击。被动窃听、主动入侵、拒绝服务则是这些攻击的常见方式。安全性 在无线传感网络的设计中至关重要。 目前对于无线传感网络本身的评价指标有:能源有效性、生命周期、时间延 4 第一章绪论 迟、感知精度、可扩展性、容错性等。但是许多指标还需要进一步模型化,不同 的应用会有进一步对应的性能评价指标。 1.2.4 无线传感网络的应用及未来前景 无线传感网络有着传统网络无法比拟的许多优势,现已被广泛应用于军事战 场、灾难救援、建筑监测、环境科学、医疗保健、智能家居、工业自动化和防范 恐怖袭击等方面。 (1)军事战场 自组织和高容错性的特征使无线传感器网络非常适用于恶劣的战场环境中, 通过飞机或者炮弹直接将传感器节点播撤到敌军、友军或者内部,进行我军兵力、 装备和物资的监控,冲突区的监视,敌方地形和布防的侦察,协助智能弹药对目 标的攻击以及战场破坏情况的评估;核武器、生化武器的成分以及攻击后的监测 和侦察等(Kumar Sand Shehperd D2001); (2)灾难救援 在发生了地震、水灾、强热带风暴或遭受其他灾难打击后,固定的通信网络 设施(如有线通信网络、蜂窝移动通信网络的基站等网络设施、卫星通信地球站 以及微波中继站等)可能被全部摧毁或无法正常工作,对于抢险救灾来说,这时 就需要无线传感器网络这种不依赖任何固定网络设施、能快速布设的自组织网络 技术(Hill 儿 2003)。

(3)建筑监测 通过布置于建筑物内的图像、声音、气体检测、温度、压力、辐射等传感器, 在发现异常事件时能够及时报警,自动启动应急措施(Galbreath JH eta1.2003; SchmidTetal.2005)。 (4)环境科学 随着人们对于环境的日益关注,环境科学所涉及的范围越来越广泛。通过传 统方式采集原始数据是一件困难的工作。传感器网络为野外随机性的研究数据获 取提供了方便,比如,监视农作物灌溉情况、土壤空气情况;跟踪候鸟和昆虫的 迁移,研究环境变化对农作物的影响;大面积的地表监测和行星探测;气象和地 理研究;洪水监测;森林火灾的监测等(Mainwaring A et a1.2002;任丰原等, 2003;Burrell Jet a1.2004;Baggio A 2005)。 .(5)医疗保健 如果在住院病人身上安装特殊用途的传感器节点,如心率和血压监测设备, 利用传感器网络,医生就可以随时了解被监护病人的病情,进行及时处理。还可 以利用传感器网络长时间地收集人的生理数据, 这些数据在研制新药品的过程中第一章绪论 是非常有用的,而安装在被监测对象身上的微型传感器也不会给人的正常生活带 来太多的不便。此外,传感器节点还可以用于医院里的药品管理,对药品种类进 行分类、辨识药品等。总之,传感器网络为未来的远程医疗提供了更加方便、快 捷的技术实现手段(Noury N et a1.2000;任丰原等,2003;马祖长等,2004)。 (6)智能家居 , 嵌入家具和家电中的传感器与执行机构组成的无线传感器执行器网络与 Internet 连接在一起将会为人们提供更加舒适、方便和具有人性化的智能家居环 境。通过布置于房间内的温度、湿度、光照、空气成分等无线传感器,感知居室 不同部分的微观状况,实现对温度、湿度、光照、空气成分等的自动控制及通过 嵌入到智能吸尘器,智能微波炉,电冰箱等家电的传感器节点,实现遥控、自动 操作和基于 Internet,手机网络等的远程监控; (7)工业自动化 在工业生产上,无线传感网络可以实现设备故障监测故障诊断,工厂自动化 生产线,恶劣环境生产过程监控,仓库管理等功能。 大型设备的监控:在一些大型设备中,需要对一些关键部件的技术参数进行 监控,以掌握设备的运行情况。在不便于安装有线传感器的情况下,无线传感器 网络就可以作为一个重要的通信手段(马祖长等,2004)。 (8)反恐应用 美目前世界各地的恐怖袭击也大有愈演愈烈之势,采用具有各种生化检测传 感能力的传感器节点,在重要场所进行部署,配备迅速的应变反应机制,有可能 将各种恐怖活动和恐怖袭击扼杀在摇篮之中,防患于未然,或尽可能将损失降低 到最少。通过特殊用途的传感器,如生物化学传感器监测有害物、危险物的信息, 准确判定生化物质的成分以及泄漏源位置,可提高对突发事件的应变能力。 无线传感器网络作为一种新的信息获取和处理技术,在各种领域,它有着传 统技术不可比拟的优势,同时也必将开辟出不少新颖而有价值的商业应用。可以 预见,在未来,无线传感器网络将会成为人们生活中不可或缺的一部分。 总之,无线传感器网络是继 Internet 之后的 IT 热点技术,具有广阔的应用前 景,将对 2l 世纪人类的生活产生重大的影响,研究无线传感器网络的意义重大而 深远。相信随着无线传感网络技术的不断成熟,其应用前景一定会更加美好。

1.3 无线传感网络研究体系 无线传感网络作为一个全新的研究领域,在基础理论和工程技术两个层面提 出了大量的挑战性研究课题。从物理层节点研制、网络协议设计到应用层的研究, 6 第一章绪论 吸引了大量学者对其各个层面展开了研究,并取得了大量成果。按照无线传感网 络功能结构划分,可以分为通信体系、中间技术、应用系统三大部分如图 1.3 所 示,目前各部分主要的研究进展及典型成果如下所示。 、。 、 、‘ : o,+、、 :! j,∥.、 、‘、 ,‘{. ≯应用体系 , 。tI, 、j,j, 节 点 部 署 覆 兰 皿 信 息 处 理 任 务 分 配 数 据 查 询 协 同 处 理 安 全 问 题 图 1.3 无线传感网络研究体系 1.3.1 通信体系研究现状 (1)物理层 在通信体系的四层协议栈中,物理层负责数据的调制、发送与接收,涉及传 输的媒介、频段的选择、载波产生、信号检测、调制解调方式、数据加密和硬件 设计等(马祖长等,2004)。无线传感网络采用的传输媒体主要有:射频(Radio Frequency,RF)、可见光、红外线等,其中,射频是最常用的。无线传感器网络 的通信频段,通常采用工业科学医疗(Industrial Scientific and Medical,ISM)

公共的频段,欧洲为 433MHz,北美和我国是 915MHz(Akyildiz I et a1.2002)。 (2)数据链路层 无线传感器网络的数据链路层包括差错控制和媒介访问控制(MAC)。目前的 数据通信网中两种重要的差错控制是:前向纠错(forward error correction,FEC)第一章绪论 及自动重复请求(automatic repeat request,ARQ)。ARQ 目前还没有用于传感 器网络,因为 ARQ 的附加重传增加了能源消耗和网络负载。由于嵌入了纠错能力, FEC 的解码复杂性变大。可见,目前还没有一种较好的差错控制机制可用于传感 器网络。为此,必须在对信道特性和实现技术的深刻认识和掌握的基础上,致力 于开发具有简单的编码解码算法的差错控制机制(Akyildiz Iet al。2002;马祖长 等,2004j。 (3)网络层 无线传感器网络的网络层主要是对路由协议进行设计,实现数据的实时多跳 传输和整个网络的节能。考虑无线传感器网络的特征以及应用和基础结构的需 要,研究者们提出了很多方案来解决无线传感器网络中的路由问题。我们可以把 它们分为四类:以数据为中心的(Date-centric)、分层次的(Hierarchical)、基 于位置的(Location-based)和基于网络流和支持 QoS 的(Network flow based and OoS aware)。 (4)传输层 无线传感网络的传输层协议主要实现与 Internet 或其它的网络进行互联。由 于可扩展性、以数据为中心的路由等特性和能耗、硬件资源的限制等闫题,传感 器节点无法像 Internet 上的服务器一样存储大量的数据,而确认(ACK)在无线传 感器网络中的代价太过于昂贵,导致 TCP 和 UDP 无法直接应用到无线传感器网络 h。 1.3.2 中间件研究现状 (1)时间同步 作为一种典型的分布式系统,无线传感器网络是通过数量众多的传感器节点 协作来完成任务的。这种协作大部分通过交换盖有节点本地时钟的时间戳信息来 实现的,因此需要传感器节点保持本地时钟来确定事件的时序。所以,时间同步 成为无线传感器网络基础结构中不可缺少的一部分。 (2)定位 定位主要是为路由层和高层的服务提供位置信息,实现对移动目标进行跟踪 等任务。无线传感器网络中的定位(Localization)机制与算法包括两部分:节点 自身定位和外部目标定位,前者是后者的基础。无线传感器网络的定位主要作用: 为一些基于位置信息的路由算法提供定位;为传感监测的对象提供位置反馈;跟 踪移动目标。 国防等军事领域的系统中应用的定位机制算法主要是 GPS 系统。但是 GPS 系统 无法在室内及地底等环境下工作,且具有能耗大、硬件成本高、体积大等缺点, 8 第一章绪论 因而无法在普通的定位中应用。下面介绍的定位机制和算法都是非 GPS 的。 传感器节点自身定位分两类: 一类是基于锚节点(Anchor-Based)的定位。这类定位机制基本思路是:先测 量未知节点(即待定位节点)到锚节点的距离(根据到达信号的强度、到达的时间 Time of Arrival、到达的角度 Angel of Arrival 等计算),再对未知节点进行定 位估计(用双曲线三边测量法,三角测量法,极大似然估计,最/J、_-乘法,Kalman

滤波等进行估计)。L 匕女 HDoherty et a1.(2001)提出了一种仅用连接约束的基于 锚节点的定位算法,Bulusu eta1.(2000)提出了一种用未知节点与基准节点之 间的无线电(Radio)连接来确定其位置的算法。Terrain 算法是建立在 ABC 算法 (Savarese C et a1.2001)的基础之上的。节点通过 ABC 算法成为锚节点。每个节点 计算到至少三个锚节点的距离,然后采用这些距离和锚节点的坐标进行并行的优 化。Savarese et a1.(2002)等提出了一种两步、基于锚节点的并行的定位算法 Hop-Terrain。Savvides eta1.(2001)提出多边协作定位算法,其节点通过解一 组包含溢出约束的方程来实现定位。Niculescu eta1.(2003)则采用到达角 (Angle 一 0f-Arrival,AOA)进行定位。Howard et a1.(2001)提出基于弹簧松弛原 理的定位算法。 另一类是没有锚节点的定位(Anchor-Free Localization,AFL):在没有预 先配置好位置的锚节点情况下采用本地的距离信息来确定节点的坐标。采用无锚 节点定位的传感器网络将不再是唯一的,并可以方便地通过多种方法(取决于全 局的转换、旋转或者倒转)嵌入到其它的全局协调的系统中。这一点在基于锚节 点定位系统中是无法实现的。这类算法包括:增加型(即对未知节点依次定位)的 ABC 算法(Savarese Cet a1.2001);并行的 AFL 算法(Nissanka Bet a1.2003),由于采 用了并行优化算法,对测量误差具有鲁棒性。 1.3.3 应用系统研究现状 无线传感器网络的应用系统主要面向应用提供专用的服务。应用系统相关的 研究热点问题包括目标定位跟踪系统(Target tracking system),节点部署与 覆盖(Deployment and Coverage),任务分配(Task Allocation),信息处理 (Information processing),数据查询(Data Query),协同处理(Coordinated processing),安全问题(Security)等。本文的第二章将对本文涉及的目标定位 跟踪系统进行重点介绍 1.4 无线传感网络研究的热点问题第一章绪论 (1)网络自组织与自我管理 由于应用环境的限制,无线传感网络必须是自我部署的。无线传感网络采用 无线方式的自组网结构,传感节点被随意放在监测区域后,进入自启动阶段,并 发出信号与邻居节点联系,记录邻居节点的位置信息及工作情况并送回一个基 站。基站根据记录信息制订整个网络的拓扑。 无线传感网络的网络拓扑一般有三种形式基于簇的分层结构、基于网的平面 结构、基于链的线结构。这三种结构在不同的应用环境下各有利弊,网络自组织 管理的目标是根据节点能量状况,合理地分配任务,有效延长网络寿命。当发生 节点失效时,产生新的拓扑在层次结构中。网络自组织管理还需要解决簇的自动 生成,簇头的选举问题。 (2)节点定位 在无线传感网络的应用中,观察者往往需要根据获得的数据信息到监测区域 做出相应的处理(例如:火灾预警监测,如果在测得某处的烟雾浓度超过某个阀 值时,就应该报警并将可能发生火灾的位置报告给服务器)。所以节点所采集到 的数据必须结合其在测量坐标系内的位置信息才有意义。此外,节点的位置信息 还可用于提高路由效率,为网络提供命名空间,向部署者报告网络的覆盖质量, 实现网络的负载均衡和网络拓扑的自配置。无线传感网络实现节点定位基本思想 是通过测量射频信号强度、到达的角度、到达的时间等。目前主要的研究方向是 如何预先摆放一定量的专用定标节点(锚节点),其他普通节点随机摆放可以取

得更好的效果。另一个挑战是在两个距离很小的节点间如何估计其位置关系。 (3)安全问题 网络安全是网络研究中的一个重要问题,由于黑客、病毒越来越猖獗, 网 络安全不但成为一个技术问题,而且也成为一个社会问题。无线网络由于其传输 介质的特殊性,网络安全问题显的更为重要。据一项研究结果表明,无线协议存 在严重安全漏洞。黑客可以利用该漏洞通过设备来中断企业的整个无线网络连 接。目前无线传感网络的安全研究内容有物理层的高效加密算法、数据链路层抗 攻击的安全协议、网络层的安全路由协议以及运用层的密钥管理和安全组播方案 等等。 (4)能量问题 无线传感网络中节点由有限的电池供能,基于能源的计算显得尤为重要。从 程序运行的方式到数据通信的方式都要达到节约能量、空间和成本的最优化。对 于长寿命的应用,无论是节点本身还是通信协议的设计都需要不同模式的能源管 理,应该合理地在工作与休眠状态间切换。通过在系统软件体系,包括操作系统、 应用层以及网络层协议,增加能源有效性的设计理念,能大大延长传感网络的生 10 第一章绪论 命周期。能源有效性的 MAC 协议也是研究的一个热点。 传统的无线网络在 MAC 协议的设计上会以吞吐量、带宽利用率、公平性和延 时作为设计要点,而对于受到能源限制的无线传感网络而言,服务质量不是首要 的考虑因素,反而会因为节约能量而牺牲服务质量。 带有应答握手信号的循环冗余校验等通用错误检测技术在传感器网络中十 分有效。将数据链路层应答(节点对节点)和网络层应答(端对端)灵活地结合起来 便可实现满足性能要求的传输层功率,并达到期望的功耗水平。 (5)其它问题 在无线传感网络中,由于各个节点互相独立,只能通过无线链路进行通讯, 时间同步比较困难,而在一些运用场合如位置定位系统、跟踪系统等这个需求变 的很重要,针对这方面的研究也很多。除了传统网络的 NTP(Network Time Protoc01)时间同步协议之外,J.Elson 和 D.Estrin 提出了一种创新性的、简 单实用的同步策略 RBS(Reference Broadcast Synchronization),并分析了在 单跳和多跳网络中实现方法,同时在实际的声音定位系统中进行了运用,取得了 很好的效果。 定位跟踪作为无线传感网络的一个很有前景的应用领域,引起了人们极大的 研究热情。在全球的范围内有 GPS(Global Positioning System)定位系统,但对 一些小范围内,如室内环境,GPS 就无法发挥其功能,这就可以利用无线传感网 络来实现。 1.5 本文的结构安排 第一章为绪论部分,主要介绍无线传感网络体系结构、特点、应用、研究体 系及热点问题。 第二章主要介绍了目标跟踪系统的研究背景和意义,及基于无线传感网络的 定位跟踪系统的优势和研究现状。 第三章为定位跟踪系统中节能问题的研究,设计了覆盖保持的 k 一连通子集构 造算法,能够用较少的节点构造出一个既能满足网络的覆盖特性又能够满足 k 一 连通特性的节点子集。 第四章为定位跟踪系统中定位问题的研究,提出了集区域定位与点定位的一

体化的室内定位方法 AIT 方法。 第五章描述了本人负责开发的煤矿井下定位跟踪系统,主要介绍了服务器部 分模块的设计。 第六章对全文进行了总结。第二章无线传感网络中定位跟踪系统介绍 第二章无线传感网络中定位跟踪系统介绍 作为一种新兴的 IT 热点技术,无线传感器网络在军事与民用诸多领域有着 广阔的应用前景。在军事上,它可以应用于导弹防御、物质监测、作战车辆监测 等;民用方面,可以用于矿井下人员定位,交通管制等。因此目标跟踪是其最具 代表性和挑战性的应用之一。 本章主要对无线传感网络中的定位跟踪系统进行介绍。首先,从目标跟踪的 研究背景和意义出发,介绍了无线传感网络在目标跟踪系统中的应用优势,接着 给出了跟踪系统中定位算法的分类,同时对已有的定位跟踪系统进行了简单的介 绍,最后对定位跟踪系统应该考虑的几个问题进行了讨论。 2.1 目标跟踪的研究背景及其意义 目标跟踪技术无论是在军事还是在民用领域都有着重要的应用价值。目标跟 踪可从目标个数来分类,可分为单目标跟踪和多目标跟踪。跟踪方法主要有空间 跟踪和时间一空问跟踪两种。 2.1.1 研究背景 传统的跟踪系统是一个传感器(也称探测器)仅连续地瞄准和跟踪一个目标。 随着技术的发展和现代战略发展的需求,出现了一个传感器同时跟踪多个目标边 扫描边跟踪(Track-whi le-Scan,TWS)机制,并得到愈来愈广泛的重视(Akyildiz I eta1.2002;马祖长等,2004;崔莉等,2005)。在过去的 30 多年中,多目标 跟踪的理论和方法已经得到极大的发展,并成为当今国际上活跃的热门研究领域 之一,许多成果己经付诸工程实际(李建中等,2003)。 发展边扫描边跟踪(TWS)系统的目的是仅在一个传感器条件下同时跟踪多个 目标。为达到这个目的,边扫描边跟踪系统必须首先很好地跟踪单个目标。匀速 直线运动目标的跟踪与估计问题较为简单且易于处理。困难的情况表现在被跟踪 目标发生机动(Maneuvering),即目标的速度大小和方向发生变化的场合。因此 单机动目标跟踪(Single Maneuvering Target Tracking,SMTT)是多机动目标跟 踪(Mult iple Maneuvering Target Tracking,MhITT)的基础(李建中等,2003)。 2.1.2 研究意义 机动目标跟踪问题是一个受被跟踪目标运动约束的优化过程,所涉及的问题 12 第二章无线传感网络中定位跟踪系统介绍 是控制、信号处理、通信等技术发展的前沿问题,是国际上的热门研究方向之一 (李建中等,2003;崔莉等,2005)。机动目标跟踪理论在军事和民用领域都有 着广泛的应用。在军事上,它可以应用于导弹防御、空防、海防、区域防御和作 战监视等:民用方面,可以用于交通管制等。概括起来,机动目标跟踪的应用领 域包括(李建中等,2003;马祖长等,2004;崔莉等,2005): (1)防卫系统,包括:反弹道导弹的防御、空防预警、机载火力控制系统、弹 载系统、机载预警系统、战场监视系统、机载空地攻击系统、地面警戒系统、舰 载预警系统、舰载空海攻击系统、水下(声纳传感器)跟踪攻击系统等,以及海洋 监视(军舰或潜艇),战场监视(地面坦克或空中飞机和其它军用设备),精确制导, 低空突防等。 (2)空中交通管制(ATC)系统,用于各种飞行器军用、民用、私人的管理,包

括途中和终端地区管理、进场管理、防撞告警、碰撞回避等。 (3)海岸监视系统(MS),它与现代导航技术相结合,完成对狭窄航道和港口 的导航、避免船只的碰撞和在低能见度下维持正常航行。 (4)空间运动体的监视,随着空间卫星、航天飞机和空间站的发展,对空间 运动体的多目标跟踪已开始受到关注,这是一个新的待开发的研究领域。 (5)其它民用领域,包括动物迁拨监测研究、生物习性研究、医疗监测、智 能玩具、汽车防盗、城市交通管制系统等。 因此,对机动目标跟踪问题进行理论和应用研究,具有重大的理论和实际意 义。 2.2 无线传感器网络在目标跟踪中的应用优势 无线传感器网络在由军事转到民用之初,主要应用于环境监控,比如栖息地 监测等,随着研究的进展,无线传感器网络在目标跟踪应用中的优势越来越明显, 归纳起来,包括以下几点: (1)跟踪更精细:密集部署的传感器节点可以对移动目标进行精确传感,跟踪 和控制,从而可以更详细的显示出移动目标的运动情况。 (2)跟踪更可靠:由于无线传感器网络的自治、自组织和高密度部署,当节点 失效或新的节点加入时,可以在恶劣的环境中自动配置与容错,使得无线传感器 网络在跟踪目标时具有较高的可靠性、容错性和鲁棒性。 (3)跟踪更及时:多种传感器的同步监控,使得移动目标的发现更及时,也更 容易。分布式的数据处理、多传感器节点协同工作,使跟踪更加的全面。 (4)跟踪更隐蔽:由于传感器节点体积小,可以对目标实现更隐蔽的跟踪,同第二章无线传 感网络中定位跟踪系统介绍 时也方便部署应用。 (5)低成本:单个传感器节点的成本低,从而降低了整个跟踪的成本。 (6)低功耗:传感器节点的设计和无线传感器网络的设计都以低功耗为主要 目标,这使得在野外工作等没有固定电源或更换电池不便的跟踪应用更加便捷。 2.3 无线传感网络中的定位跟踪技术 无线传感网络中的定位跟踪技术包括两层含义:节点自我定位与移动目标定 位跟踪。节点自我定位属于网络中间件技术研究范围,属于网络体系的研究部分, 目的为网络路由层和更高应用层的服务提供包含节点位置的信息。移动目标定位 跟踪属于无线传感网络的应用层研究,利用网络中传感器节点间的协同信号处理 (Collaborative Signal Information Processing,CSIP)完成对运动目标的定 位跟踪。因此,节点定位是节点定位服务即目标定位跟踪的基础。 2.3.1 传感器网络中的节点定位 传统的定位机制常采用 GPS 系统,但是 GPS 系统无法在室内以及有遮挡物环境 下正常工作,同时能耗大、成本高以及体积大的特点限制了 GPS 在传感器网络中 的大规模应用。节点的自我定位研究作为传感器网络研究的基础问题,近年来不 断涌现大量的研究成果。根据定位过程中是否测量距离信息,现有的定位算法分 为距离相关(Range based)算法以及距离无关(Range free)算法(He Tet a1. 2003)。部分研究涉及移动节点辅助定位情况。下面将综述相关类型的典型定位 算法。 2.3.1.1 距离相关定位算法 距离相关定位算法通过测量相邻节点间的距离或者角度信息,并利用这些测 量信息来计算未知节点的位置。传感器网络中的测量技术可以广义的分成 3 类:

信号到达角度(Angle of Arrival,AOA)、信号强度(Received Signal Strength Indicator,RSSI)、距离测量相关。其中距离测量相关的测距技术包括:信号到 达时间(Time of Arrival,TOA)、信号到达时间差(Time Difference OnArrival, TDOA)等。 基于接收信号强度的 RSSI 澳']距机制:利用已知的发射点信号强度、接收节点 接收到的信号强度,计算出信号的传播损耗,利用理论或经验模型将传播损耗转 化为距离来测量距离(Hightower Jet a1.2001)。然而通过 RSSI 方式进行测距通常 不精确而且不可靠(Savvides A et a1.200 1;Whitehouse K 2002)。这是因为射频信 14 第二章无线传感网络中定位跟踪系统介绍 号受复杂的环境影响比较严重如:遮挡物及屏蔽等。基于信号到达时间的 TOA 测距 机制:根据信号的传播时间来计算节点间的距离。通常采用声音或者无线射频信 号,其精度较高。在文(Moore Detal.2004)中进行了详细的阐述。 基于信号到达角度的 AOA 测距机制:接收节点通过天线阵列或者多个超声波 接收机感知发射节点信号的到达方向,计算接收节点和发射节点之间的相对方位 或角度,再通过三角测量法计算出节点的位置。文(Van Vcen B.D and Buckley K.M 1988;Ottersten Bet a1.1993;Stoica Pand Moses RL 1997;)中对基于 AOA 预估算法 进行了详细阐述。 基于信号到达时间差的 TDOA 测距机制:发射节点同时发射两种不同传播速度 的无线信号,接收节点根据两种不同信号到达的时间差以及已知的两种信号的速 率计算两个节点问的距离。常采用声音信号与无线射频信号,因为声音的传递在 开放区域是简单而且可预知的,因此这种技术可以达到较高精度且所需成本低 廉,如只需要 MIC 以及扬声器即可。文(Priyantha NB et a1.2000)采用了这种 TDOA 技术。 典型的距离相关算法包括:极大似然法(Patwari Neta1.2003)、APS 算法 (Niculescu D and Nath B 2003)、基于 SDP 算法(Biswas P and Ye Y 2003)、多维尺 度 MDS 算法(Shang Y et a1.2003;Shang Y and Ruml W 2004)等。同下节的距离无关 定位算法相比定位精度更高,但是在传感器节点上需要额外增加硬件,定位成本 增加。 2.3.1.2 距离无关算法 距离无关算法不需要绝对的距离信息、角度信息或者其它物理测量值,但已 知节点的射频距离信息。该类算法对硬件要求简单,相对于距离相关定位算法, 虽然其定位误差较大,但是满足部分不需要位置精度很高的场合,是一类较为经 济的定位方法。因此对于大规模 WSN 来说是一类可行定位方案。其典型算法包括: 质心算法(Bulusu N et a1.2000)、DV-HOP(distance vector—hop)算法(Niculescu D and Nath B200 1)、Amorphous 算法(Nagpal R1999)及 APIT(approximate point—in—triangulation test)算法(He T et a1.2003)等。 质心算法由 Belusu 和 Heidemann 提出,算法采用将接收的信标点进行位置平 均的方法得到。DV-HOP 由 Niculescu 和 Nath 提出,测量一个节点到一个特定信标 点的最小跳数,然后估算平均每跳的距离。利用最小跳数乘以平均每跳距离,得 到未知节点与信标节点之间的估计距离,再利用三边测量法或极大似然法计算未 知节点的坐标。 APIT 近似三角形内点测试法算法由 He T 和 Huang C 提出,首先确定多个包含 未知节点的三角区域(三角的三点由 3 个 GPS 或者其它办法得到位置的信标点组第二章无线 传感网络中定位跟踪系统介绍

成),这些三角形区域的交集是一个多边形,它确定了一个更小的包含未知节点 的区域,然后计算这个多边形区域的质心,并将该质心作为未知节点的位置。 距离无关的算法定位性能受环境影响较小,不考虑积累误差情况可以满足许 多应用需要。 2.3.1.3 移动节点辅助定位 以上定位技术主要侧重于研究传感器网络中节点全部是静止节点情况。部分 文献开始研究传感器网络中有移动节点情况的定位方法。Sichitiu 和 Ramadurai (2003)在文献中最早应用单个移动信标点结合 RSSIN 量技术预估得到节点位 置。Sun 署 NGuo(2004)将图像领域去噪声的方法引入到网络定位提出基于分布式 非参数 Kernel 估计的节点定位方法,结合 TOA 测距技术得到节点位置。Galstyan et a1.(2004)在文献中提出一种粗粒度的距离无关定位算法,采用无线射频连 接度约束来降低未知节点未知的不确定度。文献(Pfiyantha NB et a1.2005)应用 刚性理论由移动节点预估定位未知节点位置。文献(Kuo.Feng Ssu ct a1.2005)通 过一种几何方法求解未知节点,选择分布在同心圆上的四个接收的信标点,两两 信标点间的垂直平分线的交点即为未知节点位置。nu 并 DEvans(2004)在文献中采 用顺序 Monte Carlo(SMC)方法对移动传感器网络的各个运动节点进行了定位。 2.3.2 无线传感网络中已有的目标跟踪系统 无线传感网络中的目标跟踪采用网络内位置已知的节点问的协同处理、定位 各时刻移动目标的位置,得到移动目标的运动轨迹。同传统的跟踪方式相比,将 无线传感网络用于目标的定位跟踪虽然面临诸多挑战,但优势同样明显。下面概 述主要的研究成果。 Gupta R.et a1.(2003)在文献中详细分析了基于传感器网络的目标跟踪过 程包括的三个主要阶段即侦测、定位和通告阶段。传感器节点以协作方式侦测和 跟踪目标,并通知位于目标预测轨迹附近的节点加入跟踪过程,同时将通信限制 在目标及其未来运动路线附近的节点。 Mechitov K.et a1.(2003)提出一种基于二进制传感器节点的目标跟踪方 案。各节点不能检测到与目标问的距离但是能确定包含目标的圆形区域以及目标 在所在区域的持续时间,通过多个节点协作得到一个重叠覆盖区域即为目标的位 置。这种方案通过部署大量简单廉价的传感器节点得到目标的轨迹,但是需要各 个节点位置已知,同时节点问的时间需要同步。 Zhao F.et a1.(2002;Chu Meta1.2002)在文献中提出一种消息驱动传感 器查询机制 IDSQ(Info 瑚 ation Driven Sensor Querying)。其核心思想就是基于 16 第二章无线传感网络中定位跟踪系统介绍 贝叶斯算法,利用传感器节点测量到的信息迭代预估得到目标位置。算法中下一 时刻用于信息融合的单个跟踪头节点选择是基于信息增益指标,如马氏距离、交 互信息、信息墒等。这种算法在每个定位时刻只激活一个头节点从而大幅减少参 加跟踪定位的节点数量,减少整个网络的能量消耗,但同时也降低了网络的容错 性和鲁棒性。 Liu J.et a1.(Liu Jet a1.2003)提出了一种对偶空间法用于跟踪一种连续 运动的面目标,如野外火灾的蔓延跟踪、台风行进路线的跟踪以及生化物质的扩 散跟踪等场合。 Ramanathan(2002)季 DBrooks(2002a;2002b;2003)等人提出了一种“位置中 心”的方法来进行协作感应和目标定位。当前节点对目标方向进行预估,并对目 标将要进入的固定划分的单元(cells)进行预警。预警单元内节点协同探测目

标的出现,分类器判断是期望的目标类型时,启动跟踪程序。另夕 bBrooks 等人还 提出了一些自组织分布式传感器网络的目标跟踪预测算法,其中预测技术采用了 信息素、贝叶斯以及扩展卡尔曼滤波技术。 Zhang W.etal(2004)提出的 DCTC(Dynamic Convoy Tree—based Collaboration)传送树跟踪算法,是基于网络通信角度研究目标跟踪。传送树是 一种由移动目标附近的节点组成的动态树型结构。并且会随着目标的移动而动态 的添加或者删除一些节点。移动目标附近的节点通过传送树结构进行协作跟踪, 在保证对目标进行高效跟踪的同时减少节点间的通信开销。算法依赖于传递树的 树型结构本身,强调于网络层领域。 Guo D.et al(2004)在文献中基于 SMC(Sequential Monte Carlo)框架下采 用辅助粒子滤波的方法解决目标跟踪中的融合问题,并基于最优墒的信息效用函 数选择下一时刻的用于融合的头节点。头节点选择所依据的效用函数计算异常复 杂,类似于 IDSQ,分布式融合中心基于单个激活节点。 Sheng X.et al(2005)采用分布式粒子滤波算法对目标进行预测与跟踪。 算法采用 EM 算法训练高斯混合参数,使其更加接近表达粒子本身。高斯混合模型 (Gaussian Mixture Model,GMM)的参数传递取代了粒子本身的传递,大大减少了 头节点间的数据通信,减少了能量消耗。尤其是需要提高定位精度,大量粒子需 要传递情况。 Xiao W.et al(2005)提出一种选择参与定位的传感器节点的自适应调度策 略。根据当前跟踪精度以及能耗成本动态调节跟踪采样的频率而不是采用固定的 跟踪周期。跟踪精度采用扩展 Kalman 滤波算法预估,能量消耗模型采用线性模型 来预估。寻求跟踪精度与能量消耗的一种最佳平衡。 Lee J.et al(2006)考虑一种非友好环境下距离不可测的目标跟踪问题, 17 第二章无线传感网络中定位跟踪系统介绍 提出了一种轻量级的、能量有效的基于距离比的迭代预估算法 RVI(Ratiometric Vector Iteration)定位算法。同时,文章提出了一种自适应汇报目标轨迹机制 以减少能量消耗。 上述大量相关工作主要集中于网络通讯的角度以及信号处理的角度研究目 标定位以及跟踪闯题,目前部分研究工作开始关注如何优化节点的布置方式,从 保证对移动目标的充分覆盖而不丢失目标的角度研究目标跟踪定位问题。 Megerian etal(2001;2002)研究了在给定的传感器区域中的移动目标的暴露 路径问题,属于反跟踪问题;而 Clouqueur etal(2002)采用一种传感器布置 策略来增大目标的探测概率,并采用一种相对标准来衡量这种策略的跟踪效果, 这里同时考虑设备成本和布置成本因素;Charkrabarty et al(2002)探讨了在 能保证目标穿越某个区域时能始终被跟踪到的所有传感器对这个区域覆盖的容 错问题;Jung,Sukhatme(2002)研究了传感器网络中通过移动机器人来跟踪定 位目标的问题。 无线传感网络在应用于目标跟踪系统时,具有许多优势,同时也带来了一些 挑战。比如,无线传感网络能量有限、定位精度不高等,因此如何构建一种能量 有效可靠精确的定位跟踪系统将是无线传感网络定位跟踪技术的研究中的重点 研究方向之一。 2.3.3 目标跟踪系统需要考虑的问题 当前的目标跟踪算法主要是针对不同环境下的单个目标跟踪,如何以最低的 能量代价实现精确的目标定位跟踪是各种算法的核心问题。此外,网络的可靠性

也是定位跟踪系统需要考虑的重要问题之一。 2.3.3.1 跟踪能量消耗 由于用无线传感器网络跟踪目标大都应用于实际环境,节点的能量消耗是一 个非常关键的问题。因而要求传感器节点不但能储备能量(电池),还要根据实 际情况现场蓄能(太阳能)。跟踪过程中选择合适的节点参与跟踪需要考虑该节 点的通信能量消耗、感测能量消耗和计算能量消耗,其中通信能量消耗是最主要 的部分(Pattem Set a1.2003)。在设计考虑跟踪算法时要综合平衡考虑这几种能 量消耗,找到合适的比重,以满足较低的能量消耗,从而延长节点和网络的寿命。 2.3.3.2 跟踪精度 在目前的无线传感器网络的目标跟踪常见算法中,目标的计算位置与实际位 置间不可避免地存在误差。提高跟踪的精确度更有利于实际的应用以及实际的需 要,但是并不意味着精度越高就越好。若要提高目标跟踪精确度,必然需要融合第二章无线 传感网络中定位跟踪系统介绍 较多节点的数据,这就会带来较高的能量开销。实际中需根据对结果精确度的要 求和能量消耗等各方面进行综合考虑。 2.3.3.3 跟踪的可靠性 网络可靠性差对跟踪目标有很大影响,当前应用于目标跟踪方法主要有集中 式和分布式。集中式方法要求所有网络节点在探测到目标后都要向汇聚节点发回 探测结果,不但引入的通信开销大,而且计算开销也增加很多,这样网络的可靠 性下降很快。分布式方法是一种较好的选择,但是也要充分考虑跟踪方法的鲁棒 性,能适应环境的变化,以增强网络的可靠性。 无线传感器网络由于其灵活性、成本低、易于布置等特性,在目标探测跟踪 领域会有广泛的应用前景。传感器网络目标跟踪涉及目标检测、定位、运动轨迹 预测、预警等重要问题。在研究过程中需综合传感器网络的自治性、低存储和计 算能力、数据传送的鲁棒性、通信延迟、可靠性等特点深入思考,并要在节省能 耗、增大测量精度、延长生存期等性能指标的提高上进行更深入的研究。 本文的目标定位跟踪系统主要针对以上问题中的跟踪能量消耗和跟踪精度 两个问题设计的。第一,针对跟踪能量消耗问题,本文设计了直接构造覆盖保持 的 k 一连通子集的构造算法 CPC 算法,通过较少的节点实现对目标区域的覆盖和节 点连通,其它节点则可以进入休眠状态,从而减少网络的能量消耗;第二,针对 跟踪进度问题,本文提出了在室内的精确定位跟踪方法 AIT,通过区域定位和点 定位机制能实现对移动目标在室内的精确定位跟踪。 第三章跟踪系统中能量有效问题的研究 第三章跟踪系统中能量有效问题的研究 构造无线传感网络中具有连通覆盖特性的节点子集是实现网络休眠调度、延 长网络生命周期的关键技术之一,具有重要的研究意义。已有的研究大多侧重于 k 覆盖节点子集构造问题,由于 k 覆盖子集在一定条件下便满足 k 连通,故人们 对 k 连通子集的构造问题研究较少,但通过构造 k 覆盖节点子集来实现 k 连通会 耗费过多的节点,代价较大。 本章提出了一个构造 k 连通 1 覆盖节点子集的算法——CPC,能够用较少的 节点构造一个既能满足网络的覆盖特性又能够满足卜连通特性的节点子集,从 而使得网络中其他节点可以进入休眠状态,节省整个网络的能量消耗,延长了网 络寿命。本章还对算法的正确性进行了严格证明,并通过仿真实验与相关算法进 行了性能比较。结果表明,与已有的 k 覆盖算法相比,CPC 算法能够节省约 55% 的节点数。

3.1 引言 无线传感网络是通过各类集成化的微型传感器协作地实时监测、感知和采集 各种监测对象的信息,这些信息通过自组织网络的方式传送到用户终端,从而 实现物理世界、计算世界以及人类社会三元世界的连通(刘敏钰等,2005),如 图 3.1 所示。无线传感网络是由大量的传感节点组成,而传感节点通常由电池供 电且不易更换。因此节能问题成为了无线传感网络的研究重点之一。 图 3.1 无线传感网络原理图 为了有效节约能量,已有的研究者提出了构造网络连通覆盖子集的节点调度 算法,即使用一个节点子集代替整个节点集合对目标区域进行完全覆盖,网络中 的其它节点则可以进入休眠状态,从而节省整个网络的能量消耗,延长网络寿命。 20 第三章跟踪系统中能量有效问题的研究 3.2 相关概念及定义 3.2.1 o 一 1 感知模型 无线传感器网络的连通覆盖问题通常与每个节点的感知模型及所有节点的 位置部署紧密相关。简而言之,传感器节点的感知模型构建了节点物理位置与空 间位置的几何关系,可以看作是传感器感知函数的服务质量的量度。传感器节点 的感知模型很多,依具体的应用环境又有很多的变形形式。经常用到的几种模型 有:0—1 模型、指数模型、统计模型、障碍模型等。本节着重介绍本文使用到的 O—l 感知模型。 一般而言,传感器节点的感知模型通常被简化为 O—l 模型:某点被节点覆盖 (用 l 表示)或没有被覆盖(用 0 表示)。在已有的无线传感器网络的文献中,最常 用的传感器 0-1 感知模型是感知圆盘模型——所有处于以某节点为中心、以定长 r 为半径的圆盘范围内的点被认作能够被该节点覆盖。假设在被监测区域的某个 节点 i 的坐标(t,f,),节点的传感半径为吒,目标的位置乃的坐标为(六,/,),则 节点与目标点的距离 Z, ,=√(‘-L)2+(f,-L)2。用 Ci,j 来表示 i 节点对 Z 的感 知质量,当被关注目标 Z 的位置在节点 i 的传感范围‘的圆内,认为节点 i 对关 注目标 Z 的感知质量为 1,即节点 i 对 Z 界的感知度为 1,否则当 r 在节点 i 的传感范围外时,节点 i 对界的感知度为 0,如表达式 3.1 所示为: 在早期无线传感网络连通覆盖研究中使用的节点感知模型一般都是 O—l 模 型,它忽略了一些外界因素的影响,使得问题更为简化,便于我们对问题更深一 步的研究。 3.2.2 覆盖 无线传感网络是自组织网络,活跃节点的覆盖度直接影响到监测和传感的区 域。无线传感器网络最重要的功能是网络对物理世界的感知能力, 所以覆盖度 可以视为对传感器网络服务质量的度量。 对于一般的覆盖问题,定义:给定目标监测区域的每个位置,当且仅当网络 中任意的 k-1 个节点发生故障的情况下,该位置仍旧被至少一个节点覆盖,则称 该网络为 k 一覆盖;如果 k=l, 则称为该位置被覆盖。覆盖问题可以分为区域覆 盖、 点覆盖和栅栏覆盖。本章涉及的覆盖为区域覆盖。 21 急 J 8 矿们 h O = C 第三章跟踪系统中能量有效问题的研究

区域覆盖:目标区域中的任意一点能够至少被一个工作节点覆盖。 3.2.3 连通 由于无线传感网络是一种自组型网络,大量节点之问需要通过无线多跳方式 直接或间接地相互通信来协同工作。网络的连通性将有效保证自身无线多跳自组 织通信的开展, 并直接决定了无线传感网络感知、监视、传感、通信等各种 服务质量的送达汇聚节点。 对于一般的连通问题,定义:当且仅当网络中任意的 k-1 个节点发生故障的 情况下,剩余节点间仍旧保持连通,则称网络是 k 一连通的,如果 k=1,则称 该网络是连通的。 3.2.4(a,b)连通覆盖 为了便于描述,我们定义(a,b)连通覆盖是指网络满足是 a 一连通与 b 一覆 盖的; 3.3 已有的研究成果 目前,针对网络的连通覆盖子集的构建问题的研究已经取得了一些成果。如 在文献(Gupta H et a1.2003)和(Bai X et a1.2006)中提出了(1,1)连通覆盖算 法,但该算法不满足网络容错连通的功能。由于传感节点的脆弱性与不可靠性, 因此,对于(1,1)连通覆盖的无线传感网络,当因灾难或其他意外情况发生而 导致网络中某些节点发生故障或损坏时,可能导致网络的断裂,极大地减弱网络 的监测功能。如图 3.2 所示:目标区域 A+B,所有节点构成一个(1,1)连通覆 盖图,若节点 S 发生故障,区域 B 中节点收集到的数据将无法发送到服务器,即 区域 B 中的节点将全部失效。而在文献(Zhou ZH eta1.2004)与(Abrams Zet a1. 2004)中则提出了基于分布式贪心算法的 K 一覆盖算法,在文献(Hefeeda Mand Bagheri M2007)、(wan Pand Yi C2006)和(Hefeeda M and Ahmadi H2007)中提 出了基于概率的 K 一覆盖算法。其中,文献(Hefeeda M and Ba,gheri M2007)和(Tian Dand Georganas N2004)又探讨了 K 覆盖与 K 连通的关联,即在一定条件下满 足 K 覆盖便可满足 K 连通。虽然上述 K 覆盖算法可以解决容错连通问题,但在一 般情况下,连通半径大于覆盖半径,故 K 覆盖较 K 连通将需要更多的传感节点, 即代价较大,且实验部分的仿真结果也验证了该结论。 本章则提出了覆盖保持的 K 一连通子集构造算法(Coverage—Preserving 第三章跟踪系统中能 量有效问题的研究 k-Connected Subset Construction Algorithm),简称 CPC 算法,该算法构造的 节点子集能覆盖整个区域,且能保证 K 连通,因此,当网络中某些节点发生故障 或损坏时,只要受损的节点数不超过 K-I,则受影响的仅仅是故障节点的覆盖范 围,而网络中其他节点收集的数据仍能传递到服务器。 图 3.2 一般的无线传感网络 本章的主要贡献就在于:第一,首次提出了直接构造(K,1)连通覆盖子集 的 CPC 算法,并通过该算法解决了无线传感网络中在某些节点损坏的情况下如何 保证网络仍旧连通的问题。第二,我们还通过仿真实验同已有的 K 覆盖算法进行 比较,实验结果表明 CPC 算法在节点密度、连通半径和覆盖半径都相同的情况下, 能够以更少的节点构造出(K,1)连通覆盖网络。 3.4 问题模型 3.4.1 前提假设 本文基于圆盘信号传播模型进行研究,节点的覆盖面积是指以节点为圆心, 感知距离为覆盖半径的圆,且所有节点的覆盖半径相同。节点的连通区域是指以

节点为圆心,通讯距离为半径的圆,且所有节点的通讯距离相同。 被探测区域用 Region 来表示,区域内的所有传感节点用 N 来表示;节点 a 第三章跟踪系统 中能最有效问题的研究 与节点 b 之间存在一条边当且仅当节点 a 与节点 b 能够通讯。 3.4.2 问题定义 对任意传感器节点 i,a(i)表示该节点的覆盖区域,目标区域 Region 所覆 盖的区域用 A 表示,在集合 N 中寻找一个最小子集 M,该子集满足下列 2 个条件: 1、A∈U a(i); f∈M 2、在 M 中选出任意集合 z,X=“,z2,.,zN},葺∈M,1≤i≤K-1,M—X 依 .. 旧连通。 3.5 算法描述 CPC 算法的主要思想是:首先构造(1,1)连通覆盖的网络,然后以此为基 础,按照一定规则增加节点,逐步实现连通度的递增,最后实现(K,1)连通覆 盖的网络。 3.5.1 算法设计 在算法执行之前,先对节点集合 N 进行预处理,将区域内所有度数小于 K 的节点从节点集合 N 中去除。一个节点集合是 K 连通的必要条件:节点集合中所 有节点度数都大于等于 K。故节点集合 N 中度数小于 K 的节点必不在将要构造的 K 连通集合中,将这样的节点去除也可以减小后续算法的运算规模。 算法第一步,构造一个(1,1)连通覆盖的集合 M。(1,1)连通覆盖集合 的构建方法可参考文献(Gupta H et a1.2003)或文献(Xing G et a1.2003)中所提 供的构建算法。 算法第二步,在(t,1)连通覆盖集合 M 的基础上构造出(t+1,1)连通覆 盖集合(0<t<K)。 M 为(t,1)连通覆盖集合,从集合 N—M 中选出与 M 中至少 t 个不同节点相 邻的节点,构成集合 Candidate(M)。在 Candidate(M)中找出最小的卜连通子 集 S,使得 M 中每个节点至少与 S 中的一个节点相连。将 S 与集合 M 合并成新的 集合 M,t 值加 1。循环执行,直至找不到满足条件的集合 S 或构造出(K,1) 连通覆盖集合为止。 算法第三步,若最终构造出(K,1)连通覆盖集合,则返回真,否则返回假。第三章跟踪系统 中能量有效问题的研究 图 3 为 CPC 算法执行的二个实例:如图 3.3(a)所示,初始时 M 为(1,1) 连通覆盖集合,M 包含节点{A,B,C},SR 为覆盖半径,矩形区域 REGION 为目 标区域;如图 3.3(b)所示,经过步骤二的一个循环,找到子集 S 包含节点(D, E),将 M 和 S 合并,得到新的 M 为(2,1)连通覆盖集合,包含节点(A,B,C, D,E):同理,如图 3.3(c)所示再经过步骤二的一个循环,找到子集 S 包含节 点(F,G),将 M 和 S 合并,得到新的 M 为(3,1)连通覆盖集合,包含节点 fA, B,C,D,E,F,G}。 图 3.3(a) (1,1)连通覆盖集合 图 3.3(b) (2,1)连通覆盖集合 图 3.3(c) (3,1)连通覆盖集合第三章跟踪系统中能虽有效问题的研究 CPC 算法伪代码 f Step0:N=N—Y: 其中 Y 为网络中度数小于 K 的节点集合

Stepl:利用文献(Gupta H et a1.2003)或文献 ()(ing Geta1.2003)所设计的算法构造初始集 M,要求 M 满足(1,1)连通覆盖; Step2:Fort=1 to K-1{ l、构建候选集合 Candidate(M),初始为空集; ForeachIillM 的相邻节点 IfI 至少与 M 中 t 个不同的节点相邻 then Candidate(M)=Candidate(M)+{I); 2、从 Candidate(M)qb 找出最小的 1.连通子集 S,使得 M 中每个点至少与 s 中的一个点相连; If S 不存在 thenbreak; 3、M=M+S: ) Step3:if(t<K)Return False else Return True。 } 3.5.2 算法的正确性证明 图 3.4CPC 算法描述 引理 1:CPC 算法中若 M 是 t 连通的,则 M+S 是 t+l 连通的。 证明:由 K 连通的定义可知,若删除 M+S 中的任意 t 个点,剩余的点依旧连 通,则 M+S 是 t+l 连通的。 若删除的 t 个点都在 M 中,因为 M 中的所有点都与 S 是连通的,而 S 本身是 l 连通,故 M 中剩余的点之间依旧连通。 若删除的 t 个点中 t-n(n=l,2,?t)个点在 M 中,n 个点在 S 中,因为 M 是 t 连通的,故删除 t-n 个点后,M 中剩余的点依旧是连通的;对于 S,由于 S 中的每个点都与 M 中 t 个不同的点相连通,故在 M 被删除 t-n 个点后,S 中每个 的点依旧与 M 中至少一个点相连,因此,S 中剩余的点之间依旧连通。 综上所述:M+S 是 t+l 连通的。 定理 l:若 CPC 算法返回值为真,则所得的节点集合 M 是(K,1)连通覆盖 的。 证明:由算法中 Stepl 可知:初始时 M 是(1,I)连通覆盖的,再由引理 l 可知:算法在 Step2 中每循环一次 M 的连通度增加 l,当算法最终返回真时,M 的连通度显然已经增加到 K 了,由此可知,当算法返回值为真,则所得的节点集 合 M 是(K,1)连通覆盖的。第三章跟踪系统中能帚有效问题的研究 3.6 实验模拟 为了评估本章提出的 CPC 算法,我们通过仿真程序先对影响算法性能的因素 (如连通半径与覆盖半径的比值、节点密度)进行分析,再与文献(Zhou ZH ct a1.2004)中的分布式贪心算法(Distributed Greedy algorithm,简称 DGA)进 行性能比较。结果表明:与 DGA 算法相比,由 CPC 算法构造 K 一连通覆盖子集能 节省约 55%的节点。 3.6.1 实验环境描述 由于算法没有涉及到网络路由层和 MAC 层,所以我们在 Visual Studio 2005 平台上实现了一个仿真程序来模拟上节描述的算法。仿真环境的具体配置如下: 模拟的目标区域为 50m*50m 的方形区域,在该区域内随机地布置 120 个节点,

图 3.5 为仿真程序随机生成的一次节点位置图及初始的(1,1)连通覆盖子集。 仿真程序中我们假设所有节点是同构的,即所有节点的连通半径 Rc 相同,覆盖 半径 Rs 也相同;在实验中节点的覆盖半径固定为 lOm,节点的连通半径可变且 大于等于两倍的覆盖半径。考虑到无线传感网络的实际应用情况,且不失一般性, 我们的实验数据都是通过多次运行仿真程序取平均值获得。 o 普通节点 ●(1,1)连通覆盖子集的节点 3.6.2 实验结果及分析 图 3.5 节点位置示意图第三章跟踪系统中能帚有效问题的研究 在本小节中,我们将给出实验仿真结果,并对实验结果进行比较分析。首先, 我们固定节点覆盖半径为 lOm,节点密度(节点总数/区域面积)为 0.048,分别 观察 Rc/Rs 比值在 2,2.2,2.5,3.0 时,随着连通度 K 的变化 CPC 算法所需的 节点个数的变化,如图 3.6 所示。从图中可以看出:节点密度固定的情况下,连 通度 K 相同,Rc/Rs 值越小,所需的节点数就越多;节点密度固定的情况下,Rc/Rs 值越大,所能达到的最大连通度也越大。从 Rc/Rs=3 时的线性拟合曲线可以看出, 连通度的增加与所需节点数目的增加趋于线性关系。 /一、 七 、_, 辐 七 《 粑 K 图 3.6 节点密度为 0.048,Rc/Rs 比值不同的情况下,所需节点个数随连通度 K 的变化图 接着,仿真程序固定连通度 K 为 3,Rc/Rs 比值为 2,通过改变目标区域内 的节点总数,来观察在不同的节点密度下,CPC 算法所需的节点个数,如图 3.7 所示。从图中可以看出:在 Rc/Rs 固定的情况下,节点密度越大,达到相同连通 度 K 时算法所需的节点数越少。从图中曲线的变化趋势可以看出:当节点密度达 到一定程度时,算法所需的节点数将不再减小,此时节点数趋于最优值。第三章跟踪系统中 能量有效问题的研究 50 45 ^40 七 V35 籁 <--30 《 舡 25 20 15 节点密度(个/平方米) 图 3.7 连通度 K=3,Rc/Rs=2 时,所需节点个数与节点密度的关系的对数拟合图 最后,我们固定节点密度为 0.048,节点覆盖半径为 lOm,Rc/Rs 比值为 2.2, 通过改变连通度 K,来比较文献(Zhou ZH et a1.2004)中的 DGA 算法和 CPC 算法 的性能。DGA 算法是构建 K 覆盖的算法,但依文献(Zhou ZH eta1.2004)中的定

理 3 可知,当 Rc/Rs 大于等于 2 时,K 覆盖便可满足 K 连通。从图 3,8 中可以看 出:与 DGA 算法相比,由 CPC 算法构造 K 一连通覆盖子集能节省约 55%的节点。这 也验证了与 K 覆盖算法相比较,CPC 算法需要的传感节点更少的结论。 2 图 3.8 节点密度为 O.048 时,Rc/Rs=2.2 时,DGA 算法和 CPC 算法所需节点数随连通度 K 的变化图 3.7 本章小结 ∞∞∞阳∞∞们∞加加 0 ^七一藕蛭铲第三章跟踪系统中能最有效问题的研究 本章针对无线传感网络中因节点发生故障而导致网络不能正常工作的情况, 提出了直接构造(K,1)连通覆盖网络的 CPC 算法,该算法解决了无线传感网络 中在某些节点损坏的情况下如何保证网络仍旧连通的问题,构造出一个节点子集 代替整个节点集合对目标区域进行完全覆盖,网络中的其它节点则可以进入休眠 状态,从而节省整个网络的能量消耗,延长网络寿命。最后通过实验模拟的方式, 表明算法能以较少的节点来构造(K,1)连通覆盖子集。在节点发生故障的情况 下,网络虽然仍旧连通,但网络将不再具有(K,1)连通覆盖的特性。所以,如 何在节点发生故障后,启用休眠节点将网络恢复成(K,1)连通覆盖的网络就成 为我们下一步将要研究的重点。第四章跟踪系统中定位问题的研究 第四章跟踪系统中定位问题的研究 随着无线传感网络的飞速发展,基于无线传感网络的室内定位算法越来越吸 引研究者的目光。然而,现有的室内定位算法侧重于对移动目标的直接定位,而 忽略了移动节点的区域信息。在室内环境中,由于建筑结构的复杂度大,而且室 内的射频传播特性受到多径干扰等现象的严重影响,因此采用直接定位的方法的 定位精度不高,而一个小的定位误差可能使得移动节点最后的位置处于不同区 域。若我们知道正确的区域信息,那么这样的错误是可以避免的。事实上,在某 些应用(如博物馆导游,火灾监测等)中,区域信息也是用户的一个重要需求。 针对于此,本章提出了基于 RSSI 信号的室内定位方法 AIT。该方法首先通过 区域定位算法 BCA 确定移动节点处于哪个区域,然后再通过点定位算法 SGLS 对移 动节点在该区域内进行精确的点定位,确定移动节点在区域内的具体位置。其中 区域定位算法 BCA 提出了基于区域关联图的概念,设计了精确的区域判定机制; 点定位算法 SGL 提出了基于格划分的概率定位算法,有效提高了定位精度。同时, AIT 方法适用于不同规模的区域,因此适用范围更广。实验结果表明 BCA 算法将 MERIT 系统的区域定位准确度从 71%提高到 86%,而 SGL 算法与 Ecolocation 算法 相比减少了 32%的定位误差。 4.1 引言 室内环境是与人类生活生产关系最密切的场合,室内位置服务存在大量应用 需求,室内定位技术是近年研究的难点和热点。目前,全球定位系统(Globe Positioning system,GPS)(Getting I1993)己大量应用于民用领域中,如车辆监 控和汽车导航。但 GPS 采用的微波信号极易被浓密树林、建筑物、金属遮盖物等 吸收,因此不适合室内环境使用。对于室内定位应用,基于广泛普及的 WLAN、 Wi-Max 等己有硬件设施,通过增添软件模块提供多样的室内定位服务也有众多 尝试(Balll P and Padmanabhan VN 2000;Ji Y eta1.2006)。但是,wLAN 定位系统存 在过于依赖基础设施、功耗过大等弱点。

无线传感器网络的出现为室内定位系统提供了一种富有竞争力的解决方案。 由于无线传感器网络具有电池供电、机动部署、自组织组网、不依赖固定设施等 特点,因此基于无线传感器网络的室内定位技术拥有良好的应用前景(LeeYW et a1.2006)。例如,将无线传感器网络部署在仓库跟踪物流动态,临时部署在火灾 救护现场为消防员提供最优路线导航(Lorincz K and Welsh M2005)。 第四章跟踪系统中定位问 题的研究 确定用户的位置是上下文感知(context-aware)计算的重要问题之一。上下 文感知系统可以感知时问、位置、温度以及相关资源来处理当前态势。更进一步, 此类系统可以利上下文变化来适应系统的行为,而无需用户的干预。在这种系统 中,没有位置信息的感知数据是没有价值的。知道目标的位置可以帮助系统在正 确的地点做正确的事。 虽然已经有一些室外的定位系统,但在室内环境中,由于建筑结构的复杂度 大,而且室内的射频传播特性受到多径干扰等现象的严重影响.因此,室外定位 系统不能简单地移植到室内环境,需要针对室内环境的特点,重新设计适用于室 内的定位系统。 本章中,作者提出一种名为 MT 的基于 RSSI 信号的室内定位方法。本方法 的特点如下:首先,不同的室内定位应用对定位精度的要求不同,因此,AIT 提 供了两层次的定位精度:区域定位级与点定位级,前者用于区分目标处于哪个房 间或者走廊,而后者用于在某一具体房间内确定目标处于房间内的具体位置。其 次,所有传感器节点只需保存部分邻居节点的数据,而无需全局信息,因此该方 法具有较好的可扩展性。本章假定所有的锚节点(Beacons)的位置坐标已知,这 个假定在系统建立阶段容易被满足。 本章的主要贡献是: (1)提出拥有两层次定位精度的室内定位方法:区域定位和点定位,适应 于不同的应用需求; (2)区域定位算法 BCA 提出了基于区域关联图的概念,设计了精确的区域 判定机制;点定位算法 SGL 提出了基于格划分的概率定位算法,有效提高了定位 精度: (3)在 AIT 方法中执行这两个算法并与已有的工作进行比较,实验结果表 明 BCA 算法将 MERIT 系统的区域定位准确度从 7 1%提高到 86%,而 SGL 算法与 Ecolocation 算法相比减少了 32%的定位误差。 (4)对区域大小没有限制,易于扩展; 4.2 相关工作 为了提供可靠的室内定位服务,研究者们进行了许多努力。Active Badge 定位系统(Gibbons Jet a1.1992)是一种早期的用户跟踪系统。建筑物中布设传感 器组成的有线网络,这些传感器能够捕获用户发出的独特红外编码.选用红外信 号是由于它不能穿透办公室建筑物内的隔离墙的特性。但有线布置与无线相比灵 活性不足,不易于扩展。 32 第四章跟踪系统中定位问题的研究 Cricket 位置支持系统(Pfiyantha NB et a1.2000)使用射频和超声波信号两种 信号,来获得准确的测距。锚节点固定在预先选定的位置上,同时发出射频和超 声波信号。移动目标,即接收者(Listener),通过计算射频信号与超声波信号的 接收时间差估算离参考节点的位置。这样,接收者很容易通过三角测量法 (Triangulation)估计自身的位置。

以上两种技术需要接收者和发送者之间的视距传输(Line—Of—Sight,LOS) 且传输距离有限。射频信号具有较远的通信距离和非视距传输能力,且随着 Wi-Fi 和无线传感器网络技术的发展射频信号变得越来越普遍,因此是一种非常 具有前途的传输介质,在室内定位系统中已被广泛采用。 RADAR(Bahl P and Padmanabhan VN 2000)使用射频信号进行位置估计。文献 (Bahl P and Padmanabhan VN 2000)采用了两种估计方法。第一种称为经验法,需 要现场测量来构建信号数据库。运行时,系统将测量所得的信号与信号数据库匹 配得到位置估计。第二种方法忽略了现场测量而使用某种射频信号传播模型来估 算目标的位置。但是,由于射频信号传输的多径效应,传播模型非常不准确,从 而影响了定位结果的准确性。 研究者还提出了许多基于 Wi_Fi 的定位系统,这些系统也可以按照其信号处 理方法被分成两类。基于模型的方法收集射频信号强度(RSS)测量值来推算目标 和参考点之间的距离,然后应用三角测量法得到目标位置(Lim H et a1.2006)。 另一类方法先通过现场测量和信号预收集建立 RSS 电子地图,再使用不同算法计 算目标位置(Ji Y et a1.2006)。 基于 Wi-Fi 的定位系统依赖于电气基础设施或网络基础设施,因此不能部署 在无基础设施的环境中,例如仓库或温室中。甚至在办公室等有基础设施的环境 中,无线接入点(AP)的使用仍然受到限制。因此,基于无线传感器网络的定位方 案成为一种非常有吸引力的选择。 MoteTrack(Lorincz K and Welsh M2005)将无线传感器网络引入到室内定位 服务中,系统部署方便,网络具备自组织、可重构特性,可应对基础设施损坏, 鲁棒性强,并根据需要方便加载传感器模块,特别适合火灾救护等危险场合。 MoteTrack 针对高危环境中易出现的节点意外失效和信号丢失等情况设计了高 鲁棒性定位算法。针对信号丢包、扰动问题,参考节点周期性对比邻居参考点信 息估计本地丢包率,动态选择(双向或单向)信号匹配标准;针对节点失效,将 RSS 信息均衡分配到参考节点中,形成分布式存贮增强鲁棒性;系统定位算法的 执行动态放在目标附近节点上进行,避免了因基站被破坏造成的系统瘫痪。 采用历史数据建立的参考信息库不能体现实时环境波动,LANDMARC(Ni L M eta1.2003)的采用 RFID 技术思想,用活性参考标签替代离线数据采集,其动态第四章跟踪 系统中定位问题的研究 参考信息能更实时捕捉环境变化,提高定位精度和可信度。活性参考标签的应用 去除了每个测试点数百次的人工数据采集,且能更好适应室内环境波动,提高定 位精度,此外系统还具备 RFID 高速信息传输及高能效特性。尽管如此,由于参 考标签的传输距离受到多方因素影响,标签部署对定位精度影响较大,而部署情 况与室内布局关系密切,没有统一解决方案;另外由于系统需调节目标发射功率 级别估计距离远近,该过程不仅影响精度,而且造成一定时滞。 MERIT(Lee Yw eta1.2006)系统为用户提供房间级的精度,它集成了两种技 术:空间多样性和射频反射器。它能达到较高的房间区分精度。 Ecolocation(YedavaUi K et a1.2005)通过考察多个参考节点上的 RSS 测量值的平 均值排序关系来确定未知节点的位置。但通过我们的测试,MERIT 系统在走廊区 域和两个相连区域的边界位置效果较差。此外,MERIT 系统不适合于不同大小的 区域的定位。 本章的主要工作是提出了集区域定位与点定位的一体化的 AIT 方法。该方法 首先通过区域定位算法 BCA 确定移动节点处于哪个区域,然后再通过点定位算法

SGL 对移动节点在该区域内进行精确的点定位,确定移动节点在区域内的具体位 置。一旦确定移动节点所处的区域,则点定位时将只使用该区域内的锚节点信息 进行定位,这样可以提高点定位的精度。同时,AIT 方法没有区域大小必须相同 的限制,适用范围更广。实验结果表明 BCA 算法将 MERIT 系统的区域定位准确度 从 71%提高到 86%,而 SGL 算法与 Ecolocation 算法相比减少了 32%的定位误差。 4.3 室内定位系统设计 本节首先描述基本的实验环境设置,然后给出 AIT 方法的设计和实现,包括 系统结构,区域定位算法和点定位算法,最后通过实验结果比较 AIT 方法与 MERIT 系统的定位性能。 4.3.1 环境简介 实验测试平台建立在中国科学技术大学苏州研究院亲民楼 3 楼。实验使用 CrossBow 公司生产的 MicaZ 节点,它们使用低功耗射频收发芯片 CC2420 互相通 信,通信频率为 2.4GHz。网关节点连接到 MIB510 编程板,编程板再通过 RS232 串口向所连服务器(笔记本或台式机电脑)转发消息。节点端代码使用 TinyOS 环境中开发的程序,服务器端代码使用 Visual Studio 2005 平台下的 C#语言开 发的程序。第四章跟踪系统中定位问题的研究 4.3.2 系统结构 AIT 方法包含五个类型的设备:锚节点,移动节点,路由节点,基站和服务 器,如图 4.1 所示。在 AIT 方法中,办公楼中预先部署静止的 MicaZ 节点。典型 的部署方式是在每个房间的四个角各部署一个节点,这样的部署方式可以最大程 度减少用户的使用难度。走廊中的节点部署方式要取决于建筑物的布局情况。这 些静止节点作为锚节点,具有唯一的 ID 和用户指定的坐标。在当前的实现中, 所有锚节点的 ID 和坐标都是在启动阶段分配的,存于服务器端。然后系统以完 全分布方式运行,锚节点自发地维护整个网络的多跳路由并与其它锚节点协作完 成定位包从移动节点到服务器端的传递。所有定位算法的实现是由服务器端实 现。 在进行定位之前,先将所有锚节点打开,锚节点将进行多跳路由的组建,该 过程需要 2-3 分钟。路由算法使用的是 TinyOS 操作系统自带的路由算法。在多 跳路由组建完毕后,系统进入正常的工作状态,能对进入定位区域的移动节点进 行定位。 锚节点周期性的广播检测包(DCT),包中包含的锚节点的 ID(该 ID 是唯一 的),探测信息包的序列号等信息。每个被跟踪的目标身上都携带一个移动节点 或 PDA。移动节点接收到 DCT 包后,对该包进行解析,从中获得 RSSI(Received Signal Strength Indicator)值。在经过一个周期性的延迟后,移动节点将接 收到的所有锚节点的 RSSI 信息封装到一个包中,并将该包发送给最近的路由节 点。路由节点在接收到移动节点发送过来的 RSSI 信息包后,通过多跳路由的方 式发送到基站。当基站接收到 RSSI 信息包时,它会立即通过服务器的 COM 端口 将该包传递给服务器。服务器接收到 RSSI 信息包后,首先将其解析,服务器将 通过我们设计的区域决策算法和点定位算法对解析后的 RSSI 信息包进行处理, 得出移动节点的实时位置。第四章跟踪系统中定位问题的研究 锚节点 4。3.3 区域定位算法 图 4.IAIT 方法体系结构 直观上说,人们很容易区分不同的房间。但是,由传感器节点自动完成房间

区分任务并不容易。首先,选择目标能侦听到属于同一房间的锚节点最多时所对 应的房间 ID 不是一个好主意,这是由于走廊中部署的锚节点个数少于房间内部, 若采用此方法则区分结果为走廊的概率较低。其次,信号模式匹配方法对内存带 来极大的负担并且需要繁琐的地图构建过程。再次,无法预知的建筑物布局使得 传感器部署非常复杂。找到一种不严格依赖于传感器布局的定位方法非常有意 义。 在室内空间,有许多自然分割的墙壁, 挡板或门等等。根据我们的测试, 当信号穿过墙壁时 RSSI 值将衰减,并且在走廊上 RSSI 值有较大的波动。在下面 的叙述中,一个独立的房间或走廊被称为一个区域。基于实际 RSSI 信号的测试 取样,我们发现 MERIT 系统不适合于不同大小区域的定位。此外,这一系统在走 廊或两个连接的区域的边界附近定位效果很差。针对于此,在本节中我们提出了 一种新型的区域决策算法,能有效的解决不同大小区域的定位问题,并能准确的 对走廊区域及两个连接的区域的边界附近进行定位。第四章跟踪系统中定位问题的研究 在设计区域决策算法之前,我们先在实际的环境中进行 RSSI 信息的采样。 锚节点的放置位置和采样点的位置如图 42 所示。基丁采样后的结果,我们设计 了 BCA 算法用于区域决策。 剧 42 锚节点房子位置,圆点表示锚节点位置.方块表示 RSSI 采样值置 豳 43 锚甘点关联粜台不露 BCA 算法包含三个步骤。第一步,为每个锚节点构造锚节点关联集合 C(u), c(u)包含所有与锚节点 u 相近且在不同区域的锚节点。咀图 4 3 为例,c(1)={5, 9,10J,C(6)={4,10)。锚节点关联集合 c(u)的建立也可以通过 RSSI 值的比 较来实现。具体方法是:每个锚节点通过比较附近不同区域锚忸点的 RSSI 值来 决定哪个锚节点离自己最近。虽然 RSSI 值的测量的不是绝对可靠的,即两个节第四章跟踪 系统中定位问题的研究 点间的 RSSI 值最大并不表明它们之间的距离最短,但在大多数情况下,两个节 点间的 RSSI 值最大表明它们之间的距离最短是正确的。 第二步,以第一步为基础,找出移动节点可能处于的一个或几个候选的区域。 假设最大 RSSI 值为?蜮,我们选择 RSSI 值不小于?馘一 6,其中万为预先定义 好的常数。形式化描述为: B 脚={ulRssz(.)≥rm 觚一万} (4.1) 在实际执行过程中,如果?。 ,大于 190,那么艿取为 8。否则,6 取为 5。 因此,移动节点可能在的候选区域为: f’么=l J 么(甜),铭∈B 脚 (4.2) 其中,A(u)表示锚节点 u 所在的区域。现在我们要做的就是从移动节点可能 在的候选区域集合 PA 中找出移动节点实际所在的区域。直观的讲,如果移动节 点是靠近锚节点 u 的,那么它一定也靠近锚节点 u 的锚节点关联集合!对于集合 BMR 中的任意锚节点 u,我们计算集合 C(u)中的最大 RSSI 值: 形(“)=Max{RSSI(v)11,∈c(“),彳(V)磋,么} (4.3) 通过这些步骤,我们获得了具有最大权重的锚节点,它就是区域决策算法的 最终结果。整个区域决策算法的伪代码描述如图 4.4 所示。 4.3.4 点定位算法 图 4.4 BCA 算法伪代码描述 在确定了移动节点所在区域后,我们下一步的目标是确定移动节点在该区域 内的精确位置。通过 BCA 算法我们获得了移动节点所在的区域,因此,我们从第四章跟踪

系统中定位问题的研究 RSSI 信息包中只选择在该区域的锚节点的 RSSI 信息对移动节点进行点定位,这 样可以帮助我们减少定位错误。 众所周知,由于多路径损耗的影响,在某个距离上接收到的信号功率是个随 机的值。屏蔽模型将理想的圆形模型扩展为更合适的统计模型:节点以某个概率 在信号有效范围的边缘进行通信。屏蔽模型的形式化描述如下: [怒]as=-10a log(鲁 oo,+? @4, 其中 P(J)在距离为 d 时的接收功率,仪为路径损耗指数,如为单位为 dB 且服从高斯分布的 随机变量。R(dv.Ⅳ)表示锚节点 u 到移动节点 v 的 RSSI 值, 相应的接收功率为: P(4, “)=10 尺‘训 1。 (4.5) 假设移动节点 v 从锚节点“1 和锚节点扰 2 接收到的 RSSl 分别用 Ry, “。和 Rv 心表示,则我们有: 忙篡一 2 =1 O(R#2-Rv,ul+Xul 一瓦 2)/(10a) (4.6) 根据等式(4.6), (4.7) 我们定义一个新变量缈=lg(d, “。/玩心),并且用另一个变量 x 表示 h 一%,因此,等式(4.7)可转化为: 矽(x)=(Rv 托一 Rv 柏+x)/(1 Oa) (4·8) 基于上述分析,我们提出了 SGL(shadowing-grid localization)算法。 首先,我们将目标区域划分成 NxN 个网格,对于移动节点 v,我们假设 v 到锚 亟?第四章跟踪系统中定位问题的研究 节点“1 和掰 2 的 RSSI 值用 R,期和风胁表示。不失一般性,我们假设 Rv,毪≥Rv 心,对于等式(4.8), 。巍们计叠锄望距离比卢: 卢=E 净)=10(R 川吨屹)/(10 晓) (4.9) 我们用网格的中心位置来表示网格的位置 s,我们可以计算一个比值矽: , 矽=兽 (4.1 0) dJ, “l 然后,根据上面的理论分析,我们可以选择那些遵从距离约束的网格。给定 常数 c≥1,如果∥和矽满足∥/c≤矽≤c 卢,那么我们认为移动节点在该网格 的概率是很高的。这样的网格将被赋予一个权值 l,否则,该网格的权重为 0。 一个网格的最终权值为所有锚节点对在该网格的权值之和。最后,我们用权值最 大的网格的平均值作为移动节点的位置。SGL 算法的伪代码描述如图 4.5 所示, 其中 bnum 表示一个区域内的锚节点数目。第四章跟踪系统中定位问题的研究 SGL algorithm:the position of beacons(魄∥?,y) (婷 l”,bnum),the RSSI values from beacons to the mobile . node RSSIk(1c=l,,,bnum)。The area isdivided into .. Nx Ngrids,the positions of 研 ds Itl'e(gdy,x)∥驴,芦) (1≤f,J≤N); ’ Stepl:For each grid point gd§in the area Fork=1 TQ bnum d 镕 j‘=

Step2:For each grid 觋,弓 20;For any pair of beacons O 力,assul-D.e msy;>RSSIt ∥=l O‘脚 i—RSSIs 朋·拉’ ; lf(旦≤孕≤够) c 吩毋 弓=弓+1; Step3:(X,y)÷(0,o);Max---O;Count=O; em 舣=溉{易}; For each grid point gda in the area ifPij'一兄 8x then (鼍力争(x+鹏一 y+94j,y); count++; Return(x/count,y/count); 4.3.5 实验结果 图 4.5 SGL 算法伪代码描述 为评价我们设计的 AIT 方法的性能,我们与现有的 MERIT(Lee YW eta1.2006) 系统和相关的定位算法(Yedavalli K et a1.2005;Shen X et a1.2005)进行比较。对 41 第四章跟踪系统中定位问题的研究 于区域决策算法,实验结果比较的是区域定位的精度,而对于点定位算法,实验 结果比较的是算法的定位误差。我们将区域定位进度,简称为 ADP(area-decision precision),是指区域定位的正确率。定位误差是指实际位置与算法计算出的 位置之间的平均距离。 (1)区域定位精度 第一步,我们通过与 MERIT 系统进行比较来探讨 BCA 算法的性能。在实验环境 中的任一个区域中,我们随机采样区域中 100 个不同位置的 RSSI 信息,并计算不 同算法的定位精度。从实验结果我们可以看出,无论是 AIT 方法还是 MERIT 系统, 在房间区域的定位精度都要高于在走廊区域的定位精度。实验结果同时表明,相 比于 MERIT 系统,AIT 方法能极大的提高不同大小房间的区域定位精度。例如,在 房间 2 中,MERIT 系统的定位精度只有 0.58,而 BCA 算法的精度达到了 0.83。从总 体来看,在同一平台下 BCA 算法将 MERIT 系统的平均 ADP 从 71%提高到 86%。实验结 果如表 4.1 所示:其中 r 表示房间区域,c 表示走廊区域。 表 4.1 两个算法的区域定位精度 算法 1 (r) 2(r) 3(c) 4(c) MERIT 0.69 O.58 0.33 O.83 BCA 0.86 O.83 0.79 0.9l 算法 5(r) 6(c) 7(r) 平均值 MERIT O.92 0.7 0.93 0.7l BCA O.95 O.72 0.98 0.86 (2)点定位误差 第二步,我们探讨 SGL 算法的定位性能,并同其他相关算法进行比较,如 Proximity—based,Centriod(Shen X eta1.2005)and Ecolocation algorithm (Yedavalli K eta1.2005)。如图 3 所示,我们放置四个锚节点在房间 303 中,这四个 锚节点构成一个 5M*SM 的正方形区域,四个节点分别为正方形区域的四个顶点, 在该区域内随机对 25 个不同的位置进行采样。首先,我们比较在不同定位误差下 的累计概率,如图 4.6 所示。从图中我们可以看出,大多数点的定位误差小于 lM, 与之相比,其他算法只有不超过 20%的点能达到这样的准确度。图 4.7 表示了随着 SGL 算法中参数 X 的变化,各个算法的定位误差的变化。从图中可以看出,x 值越

小,定位误差越大,当参数 X 取值为 6 时,定位误差最小。最后,我们改变区域划 分数目,并观察 SGL 算法的性能变化。如图 4.8 所示,我们可以看到:当区域划分 数超过 20 时,定位误差几乎保持相同。从总体来看,与 Ecolocation 算法相比, 我们提出的 SGL 算法能降低 32%的点定位误差。 42 第四章 g 日踪系统 tp 定 1_j_问题帕研究 Fg 46Location Error vsAccumulative Probabil 时 Fig 47Parameler?Location eⅣor 第四章 P 日踪系统中定位问题的研究 4 —._Centriod Proximity—Basedj 3 5 Ecolocation i—卜 SGL 3 25 Z 1 51 k、 ,k~※ ※ ※ ※ ※ }K ※ ※ 、 7 10 20 30 40 50 60 70 80 90 100 44 本章小结 Fig 48AreaDivisionNmber vsLocation… 在这一章中,我们提出了集区域定位与点定位的体化的 AIT 方法。该方法 首先通过区域定位算法 BCA 确定移动节点处于哪个区域,然后再通过点定位算法 SGL 对移动节点在该区域内进行精确的点定位,确定移动节点在区域内的具体位 置。一旦确定移动节点所处的区域,则点定位时将只使用该区域内的锚节点信息 进行定位,这样可以提高点定位的精度。同时,AIT 方法投有区域太小必须相 l 刮 的限制.适用范围更广。实验结果表明 BCA 算法将 MERIT 系统的区域定位准确度从 71%提高到 86%,而 SG[算法与 EcolocaLion 算法相比减少了 32%的定位误差。虽然 定位精确度有所提高,但仍存在误差,如何进一步提高定位精度将是我们下一步 工作研究的方 J 目。第五章煤矿井下定位跟踪原型系统设计开发 第五章煤矿井下定位跟踪原型系统设计开发 生产安全的核心是人的安全。煤矿迫切需要利用相应的矿井人员跟踪定位设 备,全天候对煤矿入井人员进行实时自动跟踪和考勤,随时掌握每个员工在井下 的位置及活动轨迹、全矿井下人员的位置分布情况以及井下人员位置。矿用人员 定位跟踪系统是集井下人员考勤、跟踪定位、灾后急救、日常管理等于一体的综 合性应用系统。这一科技成果的实现,将为煤炭企业的安全生产、日常管理以及 事故急救带来可靠指挥依据。 本章介绍了基于无线传感网络的煤矿井下定位跟踪原型系统的设计和开发, 从系统框架到服务器端各个模块的设计及系统的实现。该系统的设计开发已经完 成,现处于验收阶段。 5.1 引言 近年来,随着各地煤矿事故频频发生,造成的人员伤亡和经济损失都非常的 惨重。为此,国家对煤矿安全生产问题也日益重视起来,监管力度也在不断加强。 虽然一些大中型煤矿已经大量装备了煤矿安全监控系统,有效地遏制了重大 瓦斯煤尘爆炸事故的发生,但是,目前的煤矿井下定位监测系统主要采取有线传 输的方式,这类系统还存在着通信方式单一、受电缆供电制约、受电缆传输通道

限制、受布线布点制约、抗干扰能力差、成本高、建设周期长等许多缺陷。特别 是矿井出现爆炸、坍塌等危险事故时,传感器及线缆将会受到致命的损坏,更不 能为抢险和搜救工作等提供信息。 针对于此,本章设计开发了一个基于无线传感网络的煤矿井下定位跟踪原型 系统,该系统是以第四章的 AIT 定位跟踪方法为基础开发的。 5.2 硬件需求 该原型系统中所需硬件包含以下四部分: (1) 传感器节点:采用 CrossBow 公司生产的 MicaZ 节点加上相应的传 感器板组成。其采用的操作系统是 TinyOS,使用类 C 语言 NesC 语 言开发相应的节点端代码,并通'r 立_jvIIB510 编程板下载到节点上。 (2) 基站:基站采用 MIB510 编程板配备一个 MicaZ 节点组成,通过 RS232 串行口与服务器相连。 45 第五章煤矿井下定位跟踪原型系统设计开发 (3) (4) 5.3 体系结构 服务器:可采样专用的服务器或配置较好的个人电脑,操作系统 采用 Windows Sever 2003,服务器负责接收基站转发过来的数据, 并对其进行处理(解析,定位),最后将处理后的数据存储于服 务器的数据库中。 远程客户端:采用普通的个人电脑,操作系统为 Windows XP,该 客户端能与服务器进行交互,获取服务器中数据库里的信息。 整个原型系统按照完成的功能不同可以划分为三大部分,它们分别是结点 端,服务器端,以及信息发布端,如图 5.1 所示。下面就这三大部分所涉及到的 具体模块的构成和功能作具体描述。 5.3.1 结点端 (1)结点定位模块:本模块位于各个结点上,主要任务是收集实时的定位跟 踪信息,为定位跟踪系统提供了可靠和及时的原始数据。整个网络分为 Beacon 结点和移动结点。Beacon 结点周期性的发送定位发现包,移动结点在收到定位发 现包后组装一个定位确定包并转发给选择的中继站点,在最终的接受站通过串口 由服务器模块存入本地数据库。 (2)路由选择模块:本模块位于各个结点上,主要任务是通过一定的路由选 择算法进行路由选择,为 Beacon 结点和移动结点动态的选择父结点,从而为消息 传递提供一个稳定的线路。本模块是上面的结点定位模块和下面讲要介绍到的网 络管理模块的辅助模块。 (3)网络管理模块:本模块的信息提供源是网络中的结点。各个结点周期性 的将自己的状态信息发送给服务器,这些状态信息包括结点的剩余电量,当前路 由表信息等,这些信息由服务器存入数据库中,以便信息发布模块查询,从而起 到检测网络状况的作用。 5.3.2 服务器端 服务器端的主要功能分为三个部分:(1)接收从结点发过来的各种信息包, 如移动结点的定位确定包,Beacon 结点和移动结点的状态包等; (2)对各种信 息包进行各自不同的处理, 如对定位确定包进行计算移动结点的定位信息, 对结第五章煤矿 井下定位跟踪原型系统设计开发

点状态包进行存储,更新等; (3)将接收到的各种信息以及计算得到的定位信 息存储本地数据库中 (1)数据采集模块:本模块位于服务器端。主要的任务是通过串口采集结点 发过来的信息包。 (2)服务器计算存储模块:本模块位于服务器端。主要的任务是通过一定的 算法对接收到的定位确认包进行计算,从而得出移动结点的相对精确的位置信 息,并将这些信息以及其他的辅助信息,起存入到本地的数据库中,以便信息发 布模块查询。 (3)数据库模块:本模块位于服务器端。主要的任务是对信息进行存储,为 信息发布模块的查询提供了数据源。 5.3.3 信息发布端 用户应用程序模块:本模块位于客户端。主要的任务是实时的显示当前网络 的状况,其中包括-]'Beacon 结点的状态情况,移动结点的定位信息等。客户端的 使用者可以通过本模块了解网络的信息,从而可以进行一定的操作,如对网络的 管理等。 f 节点端 .节熙状态信恩仪 服务器端 发布端 节点定位佰恩包。 嘧 尹 删 ‘ 迤 / 迎里 唰 / 粕 醛 / 篓 咂 / 《 p / 拽 r1 数据库 r 图 5.1 系统主要模块和关系图 结点端与服务器端之间通过无线的消息包进行通讯,在服务器端通过串口将 传入的消息存入数据库。而服务器端的数据库与消息发布端通过 TCP/IP 标准的网 络通讯协议进行通讯。作者在该原型系统的开发过程中主要负责服务器端的设计 开发,因此,本章将重点介绍服务器端的设计开发。 47 第五章煤矿井下定位跟踪原型系统设计开发 5.4 服务器端的设计 整个服务器模块要实现的功能可以分为三个部分,分别是(1)处理输入数 据,主要任务是从串口将结点发过来的消息接收进来;(2)对不同的信息包进行 相应的处理;(3)将接受到的信息(状态信息)以及计算得到的定位信息存入数 据库中。具体可划分为五个模块:数据采集模块,消息池模块,状态更新模块, 定位算法模块,数据存储模块。如图 5.2 所示。 其中各模块的功能如下: (1)数据采集模块:本模块主要负责将输入数据读入。当从串口读入一个消息 包时,启动一个线程对信息包进行解析,然后根据包的类型放入消息池中的不同 消息队列中去 (2)消息池模块:本模块主要负责消息的处理,其中包括了将消息排入队列和 将消息从队列中取出两个基本功能。本模块的核心数据结构是多个消息的队列, 分别对应不同的消息类型,这样将允许不同的线程能够处理不同的消息,而且对 于同一个队列,也能由多个线程同时处理。这个模块将是线程竞争的。 (3)状态更新模块:本模块主要负责对消息池中的结点状态信息进行存储更新

(4)定位算法模块:本模块主要负责对输入的定位确定信息进行计算。本模块 同样由~组线程进行处理,每个线程负责一个定位确定包的计算,并将计算得到 的结果存入到本地数据库中。 (5)数据存储模块:本模块主要负责对信息的存储操作,包括将结点状态信息, 移动结点定位确定信息的插入,更新等 48 第五章煤矿井下定位跟踪原型系统设计开发 数据采集模块 l I l 。■ ’ .I , ,| 舔 矾 孙 高 释 塞 斟 础 —-二 h. 赤 Dll} 皿 皿 孓 孓 \斟 猢 ‘= 状态更新模块 定位算法模块 l l 数据存储模块 l 数据库 图 5.2 整体模块结构图 5.4.1 数据采集模块设计 该模块主要由两个方法来实现:获取串口数据方法及消息包区分方法,如图 5.3 所示。下面分别对两个方法进行介绍。 获取串口数据方法:本方法不停的检测串口,如果发现有数据进入,则创建 一个新的字符串对象,将数据读入该对象的缓冲中,然后启动一个线程执行消息 包区分方法,参数为刚创建的字符串对象,其中包含了读入的信息。在启动完新 线程之后,本方法继续检测串口,以等待下一个消息的到来。 消息包区分方法:本方法由单独的线程执行,根据消息的类型,创建不同信 息对象,将消息包中的信息填入对象中,并调用消息池模块的方法将各个信息对 象放入相应的队列中。 49 第五章煤矿井下定位跟踪原型系统设计开发 5.4.2 消息池模块设计 匦堑圃 图. ,5.3 数据采集模块结构图 消息池中包含两种类型的消息队列:节点状态信息队列和定位确定信息队 列,分别通过对应的成员函数存取,如图 5.4 所示。节点状态包进队列函数,实 现节点状态包的入队列操作;节点状态包出队列函数,实现节点状态包的出队列 操作;定位确定包进队列函数,实现定位确定包的入队列操作;定位确定包出队 列函数,实现定位确定包的出队列操作。其中,节点状态包进队列函数和定位确 定包进队列函数由数据采集模块的消息包区分方法调用;节点状态包出队列函数 由状态更新模块调用;定位确定包出队列函数则由定位算法模块调用。由于每个 队列都可能有多个线程同时访问,所以对队列的互斥访问机制时必需的。 图. 。5.4 消息池模块结构 5.4.3 状态更新模块设计 该模块由一组线程执行,每个线程调用消息池模块中的节点状态包出队列函 50 第五章煤矿井下定位跟踪原型系统设计开发

数从消息池的结点状态信息队列中取出一个结点状态信息对象,然后调用数据存 储模块的更新节点状态方法将信息存入到数据库中去。 图 5.5 状态更新模块结构 5.4.4 定位算法模块的设计 该模块采用第四章中的 AIT 方法来实现,主要包含两个方法:区域定位方法 和点定位方法。区域定位方法的功能是用于确定移动节点处于哪个区域,通过 BCA 算法来实现;点定位方法的功能是确定移动节点在区域内的具体位置,通过 SGL 算法来实现。 定位算法模块调用消息池模块中的定位确定包出队列函数获得一个定位确 定包,将其作为参数传递到区域定位方法(BCA 算法)进行处理,得到移动节点 所在区域后,再调用点定位方法(SGL 算法)对其进行区域内的精确定位,最后 得到一个包含节点区域信息及区域内坐标的位置信息的节点位置包,调用数据存 储模块中的更新节点位置信息方法,将其存入数据库中。 [亟困 图 5.6 定位算法模块结构 ;丐丽画 i l???第五章煤矿井下定位跟踪原型系统设计开发 5.4.5 数据存储模块设计 该模块被状态更新模块和定位算法模块调用,主要包含两个方法:更新节点 状态方法和更新节点位置方法。如图 5.7 所示。 更新节点状态方法由状态更新模块调用,用于实现节点状态的数据库实时更 新操作;更新节点位置方法由定位算法模块调用,用于实现节点位置的数据库实 时更新操作。 匝亟圃 图 5.7 数据存储模块结构 5.5 系统的运行框架和环境 实验测试平台建立在中国科学技术大学高性能计算中,b--楼至五楼。实验使 用的传感器节点是 CrossBow 公司生产的 MicaZ 节点,包含了与 IEEE 802.15.4/ZigBee 相兼容的射频接收器。它们使用低功耗射频收发芯片 CC2420 互相通信,通信频率为 2.4GHz,提供 256Kbps 带宽的双向通信。通过一对可更 换的从电池和 DC 转换器提供稳定的电压源。MicaZ 节点还包含 51 针脚的扩展 连接器支持到 UART 的接口。网关由一个 MicaZ 节点连接到 MIB510 编程板构成, 编程板再通过 RS232 串口向所连服务器(台式机电脑)转发消息。节点端代码使 用 TinyOS 环境中开发的程序,服务器端代码使用 Visual Studio 2005 平台下 的 C#语言开发的程序,服务器端的数据都存入 Microsoft SQL 2000 数据库中。 如图 5.8 所示。第五章煤矿井下定位跟踪原型系统设计开发 用户端 蚓 5 8 系统的运行框架和环境 ‘~ ‘o,_4^.^】∞a dj 一“女 i ; ; : ?“? g; ,{ , :~ “?一” !*一’ ‘L。 v? ? 。 !——————————————————————————————二———————— ——————————————————·———————————————一一 图 5.9 节点分布图 如图 59 所示,共 25 个锚节点,4 个移动节点及一个网关,和网关相连的服务第五章煤矿井 下定位跟踪原型系统设计开发 器位于四楼 406 室,整个二楼到五楼的走廊及楼与楼之间的楼梯都是目标监视区 域。

首先开启所有锚节点,让锚节点通过自组织的方式构建起路由,该过程持续 2—3 分钟;其次,由人携带一个 MicaZ 节点充当移动节点,打开移动节点,当携带 移动节点的人在目标监视区域内走动时,其定位相关信息会通过锚节点构建好的 多跳路由网络传到服务器,由服务器通过定位算法计算出移动节点所在的位置, 并通过系统显示出来。系统可对多个移动节点进行定位跟踪。 5.6 本章小节 本章介绍了基于无线传感网络的煤矿井下定位跟踪原型系统的设计和开发, 从系统框架到服务器端各个模块的设计。现在该系统包含 1 个基站、25 个锚节点 和 4 个移动节点,目前正处于验收阶段。测试结果显示该系统的有效性。 54 第六章总结与展望 第六章总结与展望 本文主要研究了基于无线传感网络的能量有效跟踪系统关键技术,提出了能 量有效的覆盖保持 k 一连通子集构造算法,以及精确的室内定位跟踪方法 AIT 方法。 同时,在理论研究基础上,我们设计并开发了基于无线传感网络的煤矿井下定位 跟踪原型系统的体系结构和服务器端的各功能模块的设计。 节能问题是无线传感网络的重要研究问题之一,在定位跟踪系统中,系统能 耗直接影响到系统的寿命。通过使用一个节点子集代替整个节点集合对目标区域 进行完全覆盖的方式,使得网络中的其它节点可以进入休眠状态,从而节省整个 网络的能量消耗,是目前无线传感器网络中节能的重要方法之一。已有的研究大 多侧重于构造 k 覆盖节点子集来解决这个问题,由于 k 覆盖子集在一定条件下便 满足 k 连通,故人们对 k 连通子集的构造问题研究较少,但通过构造 k 覆盖节点 子集来实现 k 连通会耗费过多的节点,代价较大。因此,本文提出了一个直接构 造 k 连通 1 覆盖节点子集的算法—CPC, 能够用较少的节点构造出一个既能满 足网络的覆盖 特性又能够满足 k 一连通特性的节点子集。本文还对算法的正确性 进行了严格证明,并通过仿真实验与相关算法进行了性能比较。结果表明,与已 有的 k 覆盖算法相比,CPC 算法能够节省约 55%的节点数。 定位精度是评价定位跟踪系统好坏的重要指标之一。现有的室内定位算法侧 重于对移动目标的直接定位,而忽略了移动节点的区域信息。在室内环境中,由 于建筑结构的复杂度大,而且室内的射频传播特性受到多径干扰等现象的严重影 响,因此采用直接定位的方法的定位精度不高,而一个小的定位误差可能使得移 动节点最后的位置处于不同区域。若我们知道正确的区域信息,那么这样的错误 是可以避免的。针对室内特殊的定位环境,本文提出一种名为 AIT 的基于 RSSI 信 号的室内定位方法。该方法首先通过区域定位算法 BCA 确定移动节点所在区域, 然后再通过点定位算法 SGL 对移动节点在该区域内进行精确的点定位,确定移动 节点在区域内的具体位置。一旦确定移动节点所处的区域,则点定位时将只使用 该区域内的锚节点信息进行定位,这样可以提高点定位的精度。同时,AIT 方法 没有区域大小必须相同的限制,适用范围更广。实验结果表明 BCA 算法将 MERIT 系统的区域定位准确度从 71%提高至 U86%,而 SGL 算法与 Ecolocation 算法相比减少 了 32%的定位误差。 基于上述理论研究的基础上,我们开发了基于无线传感网络的煤矿井下定位 跟踪原型系统,本文着重介绍了系统服务器端的各功能模块的设计。目前该系统 正处于验收阶段。第六章总结与展望 定位跟踪系统是无线传感网络的最具潜力的应用之一,在本文提出的能量有 效地跟踪系统的设计方案基础上仍旧有大量问题值得我们进一步研究:

1、 在节点发生故障的情况下,(K,1)连通覆盖网络虽然仍旧连通,但 网络将不再具有(K,1)连通覆盖的特性。所以,如何在节点发生故 障后,启用休眠节点将网络恢复成(K,1)连通覆盖的网络的问题值 得研究。 2、 本文提出区域定位和点定位算法虽然定位精确度较以往的定位算法 有所提高,但仍存在误差,在一些对精度要求很高的场合仍旧不能满 足要求,如何进一步提高定位精度的问题值得我们研究。 56 参考文献 参考文献 李建中, 李金宝, 石胜飞, 传感器网络及其数据管理的概念、 问题与进展[J], 软件学报, 2003, 14(10):1717—1727 。 任丰原,黄海宁,林闯,无线传感器网络【J】 ,软件学报,2003,14(7):1282-1291 崔莉,鞠海玲,苗勇等.无线传感器网络研究进展【J】 .计算机研究与发展.2005, 42(1):163-274. 马祖长,孙怡宁,梅涛,无线传感器网络综述【J],通信学报,2004,25(4):114—124. 刘敏钰,吴泳,伍卫国.无线传感网络研究[J】 .微电子学与计算机,2005,22(7):58·61. 孙利民,李建中,陈渝等,无线传感器网络【M】 ,清华大学出版社,2005 毛剑琳,无线传感器网络中若干资源优化问题的研究[D】 ,上海交通大学,2006. Tilak S,Abu-Ghazaleh NB,Heinzelman W:A taxonomy of wireless micro—sensor network models[J],Mobile Computing and Communications Review,2002,l(2):1—8 Akyildiz I,Su W:Sankarasubramaniam Yeta1.A survey onsensor networks[J],IEEE Communications Magazine,2002(8):102_114 Wade R,Mitchell WM,Petter ETen emerging technologies that will change the world[J]. Technology Review,2003,106(1):22-49. Tubaishat M,Madria s.Sensor networks:an overview[J],IEEE Potentials,2003,22(2):20-23 Kumar S,Shehperd D。SenslT:sensor information technology for the war fighter[C], in:Proceedings of ISIF,200 1,PP.3—9 Hill J.L.System Arehiteeture for Wireless Sensor Networks[D】 .Berkeley,Califomia,USA: University of California atBerkeley,Department of Computer Science,PhD Thesis, 2003:1.185. Galbreath JH,Townsend cP,Mundell SW,et a1.Civil structure strain monitoring with power-efficient high—speed wireless sensor networks[C].In:International Workshop for Structural Health Monitoring,September 2003. Schmid T,Dubois.Ferriere H,Vetterli M,SensorScope:Experiences with awireless building monitoring sensor network[C],in:The REALWSN’05 Workshop on Real—World Wireless Sensor Networks,Stockholm,Sweden,2005 Mainwaring A, Polastre J, Szewczyk R, a1. et Wireless sensor networks for habimt monitoring[C], in:ACM International Workshop on Wireless Sensor Networks andApplications,2002 Burrell J,Brooke T,Beckwith R.Vineyard computing:sensor networks inagricultural production[J],IEEE Pervasive Computing,2004,3(1):38-45. Baggio A.Wireless sensor networks inprecision agriculture[C],in:The REALWSN’05 57 参考文献 Workshop on Real—World Wireless Sensor Networks,2005,Stockholm,Sweden.

Noury N,Herve L Rialle V eta1.Monitoring behavior in home using asmart fall sensor[C].In: Proceedings of the IEEE—EMBS Special Topic Conference on Microtechnologies in Medicine and Biology.Lyon:IEEE Computer Society,2000.607~610. Doherty L,Kristofer SJ Pister,Laurent E1 Ghaoui.Convex Position Estimation in Wireless SensorNetworks[C].In:Proceedings ofIEEE INFOCOM’01.2001:1655-1633. Bulusu N,Heidemarm J,Estrin D.GPS.1ess Low Cost Outdoor Localization for ve 巧 Small Devices[J].IEEE Personal Communications.2000,7(5):28-34. Savarese C,Rabaey J,Beutel J.Locationing inDistributed Ad—Hoc Wireless Sensor Networks[C].Proceedings oflCASSP’01.2001:2037-2040. Savarese C,Rabaey J,Langendoen 磁 Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks[C].In:Proceedings of USENIX Annual Technical Conference. 2002:3 17.327. Savvides A,Han C,Srivastava M.Dynamic Fine—Grained Localization in Ad-Hoc Networks of Sensors[C].In:Proceedings ofMOBICOM’01.2001:317—327. Niculescu D,Nath B.Ad Hoe Positioning System(APS)Using AOA[C].Proceedings of m 髓 玳 FOCoM’03.2003:1734.1743. Howard A。Mataric M,Sukhatme GRelaxation on aMesh:A Formalism for Generalized Localization[C].Proceedings ofIEEE/RSJIROS’01.2001:1—10. Nissanka B,Priyantha,Balakrishnan H,et a1.Anchor Free Distributed Localization in Sensor Networks.Massachusetts Institute of Technology,Laboratory for Computer Science,Technical Report,No.892,4,15 限】 ,2003:l 一 13 He T'Huang CD,Blum BM eta1.Range-Free localization schemes inlarge scale sensor networks[C].In:Proceeding of the 9th Annual Int'l Conf.on Mobile Computing and Networking.San Diego:ACM Press,2003.81—95 Hightower J,Vakili C,BorrieUo q et a1.Design and calibration of the spot on ad-hoc location sensing system,CSE Techniuqe Report[R],University ofWashington,August 2001. Whitehouse K.The design of calamari:an ad—hoe localization system for sensor networks[D], Master’S Thesis,University of California at Berkeley,2002. Moore D,Leonard J,Rus D,et a1.Robust distributed network localization with noisy range measurements[C],in Proc.SenSys’04,2004. Van Veen B.D,Buckley KM.Beamforming:A versatile approach to spatial filtering[J].IEEE ASSP Mag.1988,5(2):4_24 Stoica P,Moses RL.Introduction to spectral analysis[M].Englewood Cliffs,NJ:Prentice-Hall, 58 参考文献 1997. Ottersten B,Viberg M,Stoica P’et a1.Exact and large sample ML techniques for parameter estimation and detection inarray processing[J],in Haykin,Litva,and Shepherd,Editors, RadarArrayProcessing,Springer-Verlag,Berlin,1993,99-151. Priyantha NB,Chakraborty A,Balakrishnan H,The Cricket location-support system[C】 ,m Mobile Computing and Networking,PP.32__43,2000. Patwari N,Hero III AO,Perkins M,et al。Relative location estimation inwireless sensor networks[J].IEEE Trails,Signal Processing,2003,5 1(83l:2137-2148 Biswas P’Ye Y Adistributed method for solving semidefinite programs arising from ad hoe wireless sensor network localization[R].Dept.of Computer Science,Stanford Univ. ,Stanford,

CA,Tech.Rep. ,Oct.2003. Shang 巧 Ruml 彤 Zhang 巧 et a1.,Fromherz MPJ,Localization from mere connectivity[e1.In: Proceed of.The Mobihoc‘03,1une 2003,PP.201-212. Shang Y Ruml W-Improved MDS-based localization[C].In IEEE Proc.Infocom‘04,2004: 2640-2651. Niculescu D,Nath B。Ad hoc positioning system(APS)【C],In:Proceeding of the IEEE GlobeCom,San Sntonio,AZ,Nov,2001 Nagpal R.Organizing aglobal coordinate system from local information onan amporphous computer.AI Memo 1666[R],MITAI Laboratory,August 1999 Sichitiu ML,Ramadurai V Localization of wireless sensor networks with amobile beacon. Center for Advances Computing Communications, ’North Carolina State Univ. ,Tech.Rep.TR-03/06[RI,Jul.2003. Sun GL,Guo W:Comparison of distributed localization algorithms for sensor network with a mobile beacon[C].In:Proceed of IEEE Int.Conf.Networking,Sensing Control(ICNSC),Taipei, Taiwan,R.O.C. ,Mar.2004,PP.536-540, Galstyan A,Krishnamachari B,Lerman l(,ct a1.Distributed online localization insensor networks using mobile target[C].In:Proceeding of the intemational Symposium on information Processing Sensor Networks,Berkeley,CA,2004:61—70. Priyantha NB,Balakrishnan H,Demaine E,et a1.Mobile-assisted localization in wireless sensor networks[C】 .In:Proceeding ofthe IEEE Infocom,v01.1,March 2005,PP.1 72-1 83. Kuo-Feng Ssu, Chia-Ho Ou, Jiau, a1. et Localization with mobile anchor points in wireless sensor networks[J].IEEE Transactions on Vehicular Technology,2005,54(3):1 187—1 197. Hu L,Evans D.Localization for mobile sensor networks[C].In:ACM Mobicom’04, Philadelphia,Pennsylvania,September,2004 59 参考丈献 Gupta It,Das SR.Tracking moving targets in asmart sensor network[C].The VTC Fall 2003 Symposium,Oct,2003 Mechitov KSundresh S,Kwon Y eta1.Cooperative tracking with binary-detection sensor networks[C].In:Proceeding 1st Int.Conf.on Embedded Networked Sensor System(SenSys03), Los Angeles,CA,November 5-7,2003. Zhao EShin J,Reich J.Information-Driven dynamic sensor collaboration for tracking applications[J].IEEE Signal Processing Magazine,2002,19(2):61-72. Chu M,Haussecker H,Zhao EScalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks[J].International Journal on High Performance Computing Applications,2002,1 6(3):293-3 13. Liu J,Cheung P,Guinbas L'et a1.A Dual—Space approach to tracking and sensor management in wireless sensor networks[C],Proc.1 stACM Int’1 workshop on wireless sensor network and applications,Atlanta,GA.2003.13 l 一 139 Ramanathan P.Location-centric approach for collaborative target detection,classification,and tracking[C].IEEE CAS Workshop,2002. Brooks RGriffin C,Friedlander DS.Self-Organized distributed sensor network entity tracking[J].International Joumal of High Performance Computing Applications,2002,l 6(3): 207-219

Brooks R Ramanathan P,Sayeed.A distributed target classification and tracking insensor networks[J].In Proc.oflEEE,2003,91(8):1163 一 1171. Brooks It,Griffin C.Traffic model evaluation ofadhoe target tracking algorithms[J]. International Journal ofHigh Performance Computing Applications,2002,16(3):221-234. Zhang 彤 Cao GDCTC:Dynamic convoy tree—based collaboration for target tracking in sensor networks[J].IEEE Transactions on Wireless Communications,2004,3(5):1689-1701. Guo D,Wang X.Dynamic sensor collaboration via sequential Monte Carlo[J].IEEE Joumal on Selected Areas in Communication,2004,22(6):1037—1047. Sheng X,Hu YDistributed particle filter with GMM approximation for multiple target localization and tracking in wireless sensor network[C].In:Proceeding of the international symposium ofinformation processing in sensor networks,(10s Angeles,CA),2005.181—188. Xiao W.Adaptive sensor schedufing for target tracking in wireless sensor network.Advanced Signal Processing Algorithms,Architectures,and Implementations xv[J].In Proceedings ofthe SPIE,2005,Volume 5910,PP.104-112 Lee J,Cho KLee S,et a1.Distributed and energy-efficient target localization and tracking in wireless sensor networks[J].Computer Communications,2006,29(2006):2494-2505 60 参考文献 】Megerian S,Koushanfar F’Qu Geta1.Exposure inwireless sensor networks:theory and practical solutions[J].Journal ofWireless Networks,2002,8(5):443--454. Megefian S,Koushanfar F,Qu q et a1.Exposure in wireless Ad Hoe sensor networks[C].In: Proceeding ofInternational Conference onMobile Computing andNetworking (MobiCom’01),PP.139-150,Rome,Italy,July 2001. Clouqueur T,Phipatanasuphom V Ramanathan P,et a1.Sensor deployment strategy for target detection[C】 .The First ACM International Workshop onWireless Sensor Networks and Applications(WSNA'02),Sep.2002. Chakrabarty KIyengar SS,Qi H,et a1.Grid coverage for surveillance and target location in distributed sensor networks,IEEE Transactions on Computers[J].2002,51(12):1448—1453. Jung,B,Sukhatme GS.Tracking Targets using Multiple Robots:The effect of environment occlusion[J],Autonomous Robots,2002,13(3):191—205 Paaem S,Poduri S,Krishnamachari B.Energy·quality tradeoffs for target tracking in wireless sensor networks[C].In:Proc 2nd Workshop oninformation Processing in Sensor Networks(IPSN 2003),April 2003. Gupta H,Das S,Gu Q.Connected sensor cover:Self-organization of sensor networks for efficient query execution[C].In Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc),2003. Zhou ZH,Das S,Gupta H.Connected K-Coverage Problem in Sensor Networks[C].In IEEE Conference on Computer Communications and Networks CiCCCN),2004 Hefeeda M,Baghefi M.Randomized k-coverage algorithms for dense sensor networks[C].In Proc.ofIEEE INFOCOM’07 Minisymposium,Anchorage,AK May 2007. Xing G Wang X,Zhang Y et a1.Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks[C],In ACM Sensys’03,2003. Wan P,Yi C.Coverage by randomly deployed wireless sensor networks[J].IEEE Transactions on Information Theory,52:2658-2669,2006. Tian D,Georganas N.Connectivity maintenance and coverage preservation in wireless sensor

networks[J].Electrical and Computer Engineering,2004.Canadian Conference on,PP. 1097-1 100 V01.2,2-5 May 2004 Bai X,Kumar S,Xuan D,et a1.Deploying wireless sensors toachieve both coverage and connectivity[C].In Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc),May 2006. Hefeeda M,Ahmadi H.A probabilistic coverage protocol for wireless sensor networks[C].In 15th IEEE Intemational Conference on Network Protocols(icN-P),PP.4 1-50,2007. 61 参考文献 Abrams Z,Goel A,Plotkin S.Set k-cover algorithms for energy efficient monitoring inwireless sensor networks[C】 Proc.Int.Workshop on Information Processing in Sensor Networks .In (msN),PP.42 牛 432,2004. Getting I.The global positioning system[J].IEEE Spectrum,30(12),1993 Bahl P,Padmanabhan VN.RADAR:An in-building RF-based user Mcadon and tracking in sensor systemiC].In Proceeding ofIFOCOM2000,pages775-784,2000. JiYBiaz S,Pandey S,et a1.ARIADNE:A dynamic indoor signal map construction and localization system[C].In Proceedings of the 4th international conference On Mobile Systems Application and Services(MobiSys),2006. Lee YW,Stuntebeck E,Miller SC.MERl|T:Mesh of RF Sensors for Indoor Tracking[C]. Secon’06,2006; Lorincz KWelsh M.Motetrack:a robust,decentralized approach toR.F-based location 仃 acking[C].In Proceedings ofthe International workshop on Location and Context-Awareness (LNCS 3479),Pages63—82,2005. Gibbons J,Hopper A,Falcao VThe active badge location system[J].ACM Trans.Information System,10:91-102,Junel992. Priyantha NB,Chakraborty A,Balakrislman H.The Cricket location supporting system[C].In Proceeedings ofthe ACM MOBICOM,2000. Lim H,Kung L,Hou J,et a1.Zero-configuration,roboust indoor localization:Theory and experimentation[C].In Proceeding of lEEE INFOCOM’06,2006. Ni LM,Liu Y Lau Y C,et a1.LANDMARC:Indoor Location Sensing Using Active m:m[cj. InProc.of the First IEEE International Conference onPervasive Computing and Communications,2003. Yedavalli KKrishnamachari B,Ravula S,et a1.Ecolocation:A Sequence Based Technique for RF Localization in Wireless Sensor Networks[C],IPSN’05; Shen X,Wang Z,Jiang P,et al。Connectivity and RSSI Based Localization Scheme for Wireless Sensor Networks【C】 .ICIC2005. 62 致谢 致谢 时间从我们指缝问流过,转眼三年的研究生生活即将结束,在毕业论文 即将完成之际,我谨向在这几年学习生活中关心、帮助和支持我的老师、同 学和亲人们致以衷心的感谢! 首先,我要感谢我的导师黄刘生教授!在我学习和研究其间,黄老师给 予了我悉心的指导和巨大的帮助,没有黄老师的指导、支持和帮助,我的研 究工作是完不成的。导师学识渊博,治学严谨,对问题深入浅出的讲解方法, 对学生平易近人的态度,以及严于律己的作风和开拓创新的科研精神,都是

我学习的榜样,是我人生中的宝贵财富。 感谢徐宏力老师,尽管他自己的科研任务繁重,但他还是抽出大量时间 在课题研究过程中给予我很多指导和帮助.在我的研究遇到问题时,常常与 我探讨有效解决方案,并在论文写作和修改过程中提出了很多宝贵建议。 感谢肖明军老师,汪炀老师,王刚博士,王继春博士,徐学永博士,黄 河博士,霍永凯硕士,李想硕士,在论文完成过程中给以我的帮助和支持。 此外感谢实验室所有的同学和老师在三年的研究生学习和生活过程中对我 的关心和帮助。 感谢我的父亲和母亲,感谢他们在我学习过程中给以我的支持和鼓励, 以及在生活上的关心和照顾。 ’ 最后,向所有直接和间接关心、支持和帮助我的人们以及本文的评审老 师表示衷心的感谢 1 2009 年 4 月在读期间发表的学术论文与取得的研究成果 在读期间发表的学术论文与取得的研究成果 已发表论文: 【1】徐涛,黄刘生,徐宏力,王刚, “无线传感网络中覆盖保持的 K-连通子集构 造算法”《小型微型计算机系统》 , ,已录用。 【2】Xu HL,Huang LS,Xu T,Huo YK,Wang Y.Practical Indoor Tracking using Wireless Sensor Networks.WPNC 2009,已录用。 参与项目: 【l】2006.05~2011.05:无线传感网络应用示范系统的研究,973 一级子课题,260 万; 【2】2007.01—2008.12:基于 CNGI 和 WSN 的矿山井下定位与应急联动系统, 国家发改委第二批 CNGI 重大专项,1870 万(其中国拨 200 万); [3]2007.03~2009.08:无线传感网络节点定位和目标跟踪技术研究,中国科学院 知识创新工程重要方向项目,50 万。


赞助商链接

云计算系统中能量有效的数据摆放算法和节点调度策略

《现代电子技术》2015 年第 09 期 摘要: 云计算系统中数据中心的能耗问题早已...能量有效无线传感网络... 5人阅读 5页 ¥3.00 基于多信道的能量高效传...