实时交通流量统计中均衡统计任务的方法及装置

摘要

本发明涉及一种实时交通流量统计中均衡统计任务的方法，所述方法包括如下步骤：取得前一次调度后表示各主机负载情况的综合负载向量；根据所述综合负载向量，得到每台主机的第一失衡参数，选择所有第一失衡参数小于设定阈值的主机作为参与本次调度的主机；按照每台主机的第一失衡参数在所有参与本次调度主机的第一失衡参数之和中所占的比例，将本次调度的任务分配到各主机；依据每个主机分配到的任务数，组合任务，准备数据并发送到各主机执行。本发明还涉及一种实现上述方法的装置。实施本发明的实时交通流量统计中均衡统计任务的及装置，具有以下有益效果：使得主机执行任务时间短、负载较为平衡。

说明书

技术领域

本发明涉及数据处理领域，更具体地说，涉及一种实时交通流量统计中均 衡统计任务的方法及装置。

背景技术

基于网格技术的城市路网交通流采集和统计通常需要大量的计算资源来 保证任务在规定时间内完成，网格能够共享广域环境下的大量空闲资源以满足 大规模任务的高性能需求，因而交通流采集和统计的任务可以利用网格来提高 任务的执行效率，降低执行时间。在现有技术中，在任务分配时通常不会对网 格中的节点加以区分，只是将任务平均地分配到该网格中的各个节点。但是， 网格是一个动态共享的环境，负载失衡会使得交通流采集和统计的实时性无法 得到保障，各个节点处理能力的差异，往往使得节点(通常是主机)间出现负 载不均衡的情况，在基于网格的交通流采集和统计任务中通常表现为超载节点 任务执行时间过长，使得整个交通流采集和统计任务的执行时间无法满足要 求，造成了系统资源的浪费，直接影响了网格系统的整体性能，违背了网格提 高资源利用率的初衷。

发明内容

本发明要解决的技术问题在于，针对现有技术的上述对于节点不加区分而 导致节点超载、执行任务时间长、造成网格系统性能下降的缺陷，提供一种区 分网格节点、执行任务时间短、网格系统负载较为平衡的实时交通流量统计中 均衡统计任务的方法及装置。

本发明解决其技术问题所采用的技术方案是：构造一种实时交通流量统计 中均衡统计任务的方法，所述统计任务由统计系统完成，所述统计系统包括多 个并行的、用于处理统计任务的主机；所述方法包括如下步骤：

A)取得前一次调度后表示各主机负载情况的综合负载向量；

B)根据所述综合负载向量，得到每台主机的第一失衡参数，选择所 有第一失衡参数小于设定阈值的主机作为参与本次调度的主机；

C)按照每台主机的第一失衡参数在所有参与本次调度主机的第一失 衡参数之和中所占的比例，将本次调度的任务分配到各主机；

D)依据每个主机分配到的任务数，组合任务，准备数据并发送到各 主机执行。

更进一步地，所述步骤A)中进一步包括如下步骤：

A1)取得前一次调度中各主机表示其负载情况的指标，得到各主机 上一次调度的负载向量；

A2)将各主机的负载向量依次排列，并对各主机相同的负载指标乘 以相同的设定权值，得到上次调度的综合负载向量。

更进一步地，所述步骤A1)中表示主机负载情况的指标为w个，其中至 少包括CPU队列长度和CPU使用率；其负载向量表示为：L_k＝(l_k1,l_k2,…,l_kw)， 其中，k表示第k个主机；在所述w个指标中，事先对每个指标赋予一定的权 值，加权后的负载向量为(α₁l_i1,α₂l_i2,…,α_wl_iw)，其中α₁,α₂,…,α_w分别是各负载指标 的权值；所述权值是事先设定的，不同主机的相同负载指标的权值相同。

更进一步地，所述步骤B)进一步包括：

B1)按照上一次调度各主机完成任务的时间，得到上一次调度中的 轻载主机，并得到其负载均衡向量；

B2)依次对所述轻载主机综合负载向量和负载均衡向量进行运算， 得到其第一失衡参数，并选择第一失衡参数小于设定阈值的主机参与本次调 度。

