多媒体物联网系统中协作视频处理的边缘计算框架

摘要

多媒体物联网（IoT）系统已广泛应用于监控、自动行为分析和事件识别，这些系统集成了图像处理、计算机视觉和网络能力。在传统多媒体物联网系统中，监控摄像头拍摄的视频需要传输到远程物联网服务器进行视频分析。然而，由于网络带宽有限，大量视频块的远距离传输可能导致拥塞和延迟。如今，移动设备（如智能手机和平板电脑）在计算和通信能力方面资源丰富。因此，这些设备有望为远程物联网服务器提取视频特征。通过仅向远程服务器回传少量视频特征，可以避免传输原始视频块时的带宽不足问题。本文提出了一种边缘计算框架，以实现资源丰富的移动设备对延迟敏感的多媒体物联网任务的协同处理。我们发现，所提出的边缘计算框架中的关键挑战在于如何将移动设备最优地组成视频处理组，并将视频块分发到合适的视频处理组。基于推导出的最优匹配定理，我们提出了一个由两个高效算法组成的协同视频处理方案来应对上述挑战，该方案在人体检测精度上实现了次优性能。所提方案已在多种参数设置下进行了评估。大量仿真结果证实了所提方案相较于其他两种基线方案的优越性。

关键词 —边缘计算，多媒体物联网，协同视频处理，人类检测准确性。

I. 引言

近年来，随着无线传感器网络、短距离无线通信和4G/5G蜂窝通信等通信与网络技术的快速发展，物联网（IoT）正在演变为一种实现物理对象与人类在智慧城市/家居等场景中互联的范式[1],[2]。作为一种新兴的物联网类型，多媒体物联网系统集成了图像处理、计算机视觉和网络功能，并已得到广泛应用，在监控（例如人/车辆检测）、自动行为分析和事件识别 [3],[4]中，存在两种传统范式：1）在摄像头节点对捕获的视频块进行预处理（例如从视频中提取特征），以及2）将视频块传输到远程物联网服务器直接处理。然而，[5]中的测量结果表明，上述两种范式会导致显著的延迟。原因在于，摄像头节点有限的计算资源在本地预处理视频时可能引起计算延迟，而将原始视频块传输到远程服务器则可能由于网络带宽受限导致拥塞和延迟。因此，这两种范式无法满足延迟敏感型视频处理与分析任务的需求。

最近，边缘/雾计算作为一种新兴技术被引入，用于实现视频块的分布式预处理，从而减少传输延迟[6]。通过利用边缘计算技术，邻近多个移动设备的冗余计算和通信能力可以被用来通过短距离无线通信处理对延迟敏感的视频处理和分析任务。视频任务可以被划分为子任务，并由边缘节点（即具有冗余资源的移动设备）进行预处理[7]。普遍观察到，在实际场景中，边缘节点的数量多于视频子任务的数量。如果一个子任务仅分配给一个边缘节点，则其余边缘节点的冗余计算资源将得不到充分利用。因此，研究如何适当地将多个边缘节点组成不同的组并协同处理视频子任务具有重要意义，而这一问题尚未得到充分研究。

人体检测是多媒体物联网系统中的一项典型视频任务 [8]。通常，压缩视频片段中的噪声和失真可能会严重影响人体检测的效率，因此对采集到的视频块进行压缩是影响人体检测精度的关键因素。本文提出了一种边缘计算框架，以提高多媒体物联网系统中的人体检测精度，其中多个边缘节点可以相互协作，从而提升视频任务预处理性能 [9]。我们发现，所提出的边缘计算框架中的关键挑战在于将边缘节点组成视频处理组，并将视频子任务调度到合适的视频处理组。因此，在设计协同视频处理方案时，需要解决上述两个挑战。具体而言，该协同视频处理方案的目标是最大化人体检测精度。

II. 相关工作

本节旨在从两个方面讨论相关工作，即通用任务卸载和协同处理，具体如下。

A. 任务卸载

如[10],所述，边缘计算面临的主要挑战之一是任务卸载，即如何将任务合理划分为多个子任务，并高效地分配给附近的边缘节点。一种广泛研究的用于指导任务卸载的理论称为可分负载理论（DLT）[11]。该方法首先将可分任务划分为多个不同大小的子任务，然后由计算节点独立处理，以实现最短完成时间。基于可分负载理论的基本思想，[12]和[13]的研究人员分别提出了最优划分方法和最优负载分配方法。特别地，[13]推导出一个普遍结论：若所有处理器同时完成处理，则达到最短完成时间。此外，在[14],[15],中研究了两个问题，即所有处理器工作时的最短完成时间和满足应用截止时间所需的最少处理器数量。上述研究主要探讨如何划分任务并将子任务分配给边缘节点，以在截止时间之前完成任务。然而，对于某些任务而言，关键是在截止时间内获得最佳的处理结果，而不仅仅是考虑最短完成时间，例如在视频监控系统中对视频任务进行高质量的预处理，这有助于提升后续步骤中视频分析的性能。

B. 协同处理

除了任务卸载外，一些研究还考虑了协同处理以提升系统性能。例如，文献[9]中的作者提出在满足特定完成时间要求的同时，最小化移动无线传感器网络（ MWSN）中处理任务的能耗。具体而言，他们引入了协作的概念，即相关的计算任务可以在对等传感器节点的帮助下被最优地划分、卸载和执行。不同于[9],，文献[7]中的作者联合考虑了不同的传输速率和多种传输模式（即多播和单播），以最小化完成视频序列的分布式视觉分析所需的时间。然而，该工作仅考虑将子任务分配给边缘节点，未考虑边缘节点组之间的协同处理。

