基于伪卫星测试的并行计算灾害救援中心选定模型构建

鞠森森，钱若霖

(陕西工业职业技术学院 土木工程学院，陕西 咸阳 712000)

0 引言

特殊的地质环境、不利的地形条件，导致我国各地区泥石流灾害频频发生。当泥石流灾害发生时，如何对应急资源进行科学、高效的调配，防止灾害的进一步扩散，在理论和实践上都有很大的作用。

泥石流灾害救援中心的优化选址与救援时间满意度是突发泥石流灾害应急救援考虑的首要因素。其中，泥石流灾害救援中心选定环节是最关键的一个环节，紧急物资能否准确、高效地运送到灾区，直接影响到救灾工作的成功和失败。泥石流灾害救援中心选定问题，即利用科学方法决定救援中心的地理方位，实现路径最短的快速灾害救援[1]。泥石流灾害点面积广、成灾迅速，注重救援中心选址快速便利性，以便对其进行有效救援，成为灾害修复工作的重点。

对此，有学者提出了相关研究。如，文献[2]提出以覆盖满意度和经济成本为目标的选址模型，构建自适应遗传算法，并结合方向性提高搜索速度，通过自适应交叉与变异算子得到最优解。该方法不能根据道路被泥石流毁坏条件下进行再次寻优，适应度不足。文献[3]提出以救援效率和成本为目标，构建多阶段决策模型。分析每段路线的救援效率，构建多阶段选址-路径优化模型，利用改进快速非支配遗传算法求解。该方法对混合交叉算子的限制不足，在求解时得到多个解，难以判定最优方案。

针对上述模型存在的问题，本文构建一种基于伪卫星测试的并行计算灾害救援中心选定模型。使用基于并行计算的泥石流运动模拟方法，了解泥石流汇流运动过程，并将泥石流堆积作为泥石流全局运动，采用离散元算法建立泥石流堆积模型，将泥石流流团运动速率从三维变换为二维，预测泥石流灾害围线范围；构建救援中心选定优化模型，在精度因子基础上获取救援选址的中心区域点，实现泥石流灾害救援中心选定。

1 问题描述

在发生重大泥石流灾害时，必须在最短的时间内，合理地选定灾害救援中心，使其在有限的运输条件下，尽快选择合适的运输方法，最大限度地满足所需的物资运送时间和数量需求。泥石流灾害救援中心选址问题是NP-Hard问题。可以用双层模型来描述：上层模式是在最短的时间内，将救援物资从救援中心运送到对应的紧急转运站，而不超出救援中心的距离和指定运输站的的选址问题；下层模式是指在满足一定的配送量要求条件下，以更短的时间、更低的运输成本，将救援物资从紧急转运站运送到不同的紧急情况点，而选择的紧急转运站则是两种模式的连接点，由于上层模式的目标具有全局性，最优参数值依赖于自己的参数变量、约束条件，也要考虑下层的目标值，因此，必须及时向上层传递目标值；在此基础上，上层决策对下层模式的路径规划产生了一定的影响，通过这种反馈机制，可以使上下两层动态互动，从而达到两层模式的综合优化。

因此，在泥石流灾害发生后，要根据救灾物资的需求，既要考虑到救灾物资的距离，又要综合考虑各种物资的类型，以及所需物资的运输费用，从而选择一个合适的救援中心，并制定一个最佳的物资分配方案，以确保各个中心在最小的代价下，最大限度地满足灾民的需求，确保救灾的效率，降低资源的消耗，从而得到系统的整体优化。问题描述如图1所示。

图1 灾害救援中心选址-调度示意图

由图1可知，泥石流灾害救援中心选址优化问题可以描述如下：

设有n个大概率发生灾害的受灾需求点，对于受灾需求点k，其在预期内发生泥石流灾害的概率为pk，在应急救援队伍到达之前，灾害扩散造成的损失函数为dk(t)，可容纳的最大救援队数量为qk，k=1，2，...，n，设有m个备用的救援中心选址，中心为O，运行成本为bo，救援阶段反映函数为Tt，每次救援的成本为cl，l=1，2，...，m，从救援中心O到达受灾需求点k所需的时间为tkl，k=1，2，...，n，l=1，2，...，m，为找出分布最好的救援中心的开设计划和救援计划，从而使预期损失和成本之和最小化，需要构建基于并行计算的泥石流运动学模型，确保泥石流救援中心的最优选址。

2 基于并行计算的泥石流运动学模型

