基于节点复合特性的端-边协同网络生成算法

doi:10.12305/j.issn.1001-506X.2023.08.34

摘要/Abstract

摘要：

针对智慧交通系统数据处理量大、对传输时间要求严苛的难题, 通过将协同系统定义为复杂网络模型, 构建了设备端和边缘节点协作运行的端-边协同系统。提出了基于网络节点复合特性的协作网络生成算法, 实现了多层复杂网络的构建。相比随机几何法, 提出的由节点聚类系数和介数中心性两种特性参数相结合的协作网络生成算法能够更全面地描述节点特性, 反映节点重要性, 改善现有多层复杂网络模型对节点信息描述不全的问题。最后, 使用4种复杂网络模型构建多层网络模型并验证该算法, 以节点间最短路径值作为评价指标, 证明提出的由节点复合特性生成协作网络的算法能够明显降低整个网络中节点间最短路径值, 减少传输时间, 提高传输效率。

关键词: 协同计算, 复杂网络, 网络模型, 边缘计算

Abstract:

For the difficult problem of large data processing volume and strict transmission time requirement of intelligent transportation system, an end-edge collaborative system with collaborative operation of device end and edge nodes is constructed by defining the collaborative system as a complex network model. A collaborative network generation algorithm based on network node composite characteristics is proposed to achieve multi-layer complex network's sconstruction. Compared with the random geometry method, the combination of two characteristic parameters, node clustering coefficient and the betweenness centrality, to generate the collaborative network generation algorithm can describe the node characteristics more comprehensively, reflect the node importance, and improve the problem of incomplete description of node information in the existing multilayer complex network models. Finally, use four complex network models to build multi-layer network model to verify the proposed algorithm. Taking the shortest route value between nodes as evaluation indicators, the proposed node composite characteristics can significantly reduce the shortest road value between nodes in the whole network, which could reduce transmission time and improve the transmission efficiency.

Key words: collaborative computing, complex network, network model, edge computing

中图分类号:

TP393

张冰雪, 李希胜, 尤佳, 宋委任. 基于节点复合特性的端-边协同网络生成算法[J]. 系统工程与电子技术, 2023, 45(8): 2588-2596.

Bingxue ZHANG, Xisheng LI, Jia YOU, Weiren SONG. End-edge collaborative network generation algorithm based on node composite characteristics[J]. Systems Engineering and Electronics, 2023, 45(8): 2588-2596.

图/表 9

图1

图2

图3

图4

表1

图5

图6

图7

图8

参考文献 35

1	SHI W S , CAO J , ZHANG Q , et al. Edge computing: vision and challenges[J]. IEEE Internet of Things Journal, 2016, 3 (5): 637- 646. doi: 10.1109/JIOT.2016.2579198
2	SHI W S , DUSTDAR S . The promise of edge computing[J]. Computer, 2016, 49 (5): 78- 81. doi: 10.1109/MC.2016.145
3	XIE R C , TANG Q Q , WANG Q N , et al. Collaborative vehi-cular edge computing networks: architecture design and research challenges[J]. IEEE Access, 2019, 7, 178942- 178952. doi: 10.1109/ACCESS.2019.2957749
4	SHIN C S , LEE J , LEE H . Infrastructure-less vehicle traffic density estimation via distributed packet probing in V2V network[J]. IEEE Trans.on Vehicular Technology, 2020, 69 (10): 10403- 10418. doi: 10.1109/TVT.2020.3019783
5	AL RIDHAWI I , ALOQAILY M , BOUKERCHE A . Comparing fog solutions for energy efficiency in wireless networks: challenges and opportunities[J]. IEEE Wireless Communications, 2019, 26 (6): 80- 86. doi: 10.1109/MWC.001.1900077
6	DING R , UJANG N , HAMID H B , et al. Application of complex networks theory in urban traffic network researches[J]. Networks and Spatial Economics, 2019, 19 (4): 1281- 1317.
7	JIN X , WANG Z X , YANG H H , et al. Synchronization of multiplex networks with stochastic perturbations via pinning adaptive control[J]. Journal of the Franklin Institute, 2021, 358 (7): 3994- 4012.
8	SONG K J , LI G Q , CHEN X M , et al. Target controllability of two-layer multiplex networks based on network flow theory[J]. IEEE Trans.on Cybernetics, 2021, 51, 2699- 2711.
9	BOCCALETTI S , BIANCONI G , CRIADO R , et al. The structure and dynamics of multilayer networks[J]. Physics Reports, 2014, 544 (1): 1- 122.
10	BOCCALETTI S , LATORA V , MORENO Y , et al. Complex networks: structure and Dynamics[J]. Physics Reports, 2006, 424 (4-5): 175- 308.
11	MARCEAU V , NOEL P A , HEBERT-DUFRESNE L , et al. Modeling the dynamical interaction between epidemics on overlay networks[J]. Physical Review E, 2011, 84 (2): 026105.
12	GUAN W Q, WEN X M, WANG L H, et al. Network slicing management of 5G ultra-dense networks based on complex network theory[C]//Proc. of the IEEE Globecom Workshops, 2017.
13	CANO L , CAPONE A , SANSO B . On the evolution of infrastructure sharing in mobile networks: a survey[J]. ITU Journal on Future and Evolving Technology, 2020, 1 (1): 21.
14	HACKL J , ADEY B T . Modelling multi-layer spatially embedded random networks[J]. Journal of Complex Networks, 2019, 7 (2): 254- 280.
15	KO S W , HAN K , HUANG K . Wireless networks for mobile edge computing: spatial modeling and latency analysis[J]. IEEE Trans.on Wireless Communications, 2018, 17 (8): 5225- 5240.
16	KO D , CHAE S H , CHOI W . MDS coded task offloading in stochastic wireless edge computing networks[J]. IEEE Trans.on Wireless Communications, 2021, 21 (3): 2107- 2121.
17	马海瑛, 肖玉芝, 赵海兴, 等. 三层复杂网络模型构建及特性分析[J]. 复杂系统与复杂性科学, 2020, 17 (4): 16- 29.
	MA H Y , XIAO Y Z , ZHAO H X , et al. Three-layer complex network model construction and characteristic analysis[J]. Complex Systems and Complexity Science, 2020, 17 (4): 16- 29.
