基于禁忌搜索算法的AUV动态路径规划策略

Strategy of dynamic path planning based on tabu search algorithm for AUV

为有效提高水下传感器网络中未知节点的定位效率并降低网络能耗,提出一种改进禁忌搜索算法的Autonomous Underwater Vehicle(AUV)动态路径规划策略.所提出的算法和策略,采用六边形部署算法,寻找合适的虚拟锚节点位置,以达到最佳覆盖效果;然后通过在AUV节点上配置定向天线,获取未知节点方位信息;再次,利用改进的禁忌搜索算法,选定AUV节点下一步目标虚拟锚节点,引导AUV节点移动.该文通过改进的禁忌搜索算法设置两个禁忌集,防止AUV节点重复搜索,并辅助AUV节点移动方向判定,保证未知节点的定位覆盖率.为验证所提策略有效性,对所提该策略和静态路径规划算法中的典型算法Scan算法进行对比分析计算.仿真表明,基于禁忌搜索算法的AUV动态路径规划策略较Scan算法移动路径长度明显减少,虚拟锚节点数目有所降低,能有效降低能耗,延长网络寿命.同时,由于Received Signal Strength Indicator(RSSI)测距法存在误差,误差值设置为虚拟锚节点到未知节点的真实距离的10%,仿真得出基于禁忌搜索算法的AUV动态路径规划策略较Scan算法,定位精度有所提高.

The purpose of the strategy of dynamic path planning for Autonomous Underwater Vehicle（AUV）is to improve the positioning efficiency of the unknown node in underwater sensor networks and decrease the energy consumption.Firstly,the location of the potential virtual anchor nodes is determined based on the hexagonal deployment algorithm.Then,directional antenna is installed on the AUV node in order to acquire the location information of unknown nodes.Thus,improved tabu search algorithm is used to select the next virtual anchor node for AUV node to remove.Two tabu sets are set in improved tabu search algorithm to prevent repeated search and to assist in determining the direction of AUV node＇s movement.Meanwhile,the tabu sets can ensure the positioning coverage of unknown nodes.Finally,the received information of virtual anchor node is used by unknown nodes to determine their own location.In order to check the accuracy of the result,this strategy is analyzed and compared with scan algorithm by employing Matlab.The scan algorithm is typical algorithm in static path planning algorithm.The simulationshows that the energy consumption is reduced compared with the strategy of dynamic path planning for AUV and the scan algorithm.On the one hand,length of moving path is decreased obviously in the strategy of dynamic path planning for AUV.On the other hand,the number of virtual anchor nodes is reduced in this strategy.Meanwhile,the error value of Received Signal Strength Indicator（RSSI）ranging method is nearly proportional to the real distance between the virtual anchor node and unknown node.The error value is set less than 10% of the real distance.Compared with the strategy of dynamic path planning for AUV and the scan algorithm,the result shows that the positioning accuracy is improved in this strategy.