专题2(无线传感器网络专题)

专题2(无线传感器网络专题)第一页，共88页。第三章无线传感器网络WSN无线传感器网络的基本概念无线传感器网络的应用无线传感器网络中的几种典型路由协议无线传感器网络中的拓扑控制技术无线传感器网络中的几个研究热点第二页，共88页。1.1无线传感器网络的基本概念无线传感器网络的历史第一代传感器网络：无线传感器网络的构想最初是由美国军方提出的，美国国防部高级研究所计划署（DARPA）于1978年开始资助卡耐基－梅隆大学进行分布式传感器网络的研究。通过将传统传感器采用点对点传输、连接传感控制器而构成传感器网络雏形。第二代传感器网络：传感器网络具有了获取多种信息信号的综合处理能力，并通过与传感控制器的相联，组成了有信息综合和处理能力的传感器网络。第三代传感器网络：从上世纪末开始，现场总线技术开始应用于传感器网络，人们用其组建智能化传感器网络，大量多功能传感器被运用，并使用无线技术连接，无线传感器网络逐渐形成。第三页，共88页。发展背景1.1无线传感器网络的基本概念第四页，共88页。1.1无线传感器网络的基本概念无线传感器网络的定义无线传感器网络是大量的静止或移动的传感器以自组织和多跳的方式构成的无线网络,其目的是协作地感知、采集、处理和传输网络覆盖地理区域内感知对象的监测信息,报告给用户。无线传感器网络WSN（WirelessSensorNetwork）也称为智能灰尘（Smart

Dust）。被称为二十一世纪最具挑战性的研究课题之一。第五页，共88页。传感器节点拓扑结构：从上图我们可以看到一个典型的传感器节点由数据获取单元、数据处理单元、数据传输单元、以及能量供应单元四部分组成。每一个模块的功能如下：第六页，共88页。1.1无线传感器网络的基本概念传感器节点各部分的功能数据获取单元：负责监视区域内信息的采集和数据转换。数据处理单元：负责控制整个传感器节点的操作，存储处理本身采集的数据以及其它节点发来的数据。数据传输单元：负责与其它传感器节点进行无线通信，交换控制信息和收发采集数据。能量供应单元：为传感器节点提供运行所需的能量，通常采用微型电池。第七页，共88页。传感器实物体积小能耗小能量受限处理能力受限存储能力受限1.1无线传感器网络的基本概念第八页，共88页。WSN的网络拓扑结构

结构如上图所示，传感器网络系统通常包括传感器节点（sensornode），汇聚节点（sinknode），和管理节点。大量传感器节点随机的部署在检测区域内部或附近，能够通过自组织方式构成网络。传感其节点检测的数据沿着其它节点逐跳的进行传输，其传输过程可能经过多个节点处理，经过多跳后到达汇集节点，最后通过互联网和卫星达到管理节点，用户通过管理节点对传感器网络进行配置和管理，发布检测任务以及收集检测数据。1.1无线传感器网络的基本概念互联网和卫星任务管理中心用户汇聚节点监测区域传感器节点BAC第九页，共88页。

WSN的相关技术无线传感器网络是应用相关性网络，是一种应用中产生和发展的技术，所以不同的应用领域使用不同的网络技术实现，目前实现WSN的主要技术有：Zigbee：一种近距离（10-75m）、低复杂度、低功耗（两节普通５号干电池可使用２年

）、低数据速率（250Kbps）、低成本的无线网络技术。WI-FI：无线保真技术（WirelessFidelity），一种短距离（目前已达几百公里）无线技术。最大传输数据速率为54Mbps。BlueTooth：蓝牙，传输距离一般在10m左右，最大传输数据速率小于10M。UWB：一种超宽带（UltraWideBand）的短距离（10m左右）通信技术

，1GHz以上带宽。1.1无线传感器网络的基本概念第十页，共88页。1.1无线传感器网络的基本概念无线传感器网络的特点与挑战：节点带宽窄，节点通信覆盖范围只有几十到几百米,而且经常变化挑战：如何在如此有限通信能力的条件下,高质量地完成感知数据的查询、分析、挖掘与传输？多源、多跳是主要通信方式挑战：如何为多源信息传输选择优化通信路径？第十一页，共88页。1.1无线传感器网络的基本概念无线传感器网络的特点与挑战（Cont.）：节点移动、断接频繁挑战：通信路径重构成为突出问题？路由算法必须具有自适应性？节点电源能量有限、且难于补充挑战：如何传感器网络在工作过程中节省能，实现能源均衡，最大化网络生命周期？节点计算能力有限挑战：如何使用大量具有有限计算能力的传感器设计能源有效的高性能分布式算法?第十二页，共88页。1.1无线传感器网络的基本概念无线传感器网络的特点与挑战（Cont.）：传感器数量大、分布范围广挑战：如何使传感器网络软硬件具有高强壮性和容错性？感知数据流无限挑战：如何设计高效率、能源有效、实时的海量感知数据流的查询、分析和挖掘的分布式算法？传感器网络是以数据为中心的网络挑战：如何建立以数据为中心的传感器网络?第十三页，共88页。1.1无线传感器网络的基本概念无线传感器网络的特点与挑战（Cont.）：挑战：传感器的投放或撒播理论与技术挑战：传感器的定位问题挑战：时钟同步问题

