面向海量终端轻量级认证的调度算法

王传君，缪巍巍，曽 锃，张明轩，张 震

(国网江苏省电力公司信息通信分公司， 南京 210024)

物联网的理念使得设备可以不通过人作为中间媒介而直接进行信息交互，大大增加了信息传播的速度与范围，也方便了人们的生活[1-2]。国网也提出了泛在电力物联网这一概念并对建设做出了全面部署安排。然而，这种不需要人参与的信息交互在带来便利的同时也引入了新的安全问题。在网络安全形势日益严峻的现在，网络攻击的破坏性和威胁性持续增加，电力关键信息基础设施已成为网络打击破坏的首要攻击目标。

出于安全考虑，电力系统在物联设备接入平台之前都会对设备进行认证。业界物联网平台主要采用token认证[3]、TLS证书认证[4]等方式实现边缘设备的认证接入。电力物联网下连的各电力终端涉及生产数据、控制操作等功能，当通过边缘设备实现汇聚接入后，需要强化对边缘设备的安全认证，防止边缘设备被反向控制、系统/APP被恶意篡改等。

现阶段应用与边缘设备的认证技术大部分需要繁杂的加密计算，即使采用轻量级认证系统[5-6]或者简化的加密算法，如AES[7]和SHA-1[8]也需要数千个(或数万个)门电路和数千个时钟周期，因此大部分物联网设备无法应用这些加密算法实现认证。同时大量边缘设备的可信认证[9-10]需要占用物联管理平台的计算与通信资源，就算是轻量级的认证机制[11-12]，也很难在有限时间与资源约束下实时响应。与之前的工作不同，我们关注的更多是如何在海量设备同时进行验证时能够合理调度平台的计算资源使得验证能够在最短的时间内完成，对于设备具体使用哪种认证方式不做考虑，上述参考文献都是提出了一种新的轻量级身份验证机制，是系统与机制层面的工作，我们的主要是理论工作。

在电力物联网场景下，设备的认证会经过3个模块，分别是设备连接模块、设备管理模块和影子设备模块。每个模块由多个节点组成，每个节点的计算能力之间存在着差异。可以预见的是，随着物联网的不断发展，需要进行认证的设备也将越来越多。根据沙利文数据显示，2020年全球有超过500亿的终端与设备联网，中国的联网设备预计从2016年的8.4亿个增长到35亿个。如何快速有效地为海量设备进行实时认证成为了一个重要且具有挑战性的问题。

在本文中，设计面向海量边缘设备实时认证的调度算法。每当有边缘设备请求进行认证时，该框架能够根据物联管理平台上各个模块节点当前的处理资源，灵活地将该认证请求调度到最适合的节点上进行处理，使得该设备的请求能够在最短的时间内完成认证。鉴于该问题是NP完全的，最终设计了2种不同的调度算法。其中贪心算法(SJF)每次都会将认证请求调度到处理能力最快的节点上，经过理论证明，SJF在某些情况下能够达到2近似。启发式算法(MBF)则每次都将认证请求调度到边际效益最大的节点上，通过仿真实验，在设备数量较少时MBF的表现非常接近最优算法。

1 海量设备轻量级认证系统概述

1.1 海量设备轻量级认证系统

设备的认证环境中，大量的边缘设备与物联管理平台连接，并且需要在管理平台上进行轻量级认证[5-6]。认证会经过3个模块，分别是设备连接模块、设备管理模块和影子设备模块。每个模块由多个节点组成，每个节点的计算能力之间存在着差异。为了提高认证效率和专用性，每个节点经过提前配置，能够为特定类别的设备提供认证服务。物联管理平台上每个节点的处理能力都是有限的。为了更灵活地利用节点资源，一般会利用虚拟化技术[13]将节点的资源池化成多个虚拟机，假设模块节点上的虚拟机都具有相同的处理能力。

考虑到无线专用网络[16]的快速发展与设备和物联管理平台之间距离较短，不妨假设设备与物联管理平台之间的传输时延可以忽略不计，于是主要的耗时就是认证阶段。同时，为了认证的连续性，假设在认证过程中，设备无法从当前模块节点切换到另一个模块节点。

