【作者】 于磊磊；

【导师】 陈冬岩；

【作者基本信息】 山东大学 ， 控制理论与控制工程， 2014， 博士

【摘要】 因环境恶劣、能量受限和无线信道不可靠等特性,无线传感器网络经常出现节点损坏、通信链路中断等故障,使得数据传输的效率较低,难以满足实际的应用需求,因此容错(Fault Tolerance)能力是衡量无线传感器网络性能的一个重要指标。传统网络的容错技术由于没有综合无线传感器网络的上述特性,因而难以应用于无线传感器网络的实际。无线传感器网络的容错性是指当部分节点或链路失效后,能够进行传输数据的恢复或者网络结构自愈。当前对无线传感器网络的容错技术的研究主要集中在以下五个方面：硬件容错、覆盖容错、路由容错、事件容错和应用容错。其中,路由容错是无线传感器网络容错研究的基础和重点。多路径容错路由是路由容错的主要方式,相比于单路径路由机制,它在传输可靠性、均衡负载、容错恢复等方面具有明显的优势。但是,在多路径路由机制中,从源节点到目的节点的多条路径中可能包含公共节点(链路),公共节点(链路)的失效会造成多条路径的传输失败。而不相交多路径路由机制可以有效避免公共节点(链路)的出现,从而显著提升多路径路由的容错性能。不相交多路径容错路由机制面临的主要难题有三个：一是公共节点(链路)避免问题,即通过何种路径规划机制实现从源节点到目的节点的多条路径的不相交；二是不相交多路径选优问题,即在路径不相交的约束下,如何优化路径选择过程以达到节省能量和提高容错性能；三是节点移动带来的路径断裂问题,即在网络拓扑产生变化的情况下,如何以最小的代价实现不相交多路径的快速恢复。本文针对上述问题,基于数据冗余和路径冗余方法,对无线传感器网络的不相交多路径容错路由机制进行了研究。本文的研究主要立足于五个方面：(1)网络的多路径不相交约束模型；(2)中心计算方式的不相交多路径规划和维护机制；(3)分布式计算方式的不相交多路径规划和维护机制；(4)节点移动情况下的不相交多路径规划和维护机制；(5)有负载均衡要求情况下的不相交多路径规划和维护机制。本文取得的研究成果包括如下几个方面：1.中心计算的2-不相交路径容错路由算法：针对某些工业应用中网络拓扑比较稳定,sink节点运算存储能力较强等特点,利用全网信息计算出从源节点到sink节点的近似最优2-节点(链路)不相交路径,然后生成微路由表并下传到每个节点,采用中心调度的自适应机制提高路径维护的灵活性。2.面向不相交多路径的multi-routing tree拓扑结构：提出了一种面向不相交多路径的multi-routing tree拓扑结构,由一个唯一的根节点和一组特殊的子树构成。该组子树满足如下三个约束：一是任意子树都是点可相交的,二是任意子树都是边不相交的,三是连接任一节点与其子节点的边必属于同一子树。在该树结构下,从源节点沿不同子树到达根节点的路径是不相交的。3.基于1multi-routing tree的不相交多路径容错路由算法：采用集中式和分布式两种算法在网络中实现multi-routing tree,提出一种能量消耗与容错性能的平衡模型：定制冗余模型,为源数据实现三种模式的定制冗余：重发冗余、路径冗余和混合冗余。4.采用HSV色彩空间分离模型的不相交多路径容错路由算法：针对节点移动带来的路径断裂问题,采用HSV色彩空间模型为每条链路建立数值化的(h,s,v)三元组,并分离使其属于不同的色彩平面,按照不同色彩平面构造从源节点到目的节点的多条节点不相交路径,设计基于可变时间间隔链路接收信号强度指示值探测的不相交多路径维护机制。5.采用区域分割模型的不相交多路径容错路由算法：基于地理位置信息,将网络部署区域分割成若干组互不重叠的元区域链,使得源节点沿不同的元区域链可以生成到目的节点的多条不相交路径,通过化“移动节点”为“静止区域”的思想解决移动无线传感器网络的不相交多路径容错路由问题。6.基于路径代理的负载均衡不相交多路径容错路由算法：基于路径代理思想设计,根据“一个邻居一个路径代理服务,不同邻居不同路径代理服务”的路由选择原理,算法获得的从源节点到sink节点的多条路径是链路不相交的。提出了一种负载均衡模型,将数据流量均衡地覆盖到多条路径中,以延长网络生存期。更多还原