挑战：组网连通可靠性研究和探测覆盖率研究

挑战：传感器网络安全性问题和抗干扰问题挑战：信号的协作处理第十四页，共88页。1.2无线传感器网络的应用军事应用:作战环境侦查与监控军事侦查、情报获取战场监测与指挥民事应用:环境监测交通管理灾难预防(如森林火灾监测)危险区域监测有灭绝危险或珍贵动物的跟踪监护民用和工程基础设施的安全性监测等等，等等第十五页，共88页。大地与环境监测1.2无线传感器网络的应用第十六页，共88页。1.2无线传感器网络的应用第十七页，共88页。1.2无线传感器网络的应用第十八页，共88页。

污染流监控1.2无线传感器网络的应用第十九页，共88页。Sensorattachedtoeveryvehicle.Capableofdetectingtheirlocation,vehiclesizes,speedsand;roadconditions…Alternateroutes,estimatetriptimes…

TrafficControl1.2无线传感器网络的应用第二十页，共88页。

BiologicalSystems1.2无线传感器网络的应用第二十一页，共88页。作战环境侦查1.2无线传感器网络的应用第二十二页，共88页。空间探测：对星球表面的监测和探索1.2无线传感器网络的应用第二十三页，共88页。1.2无线传感器网络的应用无线传感器网络的最新应用：

2004/03/18日经BP社报道】英特尔向美国政府人员等演示了无线传感器网络的家庭护理技术。通过在鞋、家具以家用电器等家中道具和设备中嵌入半导体传感器，帮助老龄人士、阿尔茨海默氏病患者以及残障人士的家庭生活。利用无线通信将各传感器联网可高效传递必要的信息从而方便接受护理。而且还可以减轻护理人员的负担。第二十四页，共88页。1.2无线传感器网络的应用无线传感器网络的最新应用（Cont.）：

著名的沃尔玛连锁店已经投入资金，在其货物上加装射频识别条型码芯片（RFID），使该公司和供应商能够跟踪从生产厂到收款台的商品流向。这种技术可望减少商品失窃率和其他损失，并能节省仓库占用及商店的人力成本。目前每个条型码芯片的成本为24美分，未来将会降到仅仅几美分。第二十五页，共88页。1.2无线传感器网络的应用无线传感器网络的最新应用（Cont.）：

美国约克国际公司为6万家客户管理通风系统。计划在未来5年内，为其客户的空调装置上安装几万个网络化的传感器。传感器将监视温度，并自动地将最新信息传送给办公室，从而使维修人员对客户的空调运行状况一目了然。大大减少该公司2444名技术人员的工作负荷，使生产力提高15％。第二十六页，共88页。1.2无线传感器网络的应用无线传感器网络的最新应用（Cont.）：

美国《每日防务》2004年3月18日报道无线传感器网络技术将会在战场上带来革命性的变化，并将改变战争的样式。它不仅可以感觉到运动的或静止的金属，而且可以感觉到声音、光线、温度、化学物品，以及动植物的生理特征。无线传感器网络技术，预示着为战场上带来新的电子眼和电子耳，“能够在未来几十年内变革战场环境”。第二十七页，共88页。1.3无线传感器网络中的几种典型路由协议WSN路由协议面临的挑战:考虑网络和节点能量优化（能量受限&难于补充）具有高可扩展性（网络规模&自组织）适应强网络拓扑变化（节点移动&无线信道）适应非规则数据流量分布（以数据为中心&数据流）具有一定的安全性（处理能力受限&存储能力受限）第二十八页，共88页。1.3无线传感器网络中的几种典型路由协议WSN路由协议的分类:

