多源异构传感通信大数据的融合调度算法

王延松，戚 湧，李千目

（1. 中兴通讯股份有限公司 南京研发中心，江苏 南京 320100；

2. 南京理工大学 计算机科学与工程学院，江苏 南京 210094）

多源异构传感通信大数据的融合调度算法

王延松1，戚 湧2*，李千目2

（1. 中兴通讯股份有限公司 南京研发中心，江苏 南京 320100；

2. 南京理工大学 计算机科学与工程学院，江苏 南京 210094）

本文研究了在能量受限条件下服务于多种类型的数据处理和传输的多源异构通信簇交通传感器节点系统的最优大数据的融合调度控制问题。传统方法需要大量关于系统动态的统计信息，并且求解效率低。使用针对更新帧的李雅普诺夫优化技术，本文设计了一种新的在线多源传感通信大数据融合调度算法来克服以上困难。仿真实验表明所设计算法稳定、鲁棒，为后续利用交通传感器网络传输大规模数据奠定基础。

多源异构；交通大数据；数据融合

0 引言

受传统交通传感器系统设计机制的制约，单一传感器系统的探测覆盖范围、通信传输能力、抗毁性均不能满足海量数据快速、高效分发的智能交通大数据平台实际需求，因此需建立包含大量微小、低功率和低重量交通传感器单元的多源异构通信簇系统，该系统作为运行在大数据空间环境的特殊“大数据空间感知网络”，其内成员交通传感器在大数据空间使用自组织、自管理技术，网络化协同完成一系列大数据空间探测任务。一个大的多源异构通信簇包含若干子簇，子簇针对某一交通区域观测任务而临时灵活组织，其内交通传感器成员分为3类：负责指挥协调群内成员交通传感器的指挥者（Rulers）、携带着专用探测设备的大量实施者（Workers）和负责协调组织指挥者、实施者和汇聚站之间数据通信的信使（Messengers）。尽管这些异构的微小交通传感器有着不同的载荷、角色和职责，但它们都主要依赖太阳能进行数据采集、处理和通信，由于交通传感器的太阳能帆板尺寸的限制，必须在设计这样的多源异构通信簇系统时考虑能量效率问题。因此，对于多源异构通信簇来说，选择合适的交通传感器工作模式，在保证系统稳定和能耗约束的条件下，设计交通传感器工作状态的在线大数据融合调度算法以最大化时均系统的数据接纳量等均是亟待解决的问题。

图1 交通传感器工作大数据融合调度过程示意图Fig.1 Big data fusion scheduling process for traffic sensors

本文主要针对能量受限约束下交通传感器工作大数据融合调度技术开展研究，交通传感器工作大数据融合调度过程示意图如图1所描述。考虑微小交通传感器能量消耗与供电限制，首先选定交通传感器工作模式，分别建立多源异构通信簇系统模型和虚拟队列模型。在此基础上，采用基于李雅普诺夫优化技术的在线大数据融合调度算法求解能量受限交通传感器的工作状态调度问题。

1 能量受限微小交通传感器工作模式分析

考虑到微小交通传感器特别是信使星的能耗限制、准实时数据处理和传输能力要求，本文引入占空比（Duty-Cycled）工作模式。该模式已被广泛应用于无线传感器网络和下一代移动通信网络的非实时数据通信。该方式具体操作模式如下：多源异构通信簇系统内共有N类数据流（如负责多个Workers信息传输的Messenger），每类数据随机到来并按其类别被分别存储，等待处理和传输。如图2所示，多源异构通信簇按照“帧（Frame）”（或称更新帧，Renewal Frame）为单位的周期运行，每个帧r开始于一段固定长度的活动周期D，结束于一段非固定长度的休眠周期 []Ir。

图2 更新帧活动阶段、休眠阶段时间线示意图Fig.2 Updating frame activity phase and sleep phase time line

