传感环境下基于局部Voronoi图的启发式反监控路径发现算法

Heuristic anti-monitoring path finding algorithm based on local Voronoi tessellation in sensory field

针对移动对象通过传感区域时的安全问题,提出了一种基于局部Voronoi图(VT)的启发式反监控路径发现算法。首先,给出了一种基于局部Voronoi图的路径暴露风险近似估算模型。在该模型中,移动目标可依据当前探测到的传感器节点位置信息动态生成局部Voronoi图,并可依据定义的暴露风险计算公式近似估算出局部Voronoi图中各条边所对应路径的暴露风险。然后,在此基础上设计并实现了一种启发式的反监控路径发现算法。在该算法中,移动目标可首先基于局部Voronoi图确定自己的下一跳位置点候选集,然后再基于定义的启发式代价函数从候选集中选择一个风险代价最小的位置点作为其下一跳目标位置点。最后,沿着局部Voronoi图中对应的最小暴露风险路径移动到该目标位置点。理论分析和实验结果表明,所提算法具有良好的反监控性能,针对部署有n个传感器节点的区域,能够使得移动对象在不超过O(n log n)的时间内快速找到一条具有较低暴露风险的路径来穿越整个传感区域。

Considering the safety problem of mobile objects while traversing through a sensory field, a novel heuristic anti-monitoring path finding algorithm based on local Voronoi Tessellation（ VT） was proposed in this paper. First, an approximate estimation model of path exposure based on local Voronoi tessellation was presented, in which, the mobile object could generate the local Voronoi tessellation dynamically based on currently detected sensor nodes information, and approximately estimated the exposure risk of each path corresponding to an edge of the local Voronoi tessellation based on the newly defined exposure risk computation formula. And then, based on the newly given exposure model, a novel heuristic antimonitoring path finding algorithm was designed, in which, the mobile object could firstly determine its candidate set of next hop location points based on the local Voronoi tessellation, and then selected a location point with the minimum risk cost from its candidate set as its actual next hop location based on the newly defined heuristic cost function, and therefore, moved along the corresponding path with the minimum exposure risk in the local Voronoi tessellation to the selected next hop location. The theoretical analysis and simulation results show that the proposed algorithm has good anti-monitoring performance, and as for a sensory field with total n sensor nodes, the mobile object can select a path with relatively small risk to get to the destination within the time no more than O（ n log n）.