一种基于少数派博弈的不完全信息异构边缘任务卸载方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN109413197A(43)申请公布日2019.03.01(21)申请号201811347446.6(22)申请日2018.11.13(66)本国优先权数据201811320404.32018.11.07CN(71)申请人中山大学地址510275广东省广州市海珠区新港西路135号(72)发明人吴迪谢自轩胡淼(74)专利代理机构广州粤高专利商标代理有限公司44102代理人林丽明(51)Int.Cl.H04L29/08(2006.01)G06F9/445(2018.01)权利要求书3页说明书8页附图1页(54)发明名称一种基于少数派博弈的不完全信息异构边缘任务卸载方法(57)摘要本发明提供的基于少数派博弈的不完全信息异构边缘任务卸载方法，以少数派博弈模型为基础，引入联盟的概念，首先将用户生成的异构任务按照某一个基准分为不同数量的子任务，然后对这些子任务按照联盟的思想进行子任务配对以及初始化分配，之后对博弈的结果进行统计，并把博弈结果广播至各个用户，随后各个用户只需要根据上一轮博弈的结果对自身子任务的决策按照一个概率的方式进行调整，直至达到系统稳态。实验证明，对比传统方法，本发明能够减少30％的系统总处理时间。另外，本发明能够在更短的时间内收敛到一个近优点。综上所述，本发明能够在不完全信息的分布式环境中，对产生的异构任务进行高效的任务卸载。CN109413197ACN109413197A权利要求书1/3页1.一种基于少数派博弈的不完全信息异构边缘任务卸载方法，其特征在于，包括以下步骤S10.首先将问题形式化描述为一个多用户的博弈:S101.系统内有K个用户，每个用户能够周期性地在一个时间槽τ中生成一定量的任务；S102.令M为一个子任务的基本单位，则在一个决策周期中产生的任务能够用M的倍数进行表示；令Nk表示用户k生成的子任务数，则系统的子任务数总数为N＝∑kNk：TS103.令s＝[s1，s2，…，sN]表示为子任务的决策，其中sn表示为子任务n的决策，且sn∈{-1，1}，sn＝1表示子任务n将任务卸载至边缘服务器，sn＝-1表示子任务n将任务卸载至云服务器；TS104.令v＝[v1，v2，…，vK]表示为用户卸载至边缘服务器的子任务数，其中vk表示为用户k卸载至边缘服务器的子任务数，因此，有其中表示为用户k的子任务集T合；令v-k＝[v1，v2，…，vk-1，vk+1，…，vK]表示为除用户k以外，其他用户卸载至边缘服务器的子任务数：S105.一个多用户博弈其中，为用户的集合，为用户k的策略集，T(vk，v-k)为用户k的代价函数；S20.为各个用户的收益提供数学化描述；S201.ne表示卸载至边缘服务器的子任务数，令Te(ne)表示在边缘服务器需要花费的时间，同理，令nc表示卸载至云服务器的子任务数，令Tc(nc)表示在云服务器需要花费的时间，且τc>τe，将Ce和Cc分别表示为边缘服务器和云服务器的处理能力，则有其中，nc＝N-ne；S202.用户k的代价函数可以表示为：其中，ne，-k和nc，-k分别表示为除了用户k的卸载至边缘服务器和云服务器的子任务数；S203.系统的目标为最小化用户的总处理时间，即最小化用户k的代价函数，可表示为：S30.为判别是否为广义上的少数派提供理论指引；S301.平衡点ψ是平衡卸载至边缘服务器的子任务数与卸载至云服务器的子任务数的阈值，能够最小化任务的总处理时间，即为实数；在同质任务的环境中时，平衡点ψ即为总任务数的一半，当卸载至边缘服务器的子任务2CN109413197A权利要求书2/3页数超过平衡点时，卸载至云服务器的子任务数为少数派，即获胜方；反之，当卸载至边缘服务器的子任务数低于平衡点时，卸载至边缘服务器的子任务数为少数派，即获胜方；**S302.令Te(ψ)＝Tc(N-ψ)，得到S303.ψ应该为一个整数，并且需要能够最小化任务的总处理时间，因此，S40.联盟少数派博弈算法是在不完全信息情况对异构任务的任务卸载问题的进行具体求解。S401.子任务配对以及初始化分配：对于同一个用户产生的子任务，他们中的一些会组成一个联盟，给定非对称处理能力的比值ρ，用户直接把能组成联盟的子任务分配至卸载至边缘服务器或云服务器，即所述的联盟的定义为同属于一个用户的子任务按照ne，k＝ρnc，k的原则组成一个联盟；其中，ne，k和nc，k分别表示第k个联盟中的卸载至边缘服务器的子任务数和第k个联盟中的卸载至云服务器的子任务数，则有对于每个用户来说，还有一些子任务不在联盟中，没有被分配，令这些子任务随机选择自己的决策，其中，不在联盟中的子任务数为nr，k＝Nk-ne，k-nc，k；S402.信息收集以及获胜者广播：在上一步每个子