5 容错设计技术 报告人：田素云 2011. 10. 21

提纲 概述 故障模型 故障检测 故障修复 可靠性协议

概述 容错，翻译为“fault-tolerant”,有“容故障”的含义 容错研究关注的领域 网络容错 无线传感器网络容错（因素） 大规模集成电路,分布式系统,数据库,互联网,... 网络容错 网络中某个节点或节点的某个部件发生故障时，网络仍然能完成指定的工作。 无线传感器网络容错（因素） 自身容易发生故障 受到外界环境影响 WSNs正常工作，更需要有效的容错设计来满足其可靠性要求。

概述 容错的基本概念 三者的关系 故障(fault)，是指一个设备、元件或组件的一种物理状态，在此状态下它们不能按照所要求的方式工作。 差错(error)，是指一个不正确的步骤、过程或结果。 失效(failure)，是指某个设备中止了它完成所要求功能的能力。 三者的关系 故障只有在某些条件下才能在其输出端产生差错，这些差错由于在系统内部，不容易被观测到。 差错只有积累到一定程度或者在某些系统环境下，才能使系统失效。 故障和差错是面向制造与维修的；失效是面向用户的。

概述 最底层的故障,引起数据输出的差错,导致系统最后的失效,这种关系普遍存在。

容错的重要性 WSNs对容错设计的新挑战 技术和实现因素 应用模式 新兴的研究和工程领域 与传统网络的差异 传感器节点通常需要直接暴露在环境中，更易受到物理、化学、生物等外力的破坏，所以自身可靠性差。 传感器节点体积小，能量、计算、存储、通信受限，分布式组网完成任务，本身就是一个挑战。 应用模式 无线传感器网络通常是运行在无人干预模式，它们需要具有更强的容错能力。 新兴的研究和工程领域 处理特定问题的最优方法还不明确，技术与预期应用在快速变化，所以容错处理难以预见。 与传统网络的差异 无线通信网络，以网络为中心，提供网络的互联、互通和互操作,为数据提供正确、可靠的传输。 无线传感器网络，以数据的采集、 数据的处理为中心（必要时，可以牺牲部分节点，保证完成任务）。

容错的重要性(续) 面对挑战的期望 WSNs容错设计需要考虑三个方面 传感器网络的软、 硬件必须具有很强的容错性 ,以保证系统具有高可信性和高强壮性。 在网络节点的软、 硬件出现故障时 ,能够通过应用一定的容错技术使整个系统自动调整或自动重构 ,纠正错误 ,保证任务的正常执行。 无线传感器网络的容错算法不能过于复杂 ,同时还应当支持节能的特性；一般而言 ,要达到越好的容错性 ,将消耗越多的能量；,在设计无线传感器网络的容错算法时 ,还需要在这两者之间进行权衡。 WSNs容错设计需要考虑三个方面 故障模型，故障检测，故障修复

提纲 概述 故障模型 故障检测 故障修复 可靠性协议

故障模型 故障分类 三者关系 部件级 节点级 网络级 网络包含节点 节点包含部件 层次关系决定了高层故障本质由低层故障所造成 故障级别 故障表征 故障检测 修复机制 部件级 故障节点能够正常通信，但是测量数据是错误的 检测出错误的测量数据 舍弃或校正出错误的测量数据 节点级 故障节点不能与其他节点进行通信 通过询问或重新路由等方法检测故障节点 通过移动冗余节点弥补形成的连接和覆盖问题 网络级 某个区域内的节点都出现故障，造成部分网络停止工作 区域故障节点数目统计；数据包穿越率 舍弃或同上处理 表1 故障模型的层次

部件级模型 部件故障 传感器节点由计算、通信、存储、能量供应、传感等功能部件组成，每个部件都有可能发生故障。 部件故障主要归于传感部件故障 传感、供电、通信等部件发生故障，测量值偏离了实际值。 传感器节点由计算、通信、存储、能量供应、传感等功能部件组成，每个部件都有可能发生故障。 处理器、存储器、通信部件的可靠性高，不易出错。 传感部件（感应器+模数转换ADC），低成本、能量受限、暴露在外界环境，易发生故障。 部件故障主要归于传感部件故障

