基于级联失效的标准物联网抗毁性研究

黄童祎 李长连 张小飞

1(上海交通大学电子信息与电气工程学院 上海 200240) 2(中讯邮电咨询设计院有限公司 北京 100048) 3(国网电力科学研究院有限公司 南京 210006)

随着智能硬件的发展，特别是近年来大数据和边缘计算的兴起，物联网逐渐成为下一代产业变革和科技浪潮的核心驱动力，人类社会正逐步迈向全面信息化.智能物联网技术被广泛应用于车联网、智慧医疗和智能电网等领域，大大提高了生产效率[1].然而，硬件设备和网络协议的异构性给“万物互联”的物联网愿景带来了巨大的挑战.美国国家标准与技术研究院(National Institute of Standards and Technology, NIST)为实现物联网设备的互操作性牵头提出了IEEE P21451系列国际标准[2]，旨在建立基于IEEE P21451系列标准的统一物联网网络.IEEE P21451标准物联网定义2类终端节点[3]：NCAP(network capable application processors)和TIM(transducer interface module).TIM在逻辑上负责实现传感器服务接口，包括传感元件、驱动器的接口、信号处理接口、数字域模拟域之间转化的接口等.NCAP是工作于用户网络和TIM之间的智能网关，对外提供TIM发现服务、传感器访问服务、事件通知服务等.

受限于硬件资源，物联网终端容易受到恶意攻击以及设备故障的影响出现节点宕机而进一步引发网络拓扑的撕裂，甚至可能会引起整个网络的雪崩，严重影响物联网系统的正常运行.网络抗毁性是网络遭遇节点失效时继续提供正常服务的能力，现有的研究大多从网络的静态属性去研究网络抗毁性[4-5].然而实际物联网具备显著的动态特性，个别节点的失效会引起网络拓扑结构的变化，从而进一步引发网络中负载的重新分配，可能导致其余节点因负载超过承载上限而失效，持续多轮的负载重分配最终可能导致物联网网络大规模的瘫痪.这种因个别节点失效引发的连锁节点失效现象被称为级联失效，是影响物联网抗毁性的重要因素之一[6].

针对复杂网络的级联失效现象，国内外学者展开了众多研究，主要从节点的初始负载和容量以及节点负载重分配策略等方面进行研究.Yin等人[7]建立针对无线传感网无标度拓扑的级联失效模型，包括基于节点度的初始负载模型以及基于节点度和能量的负载重分配策略，研究负载及拓扑参数对级联失效的影响.韩丽等人[8]研究了加权无标度网络的级联失效现象，建立结合节点度、介数以及节点权重等因素的级联失效模型，并在与其余级联失效模型的对比实验中验证了所提模型的有效性.Zhou等人[9]利用介数定义节点的动态负载，同时考虑了节点间依赖性对网络抗毁性的影响，提出一种混合级联失效模型.Liu等人[10]基于节点介数和度的幂函数定义初始负载，根据周围节点的负载和能量进行负载再分配，并通过仿真实验表明无标度网络的级联失效抗毁性与网络平均度成反比.尽管已有一些针对物联网的级联失效模型被提出，但是这些研究很少考虑终端节点之间的异质性，通常假设网络内所有节点均为对等节点，但是在实际智能物联网场景中，同时存在着大量的终端感知节点以及数据汇集节点，使得现有的级联失效研究对于普遍的智能物联网场景并不完全适用，特别是对IEEE P21451标准物联网的级联失效研究仍处于空白.

基于以上分析，本文针对IEEE P21451标准物联网提出符合标准约束的分簇网络演化模型，在此基础上建立级联失效模型，综合考虑网络局部和全局的信息构建初始负载，为构建高抗毁性能的标准物联网网络提供理论指导.

1 标准物联网分簇网络模型