本文在建立简化泥石流堆积模型时，使用离散元+GPU算法实现泥石流堆积并行计算模型架构。运用离散元算法建立的泥石流运动公式，以颗粒之间的触碰模型为主要研究重点。本文使用的触碰模型是弹簧-阻尼器模型，将其法向接触力描述为：

(1)

其中：fi，s是颗粒i与颗粒j撞击的互斥力，颗粒在撞击时，fi，d是颗粒阻尼力，k表示弹簧弹性指数，η是阻尼系数，d为颗粒直径，vij是对应方位与两个颗粒之间的对照速率，rij表示颗粒i与颗粒j之间的距离。

通过计算机模拟泥石流，利用地形特征对得到的运动数据资料，计算出泥石流的相关运动数据结果。结合流体力学模型法，并应用流团模式对泥石流的运动进行数值仿真。其中以堆积扇面为基础，利用二维运动方程对其进行数值仿真。此模式具有简单、高效的特点。在采用流团模式进行泥石流运动的计算机仿真时，必须对其进行时空离散，在此基础上，将泥石流的运动过程划分为若干个时间步长，将其空间划分成相同的网格，利用统计学的方法，将各流团的运动参数表示为各个网格，从而得出泥石流的整体运动规律。将泥石流分为不同的多个粒子集合，这些粒子的体积和总的泥石流体积有很大的差异，因此可以认为是一大批颗粒在进行堆积扇的运动。在模型操作中，要将各个流团的运动速度从三维向二维转换。

因此，在进行模型推算时，将流团空间速率V变换成二维速度方位内的速度[4-5]，使用迭代方法推算流团每个时段的速率，并将其进行简化形变，得到流团迭代公式：

(2)

使用GPU迭代方法计算流团每个时段的速率，并将其进行简化形变，得到如式(3)的流团迭代公式：

(3)

可以将式(3)直接应用在运算过程中，在时间域求解中，每一时间步长都需要进行一次迭代，以求出堆积过程中流团的泥石流速率[6-7]，摩阻坡降Sfx、Sfy与底面坡降Ssx、Ssy的运算过程为：

(4)

其中：τ、γm、μ、B、h、kcu表示泥石流参变量。在模拟泥石流运动形态的过程中，计算出流团在每个时间步长中的速率参变量[8-9]，同时也要获取不同时段各个流团所处的方位参变量。已知第k个流团在n时段的方位坐标，那么迭代求解第k个颗粒在n及n+1时段的方位关系，具体表示为：

(5)

推算网格运动参量是一个相对动态过程，即获取某个时段n的网格运动参数。在计算式，要将全部计算区域分割为正方形网格，并将其固定，然后按照运动流团某时段经过n的流团运动参数得到其网络运动参量，运动参量分别是速率、泥深、动能及动量值[10-11]。

运用网络内全部流团位于X、Y向速度的合速度值描述各个网格的泥石流速度值，将该过程记作：

(6)

通过式(6)计算流团位置，从而可以确定流团所在的栅格位置。在相同的流团网格中，利用流团体积，计算当前网格泥深，具体如式(7)所示：

hk=Δc*w/s

(7)

式中：hk表示在某一时刻第k个网格的泥深，w表示网格中流团数量，Δc表示单流团体积，s表示网格总面积。

在计算流图动量和动能时，采用基于网格速度和网格体积的方法，由式(8)实现：

(8)

式中，Ek、Pk表示第k个网格在某一时刻的动能及动量，ρ表示泥石流密度，C表示网格内泥石流的体积，Vk表示第k个网格某一时刻的泥石流速度。

由前述求解过程可知，泥石流堆积模型中流团空间速率、泥石流速率被数值解耦，网格运动参量、流团位置求解、流图动量和动能等计算密集型流程中没有数据依赖关系的程序周期。因此，该模型的计算程序可以实现可并行性，实现多核心CPU和离散元的并行结构。当前，在 OpenMP基础上实现多核 CPU的并行化处理已经比较成熟，所以在此不做详细介绍。目前 GPU的并行处理技术有 CUDA、OpenCL、OpenACC等多种编程方式。在此基础上，从软件兼容和使用方便的角度出发，本文选择了 OpenACC的并行编程方式，该模式是通过对编译指令的识别和指令辨识，使其能够产生并行的执行代码，从而达到 CPU与离散元的异构并行运算。

