群智感知网络中的防御任务分配策略

Defense Task Allocation Strategy in Swarm Intelligence Sensing Networks

摘要: 在群智感知网络中，当执行由多个计算密集型任务组成的防御任务时，多个感知节点之间的合作是必要的。这一领域的大部分以前的工作都集中在节能和负载平衡上。然而，这些方案仅仅考虑了只需要一种资源的情况，这大大限制了它们的实际应用。为了减轻这种限制，在本文中，我们研究了复杂防御任务分配的问题，其中需要各种不同类型的资源。提出了一种基于启发式的算法来分配复杂的应用在群智感知网络。该算法分为两个阶段，在联盟间分配阶段，将防御任务的任务分配到各个联盟，以降低能耗；在联盟内分配阶段，将任务分配到适当的感知节点，兼顾能量成本和工作负载平衡。这样可以减少和平衡能量耗散，延长系统的使用寿命。

Abstract: In swarm intelligence sensing networks, when performing defense tasks composed of multiple compute intensive tasks, cooperation among multiple sensing nodes is necessary. Most of the previous work in this field focused on energy conservation and load balancing. However, these schemes only consider the situation that only one resource is needed, which greatly limits their practical application. In order to alleviate this limitation, in this paper, we study the problem of complex defense task allocation, which requires various types of resources. A heuristic algorithm is proposed to allocate complex applications in swarm intelligence sensing networks. The algorithm is divided into two stages. In the inter alliance allocation stage, defense tasks are allocated to each alliance to reduce energy consumption; in the allocation phase of the alliance, tasks are allocated to appropriate sensing nodes, taking into account the energy cost and workload balance. This can reduce and balance energy dissipation and prolong the service life of the system.

1. 引言

在许多现实场景中，群智感知网络将面临需要大量信息收集、大量计算操作和密集通信开销的防御任务 [1]。相比之下，作为一种小型、低成本和电池供电的设备，单个感知节点通常资源有限，可以执行相对简单的操作。因此，为了成功地执行复杂的防御任务，各种感知节点应该协同工作 [2]。具体来说，通过任务分解和分配，将一个困难的任务分解为几个不复杂的部分，每个子任务分配给一个能够独立处理的感知节点。一个典型的例子是第三代监视系统，其中许多摄像头连接到一个网络。对于这样的系统，一个常见的应用是检测、分类、本地化和识别一个对象；它涉及计算密集的操作，很难由单个节点执行。解决这个问题的一个很有前途的方法是将复杂的防御任务分解为简单的任务，并将它们分布到特定的感知节点中。通过这种方式，各种摄像机可以协同完成复杂的应用。因此，任务分配对群智感知网络的整体性能有着至关重要的影响，开发高效的协同任务分配策略在近年来的研究中受到了广泛关注。

虽然传统的分布式系统，包括多处理器系统 [3]、云计算 [4] 和社交网络 [5] 等，已经对任务分配问题进行了广泛的研究和很好的解决，但该问题在群智感知网络中具有独特的特点。由于群智感知网络中的感知节点通常由电池供电，且电源不可替代，因此容易因能量耗尽而失效。如果某些感知节点的能量在短期内耗尽，将无法在传感区域内采集到关键数据，这将严重削弱群智感知网络的功能。更严重的后果是，如果有太多的节点失效，通信链路将崩溃，整个网络可能无法工作。另一方面，感知节点网络中的感知节点需要均匀地消耗能量，工作负载平衡不佳可能会导致一些感知节点的能量消耗比其他节点早得多。

因此，如何降低和平衡能量消耗成为感知节点网络的一个理想设计目标 [6]。在感知节点网络的任务分配中也应该考虑到这个问题。现有的研究大多集中在感知节点之间合理分配计算和通信任务，通过负载均衡和节能来延长网络寿命。这些方法将任务分配建模为一个多目标优化问题，已被证明是NP困难的；因此，提出基于启发式的算法，以在多项式时间内解决该问题。

2. 问题描述

完成复杂防御任务的目标是找到一个应用于适当的感知节点，同时延长网络寿命。考虑到死亡节点的数量、感知覆盖范围、连接性等因素，网络寿命有多种定义。尽管这些定义涉及不同的指标，但它们都与两个要素有关：能耗和工作负载平衡。

因此，在本文中，的方案的目的是最小化能量消耗并平衡工作量。对于常规感知节点 $S_i$，其能量成本包含通信能量 $E_{comm}^i$ 和计算能量 $E_{comp}^i$，群智感知网络的能量消耗是完成防御任务的所有感知节点消耗的能量之和，可以表示为

$E_{WCSN}={\displaystyle \underset{i=1}{\overset{n}{\sum }}\left(E_{comm}^i+E_{comp}^i\right)}$ (1)