网络拓扑结构反映了网络中节点间的连接和结构关系，而网络拓扑结构与网络的抗毁性能有着密切的关系，因而确立符合标准物联网场景特性的网络拓扑模型是研究其网络抗毁性的首要步骤.已有的研究[11]表明，无标度网络适合作为物联网，特别是无线传感器网络的网络拓扑模型.但是现有的无标度网络模型主要研究的是对等节点，即网络中的所有节点都具有相同的特性，而在IEEE P21451标准物联网网络中，存在NCAP和TIM这2类网络节点，而NCAP与TIM节点形成了类似簇头节点和簇内节点的通信关系，整体网络天然呈现出分簇拓扑的特征.另一方面，经典无标度网络模型中所有的节点都可以建立连接，并没有考虑到部分物联网终端如传感器节点的通信半径有限，不能准确反映出标准物联网的网络特性.因此本文首先构建一种符合标准物联网特性且具有无标度特性的分簇网络演化模型，并在这一网络模型的基础上进行级联失效现象的研究.

1.1 网络模型约束

在本文所提的分簇标准物联网网络模型中，整体网络部署于矩形区域.网络包含2类物联网节点，分别为NCAP和TIM，其中TIM作为簇内节点，负责感知周围环境，采集环境数据并汇聚至所属的NCAP节点，每个TIM节点仅能隶属于1个NCAP节点.NCAP作为簇头节点，具备数据中继功能，利用簇间多跳机制转发各类数据，为防止NCAP拥有过多连边，从而影响网络性能，限制任何一个NCAP拥有的连接数不能超过饱和度约束kmax.同一类型的标准物联网节点(NCAP或TIM)具有相同的基本特性，例如通信半径.所有的物联网节点随机分布在边长为L的正方形监测区域内，并且节点的位置都是固定的.

1.2 分簇无标度网络拓扑演化模型

分簇标准物联网网络拓扑具体演化步骤为：

1)初始化.初始网络具有m0个NCAP节点，这些节点之间具有e0条连边.为了避免出现孤立节点，每个NCAP节点至少与任意一个NCAP节点建立连接，故e0至少为m0-1.

2)局域世界优先连接.每个时间步长增加1个标准物联网节点，该节点是NCAP节点的概率为p，作为TIM节点的概率为1-p.若新加入节点是NCAP节点，那么在其局域世界Ωn中选取m个NCAP节点建立连接.局域世界Ωn是由在新加入NCAP节点通信半径内已存在的NCAP节点中随机抽取的Mn个节点构成.若新加入节点为TIM节点，则在局域世界Ωt中选取一个NCAP节点建立链路.同样，局域世界Ωt是TIM节点通信半径范围内随机选取Mt个已存在且满足饱和度约束的NCAP节点构成.新加入节点在与局域世界内已存在NCAP节点建立链路时，依照优先连接概率Π(i,t)进行选择，优先连接概率Π(i,t)取决于被选择NCAP节点的度di(t)，具体表达式如下：

(1)

2 标准物联网级联失效模型

2.1 初始负载模型

标准物联网网络由NCAP节点和TIM节点构成.TIM节点负责标准化采集区域内的环境信息，并将数据传输至NCAP节点.NCAP节点除了汇聚所辖TIM的感知数据之外，还需要承担其余NCAP节点的数据中继任务，作为功能更为强大的终端节点，NCAP还会承担诸如数据处理、边缘计算以及网络管理的负载.2类节点所承担的负载并不完全一致.现有的研究中，绝大多数认为节点失效之后其自身所有负载均会重分配给其余存活节点.然而在实际标准物联网场景中，TIM节点失效之后，它所负责的感知环境并传送监控数据的负载无法交由其余节点来负责.另一方面，NCAP节点失效之后，由于TIM节点与其余NCAP节点未建立连接，失效NCAP节点所负责的汇聚TIM节点感知数据的负载无法转移至其余NCAP节点，而数据中继等负载能重新分配给邻居NCAP节点.因此，在Fu等人[12]研究工作的启发下，本文将节点负载划分为2类负载：传感负载以及可转移负载.其中，TIM节点只具有传感负载，NCAP节点同时具有这2类负载.

传感负载的根源来自于TIM节点感知周围环境，NCAP节点连接的TIM节点越多，所承担的传感负载也就越高，本文以节点连接的TIM节点数来确定传感负载.可转移负载的定义则综合考虑节点局部以及全局的信息，目前的研究大多只考虑1个维度的信息.从局部来看，节点度数体现了节点与其他节点的链路数，连边越多意味着在局部的影响力更大.从全局来看，节点介数体现了经过节点的最短路径的数量，经过节点的最短路径越多，说明在全局的影响力更重要.因此，本文综合利用节点度和介数来确定可转移负载.综上所述，网络中任一NCAP节点的负载定义如下：