更进一步地，所述步骤B1)中进一步包括：

B11)取得参与上一次调度各主机完成任务的时间，将其相加后除以 参与上次调度的主机数量，得到上次调度的平均时间；

B12)计算每个主机上一次调度的时间参数，如果该主机未参与上次 调度，其时间参数为零；如果该主机参与上次调度，其时间参数为其完成上次 任务时间减去上述平均时间；

B13)逐个判断主机的时间参数是否小于或等于零，并将时间参数小 于或等于零的主机作为轻载主机，将其时间参数依次排列后得到负载均衡向 量，即B_i＝(b_i1,b_i2,…,b_is)，其中，b_i1是第1个轻载主机第i次调度的时间参数，s 是本次调度轻载主机的数量。

更进一步地，所述步骤B2)中进一步包括：

按照y_k＝u_k+B_i,k计算每个主机的第一失衡参数，选择该第一失衡参数 小于设定阈值TL的主机参与本次调度；其中，k是主机编号，其取值为1到 v中的整数；B_i,k是上述上一次调度的负载均衡向量中第k个主机的时间参数； u_k是所述上次调度中第k个主机加权后的负载向量。

更进一步地，所述步骤C)中进一步包括：

按照逐个计算被选择执行本次调度的主机执行的子 任务；其中，m是本次调度的总任务数；yk是该主机上次调度的第一失衡参数； 是所有被选中主机的第一失衡参数分别与设定阈值TL之差的和；s 是参与本次调度的主机个数；n_k是该主机本次调度分配的任务数。

本发明还涉及一种实现上述方法的装置，包括：

综合负载向量取得模块：用于取得前一次调度后表示各主机负载情况 的综合负载向量；

主机选择模块：用于根据所述综合负载向量，得到每台主机的第一失 衡参数，选择所有第一失衡参数小于设定阈值的主机作为参与本次调度的主 机；

任务分配模块：用于按照每台主机的第一失衡参数在所有参与本次调 度主机的第一失衡参数之和中所占的比例，将本次调度的任务分配到各主机；

任务发送模块：用于依据每个主机分配到的任务数，组合任务，准备 数据并发送到各主机执行。

更进一步地，所述综合负载向量取得模块进一步包括：

负载向量取得单元：用于取得前一次调度中各主机表示其负载情况的 指标，得到各主机上一次调度的负载向量；

综合负载向量取得单元：用于将各主机的负载向量依次排列，并对各 主机相同的负载指标乘以相同的设定权值，得到上次调度的综合负载向量；

所述表示主机负载情况的指标为w个，其中至少包括CPU队列长度 和CPU使用率；其负载向量表示为：L_k＝(l_k1,l_k2,…,l_kw)，其中，k表示第k个 主机；在所述w个指标中，事先对每个指标赋予一定的权值，加权后的负载 向量为(α₁l_i1,α₂l_i2,…,α_wl_iw)，其中α₁,α₂,…,α_w分别是各负载指标的权值；所述权值 是事先设定的，不同主机的相同负载指标的权值相同。

更进一步地，所述主机选择模块进一步包括：

负载均衡向量取得单元：用于按照上一次调度各主机完成任务的时 间，得到上一次调度中的轻载主机，并得到其负载均衡向量；

主机选择单元：用于依次对所述轻载主机综合负载向量和负载均衡向 量进行运算，得到其第一失衡参数，并选择第一失衡参数小于设定阈值的主机 参与本次调度；

所述负载均衡向量取得单元进一步包括：

平均时间取得子单元：用于取得参与上一次调度各主机完成任务的时 间，将其相加后除以参与上次调度的主机数量，得到上次调度的平均时间；

时间参数取得子单元：用于计算每个主机上一次调度的时间参数，如 果该主机未参与上次调度，其时间参数为零；如果该主机参与上次调度，其时 间参数为其完成上次任务时间减去上述平均时间；

负载均衡向量取得子单元：用于逐个判断主机的时间参数是否小于或 等于零，并将时间参数小于或等于零的主机作为轻载主机，将其时间参数依次 排列后得到负载均衡向量，即B_i＝(b_i1,b_i2,…,b_is)，其中，b_i1是第1个轻载主机第 i次调度的时间参数，s是本次调度轻载主机的数量；