在第r帧的开始，多源异构通信簇系统从多个可选项中选择一个服务模式 []mr，该服务模式决定在第r帧中服务哪个数据流及其数量，以及带来的相应能耗。完成数据处理和传输后，多源异构通信簇系统将选择一段时间 []Ir进行休眠，当休眠结束后，系统恢复工作，新的帧开始。

2 能量受限微小交通传感器工作大数据融合调度模型构建

为了方便问题的分析，需要做以下几点假设，分别如下：

1. N个交通传感器节点按照设计协议的要求布置在某个交通区域内。如果协议需要，位于事件区域的交通传感器节点可以形成簇。

2. 交通传感器节点保持静止不动或者按照仿真场景里设计好的轨迹（移动式传感系统）进行运动。

3. 所有交通传感器节点能量有限，电池无法更替，电池消耗完，节点也随之死亡。

4. 交通传感器节点能够借助于全球定位系统(GPS)的设备来获取自己的大数据空间位置。

5. 通信是双向的。

6. 地面汇聚节点的能量无限大。

7. 对于需要进行时间判断的协议，要求所有的节点时间大致同步。

图3 随机流量、流量控制和服务调度下的一个多源异构通信簇系统Fig.3 A multi-source heterogeneous communication cluster system with random traffic, traffic control and service scheduling

如图3所示，考虑一个有着N类数据流的多源异构通信簇系统。每一类数据按照一种独立同分布的随机过程到达每个交通传感器，速率分别为λ1,… ,λN。假设存在有限常量λmax，使得对所有类型数据有这些数据按照类别分别存放在不同的队列。使用 Qn(t)表示t时刻队列中累计的第n类数据。多源异构通信簇系统在连续时间内运行，因此时间索引t从非负实数的集合里取值。对于所有的 n ∈ { 1,… ,N }和所有的 t ≥ 0 ，Qn(t)的值都是非负实数。假设系统开始于 t = 0 时刻，队列为空，即对于所有 n ∈ { 1,… ,N }有 Qn( 0) = 0。

多源异构通信簇系统在每个帧的开始时刻进行控制决策。第一帧被定义为帧0，开始于时刻0。在每一个帧 r ∈ { 0,1,2,…} 开始，系统选择控制决策变量c[r]、 m [r]，其中 c[r]∈ { 0,1,… ,N }，表征哪一类数据流将会被服务， c[r]= 0 表明没有数据流被服务且带来非常少的能量消耗； m [r]∈M，M为服务模式集合。控制决策决定了所有 μn[r],n ∈ { 1,… ,N}，μn[r]表示在帧r的活动阶段中可以被处理的第n类数据流量，同时也决定了系统能耗 e[ r]。处理结束后，多源异构通信簇系统从区间 [ 0,Imax]中选择一段休眠时间 I[r]，其中 Imax为某个给定的非负值。休眠状态下的能耗非常低，甚至可以被忽略。定义T[r] ∈ [ D,D + Imax]为总帧长，上述变量可以使用泛化函数定义如下：

其中，式（4）（5）在任何控制策略下均成立。

对于任一类数据流 n ∈ { 1,… ,N }，流程控制变量γn[ r]∈ [ 0,1]，该变量表示在帧r内新随机到达的第n类数据的接纳概率。这使得系统能在 Qn无法在数据到达速率λn条件下正常处理数据时，拒绝第n类数据进入队列。拒绝接纳新数据时一种常见的情况，无法立即接纳的到达数据被缓存起来等待之后的接纳决策。

最后，对于每一类数据流 n ∈ { 1,… ,N }，我们定义 An[r]为第r帧中接纳的新到达数据，这些数据取决于帧的全长(D + I [r])和接纳概率 γn[ r]。假设到达向量 ( A1[ r] ,… ,AN[r ])与过去条件独立，且数学期望为：

3 工作大数据融合调度模型

