第八章容错技术

1、无线传感器网络技术无线传感器网络技术讲义讲义第八章、容错设计技术内容提要1.概述 2.故障模型3.故障检测4.故障修复5.可靠性协议n容错是系统在运行过程中发生一定的硬件故障或软件错误时，仍能保持正常工作而不影响正确结果的一种性能或措施。n容错是采用冗余方法来消除故障影响的。 硬件冗余： 以检测或屏蔽故障为目的而增加一定硬件设备的方法。 软件冗余：为了检测或屏蔽软件中的差错而增加一些在正常运行时所不需要的软件方法。 信息冗余：在实现正常功能所需要的信息外，在添加一些信息，以保证运行结果正确性的方法。纠错码就是信息冗余例子。 时间冗余：使用附加一定时间的方法来完成系统功能。这些附加的时间主要用在

2、故障检测、复执或故障屏蔽上。 概述以往容错研究关注的领域:n大规模集成电路n分布式系统n数据库n互联网n概述容错方面的术语:n故障（Fault）n差错（Error）n失效（Failure）n可靠性（Dependability）n概述WSN容错的重要性：n技术和实现因素。通常需要直接暴露在环境中，在受到成本和能量限制的同时，需要完成一系列的任务。n无线传感器网络是一个新兴的研究和工程领域，处理特定问题的最优方法还不明确。n无线传感器网络的应用模式。无线传感器网络通常是运行在无人干预模式，它们需要具有更强的容错能力。 概述大鸭岛试验结果概述-一个容错实例n用声音、高度两个特征区分一间办公室的六个人

3、内容提要1.概述 2.故障模型3.故障检测4.故障修复5.可靠性协议故障模型n部件故障n传感、供电、通信等部件发生故障，测量值偏离了实际值n节点故障n节点无法连上网络故障模型故障级别故障级别故障表征故障表征故障检测故障检测修复机制修复机制部件故障节点能够正常通信，但是测量数据是错误的检测出错误的测量数据舍弃或校正出错的测量数据节点故障节点不能与其它节点进行通信通过询问或重新路由等方法检测故障节点通过移动冗余节点弥补形成的连接和覆盖问题故障模型传感部件故障n固定故障 n偏移故障n倍数故障n方差下降故障内容提要1.概述 2.故障模型3.故障检测4.故障修复5.可靠性协议故障检测n部件故障检测n基于

4、空间相关性n基于贝叶斯网络n节点故障检测n集中式n分布式部件故障检测n基于空间相关性 除了节点n或节点8，其它节点都感应到事件发生 部件故障检测n基于空间相关性 节点n在三个可信节点的三角区域内 部件故障检测n比较策略n多数投票n均值n中值n 部件故障检测n决策判断实例 logO nn(a)(b)A0(c)A1A4A2A3B0B1B4B2B3C0C1C4C2C3正常感应器故障传感器部件故障检测n加权中值判断结果 logO nn加权后的理论识别率（邻居数为4） 部件故障检测n加权中值判断结果 logO nn加权后的理论误报率（邻居数为4） 部件故障检测n基于贝叶斯网络 贝叶斯信任网络包含一个有向

5、图和与之对应的概率表集合。有向图中的顶点表示变量，边表示变量之间的影响关系。贝叶斯信任网络的关键特征是能够模型化并推理出不确定因素。模型化节点间的可靠关系是通过节点概率表实现。 n实施步骤：n构造得到所有变量的联合概率分布n学习通过训练得到各变量间的条件概率n推理由一些已知属性值推断位置变量的概率分布。 部件故障检测n基于贝叶斯网络-以大鸭岛试验为例部件故障检测n基于贝叶斯网络-以大鸭岛试验为例温度、电压的概率分布 部件故障检测n基于贝叶斯网络-以大鸭岛试验为例气压、相对湿度的条件概率分布 部件故障检测n基于贝叶斯网络-以大鸭岛试验为例计算推理节点故障检测n集中式故障检测在Sink节点放置检测

6、程序，实时监测网络状态，根据节点上报的信息判断发生了什么事件。汇聚节点收集的信息名称名称描述描述邻居列表由邻居ID号组成的一个列表链路质量用0（100丢失）至100（100传送）间的一个数来表示字节数节点传输和收到的字节数下一跳路由的下一跳节点（路由表）路径丢失从节点到Sink节点的链接质量的一种衡量（路由表）节点故障检测n集中式故障检测汇聚节点做出的判断事件名事件名描述描述用来识别事件的信息用来识别事件的信息节点丢失节点没有出现在任何节点的邻居列表中所有邻居表孤立节点节点没有任何邻居此节点的邻居表路由改变比较当前路由表与上次路由表的变化此节点的路由表信息邻居表改变比较当前路由表与上次的邻居表

