一种适配高强度弱连接环境的分布式任务分解方法

摘要

本发明公开了一种适配高强度弱连接环境的分布式任务分解方法。通过引入心跳检测机制，在分布式任务分解前确认链路情况，及时反馈通信中断或损毁信息处理节点信息。确认通信链路情况后在任务数量估算阶段引入交换区冗余处理系数和体系抗毁冗余增量系数为分布式任务分配冗余信息处理能力，通过冗余的策略保证信息处理任务在信息处理节点部分损毁的情况下仍然可以有效进行。最后，通过预估的任务数量调用k‑means聚类算法对分布式任务进行区域分解，得到任务分解结果。能够满足通信信号不稳定及信息处理设备易损条件下的分布式任务分解需求。解决分布式系统在通信不稳定或极端灾害情况下任务有效分解的问题。

说明书

技术领域

本发明属于分布式任务分解控制技术领域，尤其涉及一种适配高强度弱连接环境的分布式任务分解方法。

背景技术

随着分布式技术的发展，分布式处理技术可以将不同地点、不同配置的多套信息处理设备联合起来，在分布式控制系统的统一管理控制下，协调完成大规模信息处理任务，提高信息处理效率。分布式任务分解技术旨在将大规模信息处理任务分解成若干可执行的较小规模任务并分配任务范围给具体信息处理节点，是分布式处理技术较为核心的组成部分。其技术核心在于将合适的任务实时分配给合适的信息处理节点,已达到充分利用系统资源，提升任务完成效率的目的。

当前分布式任务分解技术主要分为再分配型和新任务型两类，其中再分配型主要解决封闭系统内部任务的再分配和调整问题，目前有负载均衡等成熟技术，新任务型主要解决新输入任务的分解处理问题，涌现了多Agent系统等多种动态任务分配方法。但这些技术多要求信息处理节点保持高度协同来有效执行分配任务，信息链路完整可靠且十分稳定。缺乏适配高强度环境以及通信遭到干扰时的应对方法。在实际应用过程中，复杂多变的环境场景会使得信息处理节点保持高度协同的期望受到多个维度的挑战，比如救灾或极端天气下的通信普遍存在干扰，信息处理节点间通信时断时续，无法建立稳定连接；地震，火灾等灾害会使得信息处理设备存在损坏情况，导致信息处理节点失能的后果，此时将任务分配给毁坏的信息处理节点无疑会使得整个系统信息处理效率下降。

发明内容

本发明针对自然灾害等高强度环境和通信信号不稳定情况下的分布式任务分解问题，提出一种适配高强度弱连接环境的分布式任务分解方法，能够满足通信信号不稳定及信息处理设备易损条件下的分布式任务分解需求。

为了解决上述技术问题，本发明公开了一种适配高强度弱连接环境的分布式任务分解方法，所述方法运行于分布式系统之上，包括以下步骤：

步骤1：输入信息处理任务。

步骤2：对所有信息处理节点进行心跳检测，若心跳检测发现所有信息处理节点均无法反馈心跳信号，则通知分布式系统心跳检测无效，将信息处理任务挂起，否则，通知分布式系统心跳检测有效，执行步骤3。

步骤3：根据心跳检测结果进行任务数量估算。

步骤4：调用k-means聚类算法进行任务处理范围划分，将步骤3估算的任务数量分配到计算区域。

步骤5：输出任务分解结果，完成分布式任务分解。

本发明步骤1中，信息处理任务队列采用优先级队列，赋予重要程度高的消息高优先级，保证其优先出队。

本发明步骤2中，通过设置心跳检测策略，在分布式任务分解前确认链路情况，及时反馈通信中断或损毁信息处理节点信息，规避将任务分配给毁坏或通信链路不通的信息处理节点计算的情况，提升分布式系统运算效率。其具体步骤如下所示：

（1）构建当前通信链路状况下的信息处理节点集

（2）对每一个信息处理节点

（3）若信息处理节点

（4）心跳检测完毕后若信息处理节点集

本发明步骤3中，通过引入冗余处理系数和体系抗毁冗余增量系数，为分布式任务分配冗余信息处理能力，保证信息处理设备性能不稳定或损毁时可提供冗余算力保证信息处理任务的有序进行。本发明按以下公式估算任务数量Sum：

Sum=

其中：

α表示冗余处理系数，表示分配的冗余信息处理能力，保证信息处理设备性能不稳定时冗余算力可以保证信息处理任务的有序进行。

β表示体系抗毁冗余增量系数，表示通过设置冗余设备提供冗余的信息处理能力，保证信息处理任务在信息处理节点部分损毁的情况下仍然可以有效进行。

本发明步骤4中，任务处理范围划分使用k-means聚类算法进行划分，聚类数设置为步骤3中输出的任务分解数量，迭代终止条件设置为中心点不再发生变化。

本发明通过引入心跳检测机制，在分布式任务分解前确认链路情况，及时反馈通信中断或损毁信息处理节点信息。确认通信链路情况后在任务数量估算阶段引入交换区冗余处理系数和体系抗毁冗余增量系数为分布式任务分配冗余信息处理能力，通过冗余的策略保证信息处理任务在信息处理节点部分损毁的情况下仍然可以有效进行。最后，通过预估的任务数量调用k-means聚类算法对分布式任务进行区域分解，得到任务分解结果。

