基于网络编码的确定性逐层构造算法

doi:10.11772/j.issn.1001-9081.2017081982

计算机应用 ›› 2018, Vol. 38 ›› Issue (3): 769-775.DOI: 10.11772/j.issn.1001-9081.2017081982

基于网络编码的确定性逐层构造算法

徐光宪, 赵越, 赖俊宁

辽宁工程技术大学电子与信息工程学院, 辽宁葫芦岛 125105

收稿日期:2017-08-15 修回日期:2017-10-19 出版日期:2018-03-10 发布日期:2018-03-07
通讯作者: 赵越
作者简介:徐光宪(1977-),男,江苏盐城人,教授,博士,主要研究方向:信息论、网络编码;赵越(1992-),女,辽宁葫芦岛人,硕士研究生,主要研究方向:信息论、网络编码、信息安全;赖俊宁(1992-),男,辽宁阜新人,硕士,主要研究方向:网络编码、信息安全。
基金资助:
国家科技支撑计划项目（2013BAH12F02）；辽宁省高等学校杰出青年学者成长计划项目（LJQ2012029）。

Deterministic layered construction algorithm based on network coding

XU Guangxian, ZHAO Yue, LAI Junning

School of Electronics and Information Engineering, Liaoning Technical University, Huludao Liaoning 125105, China

Received:2017-08-15 Revised:2017-10-19 Online:2018-03-10 Published:2018-03-07
Supported by:
This work is partially supported by National Science and Technology Support Program of China (2013BAH12F02), the Liaoning Colleges and Universities Fund for Distinguished Young Scholars (LJQ2012029).

摘要/Abstract

摘要：

为了解决适用于多源组播通信的网络编码构造算法存在收敛时间较长的问题，提出一种基于网络编码的确定线性逐层构造算法。在已有研究基础上，利用虚拟信源点进行虚拟试播：首先，根据决策树算法逐层确定获得非满秩局部编码矩阵的节点；然后，重构与该节点对应的上层变换节点的局部编码系数，生成新的编码向量；最后，重传这些编码向量至对应节点，使该节点的局部编码矩阵满秩，从而得到可行的编码方案。在试播过程中允许对出现数据冗余的链路进行修剪枝，以提高带宽利用率。与基于信宿反馈的确定网络编码（SNFDNC）算法相比，该算法只需进行一次虚拟试播。仿真测试结果表明该算法在中等规模网络中收敛时间更短，能进一步提高多源组播通信的平均传输速率。

关键词: 网络编码, 确定性网络拓扑, 多源组播, 逐层构造, 决策树算法, 收敛时间

Abstract:

To solve the problem that the construction algorithm of multi-source multicast network coding costs long convergence time, a deterministic layered construction algorithm based on network coding was proposed. On the basis of existing studies, a virtual source was used for virtual trial. Firstly, the nodes with non-full rank local coding matrix were determined layer-by-layer by decision tree algorithm. Then, the local encoding coefficients of the upper transform nodes were reconstructed and a new encoding vector was generated. Finally, the new encoding vector was transmitted to the lower node corresponding to it, and the local coding matrix of the lower node was full rank, so a feasible coding scheme was obtained to realize network coding. Moreover, when redundant data is found in some links, pruning branches method was implemented to improve bandwidth utilization. The algorithm only needs one virtual trial multicast in comparison with the Sink Nodes Feedback Deterministic Network Coding (SNFDNC), and the simulation results show that the convergence time of the proposed algorithm is shorter in the medium scale network, and the average transmission rate of multicast communication is further improved.

Key words: network coding, deterministic network topology, multi-source multicast, layered construction, decision tree algorithm, convergence time

中图分类号:

TP393.02

徐光宪, 赵越, 赖俊宁. 基于网络编码的确定性逐层构造算法[J]. 计算机应用, 2018, 38(3): 769-775.

XU Guangxian, ZHAO Yue, LAI Junning. Deterministic layered construction algorithm based on network coding[J]. Journal of Computer Applications, 2018, 38(3): 769-775.

参考文献

