论文部分内容阅读
智能终端的普及、网络覆盖范围的扩大促进了消费物联网和工业物联网等新兴产业的进一步发展,各种各样的应用也随之产生。然而,由于智能终端和物联网终端的计算能力有限,通常需要将自身无法及时处理的计算任务交由计算能力更高的设备进行处理。边缘计算技术的出现为解决上述问题提供了保障,边缘计算将计算平台迁移到产生源数据的边缘设备上,减少了数据传输的时延。边缘设备还为用户终端提供数据计算和数据存储,尤其适合用户终端的任务分配。任务分配可以将用户终端复杂的计算任务通过无线网络分配给边缘网络执行,依靠边缘设备的计算资源,完成计算任务,从而解决用户终端计算能力、计算时延等问题。尽管如此,物联网设备和应用的巨大多样性使得单一的计算模式几乎不可能满足所有的应用需求,基于上述问题,本文的主要工作包括:(1)对边缘计算的研究现状进行了分析,详细介绍了影响边缘计算任务分配策略的主要因素,通过阅读大量文献,对现有任务分配方法进行了全面梳理,并对边缘计算的任务分配算法进行了深入研究。(2)建立边缘计算场景,以DAG任务图建立用户终端任务划分模型,以能量消耗最小化为目标,综合考虑了时延、可靠性、单个边缘设备的能耗约束的任务分配(混合整数非线性规划)模型。为了有效地求解优化问题,通过引入罚函数的方法将遗传算法的适应度函数与原优化问题相结合,将带约束条件的优化问题转换为无约束问题,重复选择、交叉、变异等操作直至指定的迭代次数,求得优化问题的最优解。(3)由于上述问题是一个非确定性多项式(non-deterministic polynomial,NP)难问题,本文提出了一种内点法与简化分支定界法相结合的混合算法(Interior-Branch and Bound Algorithm,I-BBA)对上述问题进行求解。首先将优化问题松弛为松弛优化问题,并证明了松弛优化问题为凸优化问题,采用内点法求解。针对内点法在求解具体的任务分配过程中存在的局限性,考虑将内点法与简化分支定界法相结合的混合算法来求解任务分配问题,根据任务分配属性,对决策变量不断分支定界进行求解,降低了计算的复杂度。(4)通过对比五种算法在不同参数下的能耗值以及运行时间验证了本文所提算法的有效性,突出了本文算法的优势。