关键词: 传感器网络, Voronoi图, 反监控, 启发式算法, 暴露风险

Abstract:

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 anti-monitoring 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).

Key words: sensor network, Voronoi Tessellation (VT), anti-monitoring, heuristic algorithm, exposure risk