障碍物遮蔽下三维空间多传感器优化布站

俞 宙，单甘霖，段修生，2，徐公国

(1.陆军工程大学石家庄校区，河北 石家庄 050003；2.石家庄铁道大学，河北 石家庄 050043)

0 引言

目前，战术侦察系统配置了不同体制、不同功能、不同频段的雷达、红外、激光和侦察车等传感器，广泛应用于战场环境监视、目标定位跟踪、区域协同探测等。布站后的位置影响了传感器系统的覆盖范围、通信以及资源管理能力，直接影响着系统的探测效果。因此，需要寻求一种优化布站方案，确保最优的区域覆盖率和最佳系统效能。

文献[1]考虑平面上的布站问题，将目标区域划分为正方形网格。文献[2]对传统的虚拟力算法进行了改进，但采用的是简单的布尔传感器感知模型。文献[3]考虑了探测成本、目标探测值以及探测能力等因素，提出一种基于博弈论的二维平面传感器自我布站。文献[4]提出一种基于虚拟力的理想三维环境下覆盖算法，解决传感器非均匀覆盖问题。文献[5]将果蝇算法和虚拟力相结合，来控制传感器对空间的网格覆盖，但研究的是理想的三维环境。文献[6]考虑了环境因素，提出了一种基于视线覆盖范围的概率传感器放置方法。文献[7]针对三维空间中传感器布站问题，采用差分进化算法解决了盲区问题，但忽略了实际地形因素的影响。针对在指定地理位置和存在障碍物的情况下的布站问题，文献[8]提出了一种避障虚拟力算法来实现传感器自主布站，避开了障碍物但未对障碍物进行建模。文献[9]考虑了障碍物遮挡问题，采用多目标进化算法研究了传感器布站问题。文献[10]加入更实际的地形模型，但只考虑了可用凸多边形建模的地形。

以上研究的都是二维平面以及理想三维环境下的布站，且依赖于过于简单化的传感器探测模型和理想的环境因素。但在实际应用中，战场地理环境往往极不规则，且存在高山等障碍物遮蔽问题。本文针对此问题，提出了障碍物遮蔽下三维空间多传感器优化布站方法。

1 战场多传感器优化布站模型

1.1 传感器探测模型

假设地面侦察系统中有N部方向传感器S={S1,S2,…,Sn}，对于任意传感器Si，有Si={(xi,yi),hi(xi,yi),ri,rci,θi,ξi},i∈[1,2,…,N]。其中，(xi,yi)是Si在平面上的坐标；hi(xi,yi)是Si的高度；ri是Si的探测半径；rci是传感器的通信半径；θi是传感器围绕垂直轴的水平角；ξi是传感器围绕水平轴的倾斜角。则空间中的传感器探测模型可视为三维球，如图1所示。

图1 传感器模型Fig.1 Sensor model

1.2 战场环境模型

实际应用中，战场中难免会存在高山、湖泊、沼泽、建筑物等障碍物，会造成视场约束。且战场环境的地形复杂多变，难以对其精确描述。为此，本文提出了一种基于网格化的战场环境模型。

1.2.1 网格化战场环境

基于网格化的策略是一种将区域划分为网格的方法，网格点近似代表整个区域。首先将三维战场环境投影到XOY平面上，实现对地形的数字化描述；接着用平行线对区域进行等间隔的网格划分，一个网格区域都是一个备选的传感器布站位置点。精度取决于网格的大小，尺寸越小，计算的就越准确。区域中的网格点表示为E={e1,e2,…,em}，对于任一点ej，有ej={(xej，yej),hej(xej，yej),wj},j∈[1,2,…,m]。其中，(xej，yej)是该点处的坐标，hej(xej，yej)是该点处的高度，由数字高程模型(DEM)提供，wj代表该点处的权重。因此，T={he1,he2,…,hem}是一个数字高程矩阵，矩阵数值表示网格点的高度。

1.2.2 区域划分

整个战场区域可以划分为四类：侦察区域Ar、障碍物O、布站区域Ad和不能布站区域Au。侦察区域是传感器侦察系统需要覆盖的区域，应尽可能覆盖。障碍物描述了环境中存在的障碍，本文认为障碍物能阻碍传感器的探测和布站，但不会阻碍传感器之间的通信。布站区域表示传感器允许布站的区域，包括但不限于侦察区域，并排除障碍物。不能布站区域包括但不限于障碍物。

1.3 自适应LOS理论

影响可视性的主要因素是两点之间连线上点的高度。高度由DEM提供，是一个基本的二维矩阵，矩阵中的元素存储了战场环境中点的高度。传统的LOS方法根据网格大小，将连接点和传感器之间的连线划分为若干分裂点；接着将每个点高度与包含它的网格高度进行比较。如果小于网格高度，那么两者之间存在障碍物。但是这个方法的缺点是计算复杂，运算量大。

