计算机科学 ›› 2020, Vol. 47 ›› Issue (9): 232-237.doi: 10.11896/jsjkx.190800023
韩晓冬1,2, 高飞2, 张立炜1
HAN Xiao-dong1,2, GAO Fei2, ZHANG Li-wei1
摘要： 如今,人类社会存储和交换的信息总量呈几何级数飞速增长,数据传输的吞吐量和实时性亟待提升。然而,现有的网络编码研究专注于提升吞吐量,忽略了实时性对大数据网络多路径传输性能的重大影响。为此,文中针对线性网络编码的最快到达问题,提出一种矩阵优化相乘的关键路径算法,以提高算法的实时性。具体地,使用抽象代数分析关键路径算法,构造了关键路径的交换环代数,并证明了最优子结构性质。仿真结果显示,随着网络节点个数n的增加,基于Strassen思想优化的关键路径算法能够极大地降低计算复杂度,成功将时间复杂度降至O(n2.81lgn),缩短了传播时延,提高了数据传输的实时性。当n>6时,相比基于重复平方关键路径算法,基于Strassen关键路径算法的时间开销的增长速率明显更低;特别地,当n=12时,基于Strassen关键路径算法的计算量约是基于重复平方关键路径算法的2/3,而其所需的时间开销约为后者的1/2。
中图分类号:
| [1] AKPAKWU G A,SILVA B J,HANCKE G P,et al.A Survey on 5G Networks for the Internet of Things:Communication Technologies and Challenges [J].IEEE Access,2018,6:3619-3647. [2] FANG D F,QIAN Y,HU Q Y.Security for 5G Mobile Wireless Networks [J].IEEE Access,2018,6:4850-4874. [3] CUI J X,DONG G L,LI H T,et al.Prospect of Application of Physical Layer Network Coding in Deep Space Communication [C]//2016 IEEE International Conference of Online Analysis and Computing Science (ICOACS).2016:131-134. [4] JARZYNA M,ZWOLINSKI W,JACHURA M,et al.Optimi-zing deep-space optical communication under power constraints[C]//Free-Space Laser Communication and Atmospheric Propagation XXX. International Society for Optics and Photonics,2018. [5] VAN J,SMETTERS D K,THORNTON J D,et al.Networking Named Content [C]//CoNEXT’09 Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies.New York:ACM,2009:1-12. [6] CAO J X,PEI D,ZHANG X P,et al.Fetching Popular Data from the Nearest Replica in NDN [C]//2016 25th International Conference on Computer Communication and Networks (ICCCN).2016:1-9. [7] ZHAO Z F,TAN X B,SU J X.Adaptive traffic scheduling via network coding in NDN [C]//2016 35th Chinese Control Conference (CCC).2016:7200-7205. [8] AUBRY E,SILVERSTON T,CHRISMENT I.Green growth in NDN:Deployment of content stores [C]//2016 IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN).2016:1-6. [9] ALSHWEDE R,CAI N,LI S Y R,et al.Network information flow [J].IEEE Transactionson Information Theory,2000,46(4):1204-1216. [10] HO T,MÉDARD M,KOETTER R,et al.A Random LinearNetwork Coding Approach to Multicast [J].IEEE Transactions on Information Theory,2006,52(10):4413-4430. [11] HU G,XU K,XU Y.Deadline-Aware Opportunistic NetworkCoding for Multi-Relay-Aided Single-Source Single-Destination. Network [J].IEEE Communications Letters,2017,21(10):2282-2285. [12] ZHU J.Exploiting Opportunistic Network Coding for Improving Wireless Reliability Against Co-Channel Interference [J] . IEEE Transactions on Industrial Informatics,2016,12(5):1692-1701. [13] ZOHDY M,ELBATT T,NAFIE M.Maximum Throughput Opportunistic Network Coding in Two-Way Relay Networks [C]//IEEE International Conference on Communication.2015:913-918. [14] AMIRI M M,GUNDUZ D.Fundamental Limits of Coded Caching:Improved Delivery Rate-Cache Capacity Tradeoff [J].IEEE Transactions on Communications,2017,65(2):806-815. [15] JOHARI S,OJHA A.Quickest path problems in stochastic-flow networks with time constraint:A fast and reliable solution [C]//2013 3rd IEEE International Advance Computing Conference (IACC).2013:322-325. [16] SEGARRA S,MARQUES A G,RIBEIRO A.Optimal Graph-Filter Design and Applications to Distributed Linear Network Operators [J].IEEE Transactions on Signal Processing,2017,65(15):4117-4131. [17] ETZION T,STORME L.Galois geometries and coding theory [J].Designs,Codes and Cryptography,2016,78(1):311-350. [18] CORMEN T H,LEISERSON C E,et al.Introduction to Algorithm [M].MIT Press,2005. [19] HAN X D,GAO F,WANG A H.Network Coding Transmission Performance Under the NDN Protocol [J].Transactions of Beijing Institute of Technology,2017,37(5):506-510. [20] VASSILEVSKA V.Efficient Algorithms for Path Problems[D].Pittsburgh:Carnegie Mellon University,2008. [21] AHO A V,HOPCROFT J E,ULLMAN J D.The Design and Analysis of Computer Algorithms [M].Addision-Wesley Publishing Company,1974. |
| [1] | 胡蓉, 阳王东, 王昊天, 罗辉章, 李肯立. 基于GPU加速的并行WMD算法 Parallel WMD Algorithm Based on GPU Acceleration 计算机科学, 2021, 48(12): 24-28. https://doi.org/10.11896/jsjkx.210600213 |
| [2] | 杨飞,马昱春,侯金,徐宁. 基于MPSoC并行调度的矩阵乘法加速算法研究 Research on Acceleration of Matrix Multiplication Based on Parallel Scheduling on MPSoC 计算机科学, 2017, 44(8): 36-41. https://doi.org/10.11896/j.issn.1002-137X.2017.08.007 |
| [3] | 韩耀军. 基于带标记的并发可达标识图的关键路径的求解方法 Method for Finding Critical Paths Based on Concurrent Reachable Marking Graph with Tags 计算机科学, 2016, 43(11): 121-125. https://doi.org/10.11896/j.issn.1002-137X.2016.11.023 |
| [4] | 郭雅琼,宋建新. 云中多媒体应用中基于混合DAG的最优任务调度研究 Optimal Task-level Scheduling Based on Multimedia Applications in Cloud 计算机科学, 2015, 42(Z11): 413-416. |
| [5] | 尹孟嘉,许先斌,熊曾刚,张 涛. GPU矩阵乘法的性能定量分析模型 Quantitative Performance Analysis Model of Matrix Multiplication Based on GPU 计算机科学, 2015, 42(12): 13-17. |
| [6] | 邢璐,梁华国,严鲁明,张丽娜,余天送. 基于逻辑门类型的老化路径约减算法 Aging Path Reduction Algorithm for Type of Logic Gates 计算机科学, 2014, 41(5): 24-26. https://doi.org/10.11896/j.issn.1002-137X.2014.05.005 |
| [7] | 谢志强,周含笑,桂忠艳,郑付萍. 基于拟关键路径的二车间综合调度算法 Integrated Scheduling Algorithm of Two Workshops Based on ACPM 计算机科学, 2013, 40(4): 193-198. |
| [8] | 叶双，叶剑虹，刘传才. 基于Petri网的关键路径求解算法 Algorithm for Finding the Critical Paths Based on Petri Net 计算机科学, 2012, 39(6): 201-203. |
| [9] | 李 磊，韩文报. FPGA上SHA-1算法的流水线结构实现 Implementation of Pipeline Structure on FPGA for SHA-1 计算机科学, 2011, 38(7): 58-60. |
| [10] | 曾斌,安虹,王莉. 基于剖析信息和关键路径长度的软件扇出树生成算法 Profile Information and Critical Path Length Based Software Fanout Tree Generation Algorithm 计算机科学, 2010, 37(3): 248-252. |
| [11] | 谢志强,张磊,杨静. 基于调度长路径的复杂产品综合调度算法 Integrated Scheduling Algorithm of Complex Product Based on Scheduling Long-path 计算机科学, 2010, 37(2): 150-153. |
| [12] | 李勋 李鹏 顾庆 陈道蓄. 基于PERT技术的人员调度研究 计算机科学, 2008, 35(2): 301-302. |
| [13] | 王振明 都志辉. 基于动态关键路径的仿真网格资源调度算法 计算机科学, 2006, 33(4): 80-84. |
|
||
首页