$E_{comm}^i=l{E}_{elec}+l{\epsilon }_{fs}{d}^2$ (2)

$E_{comp}^i=P^i{t}^i$ (3)

其中， $l$ 是要发送的数据量， $d$ 是传输距离， $E_{elec}$ 和 ${\epsilon }_{fs}$ 是依赖于硬件的参数，这些参数取决于数字编码模式、调制、可接受的误码率等， ${\epsilon }_{fs}$ 表示处理器的平均计算功耗，是处理防御任务所需的时间。

此外，负载平衡对网络寿命也有重要影响。由于感知节点 ${\epsilon }_{fs}$ 的负载与其能量耗散成正比，并且工作负载平衡是对群智感知网络中所有节点能量消耗状态的综合测量，因此可以表示为

$B_{WCSN}=\sqrt{\frac{1}{N}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\left(E_{resid}^i-avg\left(E_{resid}^i\right)\right)}^2}}$ (4)

其中， $E_{resid}^i$ 是节点 $S_i$ 的剩余能量， $avg\left(E_{resid}^i\right)$ 表示群智感知网络中所有节点的平均剩余能量。

根据以上描述，群智感知网络中复杂防御任务的协同防御问题可以表述如下

$R_{T_k}={\displaystyle \underset{S_i\in G_{T_k}}{\sum }{C}_{S_i}\cdot h(S_i),T_k\in T}$ (5)

其中 $\Lambda$ 是所有可行解的集合， $G_{T_k}$ 是任务 $T_k$ 分配到的联盟， $h\left(A_i\right)$ 是一个二进制变量， $h\left(A_i\right)=1$ 表示感知节点 $A_i$ 将为任务贡献其指定类型的资源，否则等于0。注意，这里的符号“=”是向量相等，这意味着两个向量的每个元素都相同。这意味着必须将防御任务给能够提供所有所需资源的协同防御联盟。从上述模型中，可以发现这是一个多目标优化问题。然而，这两个目标在某种程度上是不兼容的，甚至是相互冲突的，必须进行一些权衡才能获得性能良好的解决方案。

3. 防御任务分配算法

由于任务分配问题已被证明是一个NP完全问题，在本文中，提出了一个启发式算法在多项式时间内解决它。该算法可以简单地分为两个阶段，即联盟间阶段和联盟内阶段。第一阶段运行在基站上，其目的是以最小的电力成本将防御任务分配到协同防御联盟。之后，在每个联盟中，核心感知节点负责将任务分配到适当的感知节点，前提是任务能够成功执行，同时降低能耗和平衡工作负载。

3.1. 联盟间防御任务分配算法

群智感知网络具有分层结构，所有感知节点通过多边协商过程形成多个防御联盟。复杂防御任务由各种任务组成，每个任务都需要不同的资源，只有当所有任务都成功执行时，才认为复杂防御任务已完成。对于防御任务，可以将其分给任何将提供所需资源的防御联盟。

对于一个防御联盟，如果它想要完成一个子任务 $T_j\in T$，那么能量消耗包含两部分：计算能量和通信能量。由于计算和通信的特点具有相同类型感知设备的感知节点的能量耗散主要取决于普通感知节点与核心感知节点之间的距离。为了最小化防御任务的能源成本，应该将其分配给最靠近基站的防御联盟中具有必要资源的感知节点。另一方面，协同防御联盟系统的目标是在一个防御联盟只能执行一个任务的约束下，尽可能减少整个防御任务的能耗，理想状态是将所有任务分配给其能耗成本最低的防御联盟，且不重叠。

基站可以被视为负责完成复杂防御任务的执行者，动作是将每个防御任务给一个防御联盟，奖励是能量耗散，目的是找到一个能够最小化总能量消耗的防御任务执行方案。在本文中，采用并修改了DP算法，这是一种流行的方法，因为它简单且性能高，可以将复杂防御任务中的各个防御子任务给各个防御联盟。协同防御联盟间协作算法的核心思想是使用能耗值来组织和构造最佳方案的搜索。具体来说，算法可以分为两个步骤；在第一阶段，计算当前协同防御策略的能耗，然后通过最小化总能耗来改进策略。这个过程一直持续到收敛到最优解。从以上过程中，可以发现协同防御联盟间协作算法的核心是能量成本的计算。它可以定义为函数 $o:T\times \Omega \to R$ 其中 $o$ 是一组可能的防御任务执行策略，该值等于从当前开始，然后遵循 $\omega \in \Omega$ 策略的总能耗。

