传感网原理与技术第四章--传感网关键技术PPT课件

第四章传感网关键技术,2,主要内容,4.1命名与寻址4.2拓扑控制4.3能量管理4.4时间同步4.5节点定位4.6本章小结与进一步阅读的文献,3,4.1命名与寻址,目的将WSN中的节点赋予逻辑上的名称和地址信息，能够把不同的节点区分开。,4,4.1命名与寻址,基本原理名称（Name）是表示节点、数据、处理等的名字。地址（Address）是为了找到某个事物而提供的相应信息,5,4.1命名与寻址,基本原理在传统的网络中，独立节点、网站以及它们的数据都被命名并分配地址。但是在无线传感器网络中，所有的节点都不是独立的。,6,4.1命名与寻址,基本原理名称、地址和标识符唯一的节点标识符（Uniquenodeidentifier,UID）。UID的设定可以与生产厂家、产品名称和序列号结合起来，在节点生产时就分配好，并且恒定不变。,7,4.1命名与寻址,基本原理名称、地址和标识符MAC地址。在单跳邻近节点之间区分节点地址。在无线传感器网络中，使用基于竞争的MAC协议时，把MAC地址包含在单播MAC分组中，节点就能判断哪些数据分组没有到达。,8,4.1命名与寻址,基本原理名称、地址和标识符网络地址。网络地址是用来在多跳范围内表示和找到某个节点的。因此，网络地址常常与路由关联起来。,9,4.1命名与寻址,基本原理名称、地址和标识符网络标识符。多个无线传感器网络部署在同一区域，如果无线射频芯片是相同的类型并工作在同一频段，就需要通过网络标识符来区分不同的网络。,10,4.1命名与寻址,基本原理名称、地址和标识符资源标识符。名称或资源标识符（Resourceidentifiers）是以用户可以理解的语言表达的，对于用户来说资源标识符具有一定的含义。如，这个名称。,11,4.1命名与寻址,地址管理名称、地址的唯一性全局唯一。地址在全局范围内至多只出现一次。网内唯一。地址在指定的网络内唯一。局部唯一。地址在同一网络中可能会出现几次，但是在某个恰当的邻域范围内是唯一的。,12,4.1命名与寻址,地址管理地址分配。地址再分配。如果地址空间较小，需要回收地址再重新分配。地址表达。地址的冲突检测。绑定。,13,4.1命名与寻址,地址表达地址所需二进制数的长度。假设采用IEEE802.3标准分配地址，在无线传感器网络中，数据分组可能很小，48位长的地址甚至比数据还长。寻址所需要的通信开销。在基于竞争的MAC协议中，任何节点都可能向任何其他节点传送数据，这种情况下地址长度越短越好。,14,4.2拓扑控制,目的形成一个优化的网络拓扑结构。对于延长网络的生存时间、减小通信干扰、提高MAC协议和路由协议的效率等具有重要意义。是WSN中许多研究问题的基础。,15,4.2拓扑控制,设计目标连通。WSN中的节点感知到的数据一般要以多跳的方式传送到汇聚节点。如果至少要去掉k个节点才能使网络不连通，就称该网络是k-连通的。拓扑控制一般要保证网络是1-连通的。,16,4.2拓扑控制,设计目标覆盖。覆盖可以看成是对WSN服务质量的度量，可以分为区域覆盖、点覆盖和栅栏覆盖。如果目标区域中的任何一点都被k个节点监测，就称该网络是k-覆盖的。一般要求目标区域的每一个点至少被一个节点监测，即1-覆盖。,17,4.2拓扑控制,设计目标网络生命期。一般将其定义为：从网络开始运行直到死亡节点的百分比低于某个阈值时的持续时间。我们可以认为网络只有在满足一定的覆盖质量、连通质量、某个或某些其他服务质量时才是存活的。,18,4.2拓扑控制,设计目标吞吐能力。WSN中节点的吞吐率与结点规模n和节点的无线射频芯片的发射半径成反比例关系。通过拓扑控制减小发射半径或减小网络规模，在节省能量的同时，可以在一定程度上提高网络的吞吐能力。,19,4.2拓扑控制,设计目标干扰和竞争。减小通信干扰和MAC层的竞争有助于延长网络生命期。拓扑控制可以调节发射范围或工作节点的数量。这些都能改变1跳邻居节点的个数（也就是与它竞争信道的节点数），从而减小干扰和减少竞争。,20,4.2拓扑控制,设计目标网络延迟。当网络负载较高时，较低的发射功率会带来较小的端到端延迟；而当网络负载较低时，较低的发射功率会带来较大的端到端延迟。,21,4.2拓扑控制,功率控制为WSN中的节点选择合适的发射功率。但是求解最优的发射功率控制问题是NP难的，因此只需寻找实用解。当前的一些解决方案的基本思想都是通过降低发射功率来延长网络的生命期。,22,4.2拓扑控制,功率控制基于节点度的功率控制基于邻近图的功率控制分布式功率分配算法XTC集中式功率分配算法COMPOW,23,4.2拓扑控制,基于节点度的功率控制算法思想一个节点的度数是指所有距离该节点一跳的邻居节点的数目。WSN中每个节点可以通过功率控制机制调节发射功率，以均衡节点的单跳可达邻居数量的方式优化网络拓扑结构，改进系统的相关性能。代表性算法：LMA，LMN。,24,4.2拓扑控制,基于节点度的功率控制LMA（本地平均算法）开始时所有节点都有相同的发射功率TransPower，每个节点定期广播一个包含自己ID的LifeMsg消息。如果节点接收到LifeMsg消息，发送一个LifeAckMsg应答消息。该消息中包含所应答的LifeMsg消息中的节点ID。,25,4.2拓扑控制,基于节点度的功率控制LMA（本地平均算法）每个节点在下一次发送LifeMsg时，首先检查已经收到的LifeAckMsg消息，利用这些消息统计出自己的邻居数NodeResp。如果NodeResp小于下限NodeMinThresh，那么节点在这轮发送中将增大发射功率；同理，如果NodeResp大于上限NodeMaxThresh，那么节点将减小发射功率。发射功率的范围为：最大为Bmax倍的，最小为Bmin倍的TransPower。,26,4.2拓扑控制,基于节点度的功率控制LMA（本地平均算法）发射功率计算方法：其中，Bmax,Bmin,Ainc,Adec是可调参数。,27,4.2拓扑控制,基于节点度的功率控制LMN（本地邻居平均算法）与LMA相比，仅在以下步骤中不同：如果节点接收到LifeMsg消息，发送一个LifeAckMsg应答消息。该消息中包含节点自己的邻居数。每个节点在下一次发送LifeMsg时，首先检查已经收到的LifeAckMsg消息，将消息中的所有邻居数求平均值作为自己的邻居数NodeResp。,28,4.2拓扑控制,基于邻近图的功率控制算法思想邻近图可以用G=(V,E)的形式表示，其中V代表图中顶点的集合，E代表图中边的集合。设所有节点都使用最大发射功率发射时形成的拓扑图是G，按照一定的邻居判别条件求出该图的邻近图G，每个节点以自己所邻接的最远节点来确定发射功率。代表性算法：DRNG，DLMST。,29,4.2拓扑控制,基于邻近图的功率控制基本定义E中的元素可以表示为l=(u,v)，其中u,vV。所有由一个图G=(V,E)导出的邻近图G=(V,E)是指：对于任意一个节点vV，给定其邻居的判别条件q，E中满足q的边(u,v)属于E。,30,4.2拓扑控制,基于邻近图的功率控制基本定义(u,v)和(v,u)是两组不同的边，即边是有向的。d(u,v)表示节点u、v之间的距离，r(u)代表节点u的通信半径。,31,4.2拓扑控制,基于邻近图的功率控制基本定义可达邻居集合代表节点u以最大发射半径可以到达的节点集合，有节点u和以及这些节点之间的边构成可达邻居子图,32,4.2拓扑控制,基于邻近图的功率控制基本定义定义由节点u和v构成边的权重函数w(u,v)满足:上述关系式中，id(x)表示节点x的编号,33,4.2拓扑控制,基于邻近图的功率控制准备阶段每个节点以自己的最大发射功率广播HELLO消息，该消息中至少要包括自己的ID和自己所在的位置。这个阶段完成后，每个节点通过接收到的HELLO消息确定自己可达的邻居集合,34,4.2拓扑控制,基于邻近图的功率控制DRNG算法假设节点u、v满足条件，且不存在另一节点p同时满足，时，节点v则被选为节点u的邻居节点。,35,4.2拓扑控制,基于邻近图的功率控制DLSS算法假设已知节点u以及它的可到达邻居子图，将p到所有可达邻居节点的边以权重为标准按升序排列；依次取出这些边，直到u与所有可达邻居节点直接相连或通过其他节点相连；最后，与u直接相连的节点构成u的邻居集合。,36,4.2拓扑控制,基于邻近图的功率控制结束阶段经过执行DRNG和DLSS算法后，节点u确定了自己的邻居集合，然后将发射半径调整为到最远邻居节点的距离。更进一步，通过对所形成的拓扑图进行边的增删，使网络达到双向连通。,37,4.2拓扑控制,基于邻近图的功率控制DRNG算法、DLSS算法对比(a)优化前(b)DRNG优化(c)DLSS优化,38,4.3能耗优化技术,传感器节点的体系结构传感器节点由电源、感知、计算和通信四个子系统组成,39,4.3能耗优化技术,传感器节点的能耗分布节点传输1比特数据所消耗的能量与MCU执行1000条指令的能耗大致相当,40,4.3能耗优化技术,节点能耗分布的共性通信子系统的功耗高于计算子系统Radio的传输、接收和空闲状态的功耗位于同一数量级，而休眠状态的功耗较低感知子系统的能耗取决于传感器的类型，可能成为另一主要的能耗来源,41,4.3能耗优化技术,能耗优化的对象网络子系统以“计算”换“通信”Radio无需通信时应尽量置于休眠状态感知子系统,42,4.3能耗优化技术,Radio的体系结构功耗模型通信能耗模型,43,4.3能耗优化技术,节能策略概览,44,4.3能耗优化技术,节点级能量优化来自于传统的嵌入式系统节能技术硬件技术、软件技术功耗感知计算DPM、DVS能量感知的软件技术低功耗操作系统、任务调度射频管理技术关键在于决定何时关闭射频芯片,45,4.3能耗优化技术,无线通信级能量优化优化节点的单跳通信能耗可进一步分为：物理层、数据链路层、MAC层、功率控制、协作通信技术、认知通信技术和网络编码技术物理层：DMCS根据网络通信流量和无线信道状况，动态调整信号调制和编码参数数据链路层：差错控制技术,46,4.3能耗优化技术,网络级能量优化从网络全局的角度优化、调度各节点的计算和通信任务，强调节点间的相互协作以提高全局网络的生存周期路由技术多径路由和自适应逐跳路由节点休眠状态调度Sleep/Wakeup协议网络体系结构技术平面型WSNvs.分簇WSN（层次型WSN）,47,4.3能耗优化技术,基于数据的能量优化从数据角度减少网络中不必要的通信和数据操作，提高整个系统的能量有效性，包括数据的采集、处理和存储等技术数据冗余感知数据具有较强的时间和空间相关性数据压缩、网内数据处理感知子系统的功耗不可忽略优化节点的数据采集活动数据预测技术、用计算换通信,48,4.3能耗优化技术,基于移动的能量优化产生移动的原因移动作为网络设施的一部分移动作为感知环境的一部分移动Sink、移动Relay如何控制节点的移动以优化网络性能、提高网络的能量有效性,49,4.3能耗优化技术,EnergyHarvesting技术为节点补充能量太阳能技术无线充电技术最新研究热点如何实现节点/网络的能量“收支平衡”,50,4.4时间同步,基础概念由于WSN中节点的晶体振荡器频率存在偏差，以及温度变化和电磁干扰等，他们的时间会逐渐出现偏差。在像WSN这类分布式系统的协同工作中，节点间的时间必须保持同步，因此时间同步是分布式系统中的一个关键技术。,51,4.4时间同步,基本原理WSN中节点的本地时钟依靠对自身晶振的计数实现，晶振的频率误差和初始计时时刻不同，就使得节点之间的本地时钟不同步。若能估算出本地时钟与物理时钟的关系或者本地时钟之间的关系，就可以构造对应的逻辑时钟实现同步。,52,4.4时间同步,基本原理节点时钟通常用晶体振荡器脉冲来度量，所以任意一节点在物理时刻的本地时钟读数可表示为：-节点i的晶振的实际频率，-节点晶振的标准频率；-开始计时的物理时刻，-节点i在时刻的时钟读数。,53,4.4时间同步,时间差异的来源节点开始计时的初始时间不同；每个节点的石英晶体可能以不同的频率跳动，导致时钟值逐渐偏离，称为偏差误差；随着时间推移，时钟老化或随着周围环境如温度的变化而导致时钟频率的变化，称为漂移误差。,54,4.4时间同步,时间同步的挑战能耗可扩展性；时间的同步应容忍节点数目变化和密度变化同步时间；同步时间越长，所需的通信量、计算量就越大，能耗也越高同步精度,55,4.4时间同步,时间同步方法、分类事件同步，要能够实现对事件的排序，即能够对事件的发生顺序作出判断。相对同步，绝对同步，不同点在于是否能够修改节点的本地时间。局部同步，全网同步，局部部分节点之间，或者网络中所有节点之间维护时间一致。,56,4.4时间同步,事件同步在使用无线传感器网络追踪移动目标时，捕获到移动目标的多个节点将会记录移动目标的位置l和经过时间t，由位置l和经过时间t构成的消息称为事件。多个节点将探测到的事件发送到一个指定节点，该指定节点可以动态的根据这些消息预测节点的速度，运动方向。,57,4.4时间同步,事件同步（TMOS）消息到达接收节点的顺序与发送节点发送的顺序一致；节点1,2,3,4构成一个逻辑上的环。,58,4.4时间同步,事件同步（TMOS）节点3如果要发送探测到的事件m3，必须沿着环在两个方向上向节点4分别发送一次事件m3和m3。事件m3沿着时钟方向到达节点4，事件m3沿着反向时钟方向到达节点4。,59,4.4时间同步,事件同步（TMOS）节在收到事件m3后，节点1检查是否本地产生的事件都已发送出去，接着再把m3转发到节点4。在收到事件m3后，节点2检查是否本地产生的事件都已发送出去，接着再把m3转发到节点4。,60,4.4时间同步,事件同步（TMOS）如果节点1（2）需要向节点4发送本地产生的事件m1（m2），也要沿着环发送两次事件。节点4将会在收到第二个m3事件之前收到每个时间戳早于m3.t的事件至少1次。,61,4.4时间同步,事件同步（TMOS）总结根据事件同步模型，当一个事件的第二次消息到达节点4时，能够保证所有早于该事件的事件都至少已被节点4接收到一次。也就是说，当一个事件转交给应用程序时，除非所有节点产生的时间戳早于该事件的消息都已被转交给应用程序处理。,62,4.4时间同步,局部同步RBS原理RBS在接收者之间相互同步。,63,4.4时间同步,局部同步RBS原理发送节点发送的消息不是为了向接收节点通知发送节点的时间，而是为了激发接收节点同时记录各自的本地时间,64,4.4时间同步,局部同步RBS原理发送节点发送的消息不是为了向接收节点通知发送节点的时间，而是为了激发接收节点同时记录各自的本地时间，并交换各自最近记录的多个时刻信息。,65,4.4时间同步,局部同步RBS原理RBS采用最小平方误差的线性回归方法对时间偏移数据进行线性拟合，经过对时间漂移的补偿后，接收节点间的同步误差可以在较长时间内保持在较小的范围内。,66,4.4时间同步,全网同步RBS全网同步原理,针对节点1,9：节点9和节点4以及节点4和节点1根据局部RBS可以实现时间互换，因此，经由节点4，节点1和节点9的本地时间可以相互转换。,67,4.4时间同步,全网同步RBS全网同步原理,在网络规模较大时，依靠静态指定中转节点不能够保证同步协议的健壮性，需要采用“时间路由”寻找一条连接同步源节点和目标节点本地时间的转换路径。,68,4.4时间同步,全网同步RBS全网同步原理,右图是左图的逻辑拓扑结构，在每个单跳网络范围内，如果两个节点可以直接进行本地时间转换，在逻辑拓扑结构中，两个节点之间就有一条边连接。,69,4.4时间同步,全网同步RBS全网同步原理,通过在右图中的逻辑结构中寻找一跳连接源节点和目标节点的最短路径，那么，沿着该路径可以逐跳进行两节点之间的时间同步。,70,4.5节点定位,基本概念将WSN中需要定位的节点称为未知节点（unknownnode）；已知位置，并协助未知节点定位的节点称为锚节点（anchornode）或信标节点。,71,4.5节点定位,定位方法测距定位（range-based）通过测量节点间点到点的距离或角度信息，使用三边测量（trilateration）、三角测量（triangulation）或最大似然估计（multilateration）法计算未知节点位置。常见测距定位方法：到达时间（TOA），到达时间差（TDOA），接收信号强度。,72,4.5节点定位,定位方法非测距定位（range-free）无须距离和角度信息，仅根据网络连通性等信息即可确定未知节点的位置。常见非测距方法：质心定位，平均跳数距离（DV-Hop），近似三角形内点测试（APIT）。,73,4.5节点定位,节点位置的计算方法三边测量法当未知节点D(x,y)获取其到三个（或三个以上）信标节点的距离时，可通过距离公式