无线传感器网络WirelessSensorNetworks（WSNs）.ppt

无线传感器网络,Wireless Sensor Networks（WSNs）,1. 无线传感器网络概述,无线传感器网络通常由大量具有感知、计算及无线通信能力的微小节点组成，其目的是监视环境而非通信。 传感器节点部署在要监视的区域中，采集指定的环境参数，并将数据发送到汇聚节点供分析。,传感器节点的组成,传感器节点一般由传感模块、处理模块、无线通信模块和能量供应模块组成。 传感器节点已经可以做得非常小，称为智能尘埃（smart dust）。,传感器节点的特点,廉价：每个节点的期望价格在一美元左右 体积小：火柴盒或硬币般大小 重量轻：小于100克 能量有限：两节五号电池或纽扣电池供电 无线通信能力：能够用无线电、红外线、蓝牙、超声波等通信，带宽低，干扰大 计算能力：几百兆赫兹的处理器 存储能力：几兆或几百兆的存储空间 感知能力：具有一个或几个传感器 软件环境：TinyOS是专为传感器节点开发的操作系统,传感器网络的特点,节点固定或只有较小的活动性 数量大，密度高 拓扑动态变化 节点同构，或只有少量特殊节点； 分布式：没有预先指定的中心，所有节点通过分布式算法相互协调； 自组织：传感器网络的部署和初始化等不需要外界干预； 节点资源受限，特别是能量非常有限； 以数据为中心的网络，节点具有数据处理的能力； 与应用紧密耦合的网络,传感器网络与移动自组网的不同,节点规模： 移动自组网：节点数量通常在几十或上百 传感器网络：节点数目往往高出好几个数量级 节点密度： 移动自组网：小 传感器网络：大（冗余部署的结果） 拓扑变化的原因： 移动自组网：节点运动 传感器网络：节点休眠调度、环境干扰或节点故障引起 节点处理能力： 移动自组网：较强 传感器网络：十分有限,传感器网络的应用,传感器网络在环境监视方面的优势： 通过在物理环境中部署大量廉价的智能传感器节点，可以获得长时间、近距离、高分辨率的环境数据，这是传统监视设备无法得到的。 传感器节点的计算和存储能力允许节点执行数据过滤、数据压缩等操作，也可以执行一些应用特定的处理任务。 节点之间的通信能力允许节点之间协同完成更复杂的任务，如目标跟踪。 通过任务的重新分配可以改变传感器网络的用途。,（1）监视红杉树的小气候1,在一棵红杉树的不同位置安装无线气象站进行数据采集，如光辐射、温度、湿度、气压，形成森林气候一个样本。 可在森林的不同地方（如森林的中心处、迎风面、背风面、向阳面等）部署这样的传感器网络，然后利用长距离上行链路将数据发送到汇聚节点。,无线气象站（传感器节点）,实验结果片段,（2）监视地下结构的改变2,将传感器节点固定放置在坑顶和坑壁上形成规则的网状网络（蜂窝状六边形），每个节点预先设置好位置，每个节点都知道自己的邻居集合，并定期与邻居交换信标。 当发生坍塌时，坍塌区域内的节点发生移位，在网络中形成空洞。当一个节点发现它的一些邻居突然消失时（收听不到信标），判断自己成为空洞的一个边界节点，向汇聚节点报告自己的位置。 汇聚节点计算空洞区域。,（3）人居环境监视3,在一个标准的电源插线板上扩充了各种传感器和无线收发器，一个微处理器控制所有的部件，成为一个plug节点。 利用plug节点的多模式感知能力，可以较准确地推断发生的事件。 所有plug节点构成普适计算环境中的骨干网，可以了解到plug网络所在环境的活动情况,无线传感器网络要解决的问题,网络的自组织、自配置（节点定位、时间同步、自动校准、拓扑控制等） 通信协议（MAC、路由协议） 分布式数据管理（数据采集、存储、查询、获取等） 各种应用特定的数据融合处理 节省能耗应贯穿到所有的设计中。,2. 节点定位,节点定位是传感器网络的重要基础功能，没有位置信息的环境数据是没有意义的。 手工为每个节点设定位置不可能， GPS定位系统无法大规模应用到传感器节点上。 传感器节点依靠相互之间的协作来确定各自物理位置的过程，称为节点定位。,节点定位算法的分类,绝对定位和相对定位： 绝对定位：网络中存在已知位置的参考节点（锚节点），所有节点根据参考节点确定自己的位置，所有节点使用同一个坐标系。 相对定位：网络中不存在已知位置的参考节点，所有节点确定到其它节点的相对位置。 基于测距的定位和非基于测距的定位： 基于测距的定位：借助于节点之间的距离信息或角度信息进行位置估计； 非基于测距的定位：不需要或不直接测量节点之间的距离及角度信息。,衡量定位算法的性能指标,平均定位误差：待定位节点的估测位置到实际位置的平均距离。 可定位节点的比率 算法复杂度（计算、通信） 收敛速度 健壮性,2.1 测距技术,大多数已有的位置发现方法由两个基本的阶段组成： 距离（或角度）估计 距离（或角度）融合 估计两个节点间距离最常用的方法是： 接收信号强度指示RSSI：根据接收到的信号强度计算路径损耗，再将路径损耗转换成距离。 基于时间的方法（ToA、TDoA）：根据信号到达时间或两种信号的到达时间差估算距离。 到达角度AoA：估计信号的到达角度，用几何关系计算节点位置。,RSSI（Received Signal Strength Indicator）,已知发射节点的发射功率，接收节点根据接收到的信号强度估算到发射节点的距离。 使用最广泛的信号传播模型是对数距离路径损耗模型，其中功率均用分贝表示： 大量研究表明，在无线传感器网络中无法得到信号衰减与距离之间的一致模型，主要原因在于： 环境的影响：多路径、衰落、遮蔽效应 天线高度 节点的发射功率未精确校准,TDoA（Time Difference of Arrival）,发送节点同时发出射频及超声波两种信号，接收节点根据收到两种信号的时间差来估算距离。 特点： 精度高 传输特性也受环境影响，但较易检测 超声传输距离短,RSSI与TDoA的比较4,AoA（Angle of Arrival）5,通过阵列天线或多个接收器得到信号到达的方向。 图示的例子中同时使用到达信号的时间差（TDoA）和相位差： 使用两个超声信号接收器，相距L放置； 利用TDoA得到两个超声信号接收器到发送节点的距离x1和x2； 利用x1、x2和L计算到发送节点的角度。,2.2 距离（角度）融合,距离（角度）融合常用的方法是： 三边测量法（tri-lateration）：通过计算3个圆的交点来定位节点。 三角测量法（triangulation）：使用三角函数来计算节点位置。 最大似然估计法（Maximum Likelihood estimation）：通过最小化测量距离和估计距离之间的差异来估计节点位置,距离（角度）融合的图示,三角测量转化为多边测量,知道参考节点A、B的位置及未知节点D到AB的角度，则D位于以O为圆心的圆周上，其中AOB = 2ADB。 对于每一对参考节点A、B，计算出O的位置和半径，列出圆方程，从而将三角测量问题转化为多边测量问题。,最大似然估计,位于（x0, y0）的待定位节点测得到N个参考节点的距离为d1dN，若位置及距离是精确的，则有： 在有噪声的环境下（位置或测距有误差），以上方程可能没有解（N个圆不交于一点），可采用最小均方估计来获得最佳的位置估计值：,线性化求解,将等式（2-1）的两边分别相加： 将等式（2-1）减去等式（2-3），得到N个线性方程： 以上方程组可以写为y=bX，其中b为 (x0,y0)T ，X为系数矩阵，y为常数矢量，则b=(XTX)-1XTy。,2.3 Ad-Hoc Localization System（AHLoS）4,AHLoS是一个基于TDoA和多边测量的定位算法，也称迭代多边测量法： 参考节点向邻居节点广播自己的位置； 未知节点测量到邻居参考节点的距离，若满足多边测量的条件（至少在3个参考节点的通信距离内），利用多边测量法估计自己的位置； 一旦未知节点确定了自己的位置后，就成为新的参考节点，向其邻居节点广播自己的位置； 这个过程不断重复，直至所有满足多边测量条件的未知节点都获得自己的位置。,原子多边测量,未知节点（x0,y0）到第i个参考节点的距离方程表示为： (xi-x0)2 + (yi-y0)2 = (stio)2 或 若有k个这样的方程，从其它方程中减去第k个方程，可得到以下线性方程：,该方程组可表示成y=bX的形式，并有b=(XTX)-1XTy，其中：,协同多边测量,原子多边测量需要满足的条件是： 未知节点至少有3个参考节点邻居。 协同多边测量： 未知节点利用距其多跳的参考节点位置估计自己的位置，同时可以估算出其它一些未知节点的位置。,协同多边测量的问题描述,将传感器网络抽象为一个连通的无向图G=（N, E），信标节点集合用B表示，未知节点集合用U表示，我们的目标是求解：,参与节点与参与节点对,定义1： 一个节点是参与节点，如果它是一个参考节点，或者是一个至少有3个参与邻居的未知节点。 定义2： 一个参与节点对是一对连通的参考节点-未知节点或未知节点-未知节点，其中所有未知节点均为参与节点。,2.4 不基于测距的（rang-free）定位算法,不基于测距的算法不需要知道待定位节点到参考节点的距离，或者不需要直接测量此距离，成本和功耗较低。 几种典型的不基于测距的定位算法： 质心法（Centroid） 几何约束法（Geomentic Consrain） DV-HOP,（1）质心法6,质心法基于以下两个假设： 射频信号的传播遵循理想的圆球模型 所有节点的通信距离相等 网络中放置了固定数量、通信区域相重叠的一组参考节点，这些参考节点构成规则的网状结构。,质心法（续）,参考节点周期性地发送包含自射位置信息的信标消息； 未知节点在一个给定的时间间隔t内接收信标消息，对于每个参考节点Ri，统计在该时间内收到的信标消息数Nrecv(i,t)，计算对应的连接测度CMi ： CMi = Nrecv(i,t) / Nsent(i,t) 100% 未知节点选择连接测度大于指定阈值的参考节点（设为k个），计算这些参考节点的质心作为自己的位置估计值：,（2）几何约束法7,每个节点的信号覆盖范围可以用一个几何形状来表示,几何约束法（续）,对于每个听到的参考节点，待定位节点计算这些参考节点信号覆盖范围的重叠区域。,几何约束法（续）,计算包含重叠区域的最小矩形，矩形的中心作为节点的位置估计值。,（3）基于DV的定位算法8,如何在参考节点稀疏的网络中进行节点定位？ 基本思想： 参考节点附近的节点通过直接测量 的方法获得到参考节点的距离，传播给其邻居节点； 邻居节点据此估计自己到参考节点的距离，再传播给其邻居；依次类推。 类似于距离矢量路由算法中的距离传播，因此称这一类方法为基于DV的方法。,DV-HOP传播模式,参考节点向其邻居广播信标消息，所有节点维护到每个参考节点的最小跳数，并与邻居节点交换各自的距离矢量表。 参考节点利用其它参考节点的位置及自己到这些参考节点的最小跳数计算每跳平均距离，发布到网络中。 未知节点根据其最近的参考节点发布的平均每跳距离，计算到各个参考节点的距离，使用多边测量法估计自己的位置。,DV-Distance传播模式,类似于DV-HOP，但该算法传播的是累计距离，而非累计跳数。 该方法比DV-HOP精确一些，但对测距误差很敏感。,Euclidean传播模式,该方法传播到参考节点的物理距离。 未知节点A至少要有两个邻居B和C，且B和C都有到参考节点L的物理距离估计，另外A测量到B和C的距离，且必须知道距离BC。这样A可以计算距离AL。,2.5 安全定位,大多数通用的定位算法未考虑安全问题，在出现距离或位置欺骗的情况下，无法正确定位。 已有的一些安全定位算法通用性较差，只能对付一种或几种特定的攻击。 问题： 能否找到一种统一的方法来抵御所有的节点定位攻击？,从统计的角度看节点定位问题11,各种攻击手段最终都是要欺骗未知节点得到错误的参考位置、距离、角度等信息。 节点出现异常、局部环境干扰等因素也会导致未知节点获得错误信息。 正常节点产生的测量样本也是有误差的。 如果将错误及误差都看成噪声，未知节点的任务就是要根据给定的一组有噪声样本进行尽可能准确的位置估计。 这样，我们就将应对定位攻击、节点异常和环境干扰的问题统一转化为在测量样本集中去除大噪声样本的问题。,问题描述,由未知节点和若干参考节点组成的传感器网络中，每个节点可以通过某种测距技术获得到参考节点的距离。（AoA可以转化为多边测量问题） 为简单起见，假设参考节点的位置可能受到攻击，距离信息未受到攻击（只有测量误差）。 在（x0,y0）的未知节点收到N个参考节点的位置及相应的距离(x1,y1,d1),(xN, yN, dN)，未知节点估计自己的位置。,双边测量法Bilateration,每次只计算两个方程，一般可得到两个实数解。,Bilateration的基本思想,每次只计算两个方程，得到的实数解为未知节点可能的位置，称候选位置。 如果不存在攻击和噪声，侯选位置中应当会有一些重叠的点，这个点便是未知节点的位置。 当存在攻击或噪声时，可能没有重合点，但是在误差范围有限的情况下，由正常样本产生的合理位置应当分布在真实位置的附近，因而这些位置相互靠近。 Bilateration的基本思想是找出合理位置，并只利用合理位置来进行位置估计，方法是找出最大的侯选位置簇。,Bilateration的算法过程,未知节点对于获得的每对测量样本计算候选位置，得到包含M个候选位置的集合C。 对于C中的每一个候选位置ci计算到其它候选位置的距离，找到距离小于门限的候选位置，统计其个数ni，并记录相应的候选位置集合Ei。 找到ni中的最大值nm，Em即为最大的候选位置簇，计算这些位置的质心即为未知节点的位置。,Bilateration的算法过程（续）,更精确一些，可以根据Em找到生成这些候选位置的参考节点，赋权值1，弃用的参考节点赋权值-1，与邻居交换权值表。 从收集到的所有权值表中选出共同的参考节点，将它们的权值相加，权值小于平均值的参考节点弃用，将其生成的侯选位置从Em中删除。 将Em中剩余的候选位置求平均，作为未知节点的位置估计。,及测距误差对算法性能的影响,3. 传感器网络中的射频传播模型,由于部署大规模传感器网络的成本及困难，目前大多数研究工作都是在仿真环境中进行。 为了分析上的方便，研究人员常使用一些理想的模型，但理想模型与实际情况是否相符一直受到质疑。 传感器网络中受质疑最多的一个模型是射频信号传播模型，认为信号传播是各向同性的。 该模型直接导致了圆形连通模型（circular connectivity model），即所有与节点O连通的节点均位于以O为圆心、通信距离为半径的圆中。,3.1 大规模传感器网络的复杂行为研究9,9的研究表明，哪怕是最简单的洪泛算法也会导致圆形连通模型失效。 9的贡献主要在于两个方面： 建立了一个实际的较大规模密集传感器网络，从实际网络中获取了大量的第一手数据，这些数据表明应重新审视目前使用的连通模型。 第一次系统分析了影响算法全局行为的因素。,研究例子-洪泛算法,洪泛是计算机网络中实现最简单、使用最广泛和研究最充分的协议之一，主要用于数据的分发。 洪泛是许多复杂协议的基础，在大规模传感器网络中更是频繁使用，如发现路由、传播查询请求、发布网络命令、改变网络参数、进行多跳时间同步等。 以下是基于洪泛的树构造算法：,洪泛快照,洪泛的非均匀性测度,实验平台,每做一次实验都使用新的电池； 所有节点的天线长度相同，且具有一致的垂直方向； 节点上运行TinyOS，提供包括物理层纠错、检错、MAC层、网络消息传输等在内的完整协议栈； MAC协议是CSMA的一个变种。,Reno Mote,实验一：理解链路特性,将169个节点放置于一个平坦、开阔的停车场上，形成13*13的网格网络，每个网格的边长为2英尺。 实验目的：绘制出在16个射频功率设置下节点之间的连通特性。 基站控制节点的发送：基站每次向一个节点发送命令，节点响应基站的命令发送。 在每个功率设置下，每个节点每次发送20个包，按照100ms的间隔依次发送。 接收节点记录发送节点ID、包序号和发送功率（包含在包的载荷中），保存在自己的存储器中。 利用这些数据，绘制出每一个发送功率下数据包接收的统计图。,实验二：研究洪泛的行为,将156个节点放置于平坦、开阔的停车场上，形成13*12的网格网络，每个网格的边长为2英尺。基站放置于网格底边的中点。 基站周期性地启动洪泛传输过程，周期足够长以确保前一次洪泛已结束，每个节点只在第一次收到一个新消息时转发一次。 实验中共设置了8个射频功率，每个射频功率设置下启动10次不重叠的洪泛传输。 应用层和MAC层均记录必要的信息，用于实验结束后重建消息的传播过程。,实验分析方法,将洪泛行为分解到不同的层次上，在每一层上使用不同的测度独立地研究这些行为，然后再综合这些分析来解释全局行为。 在链路层上，量化地定义和测量真实环境中对应于给定发射功率的有效通信半径，研究数据包接收率随传输距离的统计变化特性，确定哪些因素造成了非对称性。 在MAC层上，使用时间信息来给出描述洪泛传播的端到端特性和本地特性（如竞争和冲突）的测度。 在应用层上，分析洪泛生成的结构。 综合分析：重建消息传播过程，解释层次之间的相互作用如何导致最终的全局行为。,（1）链路层分析,包接收率的等值线分布,另一个发送功率下包接收率的等值线分布,不同发送功率下包接收概率随距离的分布,连通半径（connectivity radius）,算法设计者通常用连通半径及圆形连通区域来抽象系统，许多分析结果都是基于圆形区域，因为它简化了分析，并允许使用几何方法。 9基于包接收门限来定义连通半径，这个门限的选择是基于对链路好坏的判断： 称一条链路为“好”链路，如果可以使用前向纠错及其它技术来使包吞吐率达到一个恰当的水平。 称一条链路为“坏”链路，如果无法通过这些方法来提高包吞吐率。 基于这个标准和上图的曲线，9将“好”链路的门限取为65%，“坏”链路的门限取为25%。,不同射频发送功率下的连通半径,非对称链路,9用“好”链路及“坏”链路的概念来定义非对称性测度： 非对称链路：一个方向上是“好”链路，另一个方向上是“坏”链路。 双向链路：两个方向上均是“好”链路。,（2）MAC层分析,9使用三个测度来反映洪泛传输过程中三个不同方面的问题： 最大回退时间：反映每个节点通信区域内的干扰（回退是竞争的结果）。 接收延迟：网络中所有节点接收到洪泛消息的时间。 结束时间：网络中所有节点完成洪泛发送的时间。 这三个测度一般有以下关系：,三个测度的实验数据,最大回退时间随发射功率的增大而增大。 接收延迟与结束时间的差异也随发射功率的增大而增大。,冲突节点、离群节点和后向链路,洪泛初始阶段冲突频繁，产生许多离群节点，离群节点随后接收消息形成后向链路。 在较高的发射功率下，节点具有较大的通信区域，冲突概率增大，产生较多的离群节点，最终形成较多的后向链路。,（3）应用层分析,节点层次：基站到树上某个节点的跳数。,应用层分析（续）,簇大小：连接某个父节点的孩子节点个数。,（4）总结,论文提出了四种值得注意的影响：长链路、后向链路、离群节点和聚集。 离群节点可以用MAC层上的冲突解释。 长链路可以用传输的方向性解释。 长链路导致某个方向的洪泛传播较快，反弹回来填充传播较慢的区域或存在离群节点的区域，形成后向链路。 应用层上机会地、最早到来优先的父节点选择算法导致高度聚集现象。,总结（续）,实验揭示了链路层上几个值得注意的影响：高度不规则的包接收等值线，传输的方向性导致长链路，长链路呈现较高的不对称性等。 有些影响可以用现有的模型来描述，但有些影响无法用现有的模型描述，其对协议行为的影响也没有被仿真。 圆形模型或概率模型对于充分理解复杂系统的相互作用是不充分的。 非对称链路在大规模传感器网络中非常重要，一个健壮的协议必须能够恰当地处理这种情况。,3.2 Radio Irregularity Model 10,节点的接收信号强度表示为： 第一部分表示不同节点的硬件校准和电源状况 第二部分表示路径损耗的各向异性 第三部分表示环境噪声,4. 传感器网络中的数据管理,在传感器网络中，用户感兴趣的是数据而不是网络本身，因此数据管理（数据的存储与访问）是传感器网络的重要问题。 在IP风格的通信模式中，通过节点地址来访问数据；但在传感器网络中，通过节点标识来访问数据一般不可行： 用户只对数据感兴趣，并不关心到底是哪个节点采集了这个数据； 在随机部署的传感器网络中，节点标识与物理位置的对应关系在部署前并不知道，在部署后获取全部节点的位置开销很大，因此节点标识对于数据访问的用处不大。,传感器网络中的数据访问模式,用户通过简单的查询语句请求所需要的信息，比如“在地理区域X中观察到的行人数量”。 汇聚节点通过分析查询语句形成传感器网络中的查询任务，发布到网络中。 符合条件的传感器节点（如区域X中的节点）采集数据，执行行人检测与计数任务，生成事件报告。 事件报告发送给汇聚节点。,需要解决的问题,任务描述：如何描述用户感兴趣的数据 任务扩散：任务如何发送到执行该任务的节点 任务执行：与具体应用有关 数据获取：数据如何发送到发布任务的节点,4.1 定向扩散（directed diffusion）12,应用场景： 用户通过长距离链路与网络中的汇聚节点连接，发布如下任务：“在接下来的T秒时间内，每隔I毫秒向我发送出现在子区域R内的任何四足动物的位置估计”。 使用某种路由机制，该任务被传输到位于子区域R的传感器节点。 该区域的每个节点采集数据，执行目标检测与识别任务。若检测到目标，每隔I毫秒生成一个事件描述。 事件消息发送到汇聚节点。,（1）任务描述（兴趣）,任务描述（task descriptions）用一系列描述任务的对来命名。比如，动物跟踪任务可以描述为： 直观上，任务描述指出了对匹配这些属性的数据的兴趣，因此，将这样的一个任务描述称为一个兴趣（interest）。,数据命名,为响应兴趣而发送的数据也用类似的命名方法命名。比如，检测到动物的节点可以生成以下的数据： 给定传感器网络支持的一组任务，选择一种命名方案是设计定向扩散的第一步。,（2）梯度,兴趣通常通过某个节点（sink）注入网络，在duration指定的时间之后，节点清除任务的状态。 对于每个活跃的任务，汇聚节点周期性地向其邻居广播一个兴趣。 初始发送的兴趣中，interval属性取值较大，主要用于探测的目的，如：,兴趣缓存（interest cache）,每个节点维护一个兴趣缓存，每一项对应一个不同的兴趣。 每个兴趣项包含若干个域，如： Timestamp：最近一次收到兴趣的时间 Gradient：可能有多个，每个梯度域对应从一个邻居收到的兴趣： Data rate：取自兴趣的inverval属性 Duration：取自兴趣的timestamp和expiresAt属性 当节点收到一个兴趣时，检查缓存中是否有匹配的项： 没有匹配的项，创建一个兴趣项，梯度域指向发送兴趣的邻居节点。 存在匹配的兴趣项，但没有指向发送节点的梯度，添加一个梯度域，并更新timestamp和duration域。 存在匹配的兴趣项及梯度域，则只是更新timestamp和duration域。 当一个梯度过期时，将其从兴趣项中删除；当一个兴趣项的所有梯度都过期时，将兴趣项从缓存中删除。,兴趣扩散,收到一个兴趣后，节点可以决定再将其发送给自己的一些邻居进行扩散。对其邻居而言，这个兴趣是从该节点发出的（即不知道该兴趣的真正sink）。 节点如果最近已经重发过相匹配的兴趣，也可以不发送收到的兴趣。 一般有好几种选择邻居的方法： 转发给所有邻居，相当于扩散 使用地理路由，只将兴趣向目标区域扩散 使用早先响应其它兴趣时缓存的数据 通过兴趣扩散在节点中建立了梯度，这些梯度形成了从源节点到sink的传输路径。,兴趣传播与梯度建立,（3）数据生成和传播,rect区域内的传感器节点使用相同的方法处理兴趣，除此之外，指令本地传感器开始采集数据和识别目标。 检测到目标的传感器节点从其兴趣缓存中寻找匹配的兴趣项。 发现匹配的兴趣项后，按照所有梯度中的最高数据速率生成事件样本，单播发送给每个梯度指示的邻居。,数据传播,接收到数据消息的节点从其兴趣缓存中寻找匹配的兴趣项： 没有找到相匹配的兴趣项，丢弃数据消息； 找到匹配的兴趣项，检查与其关联的数据缓存： 缓存中有一个匹配的缓存项，丢弃数据消息； 否则，将数据消息添加到数据缓存中，并发送给邻居节点；根据数据缓存可确定接收事件的数据速率。 为转发数据消息，节点检查兴趣项的梯度列表： 如果所有梯度的数据速率大于等于收到的事件速率，直接将收到的数据消息发送给相应的邻居； 如果某些梯度的数据速率小于收到的事件速率，降频发送。,（4）路径巩固（reinforcement）,Sink收到低速率事件后，通过巩固某个邻居来接收高速率事件。 Sink利用数据驱动的本地规则选择一个邻居，向其发送具有较小interval值的兴趣。 如果新的数据速率高于邻居节点相应兴趣项中任何一个梯度的数据速率，邻居节点必须至少巩固它的一个邻居。 通过一系列的本地交互，建立起一条从源节点到sink节点的高事件速率传输路径。 利用数据缓存和数据驱动的本地规则选择巩固的邻居节点，如： 第一个发来最新匹配事件的邻居 发来最新匹配事件的所有邻居 发来最多事件的邻居 一向较早发送事件的邻居,路径巩固,取消巩固（negatively reinforcement）,以上算法可能导致多条路径被巩固，如果某条路径一直较差，需要一个机制来取消对路径的巩固。 取消巩固的方法： 超时：所有高事件速率的梯度必须被显式地巩固，否则在规定的时间后被取消巩固。 显式降级：通过发送低数据速率的兴趣来显式取消对某个邻居节点的巩固。 如果某个兴趣项的所有梯度均为低数据速率，节点取消巩固那些向其发送高速率事件的邻居。 选择哪个邻居节点取消巩固？ 没有新事件到来的邻居 较少发送新事件的邻居 ,（5）定向扩散的特色,以数据为中心，所有通信使用兴趣来描述数据。 在扩散过程中为事件报告建立多条传输路径，然后基于观察到的路径性能，使用路径巩固来减少路径，只保留少数较好的路径。 使用数据缓存来避免回路发生，定向扩散及路径巩固不保证无环路由。,4.2 传感器网络中的数据存储策略13,传感器网络中的数据存储研究节点采集的数据在网络中的存储策略： 如何将数据存放到网络中合适的位置 查询请求如何路由到存储位置 信息中介（information brokerage）： 生产者（传感器节点）将产生的数据按照某种策略存放在特定的位置上； 消费者（汇聚节点或传感器节点）将数据访问请求按照相同的策略路由到数据的存储位置，获得满足查询条件的结果 。,数据存储策略（1）,集中式存储： 每个节点将收集到的数据传输到基站保存，数据访问直接从基站获取数据，此时传感器网络只是作为一种收集数据的手段。 优点： 基站的能量和存储空间一般不受限制，数据可长时间保存，数据访问也不会消耗网络中节点的能量。 缺点： 所有节点都要将数据传给基站，靠近基站的节点因转发较多数据而耗能太快（漏斗效应）。,数据存储策略（2）,本地存储： 节点将采集的数据存放在自身的存储器中；查询请求通常被洪泛到整个网络中，节点依据查询条件反馈结果。 优点： 存储简单，存储过程中没有通信开销。 缺点： 节点存储能力有限，不能长时间保存历史数据； 查询请求在网络中洪泛传播，消耗较多的网络能量； 数据传输代价高，查询处理较复杂。,数据存储策略（3）,分布式存储： 节点产生的数据不一定存储在本地，而是利用分布式技术将数据存储在其它节点； 采用有效的信息中介机制协调数据存储和数据访问之间的关系，保证数据访问请求能够被满足。 优点： 分布式存储较好地吻合传感器网络本身的分布性。 缺点： 信息中介需要额外的代价。,几种存储策略代价的比较,集中式存储： 存储代价高，访问代价为0； 本地存储： 存储代价为0，访问代价高； 分布式存储： 数据存储到s个位置，是以上两种策略的折衷,4.3 分布式数据存储与访问,目前，分布式存储采用的信息中介机制主要有： 哈希映射 建立索引 数据和查询请求按一定规则路由,（1）GHT（Geographic Hash Table）14,以数据为中心的存储（data-centric storage，DCS）： 数据用关键字命名（任何命名方案都可以）。 数据的存放节点由数据的名字决定，从而具有相同名字（同一类）的数据存放在同一个节点上。 对特定数据的查询被直接发送到存放数据的节点上，避免在网络中洪泛查询。 DCS支持两个操作： Put(k, v)：根据关键字k（数据名字）存储数据v； Get(k, v)：获取以关键字k存储的数据v。,GHT的基本要点,GHT的应用前提是传感器网络的地理边界已知，且网络中的节点知道自己的位置。 GHT的核心步骤是将关键字k散列到一个地理位置，put()和get()对关键字k的散列得到相同的位置。 一个对被存储在离k的散列位置最近的节点上，对同一个k一致地选择该节点是建立GHT的关键，即使在发生节点故障、拓扑改变的情况下也要保证一致性。 GHT建立在地理位置路由算法GPSR的基础上。,家乡节点和家乡周界,对关键字k散列得到的地理位置上，可能并没有实际节点存在。 定义GHT分组的家乡节点为在地理位置上最接近分组目的位置的节点，携带或查询的GHT分组最终到达其家乡节点。 GHT使用GPSR周界模式来找到家乡节点： 当分组到达家乡节点时进入周界转发模式； 分组围绕目的位置转一圈，最后又回到家乡节点，称这个周界为家乡周界。 当节点发现GHT分组又返回时，知道自己就是它的家乡节点。,周界刷新协议PRP（perimeter refresh protocol）,GHT使用周界刷新协议复制对，并将它们放置在一致的节点上。 PRP将对保存在家乡周界的每一个节点上，家乡周界上除家乡节点之外的节点称为复制节点。 每隔Th秒，家乡节点对其保存的关键字k生成刷新分组，发送到k的哈希位置上，刷新分组中包含以关键字k存储的值。 刷新分组就像put()和get()分组一样被路由，因此将围绕目的位置当前的家乡周界转一圈。,拓扑改变后更新家乡节点,当刷新分组到达一个节点时有两种可能： 接收节点比启动节点更靠近目的位置：接收节点使用该刷新分组，并启动自己的刷新过程。 接收节点不比启动节点更靠近目的位置：继续使用周界模式转发刷新分组。 以上两种情况下，接收节点都会将本节点存储的、刷新分组中没有的对添加到刷新分组中。 当刷新分组返回启动节点、且该节点并不是原来的家乡节点时，该节点使用刷新分组，并成为k的家乡节点。,家乡节点失效,每当复制节点收到一个不是自己启动的刷新分组时，它缓存刷新分组中的数据，并设置一个接管定时器。 当接管定时器超时时，复制节点启动一次刷新，将刷新分组发往k的哈希位置。 该机制解决家乡节点失效的问题，复制节点可能不会成为家乡节点，但GHT的路由过程会使得刷新分组到达新的家乡节点。,刷新分组丢失,不管是家乡节点还是复制节点，对保存的每个k都有一个死亡定时器。当死亡定时器超时时，其缓存的k过期。 每当收到k的一个刷新分组时（不管是自己发送的还是其它节点发送的），死亡定时器复位。 当家乡节点丢失自己的若干个刷新分组后，其缓存的k过期；而复制节点等待多次刷新周期未收到家乡节点的刷新分组时，启动刷新分组。,（2）DIMENSIONS 15,15考虑一类长期观测的科学应用，传感器网络需长时间工作获取之前未观察过的现象，如微气候、栖息地、动物迁徙等。 这一类应用通常产生大量的数据，数据分析涉及非常复杂的信号处理。 大量的数据及有限的节点存储要求传感器网络进行存储优化。,DIMENSIONS的基本思想,对传感器数据生成不同分辨率的概要，存放在网络中一个为高效查询而优化的分布式存储结构上： 对应不同的空间和时间尺度，生成不同分辨率的数据概要（采用小波变换） 。 数据查询采用下钻的方式，即先访问较大时空尺度上粗粒度、高度压缩的数据概要，所获得的结果再用于访问更细粒度、更详细的数据。 数据老化，越老的数据只保留越粗略的信息。,DIMENSIONS的组成,DIMENSIONS由三个部分组成： 分层小波处理，构造有失真的多分辨率数据摘要 利用下钻查询的数据摘要使用方法 数据老化方案。 数据摘要和数据老化是周期性处理的，处理周期与具体应用有关。 15假设系统应用于寻找数据模式的各种查询，因此采用了一种广泛可获得的数据摘要技术小波变换。,多分辨率数据摘要,使用小波变化的分层处理包括两个阶段： 时间摘要：每个节点对本地产生的时间序列进行小波变化，消除时间上的冗余。 空间摘要：构造一个基于分层网格的覆盖网，使用时空小波压缩在每一层上进行数据摘要。,下钻查询,在分布式小波摘要上进行下钻查询可以极大地减小搜索的代价。 查询从最高层次上注入网络，先对最大时空尺度上的数据摘要进行处理，处理结果指示网络中哪个区域最有可能提供更精确的信息。 查询被转发到保存有哪个区域摘要信息的节点，对更细粒度的子区域数据摘要进行处理。 这个过程不断重复，直至查询到达最低层上的节点，或者某个中间节点上的数据已经满足查询要求。,数据管理,为兼顾历史数据和新数据，提供一个使数据精度随时间逐渐降低的数据老化方法： 较近的数据提供较高的精度，使用较多的内存； 较老的数据提供较低的精度，消耗较少的内存。 存储管理要考虑到存储空间在不同新、老程度的数据之间的分配。 15使用一个离线的算法来确定系统参数，包括分配给不同层次数据摘要的存储空间比例、每个节点上存储的数据摘要层数等。,分布式四叉树,分布式四叉树用来将不同层次的数据摘要分配给网络中的节点，构成DIMENSIONS搜索树。 DQT按照以下方法构造： 给定一个矩形区域R和一个全局可知的常数c，使用哈希函数h(R,c)将c散列成R中的一个位置（x, y），最靠近（x, y）的节点选为R的存储代理，该节点即为树根。 将每个父节点的矩形空间划分成四等分，将每个子矩形作为h的输入，得到每个子区域的存储代理，它们即为父节点的四个孩子。 这个过程递归进行，直至达到预定的树高。,（3）Comb-Needle 16,一个战场态势感知的例子：,基于推（push）的信息传播策略,传感器节点周期性地将信息推送到网络中。,基于拉（pull）的信息传播策略,士兵需要信息时广播一个查询请求，满足查询条件的节点发送数据。,Comb-Needle模型,传感器节点将数据推送到自己的邻域，形成针状的复制结构，查询过程动态地建立梳子状的路由结构。,算法要点,数据按照一定的路径来存储，查询请求也按照一定的路径传播，只要两条路径相交，查询就能满足。 要权衡的问题： 通信代价与查询覆盖,5. 传感器网络中的数据聚合,可将传感器网络看成是一个分布式数据库系统： 每个传感器是一个独立的数据源，产生由传感器ID、位置、传感器类型、时间戳和测量值等组成的数据记录。 不同节点上同一种传感器产生的数据记录具有相同的样式，这些数据记录形成一个分布式的表。 多个这样的表形成了传感器网络。 网络内数据聚合的必要性： 单个传感器产生的数据有噪声（由传感器硬件引起），受环境的影响也较大，因此单个测量值不可靠，多个测量值的聚合（aggregation）结果比单个测量值更有用。 在网络内聚合数据比在基站上聚合数据节省能量。,分布式查询处理架构,17提出了一个松耦合的分布式架构来支持聚合运算和更复杂的网络内计算。 在网络层和应用层之间引入一个查询层，由运行于每个节点上的查询代理组成。 一个查询优化器位于基站上，从外界收到查询后生成分布式查询处理计划。每个查询处理计划描述了传感器之间的数据流和每个传感器上的计算计划。 查询处理计划传播到所有相关的传感器节点，这些节点上的查询代理创建控制结构（用于协调传感器的行为），启动查询。 查询结果传回基站。,一个例子,一个长时间运行的查询Q，每隔t秒监测一下办公室的平均温度，超过预定值时产生一个输出记录。 查询优化器进行查询优化： 判断能否将新查询与已有的类似查询合并。 生成新的查询计划QP，指出如何确定查询的头节点（计算平均温度的节点）。 为头节点和其它节点分别生成计算计划。 启动查询： 查询计划传播给所有相关节点的查询代理。 查询代理注册该查询，创建本地操作树，激活相关的传感器，按照查询计划的说明返回记录。 平均温度超过用户定义的阈值时，头节点生成一个记录。,计算计划,网络内查询处理的研究问题,聚合： 将数据从分散的源节点传递到一个执行计算的中心节点。 头节点选举：动态可维护，最小化通信开销。 数据从源节点传输到头节点： 直接传输：所有数据记录沿着多跳路由直接发送到头节点，大范围聚合查询会产生大量消息 。 分组合并：中间节点将几个数据记录合并到一个较大的分组中传输，减少分组传输开销。 部分聚合：中间节点计算部分结果，头节点从部分结果中计算出最终结果。，减少要传输的数据量。 同步： 分组合并和部分聚合要求协调通信路径上传感器节点的传输，每个节点需要知道收集哪些节点的数据及等待多长时间。,网络内查询处理的研究问题（续）,查询语言： 从应用的角度设计通用的查询语言：无法预知新的应用需要哪些功能。 从数据的角度设计查询语言：观察传感器数据本身的特性，抽象出对这些数据类型可能的计算模式。 查询优化： 对于复杂的查询，从各种可能的查询计划中选择一个最好的，需反映网络拓扑、节点能量水平等的变化。 目录管理： 设计有效的数据结构，保存查询优化需要的网络状态信息，如传感器位置、密度和连通度、系统工作负载等。 多查询优化 在多个用户发布的查询中共享中间结果。,能量有效的数据聚合算法,一个数据聚合方案是能量有效的，如果它能够最大化网络效能（functionality），通常用网络寿命来量化算法的能量有效性。 衡量数据聚合算法的重要性能指标包括： 网络寿命：从网络开始运行至比例为的传感器节点死亡时所允许的数据聚合回合数。 数据精度：数据精度取决于传感器网络所要实现的应用。 延迟：从数据包在网络中产生至基站收到该数据包所用的时间。,网络架构与数据聚合协议,传感器网络的结构有平面结构和层次结构两大类： 平面结构的网络：数据聚合依靠以数据为中心的路由实现，基站将查询消息发送到传感器节点，符合条件的节点向基站发送数据，可能使基站承担过多的通信和计算负担。 层次结构的网络：数据聚合涉及在特殊节点进行数据融合，可减少向基站发送的数据量，提高网络的能量有效性。,5.1 基于簇的数据聚合-LEACH 18,LEACH对于节点和网络有以下假设： 节点：节点是同构的，（需要的话）所有节点都能够直接与基站通信。 网络：节点总是有数据要发送给基站，相互邻近的节点采集的数据是相关的。 LEACH的基本思想： 节点组织成簇，节点将数据发送给本地簇头，簇头进行聚合计算，将结果直接发送给基站。 采用随机轮换簇头的方法，将承担簇头的责任均匀分布到网络中。 LEACH的运行划分为一系列回合。每一个回合开始于一个建立阶段，在这个阶段建立簇；然后是稳定阶段，在这个阶段传输数据。,簇头选举,簇头选举算法有两个目标：每个回合选出k个簇头；每个节点成为簇头的机会相等。 在第(r+1)个回合（从时间t开始），节点i以概率Pi(t)选举自己成为簇头，Pi(t)应使得该轮选出的簇头节点个数的期望值为k：,基于剩余能量的簇头选举,如果节点具有不同的能量，则具有较多剩余能量的节点应比剩余能量较少的节点有更多的机会成为簇头，为此： 节点可用本簇中的节点平均剩余能量乘以N来估计网络中所有节点的剩余能量之和。,簇形成算法,节点选举自己成为簇头后，使用非坚持CSMA协议广播一个广告消息，消息中包含簇头节点的ID。 非簇头节点选择接收信号强度最大的节点作为自己的簇头，然后使用非坚持CSMA发送一个加入消息，消息中包含节点自己的ID及簇头ID。 簇头在本簇内建立一个TDMA调度，发送给本簇内所有节点，至此建立阶段完成。,稳定阶段,稳定阶段的运行划分为一系列帧，在每一帧中节点在分配给自己的时间片里最多向簇头发送一次数据。 每个时间片的长度是固定的，因此一帧的时间长度取决于簇中节点的个数。 簇头接收完所有的数据后，执行聚合计算，将结果发送给基站。 为减少簇间通信干扰，LEACH使用扩频通信。每个簇内部使用一种扩频码，簇头与基站通信时使用基站的扩频码，因此簇头与基站通信前先要监听信道。,5.2 基于链的数据聚合PEGASIS19,19从最小化能量消耗的思想提出了基于链的数据聚合，其基本思想是： 所有节点连接在一条链中，位置相近的节点在链上成为邻居。 每个节点从一个邻居接收数据，与自己的数据融合后再发送给另一个邻居。 这个过程沿着链进行，直至到达本回合的头节点，头节点将聚合结果发送给基站。 每个回合只指定一个头节点，且每个节点轮流成为头节点。 PEGASIS需要基于以下假设： 每个节点具有功率控制能力，可以发送数据给任何其它节点或直接发送给基站。 节点是同构的，能量有限，起始时能量相等。 每个节点知道网络中所有节点的位置。 节点不移动。,链的构造,从离基站最远的节点开始构造链，选择与其最近的节点加入链中。 按同样方法，每个节点都从剩余节点中选择离其最近的节点加入链中，直至所有节点均加入。 链上的节点用c0c(N-1) 顺序标记，N为节点总数。,数据收集,数据收集： 每一轮数据收集由基站发送一个信标消息启动。 在第i个回合，链上第（i-1）个节点成为头节点。 数据传输过程划分为时间片，链的末端节点c0在第一个时间片发送数据给c1，c1融合自己的数据后，在第二个时间片发送给c2。依次类推，直至到达头节点。随后数据传输从链的另一端c(N-1)开始，向头节点移动。 在第N个时间片，头节点发送数据给基站。,链的分层方案,为最大化能量-延迟乘积，19设计了基于链的分层方案： 建立由全部节点形成的单链（第一层） 将链分成G个连续的段，每段（组）包含N/G个节点。每组有一个节点成为第二层上的节点，这G个节点按照顺序构成第二层链。 将第二层上的G个节点分成连续的两组，每组有一个节点成为第三层上的节点。,在层次链上的数据收集,第i轮选择c(i-1)为头节点。 在每一组中，选择链序号为c(i-1) mod (N/G)的节点作为这一组的代表节点，该组其余节点沿着链将数据发送到本组代表节点进行融合。 在第二层上，有一组的代表节点即为头节点c(i-1)，另一组的代表节点为c(i-1)+N/2 mod N，每一组中的节点沿着链将数据发送到本组代表节点融合。 第三层上，非头节点将部分融合结果发送给头节点，头节点融合后发送给基站。,分层收集的例子,100个节点分成10组，c18为头节点。,5.3 基于树的数据聚合EADAT20,传感器节点组织成一棵树，数据向树根传播的过程中在中间节点聚合，结果报告给树根（sink）。 EADAT基于以下假设： 每个节点在网络启动时侦听信道 所有节点具有相同的传输距离（对称链路） 邻居节点具有不同的ID（可以相互区分） 控制消息包含5个域