部件级模型(续) 部件故障分类 按测量值与实际值的差值的组成与成因，故障分为4类。 固定故障，感应器的读数一直为某个固定的值（通常大于或小于正常的感知范围，不能提供任何感知环境的信息）。 偏移故障，在真实值的基础上附加一个常量。 倍数故障，真实值被放大或缩小某个倍数 方差下降故障，使用时间过长，感应器老化后变得越来越不精确而产生的。 注：没有对测量值的先验知识，仅以结果不能分辨出偏移故障与倍数故障。

提纲 概述 故障模型 故障检测 故障修复 可靠性协议

故障检测 故障检测的分类 故障检测的目标 部件故障检测（检测传感器部件） 节点故障检测（定位故障节点） 检测网络中的异常行为 基于空间相关性 基于贝叶斯网络 节点故障检测（定位故障节点） 集中式 分布式 故障检测的目标 检测网络中的异常行为

部件故障检测 部件故障的分类 故障检测的衡量指标 简单的传感器故障模型 复杂的传感器故障模型 识别率，发生故障的部件被检测为有故障的概率。 0-1模型（0-不工作；1-正常工作） 直接观察输出结果，判断故障 复杂的传感器故障模型 连续或多级数字输出 基于空间相关性或基于贝叶斯网络，判断故障 故障检测的衡量指标 识别率，发生故障的部件被检测为有故障的概率。 误报率，把正常部件判定为发生故障的概率。

基于空间相关性 基本思想 方法分类 空间相关性，WSNs中相邻节点的同类传感器所测量的值通常很相近。 一个节点通过周围邻居节点的同类传感器来检测自己的传感器是否发生了故障。 方法分类 需要地理位置信息 不需要地理位置信息

需要地理位置信息 某节点的传感部件测量结果与周围节点（依地理信息判定）测量结果都不同时，这个节点的传感部件可能发生故障。 例 节点1~节点8都感应到了事件的发生，而节点n没有感应到事件的发生，则认为节点n的传感部件发生了故障 如果节点n及节点1~节点7都感应到了事件，则可以判断节点8的传感部件发生了故障。

需要地理位置信息(续) 一种检测方法 三角形法 节点n在三个可信节点的三角区域内 切线垂直于连心线

不需要地理位置信息(1/3) 基本思想 判断策略 不需要地理信息，节点依据侦听到的邻居(依节点邻居表判定)数据来判断自己的测量值是否正确。 多数投票策略 均值策略 中值策略

不需要地理位置信息(2/3) 判断策略的形式化表达 表2 三种故障检测策略

不需要地理位置信息(3/3) 判断策略的比较 识别率 误报率 时间复杂度 多数投票策略 较高 低 O(n) 均值策略 较低 中值策略 高 O(nlogn) 表3 判断策略比较 综合能效、检测精度及时间复杂度，中值策略是一种适于无线传感器网络。

判断策略的改进 错误实例 多数投票策略 节点设置可信度（权重值） 可信度高 权重值大 投票权大 提高识别度，减少误报率

判断策略的改进(续) 策略改进、加入权值后的比较结果，提高识别度，减少误报率。

故障检测 故障检测的分类 故障检测的目标 部件故障检测（检测传感器部件） 节点故障检测（定位故障节点） 检测网络中的异常行为 基于空间相关性 基于贝叶斯网络 节点故障检测（定位故障节点） 集中式 分布式 故障检测的目标 检测网络中的异常行为

基于贝叶斯网络(1/4) 基本思想 检测工具 贝叶斯网络 不同部件间的潜在关系(部件间的信任关系)，可以用来检测传感部件是否发生故障。 这些部件可以属于同一节点，也可属于不同节点。 检测工具 贝叶斯网络(BBN) 贝叶斯网络 基于概率推理的数学模型 结构：一个有向图和与之对应的概率表的集合 阶段：构造、学习、推理 模型化并推理出不确定的因素。

