(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210577951.X (22)申请日 2022.05.25 (71)申请人 南京航空航天大 学 地址 210016 江苏省南京市御道街2 9号 (72)发明人 柴新越　李楠　宋晓勤　江榕天　 朱敏　李佳俊　张予聪　 (51)Int.Cl. H04W 4/44(2018.01) H04W 24/06(2009.01) H04W 28/08(2009.01) G06F 9/445(2018.01) G06F 9/48(2006.01) (54)发明名称 一种基于半马尔可夫过程的低时延车载边 缘计算方法 (57)摘要 本发明提出的一种基于半马尔可夫过程的 低时延车载边缘计算方案， 采用IEEE802.11p中 的车辆之间的通信传输协议为车辆环境提供可 靠、 高效的通信， 并利用一种基于贝尔曼方程的 车载边缘计算任务卸载方案优化算法， 优化目标 是最大化系统的长期奖励。 综合考虑传输延迟、 计算延迟、 当前可用资源以及车辆和任务的多样 性特征的情况， 在不同状态下采取不同行动， 通 过VEC系统获得的奖励反映VEC系统在不同状态 和行为下的收益， 并据此选择卸载策略。 本发明 使用半马尔可夫决策过程可以有效解决车载边 缘计算系统的计算卸载问题， 找到最佳的卸载决 策。 权利要求书2页 说明书9页 附图2页 CN 115175136 A 2022.10.11 CN 115175136 A 1.一种基于半马尔可 夫过程的低时延车 载边缘计算方法， 包括 步骤如下： (1)车辆边缘计算由多辆具有计算资源的车辆和其他边缘节点组成， 车辆通过V2I的通 信方式， 将任务卸载到附近的基础设施上进行处 理； (2)在车联网的通信模型中， 任务时延有两个部分， 即与RUS的计算能力有关的计算时 延以及任务传输时长和反馈计算结果时长总和的传输时延； (3)在车辆边 缘计算中， 采用IE EE 802.11p的增强DCF机制， 每 个子任务进行分组传输； (4)构建半马尔可夫决策过程模型来描述车载边缘计算系统的计算卸载问题， 找到最 佳的卸载决策； (5)对奖励、 转移概率和折现因子进行归一化处理， 将连续时间的半马尔可夫决策过程 转化为离散时间的半马尔可 夫决策过程； (6)利用迭代算法来最大化半马尔可夫决策过程的长期回报， 在每次迭代中， 根据贝尔 曼方程迭代计算 不同动作下 各状态的最大值 函数， 直到每 个状态的最大值 函数收敛为止； 进一步， 所述步骤(4)包括如下 具体步骤： (4a)定义状态S是用来表示具有不同数量的RUS的处理任务， 以及在不同事件下可用的 RUS的数量， 事件用e表示， e属于集合{A， D1， ...， DN， F+1， F‑1}； A表示任务的到来， N表示系统 可以分配的RUS的最大数量， Di表示被i个RUS处理的任务， F+1表示车辆的到来， F‑1表示车辆 的离开； 因此， 状态集 合可以表示 为： S＝{s|s＝(M， n1， ...， nN， e)} 其中M为V EC系统中所有RUS的数量， ni为i个RUS处理的任 务数量， 系统分配给任 务的RUS 数量不能超过总的RUS数量， 所以， 空 闲的RUS可以用下式计算： (4b)定义动作Ac是表示在不同事件下分配一定数量的RUS， 基于状态s的动作用a(s)表 示， 属于集合{ ‑1， 0， 1， 2， ...， N}； a(s)＝ ‑1表示不采取行动， a(s)＝0表示VEC系统可用的 RUS不足， 所以拒绝卸载任务， 丢弃任务， a(s)＝i表示分配i个RUS来处理该任务； 当一个事 件(如任务的离开、 车辆的离开或车辆的到达)发生时， VEC系统可能没有任务要处理， 也没 有动作； 当任务到达等事件发生时， VEC系统可以丢弃该任务或分配i个RUS处理该任务； 事 件与动作之间的关系为： (4c)定义奖励函数R(s， a)， 综合考虑传输延迟、 计算延迟、 当前可用资源以及 车辆和任 务的多样性特征的情况下， 在不同状态下采 取不同行动时， VEC系统获得奖励； 当在状态s上 采取动作a时， 系统获得即时收益I(s， a)； 状态s将保持一段时间， 直到当另 一个事件发生 时， 状态s转移到下一个状态； 在此期间， 系统的成本用C(s， a)表 示； 当在状态s下采 取行动a 时， 奖励R(s， a)定义收益 I(s， a)与成本 C(s， a)之差， 可以表示： R(s， a)＝ I(s， a)‑C(s， a) (4d)定义转移概率为在当前状态下采取一个动作后到达下一个状态的概率， 采取动作 a后从状态s到状态s ′的转移概 率用P(s′|s， a)表示， 其中状态s＝(M， n1， ...， nN， e)； 进一步， 所述步骤(5)包括如下 具体步骤： (5a)归一 化方程如下：权　利　要　求　书 1/2 页 2 CN 115175136 A 2其中y＝K·λt+K·N·μt+λf+ μf是一个归一 化因子； 进一步， 所述步骤(6)包括如下 具体步骤： (6a)初始化迭代次数设置为0， 每 个状态的值 函数初始化 为0； (6b)对于每一个s∈S根据贝尔曼方程计算 其 中， γ是折现因子且 (6c)如果 对于每一个s∈S： 计算 其中阈值 (6d)其他不满足收敛 条件： k+1返回执 行步骤(6b)； (6e)返回最佳决策 权　利　要　求　书 2/2 页 3 CN 115175136 A 3