【Abstract】 Due to the poor deployment environment, limited energy, and unreliable wireless channel of sensor nodes, wireless sensor networks (WSN) often encounter some system failures, such as node failure and communication interrupt. These failures make the efficiency of data transmission is very low, and it is difficult to meet the application demands. The fault-tolerant technology of traditional networks did not consider the characteristics of WSN. So it is not suitable for practical usage scenarios of WSN. The fault tolerance of WSN is defined as the recovery of data transmission or the self-healing of network structure when some nodes or links fail. Current researches on fault-tolerant technology for WSN mainly focus on following five ways:fault tolerance in hardware, fault tolerance in deployment, fault tolerance in routing, fault tolerance in event and fault tolerance in application. The fault tolerance in routing is regarded as the basis and key priority of fault tolerance for WSN.Multipath fault-tolerant routing schemes are the primarily way to achieve the fault tolerance in routing. In WSN, multipath routing schemes have better performance in terms of reliability and load balance than traditional single-path routing schemes. But in multipath routing schemes, the multiple paths from the source node to the destination node may contain shared nodes (or shared links). The failures of shared nodes (or shared links) may lead to the interrupts of multiple paths. So the disjoint multipath routing schemes which do not cause shared nodes (or shared links) have gotten immense research interest due to its capability of providing high reliability and fault tolerance.The significant challenges which the disjoint multipath routing faces include three aspects. The first is the avoidance of shared nodes (or shared links), which means how the routing schemes build paths to achieve the disjoint constraints of multiple paths. The second is the optimization of the disjoint paths, which means how the routing schemes optimize the path finding to reach the target of saving energy and improving fault tolerance under the disjoint constraints. The third is the path breakage caused by mobile nodes, which means how to restore the disjoint paths when the network topology changes. Aiming at above challenges, based on the data redundancy method and the path redundancy method, we study the disjoint multipath fault-tolerant routing schemes for WSN in this thesis. The content of this thesis includes five issues:(1) Disjoint-constrained mode of the network;(2) Disjoint multipath routing schemes based on centralized calculating;(3) Disjoint multipath routing schemes distributed calculating;(4) Disjoint multipath routing schemes for mobile wireless sensor networks;(5) Disjoint multipath routing schemes for wireless sensor networks with load-balancing requirements.The contributions of this thesis include:1. Centralized calculating based2-disjoint multipath fault-tolerant routing algorithm. Considering certain industrial monitoring applications (for example, mine safety monitoring) which have relatively stable network topologies, based on the global information, the algorithm first calculates near to optimize2-node (link) disjoint paths from a source to the destination (sink) using the number of hops and the path quality as metrics, and generates a tiny routing table which is merely composed of the <master node, secondary node> couple and the path bit series. Then the tiny routing tables are disseminated to each sensor node along the generated paths. In order to improve the resilience of route maintenance, the algorithm designs a centralized adaptive path maintenance mechanism. In the data routing phase, packets are transmitted according to the path bit series carried in their heads, without any control overhead.2. Multi-routing tree topology structure for disjoint multiple paths. We proposed a multi-routing tree topology structure which has a number of node-joint but link-disjoint subtrees. The subtrees of multi-routing tree meet the following constraints:(1) they are node-joint, which means the nodes of a subtree may also belong to the others;(2) They are link-disjoint, which means the edges of a subtree must only belong to itself;(3) The edges that connect a node to its child nodes must only belong to the same subtree. Depending on the nature of multi-routing tree, paths along different subtrees are node-disjoint.3. Disjoint multipath fault-tolerant routing algorithm based on multi-routing tree. Based on the multi-routing tree, we design two algorithms to construct the multi-routing tree in the network. One is centralized algorithm and another is distributed algorithm. For the two algorithms, we also present a customized redundancy scheme to improve the reliability of data transmission. The scheme provides individualized data redundancy for each sensor node.4. Node-disjoint multipath fault-tolerant routing algorithm for MWSN based on HSV color space. Based on the HSV color space model, the algorithm creates a numeric (h, s, v) tuple for each link in the network and distributes these tuples into six basic planes in the color space, then it can find multiple node-disjoint paths within different basic color planes. It designs disjoint multipath routing maintenance mechanism based on variable intervals for mobile nodes link Received Signal Strength Indicator (RSSI) value detection, which is without any geographic location information.5. Node-disjoint multipath fault-tolerant routing algorithm for MWSN based on area partition. In the algorithm, we first partition the deployed area of the network into a number of non-overlapping meta-area chains, and then find a path from the source node to the destination node in each chain separately. We also introduce a dynamic next hop selection method which has two modes:distance-first mode and direction-first mode.6. Load-balanced and link-disjoint multipath fault-tolerant routing algorithm based on the path deputies. According to the principle "one neighbor one deputy service, different neighbors different deputy services", we present a link-disjoint multipath routing scheme based on the path deputies. Depending on the path-deputy scheme, the paths from a source node to the sink node are link-disjoint, and the total cost of all the link-disjoint paths from a node is very small. Then we develop a load balancing model to distribute the traffic over the multiple paths. The load balancing model can effectively prolong the network lifetime.更多还原