能量受限的微小交通传感器工作大数据融合调度问题的决策变量分别为其为整数决策变量， c[r]∈ { 0,1,… ,N }，m[r]∈M，用以决定多源异构通信簇系统在第r帧内服务的数据流类型、数量及相应的系统能耗。为连续决策变量，表示多源异构通信簇系统在第r帧内的休眠时间， γn[ r]∈[0,1]表示r帧内系统接纳第n类新到达数据的概率，为简化计算，本文采用接纳/拒绝布尔控制决策，即

多源异构通信簇系统中第n类数据帧平均数据处理速度为：

多源异构通信簇系统中帧平均新到达第n类数据流量为：

平均帧长为：

多源异构通信簇系统中第n类数据时均处理速度为：

多源异构通信簇系统接纳第n类数据的时均速率为：

为使多源异构通信簇系统中所有数据队列保持稳定，则每个队列接纳第n类数据的时均速率不可超出系统对该类数据的服务速率，即：

1. 系统能耗约束

多源异构通信簇系统的帧平均能耗为：

由于多源异构通信簇系统内交通传感器成员能量受限，因此系统时均能耗速率应维持在给定常量P内，即：

2. 工作大数据融合调度模型

能量受限交通传感器的工作状态调度问题的优化目标为最大化时均接纳数据流量加权和，综上，能量受限交通传感器工作大数据融合调度模型为：

由于在每帧内对能量受限交通传感器集群系统的控制决策需兼顾系统稳定性和系统性能优化两个方面，因此利用李雅普诺夫优化中的“漂移加惩罚”（Drift-plus-Penalty）技术将模型[15]的优化目标等效替换为：

其中，[]rΔ为能量受限交通传感器集群系统的李雅普诺夫漂移，用以表征系统内数据队列的拥塞程度，即系统稳定性； []Fr为能量受限交通传感器集群系统的李雅普诺夫惩罚，表征要优化的目标函数；V是非负权值，用以控制系统稳定性和系统性能优化的相对重要程度。

定义虚拟队列 Qn[r] ,Z[r]， Qn[r]为第r帧时，系统中存储第n类数据虚拟队列，其更新原则及初始条件如下：

Z[]r为第r帧时系统的总能耗虚拟队列，其更新原则及初始条件如下：

4 能量受限微小交通传感器工作大数据融合调度算法设计

4.1 基本输入要素

4.1.1 交通传感器工作状态调度周期

交通传感器工作状态调度周期描述了进行能量受限交通传感器的工作状态调度需考虑的时间范围，它有两层含义：

1. 所有多源异构通信簇系统的数据传输与处理必须在调度周期内执行；

2. 必须在调度周期内最大化系统的时均数据接纳数量，尽可能地延迟交通传感器工作寿命，同时处理和传输尽可能多的数据。

4.1.2 数据流信息

数据流信息包括多源异构通信簇系统将接收和处理的数据流类型、到达过程描述及交通传感器对每类数据的处理速度等。本文假设每类数据按照独立同分布的伯努利过程随机到达。

4.1.3 交通传感器工作状态

交通传感器的工作状态可以由如下一些基本属性来描述：

1. 工作模式

由于在交通区域探测应用场景中并不需要非常实时的数据传输和处理能力，考虑到交通传感器的能量消耗与供电限制，交通传感器不需要一直处于工作状态，本文采用占空比工作模式，多源异构通信簇系统按照“帧”为单位周期运行，帧由固定长度的活动周期和可变长度的休眠周期组成。因此，交通传感器工作状态调度周期可由帧数量定义。

2. 服务模式集合

交通传感器有多个可选服务模式，用以决定在一个帧周期内该交通传感器服务的数据流数量及带来系统能耗。在每帧开始时刻，系统为交通传感器选择一个特定的服务模式，在整个帧周期内，该交通传感器均按照此服务模式接收和处理数据，在帧切换时，系统为交通传感器重新选择服务模式。

3. 服务数据流类型集合

服务数据流类型决定了交通传感器按照系统为其选定的服务模式服务哪类数据流，可服务数据流类型集合为系统中所有数据流类型集合。

