在我国的能源结构中，煤炭资源的消耗占了很大的比例^[1]。然而，矿井工作环境恶劣，煤矿开采力度的加大使得开采作业愈发困难，保障井下开采作业过程中的人身安全是重中之重。为了保障井下人员、设备的安全和采矿工作的顺利进行，采用了多种通信和网络技术。如在矿井中安装有线电话系统^[2]，可以加快信息调度的效率；通过建设基站，无线通信网络和有线电话系统有效连接，能实现无线通信、信息调度等各项基本功能；矿井网络互联，对煤矿井下电力设备、瓦斯浓度、通风情况等进行实时监控，及时预警灾害情况，达到降低井下事故发生概率的目的。随着移动互联网、IoT 和无线传感器网络（WSN,wireless sensor network）等技术的快速发展，IoT在矿山上的应用也得到大规模拓展，形成了面向人—机—环多元信息采集、处理与交互的矿山IoT体系。矿山IoT主要以工业以太网为骨干网，承载视频业务、语音业务、控制命令和传感数据等的传输，向上支撑态势评估、安全生产等业务。在矿山环境下联网节点的数量呈指数级增长，所感知的数据呈海量、多源、异构等特点。

将海量的感知数据经高速互联网连接，可以实时与云端进行信息交互。但是将收集的全部海量数据传输到云端是不切实际的，不仅操作难度大，而且会造成相当多的资源浪费^[3]。加快对矿山无线网络数据感知收集技术的探究迫在眉睫，因此，为了高效地收集矿山环境的感知数据，可以引入 MCS技术来改善移动感知节点的覆盖性能，提升信息收集的能力。

MCS技术与传统的WSN相比具有很多优势，如 MCS 在收集数据的过程中，不需要事先在目标区域部署相关的感知设备，充分利用矿山车辆移动范围广而灵活的特性，将其作为嵌入多种传感器的移动载体，对矿山环境中的感兴趣区域（ROI,regions of interest）进行多元数据的感知和收集^[4,5]。而传统的WSN为了感知、收集ROI的数据，需要在所有ROI部署多种传感器，成本与效果受诸多因素限制。MCS 利用动态选择的车辆进行数据的收集，可以获得较好的覆盖质量。而且，由于车辆的可维护性，不易出现类似 WSN 中传感器节点能量耗尽导致的数据收集失败的问题。

文献[6]旨在减少感知数据的冗余，通过选择最少的车辆来达到最大的时空覆盖度（STC,spatial-temporal coverage）。文献[7]将MCS服务平台与候选车辆之间的交互建模为马尔可夫决策过程（MDP,Markov decision process），使用深度强化学习最大化 STC。由于仅根据当前位置选择参与车辆，因此，仿真得到的覆盖效果不一定达到最优。文献[8]提出了一种基于预测轨迹的车辆选择算法。文献[4,9-10]通过路径规划或路径分段的方法完成感知任务。Gong等^[9]设置了车辆行驶距离预算，提出了一种基于遗传的路由（GR,genetic-based routing）算法，并根据 GR 算法设计了 4 种在线任务分配算法。文献[11,12,13]从经济角度解决了MCS 的激励机制问题，其中文献[12]考虑了 MCS中平台、参与者和任务发起者3方面的利益。此外，为了平衡平台与参与者之间的效用，文献[14]提出了一个以用户为中心的基于声誉的招募策略。文献[15]介绍了多臂赌博机（MAB,multi-armed bandit）模型并使用有界ε-first算法，有界ε-first算法将总预算B中的εB部分用来获取评估质量特性，而剩余的(1-ε)B部分则用于优化效用函数。在保证服务质量（QoS,quality of service）方面，文献[16]提出了一种GR算法，文献[17]采用了矩阵补全技术。文献[18]设计了一种高效节能的MCS任务分配框架。文献[19,20,21]讨论了感知过程中的能耗问题和感知数据的质量问题。