所述主机选择单元按照y_k＝u_k+B_i,k计算每个主机的第一失衡参数，选择 该第一失衡参数小于设定阈值TL的主机参与本次调度；其中，k是主机编号， 其取值为1到v中的整数；B_i,k是上述上一次调度的负载均衡向量中第k个主 机的时间参数；u_k是所述上次调度中第k个主机加权后的负载向量。

实施本发明的实时交通流量统计中均衡统计任务的方法及装置，具有以下 有益效果：由于对节点(即执行任务的处理主机)加以区分，在上一次任务调 度中参与且负载较重的主机不参与本次调度，且在分配本次任务时也是按照上 次调度中各主机的负载均衡向量加以分配，充分保证了参与本次调度的主机是 按照其负载程度分配本次调度任务的，负载越重的主机在本次调度时分配的任 务越少，这样均衡了本次调度的任务，使得所有主机的任务在一定时间内是与 其处理能力适配的，从而使得主机执行任务时间短、负载较为平衡。

附图说明

图1是本发明实时交通流量统计中均衡统计任务的方法及装置实施例中 的方法流程示意图；

图2是所述实施例中选择参加本次调度的主机的具体流程图；

图3是所述实施例中装置的结构示意图；

图4是实施例中采用其方法后与未采用该方法的效果对比图。

具体实施方式

下面将结合附图对本发明实施例作进一步说明。

如图1所示，在本发明实时交通流量统计中均衡统计任务的方法及装置实 施例中，该方法包括如下步骤：

步骤S11取得前一次调度各主机的负载指标，得到其综合负载向量：在 本实施例中，大规模路网的实时交通流采集和统计由独立的各个路段的采集子 任务组成，子任务之间并不互相依赖。负载均衡问题的实质就是在网格环境下， 把m个子任务以合理的方式分配到v台主机上去，并希望得到尽可能小的总 执行时间。为了平衡任务的执行时间，在本实施例中，根据系统负载变化来分 配任务到各个主机，对低负载的主机分配较多的任务，而高负载主机分配较少 或不分配；同时根据各个节点(即主机)上任务执行时间的差距来调节各个节 点的负载，对本次调度(即本次采集和统计中的数据处理)中执行时间长于平 均任务执行时间的，在下次调度中减少任务量，反之则增加任务量。为此，需 要收集各个节点的负载信息，并结合上一次(或前一次)调度反馈的各子任务 的执行时间调整各个节点的任务分配，最后根据得到的任务量，将任务组合， 准备其数据，然后发送到各主机或节点进行处理。在本步骤中，就是采集各主 机执行上一次调度时的负载情况，各主机的负载情况通过多个负载指标表示出 来，每个主机或节点采集的负载指标的名称及其代表的物理意义是相同的，但 是由于每个主机的负载情况是不一样的，所以由各主机采集来的指标的数据可 能是不同的。在本步骤中，具体而言包括：取得前一次调度中各主机表示其负 载情况的指标，得到各主机上一次调度的负载向量；将各主机的负载向量依次 (按照事先设定的顺序)排列，并对各主机相同的负载指标乘以相同的设定权 值，得到上次调度的综合负载向量。在本实施例中，被选择用来表示主机负载 情况的指标为w个，其中至少包括CPU队列长度和CPU使用率；一个主机 的负载向量表示为：L_k＝(l_k1,l_k2,…,l_kw)，其中，k表示第k个主机；l_k1,l_k2,…,l_kw分 别表示该第k个主机的w个负载指标；然后，在上述w个指标中，事先对每 个指标赋予一定的权值，加权后的负载向量为(α₁l_i1,α₂l_i2,…,α_wl_iw)，其中 α₁,α₂,…,α_w分别是各负载指标的权值；所述权值是事先设定的，不同主机的相 同负载指标的权值相同。换句话说，对于多个主机而言，对每个主机所采集的 w个负载指标是相同的，且一个负载指标在不同的主机的加权值也是相同的， 同时，在负载向量中的位置也是相同的。例如，如果一个负载向量中第一个负 载指标是CPU队列长度，其加权值为1，则所有主机的负载向量的第一个负 载指标渎职CPU队列长度，且其加权值均为1。将上述得到的每个主机加权 后的负载向量作为矩阵的行，将主机编号作为矩阵的列，依次排列后得到综合 负载向量矩阵。即$U=\left(\begin{array}{c}{u}_1\\ u_2\\ ·\\ u_v\end{array}\right)=\left(\begin{array}{c}{\alpha }_1{l}_{11}+{\alpha }_2{l}_{12}+...+{\alpha }_w{l}_{1w}\\ {\alpha }_1{l}_{21}+{\alpha }_2{l}_{22}+...+{\alpha }_w{l}_{2w}\\ ···\\ {\alpha }_1{l}_{v1}+{\alpha }_2{l}_{v2}+...+{\alpha }_w{l}_{\mathrm{vw}}\end{array}\right).$