4. 新数据流接纳控制决策

4.1.4 交通传感器平台

1. 数据存储容量

有效载荷获取的观测数据首先保存于交通传感器存储器中，当交通传感器获得数传资源后将数据下传至地面。交通传感器的数据存储容量是制约工作状态调度结果的一个重要因素。

2. 交通传感器平台的名称

交通传感器平台的名称主要指星载遥感器所在交通传感器的名称。

3. 交通传感器的轨迹（移动式传感系统）参数

交通传感器的运行轨迹（移动式传感系统）一般通过6个参数来描述，即：升交点赤经Ω（RAAN，Right Ascension of the Ascending Node），轨迹（移动式传感系统）倾角i（Inclination），近地点角w（Argument of Perigee），轨迹（移动式传感系统）长半轴a（Semi-major Axis），轨迹（移动式传感系统）偏心率e（Eccentricity），及交通传感器飞过近地点的时刻τ。交通传感器的轨迹（移动式传感系统）参数决定了其在轨运动过程中，与地球之间的相互几何关系，是计算交通传感器与地面目标可见时间窗口的直接依据。

4. 交通传感器可用电源容量

需要考虑交通传感器完成交通区域观测任务时进行姿态和轨迹（移动式传感系统）机动、有效载荷工作等所消耗的电量。

5. 交通传感器可用燃料

需要考虑交通传感器完成交通区域观测任务时进行姿态和轨迹（移动式传感系统）机动所消耗的燃料。

4.2 基本输出要素

工作状态调度的最终输出结果主要是工作状态调度方案，主要包括交通传感器将接纳何种类型的数据，服务数据的类型、数量及所耗能源，该交通传感器的休眠时长。对某颗交通传感器来说，其分配结果具体可以表示为如下的一个4元组：

4.3 大数据融合调度算法

本文采用下述算法求解交通传感器工作大数据融合调度问题。

交通传感器工作大数据融合调度算法在第r帧时，观察系统当前队列向量[]rΘ并执行如下步骤：1. 数据流控制：对于每类数据流 {1, ,}n N= … ，按照如下原则选择流量控制变量 []nr γ ■n ≤ ωn n γ ：1, [] V[] 0, otherwise ifQ r r =■■2. 服务调度：选择控制行为 [],[],[]crmrIr，以最小化漂移加惩罚比率-∑D+I 3. 更新队列：对于每类数据流 {1, ,}ZrecrmrIr Q r crmrIr r[]([],[],[]) [] ([],[],[])[]ˆ N n n n=1μˆ μ 和 []er带入式（17）（19）来更新虚拟队列向量 [] ([],[])。n N= … ，使用获得的流量控制变量 []γ , []nr nr Θr QrZr=

5 算法验证与分析

本文考虑一个城市隧道交通传感器节点系统，根据多源载荷，共处理10类不同的数据，并具有2种不同的处理方式。对于每种类型 n ∈ { 1,2,… ,1 0}，数据流量按照独立的伯努利过程到达。对所有类型的数据设置权值 wn= 1 ，即能量受限交通传感器的工作状态调度问题的优化目标为最大化总体吞吐。假设 P = 0 .5W，更新帧内活动周期 D = 5 0s，休眠周期为 I ∈ [ 0,10]s，交通传感器系统在休眠状态下的能耗忽略不计，即eˆ(c [ r],m[r],I[r] ) = eˆ(c[r],m[r ])。对每类数据的到达速率λn(Mbps)、处理数据流量μn(Mb)、能耗eˆn(J)的设置如下表所示：

表1 参数设置Tab.1 Parameter setting