本发明与现有技术相比，其显著优点为：（1）设置心跳检测策略，为解决高强度弱连接环境下的分布式任务分解问题，本发明在分布式任务分解前确认链路情况，及时反馈通信中断或损毁信息处理节点信息，规避将任务分配给毁坏或通信链路不通的信息处理节点计算的情况，提升分布式系统运算效率。（1）通过引入冗余处理系数为分布式任务分配冗余信息处理能力，保证信息处理设备性能不稳定时冗余算力可以保证信息处理任务的有序进行。（3）引入体系抗毁冗余增量系数，通过冗余的策略保证信息处理任务在信息处理节点部分损毁的情况下仍然可以有效进行。（4）任务区域分解算法采用k-means聚类算法，具有实践简单，收敛速度快，与数据输入顺序无关等特点。

附图说明

下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/或其他方面的优点将会变得更加清楚。

图1是本发明实现步骤流程图。

图2是本发明心跳检测步骤流程图。

图3是本发明任务处理范围划分步骤流程图。

具体实施方式

本发明公开了一种适配高强度弱连接环境的分布式任务分解方法。通过引入心跳检测机制，在分布式任务分解前确认链路情况，及时反馈通信中断或损毁信息处理节点信息。确认通信链路情况后在任务数量估算阶段引入交换区冗余处理系数和体系抗毁冗余增量系数为分布式任务分配冗余信息处理能力，通过冗余的策略保证信息处理任务在信息处理节点部分损毁的情况下仍然可以有效进行。最后，通过预估的任务数量调用k-means聚类算法对分布式任务进行区域分解，得到任务分解结果。能够满足通信信号不稳定及信息处理设备易损条件下的分布式任务分解需求。解决分布式系统在通信不稳定或极端灾害情况下任务有效分解的问题。

结合图1，根据本发明的一个实施例，一种适配高强度弱连接环境的分布式任务分解方法包括如下步骤：

步骤1：从信息处理任务队列中输入任务。

规则1.1：如果任务队列为空，处理流程将阻塞，直到等到新的任务到来。

步骤2：对所有信息处理节点进行心跳检测。

规则2.1：若心跳检测发现所有信息处理节点均无法反馈心跳信号，则通知系统心跳检测无效，将信息处理任务挂起，返回步骤1。

规则2.2：若心跳检测发现信息处理节点可以反馈心跳信号，则通知系统心跳检测有效，执行步骤3。

步骤3：根据心跳检测结果进行任务数量估算。执行步骤4。

步骤4：调用k-means聚类算法进行任务处理范围划分，将步骤3估算的任务数量分配到合理的计算区域。执行步骤5。

步骤5：输出任务分解结果，完成分布式任务分解。

步骤1中信息处理任务队列可以采用优先级队列，赋予重要程度高的消息高优先级，保证其优先出队。优先级策略可以和任务有效期或者任务提交时间相结合，例如同优先级情况下提交时间越早约优先，同优先级和同提交时间情况下失效时间越近越优先等。

步骤2中心跳检测旨在分布式任务分解前确认链路情况，及时反馈通信中断或损毁信息处理节点信息，规避将任务分配给毁坏或通信链路不通的信息处理节点计算的情况。其具体步骤如图2所示：

（1）构建当前通信链路状况下的信息处理节点集

（2）对每一个信息处理节点

（3）若信息处理节点

（4）心跳检测完毕后若信息处理节点集

步骤3中任务数量估算旨在根据应用任务处理总量和信息处理节点情况合理估算需要分解的任务数量，其与整个应用任务处理总量成正比，与单个计算节点处理能力成反比，另外需要考虑任务划分后的冗余处理系数、体系抗毁冗余增量系数。按以下公式估算任务数量Sum：

Sum=

其中：

α表示冗余处理系数，表示分配的冗余信息处理能力，保证信息处理设备性能不稳定时冗余算力可以保证信息处理任务的有序进行。例如：可以将冗余处理系数设置为1.2。

β表示体系抗毁冗余增量系数，表示通过设置冗余设备提供冗余的信息处理能力，保证信息处理任务在信息处理节点部分损毁的情况下仍然可以有效进行。例如：可以将体系抗毁冗余增量系数设置为1.5。

例如，某任务处理量为20000批，单个系统平均能处理1000批，冗余处理系数设置为1.2，体系抗毁冗余增量系数设置为1.5，则某任务数量估算的具体计算过程为：Sum=20000/1000*1.2*1.5=36，需要切分为36个处理区域，划分成36个处理任务。

步骤4中任务处理范围划分使用k-means聚类算法进行划分，k-means算法是典型的非监督学习方法，常用于空间聚类分析，该算法需要一个对每个对象值进行比较的准则函数，迭代过程线束的标准就是这个函数收敛，本发明中准则函数定义为：

其中

（1）构建当前通信链路状况下的信息处理节点集

（2）将步骤3中输出的任务数量作为聚类数k；

（3）在信息处理节点集S中随机选取k个点作为对象聚类的中心点，并根据这k个点初始化k个子集；

（4）将信息处理节点集S中所有对象点按照准则函数值最小原则分派到k个子集中；

（5）当所有点都分派到子集后，重新计算每个子集的中心点，将每个子集的质心作为新的中心点，获得k个新的中心点；

（6）判断是否达到收敛条件，若已达到收敛条件，则输出聚类结果，否则返回步骤（4）。

步骤4中k-means聚类算法使用的收敛条件一般为判定中心点是否改变，若保持不变，则认为算法已经收敛。

本发明提供了一种适配高强度弱连接环境的分布式任务分解方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。