1.2 问题描述

为使所有种类的设备在最短时间内能得到认证。需要决策的变量是每个种类的设备需要在物联管理平台上的哪个模块节点上进行认证。于是本文的问题描述如下：

给定需要认证的设备种类集合U与每种设备的数量Si，用来进行认证的物联管理平台中的模块节点集合E与每个模块节点上虚拟机的数量kj。给定模块节点配置rij。本文的目的是决定每种设备应该被分配到哪个模块节点上进行认证，从而使所有设备的认证时间最短(CASP)。

因为设备是在虚拟机上进行认证，所以只需要关注最后完成认证的虚拟机即可知道所有设备完成认证的时间。于是目标变成了：

(1)

需要注意的是，认证需要考虑模块节点的资源约束，且一个虚拟机同时只能对一个设备进行认证：

(2)

(3)

单个设备可以同时使用多个虚拟机进行认证，这会加快认证的速度。假设所有设备都使用相同的认证程序，认证的速度只与处理能力有关，且虚拟机只有在完成当前种类所有设备的认证后才能认证新的种类。令vi表示设备ui的处理速度，表达式为：

(4)

2 问题分析与算法设计

2.1 问题复杂度分析

通过将makespan问题[17]规约到CASP的一个特例来证明CASP是NP完全的。

Makespan问题的定义如下：给定n个作业的集合J={J1，J2，…，Jn}与每个作业所对应的处理时间，m个处理能力相同的机器，问是否存在一组作业与机器的映射，使得可以用最少的时间处理完所有的作业。

通过如下的构造将makespan问题规约到CASP问题的特例。

1) 对于每个作业Ji，将CASP问题中种类ui的认证构造成一个作业；

2) 对于每个作业Ji的处理时间，首先假设每个种类只能使用一个虚拟机进行认证(这是CASP问题的一个特例)，之后将设备种类ui的总认证时长Si/c构造成makespan问题中作业的处理时间；

3) 对于处理能力相同的机器，将模块节点的数量设置为1，并将虚拟机的数量ki设置为1，于是这些处理能力都为c的虚拟机便构造成了makespan问题中处理能力相同的机器；

这样的构造是可以在多项式时间之内完成的，于是，本文将解决NP难的makespan问题规约成了解决CASP问题的一个特例，这也意味着CASP问题是NP完全的。

2.2 算法设计

2.2.1贪心算法

CASP是NP完全的，这意味着无法在多项式时间内找到它的最优解。提出了基于处理时间贪心的设备认证调度算法(SJF)来求解。具体步骤如下：

步骤2决定初始的分配方案。如果模块节点ej有足够的虚拟机，则所有可以在该模块节点上进行认证的种类都能分配到一个虚拟机，只有当虚拟机的数量小于种类数量的时候才需要进行决策。在SJF算法中，每次都会将虚拟机分配给最快完成认证的设备种类，即一个设备种类可以获得一个虚拟机中当且仅当该种类获得该虚拟机后能够比其他的设备种类更快完成认证；

步骤3虚拟机重分配。每当一种设备完成认证后，负责该种类认证的虚拟机就可以再次分配给其他种类的设备进行验证。在虚拟机的再次分配中，SJF会将其分配给完成时间最快的种类；

步骤4当所有设备都完成认证后算法终止。

当模块节点上的虚拟机数量是O(n)时，算法SJF的复杂度是O(n3)。初始化分配时，对于m个模块节点上的O(n)个虚拟机，需要对可以认证的O(n)个设备种类进行比较，这里的复杂度是O(mn2)。当有设备种类完成认证后，需要对空闲的虚拟机进行再分配，此时需要O(n)的对比。而最多需要重新分配O(n)次虚拟机。于是当m

接下来将证明在图1的场景下，SJF算法能够达到2近似。

图1 CASP的特殊场景示意图

在图1中，每种设备都能在2个模块节点上进行认证，而模块节点有且仅有一个虚拟机。这意味着每种设备最多可以获得2c的处理能力。为了方便表述，本文定义ti=Si/c，并定义最优解的完成时间为T*。

