硕士学位论文-无线传感器网络定位系统研究及设计.pdf

浙江工业大学硕士学位论文 无线传感器网络定位系统研究及设计 作者姓名： 指导教师： 孟文超 俞立教授 浙江工业大学信息工程学院 2 0 “年4 月 D i s s e r t a t i o nS u b m i t t e dt oZ h e j i a n gU n i V e r s i t yo f T e c h n o l o g y f o rt h eD e g r e e0 fM a s t e r R E S E A R C HA N DD E S I G No FL o C A L I Z A T I O N S Y S T E MI NW I R E L E S SS E N S o RN E T W o R K S C a n d i d a t e ： M e n gW e n c h a o A d v i s o r ：P r o f Y uL iA d V l S 0 r ：r r o t Y UL i C o l l e g eo fI n f o r m a t i o nE n g i n e e r i n g Z h e j i a n gU n i V e r s i t yo fT e c h n o I o g y A p L2 0 l l 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果除文中已经加以标注引用的内容外，本论文不包含其他个人 或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构 的学位证书而使用过的材料对本文的研究作出重要贡献的个人和集体，均已在文 中以明确方式标明本人承担本声明的法律责任 作者签名：立乙又趣 日期：扣f 1 年舅砭日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅 本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 l 、保密口，在年解密后适用本授权书 2 、不保密 ( 请在以上相应方框内打“、”) 作者签名：盘天天量 刷磴辄百红 日期：2 年歹月“日 日期咖If 年厂月以日 无线传感器网络定位系统研究及设计 摘要 无线通信、传感器技术、嵌入式技术的日益成熟，使得低成本、低功耗、大规模的无 线传感器网络得到快速发展，且逐步应用于军事、民用等众多领域。在无线传感器网络中， 位置信息扮演着不可或缺的重要角色，如何设计高效实用的定位算法和系统一直是无线传 感器网络的研究热点之一。 定位算法是无线传感器网络定位系统设计的核心内容，在分析国内外定位算法及系统 技术难点的基础上，针对以下问题：l 、如何在不增加网络通信负担情况下，提供较高的 定位精度，满足大多数无线传感器网络定位系统需求；2 、如何在网络拓扑结构变化频繁 情况下，具有较强的可扩展性；3 、如何在高噪声环境下，具有较强的抗环境干扰鲁棒性： 进行了深入研究，取得如下研究成果： l 、建立W S N 节点定位模型，主要包括系统模型、测距模型和误差模型。 2 、通过分析未知节点与信标节点的距离和信标节点问的共线性这两个影响定位精度 的因素，提出了一种最优信标组选择机制。 3 、研究节点定位的扩展卡尔曼模型，通过其迭代求精过程有效抑制测量噪声，提高 了未知节点的定位精度。 4 、结合最优信标组选择机制与扩展卡尔曼滤波的优点，提出一种新的基于最优信标 组的扩展卡尔曼滤波定位算法( B B G E K F ) 。该算法复杂度低，通信量小，定位精度较高。 5 、搭建无线传感器网络定位系统，包括硬件平台与软件平台。硬件平台主要有传感 器节点设计和汇聚节点设计，测距方式结合R S S l 和超声波两种测距方式。软件平台主要 是B B G E K F 定位算法实现，以及节点软件和监控中心软件的详细设计。 关键词：无线传感器网络，定位系统，最优信标组，扩展卡尔曼滤波 浙江：T ：业大学硕士学位论文 R E S E A R C HA N DD E S I G No FL o C A L I Z A T I O N S Y S T E MI NW I R E L E S SS E N S o RN E T W o R K S A B S T R A C T R e c e n t l y ， 谢t ht h e d e V e l o p m e n t o ft e c h n o l o g yi nw i r e l e s sc o m m u n i c a t i o n ，s e n s o r t e c h n o l o g y 鲫de m b e d d e dt e c h n o l o g y ，i ti sp o s s i b l et 0d e p l o yt h el a u r g e s c a l e 、V i r e l e s ss e n s o r n e r k S( W S N ) ，锄ds oi t i s 印p l i c a b l e i n m i l i t a D ， 锄dc i V i l i 锄f i e l d s S i n c el o c a t i o n i n f 0 肿a t i o np l a y sa ni m p o r t a n tr o l ei nw i r e l e s ss e n s o rn e t 、v o r k s ，t l l ep r o b l e mo fd e s i g n i n gt h e e m c i e n tI o c a l i z a t i o na l g o r i t h m 锄ds y s t e mh a L sb e c o m e 锄h o tr e s e a r c ht o p i c L 0 c a l i z a t i o na l g o r i t p l a y s 锄i m p o n a n tr o l ei nw i r e l e s ss e n s o rn e M o r k SB a S e do nt h e 锄a l y s i so ft h ee x i s t i n ga l g o r i t h m s ，w ec o n c l u d es o m et e c h n i c a ld i 陌c u l t i e si nd e s i 印o fs y s t e m s T h e r e f o r e ，s o m ei n t e r e s t i n gp r o b l e m sa u r ep r e s e n t e d 弱f o l l o w s ：F i r s t ，h o wt od e s i g nah i 曲e r l o c a t i o na c c u I a c ya l g o r i t h I I lw i t h o u ti n c r e a s i n gt h ec o m m u n i c a t i o nb u r d e n ，锄dt h ed e s 追n e d a l g o r i m mc 觚s “s f yt l l en e e do fm o s tl o c a l i z a t i o ns y s t e mi nW S N ；S e c o n d ，h o wt 0p r o V i d ea h i 曲e rs c a l a b i l i t ya l g o r i t h n li n t h ec h a n g e a b l et o p o l o g yo fn e 似o r k ；1 1 1 i r d ，h o wt 0d e s i g I la r o b u S ta l g o r i t | u nf o rt h en o i s ee n V i r 0 肌l e n t I nt h i st l l e s i s ，m a i nr e s u l t sh a V eb e e no b t a i n e df o rt 1 1 e a f o r e m e n t i o n e dp r o b I e m s 锄da r el i s t e da Sf o l l o w s ： F i r s t l y ，t I l en o d el o c a t i o nm o d e l s ，i n c l u d i n gs y s t e mm o d e l ，r a n g i n gm o d e la n de 玎0 rm o d e l ， a r ee s t a b l i s h e d S e c o n d l y ， t 、v o f a c t o r s ， w h i c hi n f l u e n c et h el o c a t i o na c c 删置c y ， i n c l u d i n gt l l e d i s t a n c e b e t w e e nb e a c o n s 觚du m m o w nn o d e s ，锄dt h ec o l i n e 撕t yo fb e a c o n s ，a r e 锄a J y z e d T h e nan e w s e l e c t i o ns c h e m ef o rt h eb e s tb e a c o ng r o u pi sp r o p o s e d T h i r d l y ，t h ee x t e n d e dK a l m 觚m o d e lf o rn o d el o c a l i z a t i o ni si n V e s t i g a t e d B yi t Si t e r a t i V e r e f i n e m e n tp r o c e s s ，t h em e a s u r en o i s ei ss u c c e s s 如l l ys u p p r e s s e d ，a n dt h el o c a t i o na c c u r a c yo f u I l l m o 、) v - 1 1n o d e si si m p r o V e d F o u n h l y ，b a S e do nm eb e s tb e a c o ng r o u p ，an e wB B G - E K Fa l g o r i t h mi sp r o p o s e d ，觚dt l l e d e s i g n e da l g o r i t h mh a St h ea d V a n t a g eo fl o wc o m p l e x i t y ，l o wc o m m u n i c a t i o no V e r h e a da 1 1 dh i g h a c c u r a c y F i n a l l y ，al o c a l i z a t i o ns y s t e m ，i n c l u d i n gh a r d w a r ep l a t f o ma n ds o R w a r ep I a t f o n n ， i s d e s i g n e di nw i r e l e s ss e n s o rn e t w o r k s T h eh a r d w a r ep l a t f o r mm a i n l yc o n t a i n st I l ed e s i g no f 浙江I ：业人学硕十学位论文 s e n s o rn o d e sa n ds i m ( n o d e s T oe x t e n dt h ea p p l i c a t i o no ft h i sl o c a l i z a t i o ns y s t e m ，t w om g i n g w a y s ，w h i c hi n c l u d eR S S Ia n du l t r 嬲o n i c ，a r ep r o p o s e d T h es o R w a r ep l a t f o r n lm a i n l yc o n t a j n s t l l er e a l i z a t i o no fB B G - E K F a l g o r i t h r n ，t h es o R w a r eo fn o d e sa n dm o n i t o r i n gc e n t e r 1 ( e yW o r d s ： 谢r e l e s ss e n s o rn e m ，0 r k s ，I o c a l i z a t i o ns y s t e m ，b e s tb e a c o n 铲o u p ，e x t e n d e d K a l m 锄f i l t e r 浙江工业大学硕士学位论文 目录 摘要i 第l 章绪论l 、弓? 善、 1 2 研究背景及意义1 1 2 1 无线传感器网络概述。1 1 2 2 无线传感器网络的特点2 1 2 3 无线传感器网络中的节点定位3 1 3国内外研究现状4 1 4 典型定位算法分析6 1 4 1 单跳定位算法6 I 4 1 1 基于T D O A 的定位6 1 4 1 2摹十A o A 的定位7 I 4 1 3基于T o A 的定位8 I 4 2 多跳定位算法9 1 4 2 1 D V - H o p 算法9 1 4 2 2 D H L 算法1 l 1 4 2 3 M D S M A P 算法12 1 5 论文内容与结构l3 第2 章W S N 节点定位模型建立1 4 2 1系统模型1 4 2 2 测距模型l5 2 2 1 R S S I 测距15 2 2 2 超声波测距一l7 2 3 误差模型l8 2 3 1 测距误差18 2 3 2 定位误差1 9 2 3 3基十C R L B 的定位议差分析2 0 2 4 本章小节2l 第3 章基于最优信标组的扩展卡尔曼定位算法2 2 3 1 信标节点选择2 2 3 1 I未知节点0 侪标节点之间趴离2 2 3 1 2 信标节点间共线度2 3 3 I 2 1 共线度情况分析2 4 3 1 2 2 共线度定义2 5 3 1 2 3 共线度与定位谈差关系2 6 3 1 3 最优信标组2 7 浙江j 1 ：业人学硕十学位论文 3 2 3 3 3 4 3 5 第4 章 4 1 4 2 4 3 扩展卡尔曼定何2 8 B B G E K F 算法3 2 B B G E K F 仿真与分析3 3 3 4 1B B G E K F 定位效果3 3 3 4 2 通信半径变化3 3 3 4 3 迭代次数变化3 4 3 4 4 信标节点密度变化3 5 本章小结3 5 W S N 定位系统设计。3 6 传感器节点设计3 6 4 I 1 微处理器3 7 4 1 2 通信模块3 7 4 1 3 测距模块3 9 4 I 4 电K 转换摸块3 9 4 1 5 舵机模块4 0 汇聚1 了点设计4 l 软件设计4 2 4 3 1 数据包格弋一4 2 4 3 2 传感器节点软件改计。4 3 4 3 3 汇聚节点软件- 陂计4 5 4 3 4B B G - E K F 算法实现4 6 4 3 5 监控中心软件设计4 8 4 4 本章小结4 9 第5 章实验验证。5 0 5 1 基于R S S I 测距的定位实验5 0 5 2 基于超声波的定位实验5l 第6 章总结与展望。5 3 6 1总结5 3 6 2 展望5 4 参考文献5 5 j 改谢! ；9 攻读学位期间参加的科研项目和成果6 0 浙江工业人学硕十学位论文 第1 章绪论 1 1引言 无线传感器网络( W i 陀l e s sS e n s o rN e t w o r k ，W S N ) 是一门涉及计算机、通信、网络、 传感器、微电子、智能计算、嵌入式系统等多个领域的交叉学科【l 】。它由部署在监测区域 内大量的体积小、价格低廉、种类繁多的传感器节点( 传感、采集、处理、收发、网络于 一体) 以自组织的形式组成自治的网络1 2 1 。节点间通过无线通信以单跳或多跳方式交换信 息，实现对客观世界的动态智能协同感知【3 1 。无线传感器网络逐步深入到社会生活的各个 方面，如医疗监护、环境监测、目标跟踪、交通管理、军事应用、空间搜索等诸多领域， 是计算机与信息领域新的研究热点f 4 J 。 随着无线传感器网络的快速发展，传感器节点的位置信息在W S N 的诸多应用中扮演着 不可或缺的重要角色f 5 】，如在环境监测、战场侦察、目标跟踪等应用中，监测数据只有与 节点位置信息绑定才有意义【6 l 。无线传感器网络的特点给节点自定位提出很多前所未有的 挑战。因此对节点定位进行研究具有重要的意义。 1 2 研究背景及意义 1 2 1无线传感器网络概述 计算机技术、通信技术、嵌入式技术和传感器技术的发展，推动了具有感知能力、无 线通信能力和计算能力的传感器节点的进步f 7 】，使其能够在微小体积内集成信息采集、数 据处理和无线通信等多种功能f 引。无线传感器网络通过在一定的监测区域内布置大量廉价 的传感器节点，相邻传感器节点问通过无线通信方式形成一个多跳的自组织网络，能够从 复杂的物理世界获得第一手信息，是人类社会和自然环境之间的信息桥梁【9 1 。 W S N 的体系结构如图1 1 所示，整个系统由传感器节点( S e n s o r N o d e ) 、汇聚节点( S i n k N o d e ) 和管理节点三个部分组成【1 0 1 。大量传感器节点随机部署在监测区域内或附近，以无 线通信方式形成自组织网络【J 。传感器节点监测的数据沿着其他传感器节点逐跳地进行传 输，在传输过程中可能被多个节点处理，经过多跳后路由到汇聚节点，最后通过I n t e m e t 或 G P R S 到达管理节点。用户通过管理节点对传感器网络进行配置和管理，发布监测任务以 及收集监测数据。 1 浙江1 二业大学硕士学位论文 传感器节点成本低廉，遍布在整个监测区域，其主要功能是：承担监测区域内的数据 采集，并且通过邻居传感器节点以单跳或多跳方式传递给汇聚节点及任务管理节点，从网 络功能来看，每一个传感器节点兼顾着传统网络的终端和路由双重功能【1 2 l 。 监控区域或对象传感器节点 图1 1 w S N 系统结构 汇聚节点的处理能力、存储能力和通信能力相对比较强，它连接传感器网络与I n t e m e t 等外部网络f 1 3 】，实现两种协议栈之间的通信协议转换，同时发布管理节点的监测任务，并 把收集的数据转发到外部网络上。汇聚节点既可以是一个具有增强功能的传感器节点，有 足够的能量供给和更多的内存与计算资源，也可以是没有监测功能仅带有无线通信接口的 特殊网关设备。 管理节点，即整个网络的监测中心，一般配置有复杂的管理软件。用户既可以通过监 测中心查看每个传感器节点状态，了解用户关心的事件，也可以通过监测中心发布任务。 1 2 2 无线传感器网络的特点 l 、电源能量受限 传感器节点体积小，一般由能量十分有限的电池供电【1 4 1 。由于节点成千上万，分布区 域广而复杂，有些区域人员甚至难以到达，因此，通过更换节点电池来补充节点能量的方 式是不现实的。由此可见，如何有效地使用能量来提高网络寿命是无线传感网设计的一个 关键。 2 、网络规模大 网络规模大主要指分布的地理区域大和部署密集两个方面。传感器节点的数目成千上 万。这种大规模网络降低了对单个节点的精度要求，大量节点增大了覆盖的面积，减少了 盲区，使系统具有很强的容错性能。 2 浙江I ：业人学硕+ 学位论文 3 、动态网络拓扑结构 传感器节点分布在监测区域里，各自相互独立又保持协作性地感知物理世界。物理世 界的任何细微变化都可能改变网络的拓扑结构，既可能因为电能耗尽造成节点故障或失 效，也可能因为环境条件变化造成无线通信链路变化，再加上新节点加入，感知对象、传 感器节点、观察者具有移动性等因素。因此，必须设计可靠的路由协议满足网络拓扑结构 的频繁变化。 4 、自组织网络 在传感器网络应用中，通常情况下传感器节点被放置在没有基础结构的地方，传感器 节点位置不能预先精确设定，节点之间相互邻居关系预先也不知道，如通过飞机播撒大量 传感器节点到面积广阔的原始森林中，或随意放置到人工不可到达或危险的区域。这样就 要求传感器节点具有自组织的能力，能够自动进行配置和管理，通过拓扑控制机制和网络 协议自动形成转发监测数据的多跳无线网络系统。 5 、数据为中心 传统的互联网是以地址为中心的网络，而无线传感器网络的节点随机部署在监测区域 中，即传感器节点的地址是随机的【1 5 】。而对于用户来说，用户关心的是事件本身而不是节 点地址，当用户想要得知关心的事件时，是直接将所关心的事件告知给网络，而不是某个 确定节点。此后，网络在获得指定事件的信息后汇报给用户。因此，无线传感器网络是一 个以数据为中心的网络。 1 2 3无线传感器网络中的节点定位 在无线传感器网络的许多监测应用中，节点的位置信息通常起着关键性的作用【2 0 】。在 环境监测中，用户关心的一个问题就是对应的环境参数究竟发生在什么位置，没有位置信 息的温湿度等环境信息没有任何实际意义【。6 】。如在一些森林火灾等突发事件中，发生火灾 的位置信息对于抢救工作具有十分重要的意义【“ 】，精确的位置信息可以大大减少生命和财 产损失。在军事侦察应用领域，实现敌方车辆的准确实时定位不仅有助于了解敌人位置， 而且可以帮助我们掌握整个军事布局，对战争胜负起着不可估量的作用1 1 1 。 节点定位不仅具有告知事件发生位置的用途，而且还具有以下功能： 1 ) 网络拓扑结构发现：根据传感器节点的位置信息，可以快速获知网络拓扑结构及 各个区域的网络密度。针对不同的区域采取不同的措施，如在密度较小的区域增加传感器 节点的个数【1 引。 2 ) 路由建立：节点位置信息可以为网络路由协议的建立提供帮助【9 1 ，如基于地理信 1 浙江工业大学硕士学位论文 息的路由协议就是根据节点的位置信息进行进一步优化，尽量减少网络密集区域的通信 量，防止网络堵塞现象。 3 ) 定位导航：实时监测目标的运动轨迹，预测目标的运动方向，有助于对目标进行 路径优化【2 0 】。 无线传感器网络中，传感器节点具有体积小、计算能力差、资源受限、随机部署等局 限性，而且一般由成千上万个节点组成一个大规模网络。这些特点都给节点定位带来了挑 战性。这就要求w S N 节点定位系统必须具有自组织性、可扩展性、健壮性、分布式计算 等特性。 1 3 国内外研究现状 A T & TL a b o r a t o r i e sC 锄b r i d g e d 在1 9 9 2 年提出第一个室内定位系统A c t i v eB a d g e 后， 国内外学者对W S N 定位系统进行了大量深入研究，大致经历了两个阶段。 第一阶段是基于基础设施的定位系统与算法，主要有A c t i v eB a d g e 【2 1 2 2 1 、A c t i v eB a t 【2 3 1 、 A c t i v eO f n c e f 2 4 1 、S m 矾F l o o r 【2 ”、 W h e r e N e t f 2 6 1 、S p o tO n 【2 7 1 、R A D A R f 2 引、C r i c k e t 【2 9 l 等。这 些定位系统由于都需要基础设施的参与，系统成本较高，不适合在大规模无线传感器网络 中进行推广。文献【3 0 ，3 l 】对这些定位系统进行了详细的探讨与比较。 融m A R 【2 8 】是M i c r 0 S 0 f l 设计的一个基于R S S I 的室内定位跟踪系统，它在楼层内布置 了三个基站节点，通过测量R S S I 估计发射节点距离，并利用三边定位算法实现未知节点 的位置估计。C r i c k e t 【2 9 1 是M I T 提出的一种基于T D O A 室内定位系统。未知节点同时发射 无线电波和超声波，信标节点记录两种信号到达时刻并计算其差值，进而利用已知的信号 传播速度估计两者的距离。 第二个阶段是基础设施无关的定位技术。由于基础设施成本较高，给W S N 系统设计 带来了巨大挑战。因此，基础设施无关的定位技术研究受到大多数学者的青睐，它的基本 原理是：把网络节点分为信标节点与未知节点，信标节点是位置已知的节点，未知节点是 位置未知的节点，节点定位过程就是利用少数的信标节点估计未知节点的位置。典型的定 位算法有A P S 【3 2 3 4 1 、M D S M A P 【3 5 】、S P A 【3 6 1 、凸规划定位算法【3 7 ，3 引、A H L o s l 3 9 】、N - h o p m u t i I a t e r a t i o np r i m i t i v e 【4 0 1 、I S o M A P 【4 、l ( P C A 【4 2 1 、K L P P 【4 3 1 等。 A P S 不是一种定位算法，而是由美国路特葛斯大学提出的一系列分布式定位算法集合， 主要包括D V - H o p 、D V d i s t a n c e 、E u c l i d e a n 、D v c o o r d i n a t e 、D V - B e a r i n g 和D V R a d i a l ，其 基本原理是距离矢量路由协议和G P S 定位原理【3 2 。4 1 。 M D S M A P l 3 5 】是一种多维定标的定位算法，利用节点间生成的相似度矩阵，通过对其 4 浙江一r ：业大学硕十学位论文 进行线性降维，使降维后的空间节点间相似度尽量与高维空间的相似度保持一致，从而实 现定位。其初步生成的坐标是相对坐标，利用足够多的信标节点可以转换为绝对坐标。S P A 是由S r d i a nC a p k m l f 3 6 】提出的一种相对定位算法，利用在高密度区建立局部坐标系，通过节 点之间的信息交换与协调实现坐标计算。D o h e n y f 3 7 】等人提出的凸规划定位算法把节点间的 通信关系转换为约束条件，把整个网络看成一个凸集，利用凸优化理论实现未知节点定位。 S a w i d e s 【”】等人提出的A H L o s 定位算法是一种基于T D O A 的迭代定位算法，通过极大 似然定位算法获得未知节点的坐标，并转换为信标节点，然后继续广播其位置，提供更多 的信标节点，不断提高未知节点的定位精度。S a w i d e s 【4 0 l 等人还提出了A H L o s 改进定位算 法，通过在A H L o s 引入卡尔曼滤波技术，抑制测量噪声，提高定位精度。近年来，国内外 学者对无线传感网定位技术进行了深入研究。从不同的角度可以把定位算法分为不同的类 别。 1 ) 基于测距算法与测距无关算法m 】：根据定位过程中是否测量节点间的距离，定位 算法可分为基于测距算法和无需测距算法。基于测距的定位算法主要测量信标节点与未知 节点的距离或角度信息，然后再利用三边定位法或三角定位法实现节点定位。其中，接收 信息强度指示( R S S I ) 、到达时间( T o A ) 、到达时间差( T D O A ) 、到达角度( A O A ) 是最 常见的距离或角度测量方法【4 5 1 。R S S l 虽然具有低成本、低功耗的特点，但是易受环境因素 的干扰，误差一般在5 0 左右。T o A 要求发送节点与接收节点的时间严格同步，大大增加 了传感器节点的成本。T D O A 由于采用超声波技术，测距范围有限，而且也易受环境因素 的影响。A O A 由于需要特殊的天线阵列测量角度，不符合传感器节点低成本的要求。测距 无关的定位算法主要包括D V - H o p 、D H L 、A P I T 、凸规划等【4 6 1 ，一般根据节点间跳数或几 何特征来估计距离和节点位置。因此，定位精度一般没有基于测距的定位算法高，而且对 网络的拓扑结构有一定要求【4 7 1 。 2 ) 集中式定位与分布式定位【4 8 J ：根据节点的计算方式，定位算法可以分为集中式定 位与分布式定位。集中式计算是指把所需信息传送到某个中心节点，并在那里进行节点定 位计算的方式：分布式计算是指依赖节点间的信息交换和协调，由节点自行计算的定位方 式【4 9 1 。集中式计算的优点在于从全局角度统筹规划，计算量和存储量几乎没有限制，可以 获得相对精确的位置估算。它的缺点包括与中心节点位置较近的节点会因为通信开销大而 过早地消耗完电能，导致整个网络与中心节点信息交流的中断，无法实时定位等【5 0 1 。集中式 定位算法包括凸规划1 3 7 3 引，M D S M A P 【3 5 】等。N - h o pm u l t i l a t e r a t i o n 州m i t i v e 定位算法可以 根据应用需求采用两种不同的计算模式。 3 ) 绝对定位与相对定位：根据节点坐标的实际意义，节点定位可以分为绝对定位与 浙江：【业人学硕士学位论文 相对定位【5 。绝对定位的定位结果是一个标准的坐标位置，如经纬度。而相对定位通常是 以网络中部分节点为参考，建立整个网络的相对坐标系统。绝对定位可为网络提供唯一的 命名空间，受节点移动性影响较小，有更广泛的应用领域。但研究发现，在相对定位的基 础上也能够实现部分路由协议，尤其是基于地理位置的路由，而且相对定位不需要信标节 点。大多数定位系统和算法都可以实现绝对定位服务，典型的相对定位算法和系统有 S P A 【3 6 1 、I S O M A P 和S p o t O N 【2 7 1 。而M D S M A P 【3 5 1 定位算法可以根据网络配置的不同分别 实现两种定位。 1 4 典型定位算法分析 典型定位算法分析对于w S N 定位系统设计具有重要参考作用。以下分别对单跳定位 算法与多跳定位算法的原理及优缺点进行深入分析。 1 4 1 单跳定位算法 1 4 1 1基于T D O A 的定位 目前，基于到达时间差T D O A 的定位原理有两种实现方式1 5 0 】：一是利用单个信号来实 现，发射节点发射一种无线电波，多个接收节点接收到来自同一发射节点的无线电波后， 对信号进行处理，估计发射节点的距离；另外一种是利用不同速率的两个信号实现，即根 据距离与信号速度及到达时间差的关系实现。在此过程中，一般选用速率相差比较大的两 种信号，如射频信号与超声波信号，后者的成本要大于前者。 暴 一 、 X 轴 图l - 2T D O A 定位示意图 - 6 - 浙江j f ：业人学硕十学位论文 使用单个信号完成距离测量的T D O A 原理如图1 2 所示，图中c 代表发射节点， ，屹，巧，代表接收节点，任何两个接收节点间信号到达时间差f 。为： o = 一，J = 圭( 0 一I I ：一0 一l l ：) ，f ( 1 一1 ) 式中，c 是无线电信号传播速度，| f l ：代表二范式，0 分别代表信号到达接收节点的时刻。 同一信号的T D o A 数据处理研究已经比较成熟，其中应用最广泛的是利用卷积来计 算。设两个接收节点接收到同一发射节点的信号分别为s ，s ，则在一定时间间隔丁对信号 的卷积如式( 1 2 ) 所示： 7 。 岛( r ) = 亭p ，( ，) 一( f f ) z 、 ( 1 - 2 ) O 式( 1 2 ) 的计算一般转换到频域来解决，利用傅旱叶变换进行频域分析。在频域上的 信号处理不仅计算方便，且便于在计算之前做滤波处理。T D O A 技术中要求接收节点必须 实现严格的时间同步，但发射节点没有这样的要求。当接收节点位置接近时，信号干扰较 大，且信号到达时间差几乎为零，给测距过程带来很大误差。因此，在利用T D O A 技术测 距时，应当尽量使接收节点相隔较远的距离。 1 4 1 2 基于A O A 的定位 在基于到达角度的定位( A O A ) 中，角度的测量是定位实现的关键，其难度远大于距 离的测量【2 1 。基于A O A 的角度测量如图1 3 所示，其采用超声波技术和天线阵列的方法来 实现。 图1 3A O A 定位原理 炭兜风1 1 1 ：列 基于A O A 的定位示意如图1 4 所示：图1 4 ( a ) 中表示，不存在噪声和干扰源的理想环 - 7 浙江：f ：业人学硕士学位论文 境中，通过三角测量得到的三个接收节点的轴线会交于一点，此点就是发送节点的位置。 图l 一4 ( b ) 表示，实际环境中，由于存在噪声和干扰源，三条轴线的距离不会交于一点，这 样造成三角定位产生误差，因此，角度测量时要尽量选择精度高的测量装置。 7 | R I 、 ：R 、R ( a ) 理想情况 图1 4A o A 定位示意图 ( b ) 实际情况 三角测量法的计算问题已经比较成熟，文献【l 】把它转换为三边定位算法进行求解。文 献【5 2 】考虑噪声的影响，采用极大似然估计的方法。当信标节点比较多时，该方法的定位 效果较好。文献 5 3 】通过加入噪声后的非线性方程进行泰勒展开，并利用最优估计的方法 估计节点坐标。 1 4 1 3基于T O A 的定位 基于到达时间T o A 【5 u 的定位技术原理是：发射节点发射一个信息包，接收节点接收到 ! 信息包后，记录信息传播的时间f ，假设信息的传播速度为c ，则可以估计出发射节点与 接收节点的距离d 为f 和c 的乘积。 幽1 5T o A 定位示意幽 办k 0晨， 、j j R 浙江：L 业大学硕士学位论文 T o A 要求发射节点与接收节点两者的时间必须严格同步，否则无法得知传播的时间。 时间同步的常用实现方式是给传感器节点配置同步时钟或增加网络同步协议。然而，配置 精确的同步时钟无疑会增加节点成本，而增加网络同步机制可能会造成网络协议过于复 杂，且网络通信量的增加很可能造成网络堵塞问题。 文献 6 5 】提出一种“返回式“ 的T o A 技术，成功地解决了时间同步问题，原理如图1 5 所示：首先l 号节点发射无线电波并记录当前时刻，。，2 号节点接收到无线电波后立即返 回给l 号节点，1 号节点接收到返回信息后，记录当前时刻f ：。由于f I f ：都使用节点1 的 时钟，因此无需时间同步，则节点l 与节点2 的估计距离如式( 1 3 ) 所示。 d l2 = c ( f 2 一，I )( 1 - 3 ) 式中，d - 2 为节点l 和2 的估计距离，c 是无线电传播速度，f 。，“分别为发送时刻和接收时 刻。 “返回式“ 的T O A 技术虽然成功解决时间同步问题，但是它以牺牲通信量为代价， 而且接收节点的返回延迟增加了测距误差。当前，更有效的T o A 技术有待进一步研究。 1 4 2 多跳定位算法 1 4 2 1 D V - H o p 算法 D v - H o p 【3 2 1 是A d H o c 网络中一种典型的节点定位方法，因其无需直接测量节点间的距 离信息，而是利用多跳的特征估计距离，是一种容易实现的分布式定位算法，因此广泛应 用于A d H o c 网络中。 D v - H o p 的基本原理是：首先给每个节点都维持一个数据表 工，r ， ，一是跳数，初 始值为零，然后每个节点广播数据包，每经过一个节点，则跳数加l 。当节点接收到来自 同一个节点的跳数值时，检查先前保存的该节点跳数值，若新接收的跳数值小于保存的跳 数值，则更新为较小值。这样，网络中的所有节点都可以获得与其余节点的最小跳数。然 后，利用信标节点的距离和跳数获得整个网络的平均每跳距离，未知节点到信标节点的距 离为最小跳数与平均每跳距离的乘积。最后，未知节点获得信标节点的距离后，可以使用 定位算法估计位置坐标，如三边定位法、极大似然法等。D V H o p 平均每跳距离估计如式 ( 1 4 ) 所示。 一= 墅铲似力 4 ， 式中，麒碱代表第f 个信标节点估计的网络平均每跳距离，( 一，r ) 代表第f 信标节点的位 浙江I ：业人学硕十学位论文 置坐标，忽表示第f 个信标节点到其他所有节点的平均跳数。 D V - h o p 测距原理如图1 - 6 所示，其中蜀，岛，马分别代表信标节点，骂，岛的距离 d ( 且，垦) 为5 0 m ，岛，岛的距