复杂场景下移动多Sink节点巡航路径规划问题研究

项目名称： 复杂场景下移动多Sink节点巡航路径规划问题研究

项目编号： No.61300034

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 谷雨

作者单位： 合肥工业大学

项目金额： 25万元

中文摘要： 探索复杂环境下多Sink节点巡航路径规划模型与方法，对由此引出的理论问题及关键技术开展深入研究。首先突破传统静态网络模型在刻画事件能力上的局限性，通过时间轴扩展方法，将静态模型扩展成动态网络模型，并利用事件发生的区域性，精确还原网络上发生的事件。进一步的，利用隐式Markov模型，赋予此动态模型一定程度的预测能力。在此基础上，引入网络流理论，对多Sink节点巡航路径规划问题进行优化建模，以单Sink调度模型为基础，通过循序渐进的方式添加实际系统中的限制条件，从而得到贴近实际系统需求的优化方程。最后，引入Column Generation计算方法，对优化方程进行分割迭代求解，突破基础CG方法在计算复杂度方面的制约，将松弛算法机制引入现有CG迭代框架，创建一种新型的、具有在线调度能力的分布式多Sink路径规划算法，以稳健的适应复杂环境下事件与网络的动态变化，实现对多Sink 实时、有效的调度。

中文关键词： 无线传感器网络；热点问题；动态网络模型；列生成算法；动态预测模型

英文摘要： This project intends to explore the path planning model for mobile sinks in real-world wireless sensor systems under complex circumstances, with the objective of tackling its theoretic problems and key technologies. Firstly, it breakthroughs the limitation of traditional static networks in its ability of depicting events. Through the idea of the time expansion, the static model will be expanded into a dynamic network model. With its occurrence of the regional, the events on the network will be recovered. Moreover, Hidden Markov model endows a certain prediction ability of this dynamic model. Meanwhile, based on the Network Flow theory, we formally formulaize the problem of the multiple sink node cruising path planning. Based on the single-sink scheduling model, it adds the restriction of the actual system gradually in order to get close to the actual system requirements of the optimization equation. Finally, the Column Generation method segments and solves the optimization. This method not only breakthroughs the restriction of the basic CG method in computational complexity, but also the relaxation algorithm is introduced into the existing CG iterative framework in order to create a new distributed sink path algorithm, which is capable of online scheduling.The proposed scheduling algorithm should have a stable

英文关键词： Wireless Sensor Networks；Hopspot issue；Dynamic network model；Column generation；Dynamic Prediciton Model