无线传感器网络不相交多路径容错路由研究

发布时间：2018-01-18 15:50

本文关键词：无线传感器网络不相交多路径容错路由研究　出处：《山东大学》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]:Because of bad environment, energy is limited and unreliable wireless channel characteristics of wireless sensor network nodes often damaged, communication interruption link fault, the data transmission efficiency is low, it is difficult to meet the needs of practical applications, so the fault tolerance ability (Fault Tolerance) is an important index to measure the performance of wireless sensor networks in traditional network. Because of the characteristics of fault-tolerant technology without integrated wireless sensor network, the actual and difficult to be applied to wireless sensor network. The fault tolerance in wireless sensor networks is when some nodes or links fail, can be restored or self-healing network structure of data transmission. The current research on wireless sensor network fault-tolerant technology mainly focus on the following five aspects: hardware fault coverage, fault tolerance, fault tolerant routing, fault tolerance and fault tolerant event application. Among them, Lu Yourong is wrong in wireless The foundation and emphasis of fault tolerance research on sensor networks.
Multi path routing fault-tolerant routing is the main way of fault tolerance, compared to single path routing mechanism, its load balancing in transmission reliability, fault tolerance, and other aspects of recovery has obvious advantages. However, in the multi path routing mechanism, multiple paths from the source node to the destination node may contain a common node (link), public node (link) transmission failure creates multiple paths fail. And disjoint multipath routing mechanism can effectively avoid the common node (link) appears to significantly enhance the fault-tolerant performance of multipath routing.
The main problem facing the disjoint multi path fault tolerant routing mechanism has three: one is the public node (link) to avoid problems, through which path planning mechanism to realize multiple paths from the source node to the destination node disjoint; two is disjoint multi path selection problem, namely in disjoint path constraints and how to optimize the path selection process to save energy and improve the fault tolerance performance; three is the problem of path breakage caused by the movement of nodes, which produce changes in the network topology, how to minimize the cost to achieve rapid recovery of disjoint multipath. Aiming at the above problems, data redundancy and path redundancy method based on wireless sensor network disjoint multipath routing mechanism was studied in this paper. The research is mainly based on five aspects: (1) multi path disjoint constraint model; (2) center Is the disjoint multi path planning and maintenance mechanism; (3) distributed computing disjoint multi path planning and maintenance mechanism; (4) under the condition of the mobile node disjoint multi path planning and maintenance mechanism; (5) the load balancing requirements under disjoint multipath planning and maintenance mechanism. The research results of this paper are as follows:
1. center calculation 2- disjoint path fault tolerant routing algorithm for network topology is relatively stable in some industrial applications, the sink node computing and storage ability etc., utilization of the network information to calculate the approximate optimal 2- node from source node to the sink node (link) disjoint paths, and then generate micro routing table and to each node, using the adaptive mechanism of center scheduling path to improve maintenance flexibility.
Multi-routing tree topology for 2. disjoint paths: multi-routing tree proposed a topology for disjoint paths, consisting of only one root node and a special set of subtrees. The group subtree satisfies the following three constraints: one is the arbitrary subtrees are point of intersection, two arbitrary subtrees are edge disjoint, three is connected to any node and child nodes need to belong to the same tree. In the tree structure, from the source node along the path to the root nodes in different subtrees are disjoint.
3. disjoint path fault tolerant routing algorithm 1multi-routing based on tree: the centralized and distributed two algorithms multi-routing tree in the network, a model is proposed to balance the energy consumption and the fault-tolerant performance: Custom redundant models, as the data source to achieve customized redundancy in three modes: redundant retransmission, path redundancy and mixed redundancy.
Disjoint path routing algorithm using 4. HSV color space separation model: the problem of path for fracture caused by the movement of nodes, a numerical value for each link using the HSV color space model (h, s, V) three tuple, and that the separation of different colors belong to the plane, according to the different color plane constructed from a node in the source node to the destination node disjoint paths, the design variable time interval link received signal strength indication value detection mechanism based on disjoint path maintenance.
Using 5. disjoint multipath fault-tolerant routing algorithm segmentation model: Based on geographical location information, the network deployment area is divided into several groups of non overlapping area chain, so that the source node along different element area chain to the destination node can generate multiple disjoint paths, through the "mobile node" mobile solution wireless sensor network disjoint multipath fault-tolerant routing problem as "static" thoughts.
6. load balancing proxy path disjoint multipath routing algorithm based on path fault tolerance design based on agent, "according to a neighbor a path different neighbor proxy service, different path routing agent service" principle, the algorithm obtains multiple paths from the source node to the sink node is disjoint. This paper presents a load balancing model, data flow and balanced coverage to more paths, to prolong the network lifetime.

【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN929.5;TP212.9

【参考文献】