欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2021105636687
申请人: 南京邮电大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于车辆聚类的动态车辆计算任务卸载方法,其特征在于,所述卸载方法包括:S1,计算样本集中所有车辆的可达距离,根据可达距离构建最小生成树;

s2,将最小生成树转化为层次聚类结构,并对转化后的层次聚类树进行压缩;

S3,以簇的稳定性为依据对由每个车辆构成的节点进行聚类,对聚类后的各个簇内节点按优先级排序,根据排序后的结果选取簇头;

S4,基于聚类结果,利用带有跨簇卸载宽容度的UCB算法求解计算卸载策略;

步骤S3中,所述以簇的稳定性为依据对由每个车辆构成的节点进行聚类,对聚类后的各个簇内节点按优先级排序,根据排序后的结果选取簇头的过程包括以下步骤:s31,根据下述公式计算簇c每个节点的簇稳定性sc:

式中,λdeath是对压缩聚类树中的每个可达距离节点的定义,取值为当前节点值的倒数;

λp是针对压缩聚类树中所有叶子节点定义的一个数值,其中,当p不是散点时,当前节点正常分裂成左右子树,λp取值为λdeath,当p是散点时,当前节点替代了p原来的根节点,λp取值为原来根节点的倒数,λp<λdeath;

S32,进行簇提取;其中,如果节点分裂不能使左右子树稳定性之和大于当前节点则当前节点为根节点的所有车辆聚类时被划分到同一类,否则当前节点继续分裂以进一步提取聚类簇;

S33,对每个簇内部的所有节点进行评估,根据下述公式计算得到对应节点的车辆连接值、位置差异值和速度差异值作为该节点的三个评估指标:式中,out(t)表示t时刻进入车辆i邻居列表的车辆数目,in(t)表示离开的车辆数目,N(t‑1)表示车辆i上一时刻的邻居列表数量;dij(t)表示车辆i和其同簇车辆j的距离, 表示车辆i和其同簇车辆j距离的平均值,N(t)表示t时刻当前车辆的所属聚类簇中的车辆节点数量;vij(t)表示车辆i和其同簇车辆j的速度差, 表示车辆i和其同簇车辆j速度差的平均值;

S34,结合车辆连接值、位置差异值和速度差异值对簇节点进行优先级排序,根据排序结果选取优先级最高的作为簇头;

步骤s4中,所述基于聚类结果,利用带有跨簇卸载宽容度的UCB算法求解计算卸载策略的过程包括以下步骤:S41,定义概率ε,每个计算任务以ε的概率进行簇内卸载,以1‑ε的概率进行全局跨簇卸载;

S42,将任务卸载问题看成是多臂赌博机问题,每次操作的臂分为同簇车辆和异簇车辆;其中,根据下述公式计算每辆服务车的评估指标:式中,j表示服务车编号,t表示时刻,dj为将任务卸载至服务车辆j的延迟,D表示服务车和任务车的距离,Nt(i)为t时刻之前执行动作i的次数,M(t‑1)表示t‑1之前的子任务总数,表示执行动作i收益的方差。

2.根据权利要求1所述的基于车辆聚类的动态车辆计算任务卸载方法,其特征在于,步骤S1中,所述计算样本集中所有车辆的可达距离,根据可达距离构建最小生成树的过程包括以下步骤:S11,根据下述公式计算各个节点的核心距离以及实际欧氏距离,两者中的最大值被定义成两者之间的可达距离dmreach‑k(P,Q):dmreach‑k(P,Q)=max{corek(P),corek(Q),d(P,Q)}式中,corek(P)是车辆P的核心距离,corek(Q)是车辆Q的核心距离,d(P,Q)是车辆P和车辆Q之间的实际欧式距离,k是以某个样本为圆心的圆能容纳除自身之外的样本数量;

S12,结合所有车辆之间的可达距离计算结果,构建对应的无向加权图,图的顶点集为所有车辆集合,权重为对应边连接的两个车辆之间的可达距离;

S13,将无向加权图转化为最小生成树。

3.根据权利要求1所述的基于车辆聚类的动态车辆计算任务卸载方法,其特征在于,步骤S2中,所述将最小生成树转化为层次聚类结构,并对转化后的层次聚类树进行压缩的过程包括以下步骤:S21,将最小生成树映射为二叉树;

S22,将映射得到的二叉树放到二维坐标系中,二叉树的每一个叶子节点都表示一个车辆,纵坐标表示可达距离;

S23,从所有未聚类的节点中,选取其中一个可达距离节点作为子树的根节点,将根节点相同的车辆聚类到同一个簇;

S24,重复步骤S23,直至所有节点被聚类完毕;

S25,去除散点。

4.根据权利要求1所述的基于车辆聚类的动态车辆计算任务卸载方法,其特征在于,步骤S34中,所述结合车辆连接值、位置差异值和速度差异值对簇节点进行优先级排序的过程包括以下步骤:采用下述公式计算每个簇节点i的优先级评估值:

式中,w1、w2和w3是对应的权重因子。

5.一种基于权利要求1‑4任一项中所述方法的基于车辆聚类的动态车辆计算任务卸载装置,其特征在于,所述卸载装置包括:最小生成树构建模块,用于计算样本集中所有车辆的可达距离,根据可达距离构建最小生成树;

压缩模块,用于将最小生成树转化为层次聚类结构,并对转化后的层次聚类树进行压缩;

簇头选择模块,用于以簇的稳定性为依据对由每个车辆构成的节点进行聚类,对聚类后的各个簇内节点按优先级排序,根据排序后的结果选取簇头;

求解模块,用于基于聚类结果,利用带有跨簇卸载宽容度的UCB算法求解计算卸载策略。

6.一种电子设备,其特征在于,包括:

一个或多个处理器;

存储装置,用于存储一个或多个程序,

当所述一个或多个程序被所述一个或多个处理器执行,使得所述一个或多个处理器实现如权利要求1‑4中任一项所述的基于车辆聚类的动态车辆计算任务卸载方法。

7.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,该程序被处理器执行时实现如权利要求1‑4中任一项所述的基于车辆聚类的动态车辆计算任务卸载方法。