为此，我们提出了一种新的自适应LOS理论，使用分裂点之间的自适应长度来减少计算的点数。考虑到分裂点和连续两个分裂点之间网格的高度的差异性，如果在分裂点没有测量到障碍物，那么下一个分裂点也可能没有障碍物。因此，本文使用线性回归来预测连接点和传感器的线是否与障碍物相交。如果是，则记录下这一点和开始点的距离作为新长度，将该点设置为开始点，并继续寻找另一个自适应长度，直到新点超过了传感器位置点。可视性示意图如图2所示。

图2 可视性示意图Fig.2 Visibility schematic

1.4 障碍物建模

为了清晰直观地描述障碍物，我们假定平面上存在圆形和矩形这两种形状障碍物，O={o1,o2,…,oh}表示战场中存在的所有障碍物。其中，圆形障碍物对应于环形山、大石头、湖泊等圆形状障碍物，表示为oi={(xoi,yoi),roi,hoi}, (xoi,yoi)是障碍物的圆心，roi表示圆形障碍物半径，hoi表示障碍物高度。矩形障碍物对应于高山、树篱、建筑物等矩形状的障碍物，表示为oi={(xoi,yoi),loi,woi,hoi},(xoi,yoi)表示矩形障碍物左上角顶点，loi和woi分别表示矩形障碍物长度和宽度，hoi表示障碍物高度。障碍物建模示意图见图3。

1.5 优化布站数学模型

对于布站区域内的任意一个点ej，传感器和目标点之间的距离为：

(1)

如果战场区域中所有点都能被传感器系统覆盖，那么战场区域就能够被覆盖。通常，布站区域中的任一点ej需要满足以下条件才能视为被传感器Si所覆盖。

1) 传感器Si与点ej之间的距离小于等于传感器的探测半径ri，即：

(2)

2) 传感器Si与点ej之间沿X轴方向的角度不大于传感器的方位角。μb是一个用于描述传感器Si沿着垂直轴对点ej覆盖能力的二元函数：

(3)

3) 传感器Si与点ej之间沿着Z方向的角度不大于传感器Si的高低角。μc是一个用于描述传感器Si沿着水平轴对点ej覆盖能力的二元函数：

(4)

4)vij定义为传感器Si与点ej之间的可视性，如果传感器Si与点ej之间的视线被遮挡，则认为传感器Si探测不到点ej，vij=0；反之，vij=1。

(5)

式(5)中，nobstacle(Si,ej)是传感器Si与点ej之间的障碍物数量，取决于自适应LOS理论。

因此，传感器探测模型主要取决于距离、方向以及可视性。则传感器Si在点ej处的覆盖能力可以定义为：

C(Si,ej)=μa×μb×μc×vij

(6)

考虑到点ej可能被一部或者多部传感器所覆盖，且传感器之间相互独立，因此，战场环境中点ej被覆盖的概率为：

(7)

那么整个区域的覆盖率为：

(8)

综合考虑战场环境等因素，为了获得最大侦察区域覆盖率Call，建立如下的多传感器优化布站数学模时型，通过优化求解，可以获得最佳的多传感器优化布站方案：

(9)

2 多传感器优化布站算法

2.1 自适应权重粒子群算法

粒子群算法(PSO，Particle Swarm Optimization)将优化问题可行解初始化为一群随机粒子。粒子根据如下的公式来更新自己的位置和速度：

Vi(t+1)=ωVi(t)+c1r1(Pibest-Xi(t))+

c2r2(Pgbest-Xi(t))

(10)

Xi(t+1)=Xi(t)+Vi(t+1)

(11)

为了平衡PSO算法的全局搜索和局部改良的能力，采用非线性的动态惯性权重系数来改进粒子群算法。

(12)

式(12)中，ωmax和ωmin分别表示ω的最大值和最小值，f表示粒子当前目标函数值，fave和fmin分别表示当前粒子群的平均目标值和最小目标值。因此，ω随着粒子群目标函数值自动改变，故称作自适应权重。当粒子目标值趋于一致或局部最优时，将增大ω，而粒子的目标值比较分散时，将减小ω，保留该粒子。且差于平均目标值的粒子，其对应的惯性权重因子较大，使得该粒子向较好的搜索区域趋近。

2.2 虚拟力算法