基于贝叶斯网络(2/4) 实例 构造 大鸭岛实验情景来应用贝叶斯信任网络实现传感部件的故障检测 环境监测中有五个属性：温度(T)，湿度(H)，气压(P)，光照强度(L)，节点电压(V) 这五个属性的关系所示：气压和湿度受温度影响，而电压影响了所有其他属性。 构造 有向图 一个节点所有属性的联合概率分布 V P H L T 图9 属性间的条件依赖关系 P(V,T,H,P,L)=P(V) P(L|V) P(T|V) P(H|V,T) P(P|V,T)

基于贝叶斯网络(3/4) 学习 设所有属性被划分成两个不重叠的子区间r1，r2。 通过大量数据训练得到以下概率 S P(St) P(Sv) P(N|S):给定当前读数落入某个区间的概率的情况下， 邻居读数落入某个区间的概率。 S P(St) P(Sv) r1 0.9 0.6 r2 0.1 0.4 表4 温度、电压的概率分布 St Sv P(Sp) P(Sh) r1 r2 0.5 0.6 0.4 0.9 0.1 0.3 0.7 0.2 0.8 表5 气压、湿度的条件概率分布

基于贝叶斯网络(4/4) 推理 已知节点的湿度H∈r2，电压V∈r1，由此来推测是否T∈r1？ T P(H|V,T) P(T) P(V) P(T|V=r1,H=r2) r1 0.4*0.9*0.6=0.216 0.4 r2 0.8*0.1*0.6=0.048 0.8 表6 计算推理

故障检测 故障检测的分类 故障检测的目标 部件故障检测（检测传感器部件） 节点故障检测（定位故障节点） 检测网络中的异常行为 基于空间相关性 基于贝叶斯网络 节点故障检测（定位故障节点） 集中式 分布式 故障检测的目标 检测网络中的异常行为

节点故障检测 定义 节点能否与外界正常通信 原因 能量耗尽 通信故障 分类 集中式 分布式

从节点到Sink节点的链路质量的一种衡量 集中式故障检测 名称 描述 邻居列表 由邻居ID号组成的一个列表 链路质量 用0至100间的一个数来表示 字节数 节点传输和收到的字节数 下一跳 路由的下一跳节点 路径丢失 从节点到Sink节点的链路质量的一种衡量 在Sink节点放置检测程序，实时监测网络状态。 各节点周期性地向Sink节点上报信息。 Sink节点的处理能力高，利用收集的信息判断某事件的发生。 表7 收集信息列表 事件名 描述 用来识别事件的信息 节点丢失 节点没有出现在任何节点的邻居列表中 所有邻居表 孤立节点 节点没有任何邻居 此节点的邻居表 路由改变 比较当前路由表与上次路由表的变化 此节点的路由表 邻居表改变 比较当前邻居表与上次邻居表的变化 链路质量改变 此节点与邻居的链路质量低于统计定义的门槛值。把当前的和以前的链路质量写入日志 表8 事件列表

分布式故障检测 不是由Sink节点统一检测，而是由每个节点分别自行检测 算法分为多个阶段 每个阶段分为两部分 每个阶段检测一项故障原因 每个阶段分为两部分 判断故障是否发生 处理故障措施 检测阶段有顺序性，调换顺序会导致误判

提纲 概述 故障模型 故障检测 故障修复 可靠性协议

故障修复 基本思想： 容错拓扑（预防）策略：通过预先设计的拓扑算法部署无线传感器网络节点或临时变更部分节点的路由，使得WSNs对节点发生故障有一定容忍度，这样在部分传感器节点发生故障时，剩余节点仍能保持通信，继续工作。 容错节点（修补）策略：无线传感器网络通常不需要所有节点都保持活动状态，利用WSNs的容错节点（包括WSNs的冗余节点或睡眠节点），当有节点失效时，容错节点在当前位置或移动到制指定位置，从而弥补失效节点所造成的连接割断或覆盖漏洞。