算法的第一个组件是初始化。本部分计算一个联盟的资源，等于联盟中所有感知节点的资源之和。对于任务 $T_j$，如果其所需的资源被联盟 $G_u$ 的资源覆盖，则将联盟 $G_u$ 视为 $T_j$ 的潜在联盟。然后将任务随机分配到能够执行该任务的联盟，生成应用分配的初始策略。同时，将每个任务的初始值设为0。迭代计算当前分配策略下的每个任务的值。 $E\left(T_j,G_u\right)$ 表示将任务 $T_j$ 分配给联盟 $G_u$ 的能量成本。

此外，任务 $T_j$ 的值不仅包含执行 $T_j$ 的能量消耗，还包含后续执行任务的能量消耗之后的当前应用程序分配策略，记 $V\left(T_j^{succ}\right)$。这里的变量 $V\left(T_j\right)$ 不是任务 $T_j$ 的值，它表示任务分配状态的值。如果当前的策略不是最优的，那么它将得到改进。能够为当前任务以及后续任务提供最小能量成本的联盟是首选的，通过迭代评估和改进当前的应用分配策略，可以得到最优的应用分配方案。

3.2. 联盟内防御任务分配算法

尽通过协同防御联盟间协作，复杂防御任务中的所有子任务都给了多个能耗最低的防御联盟。然后，与任务关联的核心感知节点负责将防御任务分发到防御联盟中的普通感知节点。因此，核心感知节点在协同防御联盟内协作过程中发挥着重要作用。在本文的模型中，一个复杂防御任务可以划分为几个子任务，每个子任务都需要特定类型的资源；所选节点应该具有一种类型的所需资源，可以保证任务能够执行。执行复杂防御任务的潜在目标是延长群智感知网络协同防御系统寿命；可以从两个方面实现：节能和负载平衡。

为了降低在协同防御联盟内协作的能耗，将每对普通感知节点与核心感知节点之间通信的能量成本降至最低非常重要。具有相同资源类型的每个普通感知节点在进行相同的计算量时将消耗相同的能量，即：从计算能耗的角度来看，能够提供相同类型资源的节点之间没有差异。通信能量成本与普通感知节点和核心感知节点之间的距离高度相关，距离越大，所需能量越大。为了最小化在协同防御联盟内协作的总能量消耗，最好将防御任务交给距离核心感知节点最近的节点去执行。但是如果总是选择这些节点来执行任务，那么它们的能量就会被过度使用，很快就会死亡。在这种情况下，协同防御联盟系统寿命将大大缩短。因此，很难找到一个协调一致的解决方案可以同时优化能量消耗和工作负载平衡，尽管对于每个单独的目标可能都有一个最佳解决方案。如上所述，为了延长协同防御联盟寿命，这两个目标在一定程度上是一对相互矛盾的指标，为一个目标提供良好性能的解决方案可能会使另一个目标的性能恶化。

因此，必须在这两个指标之间进行一些权衡，以实现全局优化。本文开发了一种有效的方法来处理能耗和负载均衡问题。主要思想是，对于具有所需资源类型的每个感知节点，它与一个概率相关联，该概率表示其被选为执行防御任务的成员的可能性。概率由两个因素决定，其中一个与能量相关，另一个与负载相关。为了在感知节点之间实现良好的负载平衡，分配给节点的工作负载应该与节点的剩余能量相匹配。通常，节点的剩余能量越低，被选中的概率越小。通过综合这两个因素，可以采用以下公式来评估节点为任务贡献资源 $q$ 的概率。

$p\left(A_i\right)=\left(1-\mu \right)\frac{{\eta }_i}{{\displaystyle {\sum }_{A_i\in G_u\cap S_{i}q}{\eta }_i}}+\mu \frac{E_{resid}^i}{{\displaystyle {\sum }_{A_i\in G_u\cap S_{i}q}{E}_{resid}^i}}$ (6)

其中， ${\eta }_i=\left(1/E^i\right)$ 表示节点 $A_i$ 能量成本的启发式信息， $E_{resid}^i$ 是 $A_i$ 的剩余能量， $\mu$ 是一个重要参数，允许用户调整能量成本和负载平衡之间的偏好容差。 $\mu$ 值越小，表明能耗越重要，而负载均衡的重要性越低。要计算 $p\left(A_i\right)$，需要两个参数， $E^i$ 和 $E_{resid}^i$。是感知节点 $S_i$ 执行任务的总能量消耗，可以通过轻松计算，因为所有变量值都预先已知。同时核心感知节点知道初始能量和功耗，它可以构建一个列表来记录每个感知节点的剩余，当感知节点执行防御任务时，列表中元素会更新。提出了一种协同防御联盟内协作的算法，该算法可以协同防御联盟完成防御任务的能耗和负载之间权衡。

