动态Voronoi图在战场区域穿越中的应用

李前进，王希武，林克成 王寅龙

（军械工程学院计算机工程系，河北 石家庄 050003）

摘要：现代战场传感器密布用来监控敌对目标的活动，因此如何穿越战场区域就成为了一个很重要的问题。本文结合实际提出了动态Voronoi图的概念，只需知道部分传感器分布情况利用动态Voronoi图建立穿越模型，并结合经典的Dijkstra算法寻找一条最短穿越路径。经过试验验证了该方法的可行性和有效性。 关键词：暴露 动态Voronoi图 Dijkstra算法

Mobile Voronoi graphic apply in acrossing battle region

LI Qian-jin,WANG Xi-wu,LIN Ke-cheng WANG Yin-Long

(Department of Computer Enginering,Ordnance Engineering College,Shijiazhuang 050003) Abstract: In modern battle, many sensors nodes are deployed. So crossing is a important question. In our notes, we proposed the mobile Voronoi graphic .we only know a apartment of sensors nodes and we can build a acrossing model , joining the Dijkstra algorithms looks for the shortest acrossing path . Extensive experiments confirm the validity and practivety. Keywords: Expose Mobile Voronoi graphic Dijkstra algorithms

１

1、引言

在现代战争中越来越多的传感器被用来监控感兴趣的区域。单个传感器以一定的采样频率收集信号，用收集的能量判断目标的存在或活动状况。如何选择一条最佳路径穿越被监控区域就成为战争中的一个重要问题。现有的工作一般基于穿越区域内传感器布置情况完全已知，这种假设与实际战场情况有很大不同。本文从实际情况出发，提出一种动态Voronoi图，将其应用于目标路径穿越。经仿真验证了其有效性。

2、 基本概念

2.1 暴露程度[1]

为了衡量目标被传感器感知的程度，很多文献都引入了暴露程度的概念。在这里定 义暴露程度为传感器节点收集的能量，即探测到目标的可能性。建立节点s对区域内任意一点p感知模型S如下： １

李前进（1981—），男，硕士，助教

S(s,p)??(d(s,p))k

?为传感器测量能力的加权系数，k为其中d(s,p)为任意一点p到节点s的欧式距离，

与环境相关的参数。从定义中可以看出目标距离传感器越近就越容易被探知。 2.2 Voronoi图 [2] [3]

Voronoi图最早由俄国数学家Voronoi于1908年提出，平面的Voronoi图是对平面的一个剖分，其数学定义如下：

设S?p1,p2,...,pn?为二维欧氏空间上的点集，将由

?Vn(pi)?p?R2p?pi?p?pj,i?j??

所给出的对平面的分割称为以点pi(i?1,2,...,n)为生成元的Voronoi图，简称V图。其中p?pi表示p和pi之间的距离。这里的距离可以是欧式距离，也可以是其它距离。Voronoi图的边界我们称为Voronoi边（Voronoi edge）简称V边，两条或者两条以上Voronoi边的交点我们称为Voronoi顶点（Voronoi vertex）简称V顶点。如果我们以暴露程度来定义

2Voronoi图中的距离，即Vn(pi)?p?RS(pi,p)?S(pj,p)，则最小暴露路径恰好落

??在Voronoi边上。由此我们想到利用Voronoi图来解决问题。 3、动态Voronoi图应用于战场区域穿越

在军事上穿越一个分布有传感器网络的区域，最重要的一点就是被传感器发现的概率最小。本文我们引入暴露的概念来表示传感器发现概率的大小。传感器能够探测到目标，同时目标也能发现布置的传感器，且目标对传感器的探测距离要大于传感器对目标的探测距离，否则反探测就不能成为可能。但由于目标探测设备的限制，不可能对敌方全部探测器的部署获得了解，只能了解区域内部分的探测器部署情况。为解决这个问题，本文提出了动态Voronoi图的概念。即当每发现一个传感器节点时就将这个节点加入生成元集合，生成新的Voronoi图。如下图所示：

图1

图中实线部分为7个生成元（S0,S1,S2,...S6）生成的Voronoi图，当目标沿图中箭头方向移动时发现新的传感器节点S7，这时需要将S7加入生成元集合，并利用更新后的生成元集合来生成一个八个生成元生成的新的Voronoi图。

对于构造Voronoi图本文采用增量构造算法，即将新发现的节点逐点添加到生成元集合，生成新的Voronoi图。增量构造算法如下：

假设点集S?p1,p2,...pn?，设已构造出的k个点的Voronoi图为Vor(p1,p2,...,pk)，要添加的点为pk?1，若pk?1?Vn(pi)，则做pk?1与pi的垂直平分线l，设l与Vn(pi)的边界交于两点q1,q2，其中q2为一有限坐标点，然后再找以q2所在边为公共边的与Vn(pi)相邻的V区域Vn(pj)，再做pk?1与pj的垂直平分线l1，…如此进行下去直到找到的相交点和，将连接后形成的区域内的V边去掉即可形成新的q1重合，最后将这些找到的点连接起来，Voronoi图。

由于目标探测距离大于传感器的探测距离，目标在发现传感器之前一定在新发现的传感器生成的V区域之外，这样在构造新的V区域时就不会去掉目标所在的V边部分保证了目标始终沿着V边行进。

在沿Voronoi边行进过程中可能会有多条行进路径，我们希望能找到一条最短的路径。

?Voronoi图其实是一个平面的网络拓扑图，以V顶点为网络节点，以V边为网络连接路径，我们面临的任务是找出从某一节点到另一节点的最短路径。本文采用经典的Dijkstra算法[5]来寻找最优路径。

Dijkstra算法是用逐点增长的方法构造一棵路径树，从而得到从该树的根节点到其它所有节点的最短路径。Dijkstra算法将网络节点分为未标记节点、临时标记节点和永久标记节点。网络中的所有节点首先初始化为未标记节点，在搜索过程中和最短路径节点连通的节点为临时标记节点，从临时标记节点中搜索距离源点路径最短的节点作为永久标记节点，直到找到目标节点或者所有节点都成为永久标记节点。

选择路径时，出发点有两种情况：（一）出发点在Voronoi边或者Voronoi顶点，这时我们只需沿着Voronoi边行走至终点即可。（二）出发点在Voronoi区域内，这是我们需要先向出发点所在的Voronoi区域的Voronoi边做垂线，然后选择垂线段最短的Voronoi边，目标从出发点沿着垂线段行进到Voronoi边上，然后再沿Voronoi边行进到终点。

动态Voronoi图应用于战场区域穿越算法的具体步骤如下： （1） 根据已有生成元集合，生成Voronoi图。

（2） 把V顶点作为网络节点，将V图映射为一个网络。以起始的V顶点为源节点，利

用Dijkstra算法寻找最短路径并沿此路径行进，直到发现新的感应器节点。

（3） 判断新增生成元pk?1所在的V区域，然后修改V多边形及相应的V边。

（4） 继续添加生成元，然后转步骤（3），直到所有新发现的生成元都添加到生成元集合

里面，最终生成新的Voronoi图。

（5） 转步骤（2），直到抵达目的点，或目的点所在V区域。

4、仿真试验

本文的试验平台主要为VC++ ，感知区域被定义为1020?645的平面区域。总共有40个传感器节点随机分布在该区域内。为了简化起见参数k,?都被设为1。假设目标从区域中一点p出发，要行进到点q。