故障修复 具体策略的应用，取决于WSNs的具体情况（WSNs是否可以按预先设计部署节点；局部范围内是否存在容错节点等），当然如果将上述预防策略与修补策略相结合，会得到更好的WSNs故障修复结果。 本节将论述基于连接和基于覆盖的两类故障修复方法。

基本概念 节点模型 节点连通 点覆盖 区域覆盖 连通与覆盖 定理 R-通信半径 r-感知半径 r通常小于R，如图13 |AB|<=R,即节点A与节点B连通，如图14 点覆盖 |AC|<=r，即位置C在节点A的感知范围内，如图15-1 区域覆盖 区域内所有点被覆盖，如图15-2 连通与覆盖 连通问题，保证网络中各节点都能正常通信 覆盖问题，保证监控区域中每个位置至少被一个节点覆盖 定理 R>=2r,完全覆盖保证监控区域内各节点都连通

故障修复分类 基于连接的修复 部署k连通拓扑 非k连通图 基于覆盖的修复

部署k连通拓扑 基本概念：构造k连通图是一种建立容错拓扑的方法。k连通网络是指网络中任意两点之间都至少有k条不相交的路径，k连通网络中任意k-1个节点发生故障时网络仍能保持连通。 例：三连通图能容忍任意2个节点的故障而剩余节点仍能保持网络连通性

部署k连通拓扑(续) 在完全图中找最小代价的k连通子图是NP难题，有很多近似算法。 例：集中式算法 FGSS （Fault-tolerant Global Spanning Subgraph） FGSS是一个集中式贪婪算法，它使得网络中的最大能耗最小化。把网络模型化为一个图，节点是图中的点，存在直接通信连接的节点间作一条边，两个节点间的距离作为该边的权重。（把距离等效为能量，信息传送距离越远，耗能越大）

FGSS 算法步骤： 例：生成最小代价二连通图 a) 按权重对所有边排序，生成最小连通子树（单连通图，权重和最小）； b) 然后按剩余边权重从小到大依次考虑边是否加入生成子图，判断准则是该边的两个端点还没有k条不相交的路径连通时，就把这条边加入生成子图； c）最后判定是否所有节点都达到k连通，如果不是则重复b步，否则算法结束。 例：生成最小代价二连通图

FGSS(续)

故障修复分类 基于连接的修复 部署k连通拓扑 非k连通图 基于覆盖的修复

非k连通图 (1/4) 网络维持k连通需要消耗大量资源，所以很难在大规模的网络中要达到k连通。在非k连通的网络中，需要有特定的方法来处理节点故障。 例：当上层节点发生故障，基站将不能收到下层节点的信息。

非k连通图 (2/4) 介绍一种基于重新路由建立的（动态）容错拓扑方法。 基本概念： 该拓扑方法要求基站有数据结构存储每个节点的邻居节点信息（包含邻居节点间的距离）。 WSNs中的节点被分为3个集合 R={WSNs中处于活动状态的节点，图例以白色节点表示} D={WSNs中失效的节点，图例以黑色节点表示} S={WSNs中由于上层节点失效无法与基站通信但仍有效能的节点，图例以灰色节点表示} Best R Neighbors：S集中离R集最近的节点（距离最近）。 （以相邻节点间的距离为衡量尺度） Best Base Station Neighbors：S集中离基站最近的节点（跳数最小）。 （以节点到基站的跳数为衡量尺度，因为多跳情况下节点到基站的传输距离很难得到，但以跳数为衡量尺度会导致两节点跳数少实际传输距离长的情况，屏蔽了两节点跳数多实际传输距离短的情况）

