时间触发以太网的分布式任务负载均衡分配方法

汤 宇，李 峭，贾琪明

（北京航空航天大学 电子信息工程学院，北京100191）

0 引 言

在实时分布式系统中，采用时间触发通信 （time－triggered，TT）可以避免数据帧争用物理链路，保证数据交换的严格的实时性，提高了离线任务负载均衡分配的效果。

时间触 发 以 太 网 （time－triggered Ethernet，TTE）［1，2］在交换式网络的环境下实现了可以精确到亚微秒量级的分布式时钟同步，为时间触发通信的调度提供了必要条件。

TTE调度表设计需要考虑的因素包括网络的物理拓扑、虚拟链路拓扑，以及时钟同步拓扑，并且与分布式综合应用的处理和通信任务的分配有关，这具体体现于：

（1）总线形网络 （如：SAE AS6003标准［3］定义的TTP）的时间触发调度面对的是共享介质的局域网，只需要一套公共的调度表；而对于TTE这种交换式网络，交换机端口之间是空分隔离的，不同网段可以同时传输不同的数据包；

（2）在传统的分布式任务分配中，采用分步骤的分配方法，通常先分配处理任务，然后再依据分配的结果对通信任务的调度，通信任务之间被认为是异步的；而在TTE网络中，为了实现分布式时钟精确同步下更深层次的应用综合，需要考虑处理任务和通信任务之间的同步配合关系，它们的分配与设计的优化相关联。

本文针对以TTE网络为互连基础设施的分布式综合系统，提出了一种将各个任务的多种设计约束转化定义为代价函数，并通过建立处理任务间的通信关系矩阵，将通信任务作为处理任务的参数，由此给出处理任务和通信任务统一地映射到嵌入式资源的方法，其目的在于优化整网的任务分配关系，提高整网中的节点和链路上的负载均衡程度，完成离线时刻调度表生成的预设计过程。

1 网络与任务模型的模型

1.1 时间触发以太网简介

时间触发以太网，采用时间触发代替事件触发的方式将通信任务通过合理的调度定时触发发送，可避免数据帧争用物理链路，保证实时性。其相应的规范由TTTech公司发布，并在2011年形成SAE AS6802标准［4］。时间触发通信可以支持远程任务之间同步处理，有望实现分布式综合模块化 （distributed integrated modular architecture，DIMA）的体系结构，并应用于航空、航天等嵌入式平台，例如：美国Orion载人飞船［5］采用1000BASE－CX物理层和双冗余配置的TTE网络综合互连方案，考虑了抗恶劣环境的高完整性。

1.2 网络的物理拓扑

在综合化航空电子系统中，采用交换机骨干网络将具有处理资源的嵌入式主机通过全双工的方式接入到交换网络中，处理任务不受限于主机的物理边界，在一定的约束下，软件构件可以在不同的标准化处理模块中运行。具体到DIMA架构［6，7］下，异构的处理主机，如：LRM集群或具有开放资源的LRU可以通过TTE网络互连进行综合化分区管理下的同步并行处理。图1所示的是DIMA架构下的航空电子互连的简单的例子。

图1 DIMA架构下的航空电子互联

为了求解任务分配问题，将功能分区相同的处理主机及其直接接入的交换结构抽象为一个网络节点，而节点之间的链路则由交换机之间的骨干链路所构成。例如：对于图1所示的航空电子系统，将执行相同功能的ES3、ES4连同它们之间的交换机抽象为一个处理集群，抽象后所形成的拓扑结构如图2所示。

图2 抽象出的拓扑结构

根据功能抽象后，用有向图G＝ （V，E）来表示处理节点之间的通信关系，如图2所示。其中V为网络节点集合，在TTE网络中为交换结构和与之相连接的处理机的合集，V＝ （v1，v2，…，vN），N为节点数量。E为连接节点的链路的集合，Q为链路数量，节点vi到节点vj（vi∈V，vj∈V）的链路e（e∈E）可以表示为eij。

采用连接矩阵A＝ （aij）N×N定义节点之间的联通关系，其中aij为

其中aij＝1表示节点vi有到节点vj（vi∈V，vj∈V）有链路连接，aij＝0则表示没有连接。

1.3 处理任务与通信任务

考虑到处理任务有可能分解到不同的综合化处理机运行，根据可以并发执行的部分，首先对待分配的处理任务进行分解，作为简化的假设，忽略分解后带来的额外开销。同时，对于任务之间由于应用需求而带来的依赖关系，通过将具有依赖性的关系的部分融合在一起。

分解后的处理任务集合用P表示，P＝ （p1，p2，…，pM），M为处理任务的数量，用μk表示处理任务pk在节点上所需要占用的资源量。