本文建立了一个MCS数据模型，主要提出CP和CD两个概念来衡量车辆对ROI的覆盖质量。使用真实的车辆轨迹数据集进行仿真评估，结果表明，所提出的CQO算法可以获得较高的覆盖质量。同时，研究了成本预算、候选车辆数量和感知次数等变量对覆盖质量的影响。

本文提出的智慧矿山MCS系统模型如图1所示，此系统由一个云平台和配备多个传感器的车辆组成，地面场景如图1(a)所示，井下场景如图1(b)所示。云平台的工作是将感知任务分发给候选车辆，并根据本文提出的策略选择合适的车辆来执行感知任务。当车辆完成感知任务后，将感知数据上传到云平台。

需要指出的是，在现实中，不同区域的感知需求是不同的。某些感知任务的感知结果是“是”或“否”的二值（0或1）类型，如果只根据一辆车的感知数据来判断得出结论，会造成较大的偏差，因此，收集具有一定冗余度的数据是相当有必要的。为了提高相同位置感知数据的准确度，需要进行多次采集以保证数据的准确性。

基于 MCS 的场景，本文将目标区域划分为10×10的网格单元，区域重要度示意图如图2所示。文献[22]以矿工为主要检测目标，井下矿工尤其是某些区域的矿工并非均匀分布在巷道或井下其他位置，也就是说ROI可分为热点区域和非热点区域（普通区域）。在图2中，A、G、H、J为权重为2的热点区域，其他区域（B、C、D、E、F、I、K、L）为权重为 1 的非热点区域，此处权重值的设定主要是为了区分热点区域和非热点区域对覆盖质量的影响。若将热点区域的权重值设置为10，非热点区域权重值设置为1，10:1的比例会对本文提出的覆盖质量造成过大的影响；若将热点区域和非热点区域的权重比例设置得过小，则无法显示本文提出的非均匀覆盖问题以及无法表示热点区域较非热点区域可以对覆盖质量做出更大的贡献。借鉴了文献[23]中视觉敏感度函数模型的思想，视觉对比敏感度反映了人类视觉对不同频率的图像信息接受程度的不同，即人类视觉对分布在不同频带上的图像信息具有不同的视觉敏感程度。本文为了区分不同区域的重要程度，同时保证不同区域的权重不至于失衡，所以设置热点区域和非热区域权重比例为2:1。

W_i表示i区域的权重值，则有

图2中的蓝线、绿线代表两辆车的轨迹，轨迹上的点代表每一次记录时车辆的地理位置。本文假设有m辆车，由集合$V=\left\{v_1,v_2,v_3,\cdots ,v_m\right\}$表示，在n个时间段$T=\{t_1,t_2,t_3,\cdots ,t_n\}$ 内运动。

2.2.1 车辆轨迹

车辆轨迹$L\left(V\right)$为m×n矩阵，表示为

其中，R为ROI的集合，K为ROI的数量，l_ij代表区域R内v_i在时间t_j的位置，l_ij∈R。根据车辆在各时刻的经纬度确定车辆的位置，构造候选车辆$L\left(V\right)$的轨迹矩阵。$L\left(V\right)$的行表示车辆在感知时间内的行驶轨迹，列表示某一时间段内所有候选车辆的位置。

2.2.2 覆盖次数的统计矩阵

P(V)是候选车辆到达ROI的次数的统计矩阵，表示为

其中，$P\left(V\right)$的行表示车辆到达k个区域的次数统计值。以图2中两辆车的轨迹为例，简单起见，假设车辆从左向右行驶。$L(v_1)=\left[AFKH\right]$ ，$L(v_2)=\left[EFBG\right]$ ，时间段为t₁～t₄，并且有

根据$P\left(V\right)$的定义，$P\left(v_1\right)=\left[100001010010\right]$ ，$P\left(v_2\right)=\left[010011100000\right]$，则有