步骤S12取得上一次调度中各主机的任务完成时间，得到其负载均衡向 量：在本步骤中，取得上一次调度时各主机完成分配到的任务的时间，通过这 些时间，可以得到多个主机完成上次调度的平均时间，每个主机完成任务的时 间和上述平均时间比较，就能在一定程度上看出该主机的负载情况。在本实施 例中。对于上述每个主机完成任务的时间和平均时间的关系，就是该主机在上 一次调度的时间参数；通过这个时间参数，就能得到上一次调度该主机的负载 均衡向量，即B_i＝(b_i1,b_i2,···，b_iv)，其中，b_i1是第一个主机第i次调度(即对 于本次调度而言的上一次调度)的时间参数，b_i2是第2个主机第i次调度的时 间参数，b_iv是第v个主机第i次调度的时间参数；至于其中具体的步骤，稍后 详述。

步骤S13对得到的两个向量进行运算，得到各主机的第一失衡参数，选 择失衡参数小于设定阈值的主机参与本次调度：在本步骤中，将上述步骤中得 到的两个向量进行运算，分别得到对应于每个主机的第一失衡参数，该第一失 衡参数表示在前一次调度中该主机的负载情况，如果一个主机的第一失衡参数 小于事先设定的设定阈值，则表示该主机上一次调度的负载较为均衡，可以参 加本次调度；如果一个主机的上述第一失衡参数大于或等于上述事先设定的设 定阈值，则不选择该主机参与本次调度。在本实施例中，按照y_k＝u_k+B_i,k计算 每个主机的第一失衡参数，选择该第一失衡参数小于设定阈值TL的主机参与 本次调度；其中，k是主机编号，其取值为1到v中的整数；B_i,k是上述上一 次调度的负载均衡向量中第k个主机的时间参数；u_k是所述上次调度中第k 个主机加权后的负载向量。

步骤S14逐个计算分配给参与本次调度主机的任务：由于上述步骤已经 选择了参与本次调度的主机，在本步骤中，就是将本次调度的任务合理地分配 到这些参与本次调度的主机中。具体而言，在本实施例中，按照 逐个计算被选择执行本次调度的主机执行的子任务；其中， m是本次调度的总任务数；y_k是该主机上次调度的第一失衡参数；是 所有被选中主机的第一失衡参数分别与设定阈值TL之差的和；s是参与本次 调度的主机个数；n_k是该主机本次调度分配的任务数。值得一提的是，在本步 骤中，分别对上述被选择参与本次调度的主机进行上述子任务的计算，使得每 个被选择参与本次调度的主机都按照上述规则分配其在本次调度需要执行的 任务数；全部被选择的主机分配任务数的总和就是本次调度的任务总数。

步骤S15组合任务，准备数据并发送给相应主机执行：在本步骤中，根 据每个主机的任务数，将本次调度的任务进行组合，准备执行这些任务的数据， 并将这些数据发送到相应的主机进行处理。值得一提的是，在本实施例中，这 些任务时独立同构的，即其相互独立，但是其结构相同。