综上所述，基于分布式账本技术和协同处理方法，本文提出了一种面向延迟敏感型视频任务的边缘计算框架，旨在截止时间内最大化人体检测精度，这一问题尚未得到充分研究。特别地，我们考虑了不同的传输速率、边缘节点以组为单位的协作、视频任务划分、子任务的压缩与分配，这些带来了两个主要挑战：如何将边缘节点最优地组成视频处理组，以及如何将视频子任务调度到合适的组中。

III. 所提出的边缘计算框架

在本节中，我们首先对所提出的用于协同视频处理的边缘计算框架进行概述。随后，分别详细介绍了通信、计算模型以及人体检测精度与平均视频编码码率之间的关系。

A. 框架概述

在所提出的面向延迟敏感型视频任务的边缘计算框架中，我们考虑如图1所示的场景，其中摄像头节点固定在路灯顶部，可通过设备到设备（D2D）通信将视频任务卸载至附近的边缘节点[16], ，而边缘节点（例如移动设备）位于D2D通信范围内。摄像头节点捕获视频序列（即视频任务），将每个视频序列划分为多个视频子任务，并对这些视频子任务进行压缩（以视频块）并将其传输到边缘节点。然后，边缘节点处理接收到的视频子任务，并通过长期演进（LTE）网络将计算结果上传至基于云的物联网服务器，以进行进一步视频分析，例如人体检测。本文中的延迟敏感型视频任务指的是由摄像头节点捕获的视频序列，该任务需在截止时间前完成处理，否则将被丢弃。

所提出的框架的架构如图2所示，包含三个主要组件，即摄像头节点、边缘节点和服务器。
- 摄像头节点 ：这可以是一个固定在路灯顶部的固定摄像设备，用于调用视频任务，将任务划分为更小的子任务（视频块），压缩视频块，并最终通过设备到设备通信将它们传输到一定距离范围内的边缘节点。
- 边缘节点 ：这是一种具有足够计算能力和存储容量的移动设备，用于帮助处理视频子任务，例如图像特征检测和提取。边缘节点根据所提出的组形成算法形成协作组，并依据视频‐组匹配算法接收压缩视频片段（分别见第五节、第六节）。
- 服务器 ：这是一个静态设备，用于收集来自边缘节点的处理结果并进行进一步视频分析，具有强大的计算能力。

摄像头节点周期性地捕获视频序列，然后对其进行一些操作。以一个视频任务为例，摄像头节点将其划分为固定数量且大小相同的视频块，以不同的视频编码率压缩视频块，并根据所提方案将压缩后的视频块分配给所有边缘节点。摄像头节点通过两种传输模式将视频块传输到边缘节点，即多播模式和单播模式。在多播模式下，一个视频块同时传输到一组中的多个边缘节点，这些边缘节点协同处理该视频块的不同部分。在单播模式下，一个视频块仅传输到一个边缘节点。为了简化问题，本文不考虑如何协调组内边缘节点协作的具体操作。同时，我们假设一组中的边缘节点处理大小相同的非重叠分区。在完成指定的视频任务后，边缘节点通过蜂窝链路将结果传输到服务器。最后，服务器执行视频分析，其中以人体检测作为示例说明。

B. 通信与计算模型

在本文中，我们考虑一种基于正交频分多址（ OFDMA）的蜂窝网络，该网络支持设备到设备（D2D）通信模式。摄像头节点通过D2D链路与边缘节点通信，边缘节点通过蜂窝链路将数据传输至服务器。我们假设所有 D2D链路共享一个信道，并且时间被均等地划分为时隙，每个时隙持续几毫秒[17]。也就是说，视频块只能逐个传输到边缘节点。根据[7], ，将从摄像头节点到边缘节点的传输时间建模为所传输视频块大小的线性函数是合理的。因此，从摄像头节点到边缘节点n的传输速率表示为 Cn ms ，其定义为单位时间内传输的数据量，例如1MB/s。同时，C n ms 被定义为 C n ms 的倒数，例如1s/MB，因此 C n ms 越大，对应的传输速率越小。由于许多视频任务的输出数据仅为一条短消息，在考虑大量输入数据时可以忽略不计[14]。因此，服务器收集视频处理结果所花费的传输时间可以忽略。在使用多播传输模式时，组传输速率由可实现最低传输速率的边缘节点决定[16]。

不失一般性，我们假设每个边缘节点具有相同的计算速率C p s ，其定义为单位时间内处理的数据量，例如0.2MB/s。同时，˜ C p s 被定义为 C p s 的倒数，例如5s/M，因此˜越大，相应的计算速率越小。这里给出了采用所提方案与使用现代多核计算机处理视频任务的对比，所提方案具有以下特点：1）大约十个边缘节点（例如移动设备）可以拥有与多核计算机相同的计算能力[18]；2）无需部署额外设备，并充分利用了边缘节点的冗余计算资源；3）传输延迟显著降低。

表I 重要符号
| 符号 | 定义 |
| — | — |
| N | 边缘节点数量 |
| L | 视频块数量 |
| N | N={1, 2,…, N}，边缘节点集合 |
| L | L={1, 2,…, L}，视频块集合 |
| Ng | Ng={N1 g, N2 g,…, N L g}，组的集合 |
| Ng∗ | Ng∗={N1 g∗, N2 g∗,…, N L g∗}，最优组集合 |
| C˜ms | C˜ms ={C˜1 ms, C˜2 ms,…, C˜N ms}，所有边缘节点的传输速率的倒数集合 |
| C˜ps | C˜ps={C˜1 ps , C˜2 ps ...， C˜N ps}，所有边缘节点的计算速率的倒数集 |
| C˜msg | C˜msg={C˜1 msg , C˜2 msg ...， C˜L msg}，所有组的传输速率倒数的集合 |
| C˜psg | C˜ psg ={C˜ 1 psg, C˜ 2 psg,…, C˜ L psg}，所有组的计算速率的倒数的集合 |
| C˜msg∗ | C˜msg∗={C˜1 msg∗ ，C˜2 msg∗ ，...，C˜L msg∗} ，传输速率倒数的集合 |
| C˜psg∗ | C˜psg∗={C˜1 psg∗ , C˜2 psg∗...， C˜ L psg∗} ，计算速率倒数的集合 |
| G | The L× L视频‐组匹配矩阵 |
| Gi,j | Gi,j = 1如果视频块 i被分配到组 j |
| ti | 视频块 i ∈ L 的完成时间 |
| T | 给定视频任务的完成时间 |
| D | 给定视频任务的截止时间 |
| S | 每个视频块在压缩前的原始大小 |
| α | α={α1 ,α 2 ,…,αL}，所有 L 的视频编码率的集合 |
| β | β={β1 , β 2 ,…, β p} ，每个视频块的视频编码比率等级集合 |
| r | r={r1 , r 2 ,…, r L}，所有视频块的编码率集合 |
| A j i | 匹配序列 j的视频编码比率之和，当存在 i视频块 |