设一个变量ϕ表示候选车辆v_i是否被选中，即

其中，Ω是从候选车辆集合V中被选出的车辆的集合，$\Omega \subseteq V$。

将矿工聚集的区域视作热点区域，对于热点区域，要进行重点的数据收集；而对于非热点区域，如果收集的数据量和热点区域的数据量一样，不仅会造成数据的冗余，通信开销增大，还会过度消耗额外的能量。所以本文假设条件之一就是对ROI进行非均匀覆盖。一方面减少能源的消耗，另一方面实现对热点区域的重点覆盖，同时对ROI整体的覆盖范围进行评估。本文提出了一个新的指标来衡量覆盖质量，考虑了CP和CD。其中，CD可以看作所选车辆到达热点区域而不是所有ROI的平均次数。

2.2.3 CD

CD的计算式为

其中，K₁表示ROI中热点区域的数量，${p^{\prime }}_{ij}$表示选中车辆v_i到达热点区域的次数，v_i∈Ω，并且有

CD是车辆到达热点区域的平均累积次数（并非所有ROI）。为了便于说明，图2中的热点区域为A、G、H、J，所以K₁=4，K=12。为了更清楚地表达CD的含义，相应的${p^{\prime }}_{ij}$显示在式(8)的实线框中。

通过计算可知，CD(v₁,v₂)=(1+0+1+0+0+1+0+0)/4=0.75，则在 t₁～t₄期间，v₁、v₂到达热点区域的平均次数为0.75。

CD 的引入是为了表示所选车辆在热点区域覆盖的情况，对热点区域覆盖的次数越多，则所收集的数据的准确度也会越高，即CD越大热点区域的数据也就越可信。文献[21]研究了WSN节点对区域的覆盖情况的影响，当至少存在K个节点覆盖该区域时，视为该区域被有效覆盖，研究结果表明，只有较少的区域可以满足有效覆盖的要求。文献[21]设计了一种离线计算的过程来达到选择最少的节点数来实现有效覆盖区域的CP要求，这一点和本文提出的问题不谋而合，因为本文考虑的热点区域覆盖次数问题和文献[21]提出的有效覆盖是同样的问题，本文考虑的热点区域的有效覆盖用CD表示。

2.2.4 CP

CP的计算式为

其中，W _k表示ROI中每个区域的权重，P_{i j}表示选中车辆v_i到达ROI的次数，v_i∈Ω。CP是选定的车辆集合Ω到达ROI的数量与感知区域总数K的比例，表示对ROI的覆盖范围，不同的任务可能需要不同类型的覆盖。如有些任务需要 ROI 的全覆盖，这时CP作为衡量标准比较适合；而CD衡量的是ROI热点区域的数据的可信度，当CD达到设定值时，认为数据可信。

应该注意的是，当多于一辆车经过同一区域时，P_ij计数一次。以图2中的v₁、v₂为例，它们在t₂时刻到达F，此时，仍然认为F被覆盖一次，因为本文关心的是总覆盖情况，那么重复覆盖只计数一次，在下面的虚线框中表示。

另外，车辆的感知成本记为 C，$C=\{c_1,c_2,c_3,\cdots ,c_m\}$ ，Ω 表示选中车辆的集合，C(Ω)表示所选车辆的总成本，所以$C\left(\Omega \right)=\left[C,\phi \right]$。本文的C_m～U (1,5)服从均匀分布。

2.2.5 覆盖质量的效用函数

本文衡量的覆盖质量主要包括CP和CD两个方面。覆盖质量的效用函数F(Ω)的优化目标是在感知成本预算B有限的约束条件下，实现MCS框架的高覆盖质量，计算式为

其中，α和β分别是CP、CD的权重系数。CP代表覆盖范围的大小，即有多少ROI可以实现覆盖，单位是百分比。CD表示覆盖密度，CD越大，得到的感知数据越可信。为了设定一个合理的α、β值，本文利用文献[4]中Leave-one-out方法调整α和β，在每次迭代中，只有一辆车不参与迭代，并从给定的α、β参数范围中选择可以最大化F(Ω)的α和β值。