7、的变化此节点的邻居表链路质量改变此节点与邻居的链路质量低于统计定义的门槛值。把当前的和以前的链接质量写入日志。此节点的邻居表节点故障检测n分布式故障检测 由每个节点自行检测。节点发现数据下降后，询问子节点，如果得到肯定答复则继续询问下去，如果遇到否定回答，则这个父节点触发诊断程序，把诊断到的原因和可能的补救措施发往基站以写入日志。并发冲突？隐藏终端使能RTS/CTS是否发送队列满？网络拥塞减低发送速率是否并发冲突？非对称链路修改路由表是否.每个节点判断的算法内容提要1.概述 2.故障模型3.故障检测4.故障修复5.可靠性协议故障修复n基于连接的修复 （保证连接的通畅）n部署k连通拓扑 n非k连

8、通图 n基于覆盖的修复 （保证区域覆盖）故障修复n基于连接的修复 -部署k连通拓扑 V7失效会导致网络断开成三部分n基于连接的修复 -部署k连通拓扑 K连通网络：网络中任意两点之间都至少有K条不相交的路径，K连通网络中任意K-1个节点发生故障时网络仍然保持连通。故障修复n基于连接的修复 -部署k连通拓扑 三连通图故障修复n基于连接的修复 -部署k连通拓扑 n在完全图中找最小代价的K连通子图的算法n集中式 n分布式 kFGSSkFLSSn集中式 n 基本思路：把网络模型化一个图，节点是图中的点，存在直接通信连接的节点间做一条边，节点间的距离作为这条边的权重。n 步骤：1、按权重对所有边排序； 2

9、、根据该边两个端点是否有K条路径连通按照权重由大到小考虑是否加入生成子图； 3、判断所有节点是否都达到K连通，不是则重复第2步。 kFGSSn分布式 由信息收集、拓扑构造、决定传输能量三个阶段组成。n信息收集：节点广播ID并收集周围节点信息；n拓扑构造：使用FGSSk算法，每个节点生成一个K连通子图；n 决定传输能量：去掉单向边或者加强为双向边改进生成的连通图kFLSS故障修复n基于连接的修复 -非k连通拓扑 基站收不到某些节点的消息 故障修复n基于连接的修复 -非k连通拓扑 重新路由故障修复n基于连接的修复 -选择容错节点 Sk可作为S3的容错节点Sks2s3s1故障修复n基于覆盖的修复名称

10、名称定义定义计算方法计算方法覆盖区域节点单独覆盖的区域整个感知区域去掉与其它节点重叠的感知区域移动区域有效节点移动到该区域即可重新覆盖漏掉的区域以遗漏区域的边界为圆心，节点感知半径为半径作圆所形成的所有区域故障修复n基于覆盖的修复故障修复n基于覆盖的修复1，初始化阶段；节点计算自己的覆盖区域、每个覆盖区域对应的移动区域。2，恐慌请求阶段；垂死节点广播求助消息。3，恐慌回应阶段；垂死节点的邻居收到求助消息后计算如果自己移动到垂死节点的移动区域，是否会影响到自身的覆盖区域，如果不影响则给求助节点返回消息。4，决策阶段；垂死节点根据收到的回应信息，决定让哪个节点移动。 内容提要1.概述 2.故障模型

11、3.故障检测4.故障修复5.可靠性协议可靠性协议n物理层 n链路层n网络层n传输层可靠性协议n物理层 物理层是实现无线网络通信的基石，其可靠性能的优劣直接影响到整个系统的容错能力。物理层主要负责数据的编码调制、解调解码、发送与接收。对于无线传感器网络节点间的通信，为了使得数据能够被可靠地传输或接收，必须要做到高的接收机灵敏度、低的背景噪声及较强的抗干扰能力。 可靠性协议n链路层 数据链路层主要负责数据流的多路选择、数据帧侦测、媒介访问、差错控制 ，保证了点到点、点到多点的可靠性链接。媒介访问控制为数据传输建立通信链路，并提供对共享媒介的公平、有效的访问。它需要减少或避免媒介中的包冲突。 差错控

12、制主要采用自动重发请求（ARQ）和前向纠错（FEC）。 可靠性协议n网络层 建立局部多路径可靠性协议n网络层 定向洪泛Sink NodeVirtual ApertureSenderBAn无线传感器网络的传输层需要提供可靠的、低延迟、能量有效的、公平的信息传输。为了达到这些要求，它需要解决信道损耗、干扰、带宽有限、突发通信、节点资源受限等问题。分布式的跳与跳的传输层机制来提供传输的可靠性。可靠性协议可靠性协议n传输层事件汇聚到Sink可靠性协议n传输层 - 从汇聚节点到传感节点的传输 PSFQ（Pump Slowly, Fetch Quickly）为无线传感器网络的重编程或重新指定任务提供了可靠传输，并提供了到接收端延迟保证。源节