(2)

(3)

节点的容量是节点所能承载的最大负载，一旦超过容量，就认为节点失效.根据已有的研究[13]，节点的容量通常遵循按需分配的原则，一般认为节点的容量与初始负载成正比.因此，本模型节点容量定义如下：

Ci=(1+ac)Li,

(4)

其中，ac为网络容限系数，表征网络承受负载的能力，ac值越大，网络处理额外负载、抵御级联失效的能力越强，同时网络布设的成本也越高.

2.2 范围可调的负载重分配策略

如2.1节所述，本模型将节点负载划分为传感负载和可转移负载.其中节点失效时传感负载也随之消失，无法重分配至其余节点，而可转移负载可以进一步重分配至其余节点，所以本模型的负载重分配过程仅限于可转移负载.当NCAP节点失效后，其可转移负载将分配给与之相邻的节点(例如中继流量)，而邻居节点可能将转移得到的负载进一步在其周围正常运行节点间转移.另一方面，由于受节点通信范围、节点间连接关系等因素影响，标准物联网中的节点失效后难以将负载重新分配给相距较远的存活节点，因此本文采取一种介于全局和最近邻分配之间的策略.具体策略如下：

1)网络中任一节点的初始负载均小于其容量，即初始网络正常运行.

2)当发生节点失效时，其传感负载消失，而可转移负载将会择优分配到与其直接相连的邻居NCAP节点.也就是说，TIM节点失效时不会导致负载重分配过程，也就不会导致级联失效的出现.负载重分配过程可能会进一步导致新的NCAP节点失效，进而触发新一轮的负载重分配过程.负载重分配过程直到没有新的节点失效或者全部节点失效为止.

4)考虑到NCAP节点的初始可转移负载一定程度上表征了承担负载和处理额外负载的能力，相对距离更为遥远的节点在负载重分配过程中更难被分配负载，因此本模型的负载增量比例系数定义如下：

(5)

图1展示了负载重分配的过程.当NCAP节点i发生失效时，其原有的可转移负载LT将按照负载增量比例沿实线箭头分配给与之联通的存活NCAP节点j,k,l和m等.和节点i拓扑距离更近的k,l和m节点分配得到更多的负载.其中NCAP节点k原负载加上新增的可转移负载之后超过节点容量，节点k的可转移负载继续沿虚线箭头重分配至可联通的正常工作的NCAP节点j，而在节点i失效后，节点l和节点m与节点k不再联通，所以在节点k的可转移负载重分配过程中不会被分配负载.不断重复该过程直至不再有NCAP节点因负载超过容量而失效.

图1 负载重分配示意图

2.3 抗毁性测度指标

根据前述的初始负载-容量模型以及负载重分配策略，只有NCAP节点的可转移负载才会在节点失效之后转移至其余节点，进而触发级联失效过程.NCAP节点失效之后，其直接相连的TIM节点将成为网络中的孤立点，相应的感知数据也将无法被采样读取，因此，本文采用基于网络最大联通子图规模的方式来量化标准物联网面临级联失效的抗毁性，即联通节点比例.NCAP节点i失效后的联通节点比例CSi可以表示为CSi=Si/N，其中Si为NCAP节点i失效后到级联失效结束时剩余节点构成的最大联通子图规模，N为原始网络节点总数(初始网络是全联通的).为了量化标准物联网在面临级联失效时的整体抗毁性，本文给出联通节点比例的归一化指标，通过逐一移除网络中的NCAP节点，计算其失效结束后的联通节点比例，将所有NCAP节点对应的联通节点比例求和作归一化处理，得到网络抗毁性归一化指标网络节点联通规模CS：

其中，Vn为网络中NCAP节点的集合，Nn为网络中NCAP节点的数目.显然，CS值越大，说明网络在级联失效过程之后平均节点存活的比例越高，网络抵御级联失效的能力越强，当CS值接近1时，网络中正常工作的节点规模在任一NCAP节点的失效后几乎都不会降低.

3 实验结果与分析

3.1 实验环境