不失一般性，假设ti是所有种类里耗时最长的，up是所有种类里最后一个完成的。这里需要对2种情况进行讨论。

综上，在某些特殊场景下，算法SJF能够取得2+ε的近似比，其中ε<1。

2.2.2启发式算法

针对一般场景下的CASP问题，设计了一个边际最优调度的启发式算法(MBF)来解决它。

2) 决定初始的分配方案。本文使用细粒度的分配方式，最小的分配单位是一个虚拟机。在进行决策时，首先定义认证效益(MB)这一概念，其表达式为Si/vi-Si/(vi+c)。在初始阶段，所有的设备种类处理速度都为0，此时每次分配都将一个虚拟机分配给处理时长最短的且还未分配到虚拟机的种类。这一阶段持续到虚拟机分配结束或者所有能够分配的种类都至少分配到一个虚拟机为止。对于初始阶段剩余的虚拟机，算法再按照认证效益从大到小的顺序进行分配，直到所有的虚拟机分配完成；

3) 虚拟机重分配。每当一种设备完成认证后，分配给它的虚拟机就空闲了，此时算法会对这些虚拟机进行再分配，分配的策略依然是按照认证效益从大到小的顺序；

4) 当所有的设备得到认证后算法终止。

看起来似乎MBF能够充分地利用每一个虚拟机，因为虚拟机每次都会被分配给边际效益最大的设备种类。然而，这样的分析并没有考虑到模块节点配置的影响。考虑如下的一个场景，模块节点e1可以为种类u1与u2提供认证服务，且e1上只有一个虚拟机，初始时，由于e1上的虚拟机是第一个进行分配的，按照处理时长的顺序，虚拟机被分配给了u2。然而种类u1的设备只能在模块节点e1上进行认证，而种类u2的设备则可以在多个模块节点上进行认证。这样的分配很可能会错过一些更好的方案。为了避免这种情况，就需要在初始分配时检查所有可能的分配情况，即所有模块节点的全排列，共有m!种情况。很显然，要想检查所有的排列是不现实的。因此，MBF算法会检查R种排列，最后在这R种排列中选择最小的完成时间作为算法的输出。每种排列的复杂度都与SJF的复杂度相同。当m

3 实验验证与分析

3.1 实验设置

1) 环境设置：将物联设备分为输电设备、变电设备、配电设备与用电设备等种类，其中每种电力设备设置为4 000～8 000个，每个设备的认证时间设置为400～600 μs。在电力物联网场景下，设备的认证会经过3个模块，分别是设备连接模块、设备管理模块以及影子设备模块。每个模块由多个节点组成，每个节点的计算能力之间存在着差异。为了方便起见，在设备的认证过程中只考虑设备管理模块，本文的方法也可以扩展到设备连接模块与影子设备模块的处理分析。每种设备能在1～10个模块节点上进行认证。

2) 对比算法：除了本文中提出的SJF算法和MBF算法之外，还将介绍随机算法(RA)作为参照。RA算法分配的粒度也是单个虚拟机，每次分配虚拟机时，都会随机选择一个种类进行分配，直到虚拟机全部分配或者所有种类都完成认证。

在正式进入验证环节之前，首先将MBF算法与暴力搜索算法(OPT)进行对比。鉴于运行暴力搜索算法的复杂度太高，只进行了小规模的实验对比(10种设备，每种设备最多在3个模块节点上进行认证，每个模块节点只有一个虚拟机)，实验结果如图2所示。可以看出，小规模时，MBF算法的性能非常接近暴力搜索算法(最优解)。

图2 MBF算法与暴力搜索算法实验结果直方图

3.2 实验结果

为了验证虚拟机的数量对完成时间的影响，将设备的种类设置为10个，将认证模块节点的数量设置为10，并提前配置好模块节点可以认证的设备种类，然后观察虚拟机数量对实验的影响，结果如图3所示。可以看出，完成时间随着虚拟机数量的增加而不断递减，这是很显然的，虚拟机越多，模块节点的处理能力就越大，总完成时间就减少了。虚拟机较少时，SJF的性能也更接近MBF算法。

