公路传感器网络中面向可靠性的最优生命期节点调度理论与算法研究

Road sensor networks are wireless sensor networks utilized to monitor roads. It is expected to be widely used for massive scale highway monitoring. Aiming at the two key aspects in real application, reliability and lifetime of road sensor networks, this project theoretically analyzes and studies sensor scheduling schemes to maximize the lifetime of road sensor networks while considering its reliability requirements. In addition, a novel energy efficient distributed sensor scheduling algorithm is explored in this project. Firstly, with the objective of maximizing the lifetime of road sensor networks while considering the reliability requirements to ensure both the network connectivity and the accuracy of vehicle detection applications, this project transforms the reliability requirements to multi-coverage constraints over both horizontal and vertical directions, and models the scheduling problem to optimization problems on graphs. Then, this project proposes optimal scheduling algorithms satisfying multi-coverage constraints over both horizontal and vertical directions based on network flow optimization algorithms, flow decomposition and graph transformation techniques. Finally, focusing on the features of massive scale for road sensor networks, the project studies efficient distributed algorithms for applications of road sensor networks with massive scale based on the optimal scheduling algorithm. The expected scheduling theories and algorithms will further promote practical applications for road sensor networks.

公路传感器网络通过部署无线传感器网络来对道路进行监控，在大规模高速公路监控领域有着广泛的应用前景。针对公路传感器网络的可靠性和生命期这两个实际应用中的关键因素，本项目以公路传感器网络的可靠性为切入点，对网络的最优生命期节点调度方法进行理论分析和研究，并探索实用性强、能量高效的分布式节点调度算法。首先, 以最优生命期为目标，综合考虑网络连接和车辆监测应用的可靠性要求，研究将可靠性要求转化为图上横向和纵向上的多重覆盖约束，从而建模并抽象问题为图的优化问题；其次，研究横向和纵向上多重覆盖约束下图的网络流优化算法、流分解方法和图转换技术，提出基于图优化的满足多重覆盖约束的最优调度算法；最后，针对网络大规模分布的特性，在最优调度算法的基础上，研究适用于大规模应用的高效分布式算法。本项目预期形成的调度理论和调度算法将进一步推动公路传感器网络走向实际应用。

本研究综合考虑了公路传感器网络可靠性、生命周期以及面向公路交通管理的预测和调度的需求，围绕公路传感器网络的实际需求，以实现网络连接可靠性和对车辆监控的无遗漏检测，研究以最优生命期和最优交通流量吞吐量为目标的节点调度方法，探索适用于公路传感器网络且面向实际应用的调度算法，重点解决计算网络最优生命期、以及求解能实现最优生命期的节点调度方案中所涉及到的关键技术，设计保证公路传感器网络可靠性和实用性的传感器协同调度算法。针对以上研究目标和研究内容，本研究将按照从问题建模优化出发、提出理论最优算法、进一步研究适用于实际应用的算法这一研究思路展开。首先根据公路传感器网络的特点，对满足可靠性的最优生命期调度问题建模，将问题转换为横向和纵向覆盖约束下的图中网络流优化问题，同时通过图论理论来保证问题转换的正确性；其次，研究和设计满足横向和纵向上一重覆盖的最优化调度算法，包括横向和纵向上一重覆盖约束下的最大流算法，以及对应的流分解方法和理论，在此基础上设计能实现最优生命期的调度算法；接下来，创建图转换技术，将横向和纵向上多重覆盖约束下的最优化调度问题转换为一重覆盖约束下的最优化调度问题，建立横向和纵向上多重覆盖约束下的流分解理论，并应用于寻找最终调度方案的算法设计；然后以集中式算法为基础，拓展已有的分布式网络流设计思路和框架，以分布式方式实现流方向控制和满足多重覆盖的约束要求，从而设计能量高效的分布式调度算法，从而推进其在实际中的应用。