为了验证本节所提的级联失效模型使标准物联网达到更强的网络抗毁性，以及探究模型中关键参数对网络抗毁性的影响，本节在MATLAB平台上进行模拟实验来仿真分析标准物联网网络面临级联失效的网络抗毁性.实验主要考察网络整体在面临级联失效时的抗毁性能，首先按照表1给定的网络参数演化生成网络拓扑.

表1 网络拓扑演化参数

实验的基本思路是基于表1的参数以及第1节的分簇网络模型随机演化生成30个不同的网络拓扑;根据第2节给出的级联失效模型进行仿真模拟，计算级联失效抗毁性归一化指标CS并取30个网络拓扑的平均值作为网络整体抗毁性的结果.

3.2 级联失效模型对比分析

为了验证初始负载模型在面临级联失效时具备更好的网络抗毁性，在初始负载参数α=1.6,β=18,G=0.4，负载重分配参数θ=4,γ=2的设定条件下,将本文模型与文献[12]的只考虑节点度的初始负载模型进行对比，对比的结果如图2所示,横坐标为容限参数ac，纵坐标为网络抗毁性指标CS.

图2 不同模型网络抗毁性CS与ac关系图

由图2可以看出，容限参数(ac<0.28)相同的情况下，本文所提级联失效模型的归一化网络节点联通比例CS高于文献[12]的模型.相较于只考虑节点度的初始负载定义方式，本文方法综合考虑了节点度和介数的影响，网络中介数越大的节点经过其最短路径也就越多，途径其中继流量一般也会越大，而像网络管理、边缘计算等额外负载任务出于效率的考量也会优先考虑这类节点，导致这类节点容易陷入过载，因此，给这类NCAP节点额外分配更大的容量能够有效提高网络抗毁性.

容限系数ac越大意味着在网络容量上付出的成本更多，而物联网节点中充斥着大量计算、通信以及能源受限的终端设备，这些设备通常难以提供宏观意义上比较充足的容量，而本文方法在ac较低的情况下，即在成本投入较低的网络中，可以保持更好的抵御级联失效的能力，因此本文模型在实际物联网应用中更具优势，对于资源相对受限的物联网网络的容量设计有更重要的启发和指导意义.

3.3 模型参数对网络抗毁性的影响

本文设计2组实验分别考察负载重分配范围调节参数θ和负载比例参数G对网络面临级联失效时抗毁性能的影响.

由图3不难发现，负载重分配范围调节参数θ越大，在容限系数相同的情况下级联失效过程后的联通节点比例越高，其中θ取值为∞的情况也就是采取最近邻负载重分配策略的局部方案网络抗毁性能最低.这一实验说明负载重分配范围调节参数θ取值的降低能够有效提高网络整体抗毁性能.因此，为了增强标准物联网面临级联失效时的抗毁性能，在负载重分配时应尽量选择在更大的范围内转移负载，特别是网络管理等复杂任务产生的负载.

图3 网络抗毁性CS与θ关系图

第2组实验研究负载比例参数G对网络级联失效抗毁性的影响.由图4不难发现，负载比例参数G与标准物联网网络整体抗毁性呈现正相关的关系.G值的提高意味着NCAP节点的主要任务更加集中于汇聚TIM节点的感知数据，也会减少负责诸如状态监管、数据转发等额外可被转移的负载任务，因而在NCAP节点失效时，参与再分配过程的负载在容量中的占比变低，标准物联网网络抵御级联失效的能力也随之增强.因此，为了保障标准物联网在面临失效时的鲁棒性，应合理安排节点整体的任务，在保障基础的感知任务和完成额外的管理、数据处理任务之间寻找平衡，同时也要减少多跳数据转发带来的额外流量.

图4 网络抗毁性CS与G关系图

4 结束语

本文从网络拓扑结构角度来研究标准物联网的抗毁性，设计了具备无标度特性的分簇标准物联网网络演化模型，在网络演化模型基础上构建参数可调的级联失效模型，该模型将负载划分为感知负载和可转移负载，综合考虑节点全局信息介数和局部信息度来定义初始可转移负载.通过实验仿真验证了所提初始负载模型在面临级联失效时具备更好的网络抗毁性，特别是在容限参数较低，也就是节点容量成本投入较小的情况下.此外，仿真实验验证了：1)负载重分配范围调节参数θ与标准物联网整体网络抗毁性负相关；2)负载比例参数G与标准物联网网络整体抗毁性呈现正相关的关系.