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

Scheduling Algorithm for Lightweight Authentication of Massive Terminals

作　　者：王传君 缪巍巍 曽锃 张明轩 张震 WANG Chuanjun;MIAO Weiwei;ZENG Zeng;ZHANG Mingxuan;ZHANG Zhen(Information and Telecommunication Branch,State Grid Jiangsu Electric Power Co.,Ltd.,Nanjing 210024,China)

机构地区：[1]国网江苏省电力公司信息通信分公司,南京210024

出　　处：《重庆理工大学学报（自然科学）》2021年第11期142-149,共8页Journal of Chongqing University of Technology：Natural Science

基　　金：国网江苏省电力有限公司科技项目(J2020066)。

摘　　要：随着物联网的不断发展,大量边缘设备的可信认证需要占用物联管理平台越来越多的计算与通信资源,传统方法难以在有限时间与资源约束下进行实时响应。将该问题建模为并发认证调度问题(CASP),并证明了它是NP完全的。首先提出了一个贪心算法(SJF),并证明了在某些场景下SJF具有近似比。随后将其扩展并提出了一个启发式算法(MBF)来解决一般场景下的CASP问题。实验结果表明:提出的算法能够取得比较好的效果,且在小规模时算法性能接近于最优算法。With the continuous development of the IoT,the trusted authentication of a large number of edge devices needs to occupy more and more computing and communication resources of the IoT Management Platform.Traditional methods are difficult to respond in real time under limited time and resource constraints.This paper models the problem as a concurrent authentication scheduling problem(CASP)and proves that it is NP-complete.This paper first proposed a greedy algorithm(SJF)and proved that it has an approximate ratio in some scenarios.This paper then extended it and proposed a heuristic algorithm(MBF)to solve the CASP problem in general scenarios.The experimental results show that our proposed algorithm achieves better results,and the performance of the algorithm is close to the optimal algorithm at small scales.

关 键 词：海量终端 物联管理平台 NP完全 近似算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]