摘要
当智能目标穿越敌方无线传感器网络的穿行时间受限时,现有基于广度优先搜索的穿越算法不能保证路径满足约束条件.为此,建立了一种穿越模型,并提出一种启发式的近似数值优化算法:k-shortest path-线性聚合启发式穿越路径算法(kSP-LAHTP).算法利用Voronoi图将连续路径问题域离散化,以曝露度和穿行时间为衡量指标,结合线性聚合的启发式路由机制,使目标实现满足时间约束值的最佳穿越.分析和实验结果表明:算法很好地解决了目标穿越时间受限情况下的穿越问题;且随系数k的增加,算法搜索路径更接近实际最佳.
Most wireless sensor networks（WSN） are deployed to monitor a region of interest for any intruding target.On the contrary,the intelligent target looks for the optimal path to traverse the enemy sensor networks for avoiding being detected.However,the target may be subject to traversal time constraint.It is difficult for most existing traversal algorithms based on breadth-first-search to satisfy a pre-determined time constraint value.Motivated by this reason,a traversal model is constructed and an approximately optimization algorithm is proposed in this paper.The algorithm makes the continuous path problem domain a discrete one by Voronoi diagram.Using exposure and traversal time as the path performance metric,the algorithm combines the linear aggregated routing mechanism to find the optimal path.It enables the intelligent target to traverse the enemy sensor networks field.And the traversal time from the source to the destination is less than a given threshold.Theoretically and experimentally,it is concluded that the proposed algorithm is able to solve the traversal path problem with time constraint.The k shortest path heuristic traversal path algorithm based on linear aggregation（kSP-LAHTP） is able to find a traversal path closer to the optimum with parameter k increasing.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2010年第11期1919-1927,共9页
Journal of Computer Research and Development
基金
湖南省科技计划基金项目(2009FJ3083)~~
关键词
感知模型
曝露度
穿越时间
时间约束最小曝露路径
启发式穿越路径算法
sensing model
exposure
traversal time
minimal exposure path with time constraint
heuristic traversal path algorithm