并行计算与串行运算相关。该方法可以同时处理多条命令，以加快运算速度，并扩展问题的求解范围，从而处理大量的、繁杂的运算。利用 GPU实现并行运算的方法有三大部分：①将所需要的存储空间分布在主、设备两个终端，并将其从主服务器拷贝到装置；②通过设备端进行并行运算；③将计算的数据从设备上复制到主机，基于离散元+GPU算法是以 CPU为基础的并行计算。

此外，如果将所有的泥石流都用离散元方法进行数值模拟，并通过CPU进行计算，该模型的规模将会非常有限。而在灾害救援过程中，多个目标的集中救援和多个目标需求点，传统方法很难得到精确的求解。因此，本研究在采用离散元法建立的泥石流运行累积模型中，所有的渲染运算都通过GPU完成，GPU则完成大量高密度的并行运算，CPU则承担连续运算。通过 CPU/GPU的协作运算，可以对大规模泥石流汇流现象进行模拟，该研究结果可为面向流域泥石流汇流聚集风险区域的分析和救援中心选址提供更加精细的虚拟地理环境仿真。运用ThingJSglb三维模拟软件模拟泥石流模型效果如图2所示。

图2 并行计算泥石流模型模拟结果

3 基于伪卫星测试的泥石流灾害救援中心选定

在计算得到准确的泥石流模型后，将泥石流灾害救援中心选定结合伪卫星测试技术，进行如下描述：假设伪卫星采集到具备m个可能的灾害地点，关于灾害地点j而言，其计划期内产生灾害的几率是pj，在救援抵达之前，灾害扩散拥有的损失函数是dj(t)，能够容纳的救援队最多个数是Kj。若有n个备用的救援中心位置，中心i设立成本是Ci。从救援中心i抵达灾害地点需要的时间是tij，决策人员希望寻找最佳分布的救援中心的设立方案和救援方法，使期望损失与成本为最低。允许多个救援中心联合救援，一旦地点j发生灾害，优先抵达该位置的救援中心次序是[1]，[2]，…，[Kj]，将联合救援解析式定义为Uj(R[1](t)，R[2](t)，…，R[n](t))。如果灾害地点j有泥石流现象发生，损失函数dj(t)会直线上升。在救援队[1]在时段tj[1]抵达时，灾害终止扩散，损失函数开始减小。救援队[2]、[3]陆续抵达后，在多个救援小组的共同作用下，灾害损失成快速下降趋势[12-14]，因此可得到救援优化模型的模型参变量为：

i=1，2，…，n，j=1，2，…，m

(9)

(10)

将上述两个公式使用以下数学模型进行描述：

(11)

(12)

(13)

xij，yi=0j=1，2，…，m

(14)

式中，在联合救援函数U(°)内，如果x[k]j=0，那么证明R[k](t)不包括在U(°)中。

以上模型(9)～(12)是一个十分繁杂的0-1整数规划模型。在目标函数式(9)内，第一项为救援中心的设立成本，针对以几率pj产生的灾害带来的损失而言[15-17]，第一项表示救援成本，首个定积分为救援队抵达前的损失，第二个积分为救援过程损失。约束式(10)代表参与救助的救援中心必须开设条件，式(11)为每个受灾点所需的救援队伍上限收敛，式(12)代表变量类别收敛。

假设某个时段用户Ti探测到一个伪GPS卫星sj，同时构建以下测码伪距观察解析式：

(15)

(16)

不考虑大气层的偏差影响，继而获取下列公式：

(17)

从上式可知，公式内含有四个未知参变量，因此最少构建四个相似的解析式[18-19]，用户应同时观察到四个伪卫星，满足泥石流灾害救援选址系统的精准定位。

矩阵Q内的矢量(li，mi，ni)为四颗定位伪卫星至测验中心构成的向量和三个坐标轴夹角的方位余弦[20]。在系统内加入精度因子准则来评估选址定位结果，将平面精度因子与垂直精度因子描述为：

(18)

(19)

因为救援选址系统是以电子地图作为解析目标，而电子地图涵盖的是地图上各个点的二维位置，从上述的运算过程，方向余弦矩阵Q是推算精度因子的关键[21-22]，而方向余弦矩阵Q是通过参加定位的四颗伪卫星到用户检测点构成的四个向量和坐标系三个坐标轴夹角的余弦组成。

将检测点O定位坐标系中心零点、四颗伪卫星及测量点组成四个向量OS1、OS2、OS3、OS4，将O当作球心组建一个单位球，获得四个单位向量，且Z轴与地面保持垂直。

