基于网络流的图像传感器网络路径优化问题研究

发布时间：2018-01-15 16:13

本文关键词：基于网络流的图像传感器网络路径优化问题研究　出处：《扬州大学》2017年硕士论文　论文类型：学位论文

【摘要】：本文首先简要论述了无线图像传感器网络的一些背景知识如无线传感器网络的特点、网络结构以及与之相关的性能评估。分析了无线图像传感器网络这一特定类型的传感器网络系统的特点,对此进行了分析与介绍。在基于图像的无线传感器网络中,由于采集的图像文件的特点,这对传感器网络数据输送链路带宽提出了较高的要求。此外,因为无线传感器网络节点的能量是有限的,并且大规模随机部署的数据采集设备很难进行电量的补充,因而传感器网络的生命周期是有限的。在无线图像传感器网络中,保证整个网络的传输链路带宽以及最大化的延长网络的生命周期是当前亟待解决的两个问题。本文研究了传感器网络路由规划相关的问题,分析了不同的路由规划与传输链路带宽以及生命周期之间的关系。在对基于无线传感器网络转化而成的图的最大流问题研究的基础上,本文提出了一种新的流分解算法。算法针对多目标问题进行传输路径的优化分配,在将传感器网络对应的有向图转化成流网络之后,使用网络最大流算法求解出整个网络的最大流。接着在求解得出的网络最大流的基础上,使用流分解算法将最大流分解成一组可以覆盖目标的节点邻接路径组成的集合,从而保证传感器网络中数据传输对于链路带宽的需求。此外,文中证明了有向图对应的流网络是k-平衡的,从而可以求解出流网络的最大k-平衡流。以此为基础,本文提出了一种k-平衡流分解算法将网络流分解成一系列节点邻接的路径组成的集合,保证了整个传感器网络的生命周期最大化。在文章的最后通过相关的实验仿真,在与传统算法对比后验证了文章中提出的相关算法的有效性。论文的主要工作如下:1、分析了目前的无线传感器网络的基础结构、体系特点以及目前的传感器网络存在的问题,并针对图像传感器这一特定类型的数据感知设备具有的特性进行针对性的研究,包含数据传输分析以及传感器生命周期分析。2、针对图像传感器网络传输数据量大及监测目标数目多的特点,本文将传感器网络链路带宽问题转化成图论中的网络流问题,在网络最大流的基础上提出了一种流分解算法从而将网络流分解成一组覆盖各目标的节点邻接的路径,以此很好地保证了各目标的可用链路带宽。3、针对传感器网络生命周期有限这一问题进行了针对性的研究,将网络生命周期最大化问题转化成流网络中的最大k-平衡流问题进行求解。在网络k-平衡流的基础上,给出了一个k-平衡流分解算法将最大k-平衡流进行充分的分解并转化成多组节点邻接的路径,每组路径可以独立的进行目标的监测与数据传输任务。通过实验可以证明,给出的k-平衡流分解算法可以将网络流完全的分解,证明了算法的可行性。
[Abstract]:Firstly, this paper briefly discusses some background knowledge of wireless image sensor networks, such as the characteristics of wireless sensor networks. Network structure and related performance evaluation. The characteristics of wireless image sensor network (WSN), a specific type of sensor network system, are analyzed. In the image-based wireless sensor network, due to the characteristics of the collected image files, it puts forward a higher requirement for the bandwidth of the sensor network data transmission link. Because the energy of wireless sensor network nodes is limited, and large-scale random deployment of data acquisition equipment is difficult to supplement the power. Therefore, the lifetime of sensor networks is limited. There are two problems that need to be solved urgently to ensure the transmission link bandwidth of the whole network and to maximize the lifetime of the network. In this paper, some problems related to the routing planning of sensor networks are studied. The relationship between different routing planning and transmission link bandwidth and life cycle is analyzed. Based on the research of the maximum flow problem based on the transformed graph of wireless sensor network (WSN). In this paper, a new flow decomposition algorithm is proposed. The algorithm optimizes the transmission path allocation for the multi-objective problem, after transforming the corresponding directed graph of the sensor network into a flow network. The maximum flow of the whole network is solved by using the algorithm of the maximum flow of the network, and then the maximum flow of the network is solved on the basis of the solution. Using the flow decomposition algorithm to decompose the maximum flow into a set of adjacent paths of nodes that can cover the target, so as to ensure the demand of link bandwidth for data transmission in sensor networks. In this paper, it is proved that the flow network corresponding to the directed graph is k- equilibrium, so that the maximum k-equilibrium flow of the outgoing flow network can be solved. In this paper, a k- equilibrium flow decomposition algorithm is proposed to decompose the network flow into a set of paths adjacent to a series of nodes. Ensure the maximum lifetime of the whole sensor network. At the end of the article through the relevant experimental simulation. After comparing with the traditional algorithms, the effectiveness of the proposed algorithm is verified. The main work of this paper is as follows: 1, the basic structure of wireless sensor networks is analyzed. The characteristics of the system and the problems existing in the current sensor network, and the image sensor, a specific type of data sensing device has the characteristics of targeted research. Including data transmission analysis and sensor life cycle analysis. 2. Aiming at the large amount of data transmitted by image sensor network and the large number of monitoring targets. In this paper, the link bandwidth problem in sensor networks is transformed into the network flow problem in graph theory. On the basis of the maximum flow in the network, a flow decomposition algorithm is proposed to decompose the network flow into a set of adjacent paths of nodes covering each target, so that the available link bandwidth of each target is guaranteed very well. Aiming at the problem of limited lifetime of sensor networks, a targeted study has been carried out. The life cycle maximization problem of the network is transformed into the maximum k-equilibrium flow problem in the flow network, and the solution is based on the k-equilibrium flow of the network. In this paper, a k- equilibrium flow decomposition algorithm is proposed to decompose the maximum k-equilibrium flow sufficiently and transform it into a path adjacent to multiple groups of nodes. Each group of paths can independently monitor the target and transmit data. It can be proved by experiments that the k- equilibrium flow decomposition algorithm can completely decompose the network flow and prove the feasibility of the algorithm.
【学位授予单位】：扬州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP212.9;TN919.8

【相似文献】