论文总字数：28156字

摘 要

公路传感器网络指使用大量无线传感器全面监控道路状况构成的无线传感器网络。因电池供电对无线传感器的能量约束，如何合理的调度传感器节点，实现公路传感器网络最优生命期，是公路传感器网络研究中的一个重要问题。此外，实际应用中，公路监控需要覆盖整个公路监测区域，从而确保通过监测区域的车辆无遗漏的被检测。所以，保证公路传感器网络检测的可靠性是另一个急需解决的重要问题。

已有研究通过将一段公路抽象成一条长线段并利用图优化理论求解满足覆盖约束条件的公路传感器网络的最优生命期。但是，这一理论抽象不符合现实中公路是有一定宽度的条带状的实际情况。因此，为满足公路传感器网络的可靠性，本论文首先研究构建反应公路横向和纵向覆盖关系的区间覆盖图，抽象建模该问题为满足横向和纵向覆盖约束的最优化调度问题；其次，通过创建反映方向的辅助节点和建立保证流方向的图组件，构造转换区间覆盖图为满足流映射要求的辅助图，从而转换该问题为区间覆盖图上的图优化理论问题；最后，应用线性优化方法求解横向和纵向覆盖约束下的最优生命期，并通过流分解方法对结果中的传感器节点进行流分解，从而给出实现公路传感器网络中面向可靠性的高效的生命期节点调度算法。

关键词：最大流；公路传感器网络；无线传感器网络

Research on Theory and Algorithm of Optimal Lifetime Node Scheduling for Reliability in Roadside Sensor Networks

ABSTRACT

Roadside sensor network refers to a wireless sensor network composed of a large number of wireless sensors to comprehensively monitor road conditions. With limited energy of battery-driven sensors, a challenging problem is to study how to reasonably schedule the sensor nodes and achieve the optimal sensor network lifetime. In addition, highway monitoring needs to cover the entire highway monitoring area to ensure that vehicles passing through the monitoring area are not missed in practical applications. Therefore, ensuring the reliability of roadside sensor network detection is another important problem that needs to be solved urgently.

Existing researches have solved the optimal lifetime of roadside sensor networks satisfying the coverage constraints by abstracting a section of highway into a long line and using graph optimization theory. However, highways look like strips with a certain width in reality. Therefore, in order to meet the reliability of roadside sensor networks, this paper first studies the construction of interval coverage maps that reflect the horizontal and vertical coverage of highways. We convert this problem to an optimal scheduling problem that meets the horizontal and vertical coverage conditions. Secondly, we convert the interval coverage map to an auxiliary graph that meets the flow mapping requirements by creating auxiliary nodes that reflect the direction and graph components that guarantee the direction of the flow, and thus convert the problem into a graph optimization theory problem on the interval coverage map. Finally, we apply a linear optimization method to solve the optimal life time, and use the maximum flow decomposition method to decompose the resulting flow. Thus, we will get an efficient life-time node scheduling algorithm for reliability in roadside sensor networks.

Keywords: Maximum flow，roadside sensor network，wireless sensor network

目 录

摘 要 I

ABSTRACT II

第一章 绪论 1

1.1 选题背景 1

1.2 课题研究现状 2

1.3 研究内容 2

1.4 论文结构 3

第二章 相关工作与理论基础 4

2.1 相关工作 4

2.2 理论基础 5

2.2.1 流网络 5

2.2.2 一般最大网络流优化流问题 6

2.2.3 图改造技术 7

2.2.4 路由流 10

2.2.5 图转换技术 12

第三章 面向可靠性的最优生命周期算法研究 13

3.1 公路传感器部署图到横纵区间覆盖图的映射 13

3.1.1 横向区间覆盖图的映射 13

3.1.2 横纵区间覆盖图的映射 15

3.2 公路传感器流网络图的构造 25

3.3 面向一重横向和纵向覆盖约束的最优生命期调度优化研究 26

3.3.1 流网络图到二维元组图 26

3.3.2 面向一重覆盖最优生命周期优化算法的研究 30

3.4 一重覆盖的传感器节点调度方案研究 31

第四章 算法评估与总结 33

4.1 算法评估与总结 33

4.1.1 算法评估 33

4.1.2 算法总结与未来展望 35

参考文献 36

致 谢 39

第一章 绪论

1.1 选题背景

近年来，国内道路交通建设随着经济的持续发展也取得了飞速的进步。在道路建设中，考虑到交通安全、道路维护等多种因素，监控道路状况是必不可少的。目前监测道路情况的方法多是沿交通道路设置视频监控点。在城市交通网络中，设置大量视频监控点，留存的视频信息可以通过利用计算机视觉等技术及时抓取车辆信息为交通流量统计及交通控制提供数据支撑，另外设置大量视频监控点也为破解刑侦案件、维护社会和平提供了数据保障。

请支付后下载全文，论文总字数：28156字