[1] AHLSWEDE R, CAI N, LI S-Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216.
[2] KOETTER R, MÉDARD M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking, 2003, 11(5):782-795.
[3] JAGGI S, SANDERS P, CHOU P A, et al. Polynomial time algorithms for multicast network code construction[J]. IEEE Transactions on Information Theory, 2005, 51(6):1973-1982.
[4] YEUNG R W. Information Theory and Network Coding[M]. Berlin:Springer-Verlag, 2010:505-545.
[5] 蒲保兴,王伟平.线性网络编码运算代价的估算与分析[J].通信学报,2011,32(5):47-55. (PU B X, WANG W P. Evaluation and analysis of the computation[J]. Journal on Communications, 2011, 32(5):47-55.)
[6] 陈超.确定网络编码的安全特性研究[D].南京:南京理工大学,2012:15. (CHEN C. Research on deterministic network coding[D]. Nanjing:Nanjing University of Science and Technology, 2012:15.)
[7] CHARLES D, JAUTER K, LAUTER K. Signatures for network coding[J]. International Journal of Information and Coding Theory, 2009, 1(1):3-4.
[8] 王龙翔.基于网络编码的MAC协议研究[D].成都:电子科技大学,2013:12. (WANG L X. Research on MAC protocol based on network coding[D]. Chengdu:University of Electronic Science and Technology of China, 2013:12.)
[9] LUN D S, MÉDARD M, KOETTER R, et al. On coding for reliable communication over packet networks[J]. Physical Communication, 2008, 1(1):3-20.)
[10] 付卫平,蒲保兴,刘远军,等.确定性网络编码构造的仿真实现[J].邵阳学院学报(自然科学版),2013,10(1):26-32. (FU W P, PU B X, LIU Y J, et al. Simulation implementation of deterministic construction of network coding[J]. Journal of Shaoyang University (Natural Science Edition), 2013, 10(1):26-32.)
[11] 魏姗.基于网络编码的分层组播算法研究[D].长沙:中南大学,2012:25. (WEI S. Layered multicast based on network coding[D]. Changsha:Central South University, 2012:25.)
[12] 蒲保兴,杨路明,王伟平.网络拓扑未知环境下确定性网络编码数据传输[J].电子学报,2009,37(10):2119-2124. (PU B X, YANG L M, WANG W P. A deterministic data transmission approach with network coding under unknown network topology[J]. Acta Electronica Sinica, 2009, 37(10):2119-2124.)
[13] 靳美丽.基于网络编码的分布式卫星路由算法[D].西安:西安电子科技大学,2013:33-40. (JIN M L. A distributed satellite routing algorithm based on network coding[D]. Xi'an:Xidian University, 2013:33-40.)
[14] 王白婷.能量有效的无线传感网分簇路由协议研究[D].长春:吉林大学,2016:25. (WANG B T. Research on energy efficient clustering routing protocol for wireless sensor networks[D]. Changchun:Jilin University, 2016:25.)
[15] WIDMER J, CAPALBO A, ANTA A F, et al. Efficient interlayer network codes for fair layered multicast streaming[J]. IEEE/ACM Transactions on Networking, 2015, 23(4):1107-1120.
[16] TASSI A, CHATZIGEORGIOU I, VUKOBRATOVIC D. Resource-allocation frameworks for network-coded layered multimedia multicast services[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(2):141-155.
[17] CHENG M X, YE Q, CHENG X, et al. Network coding and coding-aware scheduling for multicast in wireless networks[C]//ICC 2015:Proceedings of the 2015 IEEE International Conference on Communications. Piscataway, NJ:IEEE, 2015:5703-5708.
[18] KWON M, PARK H. Network coding-based distributed network formation game for multi-source multicast networks[C]//ICC 2017:Proceedings of the 2017 IEEE International Conference on Communications. Piscataway, NJ:IEEE, 2017.
[19] 陈仁亮,韩亮,董超,等.基于随机网络编码的转发速率在线控制策略[J].军事通信技术,2016,37(1):8-11. (CHEN R L, HAN L, DONG C, et al. Online forwarding rate controlling strategy based on random network coding[J]. Journal of Millitary Communications Technology, 2016, 37(1):8-11.)
[20] 蒲保兴,杨路明,王伟平.线性网络编码的导出与扩展[J].软件学报,2011,2(3):558-571. (PU B X, YANG L M, WANG W P. Generation and extension of linear network coding[J]. Journal of Software, 2011, 22(3):558-571.)
[21] LANGBERG M, SPRINTSON A, BRUCK J. The encoding complexity of network coding[J]. IEEE/ACM Transactions on Networking, 2006, 14(SI):2386-2397.
[22] 尹吉星,任平安.基于网络编码的多播路由算法研究[J].计算机技术与发展,2014,24(5):9-82. (YIN J X, REN P A. Multicast routing algorithm based on network coding[J]. Computer Technology and Development, 2014, 24(5):79-82.)
[23] 徐光宪,赖俊宁.新型集中式网络编码组播路由算法[J/OL].计算机科学与探索(2016-11-01)[2017-02-22]. http://d.g.wanfangdata.com.cn/Periodical_pre_cfe78018-9cd1-45c6-8e0b-a99f3e67cab2.aspx. (XU G X, LAI J N. Centralized network coding multicast routing algorithm[J/OL]. Journal of Frontiers of Computer Science and Technology (2016-11-01)[2017-02-22]. http://d.g.wanfangdata.com.cn/Periodical_pre_cfe78018-9cd1-45c6-8e0b-a99f3e67cab2.aspx.)
[24] 潘峰.基于C5.0决策树算法的考试结果预测研究[J].微型机与应用,2016,35(8):68-70. (PAN F. The test results prediction research based on C5.0 decision tree algorithm[J]. Microcomputer & Its Applications, 2016, 35(8):68-70.)
[25] 蔡慧,刘洪波,韩国栋,基于K均值聚类的随机网络拓扑模型[J].计算机工程与设计,2009,30(5):1089-1091. (CAI H, LIU H B, HAN G D. Random network topology model based on K-means[J]. Computer Engineering and Design, 2009, 30(5):1089-1091.)
[26] YUAN N Q, JIANG T, BAI S, et al. Dynamic network model analysis based on communication network[J]. Advanced Materials Research, 2014, 989/990/991/992/993/994:2639-2642.
[27] 杨建业.动态网络拓扑结构变化的多角度度量[D].西安:西安电子科技大学,2013:9. (YANG J Y. Multi-aspects measurement of topological structure in dynamic networks[D]. Xi'an:Xidian University, 2013:9.)

基于网络编码的确定性逐层构造算法

Deterministic layered construction algorithm based on network coding

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王雅辉, 钱宇华, 刘郭庆. 基于模糊优势互补互信息的有序决策树算法[J]. 计算机应用, 2021, 41(10): 2785-2792.
[2]	徐光宪, 王栋. 基于混沌加密对抗窃听的安全网络编码方案[J]. 计算机应用, 2019, 39(5): 1374-1377.
[3]	辛营营, 刘晓娟, 方春林, 罗欢. 信息中心网络内数据重传算法的优化[J]. 计算机应用, 2019, 39(3): 829-833.
[4]	崔华力, 孙钦东, 张兴军, 伍卫国. 视频流传输中的网络编码综述[J]. 计算机应用, 2018, 38(4): 1084-1088.
[5]	高枫越, 王琰, 李牧, 于睿. 联合信道非相干网络编码调制方法[J]. 计算机应用, 2018, 38(10): 2955-2959.
[6]	周坤晓, 赵慧, 袁华强. 认知无线电网络组播路由算法和协议综述[J]. 计算机应用, 2017, 37(2): 422-426.
[7]	姚玉坤, 李小勇, 任智, 刘江兵. 基于协作网络编码的高效媒体访问控制协议[J]. 计算机应用, 2017, 37(10): 2748-2753.
[8]	黄成兵, 唐刚, 王波. 基于超级节点MAC中继的复域分布检测非正交网络编码[J]. 计算机应用, 2016, 36(12): 3256-3261.
[9]	何克岩, 赵宏宇. 新的对抗全局窃听的安全网络编码方案[J]. 计算机应用, 2016, 36(12): 3317-3321.
[10]	国强, 秦月. 改进的基于网络编码中继转发方案[J]. 计算机应用, 2016, 36(1): 61-65.
[11]	陈卓, 周江. 基于网络编码的对等网流媒体网络中优化的带宽分配策略[J]. 计算机应用, 2015, 35(6): 1509-1513.
[12]	蒲保兴, 朱鸿鹏, 赵乘麟. 多源多宿组播网络编码的可达信息率区域[J]. 计算机应用, 2015, 35(6): 1546-1551.
[13]	蒲保兴, 赵乘麟. 基于网络编码的组播率与编码节点数的平衡[J]. 计算机应用, 2015, 35(4): 929-933.
[14]	邱树伟, 李琰琰. 能量捕获无线传感器网络中低时延的可靠数据传递[J]. 计算机应用, 2015, 35(2): 345-350.
[15]	刘期烈吴阳阳曹傧. 无线网络中基于网络编码的重传机制[J]. 计算机应用, 2014, 34(2): 309-312.