利用余弦定理求解OS2的水平方位角，OS2的方位角是其与OS1的水平夹角，记作：

(20)

通过上述计算，获得原始测试点位置的HDOP值和VDOP值，继而将其与评判标准进行对比，明确该位置是否是救援选址的核心区域点。

本文泥石流灾害救援选址系统主要包含三个板块，具体如图3所示。

图3 灾害救援中心选定方法架构

卫星通信节点主要分布在灾害地区附近，利用自组织模型构成通信网络，以此进行数据收集与传送。基站节点关键负责汇集节点传送的有关数据，同时采用互联网把数据输送至服务器内。服务器处于救援中心，主要作用于信息储存与加工，按照对应数据构建最佳的救援选址方案。

4 选址算法流程

由于灾害扩散的损失远高于救灾的成本，因此距离灾难现场最近的救援中心是参与联合救援的救援中心的首选，其他参加救援的中心可以由离散元+GPU算法求出。采用离散元法与 GPU并行计算方法，建立了泥石流的流动堆积模式，以其堆积特征和灾区为模拟参考，对泥石流运动进行模拟，根据模拟结果，预测泥石流覆盖范围，利用伪卫星技术计算灾害扩散程度和易发点距离，将用户选择的位置与高度作为已知条件，以期望损失最低为约束，以精度因子为标准得到救援选址的核心区域点，可以避免陷入局部循环，最终可求得全局最优解。选址算法流程图如图4所示。

图4 选址算法流程图

5 仿真实验

为了证明本文模型的可靠性，以某县泥石流为例，对灾害救援中心选定进行仿真分析。选取的泥石流流域面积5.66 km2，主沟长度为9 km，主沟比降142.5‰，最大高程为1 256 m，沟口高程为1 698 m，相对高度为1 242 m，流向由东向西。选址范围在泥石流区域10公里半径的圆内，设该地区有10个受灾需求点。实验平台为Matlab 7.0仿真软件，在处理器CPU为16 Core；Memory为128 GB；Disk为3TBBandwidth为1 000 Mb/s，内存为 DDR4 4 G的计算机上运行通过。

伪卫星测试得到的泥石流模拟效果如图5所示。

图5 泥石流仿真模拟效果图

选址模拟图结果如图6所示。

图6 选址模拟图

通过图4可以看出，黑色代表泥石流灾害区域，浅黑色代表最优救援区域。本文给出不同的救援中心方案。通过不同方案均能快速到达最优救援区域。

为了验证基于伪卫星测试的并行计算灾害救援中心选定模型的定位准确性，将文献[2]提出的基于自适应遗传算法的应急物资储备库选址及物资调配优化模型、文献[3]提出的带模糊需求的多阶段双目标应急选址—路径优化模型与本文模型进行对比，以救援中心选定定位精度为测试指标，三种模型救援中心选定定位精度对比示意图如图7所示。

图7 救援中心选定定位精度对比

从图7中可以看出，本文模型拥有较强的定位精度，随着实验次数的增加，其定位精度逐步稳定于90%以上，表明该模型具备较优的实用性，可以满足灾害后救援中心选定的及时选择，为受灾地区提供更快的救援效率。文献[2]模型在实验次数较少时，与本文模型的定位精度较为接近，但在实验次数为5时，其选址精度仅有73%，而文献[3]模型的救援选址定位精度最低，鲁棒性较差。

为了验证本文模型的有效性，为保证实验数据的准确性，在同一试验环境下进行试验，确保实验条件的一致性，以救援中心选址时间为测试指标，对本文模型、文献[2]模型和文献[3]模型的救援选址时间进行对比分析，对比结果如表1所示。

表1 救援中心选址时间对比

从表1中可知，文献[2]模型的救援选址时长约为本文模型时长的2倍，而文献[3]模型的救援选址时长约为本文模型时长的3倍，实用性均不高，无法提高灾后救援的高效率执行。综合判定，本文模型的救援选址效率优于传统模型的救援选址效率，可广泛应用于实际场景中。另外，根据上述结果可以看出，灾害救援中心的选址在不同实验次数下，由于救援地点的灾情和需求的不同，呈现出动态变化的现象。在不同实验次数下，根据灾害救援中心的位置和救援地点的实际情况，合理选择救援地点，最大限度地提高救援效率和救援地点的时间满意度。