上述步骤是一次调度时执行的步骤。在实际使用中，一个系统中的调度时 不断进行的，上述步骤也是不断进行的。这样，每次调度时都是按照上述步骤， 依据上一次调度时个主机的负载情况动态地选择参与本次调度的主机以及动 态地为参与本次调度的主机分配任务，使得整个系统的负载情况能够依据其实 际的负载情况得到均衡，从而使得主机执行任务时间短、负载较为平衡。

对于选择参与本次调度的主机，在本实施例中，具体的方法如图2所示， 包括如下步骤：

步骤S21取得前一次调度各主机的任务完成时间，得到其平均任务时间： 在本步骤中，分别取得参与前一次调度的主机完成上一次调度任务的时间，将 其相加，并除以参与上一次调度的主机数量，得到上次调度任务完成的平均时 间。

步骤S22得到各主机前次调度的时间参数：在本步骤中，分别计算全部 主机对于前一次调度而言的时间参数，具体而言，如果该主机未参与上次调度， 其时间参数为零；如果该主机参与上次调度，其时间参数为其完成上次任务时 间减去上述平均时间。

步骤S23选择小于零的时间参数的主机为轻载主机，得到其负载均衡向 量：上一步骤中已经得到各主机的时间参数，在本步骤中，选择其时间参数小 于或等于零的主机，将其定义为轻载主机，表明这些主机在上一次调度时其负 载较轻，可能可以用于本次调度；同时，在本步骤中，还将所有主机的时间参 数进行排列，得到前一次调度的负载均衡向量，即B_i＝(b_i1,b_i2,···，b_iv)， 该向量表示各主机在前一次调度中的负载失衡程度。

步骤S24逐个运算得到轻载主机的第一均衡参数：在本步骤中，针对上 述得到的轻载主机，逐个计算其第一均衡参数。即按照y_k＝u_k+B_i,k计算每个主 机的第一失衡参数，选择该第一失衡参数小于设定阈值TL的主机参与本次调 度；其中，k是主机编号，其取值为1到v中的整数(在本实施例中，对于上 述轻载主机而言，k不一定是连续的，但是对于一个轻载主机而言，k一定是 1到v中的一个)；B_i,k是上述上一次调度的负载均衡向量中第k个主机的时间 参数；u_k是所述上次调度中第k个主机加权后的负载向量。在本步骤中，上述 轻载主机有多少个，就按照上述公式计算多少次，直到每个轻载主机都得到自 己的表示其在上一次调度中的负载失衡程度的第一均衡参数。

步骤S25选择第一均衡参数小于设定阈值的主机参与本次调度：在本步 骤中，分别将上述得到的多个第一均衡参数与事先设定的设定阈值TL比较， 如果其值小于TL，则选择该主机参与本次调度；否则，不选择该主机参与本 次调度。

值得一提的是，上述描述仅仅是为了便于说明问题。在本实施例中，上述 步骤在实际使用时可以做出适当的调整，例如，计算出一个轻载主机的第一均 衡参数，就立即将其与设定阈值比较，从而马上决定该主机是否参与本次调度。

在本实施例的一个例子中，本实施例中的方法也可以用伪代码表示如下：

BEGIN

初始化向量B₀＝(b₀₁,b₀₂,…,b_0v)的各个分量为0

FOR任务i(1≤i≤n)

从各个主机收集基本负载指标

将基本负载指标组装成负载向量,计算综合负载向量U＝(u₁,u₂,…,u_v)

FOR主机k(1≤k≤v)

计算y_k＝u_k+βb_i-1,k

IF y_k<TL THEN

h_k为轻载节点,加入轻载节点向量

END IF

END FOR

计算分配到各个轻载节点的任务量

根据任务量组合各个作业

提交任务到选择的各个节点

任务返回后得到各个节点的任务执行时间T_i＝(t_i1,t_i2,…,t_is)

计算负载失衡向量B_i＝(b₁,b₂,…,b_v)

END FOR

END

在一个例子中，以一个具有30台主机的网格环境为实验目标,这30台主机的 配置如表1。

表1 节点配置

网格环境使用的是GlobusToolkit 4.0。这30台主机间使用千兆以太网连接, 这些主机除了参与网格任务外,还不断被调度运行其他科学计算任务,因此在 网格任务中时常出现负载失衡的情况,使用这些节点来进行交通流采集和统 计,需要负载均衡来降低任务的执行时间。