C. 人体检测精度与视频编码率之间的关系

在本小节中，我们首先将人体检测精度建模为视频编码率的函数，然后发现在此过程中，通过最大化视频编码率即可实现人体检测精度的最大化。根据[8], ，我们可以使用量化参数(QP)（通常用于衡量视频质量，QP越大，视频质量越低）来建立视频编码率与人体检测精度之间的关系。具体而言，采用两个方程将视频的QP与这两个参数关联起来。首先，QP可以表示为视频编码率的函数，即以下方程。
$$ q(rb)= \frac{1}{c2} \log_2(rc1b), $$
其中， q(rb) 表示对应于平均视频编码码率 rb、 c1 ≥ 0 和 c2 ≤ 0 的量化参数。此外，人体检测精度也可以表示为量化参数的函数，如下方程所示。
$$ P(q)= a ∗ 2^{uq}+ b, $$
其中 P(q) 表示对应于量化参数 q, a< 0, b> 0 和 u> 0 的人体检测精度。然后，结合上述两个方程，我们可以推导出人体检测精度与平均视频编码率之间的关系如下。
$$ P(rb)= a ∗(cr1b )^{\frac{u}{c 2}}+ b, $$
其中 P(rb)表示对应于视频编码率 rb的人体检测精度。根据公式(3)，可以推导出人体检测精度与平均视频编码率呈正相关。因此，在接下来的第四节中，采用最大化平均视频编码率的方案，而非直接优化人体检测精度。

IV. 问题建模与分解

通过利用第三节中所提出的框架，我们可以根据传输速率、计算速率以及人体检测精度与平均视频编码率之间的关系等信息，将视频任务卸载到边缘节点。为了基于上述信息优化人体检测精度，本节提出了如何联合进行任务划分、压缩以及子任务分配以最大化所有视频块的平均视频编码率的问题建模。具体而言，第四节A部分和第四节B部分分别讨论了问题建模及所推导出模型的分解。

A. 问题建模与分析

在本小节中，我们首先给出三种约束，即截止时间约束、组形成约束和匹配约束，然后提出如何联合分割任务、压缩并分配子任务以在截止时间内最大化所有视频块的平均视频编码率的问题。

首先，我们给出原始问题的约束条件。

1) 截止时间约束 ：视频任务必须在给定的截止时间内完成。
$$ t_i = \sum_{k=1}^{i} \sum_{j=1}^{L} G_{k,j} \alpha_k S \tilde{C} {j}^{msg} + \sum {j=1}^{L} G_{i,j} \alpha_i S \tilde{C} {j}^{psg} $$
$$ T= \max{t_i | i \in L} $$
$$ T \leq D, $$
其中， t_i 表示视频块 i的完成时间，T表示视频任务的完成时间（即所有视频块中最大的完成时间）， D表示视频任务的截止时间。这里， t_i 包含两部分，即$\sum {k=1}^{i}\sum_{j=1}^{L} G_{k,j} \alpha_k S \tilde{C} {j}^{msg}$ 和$\sum {j=1}^{L} G_{i,j} \alpha_i S \tilde{C}_{j}^{psg}$，前者为传输前者 i视频块的传输时间（此处，视频块依次传输），后者是视频块 i的处理时间。约束条件(6)确保视频任务必须在截止时间之前完成处理。

2) 组形成约束 ：边缘节点形成协作的、非重叠的组来处理视频块。
$$ n_j= |N_j^g| \neq 0, \forall N_j^g \in Ng $$
$$ \tilde{C} j^{msg}= \max{\tilde{C}_u^{ms} | u \in N_j^g} $$
$$ \tilde{C}_j^{psg}= \tilde{C}^{ps}/n_j $$
$$ \sum {j=1}^{L} n_j \leq N $$
$$ N_d^g \cap N_e^g= \varnothing, \forall d \neq e, d, e \in L, $$
其中， nj表示第j组中边缘节点的数量， $\tilde{C}_j^{msg}$和 $\tilde{C}_j^{psg}$ 分别表示组 j的传输速率倒数和计算速率倒数。 $\tilde{C}_j^{msg}$ 表示第 j组中所有边缘节点的最小传输速率的倒数。同时，由于假设每个边缘节点的计算速率相同，因此 $\tilde{C}_j^{psg}$等于 $\tilde{C}^{ps}/n_j$。约束(7)确保每组至少包含一个边缘节点。约束 (10)确保所有组中的边缘节点数量不超过总数，而约束 (11)确保每个边缘节点只能加入一个组。

3) 匹配约束 ：
$$ \sum_{j=1}^{L} G_{i,j}= 1, i \in L $$
$$ \sum_{i=1}^{L} G_{i,j} = 1, j \in L $$
$$ G_{i,j} \in{0, 1}, $$
其中$G_{i,j} = 1$ 如果视频块 i 被分配给组 j，且$G_{i,j} = 0$ 如果未分配。这里，约束(12)确保每个视频块只能由一个组处理，约束(13)确保每个组只能处理一个视频块。也就是说，视频块和组之间是一一对应的。