WSN路由协议负责在Sink点和Sensor节点间可靠地传输数据。由于WSN与应用高度相关，单一的路由协议不能满足各种应用需求，因而人们研究了众多的路由协议。根据路由协议采用的通信模式、路由结构、路由建立时机、状态维护、节点标识和投递方式等策略，可对其进行了如下分类：根据传输过程中采用路径的多少，可分为单路径路由协议和多路径路由协议。单路径路由节约存储空间，数据通信量少，多路径路由容错性强，健壮性好，且可从众多路由中选择一条最优路由。第二十九页，共88页。1.3无线传感器网络中的几种典型路由协议WSN路由协议的分类（Cont.）:根据节点在路由过程中是否有层次结构、作用是否有差异，可分为平面路由协议和层次路由协议。平面路由简单，健壮性好，但建立、维护路由的开销大，数据传输跳数多，适合小规模网络。层次路由扩展性好，适合大规模网络，但簇的维护开销大，且簇头是路由的关键节点，其失效将导致路由失败。第三十页，共88页。1.3无线传感器网络中的几种典型路由协议WSN路由协议的分类（Cont.）:根据路由建立时机与数据发送的关系，可分为主动路由协议、按需路由协议和混合路由协议。主动路由建立、维护路由的开销大，资源要求高。按需路由在传输前需计算路由，时延大。混合路由则综合利用这两种方式。根据是否以地理位置来标识目的地、路由计算中是否利用地理位置信息，可分为基于位置的路由协议和非基于位置的路由协议。有大量WSN应用需要知道突发事件的地理位置，这是基于位置的路由协议的应用基础，但需要GPS定位系统或者其他定位方法协助节点计算位置信息。第三十一页，共88页。1.3无线传感器网络中的几种典型路由协议WSN路由协议的分类（Cont.）:根据是否以数据来标识目的地，可分为基于数据的路由协议和非基于数据的路由协议。有大量WSN应用要求查询或上报具有某种类型的数据，这是基于数据的路由协议的应用基础，但需要分类机制对数据类型进行命名。根据节点是否编址、是否以地址标识目的地，可分为基于地址的路由协议和非基于地址的路由协议。基于地址的路由在传统路由协议中较常见，而在WSN中一般不单独使用而与其他策略结合使用。第三十二页，共88页。1.3无线传感器网络中的几种典型路由协议WSN路由协议的分类（Cont.）:根据路由选择是否考虑QoS约束，可分为保证QoS的路由协议和不保证QoS的路由协议。保证QoS的路由协议是指在路由建立时，考虑时延、丢包率等QoS参数，从众多可行路由中选择一条最适合QoS应用要求的路由。根据数据在传输过程中是否进行聚合处理，可分为数据聚合的路由协议和非数据聚合的路由协议。数据聚合能减少通信量，但需要时间同步技术的支持，并使传输时延增加。第三十三页，共88页。1.3无线传感器网络中的几种典型路由协议WSN路由协议的分类（Cont.）:根据路由是否由源节点指定，可分为源站路由协议和非源站路由协议。源站路由协议节点无须建立、维护路由信息，从而节约存储空间，减少通信开销。但如果网络规模较大，数据包头的路由信息开销也大，而且如果网络拓扑变化频繁，将导致路由失败。根据路由建立时机是否与查询有关，可分为查询驱动的路由协议和非查询驱动的路由协议。查询驱动的路由协议能够节约节点存储空间，但数据时延较大，且不适合环境监测等需紧急上报的应用。第三十四页，共88页。几种代表性的WSN路由协议:基于梯度(Gradient)的路由协议DD(DirectedDiffusion)基于协商机制(Negotiation)的路由协议SPIN(SensorProtocolforInformationviaNegotiation)基于位置信息(LocationInformation)的路由协议GEAR(GeographicandEnergyAwareRouting)基于单层簇的路由协议LEACH(LowEnergyAdaptiveClusteringHierarchy)基于多层簇的路由协议TTDD(TwoTierDataDissemination)基于谣言的路由协议Rumor无线传感器网络的组播与选播路由协议1.3无线传感器网络中的几种典型路由协议第三十五页，共88页。1.3.1DD(DirectedDiffusion)

DD是一种查询驱动的DC(Data-Centric)路由协议。在DC协议中，源节点采集的原始数据首先在某些中间节点处进行合并处理，然后再将汇聚后的数据统一发送到目的节点，从而实现减低通信开销，达到节能的目的。基于DC路由协议的数据传播模型如下。

第三十六页，共88页。1.3.1DD(DirectedDiffusion)

DD采用基于消息驱动(Information-Driven的数据传播模式，以节点可以提供的数据作为寻址依据，即Sink节点在网络中广播以某种数据格式构成的消息来告之所有传感节点它所感兴趣的监测数据，这种消息简称为兴趣(Interests)。DD协议的工作原理如下：Step1（请求扩散）：Sink节点发出的兴趣查询逐级扩散，最终遍历全网，找到所有匹配的原始数据。

第三十七页，共88页。1.3.1DD(DirectedDiffusion)

DD协议的工作原理（Cont.)：Step2（梯度场建立）：在Sink节点的兴趣扩散过程中，有一个称为“梯度(Gradient)”的变量与整个业务请求的扩散过程相联系，其反映了网络中间节点对匹配请求条件的数据源的近似判断。

第三十八页，共88页。1.3.1DD(DirectedDiffusion)