通信任务则对应着一个处理任务到另一个处理任务的应用层 “端到端”的有向流量。因而通信任务集合用C表示，那么对于任意c∈C，可以用三元组 （sk，tk，λk）表示，sk表示通信任务的发出任务，tk表示通信任务的接收任务，λk表示通信任务在的流量。

在TTE网络中，时间触发通信任务具有精确的时间确定性，使得处理任务和通信任务之间具有了明确的关联性。因而，可以建立处理任务间的通信关系矩阵B＝ （bij）N×N，其中bij为

通过建立处理任务间的通信关系矩阵，就可以将通信任务转化为处理任务的一个参数，从而能够统一地完成处理任务和通信任务的分配，达到更好的优化效果。

2 任务分配的优化

2.1 目标函数的确定

由于TTE网络［1，3］通信本身所具有的时间确定性，并且在TTE网络中，节点和链路上的负载均衡可以显著降低离线调度表生成的不可行的概率，同时也能保证整个网络中的各个部分都能有足够的空闲时间片剩余，以保证RC和BE任务的正常传输。因而本文使用TTE网络中节点和链路上的负载均衡程度来衡量任务分配方法的性能。

由于在给定的分配方案下，由于各个任务的粒度不同，使得各节点和链路上负载不可能完全一致，但可以通过定义如下的指标进行衡量

其中

由于上述定义的二次的指标与统计中方差的定义类似，所以这里也称之为衡量负载均衡的 “方差”。本文以TTE网络中处理任务和通信任务的方差之和作为目标函数，目标函数越小，则说明其负载均衡度越好

解集X＝ （x1，x2，…，xM），xk≤N，xk∈N＋，分别表示各个处理任务pk分配到第xk个节点上。

由于各个节点的处理能力以及各链路的带宽都是有限的，在分配时要考虑到各节点和链路的约束条件，因而本文采用惩罚函数的方法对非可行解进行处理，即在目标函数中加入惩罚函数，将有约束极值问题转化为带有罚函数的极值问题

式中：hk——节点vk在解集X 中所使用的资源量，hmaxk——节点vk所能处理的最大资源量，dk——链路ek在解集X中所使用的带宽，dmaxk——链路ek的最大带宽。M为一个比目标函数值大很多的正整数。在满足各节点和链路的约束条件的情况下，hk－hmaxk≤0，dk－dmaxk≤0恒成立，G（X）＝f（X）＋M×0，为可行解所得的函数值，从而起到剔除的作用。在实际问题中，某些处理任务只能在特定的一个或者几个处理器中处理，例如：某些信号处理只能在接近传感器的前端进行，这也可以使用罚函数表示这种选择特定处理节点的强约束关系。

2.2 通信任务路径选择

由于TTE网络拓扑所具有的任意性，在各个节点间会存在多条可行的通信任务路径。在通信任务路径的选择过程中，若选择最短通路 （采用图论中的Dijkstra算法［8］得出）则会导致某些链路上的负载过大，影响链路的负载均衡；若选择负载最低的通路则会导致转跳次数较多，增大整网的负载。同时，由于通信任务路径选择需要在每次目标函数的计算过程中都进行一次，因而，提出了一种快速的通信任务路径选择方法，具体步骤如下：

步骤1 将发出节点和接受节点间有链路直接相连的通信任务的路径确定为相连的链路。

步骤2 把剩余的任务按照最少转跳数tmin和所占带宽d的乘积的大小进行排序，从而得到剩余任务对于整网负载的影响程度的排序。

步骤3 按照影响程度从大到小依次确定任务的路径，任务的路径为在所有转跳数为tmin或tmin＋1的路径中，所经过的链路上的负载之和最小的路径。

这种通信任务路径选择方法均衡地考虑了转跳次数和链路的负载均衡，解决了两者之间的矛盾；算法的复杂程度较低，可以较快地得到通信任务路径，非常适合于在TTE网络拓扑中使用。

2.3 优化问题的求解

在约束和目标函数较为复杂的情况下，任意拓扑结构下任务与资源映射的组合优化问题很难采用解析方法，可以采用启发式算法，在有限的计算时间内寻找次优解。选用了模拟退火算法［9］，利用它较强的局部搜索能力求解任务均衡分配方案。

具体步骤如下：

步骤1 获取TTE网络的基本信息。包括网络的拓扑结构、处理与通信任务的相关参数以及网络节点及链路的约束条件。

步骤2 依据由于TTE网络通信本身所具有的时间确定性，对通信任务进行优化处理，将通信任务转化为处理任务的参数，以达到两者同时进行分配的效果。

步骤3 设定控制参数，即调整模拟退火法的冷却进度表。包括控制参数 “温度系数”的初值t0及其衰减函数α，以及马尔科夫长度。