文献[4]对均匀覆盖和最大范围覆盖问题进行了研究，量化了覆盖质量，覆盖质量$\Gamma =E_{cp}+\delta E_{ud}$由 E_cp（CP）和E_ud（覆盖均匀度）表示，覆盖均匀度表示的是节点空间的分布情况。当前大多数相关工作集中于如何在预算内获得ROI的最大CP，却较少关注热点区域的覆盖质量（可信度）问题，本文覆盖质量的效用函数F(Ω)的引入是为了在获得较大的CP的同时，使热点区域的覆盖质量也能够得到保障。

本文提出的问题是在有限的成本范围内选择合适的车辆去达到较优的覆盖质量，这是NP难问题。为了证明该问题是NP难问题，首先证明它属于NP问题。假设有可能的解决方案Ω′，Ω′可以在多项式时间内验证，并且检查算法的复杂度为O（n），因此该问题为NP问题。为了进一步证明该问题是NP难问题，对于给定集合$S=\{\begin{array}{c}{S}_1,S_2,\cdots ,S_n\}\end{array}$，每一个S_i都有对应的感知收益F_i和感知成本C_i，目标是找到$S^{\prime }\subseteq S$，满足相应的预算成本限制并获得较大的感知收益。此时问题也就转换为文献[24]中预算内最大覆盖范围问题（MCP,maximum coverage problem），而MCP已被证明为NP难问题，因而该问题为NP难问题。文献[24-25]详细地论证了该类问题是NP难问题。由于很难在多项式时间内找到一个NP完全问题的精确解，因此设计了近似算法。贪婪算法通常被用来解决该类问题，因此本文采用了贪婪算法，并对贪婪算法的指标进行了改进和优化。

本文使用了 3 种算法来优化效用函数F(Ω)，它们是随机选择算法、贪婪算法^[25]和本文提出的改进贪婪算法（CQO算法）。随机选择算法是从候选车辆中随机选取参与车辆进行计算仿真；贪婪算法的选择策略是选择尽可能多的车辆，从感知成本最低的车辆开始，直到达到成本预算的上限，将所选中的车辆添加到Ω集合中。

定义边际效用函数E_i为

其中，E_i是车辆在单位感知成本条件下获得的边际效用函数$F\left(v_i\right)$的增量，F(Ω′)是Ω′的效用函数， Ω′={Ω∪v_i}，v_i∈V-Ω。CQO 算法在成本预算限制下选择F(Ω)与感知成本比例最高的车辆参与感知任务，所以选择车辆的标准是从 Ω 中选择 E_i最大的车辆。F(Ω)是被选定车辆集Ω的效用函数。$\Delta F\left(v_i\right)$是由 v_i 得到的效用增量，它由F(Ω)和F(Ω′)计算得出。本文提出的 CQO 算法优先选择拥有最高边际效用函数E_i的车辆来优化覆盖质量。

CQO 算法的主要思想是将所有 m 辆候选车辆分成两组，一组是选定的集合，另一组是未被选择的集合。在每一轮选择中，从未被选择的集合中选出一辆新车并将其添加到选定的集合中；在每次选择迭代后计算效用函数F(Ω)，每次总是选择E_i最大的车辆，不断重复此过程直到成本预算B用完。根据选择策略，必须在每次迭代时遍历未选择集合中的每一辆车。在最坏的情况下，一共有m次选择迭代，因此计算复杂度为O(m²n)。CQO算法流程如算法1所示。

算法1 CQO算法

Input:$V=\left\{v_1,v_2,v_3,\cdots ,v_m\right\}$，$C=\{c_1,c_2,c_3,\cdots ,c_m\}$，B

Output:Ω