DD协议的工作原理（Cont.)：Step3（数据传输）：传感节点通过与Sink节点的兴趣匹配，最终将会在整个网络中为Sink节点的请求建立一个临时的“梯度”场，从而使得匹配数据可以沿“梯度”最大的方向中继返回Sink节点。数据在回传Sink节点的过程中，算法将利用沿途的中间节点进行数据汇聚处理，从而使得数据传输的通信开销减低，达到节能的目的。第三十九页，共88页。1.3.1DD(DirectedDiffusion)

DD协议的优缺点：其优点是由于“梯度”场的建立及采用了数据汇聚思想，因此DD协议比较节能。其缺点是“梯度”场的建立过程复杂、Sink节点的兴趣广播采用洪泛(Flooding)机制、数据均沿最短路径进行传输，没考虑均衡所有节点的能量消耗，不具有能量感知功能，因此，算法易于使得部分节点因能耗过大而失效，从而导致网络的拓扑结构经常变化，影响了算法的路由性能。第四十页，共88页。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN是第一个采用DC思想的基于洪泛的路由协议。洪泛协议具有延时小和分布式的特点。

SPIN的主要思想是通过协商机制来解决洪泛协议中的”内爆”问题。

在SPIN中，传感节点通过广播发送数据的描述信息，而不是真实数据，仅当有相应的数据请求时，才有目的地发送实际数据，从而通过减低数据广播的通信开销来达到节能的目的。

SPIN的路由原理图如下：第四十一页，共88页。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN协议的工作原理:Step1：SPIN包括三种类型的数据：ADV、REQ以及DATA。在实际广播DATA消息前，如图的Step1所示，源节点首先向邻节点广播携带DATA描述的ADV消息。第四十二页，共88页。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN协议的工作原理(Cont.):Step2：若某个邻节点对该DATA消息感兴趣，则该邻节点将如图的Step2所示，通过回送REQ消息来向源节点申请数据DATA。第四十三页，共88页。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN协议的工作原理(Cont.):Step3：源节点在收到REQ消息后，再如图的Step3所示，将实际采集的DATA消息发送给该邻节点。第四十四页，共88页。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN协议的工作原理(Cont.):Step4-6：该邻节点在收到DATA之后，将如图的Step4~6所示，重复上述路由过程，最后，网络中所有对该DATA消息感兴趣的节点均可收到该消息的一份拷贝。第四十五页，共88页。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

SPIN协议的优缺点:与传统Flooding协议相比，由于SPIN采用三步握手(ADV-REQ-DATA)协商机制与邻节点协商解决洪泛算法中的“内爆”与“重叠”问题，因此比传统Flooding协议要更加节能。另外，无需路由维护，对网络拓扑变化不敏感。其缺点是要求所有节点均具有路由功能，因此节点的路由开销大。

第四十六页，共88页。1.3.2SPIN(SensorProtocolforInformationviaNegotiation)

Flooding协议的“内爆”与“重叠”问题:“内爆”：节点向邻节点转发数据，而不管其是否已经收到相同的数据。“重叠”：传感器节点感知区域有重叠，导致数据冗余。

第四十七页，共88页。1.3.3GEAR(GeographicandEnergyAwareRouting)

GEAR是一种基于位置信息的DC路由协议。在GEAR协议中，传感节点首先利用GPS定位装置通过卫星定位等方式来获知自己的地理坐标位置，同时假定其知道目标区域的位置信息。然后利用目标区域的位置信息与邻节点的能量信息来决定路由的下一跳，直到将数据发送到目标区域(TargetRegion)R。当数据发送到目标区域R之后，在R内，算法将目标区域分解为几个子区域再利用一种递归地理转发算法(RecursiveGeographicForwarding)来将数据向各个子区域的中心位置分发。

第四十八页，共88页。1.3.3GEAR(GeographicandEnergyAwareRouting)

GEAR协议中的递归地理转发算法原理：图中假设目标区域R是一个矩形区域，且节点Ni收到发送给R的数据包P。此时，Ni将首先发现自己在目标区域R之中，然后如图所示，Ni将R划分为4个子区域，然后生成4个包P的拷贝分别转发到R的4个子区域(Sub-Region)。当子区域中的某个节点收到数据包P后，重复上述过程，显然最终所有目的节点均能收到源节点发送的数据包P。

第四十九页，共88页。1.3.3GEAR(GeographicandEnergyAwareRouting)

GEAR的优缺点：优点：利用位置信息和递归地理转发算法，避免了使用Flooding来查询消息。缺点：不适合在移动WSN中使用。

第五十页，共88页。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)

LEACH是第一个提出数据聚合思想的单层簇DC协议。其主要思想为通过在每个周期内通过一个概率函数随机选择簇头(ClusterHead),由簇头来平均分担中继通信业务以实现延长网络生命周期的目的。一旦簇头被选定，则簇成员(ClusterMember)节点将采集到的监测数据传与簇头，簇头在进行必要的数据汇聚处理之后，再将汇聚数据直接发送到用户。LEACH具有能量感知功能，能均衡节点的能量消耗，提高网络的稳定性与生命周期；但算法中对簇头可通过长距离信号发射直接与用户进行通信的假设不切实际，因此算法的实用性较差。