基于上述约束(4)–(14)，我们给出以下优化问题：
$$ P0 \quad \max f(\alpha)= \frac{1}{L} \sum_{i=1}^{L} r_i $$
$$ s.t.:(4)-(14) $$
$$ r_i = \alpha_i S, i \in L, \alpha_i \in \alpha $$
$$ \alpha_i \in \beta={\beta_1 , \beta_2 ,…, \beta_p} , i \in L, $$
其中 f(α)表示总体目标函数，即最大化所有视频块的平均视频编码率， r_i 是视频块 i的编码率，同时视频块的视频编码比率（α i ∈ α）和匹配矩阵（G）为变量， β是每个视频块的视频编码比率级别集合。基于人体检测精度与平均视频编码率呈正相关的事实，最大化所有视频块的平均视频编码率的目标等同于最大化人体检测精度。此外，

约束(15)是每个视频块的编码速率公式，约束(16)给出了每个视频块的视频编码比率级别集合。

显然，问题 P0是一个整数非线性规划问题，属于NP难问题。其计算复杂度为 O(N! (N−L)!L N−LpLL!)，其中 N是边缘节点总数， L是视频块数量，p是视频编码比率等级的数量。因此，降低原始问题 P0的计算复杂度至关重要。

B. 组形成与视频组匹配子问题

在本小节中，我们首先将问题 P0分解为两个子问题，即组形成子问题和视频‐组匹配子问题，然后给出一个简单示例来说明这两个子问题以及所提出的框架的工作流程。

将问题 P0分解为两个子问题的原因如下：如性能评估所示（见图6），最优解与所提方案之间的性能差距相对较小。此外，理论分析（见第五节和第六节）表明，这两个子问题的计算复杂度远低于原始问题。因此，将原始问题 P0分解为两个子问题是可行的。接下来，我们分别通过图3和图4对这两个子问题及其工作流程进行简单说明。

图3和图4分别展示了当存在六个边缘节点和三个视频块时的子问题和工作流程。根据图3可知，组形成问题是如何利用六个边缘节点形成三个协作组。视频‐组匹配问题是确定三个视频块与三个已形成组之间的最优匹配。此处给出一个可能的解决方案：每个组的组成如下，组1由边缘节点1构成，组2由边缘节点2、3和4构成，第3组由边缘节点5和6构成。此外，视频块1、2、3分别传输至组2、1、3。

在图4中，三个视频块具有相同的原始大小，在摄像头节点处根据所提方案以不同的比率进行压缩。具体而言，每个视频块的视频编码比率级别由所提方案的两个组成部分决定，即组形成算法和视频组匹配算法（见第五节、第六节）。此外，由于压缩视频相比处理和分析视频不需要很强的计算能力，因此本文忽略了压缩视频块所花费的时间。然后，压缩后的视频片段被传输到协作组进行处理。

V. 组形成问题的解决方案

在本节中，我们结合边缘节点的特性（即从摄像头节点到边缘节点的传输速率以及边缘节点的计算速率）对组形成问题进行建模，并设计了一种算法来解决该问题。通过分析组形成问题的数学形式，我们发现它可以转化为胜者判定问题的标准形式。因此，我们将组形成问题建模为一个胜者判定问题，并利用贪心算法对其进行求解。

A. WDP描述

在本小节中，给出胜者判定问题的简要定义。胜者判定问题是指：在组合拍卖中，给定一组投标，寻找一种将物品分配给投标者的分配方式，以最大化总体效用[19]。

定义1.（WDP） 给定一组投标 $v_i$, $i \in Q$，胜者判定问题是指计算
$$
x \in \arg\max\left(\sum_{i \in Q} v_i(B)x_i(B)| x \text{ satisfies }(17),(18)\right).
$$
$$
\sum_{i \in Q} \sum_{B \subseteq M, j \in M} x_i(B) \leq 1, \quad \forall j \in M \tag{17}
$$
$$
\sum_{B \subseteq M} x_i(B) \leq 1, \quad \forall i \in Q, \tag{18}
$$
其中 $x$ 是最大化整体效用的物品最优分配集合，bubble $B$ 是物品的一个子集（即 $B \subseteq M$)，投标者和物品的集合分别表示为 $Q$ 和 $M$。 $v_i(B)$ 定义为投标者 $i$ 对气泡 $B$ 的打包投标，例如，投标者 $i$ 愿意为气泡 $B$ 支付的最高价格。当且仅当投标者 $x_i$ 获得气泡 $B$ 时，$x_i = 1$ 成立。约束条件(17)和(18)分别确保每个物品最多只能被分配一次，且每个投标者最多只能获得一个气泡。

B. 组形成问题

在本小节中，我们将组形成问题建模为胜者判定问题的形式，即定义投标者的效用及其最大化所有投标者总体效用的目标。然后，给出了一种贪心算法。为了简化起见，边缘节点按照传输速率的降序排列，即 $C˜1^{ms}< C˜2^{ms}<…< C˜N^{ms}$（它是传输速率的倒数，单位为秒/兆字节，该值越大，传输速率越小）。我们将前 $L$ 个边缘节点定义为投标者 $I={1, 2,…, L}$，其余边缘节点定义为物品 $\Delta={1, 2,…, \delta}$，以及 $\delta= N - L$。气泡 $B$ 是一组物品，并满足 $B \subseteq\Delta$。对于一个投标者$i$和气泡 $B$，我们定义 $υ_i(B)$为投标者 $i$对气泡 $B$所出的效用，该效用定义为视频块的减少的完成时间（减少的延迟）。

