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

摘要

本文首先简要论述了无线图像传感器网络的一些背景知识如无线传感器网络的特点、网络结构以及与之相关的性能评估。分析了无线图像传感器网络这一特定类型的传感器网络系统的特点，对此进行了分析与介绍。在基于图像的无线传感器网络中，由于采集的图像文件的特点，这对传感器网络数据输送链路带宽提出了较高的要求。此外，因为无线传感器网络节点的能量是有限的，并且大规模随机部署的数据采集设备很难进行电量的补充，因而传感器网络的生命周期是有限的。在无线图像传感器网络中，保证整个网络的传输链路带宽以及最大化的延长网络的生命周期是当前亟待解决的两个问题。
　　本文研究了传感器网络路由规划相关的问题，分析了不同的路由规划与传输链路带宽以及生命周期之间的关系。在对基于无线传感器网络转化而成的图的最大流问题研究的基础上，本文提出了一种新的流分解算法。算法针对多目标问题进行传输路径的优化分配，在将传感器网络对应的有向图转化成流网络之后，使用网络最大流算法求解出整个网络的最大流。接着在求解得出的网络最大流的基础上，使用流分解算法将最大流分解成一组可以覆盖目标的节点邻接路径组成的集合，从而保证传感器网络中数据传输对于链路带宽的需求。此外，文中证明了有向图对应的流网络是k-平衡的，从而可以求解出流网络的最大k-平衡流。以此为基础，本文提出了一种k-平衡流分解算法将网络流分解成一系列节点邻接的路径组成的集合，保证了整个传感器网络的生命周期最大化。在文章的最后通过相关的实验仿真，在与传统算法对比后验证了文章中提出的相关算法的有效性。论文的主要工作如下:
　　1、分析了目前的无线传感器网络的基础结构、体系特点以及目前的传感器网络存在的问题，并针对图像传感器这一特定类型的数据感知设备具有的特性进行针对性的研究，包含数据传输分析以及传感器生命周期分析。
　　2、针对图像传感器网络传输数据量大及监测目标数目多的特点，本文将传感器网络链路带宽问题转化成图论中的网络流问题，在网络最大流的基础上提出了一种流分解算法从而将网络流分解成一组覆盖各目标的节点邻接的路径，以此很好地保证了各目标的可用链路带宽。
　　3、针对传感器网络生命周期有限这一问题进行了针对性的研究，将网络生命周期最大化问题转化成流网络中的最大k-平衡流问题进行求解。在网络k-平衡流的基础上，给出了一个k-平衡流分解算法将最大k-平衡流进行充分的分解并转化成多组节点邻接的路径，每组路径可以独立的进行目标的监测与数据传输任务。通过实验可以证明，给出的k-平衡流分解算法可以将网络流完全的分解，证明了算法的可行性。

目录

摘要

第一章 绪论

1．1 研究背景及目的

1．2 国内外研究现状

1．3 无线图像传感器网络的应用

1．4 本文的主要创新之处

1．5 论文的主要内容及结构安排

第二章 无线图像传感器网络及图模型

2．1 无线传感器网络简介

2．2 无线传感器网络的发展历史

2．3 现代无线传感器网络的特点

2．4 无线图像传感器结构

2．4．1 无线图像传感器网络体系结构

2．4．2 无线图像传感器节点结构

2．5 无线图像传感器路由设计的挑战

2．6 图论相关知识

2．6．1、传感器网络图模型

2．7 无线传感器网络能量优化

2．8 本章小结

第三章 传感器网络数据传输带宽最大化问题

3．1 问题定义

3．1．1 图与流网络的转换

3．2 无线传感器网络路由策略

3．3 网络最大流算法分析

3．3．2 Edmonds-Karp修正算法

3．4 多目标的数据传输问题

3．4．1 网络最大流问题

3．4．2 一种改进的求解最大流算法

3．4．3 流分解算法

第四章 多目标监测生命周期最大化问题

4．1 问题定义

4．1．1 通信模型

4．2 FDSSP-NUE算法分析

4．3 目标数为k的图像传输问题(k>1)

4．3．1 流分解算法

4．3．2 k-平衡流的分解

4．3．3 寻找一组k-覆盖

第五章 实验仿真

5．1 链路带宽优化实验仿真

5．1．1 单目标时算法性能分析

5．1．2 多目标时算法的性能分析

5．2 生命周期实验仿真

5．2．1 单目标时算法的性能分析

5．2．2 多目标时算法性能分析

第六章 总结和展望

6．1 论文工作总结

6．2 未来的展望

参考文献

致谢

个人简历、在学期间发表的论文与研究成果

声明