18	刘强, 方锦清, 李永. 三层超网络演化模型特性研究[J]. 复杂系统与复杂性科学, 2015, 12 (2): 64- 71.
	LIU Q , FANG J Q , LI Y . Some characteristics of three-layer super network evolution model[J]. Complex Systems and Complexity Science, 2015, 12 (2): 64- 71.
19	郁湧, 王莹港, 罗正国, 等. 基于聚类系数和节点中心性的链路预测算法[J]. 清华大学学报(自然科学版), 2022, 62 (1): 98- 104.
	YU Y , WANG Y G , LUO Z G , et al. Link prediction algorithm based on clustering coefficient and node centrality[J]. Journal of Tsinghua University (Science and Technology), 2022, 62 (1): 98- 104.
20	QI X , MEI G , PICCIALLI F . Resilience evaluation of urban bus-subway traffic networks for potential applications in iot-based smart transportation[J]. IEEE Sensors Journal, 2021, 21 (22): 25061- 25074.
21	边缘计算产业联盟. 边缘计算参考架构2.0[J]. 自动化博览, 2018, (1): 60- 62.
	Edge computing consortium . Edge computing reference architecture 2.0[J]. Automation Panorama, 2018, (1): 60- 62.
22	WATTS D J , STROGATZ S H . Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393 (6684): 440- 442.
23	FREEMAN L C . A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40 (1): 35- 41.
24	ROTH A E , SOTOMAYOR M . Two-sided matching[J]. Handbook of Game Theory with Economic Applications, 1992, 1, 485- 541.
25	JORSWIECK E A. Stable matchings for resource allocation in wireless networks[C]//Proc. of the 17th International Confe-rence on Digital Signal Processing, 2011.
26	HAAS C , HALL M . Two-sided matching for mentor-mentee allocations—algorithms and manipulation strategies[J]. PloS One, 2019, 14 (3)
27	乐琦, 张莉莉. 基于新排序函数的直觉模糊双边匹配决策方法[J]. 控制与决策, 2020, 35 (4): 985- 992.
	YUE Q , ZHANG L L . Decision method for intuitionistic fuzzy two-sided matching based on the new ranking function[J]. Control and Decision, 2020, 35 (4): 985- 992.