首先，在1000帧范围内针对不同的控制参数V对大数据融合调度算法进行了仿真。在图4中，我们给出了系统所达到的平均接纳速率。从图中可知，接纳速率随着V的增长，收敛于最优值（实际总体到达速率）1.56212Mbps，并呈现出 o ( 1/V )的变化差距。为了对比，同时仿真了另外一种随机调度算法，该算法随机选择可行的控制决策，并使用简单的接纳策略，在An＞μn时迫使An[r]= 0 ，以保证队列 Qn的稳定。随机调度算法10000次，最终发现其作用下的接纳速率范围在1.1978Mbps到1.4574Mbps范围之间，当V>210时，大数据融合调度总体吞吐率大于随机调度总体吞吐率上界。结果表明，当V足够大时，我们设计的基于李雅普诺夫优化技术的大数据融合调度算法能确保更好的数据接纳率。

图5给出了1000帧内的平均队列长度及理论平均队列长度。由图中可以看出，当V<570时，平均队列长度呈线性增长趋势；当V≥570时，队列长度达到饱和，饱和值即为直接接纳所有到达数据时的平均队列长度。

综上，调节参数V可以达到接纳数据量与队列长度之间的折中。

图4 不同V条件下的总体吞吐率Fig.4 Overall throughput under different V conditions

图5 不同V条件下的平均队列长度Fig.5 Average queue length under different V conditions

图6给出了不同V条件下的交通传感器系统平均能耗速率，可以看出，图中6种情况下系统均能满足能耗约束，即平均能耗速率小于能耗门限0.5Watt。随着V的增加，系统的平均能耗速率减少，这是因为我们设计的交通传感器状态大数据融合调度算法通过使虚拟队列 []Zr稳定而保证了整个系统的能耗限制。当V较大时，虚拟队列变得不太稳定，算法将会更频繁的选择较长时间休眠周期而降低能耗，因为系统在休眠周期内的能耗计算忽略不计。综上，系统的平均能耗速率将随着 V和 []Ir的增大而下降。

为验证大数据融合调度算法对突发到达速率变化的鲁棒性。本文设计了两组到达速率突变的仿真场景，分别为在第350帧至700帧之间将所有类型数据的到达速率增加为原值的2倍和4倍。图7、图8分别给出了到达速率突变时系统平均吞吐率与平均队列长度变化示意图。从图7，图8可以看出，当r < 350帧时，所有类型数据均可被系统接纳，当数据到达速率突变时，系统平均队列长度迅速增加，因此系统频繁的拒绝接纳进入低服务速率的队列数据。当 r=700帧时，数据到达速率恢复原值，一些拥塞严重的队列仍在一段时间内拒绝接纳新的数据到达，因此系统平均吞吐率持续低于原来的值约114帧（数据到达速率突变2倍）、125帧（数据到达速率突变4倍）后才恢复原值。另外可以得到系统的理论平均队列长度为579.373 Mb，和数据到达速率突变无关。

图6 不同V条件下的平均能耗速率Fig.6 Average energy consumption rate under different V conditions

为探究权值变化对控制决策与优化结果的影响。考虑两种数据类型，其权重设置为 w1= 1 ,w2=2。从图9可以看出，当V相对较大时，权值将会对控制决策和个体队列数据吞吐率有影响，并且队列将会按照权值设置分别得到服务，这是因为V表征着系统稳定性与优化目标的相对重视程度，只有当 V达到一定程度时，优化目标才会在算法执行中得到明确体现。

6 结束语

本文研究了在能量受限条件下服务于多种类型的数据处理和传输的多源异构通信簇交通传感器节点系统的最优大数据的融合调度控制问题。传统方法需要大量关于系统动态的统计信息，并且求解效率低。使用针对更新帧的李雅普诺夫优化技术，本文设计了一种新的在线多源传感通信大数据融合调度算法来克服以上困难。仿真实验表明所设计算法稳定、鲁棒，为后续利用交通传感器网络传输大规模数据奠定基础。

图7 到达速率突变时系统平均吞吐率Fig.7 Average throughput of system when the rate of arrival is abrupt

图8 到达速率突变时系统平均队列长度Fig.8 Average queue length of system with abrupt change of arrival rate

图9 当权值变化时个体队列数据吞吐率Fig.9 Throughput of individual queue data when power values change