虚拟力算法VF(Virtual Force Algorithm)，虚拟力借助于物理中的范德华力对区域中随机分布的传感器进行重新布站，包括引力和斥力。布站时，传感器随其受到的合力进行移动，从而实现对目标区域的均匀覆盖。假设在侦察区域中，相邻传感器Sj作用在传感器Si上的虚拟力为Fij，当两个传感器之间的距离大于距离阈值Dth时，传感器之间产生引力，传感器向着对方移动。当传感器之间的距离小于该阈值时，传感器之间产生斥力，传感器向着相反方向移动。Fij的计算公式为：

(13)

目标区域边界对传感器Si的作用力为Fia，障碍物对传感器Si的作用力为Fir，则作用在传感器Si上的总的虚拟力Fi为：

(14)

式中，dij是传感器Si与传感器Sj之间的几何距离；adj(Si)是传感器Si的邻接集，当且仅当dij≤rc时，传感器Sj称为Si的临集；Dth表示均匀分布时传感器之间的平均距离。

2.3 虚拟力自适应权重粒子群算法

本文在粒子进化过程中，加入虚拟力来增强粒子的位置更新能力。得到了虚拟力自适应权重粒子群算法(VF-APSO)，进化过程如下：

Vi(t+1)=ωVi(t)+c1r1(Pibest-Xi(t))+

c2r2(Pgbest-Xi(t))+c3r3Fi

(15)

Xi(t+1)=Xi(t)+Vi(t+1)

(16)

式中，c3是调节虚拟力的加速因子，r3是[0,1]之间随机数。虚拟力对于粒子位置更新具有积极作用，提高了算法的收敛速度。但到了后期，由于虚拟力的存在也会阻碍粒子的局部搜索，无法搜索到最优解。因此，本文对c3进行动态调整。更新公式为：

(17)

此处，c3start取为0.6，c3end取为0.2。这样，算法前期主要发挥虚拟力算法的优势，加快粒子的收敛速度。算法后期减小了虚拟力带来的影响，发挥自适应权重粒子群算法的优势，对全局最优解附近的解空间进行精确搜索，找到更优解。

3 仿真与实验

为了验证所提算法的有效性，本文用Matlab对三维空间中视场约束下的多传感器布站问题进行了仿真实验。实验中，首先采用大量的测试点对自适应LOS理论进行验证。接着采用VF-APSO算法进行传感器优化布站，并与经典的PSO、VF-PSO算法进行仿真对比。

3.1 自适应LOS理论

首先，我们分别采用100，200，500，1 000，2 000，5 000个点对所提的LOS理论进行了测试，每组运行50次，平均结果如表1和图4所示。

表1 自适应LOS理论测试结果Tab.1 Adaptive LOS method test results

图4 新旧LOS理论对比Fig.4 Comparison of two LOS method

仿真结果表明：自适应LOS理论在检测障碍物方面获得了较好的精确度；且与传统的LOS 理论相比，大大减少了运算时间，提高了检测效率，可以有效解决对空间中存在的障碍物检测问题。

3.2 基于VF-APSO的多传感器优化布站

实验中，首先将传感器随机分散在30 km×30 km×10 km的三维空间区域中。为了避免资源浪费，采用10部传感器对地面目标区域进行覆盖，并在目标区域中随机设立了一些障碍物，用黄色区域表示。假定侦察系统中所有传感器的探测半径r为5 km，通信半径rc为2r=10 km，距离门限值Dth为r=5 km，初始种群为300，最大迭代次数500。采用VF-APSO算法进行优化布站，并与经典的PSO、 VF-PSO算法进行仿真对比。运行结果如表2，图5—图7所示。

表2 50次不同算法独立优化平均性能比较Tab.2 Comparison of different algorithms’ optimization performance

图5 PSO优化布站Fig.5 View of PSO optimal deployment

图6 VF-PSO优化布站Fig.6 View of VF-PSO optimal deployment

图7 VF-APSO优化布站Fig.7 View of VF-APSO optimal deployment

仿真结果表明：相比于PSO、VF-PSO算法，改进后的VF-APSO算法增强了粒子的全局搜索能力，提高了运算速度；且基于VF-APSO算法的多传感器布站方法求出的传感器位置有了明显的改善，提高了覆盖率，实现了对侦察区域的有效覆盖，解决了障碍物遮蔽下的多传感器优化布站问题。

4 结论

本文提出了障碍物遮蔽下三维空间多传感器优化布站方法。该方法首先网格化侦察区域，然后采用自适应LOS理论来检测区域中存在的障碍物，构建多传感器优化布站数学模型，最后采用虚拟力自适应权重粒子群算法求解传感器的最优布站位置，并与经典算法进行对比。仿真实验表明，该方法增强了粒子的全局搜索能力，提高了粒子的运算速度，有效提高了区域覆盖率。对于解决实际中存在障碍物条件下的多传感器优化布站问题，具有一定的参考意义。