首先使用100,300,500,1000个路段的交通流采集和统计任务进行实验,可 在调度中得到图4的结果(在图4中，有斜条的表示采用本实施例中方法的调度 所用的时间)。从图4中可以发现随着任务量的增加自适应算法仍然能够较好的 平衡各个节点的负载,使得任务的完成时间较低。在不使用负载平衡时,任务 量从100到1000执行时间增加了31.62s,而使用本实施例中的负载平衡的时间 仅增加了15.28s。

此外，在本实施例中，还涉及一种实现上述方法的装置，图3中示出了该 装置的结构。在图3中，该装置包括：综合负载向量取得模块1、主机选择模块 2、任务分配模块3和任务发送模块4；其中，综合负载向量取得模块1用于取得 前一次调度后表示各主机负载情况的综合负载向量；主机选择模块2用于根据 所述综合负载向量，得到每台主机的第一失衡参数，选择所有第一失衡参数小 于设定阈值的主机作为参与本次调度的主机；任务分配模块3用于按照每台主 机的第一失衡参数在所有参与本次调度主机的第一失衡参数之和中所占的比 例，将本次调度的任务分配到各主机；任务发送模块4用于依据每个主机分配 到的任务数，组合任务，准备数据并发送到各主机执行。

在本实施例中，上述综合负载向量1取得模块进一步包括：负载向量取得 单元11和综合负载向量取得单元12；其中，负载向量取得单元11用于取得 前一次调度中各主机表示其负载情况的指标，得到各主机上一次调度的负载向 量；综合负载向量取得单元12用于将各主机的负载向量依次排列，并对各主 机相同的负载指标乘以相同的设定权值，得到上次调度的综合负载向量；所述 表示主机负载情况的指标为w个，其中至少包括CPU队列长度和CPU使用 率；其负载向量表示为：L_k＝(l_k1,l_k2,…,l_kw)，其中，k表示第k个主机；在所述 w个指标中，事先对每个指标赋予一定的权值，加权后的负载向量为 (α₁l_i1,α₂l_i2,…,α_wl_iw)，其中α₁,α₂,…,α_w分别是各负载指标的权值；所述权值是事先 设定的，不同主机的相同负载指标的权值相同。

此外，上述主机选择模块2进一步包括：负载均衡向量取得单元21，其 用于按照上一次调度各主机完成任务的时间，得到上一次调度中的轻载主机， 并得到其负载均衡向量；主机选择单元22，其用于依次对所述轻载主机综合 负载向量和负载均衡向量进行运算，得到其第一失衡参数，并选择第一失衡参 数小于设定阈值的主机参与本次调度；其中，负载均衡向量取得单元21进一 步包括：平均时间取得子单元211，其用于取得参与上一次调度各主机完成任 务的时间，将其相加后除以参与上次调度的主机数量，得到上次调度的平均时 间；时间参数取得子单元212，其用于计算每个主机上一次调度的时间参数， 如果该主机未参与上次调度，其时间参数为零；如果该主机参与上次调度，其 时间参数为其完成上次任务时间减去上述平均时间；负载均衡向量取得子单元 213，其用于逐个判断主机的时间参数是否小于或等于零，并将时间参数小于 或等于零的主机作为轻载主机，将其时间参数依次排列后得到负载均衡向量， 即B_i＝(b_i1,b_i2,…,b_is)，其中，b_i1是第1个轻载主机第i次调度的时间参数，s是本 次调度轻载主机的数量；

在本实施例中，主机选择单元22按照y_k＝u_k+B_i,k计算每个主机的第一 失衡参数，选择该第一失衡参数小于设定阈值TL的主机参与本次调度；其中， k是主机编号，其取值为1到v中的整数；B_i,k是上述上一次调度的负载均衡 向量中第k个主机的时间参数；u_k是所述上次调度中第k个主机加权后的负载 向量。

上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细， 但并不能因此而理解为对本发明专利范围的限制。应当指出的是，对于本领域 的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和 改进，这些都属于本发明的保护范围。因此，本发明专利的保护范围应以所附 权利要求为准。