步骤4 使用模拟退火算法进行求解，其运算过程如图3所示，包含内、外两层循环，内循环模拟升温过程，外循环模拟冷却过程，升温时在当前解X的邻域通过搜索能够改进目标函数值的解，为了能够摆脱局部极值，当改进量ΔG暂时没有优势时，以概率exp（－ΔG（X）／T）接受新解X←X（b），冷却时进行终止条件的判断。

图3 模拟退火算法流程

3 案例研究与仿真分析

在拥有4台节点的TTE网络仿真环境下对16个处理任务和64个通信任务进行分布式任务均衡分配。在本例中，暂不考虑处理任务的约束关系，各处理任务的负载见表1，TTE网络的网络拓扑如图4所示，各处理任务间的应用层 “端到端”的有向流量，即通信任务见表2（其中0已省略）。

图4 TTE网络拓扑

表1 处理任务的负载

表2 处理任务间的有向流量

利用编程仿真的方法分别对本文提出的处理任务和通信任务统一地映射的分配方法进行仿真。作为比较组，采用分步分配［10，11］的方法，即先进行处理任务分配，然后在此基础上进行通信任务分配。对于这个例子，仍然采用式（1）的算法，只不过在分配处理任务时，不考虑通信任务间的负载均衡情况，式 （1）中的f（X）＝σ2v，而在分配通信任务时，则不考虑处理任务间的负载均衡情况，f（X）＝σ2E。相当于分别用本算法的特例分两步解决任务分配问题，从而得到表3及图5中的数据。

表3 各节点的分配结果

图5 各链路的分配结果

由上述数据可以算出，使用统一分配的算法得到的目标函数值为9.9475，而使用分步分配的算法得到的目标函数值为174.9875。这说明使用统一分配算法在时间触发以太网任务分配上远远优于通常所使用的分步式分配方法。

这主要是因为传统的分步式分配方法虽然在分配处理任务的过程中取得了很好的效果，但是在分配通信任务时，由于处理任务的影响而无法达到很好的效果。而统一分配算法则利用了TTE网络通信所具有的时间确定性机制，将不同处理资源上的处理任务通过通信互连的关系联系起来，在整体上取得优化的效果。

4 结束语

本文以采用TTE网络的分布式综合化系统为研究背景。提出了一种将信息处理和通信任务统一处理的任务均衡分配方法。案例研究表明，该方法充分发挥了TTE网络通信本身所具有的时间确定性，将处理任务和通信任务统一地进行分配，相较于传统分配方法，提高了网络的整体负载均衡程度，可以有效改善网络的性能。

由于分布式任务均衡分配的复杂性，本文在处理任务间的依赖性关系及任务路径分析等方面采取了简化的手段进行处理，因此对此类问题如何进行优化分配还需要进一步深入探讨。

［1］Steiner W.TTEthernet specification ［S］.Austria：TTTech Computertechnik AG，2008.

［2］Jakovljevic M.Deterministic Ethernet：SAE AS6802 “Time－Triggered Ethernet” ［EB／OL］. ［2013－08－19］.SAE AS－2D2“Deterministic Ethernet and Unified Networking”Committee，http：／／www.sae.org／servlets／works／committeeHome.do？comtID＝TEAAS2D.

［3］SAE AS6003.TTP communication protocol［S］.

［4］SAE AS6802.Time－triggered Ethernet ［S］.

［5］McCabe Mary，Baggerman Clint，Verma Dinesh.Avionics architecture interface considerations between constellation vehicles［C］／／IEEE Digital Avionics Systems Conf，2009：25－29.

［6］Wolfig R，Jakovljevic M.Distributed IMA and DO－297：Architectural，communication and certification attributes ［C］／／27th Digital Avionics Systems Confe－rence，2008：26－30.

［7］RTCA DO－297.Integrated modular avionics （IMA）development guidance and certification considerations ［S］.

［8］Zhu Y，Liu X，Yu X.An optimal path algorithm of high security based on Dijkstra algorithm ［C］／／International Conference on Sensor Network Security Technology and Privacy Communication System.IEEE，2013：93－96.

［9］Matusiak M，de Koster R，Kroon L，et al.A fast simulated annealing method for batching precedence－constrained customer orders in a warehouse ［J］.European Journal of Operational Research，2013.

［10］LIU Yang，TONG Xiaonian.Research on network loading balance based on genetic simulated annealing algorithm ［J］.Computer ＆ Digital Engineering，2008，36 （9）：16－18 （in Chinese）.［刘阳，童小念.基于遗传模拟退火算法的网络负载均衡研究 ［J］.计算机与数字工程，2008，36 （9）：16－18.］

［11］HU Rong，YANG Chun.Energy－balanced multi－hop routing scheme based on simulated annealing algorithm ［J］.Computer Engineering，2010，36 （16）：71－73 （in Chinese）. ［胡荣，杨春.基于模拟退火算法的能耗均衡多跳路由方案 ［J］.计算机工程，2010，36 （16）：71－73.］