非k连通图 (3/4) 该方法中基站查询到从某个节点失效通信中断，将它的下层节点的下一跳重新定向到能与基站保持通信的最近节点，并给出了两中路由选择方案 Subdividing by Best R Neighbors Subdividing by Best Base Station Neighbors

非k连通图 (4/4) Subdividing by Best R Neighbors 算法步骤： a）将WSN节点划分到不同的集合。 b）依据基站存储的每个节点的邻居节点信息，每次从S集中寻找一个节点到某个R集的距离最近，将其从S划出归到R集。 c）最后判断S集是否为空，如果非空，则重复b步；否则为空，路由变更结束，基站广播更新后的路由信息到各节点。 优点：相邻节点的平均传输距离小，网络整体能耗小。 缺点：节点路由更新的信息量大。 Subdividing by Best Base Station Neighbors b）按找规定上层节点的路由重定向，其下层相连的子节点路由不再发生变化。所以依据基站存储的每个节点的邻居节点信息以及原有的路由信息，每次从S集中分层寻找到基站跳数最少的上层节点，然后将其及其下层子节点从S划出归到R集。 优点：节点路由更新的信息量小。 缺点：相邻节点的平均传输距离大，网络整体能耗大。

故障修复分类 基于连接的修复 部署k连通拓扑 非k连通图 基于覆盖的修复

基于覆盖的修复 无线传感器网络用来监测环境时，节点失效会造成某些区域不被覆盖，这时需要采取措施来弥补造成的覆盖空洞。可以在网络中部署一部分可以移动的节点，当其他节点失效时，这些冗余的节点就移动到某个区域以弥补失效节点对网络造成的影响。 覆盖的两个定义 注：当节点失效，节点的覆盖区域将变成遗漏区域

基于覆盖的修复(续) 覆盖修复过程：（假设网络中的节点具有移动能力） 1）初始化阶段：节点计算自己的覆盖区域、每个覆盖区域对应的移动区域。 2）恐慌请求阶段：垂死节点广播求助消息。 3）恐慌回应阶段：垂死节点的邻居收到求助消息后计算如果自己移动到垂死节点的移动区域，是否会影响到自身的覆盖区域，如果不影响则给求助节点返回消息。 4）决策阶段：垂死节点根据收到的回应信息，决定让哪个节点移动。 （以节点A失效为例，补图说明）

提纲 概述 故障模型 故障检测 故障修复 可靠性协议

可靠性协议 无线传感器网络在不同的抽象级别具有不同的容错技术 从网络各层次协议的角度，主要介绍物理层、链路层、网络层、传输层设计需要考虑的与容错相关的问题

可靠性协议 可靠性分析 物理层 链路层 网络层 传输层

物理层 物理层是实现无线网络通信的基石，其可靠性能的优劣直接影响到整个系统的容错能力。 物理层功能：负责数据的编码调制、解调解码、发送与接收。 设计考虑因素：WSNs中的通信，为了使得数据能够被可靠地传输或接收，必须要做到高的接收机灵敏度、低的背景噪声及较强的抗干扰能力。 设计实现方法：天线设计，增强信号强度；跳频扩频调制技术，增大传输带宽；CMOS工艺及软件无线电技术发展；采用自适应调制编码方式，提高可靠性及容错能力。

链路层 链路层功能：负责数据流的多路选择、数据帧侦测、媒介访问、差错控制。 设计考虑因素：保证点到点、点到多点的可靠性链接，并提供对共享媒介的公平、有效的访问。 设计实现方法：自动重发请求（ARQ）；前向纠错（FEC）。 1）ARQ:发送方在收到重发请求或超时没有收到接收方的确认时，会重发数据包。 （ 优点：可靠性强；缺点：数据可能多次发送，消耗能量。现在WSNs已很少使用） 2）FEC:要求编码器对信源产生的符号信息按照一定的规则加上冗余，即使接收方收到的数据包出现部分错误，它仍然能够通过冗余译码得到正确的信息。前向纠错既能检测错误，也能纠正一定数量错误。 （优点：减少数据多次重复发送，节约能量；缺点：需要编码译码设备，计算复杂）