1) 效用函数 ：如果投标方 $i$ 获得气泡 $B$，减少的计算时间和增加的通信时间分别表示为 $t_i^{ps}(B)$、 $t_i^{ms}(B)$。两个公式如下所示：
$$
t_i^{ps}(B)= \frac{S \tilde{C}^{ps}}{n_B+ 1} \tag{19}
$$
$$
t_i^{ms}(B)= S(\tilde{C}_i^{msg}(B)- \tilde{C}_i^{ms}), \tag{20}
$$
其中，投标人 $i$获得气泡 $B$后，组 $i$的传输速率的倒数表示为 $\tilde{C}_i^{msg}(B) = \max{\tilde{C}_j^{ms} |j \in B⋃{i}}$， $S$是每个子任务的大小，气泡 $B$所包含的物品数量表示为$n_B= |B|$。

我们将减少的完成时间定义为效用，因此效用函数为：
$$
v_i(B)=\begin{cases}
t_i^{ps}(B)- t_i^{ms}(B) & \text{if } t_i^{ps}(B)> t_i^{ms}(B) \
0 & \text{else.}
\end{cases} \tag{21}
$$

2) 组形成的目标函数 ：根据每个投标者对所有气泡的效用，组形成问题 $P1$的目标是最大化所有投标者的总体效用。
$$
P1 \quad \max \sum_{i \in I} \sum_{B\subseteq \Delta} x_i(B)υ_i(B)
$$
$$
\text{s.t.: } \sum_{B \subseteq \Delta} x_i(B) \leq 1, \quad \forall i \in I \tag{22}
$$
$$
\sum_{B: d \in B} \sum_{i \in I} x_i(B) \leq 1, \quad \forall d \in\Delta, \tag{23}
$$
其中 $x_i(B) = 1$如果竞标者 $i$获得气泡 $B$ ，否则$x_i(B) = 0$。约束(22)确保每个竞标者最多只能获得一个气泡，约束(23)表示每个项目不能被多次出售。

