一种基于雾云环境的无人机弹性计算方法
技术领域
本发明涉及雾计算、云计算、无人机与调度优化领域，具体涉及一种基于雾云环境的无人机弹性计算方法。
背景技术
随着科技的持续发展和技术的不断进步，无人机以其快速、机动、灵活等优点被广泛地应用于救灾、测绘、航拍、智能制造等领域。比如在救灾方面，森林是自然界中的宝贵资源,森林火灾检测技术的研究在林业中具有非常重要的意义。无人机以其高机动性和能够以相对较低的成本覆盖不同高度和位置的区域,越来越多地应用于森林火灾监测和检测。另一方面，使用无人机来代替人工去完成这些高危的工作也是百利而无一害。而在智能制造领域，制造业以互联网为基础设施，实现广泛的互联互通——贯穿于设计、生产、管理、服务等制造活动的各个环节，明显地提升了行业内的生产效率，改善了在过去使用人工来工作时生产的产品质量参差不齐的问题，保证了出厂产品的质量和统一性。
无人机在处理范围大、数据处理量大、网络带宽占用率高的背景环境中占有优势，如何使无人机在同时存在雾计算和云计算的环境中充分发挥其功能是值得思考的问题。并且在这样的雾云环境中对云节点、雾节点和无人机来说，按照计算能力从大到小排序为云节点、雾节点、无人机，按照通信能力从大到小排序为无人机、雾节点、云节点，费用消耗最大的为云节点(云服务器租赁和流量费用)。如何充分利用无人机的计算能力和通信能力与环境系统中的雾节点和云节点配合从而能在截止时长内完成任务请求的同时使得费用尽可能降低，达到效率经济的双赢，是亟需解决的问题。
目前针对无人机在雾云环境中的弹性计算调度问题的研究较少，大多只考虑将无人机引入云计算背景中。随着物联网和5G的飞速发展，将无人机引入雾云环境作为新的计算资源的想法更具有现实可行性，因此如何利用三者之间的协作在约束条件下完成调度是研究的重点。
发明内容
本发明针对上述背景技术中存在的问题，提出一种基于雾云环境的无人机弹性计算方法。
一种基于雾云环境的无人机弹性计算方法，包括如下步骤：
S01：调度中心接收数据源采集到的一批新的任务请求，解析各个请求是计算密集型任务还是数据密集型任务并存入新任务集合D1，并设置任务数据新鲜度初值；同时监视在待二次优化集合D2中的任务执行情况，即同时执行S02和S12；
S02：调度中心判断新任务集合D1是否为空，如新任务集合D1为空，执行S01，如不为空，则执行S03；
S03：调度中心根据给定的排序策略为各任务设置优先级，任务优先级越高则初始任务分配方案优先级越高；
S04：调度中心判断出之前解析的所有计算密集型任务，执行S06，其余不是计算密集型任务的，执行S07；
S05：调度中心对解析的所有计算密集型任务生成初始任务分配方案，其中的雾任务分配子方案指将全部计算数据分配至附近对应的雾设备处理；其中的无人机任务分配子方案指无人机作为雾设备计算能力的补充，调度中心安排离雾设备较近且电量充足的无人机一台或多台飞往雾设备附近指定地点承担剩余部分计算任务；其中的云任务分配子方案指在雾任务分配子方案和无人机任务分配子方案均调度分配过后仍达不到满足截止时长要求时将余下数据发送至云端处理，之后执行S07；
S06：调度中心对解析的所有数据密集型任务生成初始任务分配方案，其中的无人机任务分配子方案指无人机作为通信能力较强的设备，调度中心安排离数据源较近且电量充足的无人机一台或多台飞往数据源附近指定地点承担计算任务；其中的雾任务分配子方案指将剩余部分计算数据分配至附近对应的雾设备处理；其中的云任务分配子方案指在雾任务分配子方案和无人机任务分配子方案均调度分配过后仍达不到满足截止时长要求时将余下数据发送至云端处理，之后执行S07；
S07：调度中心向各个数据源、雾设备和无人机发送初始任务分配方案并为无人机规划路径，生成无人机任务方案，并实时更新资源可用信息；
S08：调度中心协助各个无人机到达指定地点，并监控数据源、雾设备和无人机执行任务分配方案的情况，并将该任务从新任务集合D1中移出；
S09：调度中心监控所有任务是否存在较高超期风险的任务，如果不存在，执行S02，如存在，则执行S10；
S10：调度中心更新未按期执行任务的数据新鲜度，将初始任务分配方案存入待二次优化集合D2，之后执行S01；
S11、调度中心判断待二次优化集合D2是否为空，如D2为空，执行S01，如不为空，则执行S12；
S12、调度中心若发现有任务数据新鲜度低于阈值，则丢弃该任务并释放资源；其余任务根据数据新鲜度从低到高排序设置待优化方案的优先级，数据新鲜度越低则待优化方案优先级越高；
S13、调度中心判断出之前解析的所有计算密集型任务，执行S14，其余不是计算密集型任务的，执行S15；
S14、调度中心检测到执行计算密集型任务时数据传输时间超期的所有任务，则安排离数据源较近的有空闲时间段和充足电量的无人机一台或多台飞往数据源附近指定地点，并为无人机规划路径，更新无人机任务方案，实时更新资源可用信息，之后执行S16；
S15、调度中心检测到执行数据密集型任务时计算时间超期的所有任务，则安排离雾设备较近的有空闲时间段和充足电量的无人机一台或多台飞往雾设备附近指定地点，并为无人机规划路径，更新无人机任务方案，实时更新资源可用信息，之后执行S16；
S16、调度中心将二次优化方案发送给对应数据源和无人机或对应雾设备和无人机后从D2中移出，并监测二次优化方案执行情况，之后执行S01进行循环。
进一步地，S01中，调度中心接收到区域内生产设备上如传感器、摄像头的数据源采集到的一批新的生产任务请求信息，一条生产任务请求信息在通过解析后包含请求任务ID、数据源编号ID、解析任务类型、对应雾设备编号ID、任务数据信息、截止时长、数据新鲜度的信息；调度中心维护一个空闲的新任务集合表，将新到达的生产任务请求信息存入表中；同时，调度中心还维护一个可用资源信息表，其中包含设备编号ID、位置信息、资源利用信息，其中在设备编号ID里数据源以D开头表示，雾设备以F开头表示，无人机以U开头表示，云服务器以C开头表示；若设备编号ID为雾设备，资源利用信息应该只记录资源监视器信息，若设备编号ID为无人机，资源利用信息应该同时记录资源监视器信息和剩余飞行时间。
进一步地，S01中，调度中心将各个生产任务请求存入新任务集合表中，并且调度中心为各个任务设置数据新鲜度初值为100％，数据新鲜度计算方法引入数据新鲜度运算公式，即截止时长和已执行时长之差占截止时长的比值。
进一步地，S03中，调度中心根据各请求任务的截止时长从小到大排序设置初始任务分配方案的优先级，优先级排序表需要包含优先级、请求任务ID，截止时长越小初始任务分配方案优先级越高。
进一步地，S03中，调度中心根据当前资源的可用状态按照任务优先级高低依次为每一个任务生成初始任务分配方案，初始任务分配方案包括雾任务分配子方案、无人机任务分配子方案和云任务分配子方案。
进一步地，S05和S06中，调度中心为计算密集型任务生成初始任务分配方案时依次生成雾任务分配子方案、无人机任务分配子方案、云任务分配子方案；为数据密集型任务生成初始任务分配方案时依次生成无人机任务分配子方案、雾任务分配子方案、云任务分配子方案；生成的初始任务分配方案中需包含请求任务ID、第一处理设备ID、第一处理设备承担任务百分比、第二处理设备ID、第二处理设备承担任务百分比、第三处理设备ID、第三处理设备承担任务百分比、预计任务完成时长等信息。
进一步地，S09中，调度中心对所有正在执行的任务进行超期风险评估，是根据任务已经处理的数据量和处理时间计算处理速度，以此判断剩余数据量是否能按期完成；超期风险值的计算方法为超期时长与预计任务完成时长的比值，当超期风险值大于一定阈值的时候则认为该任务有较高超期风险。
进一步地，S12中，调度中心若发现待二次优化集合D2中有数据新鲜度阈值已低于5％，就要丢弃该任务并释放其所有已占有的资源，对于其余数据新鲜度阈值高于5％的待二次优化任务，根据数据新鲜度从低到高排序，以此顺序为待优化方案的优先级，生成待二次优化任务优先级表，待二次优化任务优先级表需要包含优先级、请求任务ID、更新的数据新鲜度等信息。
进一步地，所述无人机在运行过程中执行弹性计算流程为：
无人机收到任务分配方案和无人机任务方案，按照方案中指定路线去到第一个指定地点，到达指定地点后向调度中心发送到达指令；
无人机若按时到达指定地点，向调度中心发送到达指令，连接对应数据源或雾设备接收计算数据，执行任务分配方案；
无人机若未按时到达指定地点或未按计划完成计算任务，则向调度中心发送未按期执行任务分配方案消息，等待调度中心发送更新后的方案；
无人机若完成该任务分配方案，按照其无人机任务方案判断是否按计划完成所有分配任务，如果未完成所有分配任务，则无人机向调度中心发送此任务完成响应，并按实时更新的无人机任务方案中指定路线飞往下一指定地点；
无人机若完成无人机任务方案中所有分配任务，重新检测其电量，若无人机检测到电量低至阈值，则向调度中心发送充电指令，飞往距离最近的充电桩充电，充电完毕后等待调度中心发送新的任务分配方案和无人机任务方案；否则就直接等待调度中心发送新的任务分配方案和无人机任务方案。
本发明所述的有益效果为：本发明提供一种基于雾云环境的无人机弹性计算方法方法，包含弹性雾计算流程和无人机执行计算任务流程，利用无人机作为系统中计算能力的补充或通信能力的补充，使得各样的计算任务可以在截止日期前完成并尽量降低成本的优化和实施。
附图说明
图1是本发明实施例中调度中心的调度流程示意图。
图2是本发明实施例中无人机执行计算任务流程示意图。
图3是本发明实施例中无人机移动时进行弹性计算的示意图。
图4是本发明实施例中新任务集合表。
图5是本发明实施例中可用资源信息表。
图6是本发明实施例中优先级排序表。
图7是本发明实施例中任务分配方案表。
图8是本发明实施例中无人机任务方案表。
图9是本发明实施例中待二次优化任务优先级表。
图10是本发明实施例中更新过后的二次优化任务分配方案表。
图11是本发明实施例中更新过后的无人机任务方案表。
具体实施方式
下面结合说明书附图对本发明的技术方案做进一步的详细说明。
下面将结合本发明实施例中的附图，以工厂中的智能制造为例，对本发明实施例中的技术方案进行清楚、完善地描述，显然，所描述的实施例仅仅是本发明的一部分实施例，而不是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出劳动成果的前提下所获得的所有其他实施例，都属于本发明的保护范围。
图1为本发明一种无人机弹性计算方法的调度中心调度流程示意图，具体包括如下步骤：
S01：调度中心接收数据源采集到的一批新的任务请求，解析各个请求是计算密集型任务还是数据密集型任务并存入新任务集合D1，并设置任务数据新鲜度初值；同时监视在待二次优化集合D2中的任务执行情况，即同时执行S02和S12。
调度中心接收到区域内生产设备上数据源(如传感器、摄像头等)采集到的一批新的生产任务请求信息，一条生产任务请求信息在通过解析后应该包含请求任务ID、数据源编号ID、解析任务类型、对应雾设备编号ID、任务数据信息、截止时长、数据新鲜度等信息。调度中心维护一个空闲的新任务集合表，将新到达的生产任务请求信息存入表中；同时，调度中心还维护一个可用资源信息表，其中应该包含设备编号ID、位置信息、资源利用信息，其中在设备编号ID里数据源以D开头表示，雾设备以F开头表示，无人机以U开头表示，云服务器以C开头表示；若设备编号ID为雾设备，资源利用信息应该只记录资源监视器信息，若设备编号ID为无人机，资源利用信息应该同时记录资源监视器信息和剩余飞行时间；地点位置信息如图3所示。
调度中心将各个生产任务请求存入新任务集合表中，并且调度中心为各个任务设置数据新鲜度初值为100％，数据新鲜度计算方法可引入数据新鲜度运算公式，即截止时长和已执行时长之差占截止时长的比值。本例中规定当数据新鲜度低于5％时将该任务数据视为不新鲜数据，丢弃该任务并释放其占用的所有资源。
例如，调度中心将新一批生产任务请求信息存入新任务集合表如图4所示，当前可用资源信息如图5所示(为简化起见，请求任务的具体任务数据信息用Task1 Data，Task2Data……表示)。
S02：调度中心判断新任务集合D1是否为空，如新任务集合D1为空，执行S01，如不为空，则执行S03。
此时调度中心新任务集合表(图4)不为空，则执行S03。
S03：调度中心根据给定的排序策略为各任务设置优先级，任务优先级越高则初始任务分配方案优先级越高。
调度中心可以根据各请求任务的截止时长从小到大排序设置初始任务分配方案的优先级，截止时长越小初始任务分配方案优先级越高。
优先级排序表需要包含优先级、请求任务ID。此例中得到的优先级排序表如图6所示。
调度中心根据当前资源的可用状态按照任务优先级高低依次为每一个任务生成初始任务分配方案，初始任务分配方案包括雾任务分配子方案、无人机任务分配子方案和云任务分配子方案。
调度中心根据当前资源的可用状态(图5)按照任务优先级(图6)高低依次为Task2、Task1生成初始任务分配方案，初始任务分配方案包括雾任务分配子方案、无人机任务分配子方案和云任务分配子方案。
S04：调度中心判断出之前解析的所有计算密集型任务，执行S06，其余不是计算密集型任务的，执行S07。
根据图4，请求任务Task1解析为计算密集型任务，执行S05；请求任务Task2解析为数据密集型任务，执行S06。
S05：调度中心对解析的所有计算密集型任务生成初始任务分配方案，其中的雾任务分配子方案指将全部计算数据分配至附近对应的雾设备处理；其中的无人机任务分配子方案指无人机作为雾设备计算能力的补充，调度中心安排离雾设备较近且电量充足的无人机一台或多台飞往雾设备附近指定地点承担剩余部分计算任务；其中的云任务分配子方案指在雾任务分配子方案和无人机任务分配子方案均调度分配过后仍达不到满足截止时长要求时将余下数据发送至云端处理，之后执行S07。
调度中心为任务Task1生成初始任务分配方案，首先生成雾任务分配子方案，预计将全部计算数据发送至对应雾设备F01进行计算是否可行，预计结果为F01最多可承担任务Task1计算任务的60％，则将剩余40％的计算量分配到无人机处理。于是接着生成无人机任务分配子方案，调度中心发现离F01较近且电量充足有空闲时间段的无人机有U01和U02，且两台无人机刚好能满足剩余任务需求，且满足截止时长，不需安排云任务分配子方案。调度中心将规划好的初始任务分配方案存入任务分配方案表中，之后执行S07。
任务分配表中需包含请求任务ID、第一处理设备ID、第一处理设备承担任务百分比、第二处理设备ID、第二处理设备承担任务百分比、第三处理设备ID、第三处理设备承担任务百分比、预计任务完成时长。其中预计任务完成时长是雾任务分配子方案完成时长、无人机任务分配子方案完成时长和云任务分配子方案完成时长三者的最大值；雾任务分配子方案完成时长和云任务分配子方案完成时长包括数据传输时长和计算时长；无人机任务分配子方案完成时长包括数据传输时长、计算时长和无人机飞行时长。此例的任务分配方案表如图7所示。
S06：调度中心对解析的所有数据密集型任务生成初始任务分配方案，其中的无人机任务分配子方案指无人机作为通信能力较强的设备，调度中心安排离数据源较近且电量充足的无人机一台或多台飞往数据源附近指定地点承担计算任务；其中的雾任务分配子方案指将剩余部分计算数据分配至附近对应的雾设备处理；其中的云任务分配子方案指在雾任务分配子方案和无人机任务分配子方案均调度分配过后仍达不到满足截止时长要求时将余下数据发送至云端处理。
调度中心为任务Task2生成初始任务分配方案，首先生成无人机任务分配子方案，调度中心预计将全部计算数据发送至数据源D02附近电量充足有空闲时间段的无人机进行计算是否可行，预计结果为只有无人机U03可承担任务Task2计算任务的30％。于是接着生成雾任务分配子方案，预计对应雾设备F02在截止时长内最多可承担任务Task2计算任务的55％，则将剩余15％的计算量分配到云端C01处理，生成云任务分配子方案。调度中心将规划好的初始任务分配方案存入任务分配方案表中。此例的任务分配方案表如图7所示。
S07：调度中心向各个数据源、雾设备和无人机发送初始任务分配方案并为无人机规划路径，生成无人机任务方案，并实时更新资源可用信息。
调度中心根据任务分配表中的任务分配方案，将请求任务Task2的初始任务分配方案发送给U03、F02、C01，请求Task1的初始任务分配方案发送给F01、U01、U02。同时调度中心为无人机U01、U02、U03根据其当前位置和目标位置分别生成规划路径，存入无人机任务方案表中。无人机任务方案表需要包含无人机设备编号ID、目的地编号ID、多点路线规划、预计飞行时长等信息。其中的规划路线由于无人机在一批任务中可能依次有多个目的地，因此也就有多个子路线。此例的无人机任务方案表如图8所示(为简化起见，无人机的多点路线规划用U01规划路线，U02规划路线……表示，具体路线见示例图3)。
S08：调度中心协助各个无人机到达指定地点，并监控数据源、雾设备和无人机执行任务分配方案的情况，并将该任务从新任务集合D1中移出。
调度中心协助无人机U03、无人机U01、无人机U02沿无人机任务方案表中生成的多点路径规划到达指定地点，同时监控各个数据源、雾设备和无人机执行各任务分配方案的情况，并将任务Task1和任务Task2从新任务表T(图4)中移出。
S09：调度中心监控所有任务是否存在较高超期风险的任务，如果不存在，执行S02，如存在，则执行S10。
调度中心监控任务Task1和任务Task2是否具有较高超期风险，根据任务Task1和任务Task2已经处理的数据量和处理时间计算处理速度，以此判断剩余数据量是否能按期完成。超期风险值的计算方法可为超期时长与预计任务完成时长的比值，当超期风险值大于20％的时候则视为该任务有较高超期风险。监控发现任务执行过程中Task1的数据传输时间超期，新预计的任务完成时长为4.8分钟，任务Task2的计算时间超期，新预计的任务完成时长为3.1分钟，均具有较高超期风险，执行S10。
S10：调度中心更新未按期执行任务的数据新鲜度，将初始任务分配方案存入待二次优化集合D2，之后执行S01。
调度中心根据数据新鲜度运算公式计算并更新任务Task1和任务Task2的数据新鲜度，并将任务分配方案表中任务Task1和Task2的初始任务分配方案存入待二次优化集合D2，返回执行S01。
S11：调度中心判断待二次优化集合D2是否为空，如D2为空，执行S01，如不为空，则执行S12。
调度中心一直监控新任务集合和待二次优化集合D2的情况，当调度中心发现二次优化集合D2不为空时，执行S12。
S12：调度中心若发现有任务数据新鲜度低于阈值，则丢弃该任务并释放资源；其余任务根据数据新鲜度从低到高排序设置待优化方案的优先级，数据新鲜度越低则待优化方案优先级越高。
调度中心若发现待二次优化集合D2中有数据新鲜度阈值已低于5％，就要丢弃该任务并释放其所有已占有的资源。对于其余数据新鲜度阈值高于5％的待二次优化任务，根据数据新鲜度从低到高排序，以此顺序为待优化方案的优先级。目前待优化二次集合D2中有任务Task1和任务Task2的分配方案待优化，生成待二次优化任务优先级表。
待二次优化任务优先级表需要包含优先级、请求任务ID、更新的数据新鲜度等信息。此例中得到的待二次优化任务优先级表如图9所示。
S13：调度中心判断出之前解析的所有计算密集型任务，执行S14，其余不是计算密集型任务的，执行S15。
调度中心根据图9和生产任务请求信息判断所有需要二次优化的任务是计算密集型任务还是数据密集型任务。请求任务Task1解析为计算密集型任务，执行S14；请求任务Task1解析为数据密集型任务，执行S15。
S14：调度中心检测到执行计算密集型任务时数据传输时间超期的所有任务，则安排离数据源较近的有空闲时间段和充足电量的无人机一台或多台飞往数据源附近指定地点，并为无人机规划路径，更新无人机任务方案，实时更新资源可用信息，之后执行S16。
调度中心重新为任务Task1进行任务调度分配。调度中心发现任务Task1在执行时数据传输时间超期，在初始任务分配方案的基础上，检查数据源D01附近是否存在有空闲时间段且电量充足的无人机，检查发现无人机U04符合要求，调度中心为无人机U04规划路径，更新无人机任务分配表，并实时更新资源可用信息，之后执行S16。
此例更新过后的二次优化任务分配方案表和无人机任务方案表分别如图10，图11所示。
S15：调度中心检测到执行数据密集型任务时计算时间超期的所有任务，则安排离雾设备较近的有空闲时间段和充足电量的无人机一台或多台飞往雾设备附近指定地点，并为无人机规划路径，更新无人机任务方案，实时更新资源可用信息。
调度中心重新为任务Task2进行任务调度分配。调度中心发现任务Task2在执行时计算时间超期，在初始任务分配方案的基础上，检查雾设备F02附近是否存在有空闲时间段且电量充足的无人机，检查发现无人机U01符合要求，调度中心为无人机U01规划路径，更新无人机任务分配表，并实时更新资源可用信息。
此例更新过后的二次优化任务分配方案表和无人机任务方案表分别如图10，图11所示。
S16：调度中心将二次优化方案发送给对应数据源和无人机或对应雾设备和无人机后从D2中移出，并监测二次优化方案执行情况，之后执行S01。
调度中心将更新过后的二次优化方案(图10)和更新过后的无人机任务方案表(图11)发送给对应数据源和无人机或对应雾设备和无人机，即将更新过的请求任务Task1的任务分配方案发送给数据源D01和无人机U04；将更新过的请求任务Task2的任务分配方案发送给雾设备F02和无人机U01。之后将其从待二次优化集合D2中移出，并监测二次优化方案执行情况，重新返回执行S01。
以上所述仅为本发明的较佳实施方式，本发明的保护范围并不以上述实施方式为限，但凡本领域普通技术人员根据本发明所揭示内容所作的等效修饰或变化，皆应纳入权利要求书中记载的保护范围内。