Ω=∅;S=∅;C_temp=0;

repeat

for S′⊆V,C (S′)≤B do

S=S′; max=0;

for v_i∈V -S do

S′={S′∪v_i},$\text{Δ}F(v_i)=F(S\text{'})-F(S)$;

if E_i>max and C(S′)≤B

S=S′

max=E_i

end if

if F (S)>F(Ω)

Ω= S

end if

end for

end for

在模拟实验中，本文采用了基于 Intel Core i7 3470 CPU的服务器，内存大小为12 GB。仿真工具为Python 3.7和MATLAB R2017b。

实验是在真实数据的基础上进行的，由于井下矿工的移动轨迹数据获取难度较大，因此对于本文提出的模型采用了文献[26]中的车辆轨迹数据集进行模拟，该数据集为一天内约4 300辆车的GPS坐标、时间、行驶速度等数据，如[id:105,time:2007-02-20 00:00:48,longitude:121.466600,latitude:31.220800]。

在将数据集导入仿真之前，首先对车辆的轨迹进行预处理，舍弃了采样频率过低的车辆。值得指出的是，文献[24-25]中启发式贪婪算法在每次循环中选择最大化$E_i=\frac{\text{Δ}F(v_i)}{c_i}$的对象，这与本文中车辆选择标准$E_i=\frac{\text{Δ}F(v_i)}{c_i}$ 是相同的。假设有两辆车，即F(v₁)=1的v₁和F(v₂)=h的v₂。设c₁=1,c ₂=h+1 (h>0)，B =h+1。 $E_1=\frac{1}{1}＞E_2=\frac{h}{1+h}$。选择v₁是满足预算限制条件且E_i最大化的合理选择。c₁+c₂ =h+2>h+1。而最优解选择v₂时，其效用函数F(Ω)的增益大于选择v₁，也满足要求。文献[24-25]更详细地说明了这个问题。所以 CQO 算法在参与者有限的情况下，所获得的结果并非总是最优的。

在本节讨论CD。将算法1的第8行、第9行的ΔF i)(v 用 CD 替代，也就是选择车辆的指标是$E_i=\frac{\text{ΔCD}(v_i)}{c_i}$ 。

车辆轨迹的示意图如图3所示，图3展示了100辆车在采样次数设为24次时的运动轨迹。车辆的CD分布如图4所示，图4为ROI内100辆车一天内采样24次轨迹的CD分布图，图例表示该区域被覆盖的次数。可以看到，实际的车辆覆盖并不是均匀地分布，而是以热点区域为中心分散分布，覆盖的不平衡性表明热点区域的覆盖质量可能优于其他区域，而不只是随机或均匀分布。离热点区域越远，该区域的覆盖次数越少。实际上，CD 与车辆的采样次数有关。较大的采样次数会使该区域更容易被覆盖，因此CD越大，成本越高。

经过算法仿真，CD 在不同预算成本、候选车辆数、感知采样次数下的对比如图5所示。

图5(a)展示了在不同预算成本下3种车辆选择算法的CD性能。横轴表示预算成本，纵轴表示CD。可以看出，CD 随着感知预算成本的增加而增加，预算成本越高意味着更多的车辆会被选中。

图5(b)是在固定预算成本下3种算法的候选车辆数对 CD 的影响。随着候选车辆数的增加，CD也呈现逐渐增加的趋势。当候选车辆数较少时，覆盖ROI的车辆数量有限。因此，候选车辆越多，能够覆盖ROI的次数也就越多。然而，由于感知预算成本有限，当候选车辆数达到80辆时，CD增加趋势不明显，这是因为之前所选的车辆几乎耗尽了感知成本。

图5(c)展示了3种算法在不同感知采样次数下的CD性能。横轴表示一天之内的车辆感知采样次数。T =12表示在一天内每2 h采样一次车辆轨迹， T=48表示每30 min采样一次。实验结果趋势可以近似视作直线，这一点很容易理解。当车辆感知次数增加时，收集的区域覆盖数据会增多，那么车辆覆盖ROI的次数也会增加，采样频率越高，采集和处理传感数据所需的能量就越多，如何在减小能源消耗和得到更高的CD之间获得平衡是一个亟待解决的问题。

CP是STC的另一种形式，CP将STC百分比化。CP与CD的不同之处在于，本文赋予热点区域比非热点区域更大的权重值 W。经过前期研究发现，CP 的实验结果随着成本预算、候选车辆数量和感知次数变化，CQO算法的性能也优于其他算法的性能，这与[6]中STC以及文献[4]中平均CP的性能相似，故CP的比较不在本文中赘述。

在本节中，将讨论包括CD和CP在内的效用函数F(Ω)。为了在保证CP的同时最大化CD，所以α设置为1。为了确定β的值，参考了文献[4]中的Leave-one-out方法。在经过计算后，当β=0.3时，CQO 算法可以得到最大$\frac{F_{\text{CQO}}-F_{\text{benchmarks}}}{F_{\text{benchmarks}}}$增益。因此，在 F(Ω)=α× CP+β× lg(CD) 中，设α=1,β=0.3，即F(Ω)=CP+0.3 lg(CD)。将贪心算法作为对比算法，所以此式等于$\frac{F_{\text{CQO}}-F_{\text{greedy}}}{F_{\text{greedy}}}$。

F(Ω)在不同预算成本、候选车辆数、感知采样次数下的对比如图6所示。从图6(a)可以看到，当预算成本低于60时，贪婪算法和CQO算法的性能相近，原因在于当成本较低时，只有更少的车辆可以被选中。然而，随着预算成本的增加，CQO算法的性能优于其他算法的性能。从图6(b)可以看出，在候选车辆数量从40辆增加到60辆期间，F(Ω)迅速增加，增速明显大于车辆数目从 60 辆增加到 80辆和从80辆增加到100辆期间的增速。通过分析车辆编号为 40～60 的候选车辆轨迹，发现这些车辆到达热点区域的频率比其他车辆高得多，所以这些车辆的CD要比其他车辆的CD大，F(Ω)也是同样的道理。由此可见，ROI的热点区域设置和候选车辆的行驶轨迹对实验结果有很大影响。图6(c)显示了不同算法在不同感知采样次数下的性能。总的来说，与图5(c)的仿真结果有些相似，都表现出线性增长的趋势。CQO算法同其他算法相比，性能依旧较好。感知采样次数的增加将不可避免地导致更高的成本，如通信成本和汽油成本。覆盖质量的提高，如感知数据数量和精度的提高，会消耗更多的能量。

在模拟实验过程中，发现了一些其他问题。本文所分析的车辆数据集中，有些车辆只是停滞在某个区域，并没有移动。当这个区域正好是热点区域时，那么CD是很大的；反之，CD就会很小。通过设置适当的 β 值可以缓解该问题对 F(Ω)的影响。

本文旨在分析在智慧矿山中数据采集的重要意义，基于矿山中车辆移动的特性，针对 MCS 模型，提出了一个综合考虑CP和CD的效用函数F(Ω)来衡量覆盖质量。本文要解决的问题是在有限预算成本下获得较好的覆盖质量，该问题已被证明是NP 难问题，因而提出改进后的贪婪算法——CQO算法。仿真验证表明，本文提出的 CQO 算法在仅考虑CD的情况下和在联合考虑CD和CP的情况下，与贪婪算法和随机选择算法两种算法相比，都达到了更好的覆盖质量。CD和效用函数F(Ω)在预算成本、候选车辆数和感知采样次数参数改变时都能够达到较好的稳定性，进一步研究了 CQO 算法的合理性。本文对效用函数F(Ω)的研究为智慧矿山IoT 面向人—机—环海量数据收集的性能优化提供了理论参考。