网络层 网络层功能：负责源节点到汇聚节点的路由。 设计考虑因素：无线传感器节点容易失效，路由协议必须考虑容错性。 设计实现方法：多路径路由（包括局部多路径路由，泛洪等） 1）局部多路径路由：适用于路由路径可分主次的情况，当主路经上的节点失效时，可以选择备份的路径来消除故障节点的影响。 （优点：控制拥塞，节能；缺点：需要维护路由表） 2）泛洪：一类适用于路由路径不分主次的容错路由协议。消息到达目的地或到达最大允许跳数之前，每个节点都广播收到的消息，具有很高的容错性。 （优点：不需要维护路由表；缺点：发送大量冗余信息，造成通信链路拥塞，消耗大量能量）

网络层(续)

传输层 传输层功能：提供可靠的、低延迟、能量有效的、公平的信息传输。 设计考虑因素：信道损耗、干扰、带宽有限、突发通信、节点资源受限等。 设计实现方法：信息传输在不同方向的不同实现方法。 1）从传感器节点到汇聚节点的传输 事件区域感应：事件区域一般会有多个传感器节点感应到数据，而这些数据具有相似性，汇聚节点不是对单个节点的数据感兴趣，而是整个事件区域内感应节点所收集的信息，保证了感应/检测到事件特征而形成的数据流的可靠传输

传输层(续) 2）从汇聚节点到传感器节点的传输 汇聚节点到传感器节点传输的数据流通常较为重要，可能包含编程配置文件，应用相关的查询和指令（需要更高可靠性）。 PSFQ（Pump Slowly，Fetch Quickly）：发送节点低速向网络注入数据包以避免网络拥塞，接收节点有足够的时间来检测这些数据包是否丢失，假如发送丢失就请求重传。当节点收到的包序不等于上一个包序号加1，那么就认为有包丢失。这个节点在收到正确的包前停止继续发送包。（提供了接收端延迟，可靠传输） 例：节点B在没有收到2号包就收到了3号包，那么判断2号包丢失了，于是向A请求重发2号包。只有真正收到2号包后，节点B才继续向C发送包。

小结 本章首先介绍容错领域的基本概念和容错的重要性，然后分别从故障模型、故障检测、故障修复三个方面讲述了无线传感器网络的容错技术，最后分析了容错在无线传感器网络各个协议层次设计时需要考虑的因素。 由于无线传感器网络的特点，可靠性必定是需要考虑的关键因素之一，无线传感器网络的各个关键技术都必须考虑故障的存在，容错技术将是无线传感器网络需要重点考虑的技术之一。

参考文献 [1] 孙利民,李建中,陈渝,等. 无线传感器网络[M]. 北京:清华大学出版社,2005. [5]闵应骅.容错技术二十五年[J].计算机学报,1995,18(12):930-943. [6] 崔莉,鞠海玲,苗勇等. 无线传感器网络研究进展[J].计算机研究与发展,2005,42(1):163-174. [7] 陈颖文,徐明,虞万荣.无线传感器网络的容错问题与研究进展[J].计算机工程与科学,2008, 30(2):87-91. [8] Ning Li,Jennifer C.Hou . FLSS:A Fault-Tolerant Topology Control Algorithm for Wireless Networks .WSNA’04,Sept.26 Oct.1,2004,Philadelphia,Pennsylvania, USA. [9] Jessica Staddon,Dirk Balfanz,Glenn Durfee. Efficient Tracing of Failed Nodes in Sensor Networks . WSNA’02,Sept.28,2002.Atlanta,Georgia,USA.275-286. [10] Saurabh Ganeriwal,Aman Kansal,Mani B.Srivastava. Self Aware Actuation for Fault Repair in Sensor Networks .international Conference on Robotics d Automation New Orleans.LA April.2004:5244-5249.

谢谢！