自动化学报2016，Vol.42Issue(8)：1185-1197,13.DOI:10.16383/j.aas.2016.c150794
基于维诺图和二分图的水面移动基站路径规划方法
A Path Planning Method for Water Surface Mobile Sink Based on Voronoi Diagram and Bipartite Graph
摘要
Abstract
In surface sensor networks with sparsely deployed sensors, the distance between sensors is usually larger than the communication radius of sensors. So, it is difficult for sensors to gather their data by multi-hop routing. At present, an effective data gathering method is to use a mobile sink travelling in the network, and the path planning for the mobile sink becomes a key problem. In this paper, a path planning method based on Voronoi diagram and bipartite graph is proposed. Firstly, the data gathering “candidate vertexes” are generated using the Voronoi diagram theory. Secondly, a bipartite graph is constructed to describe the dominating relationship between candidate vertexes and sensors, and the “minimum effective dominating set”, which includes the least candidate vertexes gathering all sensors data, can be computed by dominating set theory. Lastly, the optimal path is formed based on the minimum effective dominating set. Extensive experiments have demonstrated that the proposed method can effectively plan the path for mobile sink to gather all sensors0 data with advantages such as short path, high energy efficiency, and balanced energy consumption among sensors.关键词
水面传感器网络/移动基站/路径规划/维诺图/二分图/支配集Key words
Surface sensor networks (SSNs)/mobile sink (MS)/path planning/Voronoi diagram/bipartite graph/dom-inating set引用本文复制引用
夏娜,束强,赵青,伊君..基于维诺图和二分图的水面移动基站路径规划方法[J].自动化学报,2016,42(8):1185-1197,13.基金项目
国家自然科学基金(61100211,61003307),教育部新世纪优秀人才支持计划(NCET-13-0768),安徽省杰出青年科学基金(1408085J05)资助 （61100211,61003307）