第五十一页，共88页。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)

LEACH中概率函数的推导过程需求：让所有节点轮流成为簇头，从而使得网络中各节点的能耗更加均匀。Step1：首先要确定得经过多少轮才能使得所有节点都有机会能成为簇头？显然，为了解决该问题，则需要增加一个限制条件，即需要预先知道将整个网络划分为多少个簇，否则问题将无法求解。基于上述分析，因此可先给出一个假定如下：假定簇头节点占网络节点总数的百分比为p。由该假定即可计算出经过1/p轮才能使得所有节点都有机会能成为簇头。第五十二页，共88页。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)

LEACH中概率函数的推导过程(Cont.)Step2：显然，在最近1/p轮中已经成为过簇头的节点不能再成为簇头。因此，可初步设计判定节点n在当前轮中成为簇头的概率函数T(n)如下：T(n)=0，若nG，其中G表示网络中最近1/p轮未当选簇头的节点的集合。显然，现在剩下的问题是需要针对nG时给出其在当前轮中成为簇头的概率函数T(n)。Step3：那么，如何确定T(n)呢？先考虑最特殊的情形，假定当前轮为第1/p轮，显然，所有未当选为簇头的节点均需要当选为簇头，即nG时，其成为簇头的概率函数T(n)应等于1。因此，可修正判定节点n在当前轮中成为簇头的概率函数T(n)如下：T(n)=1，若nG，且rmod1/p=1/p-1{即1/p–(rmod1/p)=1}，其中r表示到目前为止经过的总的轮数。至此，剩下的问题为仅需要确定当nG，且1/p–(rmod1/p)1时其在当前轮中成为簇头的概率函数T(n)。

第五十三页，共88页。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)

LEACH中概率函数的推导过程(Cont.)Step4：显然，节点n在最近1/p轮中越晚未当选为簇头，其应以越大的概率在当前轮中成为簇头，即当1/p-(rmod1/p)越小，则节点n在当前轮中成为簇头的概率应越大。因此，可修正判定节点n在当前轮中成为簇头的概率函数T(n)如下：T(n)==，若nG。Step5：综上所述，可得到节点n在当前轮中成为簇头的概率函数T(n)如下：第五十四页，共88页。1.3.4LEACH(LowEnergyAdaptiveClusteringHierarchy)LEACH的优缺点：优点：使得网络中节点的能耗更加均匀。

缺点：不能保障簇头节点能够遍及整个网络，也不能保证簇的大小近似均匀。

第五十五页，共88页。1.3.5TTDD(TwoTierDataDissemination)

TTDD是一种基于层次簇的路由协议，其适用的环境为静止传感区域内的移动Sink节点的情形。在TTDD协议中，由源节点首先基于节点的位置信息分布式地将传感区域划分成网格(Grid)，同时为每个网格确定一个传播节点(Disseminationnode)，并使得相邻传播节点之间的距离为1跳；源节点默认为其所在网格的传播节点。

在实际进行路由时，Sink节点利用不同方式分两个层次进行路由。

首先Sink节点利用洪泛在自己所属的网格内广播查询，直到查询消息到达其所属网格的传播节点；该路由过程称为”低层”路由。当查询到达Sink节点所属网格的传播节点后，传播节点直接将查询转发给自己相邻网格的传播节点，依次类推，直到查询到达源节点；该路由过程称为”高层”路由。源节点在传输数据时，数据通过传播节点的转发最终到达Sink节点，在传输过程中，传播节点对数据进行汇聚处理，从而可以减低数据的传输开销，达到节能的目的。

第五十六页，共88页。1.3.5TTDD(TwoTierDataDissemination)

TTDD的优缺点：优点：提出了一种新的应用场景，支持Sink移动的网络环境。

缺点：需要地理位置信息的支持，且网格大小不容易确定。

第五十七页，共88页。1.3.6Rumor

Rumor的工作原理：如果Sink点的一次查询只需一次上报，DirectedDiffusion协议开销就太大了，Rumor协议正是为解决此问题而设计的。该协议借鉴了欧氏平面图上任意两条曲线交叉几率很大的思想。当节点监测到事件后将其保存，并创建称为Agent的生命周期较长的包括事件和源节点信息的数据包，将其按一条或多条随机路径在网络中转发。收到Agent的节点根据事件和源节点信息建立反向路径，并将Agent再次随机发送到相邻节点，并可在再次发送前在Agent中增加其已知的事件信息。Sink点的查询请求也沿着一条随机路径转发，当两路径交叉时则路由建立。如不交叉，Sink点可flooding查询请求。

在多Sink点、查询请求数目很大、网络事件很少的情况下，Rumor协议较为有效。但如果事件非常多，维护事件表和收发Agent带来的开销会很大。