图3 不同虚拟机数量的完成时间直方图

为了探究完成时间与种类数量的关系，将模块种类的数量设置为10，将每个模块节点上的虚拟机设置为2～5个，设备种类的变化数量来观察影响，结果如图4所示。可以看出，完成时间随着种类的增加而不断递增，这是很合理的，随着设备种类的变多，需要进行验证的设备也变多了，总认证时间也相应变多了。同时，在设备种类数量较少的时候各算法之间的性能差别也较小，这是因为设备种类较少时，模块节点的处理能力是完全足够的，所以设备认证时几乎没有等待时间。

图4 不同设备种类的完成时间直方图

为了探究完成时间与模块节点数量的关系，将设备的种类设置为10，将每个模块节点上的虚拟机设置为2～5个，然后变化设备种类的数量来观察影响，结果如图5所示。可以看出，完成时间随着模块节点数量的增加而不断减少，这是合理的，随着模块节点的变多，可以进行认证的虚拟机也变多了，认证的时间也相应变少了。同时，在模块节点数量较少的时候各算法之间的性能表现差不多，这是因为模块节点数量较少时，可供选择的调度方案并不多，最佳调度与最差调度之间的差别也不大。

图5 不同模块节点数量的完成时间直方图

系统环境的配置(每个模块节点可以认证的设备类型)也会对结果产生较大的影响。为了研究系统配置对认证完成时间的影响，将设备种类设置为10，模块节点数量设置为10，每个节点上的虚拟机设置为5。然后变化的是每类设备提供认证服务的模块节点数量，从而观察认证时间的变化，实验结果如图6所示。

图6 不同提供服务的模块节点数量的完成时间直方图

由图6可以看出，随着每个种类的设备可以在更多的模块节点上进行认证，认证的完成时间也随之递减。这是显然的，当为每类设备提供认证服务模块节点数量变多后，每种设备能够接触到的虚拟机数量也变多了，这使得虚拟机的分配更加地灵活，而且能够使得资源得到充分利用。

图7探究了完成时间与设备数量的关系。实验中将设备的种类固定为4种，并改变每种设备的数量来探究对结果的影响。很显然，当设备数量增加时，需要更多的时间去进行认证。

图7 不同类别设备数量的完成时间直方图

观察图5可以看出，当虚拟机的数量从5增加到6时，算法SJF和MBF的性能没有发生变化。这是因为模块节点已经将能够分配的虚拟机都分配了，多出的虚拟机也因为可以服务的设备种类限制而无法进行分配。观察图6可以看出，当模块节点的数量为2时，3个算法的完成时间是相同的，这是因为在模块节点的配置时，某些种类的设备只能在某个特定的模块节点上进行认证，所有这些设备必须进行排队才可以进行认证。

本文中还对不同算法的运行时间进行了实验。结果如图8和图9所示。可以看出，算法SJF和RA的运行时间远低于MBF算法。这是因为MBF算法需要在初始分配时，对模块节点的不同排列进行检查，而这一操作花费了大量的时间。在图8中，当设备种类的数量增加时，3个算法的运行时间都增加了，且变化的幅度都差不多，因为随着设备种类的增加，每个模块节点都需要对更多设备的认证请求做出决策，从而导致时间变长。在图9中，当模块节点的数量增加时，算法MBF的运行时间很明显比RA和SJF增长的快。如之前所说，在初始分配时，MBF需要检查模块节点的一些排列，而排列的增长是与模块节点的数量指数相关的。所以MBF的运行时间也增长得很快。

图8 不同设备种类的完成时间曲线

图9 不同模块节点数量的完成时间曲线

当所有的模块节点都只有一个虚拟机的时候，算法SJF就是最优算法。在这种情况下，CASP变成了一个简单的调度问题，此时最优策略就是最短任务优先，即SJF算法。

4 结论

研究了海量设备的认证调度问题(CASP)，证明了CASP是NP完全的。提出了2近似的SJF和MBF算法，实验结果表明：SJF在小规模时性能接近MBF算法，在某些特殊情况下具有最优解。