无线传感器网络.ppt.ppt

无线传感器网络,主要内容,1.无线传感器网络概述,无线传感器网络通常由大量具有感知、计算及无线通信能力的微小节点组成，其目的是监视环境而非通信。传感器节点部署在要监视的区域中，采集指定的环境参数，并将数据发送到汇聚节点供分析。,传感器节点的组成,传感器节点一般由传感模块、处理模块、无线通信模块和能量供应模块组成。传感器节点已经可以做得非常小，称为智能尘埃（smart dust）。,传感器节点的特点,廉价：每个节点的期望价格在一美元左右体积小：火柴盒或硬币般大小重量轻：小于100克能量有限：两节五号电池或纽扣电池供电无线通信能力：能够用无线电、红外线、蓝牙、超声波等通信，带宽低，干扰大计算能力：几百兆赫兹的处理器存储能力：几兆或几百兆的存储空间感知能力：具有一个或几个传感器软件环境：TinyOS是专为传感器节点开发的操作系统,传感器网络的特点,节点固定或只有较小的活动性数量大，密度高拓扑动态变化节点同构，或只有少量特殊节点；分布式：没有预先指定的中心，所有节点通过分布式算法相互协调；自组织：传感器网络的部署和初始化等不需要外界干预；节点资源受限，特别是能量非常有限；以数据为中心的网络，节点具有数据处理的能力；与应用紧密耦合的网络,传感器网络与移动自组网的不同,节点规模：移动自组网：节点数量通常在几十或上百传感器网络：节点数目往往高出好几个数量级节点密度：移动自组网：小传感器网络：大（冗余部署的结果）拓扑变化的原因：移动自组网：节点运动传感器网络：节点休眠调度、环境干扰或节点故障引起节点处理能力：移动自组网：较强传感器网络：十分有限,传感器网络的应用,传感器网络在环境监视方面的优势：通过在物理环境中部署大量廉价的智能传感器节点，可以获得长时间、近距离、高分辨率的环境数据，这是传统监视设备无法得到的。传感器节点的计算和存储能力允许节点执行数据过滤、数据压缩等操作，也可以执行一些应用特定的处理任务。节点之间的通信能力允许节点之间协同完成更复杂的任务，如目标跟踪。通过任务的重新分配可以改变传感器网络的用途。,无线传感器网络要解决的问题,网络的自组织、自配置（节点定位、时间同步、自动校准、拓扑控制等）通信协议（MAC、路由协议）分布式数据管理（数据采集、存储、查询、获取等）各种应用特定的数据融合处理节省能耗应贯穿到所有的设计中。,2.国内外研究现状,从目前国内外WSN已有研究成果统计来看，WSN领域各研究点所占的比例如右图所示。对网络协议、能量、定位、可靠性、网络架构以及数据处理的研究是WSN研究的热点问题。,国内外研究现状:产品,加州大学Berkeley分校Mote系列,国内外研究现状,主要研究方法解析(Analytic)根据限定条件和合理假设，描述研究对象和系统，抽象数学分析模型来对问题进行求解。模拟和仿真(Simulation&Emulation)应用网络模拟和仿真软件(自己开发或通用)，建立网络和系统模型，运行模型并计算和分析结果。实验(Testbed)设计所需硬、软件配置，建立测试床等现实网络来进行网络协议、行为和性能的研究。,国内外研究现状,主要研究方法对比解析方法的有效性和精确性受假设限制很大。模拟仿真方法可根据需要设计所需网络模型，只需较少的时间和费用就能得到网络在不同条件下的各种特性，灵活，高效，低成本。但目前网络模拟和仿真软件对WSN的模拟和仿真并不能完全真实和有效的反映整个网络的状态。(注：采用解析和模拟仿真相结合的方法是WSN理论研究的主要手段)实验方法相对成本较高，不如仿真灵活，但能获得丰富有效的网络数据，准确的测试和评估网络的性能，是将理论成果转化为网络标准或产品的必经之路。,3.WSN的协议,MAC协议 在无线传感器网络中，介质访问控制协议决定无线信道的使用方式，在传感器节点之间分配有限的无线通信资源，用来构建传感器网络系统的底层基础结构。设计MAC协议时考虑：节省能量 可扩展性 网络效率,WSN的协议（续）,MAC协议 MAC网络能量浪费主要原因：数据重传，耗费节点更多能量。节点接受不必要的数据。节点不需要发送数据时，过度侦听。信道分配时，控制消息过多。,WSN的协议（续）,MAC协议 节点无线通信模块的状态包括：发送状态、接受状态、侦听状态、睡眠状态。各状态耗能按上述顺序依次减少，因此通常采用”侦听/睡眠”交替使用的无线信道使用策略。,WSN的协议（续）,MAC协议 针对不同的传感器网络应用，提出不同的MAC协议，主要分3类：时分复用（TDMA）的MAC协议。随机竞争的MAC协议。其他MAC协议。如：频分复用或码分复用等协议。,WSN的协议（续）,MD(Mediation Device)协议TDMA和CSMA的混合SMACS/EAR(selforganizing medium access control for sensor networks/eavesdrop and register)协议TDMA和FDMA的混合,WSN的协议（续）,路由协议 和传统的路由协议相比，无线传感器的路由协议有以下特点：能量优先基于局部拓扑信息以数据为中心应用相关,WSN的协议（续）,路由协议分类能量感知路由协议。基于查询的路由协议。地理位置的路由协议。可靠的路由协议。,4.WSN MAC,任何共享媒体如以太、无线频率资源。通常在任一特定时刻只能为一个用户服务，多用户共享媒体资源。MAC协议起着协调多个用户接入共享媒体的作用。,WSN MAC,MAC协议的选择与应用关系密切 在其他应用中，我们有足够的能量与带宽来使用高开销的解决方案。例如，CSMA，发送者一直侦听媒体，直到其空闲才进行发送。但这样的协议在WSN并不适用。,WSN MAC,WSN需要energy-efficient MAC耗能的各个方面发送（transmitting）耗能大接收（Receiving）耗能大空闲（Idling）耗能较少引起能量浪费的各个方面碰撞带来的开销（Collisions）额外开销（Overhearing）协议开销（Protocol overhead）空闲侦听（Idle listening）,WSN MAC,基于竞争的MAC(Contention-Based)追求最小时延与最 大吞吐量需要进行信道侦听,WSNMAC,基于调度的MAC(Reservation/ScheduleBased)公平的进行共享信 道资源的分配避免了冲突发生,WSN MAC,基于竞争的MAC工作原理Sender A checks to see that the line is clear(Carrier Sense载波侦听)Sender A announces Request-To-Send(RTS请求帧)All nodes seeing the RTS defer pending sends to avoid collisionsRecipient B sends Clear-To-Send(CTS清除帧)All nodes seeing the CTS defer pending sends to avoid collisionsSender A sends data,WSN MAC,Contention-Based MAC载波侦听方式物理载波侦听 Physical Carrier Sense由物理层提供虚拟载波侦听 Virtual Carrier Sense 网络活动向量 Network Activity Vector(NAV)由MAC层提供,WSN MAC,Contention-Based MAC优缺点优点很好的避免了碰撞的发生有报文长度指示，其他节点知道延迟发送时间缺点控制报文的开销大在空闲模式下能量消耗大不支持多播,WSN MAC,Schedule-Based MAC（基于调度的MAC）主要运用TDMA时分多址技术 Time-Division Multiple Access 基于时隙的调度 基本调度单位是 slot/slice,WSN MAC,Schedule-Based MAC优点较低的能量消耗所有节点只需在每个时隙的开始时刻侦听所有节点只在分配给自己的时隙发送数据一旦本地组建立，不再需要控制报文,WSN MAC,Schedule-Based MAC缺点需要时间同步假定节点只与本地组内的节点通信网络规模受限（Scales badly)不适应网络拓扑变化带宽利用率低,WSN MAC,S-MAC（sensor MAC）2003年在802.11MAC协议基础上针对传感器网络的节省能量需求提出的新的MAC协议。特点：energy efficient good scalability collision avoidance,WSN MAC S-MAC,S-MAC Listen/Sleep Cycle周期性侦听/睡眠机制,监听间隔包括接收SYNC帧和接收RTS帧 发送者试图发送SYNC帧时，他在接收者开始侦听时开始载波侦听，并随机的选择一个时隙来完成载波侦听的过程 如果在时隙结束时没有检测到信息传输，发送者就赢得信道并同时发送SYNC帧。,WSN MAC T-MAC,在S-MAC基础上提出来根据通信量的变化来调整节点的侦听时间引入了可变占空比的概念可以动态决定活跃时间的长度降低节点在消息传输频率较低的情况下的空闲侦听带来的能耗,WSN MAC T-MAC,T-MAC针对早睡问题提出的解决方法：未来请求发送（Future RTS）满缓冲区优先（full buffer priority）,5.OMNET,OMNeT+OMNeT+(Object Modular Network Test-bed in C+)是1992年开发的一个开源的、基于组件的模块化离散事件模拟器，主要用于通信网络及分布式系统方面的模拟，可以运行在Unix和windows环境下。仿真模型采用了混合式的建模方式，同时使用了OMNet+特有的NED（NEtwork Discription）语言和C+进行建模。,6.节点定位,节点定位是传感器网络的重要基础功能，没有位置信息的环境数据是没有意义的。手工为每个节点设定位置不可能，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为圆心、通信距离为半径的圆中。,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模型,传感器节点将数据推送到自己的邻域，形成针状的复制结构，查询过程动态地建立梳子状的路由结构。,算法要点,数据按照一定的路径来存储，查询请求也按照一定的路径传播，只要两条路径相交，查询就能满足。要权衡的问题：通信代价与查询覆盖,参考文献,1Overview of Sensor Networks.2Underground Structure Monitoring with Wireless Sensor Networks.3A Platform for Ubiquitous Sensor Deployment in Occupational and Domestic Environments.IPSN07最佳论文。4Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors.ACM SIGMOBILE01.5Ad Hoc Positioning System(APS)Using AoA.6GPS-less Low Cost Outdoor Localization for Very Small Devices.7Convex Position Estimation in Wireless Sensor Networks.8DV Base