第五十八页，共88页。1.3.7无线传感器网络的组播与选播路由协议

目前，无线传感器网络路由协议着重研究的基本上是单播(Unicast)路由。事实上，在传感器网络应用中还经常要求提供组播(Multicast)和选播(Anycast)支持技术。例如，在对军事目标的监控中经常要求对同一目标进行分组监测等。而组播与选播技术的引入必将导致对服务质量的要求。目前，典型的QoS组播和选播算法包括：QoS组播算法：Mobicast(Mobicast:Just-in-timemulticastforsensornetworksunderspatiotemporalconstraints)、VLM2(VeryLightweightMobileMulticast)等。QoS选播算法：SARP(Sink-basedAnycastRoutingProtocol)等。

第五十九页，共88页。1.3.7无线传感器网络的组播与选播路由协议

组播、广播、单播、选播的定义：组播：是指一台主机与一组目的主机之间的通信。广播：是指一台主机与所有目的主机之间的通信。单播：是指一台主机与另一台目的主机之间的通信。从投递目的地的数量而言，单播和广播均可看作是组播的一个子集。单播可以看作仅包括一台机器群组的组播；广播可以看作包含了所有机器的组播。选播：是指一台主机与一组目的主机之间最“近”的一个之间的通信。

第六十页，共88页。1.3.8无线传感器网络路由协议的发展趋势

减少通信量以节约能量：由于WSN中数据通信最为耗能，因此应在协议中尽量减少数据通信量。例如，可在数据查询或者数据上报中采用某种过滤机制，抑制节点上传不必要的数据。或采用数据聚合机制，在数据传输到Sink点前就完成可能的数据计算。保持通信量负载平衡：通过更加灵活地使用路由策略让各个节点分担数据传输，平衡节点的剩余能量，提高整个网络的生存时间。例如，可在层次路由中采用动态簇头。在路由选择中采用随机路由而非稳定路由。在路径选择中考虑节点的剩余能量。第六十一页，共88页。1.3.8无线传感器网络路由协议的发展趋势

路由协议应具有容错性：由于WSN节点容易发生故障，因此应尽量利用节点易获得的网络信息计算路由，以确保在路由出现故障时能够尽快得到恢复，并可采用多路径传输来提高数据传输的可靠性。路由协议应具有安全机制：由于WSN的固有特性，其路由协议极易受到安全威胁，尤其是在军事应用中。目前的路由协议很少考虑安全问题，因此在一些应用中必须考虑设计具有安全机制的路由协议。WSN路由协议将继续向基于数据、基于位置的方向发展。这是由WSN一般不统一编址和以数据、位置为中心的特点决定的。第六十二页，共88页。1.4无线传感器网络中的拓扑控制技术

TopologyControl研究问题介绍在保证一定的网络连通质量和覆盖质量的前提下,一般以延长网络的生命期为主要目标，兼顾通信干扰、网络延迟、负载均衡、简单性、可靠性、可扩展性等其他性能，形成一个优化的网络拓扑结构。TopologyControl的重要性拓扑控制是一种重要的节能技术拓扑控制保证覆盖质量和连通质量拓扑控制能够降低通信干扰延长网络的生存时间提高MAC(mediaaccesscontrol)协议和路由协议的效率为数据融合提供拓扑基础提高网络的可靠性、可扩展性等其他性能拓扑控制对网络性能具有重大的影响第六十三页，共88页。网络中常见的拓扑结构:

1.4无线传感器网络中的拓扑控制技术

第六十四页，共88页。无线传感器网络中TopologyControl研究的主流方向:功率控制:就是为传感器节点选择合适的发射功率;睡眠调度:就是控制传感器节点在工作状态和睡眠状态之间的转换.

TopologyControl的主要形式:静态节点不可控部署静态节点随机地部署到给定的区域；稀疏网络的功率控制和对密集网络的睡眠调度是两种主要的拓扑控制技术；静态节点可控部署节点通过人或机器人部署到固定的位置.拓扑控制主要是通过控制节点的位置来实现的,功率控制和睡眠调度虽然可以使用,但已经是次要的了动态节点不可控部署称为移动自组织网络(mobileadhocnetwork,简称MANET)其挑战是无论独立自治的节点如何运动,都要保证网络的正常运转.功率控制是主要的拓扑控制技术动态节点可控部署移动节点能够相互定位.拓扑控制机制融入到移动和定位策略中.因为移动是主要的能量消耗,所以节点间的能量高效通信不再是首要问题.因为移动节点的部署不太可能是密集的,所以睡眠调度也不重要.1.4无线传感器网络中的拓扑控制技术

