2.2 系统模型和问题表述

2.2.1 系统概述

如图2.1所示，本节考虑一个由多个设备组成的无线网络，设备集合表示为 ={1,…, i ,…, N }。在时隙 t 中，设备 i ∈ 生成一组任务 ，其中 K ( i , t )是时隙 t 时设备 i 能生成的任务总数。任务 x _i,k 的大小由 s _i,k 来表示，并且它计算所需的CPU周期为 c _i,k 。每个设备的任务生成过程可以建模为具有生成强度为 的泊松过程 ^[5-6] 。对于任务 x _i,k ，设备 i 既可以卸载给设备 ，也可以在本地处理。用二进制值 fi , k , j 来表示将任务 x _i,k 迁移给设备 j ，并且 。表示分配任务的标志为 f _i,k ={ f _{i,k, 1} ,…, f _i,k,N }。本节的主要符号及描述如表2.1所示。

本节考虑的系统中没有集中式的控制，每个设备都在本地维护一个状态列表。当设备首次加入网络时，列表中只包含设备自身的传输和处理队列状态、当前速度、位置和移动方向。每个时隙开始时，设备将其状态列表中的所有记录广播给相邻的设备。然后，设备根据接收到的记录更新本地状态列表。例如，网络中有4个相对静态节点，每个节点在图2.2所示的示例中本地维护一个状态列表。最初，每个节点只知道自己的状态。随着时间的推移，节点可以学习当前时隙中记录的直接连接节点的状态，也可以学习前一个时隙中记录的间接连接节点的状态。

例如，时隙1（ t =1）中的节点 A 只有自己的状态，而在时隙2（ t =2）有直接连接的节点 C 接收状态记录。在时隙3（ t =3）中，节点 A 从时隙2更新的节点 C 的记录中获知其他间接连接的节点状态，并在时隙3中接收节点 C 的更新状态。 表示设备 i 和设备 j 在时隙 t 的连接状态，即：如果 ，表示在时隙 t 时设备 i 和设备 j 可以直接或间接建立彼此的联系。也就是说，它们可以在邻近时相互连接，或者通过一组中继节点实现间接传输。此外，本节假设设备可以在现有安全和激励机制的保证下准确地为他人处理任务。同时，本节主要关注如何实现在线任务调度，因此不需要考虑任务处理过程中链路断开的情况。

2.2.2 通信和计算模型

设备之间可以通过OFDMA技术进行通信，使得每个设备的子载波可以相互正交。因此， N 个设备之间的通信需要( N −1)·( N −1)个子载波。每个设备在本地维护( N −1)个传输队列，用于向其他设备传输任务。当设备 i 和设备 j 邻近时，任务 x _{i, k} 的传输时延可以表示为 T _d ( i , k , j )= s _{i, k} / γ _ij ，其中 γ _ij 表示设备 i 到设备 j 的传输速率。任务按照先进先出顺序传输。然后，根据 M / G /1排队系统 ^[7] ，得到设备 i 到设备 j 传输队列中任务 x _{i, k} 的等待时间，如式（2-1）所示。

其中， 表示任务从设备 i 到设备 j 的平均传输时延； δ ² 表示传输时延的方差； 表示从设备 i 到设备 j 的任务传输强度。

对于任务卸载，本节认为设备 i 上的任务可以卸载到几跳之外的设备上。也就是说，设备 i 的任务可以通过多个中继节点传输到目标设备进行处理。因此，当通过多个中继节点在设备 i 和 j 之间建立连接路径时，任务 x _{i, k} 从设备 i 到设备 j 的总传输时延可计算为

其中， β _{i, k, l} 是一个二进制值，表示设备 l 是否为一个中继节点，该中继节点可以帮助将任务 x _{i, k} 传输到设备 j ，且 T _d ( i , k , i )=0。

当设备 j 接收到任务 x _{i, k} 后，它首先在处理队列中等待，然后按照先进先出顺序进行服务。处理队列中的等待时延 T _q ( i , k , j )与式(2-1)相似。设备 j 执行任务 x _{i, k} 的处理时延为 T _p ( i , k , j )= c _{i, k} / b _j , b _j 为设备 j 的计算能力，即每秒运行的 CPU 周期数。本节设定计算结果数据小到可以忽略传输时延 ^[5-6] 。

2.2.3 问题公式化

在时隙 t 中，当设备 i 有任务要计算时，它可以将这些任务卸载到其他设备上，也可以在本地处理。对于任务 x _{i, k} ，平均任务执行时延可以通过式（2-3）计算

则设备 i 的平均任务完成时间为

其中， 是算法已经运行的总时隙。每个设备的目的是最小化其平均任务完成时间，即：

在这里，约束C2.1确保了任务 x _{i, k} 可以直接分配设备或通过多个中继节点与设备 i 建立连接。由于一个设备的任务调度决策可能受到其他设备的影响，因此需要进行一个交易过程，以实现不同设备之间的公平性。通常情况下，可以利用非合作博弈来解决上述问题 ^[5] ，即所有设备都应该知道系统状态，以便做出决策。然而，在去中心化的分布式环境中，设备无法获得瞬时的系统状态。因此，本章在系统中使用了多智能体模仿学习，每个智能体不需要知道整个系统的状态，而是根据其局部观测跟随专家的演示来训练策略。 DaFtHU44jO3oEWiWu2V0fMWkjHXQska2JXs0mJpSKuHbEuTLa1ZayqaR9rJjDdj3