复杂场景下移动多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 performance in complex situations, well adapt to dynamic network events and be able to schedule multiple mobile sinks effectively in a real-time manner.

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

传统无线传感器研究中，“静态”为其主要特征，这在带来硬件设计的简约与便利的同时，也带来了一些难以解决的基础限制，如热点问题。针对“静态”传感器网络的局限，本课题引入可移动基站思想加以解决。主要研究内容由以下三个方面构成：1）动态网络模型研究。提出了一个包容动态因素的网络模型，对网络中已发生事件进行还原，以及对未来可能发生事件进行预测。2）离线多Sink路径规划算法研究。针对离线情况，基于动态网络模型，利用网络中已发生事件的相关数据，在每个节点各个时刻数据流量已知的情况下，利用网络流模型，根据网络对数据的延迟需求、实际物理世界对可用路径限制等制约下，以提高网络容量、延伸网络的生命周期为目标而建立相应的数学优化模型。由于该优化模型是一个大规模的整形非线性优化，基于列生成算法对该模型进行迭代求解。3）在线多Sink路径规划研究。离线情况下，可以通过后验的方式得到所需网络各变量，从而建立统一优化方程就行解析。而在线情况下，该条件并不具备。因此，通过对历史数据的挖掘，建立一个基于Markov模型的事件预测模型，利用基于物理世界中同一地点、不同时间发生的事件有一定的关联性这一特性，进行在线路径规划，以提高规划效率。. 本课题突破了传统静态网络模型在刻画事件能力的局限性，建立了具有一定预测能力的动态网络模型，此为本课题在网络模型层面的研究意义。本课题通过建立普适多目标凸优化模型，对热点问题进行细化，提出了贴近实用的多Sink节点循环路径规划算法，此为本课题在新问题领域层面的研究意义。此外，本课题突破基础Column-generation算法在计算复杂度方面的制约，将松弛算法机制引入现有的Column-generation算法优化框架之中，提出一种新的具有自适应、低复杂度特性的Column-generation计算框架，此为本课题在数学优化方法层面的研究意义。. 基于以上研究工作，发表论文杂志论文6篇，会议论文4篇，发明专利2项。其中第一作者JCR1区杂志一篇，CCF C类会议2篇。