第六十五页，共88页。相关概念:覆盖:看成是对传感器网络服务质量的度量.区域覆盖:研究对目标区域的覆盖(监测)问题;点覆盖:研究对一些离散的目标点的覆盖问题;栅栏覆盖:研究运动物体穿越网络部署区域被发现的概率问题.k-覆盖/覆盖度为k:如果目标区域中的任何一点都被k个传感器节点监测.部分覆盖渐近覆盖:当网络中的节点数趋于无穷大时,完全覆盖目标区域的概率趋于1完全覆盖:Voronoi图是常用的覆盖分析工具.

1.4无线传感器网络中的拓扑控制技术

第六十六页，共88页。Voronoi图/泰森多边形/Dirichlet图:它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成，N个平面上有区别的点，按照最邻近原则划分平面；每个点与它的最近领区域相关联。

应用：(1)图形学、机械工程、虚拟现实、地理信息系统、机器人、图像处理、CAD等;(2)解决距离计算、碰撞检测、路径规划、Delaunay三角化、骨架计算、凸包计算以及可见性计算等计算几何其它问题的有效工具1.4无线传感器网络中的拓扑控制技术

第六十七页，共88页。相关概念:连通:k-连通/连通度为k:如果至少要去掉k个传感器节点才能使网络不连通讨论渐近意义下的连通,亦即当部署区域趋于无穷大时,网络连通的可能性趋于1网络生命期:定义为直到死亡节点的百分比低于某个阈值时的持续时间;可以通过对网络的服务质量的度量来定义网络的生命期.吞吐能力:目标区域是一个凸区域,每个节点的吞吐率为λbits/s.

A是目标区域的面积;W是节点的最高传输速率;π是圆周率;Δ是大于0的常数;L是源节点到目的节点的平均距离;n是节点数;r是理想球状无线电发射模型的发射半径通过功率控制减小发射半径和通过睡眠调度减小工作网络的规模,在节省能量的同时,可以在一定程度上提高网络的吞吐能力.1.4无线传感器网络中的拓扑控制技术

第六十八页，共88页。补充：1.4无线传感器网络中的拓扑控制技术

第六十九页，共88页。相关概念:干扰和竞争:

减小通信干扰、减少MAC层的竞争和延长网络的生命期基本上是一致的网络无线信道竞争区域的大小与节点的发射半径r成正比,所以减小r就可以减少竞争.网络延迟:

当网络负载较低时,高发射功率减少了源节点到目的节点的跳数,所以降低了端到端的延迟;当网络负载较高时,节点对信道的竞争是激烈的,低发射功率由于缓解了竞争而减小了网络延迟.拓扑性质:

除了连通性之外,对称性、平面性、稀疏性、节点度的有界性、有限伸展性(spannerproperty)等,都是希望具有的性质,还要考虑诸如负载均衡、简单性、可靠性、可扩展性等其他方面.拓扑控制的各种设计目标之间有着错综复杂的关系.

对这些关系的研究也是拓扑控制研究的重要内容.

1.4无线传感器网络中的拓扑控制技术

第七十页，共88页。功率控制通过降低节点的发射功率来延长网络的生存时间睡眠调度

对于节点密集型和事件驱动型的网络十分有效1.4无线传感器网络中的拓扑控制技术

第七十一页，共88页。功率控制/RangeAssignment(RA)问题.设N={u1,…,un}是d(d=1,2,3)维空间中代表网络节点位置的点的集合,r(ui)代表节点ui的发射半径.RA问题就是要在保证网络连通的前提下,使网络的发射功率(各节点的发射功率的总和)最小.Min试图寻找功率控制问题的最优解是不现实的,应该从实际出发,寻找功率控制问题的实用解/可行解;1.4无线传感器网络中的拓扑控制技术

第七十二页，共88页。功率控制算法分类：

(1)与路由协议结合的功率控制(2)基于节点度的功率控制(3)基于方向的功率控制(4)基于邻近图的功率控制(5)XTC算法

1.4无线传感器网络中的拓扑控制技术

第七十三页，共88页。功率控制算法分类：(1)与路由协议结合的功率控制

COMPOW:(CommonPower)基本思想是:所有传感器节点使用一致的发射功率,在保证网络连通的前提下,将功率最小化.基本步骤:

优缺点:在节点分布均匀的情况下,COMPOW具有较好的性能.但是,一个相对孤立的节点会导致所有的节点使用很大的发射功率,所以在节点分布不均的情况下,它的缺陷是明显的.1.4无线传感器网络中的拓扑控制技术

第七十四页，共88页。功率控制算法分类：

(2)基于节点度的功率控制LMA:LocalMeanAlgorithmLMN:LocalMeanofNeighborsAlgorithm

基本思想是:

给定节点度的上限和下限,每个节点动态地调整自己的发射功率,使得节点的度数落在上限和下限之间.缺点:算法一般难以保证网络的连通性.

1.4无线传感器网络中的拓扑控制技术