28	ZHENG Y J , LI M Y , LIU J K . A two-sided stable matching model of cloud manufacturing tasks and services considering the nonlinear relationship between satisfaction and expectations[J]. Complexity, 2021, 2021, 6735210.
29	ERDOS P L , RENYI A . On the evolution of random graphs[J]. Transactions of the American Mathematical Society, 1984, 286, 257- 286.
30	BOLLOBAS B. Random graphs[M]. BOLLOBAS B, ed. Modern graph theory. New York: Springer, 1998: 215-252.
31	BARABASI A L , ALBERT R . Emergence of scaling in random networks[J]. Science, 1999, 286 (5439): 509- 512.
32	NEWMAN M E J , WATTS D J . Renormalization group analysis of the small-world network model[J]. Physics Letters A, 1999, 263 (4-6): 341- 346.
33	ZHANG Y Q , LI Y M , LI M , et al. Method to enhance traffic capacity for multilayer networks[J]. International Journal of Modern Physics B, 2020, 34 (13): 2050140.
34	WANG Y Y, TANG M M, ZHOU S Y, et al. Performance analysis of heterogeneous mobile edge computing networks with multi-core server[C]//Proc. of the IEEE 20th International Conference on Communication Technology, 2020: 1540-1545.
35	DING R , ZHANG Y L , ZHANG T , et al. Development of a complex network-based integrated multilayer urban growth and optimisation model for an efficient urban traffic network[J]. Complexity, 2021, 2021, 3467485.

复杂网络模型	参数	取值
ER随机模型	节点总数/个	500
ER随机模型	连接概率	0.02
BA无标度模型	初始节点数/个	10
	最终节点数/个	500
	每次增加边数/条	2
WS小世界网络	节点总数/个	500
	每个节点邻居数/个	2
	随机重连概率	0.2
NW小世界网络	节点总数/个	500
	每个节点邻居数/个	2
	随机加边概率	0.01

[1]	陈韩, 张晶, 董俊, 董洁. 子任务调度和时延联合优化的MEC卸载方案[J]. 系统工程与电子技术, 2023, 45(2): 572-579.
[2]	邹虹, 白陈阳, 何鹏, 崔亚平, 王汝言, 吴大鹏. 基于分布式深度学习的边缘服务放置策略[J]. 系统工程与电子技术, 2022, 44(5): 1728-1737.
[3]	余雪勇, 朱烨, 邱礼翔, 朱洪波. 基于无人机辅助边缘计算系统的节能卸载策略[J]. 系统工程与电子技术, 2022, 44(3): 1022-1029.
[4]	金志刚, 段晨旭, 羊秋玲, 苏毅珊. 基于水下云边协同架构的珊瑚礁监测新机制[J]. 系统工程与电子技术, 2022, 44(12): 3829-3836.
[5]	刘浩楠, 宋骊平. 基于核Fisher判别的群结构更新模型及群目标跟踪算法[J]. 系统工程与电子技术, 2022, 44(10): 3012-3019.
[6]	王琮, 沈会良, 夏永祥, 白光晗, 方依宁. 装备保障体系关键节点分析[J]. 系统工程与电子技术, 2022, 44(10): 3134-3142.
[7]	王岩韬, 杨拯. 航班运行风险网络的传播与控制改进[J]. 系统工程与电子技术, 2021, 43(9): 2544-2552.
[8]	毕可心, 吴明功, 张文斌, 温祥西, 杜坎. 基于速度障碍法的飞行冲突网络建模与分析[J]. 系统工程与电子技术, 2021, 43(8): 2163-2173.
[9]	李昂, 聂党民, 温祥西, 王泽坤, 杨诚修. 基于相依网络和SVM的管制系统运行态势评估[J]. 系统工程与电子技术, 2021, 43(5): 1287-1294.
[10]	邢志伟, 刘洪恩, 李彪, 罗谦, 文涛, 陈肇欣. 基于时空关联网络的机场机位运行过程建模[J]. 系统工程与电子技术, 2021, 43(3): 722-730.
[11]	赵辰豪, 吴德伟, 韩昆, 代传金. 无环境信息下多尺度网格细胞群空间表征模型[J]. 系统工程与电子技术, 2021, 43(3): 814-822.
[12]	王哲, 李建华, 刘子杨, 康东. 基于功能依赖的网络信息体系建模及重心分析[J]. 系统工程与电子技术, 2021, 43(10): 2876-2883.
[13]	赵辰豪, 吴德伟, 韩昆, 朱浩男, 代传金. 基于多尺度网格细胞的路径整合模型[J]. 系统工程与电子技术, 2021, 43(10): 2961-2967.
[14]	顾凌枫, 何明, 陈国友, 季敏惠, 刘锦涛. 无人机集群系统弹性研究[J]. 系统工程与电子技术, 2021, 43(1): 156-162.
[15]	黄晓舸, 崔艺凡, 张东宇, 陈前斌. 基于MEC的任务卸载和资源分配联合优化方案[J]. 系统工程与电子技术, 2020, 42(6): 1386-1394.