为了进一步验证本文模型的可行性，采用本文提出的基于伪卫星测试的并行计算灾害救援中心选定模型进行灾害救援中心选址，并与文献[2]模型和文献[3]模型进行对比，3种模型获得的灾害救援中心位置坐标值如表2所示。

表2 灾害救援中心选址结果

由表2中的灾害救援中选址位置数值结果，绘制灾害救援中心选定目标情况如图8所示，其中圆形表示本文模型，三角形表示文献[2]模型，实心方形表示文献[3]模型，感知区域为核心区域，即灾害救援中心的最优选址。

图8 灾害救援中心点最优解

对比三种模型的灾害救援中心选址结果可知：感知区域的四个位置坐标分别为(3.53，3.11)、(5.76，3.11)、(3.53，8.09)、(5.76，8.09)，本文模型的5个灾害救援中心选址点均在感知区域内部，且灾害救援中心选址位置较近，方便受灾人员转移，本文模型的灾害救援中心点最优解位置坐标为(4.23，5.12)；而文献[2]模型和文献[3]模型的灾害救援中心选址点距离感知区域的最优位置坐标为(8.59，9.15)和(12.32，13.45)，且文献[2]模型和文献[3]模型的灾害救援中心选址点均不在感知区域内部，其原因是未解决线性不收敛问题。经上述测试结果表明，本文模型的灾害救援中心选址性能综合最优。原因是利用伪卫星技术计算灾害扩散程度和易发点距离。

为验证本文构建一种基于伪卫星测试的并行计算灾害救援中心选定模型中，离散元+GPU算法的收敛性，设置相同的最大迭代次数20，得到3种算法收敛曲线的对比结果如图9所示。

由图9可以看到本文提出的离散元+GPU算法，收敛速度优于其他两种对比算法，上述实验结果均表明本文算法的救援中心选址性能远超于另外两种对比算法。原因是该离散元+GPU算法运用离散元算法建立的泥石流运动公式，以颗粒之间的触碰模型为核心要点，实现泥石流堆积并行计算模型架构。结合伪卫星测试技术，在系统内加入精度因子准则来评估选址定位结果，继而将其与评判标准进行对比，明确该位置是否是救援选址的核心区域点，按照对应数据构建最佳的救援选址方案。同时，该算法采用增强了局部搜索能力，本文算法能迅速地将数据输送至服务器内，进而表现出较好的优化性能。

结合上述内容，与其他常用于解决这两类问题的两种文献模型做比较，得到的对比结果如表3所示。

表3 不同模型实验性能的结果

从表3结果分析可以看出，文献[2]模型和文献[3]模型的迭代次数分别为20次和25次，均不能获得全局最优解；而本文模型的迭代次数为15次，本文针对中心选址问题，该方法的并行运算采用了离散单元+ GPU的方法，能够得到最优解，而且具有很高的效率。将两种方法结合起来，可以得出一套科学的灾害救援中心选址方案。

综上所述，本文建立的模型具有极大的柔性，无论是救援地的时间满意度，还是灾害救援中心的选定，在实际泥石流灾害救援中都是非常必要的，可以保证灾害救援各个时期内最大限度地满足救援地的物资需求，可以获得全局最优解并且求解效率较高，同时使得救援地的时间满意度和救援中心位置最优，为灾害救援中心选定提供了科学依据。

6 结束语

为了增强灾害救援的及时性，构建一种基于伪卫星测试的并行计算灾害救援中心选定模型。通过分析固相泥石流颗粒之间的受力，采用离散元方法构建泥石流运动公式，将泥石流体分解为多流团颗粒集合，运用并行计算获得泥石流运动模拟结果，准确评估泥石流灾害具体情况；使用救援中心选定模型和伪卫星测试手段，完成并行计算灾害救援中心选定模型构建，并增强救援选址模型整体性能，为真实场景下泥石流灾害救援提供有效帮助。经实验验证可知，本文模型拥有较强的定位精度，随着实验次数的增加，其定位精度逐步稳定于90%以上，本文模型的5个灾害救援中心选址点均在感知区域内部，且灾害救援中心选址位置较近，方便受灾人员转移。因此，本论文的研究对紧急情况下的灾害救援中心选定具有一定的现实意义。由于灾害突发事件的影响因素较多，其优化模型的目标和约束条件相对简单，没有考虑到救援过程中的道路运输条件、救援半径、救援人员的应急反应速度、应急救援中心的周边环境等，因此还有待于实践的具体改进。