第七十五页，共88页。功率控制算法分类：(3)基于方向的功率控制CBTC:(Cone(圆锥)-baseddistributedtopology-control),能够保证网络连通性的基于方向的算法

基本思想是:节点u选择最小功率pu,ρ,使得在任何以u为中心的角度为ρ的锥形区域内至少有一个邻居.文章证明了当ρ≤5π/6时,可以保证网络的连通.特点:基于方向的算法需要可靠的方向信息,因而需要很好地解决到达角度问题,节点需要配备多个有向天线,因而对传感器节点提出了较高的要求.

1.4无线传感器网络中的拓扑控制技术

第七十六页，共88页。功率控制算法分类：(4)基于邻近图的功率控制DRNG:DirectedRelativeNeighborhoodGraph)基于有向RNG(邻近图)DLMST:DirectedLocalMinimumSpanningTree)基于有向局部MST(最小生成树)基本思想是:

设所有节点都使用最大发射功率发射时形成的拓扑图是G,按照一定的邻居判别条件求出该图的邻近图G′,每个节点以自己所邻接的最远节点来确定发射功率.特点:能够保证网络的连通性在平均功率和节点度等方面具有较好的性能.基于邻近图的功率控制一般需要精确的位置信息1.4无线传感器网络中的拓扑控制技术

第七十七页，共88页。功率控制算法分类：(5)XTC算法

微软亚洲研究院的Wattenhofer等人提出的XTC[18]算法:对传感器节点没有太高的要求对部署环境也没有过强的假设,提供了一个面向简单、实用的研究方向.XTC代表了功率控制的发展趋势XTC的基本思想:是用接收信号的强度作为RNG(relativeneighborhoodgraph)中的距离度量.XTC算法可分为如下3步:1.4无线传感器网络中的拓扑控制技术

第七十八页，共88页。偏序：若集合X上的关系R是自反的、反对称的和传递的，则称只是集合X上的偏序关系。(如：实数集上的<=关系,>=关系)全序：设R是集合X上的偏序(Partial

Order)，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。

直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。功率控制算法分类：(5)XTC算法补充概念：(集合论)三歧性定理：在实数域，这种关系表现为“三歧性”，即对任意两个实数，必然存在：要么a>b；要么a<b；要么a=b。1.4无线传感器网络中的拓扑控制技术

第七十九页，共88页。功率控制算法分类：(5)XTC算法

XTC的优缺点:不需要位置信息对传感器节点没有太高的要求适用于异构网络也适用于三维空间与大多数其他算法相比,XTC更简单,更实用XTC与实用化要求仍然有一定的距离(如:XTC并没有考虑到通信链路质量的变化)1.4无线传感器网络中的拓扑控制技术

第八十页，共88页。睡眠调度算法分类：(1)非层次型网络的睡眠调度算法当然也可以用在层次型网络中,因为它们可以在簇的内部使用.(2)层次型网络的睡眠调度算法非层次型/平面的:如果网络中的节点都具有相同的功能,扮演相同的角色层次型的/基于簇的:反之1.4无线传感器网络中的拓扑控制技术

第八十一页，共88页。睡眠调度算法分类：(1)非层次型网络的睡眠调度算法基本思想是:每个节点根据自己所能获得的信息,独立地控制自己在工作状态和睡眠状态之间的转换.它与层次型睡眠调度的主要区别在于:每个节点都不隶属于某个簇,因而不受簇头节点的控制和影响.RIS:RandomizedIndependentSleepingRIS将时间划分为周期,在每个周期的开始,每个节点以某一概率独立地决定自己是否进入睡眠状态.RIS需要较为严格的时间同步1.4无线传感器网络中的拓扑控制技术

第八十二页，共88页。睡眠调度算法分类：(2)层次型网络的睡眠调度算法基本思想是:由簇头节点组成骨干网络(Backbone),则其他节点就可以(当然未必)进入睡眠状态.层次型网络睡眠调度的关键技术是分簇.

LEACH:需要较为严格的时间同步,也不能保证簇头均匀分布EECS:EnergyEfficientClusteringScheme能够保证簇头的均匀分布,但EECS与LEACH一样,簇头与汇聚节点的单跳通信方式限制了网络的规模LDS:LinearDistance-basedScheduling适用于基于簇的高密度传感器网络,只考虑簇内的睡眠调度,它假设分簇结构已经存在.但是,LDS不能保证能量的均匀消耗1.4无线传感器网络中的拓扑控制技术

第八十三页，共88页。睡眠调度算法分类：(2)层次型网络的睡眠调度算法GAF:GeographicalAdaptiveFidelity以节点地理位置为分簇依据,把监测区域划分成正方形虚拟单元格,将节点按照位置信息划入相应的单元格,相邻单元格的任意两个节点可直接通信.GAF节点有3种状态:工作状态、睡眠状态、发现状态.每个单元格只有一个随机产生的簇头节点处于工作状