[1] LIU Lixia, LING Ren, BEI Xiaomeng, GUO Rongwei, et al.coexistence of synchronization and anti-synchronization of a novel hyperchaotic finance system[C]. IEEE Proceeding of the 34thChinese Control conference, Hangzhou, 2015: 8585-8589.

[2] 杨淙钧, 艾中良, 刘忠麟, 等. 基于多级列式索引的海量数据高效查询设计[J]. 软件, 2016, 37(3): 79-83

[3] Luis M L, Sara F, Clara G. Complete synchronization and delayed synchronization in couplings[J]. Nonlinear Dynamics.2015, 79(02): 1615-161624.

[4] 邹积凯. 公安系统应急平台建设及资源应用研究[J]. 软件,2016, 37(4): 122-125

[5] GUO Peilin, WANG Yuzhen. Matrix expression and vaccination control for epidemic dynamics over dynamic networks [J]. Control Theory and Technology, 2016, 14(01):39-48.

[6] 李沛然, 苏卫东, 段振华等. 国家电网运营诊断关键技术研究与实证分析[J]. 软件, 2016, 37(01): 127-131

[7] Li QM. Multiple QoS Constraints Finding Paths Algorithm in TMN. INFORMATION. 2011, 14(3): 731-737.

[8] Li QM, Zhang H. Information Security Risk Assessment Technology of Cyberspace: a Review. INFORMATION.2012, 15(11): 677-683.

[9] Li QM, LiJ . Rough Outlier Detection Based Security Risk Analysis Methodology. CHINA COMMUNICATIONS. 2012,9(7): 14-21.

[10] Li, QM; Hou, J; Qi, Y; Zhang, H. The Rule Engineer Model on the high-speed processing of Disaster Warning Information.DISASTER ADVANCES. 2012, 5(4): 1196-1201.

[11] Qianmu Li *, Tao Li, Bin Xia. FIRST: Face Identity Recognition in SmarT Bank. International Journal of Semantic Computing. 2016, 31(2): 1-24.

[12] Jing Zhang, Qianmu Li, & Wei Zhou. HDCache: A Distributed Cache System for Real-Time Cloud Services. Journal of Grid Computing, 2016, 14(3): 407–428.

A Fusion Scheduling Algorithm for Big Data Communication in Multi-source Heterogeneous Sensing Communication

WANG Yan-song1, QI Yong2, LI Qian-mu2

(1. ZhongXing Telecommunication Equipment Corporation, Nanjing R & D Center, Nanjing, 320100;2. School of Computer science and Engineering, Nanjing University of Science and Technology, Nanjing 210094)

This paper studies the scheduling problem of optimal big data fusion for a traffic sensor node system with multi-source heterogeneous communication cluster, which serves various data processing and transmission under the condition of energy constraint. Traditional methods require a large amount of statistical information about system dynamics, and their efficiency is low. Using the Lyapunov optimization technique for updating frames, a new data fusion scheduling algorithm for on-line multi-source sensing communication is designed to overcome the above difficulties. Simulation results show that the proposed algorithm is stable and robust, and lays the foundation for subsequent transmission of large-scale data using traffic sensor networks.

: Multi-source heterogeneous; Traffic big data; Data fusion

TP391

A

10.3969/j.issn.1003-6970.2017.10.006

本文著录格式：王延松，戚湧，李千目. 多源异构传感通信大数据的融合调度算法[J]. 软件，2017，38（10）：29-38

国家重点研发计划政府间国际科技创新合作重点专项(S2016G9070)；江苏省重大研发计划社会发展项目(BE2017739)；赛尔下一代互联网创新项目(NGII20160122)；中兴通讯产学研合作论坛合作项目(2016ZTE04-11)

王延松(1970-)，总工，研究方向：通信网络；戚湧(1970-)，教授，研究方向：大数据处理；李千目(1979-)，教授，研究方向：数据挖掘。