3) 一种贪心算法 ：胜者判定问题为NP难问题，无法在多项式时间内求解[19]。因此，组形成算法1用于组形成的贪心算法输入所有投标者的集合， $I$； 所有物品的集合， $\Delta$； 输出： 1: 设置 $B_i= \emptyset, \forall i \in I$和 $S= \Delta$； 2:当 $S \neq \emptyset$ 时执行 3:令$(i, j) \in\arg\max(v_i(j | B_i)| i \in I, j \in S)$; 4:设置 $B_i= B_i \cup{j}, S= S\backslash{j}$； 5:结束循环 6: 对所有 $i \in I}$ 返回 ${B_i |$。该问题也是NP难的。如果我们采用穷举攻击算法来解决该问题，其计算复杂度为 $O(L^\delta)$，其中 $L$是投标者数量， $\delta$是物品数量。因此，本文给出了一种贪心算法，其具体细节见算法1。根据[20],，该贪心算法是2‐近似的，即贪心算法获得的总体效用至少是最优解的一半。

贪心算法的基本思想：基本思路是按任意顺序枚举物品，并将每个物品逐一分配给在当前分配情况下具有最大边际效用（见定义2）的竞标者。例如，第一个物品被分配给通过获得该物品能够得到最大效用的竞标者。在第一个物品分配完成后，第二个物品被分配给因获得第二个物品而产生最大边际效用的竞标者。该分配过程将持续进行，直到所有物品都被分配完毕。

定义2. 边际效用 ：给定在集合X的物品上的估值 $\xi$ 以及一组物品集合 $W \subseteq X$，则集合 $A \subseteq X - W$的边际估值由(24)给出，其函数值为边际效用：
$$
\xi(A | W)= \xi(A \cup W)- \xi(W). \tag{24}
$$

定理1. 贪心算法的计算复杂度为 $O(\delta L)$，其中 $L$是视频块总数， $\delta$是物品数量。

证明 。根据算法1，每次迭代中，我们分配一个物品并计算 $L$次相应的估值 $υ$。此外，由于共有 $\delta$个物品需要分配，因此存在 $\delta$次迭代。因此，贪心算法的计算复杂度为 $O(\delta L)$。

VI. 视频‐组匹配问题的解决方案

在本节中，通过视频‐组匹配子问题将视频块分发到合适的视频处理组。首先，根据第五节中的组形成算法，去除组形成约束，将原问题 $P0$转化为问题 $P2$。然后，提出并证明了最优匹配定理（定理2），在此基础上去除匹配约束，将问题 $P2$ 转化为整数线性规划问题 $P3$ 。最后，提出了一种低复杂度启发式算法来求解问题 $P3$。

通过求解 $P1$获得协作组集合 $Ng^ ={N_1^{g },…,N_L^{g }}$，每个组由 $N$中的边缘节点˜ ˜组成。相应地，我们可以得到 $\tilde{C}_{msg}^ $和 $\tilde{C} {psg}^ $，它们分别是组传输速率和组计算速率的倒数组成的集合。 $\tilde{C}_{msg}^ $和 $\tilde{C} {psg}^ $中的元素可分别通过 $\tilde{C}_i^{msg }= \max{\tilde{C} j^{ms}|j \in N_i^{g }}$和 $\tilde{C}_i^{psg }= \tilde{C}^{ps}/n_i^{g }= |N_i^{g }|$是组 $N_i^{g }$所包含的边缘节点数量。为简便起见，我们假设协作组按传输速率降序排列，即 $\tilde{C}_1^{msg }<…< \tilde{C}_L^{msg }$（它是传输速率的倒数，单位为秒/兆字节，该值越大表示传输速率越小）。基于上述形成的组，组形成约束(7)–(11)被移除，问题 $P0$被转化为子问题 $P2$，具体如下所示：
$$
P2 \quad \max f(\alpha)= \frac{1}{L} \sum_{i=1}^{L} r_i
$$
$$
\text{s.t.: } r_i= \alpha_i S, i \in L, \alpha_i \in \alpha \tag{25}
$$
$$
t_i= \sum_{k=1}^{i} \sum_{j=1}^{L} G_{k,j}\alpha_k S \tilde{C}_j^{msg } + \sum {j=1}^{L} G_{i,j}\alpha_i S \tilde{C} j^{psg*} \tag{26}
$$
$$
T= \max{t_i | i \in L} \leq D \tag{27}
$$
$$
\sum {j=1}^{L} G_{i,j}= 1, i \in L \tag{28}
$$
$$
\sum_{i=1}^{L} G_{i,j} = 1, j \in L \tag{29}
$$
$$
\alpha_i \in{\beta_1, \beta_2,…, \beta_p} , i \in L \tag{30}
$$
$$
G_{i,j} \in{0, 1}. \tag{31}
$$
显然，子问题 $P2$仍然是一个整数非线性规划问题，且是NP难的，其计算复杂度为 $O(p^L L!)$，其中 $p$是视频编码比率等级的数量， $L$是视频块数量。在下文中，我们首先证明定理2（即最优匹配定理），然后将子问题 $P2$转化为一个整数线性规划问题。

定义3. 最优匹配序列 ：在 $N_g$ 中处理从视频块1到视频块 $L$的 $L$个组的序列，且该序列产生最大平均视频编码比率。

定理2. （最优匹配定理） 当视频块与组按照组传输速率的降序进行匹配时，可获得最优匹配序列。

证明 . 详细证明可见附录A。

根据定理2，可以确定$G_{i,j}(i, j \in L)$的值，因此子问题 $P2$ 可以简化为一个计算复杂度为 $O(p^L)$的整数线性规划问题 $P3$ ，如果使用穷举攻击算法的话采用。此外，最优匹配矩阵$G_{opt}$满足：$G_{i,j}= 1$ 如果 $i= j$ 且$G_{i,j}= 0$ 如果不满足。因此， $P2$ 中的匹配约束可以被移除。从而，子问题 $P2$ 的最优解可以通过求解 $P3$获得。
$$
P3 \quad \max f(\alpha)= \frac{1}{L} \sum_{i=1}^{L} r_i
$$
$$
\text{s.t.: } r_i= \alpha_i S, i \in L, \alpha_i \in \alpha \tag{32}
$$
$$
t_i= \sum_{k=1}^{i} \sum_{j=1}^{L} G_{k,j}\alpha_k S \tilde{C} j^{msg } + \sum_{j=1}^{L} G_{i,j}\alpha_i S \tilde{C}_j^{psg } \tag{33}
$$
$$
T= \max{t_i | i \in L} \leq D \tag{34}
$$
$$
\alpha_i \in{\beta_1, \beta_2,…, \beta_p}, i \in L \tag{35}
$$
$$
G {i,j}=\begin{cases}
1 & \text{if } i= j \
0 & \text{if } i \neq j.
\end{cases} \tag{36}
$$
为了解决问题 $P3$，我们提出了一种低复杂度启发式算法，如下所示。

所提出的启发式算法：首先，基于所提出的组形成算法和最优匹配定理，形成协作组并确定组的匹配序列。其次，将初始迭代索引设置为 $d= 0$，将每个视频块的初始视频编码率级别设置为最小值（即 $\beta_1$），集合Γ包含当前视频编码率级别下在截止时间内的视频块（即 $t_i< D$），集合 $O$包含超出截止时间的视频块（即 $t_i> D$），集合 $\Psi$包含即使在最低视频编码率级别下仍超出截止时间的视频块（即 $t_i> D$）。集合 $\Gamma$、 $O$和 $\Psi$分别初始化为 $L$、 $\emptyset$和$\emptyset$。每次迭代过程如下所示：
步骤1：计算每个视频块在$L$中的完成时间，将超出截止时间的视频块从集合 $\Gamma$中移除并添加到集合 $O$中。
步骤2：判断集合 $O$是否为空，如果是，则将集合$\Gamma$中所有视频块的视频编码比率等级提高一级，并在执行增加操作前，从 $\Gamma$中移除视频编码比率等级已达到最大值（即 $\beta_p$）的视频块；如果不是空集，则从集合 $O$中移除视频编码比率等级为最小值（即 $\beta_1$）的视频块，将其加入集合 $\Psi$，并将集合 $O$中所有视频块的视频编码比率等级降低一级。
步骤3： $O$再次被设置为 $\emptyset$，迭代 $d$增加1。
当集合 $\Gamma$为空或$\Psi$等价于$L$时，迭代停止。然后得到视频块的视频编码比率集合。

启发式算法的一个示例 ：
场景设置：四个边缘节点 $N={1, 2, 3, 4}$具有 ˜传输速率的倒数集合 $\tilde{C}^{ms} ={1, 2, 3, 4}$秒/兆字节和计算速率的倒数集合˜ $\tilde{C}^{ps} ={10, 10, 10, 10}$秒/兆字节，两个视频块$L={1, 2}$，每个的原始大小为 $S= 10MB$，以及视频编码比率级别集合 $\beta={0.5, 1.0}$。同时，视频任务的截止时间为 $D= 80$秒。
首先，形成两个组，即包含边缘节点1、3的 $N_1^g$，以及包含边缘节点2、4的 $N_2^g$。因此，该组的倒数˜传输速率集为 $\tilde{C} {msg}={3, 4}$秒/兆字节，计算速率集的倒数˜为 $\tilde{C} {psg}={5, 5}$秒/兆字节。集合 $O$为空且 $\Gamma= L$。
其次，根据定理2，视频块1首先传输到组 $N_1^g$，然后视频块2传输到组 $N_2^g$。初始视频编码率级别设置为最低级别（即 $\alpha_1= \alpha_2= 0.5$）。第三，确定视频编码率级别的过程描述如下：
步骤1：计算完成时间（基于公式(4)）$t_1= 40$秒$< D$和 $t_2= 60$秒$< D$。然后，将两个视频块的视频编码比率等级设置为 $\alpha_1= \alpha_2= 1.0$。
步骤2：计算 $t_1= 80$秒$= D$和 $t_2= 120$秒$> D$。然后，将视频块2的视频编码比率等级设置为 $\alpha_2= 0.5$，同时将视频块2从集合 $\Gamma$中移除并添加到集合 $O$中。视频块1的视频编码比率等级仍设置为 $\alpha_1= 1.0$。
步骤3：计算 $t_1= 80$s $= D$，以及 $t_2= 75$s $< 80$s。视频块1已从集合 $\Gamma$中移除。因此，得到两个视频块的视频编码比率等级，分别为 $\alpha_1= 1.0$和 $\alpha_2= 0.5$。

定理3 。所提出的启发式算法具有 $O(pL)$的计算复杂度，其中 $L$是视频块总数， $p$是视频编码比率的等级数。

证明 。考虑最坏情况，即所有视频块均以最高视频编码率级别 $\beta_p$ 传输，根据所提出的启发式算法，计算复杂度显然为 $O(pL)$。

VII. 性能评估

在本节中，我们通过基于计算机的仿真研究来评估所提出的边缘计算框架在延迟敏感型视频任务中的性能。我们考虑在路灯顶部设有一个摄像头节点，并且一组边缘节点 $N={1, 2,…, N}$均匀分布，能够通过设备到设备通信与该摄像头节点进行通信。摄像头节点捕获一个视频序列（即视频任务），并将其分割为多个视频块 $L$，每个视频块具有相同的原始大小 $S$。每个视频块的视频编码比率等级范围在$(0, 1]$之内。该视频任务的截止时间为 $D= 80$秒。此外，基于[21], ，我们将˜计算速率的倒数设为 $\tilde{C}^{ps} = 10$秒/兆字节，˜传输速率的倒数 $\tilde{C}_i^{ms}$ 在$[0.1, 1.0]$秒/ 兆字节范围内均匀分布， $\forall i \in L$。所有仿真均在一台配备 3.6GHz Intel(R) Core(TM) i7‐4790 CPU和8GB内存的台式计算机的MATLAB平台上进行。

A. 组形成算法分析

在本小节中，对贪心算法和穷举攻击算法进行了比较。衡量指标减少的延迟（简称RD）表示前$L$个边缘节点的处理时间与协作组处理时间之间的差值。此处，视频块数量固定为 $L= 6$，边缘节点数量记为 $N={12, 15, 18}$，每个视频块的原始大小设置为 $S= 1MB$。

表II 两种算法在视频块固定数量下的比较
| 算法 | 设置 $N= 12$ | $N= 15$ | $N= 18$ |
| — | — | — | — |
| | RD(秒) 时间(秒) | RD(秒) 时间(秒) | RD(秒) 时间(秒) |
| 暴力破解攻击 | 27.7 1.3 | 32.1 288.1 | 37.0 62919 |
| 贪心算法 | 27.7 0.009 | 31.9 0.01 | 36.3 0.01 |

选择减少的延迟作为衡量指标的原因是，减少的延迟越大，处理相同视频任务（包含传输与计算延迟）所需的时间就越少。因此，在相同的截止时间内，平均视频编码率可以更高，从而有助于提高人体检测精度。详细结果如表II和图5所示。此外，穷举攻击算法的定义如下：
• 暴力破解攻击：搜索所有可能的情况，并找到实现最大减少延迟的最优解。
根据表II可知，在三种不同的设置下，两种算法的减少的延迟几乎相同。随着边缘节点数量的增加，穷举攻击算法的程序运行时间（简称时间）从1.3秒迅速增加到62919秒，而贪心算法的程序运行时间几乎保持不变（约0.01秒），这表明贪心算法能够显著降低计算复杂度。
从图5可以看出，随着边缘节点数量的增加，两种算法的减少延迟均有所增加，且增长趋势基本相同。原因是更多的边缘节点可以形成成员更多的协作组，从而提升每个组的计算能力，减少完成时间。然而，当边缘节点数量为15或18时，贪心算法实现的减少延迟略小于穷举攻击算法。由于贪心算法是逐个分配物品而非一次性分配，因此只能得到次优解。

表III 排序结果与最优匹配的比较
| 速率的倒数 | 匹配结果 | 排序依据 |
| — | — | — |
| $\tilde{C} {msg}$ | 最优匹配 $G {opt}$ | $\tilde{C} {msg}={0.31 0.43 0.90}$ 1 0 0 $\tilde{C} {psg}={5.00 5.00 10.0}$ (1, 2, 3) 0 1 0 0 0 1 $\tilde{C} {msg}={0.31 0.90 0.43}$ 1 0 0 $\tilde{C} {psg}={5.00 5.00 10.0}$ (1, 3, 2) 0 0 1 0 1 0 $\tilde{C} {msg}={0.43 0.31 0.90}$ 0 1 0 $\tilde{C} {psg}={5.00 5.00 10.00}$ (2, 1, 3) 1 0 0 0 0 1 $\tilde{C} {msg}={0.90 0.31 0.43}$ 0 1 0 $\tilde{C} {psg}={5.00 5.00 10.00}$ (2, 3, 1) 0 0 1 1 0 0 $\tilde{C} {msg}={0.43 0.90 0.31}$ 0 0 1 $\tilde{C} {psg}={5.00 5.00 10.0}$ (3, 1, 2) 1 0 0 0 1 0 $\tilde{C} {msg}={0.90 0.43 0.31}$ 0 0 1 $\tilde{C} {psg}={5.00 5.00 10.0}$ (3, 2, 1) 0 1 0 1 0 0 |

B. 视频‐组匹配分析

在本小节中，通过仿真来验证最优匹配定理。基本思想是将通过穷举攻击算法得到的匹配矩阵（即组与视频块的匹配序列）与按照组传输速率降序排列的视频‐组匹配结果进行比较，从而证实最优匹配定理的正确性。在仿真中，共有三个组和三个视频块，这些组的传输速率倒数集合和计算速率倒数集合分别表示为 $\tilde{C} {msg}={\tilde{C}_1^{msg} , \tilde{C}_2^{msg} , \tilde{C}_3^{msg}}$、$\tilde{C} {psg}={\tilde{C} 1^{psg} , \tilde{C}_2^{psg} , \tilde{C}_3^{psg}}$ 。每个视频块的原始大小设置为 $S= 18MB$，视频编码比率级别集合 $\beta$包含若干具有预设值的元素（例如$\beta={0.1, 0.11, 0.12,…, 1.0}$），关于视频块和组的最优匹配矩阵为$G {opt}$，一个3× 3矩阵，该矩阵是根据穷举攻击算法得到的。
这里，六种情况中的每一种都对应于当三个组计算速率的倒数固定时，三个组传输速率的倒数的一种排列。由于篇幅有限，表III中未给出不同组计算速率集合的其他情况，而在我们的仿真中，匹配结果与计算速率无关，这与定理2（最优匹配定理）一致。表III显示，组传输速率倒数的排序序列（按升序排列）与最优匹配序列（由最优匹配矩阵反映）相同，这与最优匹配定理一致。

C. 最大平均视频编码率

在本小节中，我们首先比较了最优解与所提方案的性能，该方案由贪心算法和启发式算法组成。此外，还对无协作方案、任意协作方案以及所提方案之间的性能进行了比较

进行了方案实验。最后，我们给出了人体检测精度与平均视频编码率之间的关系图。此处，原始视频块大小和视频块数量分别设置为 $S= 18MB$和 $L= 4$。下面简要描述无协作方案和任意协作方案。
无协作：不存在协作组，视频块被随机传输至按传输速率降序排列的前几个边缘节点。也就是说，一个视频块仅由一个边缘节点处理。
• 任意协作：边缘节点随机形成协作组，视频块与所形成的组进行任意匹配。没有特定的组形成和视频‐组匹配方案。
由于平均视频编码率越大，平均视频编码码率就越高，从而带来更高的人体检测精度。因此，我们选择平均视频编码率作为性能指标。在图6中，随着边缘节点数量的增加，两种方案的平均视频编码率均有所提高但两者之间的差距逐渐减小。具体而言，最优值（即最优解）略大于所提方案得到的结果，分别在 $N= 7$处高出4.4%2，在 $N= 9$处高出3.6%。原因在于，在视频块数量固定的情况下，更多的边缘节点可以形成包含更多成员的协作组，每个组的计算能力增强，从而可在截止时间内处理更多的视频数据。此外，每个组的成员集合趋于更加相似，同时传输时间的增加远小于计算时间的减少，这也缩小了差距。
在无协作方案、任意协作方案和所提方案之间的性能比较如图7所示。此处，边缘节点数量$N$从集合 ${5, 7, 9, 11, 13}$中选取。对于任意协作方案和所提方案，平均视频编码率随着边缘节点数量的增加而增加，而无协作方案的平均视频编码率保持不变，为0.375。同时，所提方案的平均视频编码率比无协作方案高出约107%（在 $N= 11$处获得）。其原因是，在考虑协作的情况下，随着边缘节点数量的增加，更多边缘节点协同处理固定数量的视频块，从而提升了系统性能。然而，在无协作场景中，仅选择前 $L= 4$个边缘节点来处理固定的视频块，因此边缘节点数量无法影响平均视频编码率。所提方案的平均视频编码率比任意协作方案高出约12%（在 $N= 9$处获得），这是因为在任意协作方案中，边缘节点随机形成组，且视频块被随机分配给这些组。
根据第三节‐C，我们设置参数 $c_1, c_2$为$c_1= 20000, c_2= -0.08$，以及 $a= -0.0098, b= 0.6049, u= 0.1206$，这些参数是通过[8]中的曲线拟合获得的。然后，图8给出了三种方案在人体检测精度随边缘节点数量变化方面的比较。随着边缘节点数量的增加，任意协作方案和所提方案的人体检测精度提高，而无协作方案的精度保持不变，同时所提方案的精度比无协作方案高约19%。
从图7可知，当边缘节点数量增加时，平均视频编码率增加，因此平均视频编码码率也随之增加。从而，人体检测精度提高。所提方案的人体检测精度比任意协作方案高约3%（在 $N= 9$处获得）。

此外，根据图7和图8，人体检测精度与平均视频编码率之间的关系如图9所示。随着平均视频编码比率增加时，人体检测精度提高，同时其速度减慢，这与第三节‐C中给出的公式(3)一致。

VIII. 结论与未来工作

本文研究了一种边缘计算框架下的协同视频处理方案。在所提方案中，综合考虑了组形成和视频‐组匹配，以在视频任务截止时间内最大化人体检测精度。所提出的组形成算法能显著降低计算复杂度并实现次优性能。此外，通过数学归纳法证明了最优匹配定理，并针对视频‐组匹配问题提出了一种低复杂度启发式算法。仿真结果验证了我们的理论分析，并表明与无协作方案和任意协作方案相比，所提方案能够提高人体检测精度。
所提方案如果在实践中部署，可以带来诸多优势，例如1) 降低延迟，即减少在摄像头处处理任务和将数据上传至服务器的延迟，2）降低成本，即减少通过LTE上传大量数据的成本，以及3）易于部署，即依赖现有设施。然而，也存在一些局限性。例如，未考虑处理结果的整合，且假设每个边缘节点的计算能力相同。
在未来的工作中，我们将考虑能耗与完成时间之间的平衡、移动设备的差异（如计算能力和能量存储）以及视频块上的实际处理模型。此外，还将在LTE网络中考虑在满足最低可接受检测精度约束的前提下最小化所需带宽的问题，其中带宽和成本是受限的。