在算法中， $B$ 表示选择出来执行防御任务的感知节点集，初始化为空。 $G_u^q$ 是当前联盟 $G_u$ 中拥有资源 $q$ 的节点集合，根据资源类型对具有任务所需资源的节点进行分类。然后，确定每一类中概率最大的节点，最终组成一组，协同执行任务。

4. 仿真试验

在本节中进行了试验，以客观评估的两阶段复杂防御任务分配策略在群智感知网络中的性能，该算法称为启发式算法。使用并修改了基于贪婪的分配方法和基于二进制粒子群的方法，并且将本文的方法与这两种方法进行了比较。基于贪婪的方法：复杂的防御任务首先随机分布到防御联盟，对于拥有特定任务所需资源的所有防御联盟，它们被选中执行任务的概率相同。通过贪婪启发式算法将防御任务给防御联盟内的各个感知节点；核心感知节点计算每个感知节点的能量耗散，这些节点可以匹配防御任务所需的资源，成本最低的节点将协同执行任务。基于二进制粒子群优化的方法：将所有感知节点根据其资源类型划分为若干组，在每个组中，使用粒子群算法确定一个感知节点，同时考虑能量消耗和负载平衡。但是在此框架中，群智感知网络具有扁平结构，所有感知节点都直接与基站通信。

由于启发式算法以最小化能量成本为目标向协同防御联盟分配防御任务，而贪婪算法随机执行防御任务，启发式算法优于贪婪算法。它说明了算法在协同防御联盟完成防御任务方面是有效的。图1显示了群智感知网络中所有节点的剩余能量的标准偏差，发现剩余能量标准偏差随着防御任务的执行而增加。所提出的算法优于其他两种方法，这意味着启发式算法可以更均匀地将防御任务给感知节点。当应用数量较大(大于约190)时，粒子群优化算法的剩余能量标准偏差减小。这是因为对于粒子群优化算法而言当分配更多防御任务时，节点显著减少，最终，大多数感知节点的剩余能量降至0或接近0。在这种情况下，标准偏差也将下降。

Figure 1. Influence of the number of defense tasks on the standard deviation of residual energy

图1. 防御任务数量对剩余能量标准差的影响

最后一个实验是为了研究关于存活感知节点数量的性能，是群智感知网络群智感知网络协同防御系统寿命的间接说明。结果如图2所示。随着防御任务数量的增加，粒子群优化算法的存活感知节点数量急剧下降，而启发式算法只有极少数节点死亡，贪婪算法有一部分感知节点死亡。因为，启发式算法采用了降低能耗和负载均衡的技术，这对延长单个感知节点的寿命非常有益。相反，对于粒子群优化算法，感知节点将信息直接传输到基站，这严重消耗了感知节点的能量，大量节点在短时间内死亡。对于贪婪算法，尽管感知节点与核心感知节点进行通信，但它忽略了负载平衡，过度使用的节点会迅速耗尽其能量。

Figure 2. Influence of the number of defense tasks on the number of surviving nodes

图2. 防御任务数量对存活节点数量的影响

5. 总结与展望

在文中，讨论了群智感知网络中的复杂防御任务分布问题。一个复杂的防御任务由多个任务组成，每个任务需要各种类型的资源。目标是将复杂的防御任务分布到适当的感知节点，以延长系统的生命周期，同时确保每个任务所需的资源可以被节点的资源覆盖。为此，提出了一种基于两阶段的应用分配算法。首先，采用基于dp的方案将复杂防御任务中的所有任务分配到多个联盟中，以最大限度地降低能耗延长系统整体寿命。然后，在联盟内部，通过防止单个节点过度使用的反馈机制，将任务进一步分配给感知节点。特别地，提供了一个参数，允许终端用户调整节能和工作负载平衡之间的重要性，保证了系统中感知节点的存活数量。实验结果表明，与基于贪心算法和粒子群优化算法相比，该算法在能耗和负载均衡方面都取得了较好的性能。

在本文中，可以不受时间限制地分配防御任务。但是，在某些场景中，需要在有限的时间内分发 [7] 和执行防御任务 [8]。在未来，将扩展该方法，考虑到申请截止日期，可以提供实时保障。与此同时，近年来，移动汇聚技术的出现是进一步降低群智感知网络能耗的一种很有前景的方法，因此，另一个有趣的未来方向是在具有移动汇聚的群智感知网络中解决这一问题。

基金项目

哈尔滨师范大学研究生培养质量提升工程“新工科背景下创新创业型研究生多维培养模式的研究——以网络安全方向研究生培养为例”和哈尔滨师范大学本科专业人才培养方案研究改革专项(XJGRYK2022012)。

参考文献