基于网络编码的协作恢复机制线性可解性研究

doi:10.11959/j.issn.1000-436x.2021050

通信学报 ›› 2021, Vol. 42 ›› Issue (5): 216-229.doi: 10.11959/j.issn.1000-436x.2021050

• 学术通信 • 上一篇

基于网络编码的协作恢复机制线性可解性研究

殷俊¹^,², 沙雪琪², 王磊¹^,², 张登银¹^,², 杨余旺³

¹ 南京邮电大学江苏省宽带无线通信重点实验室，江苏南京 210003
² 南京邮电大学物联网学院，江苏南京 210003
³ 南京理工大学计算机科学与工程学院，江苏南京 210004

修回日期:2021-02-07 出版日期:2021-05-25 发布日期:2021-05-01
作者简介:殷俊（1989- ），男，安徽巢湖人，博士，南京邮电大学讲师，主要研究方向为网络编码及其应用
沙雪琪（2000- ），女，江苏徐州人，南京邮电大学硕士生，主要研究方向为协作通信
王磊（1986- ），男，安徽马鞍山人，博士，南京邮电大学副教授，主要研究方向为网络编码及其应用
张登银（1964- ），男，江苏靖江人，博士，南京邮电大学研究员，主要研究方向为现代通信网络、信号与信息处理技术等
杨余旺（1966- ），男，安徽桐城人，博士，南京理工大学教授，主要研究方向为网络编码、工业物联网等
基金资助:
国家自然科学基金资助项目(61971235);国家自然科学基金资助项目(61801236);国家基础科研计划基金资助项目(JCKY201760xxx003);国家基础科研计划基金资助项目(JCKY201860xxx001);南邮科研基金资助项目(NY217148);南邮科研基金资助项目(NY219111);苏州创新计划基金资助项目(SYG201826)

Research on linear solvability of network coding based cooperative recovery scheme

Jun YIN¹^,², Xueqi SHA², Lei WANG¹^,², Dengyin ZHANG¹^,², Yuwang YANG³

¹ Jiangsu Key Laboratory of Broadband Wireless Communication, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
² School of Internet of Things, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
³ School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210004, China

Revised:2021-02-07 Online:2021-05-25 Published:2021-05-01
Supported by:
The National Natural Science Foundation of China(61971235);The National Natural Science Foundation of China(61801236);Basic Research Foundation of China(JCKY201760xxx003);Basic Research Foundation of China(JCKY201860xxx001);Nanjing University of Posts and Telecommunications Science Foundation(NY217148);Nanjing University of Posts and Telecommunications Science Foundation(NY219111);Research Program of Suzhou(SYG201826)

摘要/Abstract

摘要：

针对基于网络编码的协作恢复（CR）机制线性可解性未知问题，建立了CR机制网络编码包的线性可解性的量化分析模型，给出了在任意阶伽罗华编码有限域下接收方解码出所有源数据包的概率上下界，并提出了一种改进Gauss-Jordan的线性可解性在线判定算法。数值实验结果验证了所提上下界的紧密性和改进Gauss-Jordan算法解码的低等待时延特性，节点部署实验显示改进Gauss-Jordan算法较传统Gauss算法解码复杂度降低35%。

关键词: 协作恢复, 网络编码, 线性可解性, 改进Gauss-Jordan算法

Abstract:

The linear solvability of network coding based cooperative recovery/repair (CR) scheme was studied.Specifically, the solvability analysis model for network coding based CR scheme was established, the upper and lower bounds of the probability for any receiver to decode all original information under arbitrary order of Galois coding field were proposed and proved, and an on-line solvability judgement algorithm was designed by improvement of Gauss-Jordan algorithm.Numerical results validate the compactness of the proposed upper and lower bounds as well as the short-time decoding waiting delay of the improved Gauss-Jordan algorithm.Node deployment experiments show that the decoding complexity of the improved Gauss Jordan algorithm is reduced by 35% compared with the traditional Gauss algorithm.

Key words: cooperative recovery/repair, network coding, linear solvability, improved Gauss-Jordan algorithm

中图分类号:

TN92

殷俊, 沙雪琪, 王磊, 张登银, 杨余旺. 基于网络编码的协作恢复机制线性可解性研究[J]. 通信学报, 2021, 42(5): 216-229.

Jun YIN, Xueqi SHA, Lei WANG, Dengyin ZHANG, Yuwang YANG. Research on linear solvability of network coding based cooperative recovery scheme[J]. Journal on Communications, 2021, 42(5): 216-229.

图/表 14

图1

图2

表1

模型参数及其含义"

参数	含义
M	协作簇内节点数量
$S_{N}$	源数据包集合向量，数据包数量为N
F_q	阶为q的编码伽罗华有限域GF(q)
e_sr	广播阶段信道删除率
e_rd	协作阶段信道删除率
Pr_suc	一次完整CR过程节点解码出所有源数据包概率
C	编码系数矩阵，也称为传输矩阵
snr_{i ,j}	节点间协作传输信道信噪比
snr_base,i	基站与节点间广播信道信噪比
E_threshold	频谱效率门限
h_{i ,j}	节点间协作传输信道增益
h_base,i	基站与节点间广播信道增益
n_{i ,j}	节点间协作传输信道噪声
n_base,i	基站与节点间广播信道噪声
u	路径损耗指数
P_base	基站广播信号功率
P_i	节点间协作传输信号功率

表1

图3

表2

改进Gauss-Jordan算法解码过程"

时间片	事件	解码矩阵 $C$	码字阵 $C P$
1	Receive(s₁) (失败)	NULL	NULL
2	Receive(s₂) (失败)	NULL	NULL
3	Receive(s₃)	$[\begin{matrix} 0 & 0 & 1 \end{matrix}]$	$[s_{3}]$
4	Receive( $c p_{1}$ )	$[\begin{matrix} \begin{matrix} 0 & 1 & 0 \end{matrix} \\ \begin{matrix} 0 & 0 & 1 \end{matrix} \end{matrix}]$	$[\begin{matrix} s_{2} \\ s_{3} \end{matrix}]$
5	Receive( $c p_{2}$ )	$[\begin{matrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}]$	$[\begin{matrix} 2 s_{1} \\ s_{2} \\ s_{3} \end{matrix}]$
5	rank=3 (解码完成)	$[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}]$	$[\begin{matrix} s_{1} \\ s_{2} \\ s_{3} \end{matrix}]$

表2

图4

表3

图5

图6

表4

图7

图8

图9

图10

参考文献 15

[16]	HO T , MEDARD M , KOETTER R ,et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory, 2006,52(10): 4413-4430.
[17]	TRULLOLS-CRUCES O , BARCELO-ORDINAS J M , FIORE M . Exact decoding probability under random linear network coding[J]. IEEE Communications Letters, 2011,15(1): 67-69.
[18]	LANEMAN J N , WORNELL G W . Distributed space-time-coded protocols for exploiting cooperative diversity in wireless networks[J]. IEEE Transactions on Information Theory, 2003,49(10): 2415-2425.
[19]	TSE D , VISWANATH P . Fundamentals of wireless communication[M]. Cambridge: Cambridge University Press, 2005.
[20]	BL?MER J , KARP R , WELZL E . The rank of sparse random matrices over finite fields[J]. Random Structures ＆ Algorithms, 1997,10(4): 407-419.
[21]	LI X L , MOW W H , TSANG F L . Rank distribution analysis for sparse random linear network coding[C]// 2011 International Symposium on Networking Coding. Piscataway:IEEE Press, 2011: 1-6.
[22]	MARRIOT P . Finite Markov chains[R]. Waterloo:University of Waterloo, 2015.
[23]	王磊 . 网络编码理论与实践[M]. 上海: 上海交通大学出版社, 2017.
	WANG L . Network coding theory and applications[M]. ShangHai: ShangHai Jiao Tong University Press, 2017.
[1]	GUO W , FUENTES M , CHRISTODOULOU L ,et al. Roads to multimedia broadcast multicast services in 5G new radio[C]// International Symposium on Broadband Multimedia Systems and Broadcasting,Piscataway:IEEE Press, 2018: 1-5.
[2]	DRESSLER F , KLINGLER F , SOMMER C ,et al. Not all VANET broadcasts are the same:context-aware class based broadcast[J]. IEEE/ACM Transactions on Networking, 2018,26(1): 17-30.
[3]	KARIMI P , SHERMAN M , BRONZINO F ,et al. Evaluating 5G multihoming services in the MobilityFirst future Internet architecture[C]// 2017 IEEE 85th Vehicular Technology Conference. Piscataway:IEEE Press, 2017: 1-5.
[4]	QIU C X , SHEN H Y , SOLTANI S ,et al. CEDAR:a low-latency and distributed strategy for packet recovery in wireless networks[J]. IEEE/ACM Transactions on Networking, 2015,23(5): 1514-1527.
[5]	BENRHAIEM W , HAFID A , SAHU P K . Reliable emergency message dissemination scheme for urban vehicular networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2020,21(3): 1154-1166.
[6]	PARK J S , GERLA M , LUN D S ,et al. Codecast:a network-coding-based ad hoc multicast protocol[J]. IEEE Wireless Communications, 2006,13(5): 76-81.
[7]	DATSIKA E , ANTONOPOULOS A , ZORBA N ,et al. Cross-network performance analysis of network coding aided cooperative outband D2D communications[J]. IEEE Transactions on Wireless Communications, 2017,16(5): 3176-3188.
[8]	YAN Y , ZHANG B X , LI C . Opportunistic network coding based cooperative retransmissions in D2D communications[J]. Computer Networks, 2017,113: 72-83.
[9]	GOU L , ZHANG G X , BIAN Z G ,et al. Minimizing completion time for relay-assisted multicast with instantly decodable network coding[J]. IEEE Communications Letters, 2016,20(3): 434-437.
[10]	ABOUTORAB N , SADEGHI P , TAJBAKHSH S E . Instantly decodable network coding for delay reduction in cooperative data exchange systems[C]// 2013 IEEE International Symposium on Information Theory. Piscataway:IEEE Press, 2013: 3095-3099.
[11]	王练, 王萌, 任治豪 ,等. D2D 网络中基于立即可解网络编码的时延最小化重传方案[J]. 电子与信息学报, 2018,40(7): 1691-1698.
	WANG L , WANG M , REN Z H ,et al. Delay minimization retransmission scheme based on instantly decodable network coding for D2D communications[J]. Journal of Electronics ＆ Information Technology, 2018,40(7): 1691-1698.
[12]	FAN Y F , JIANG Y X , ZHU H J ,et al. PIE:cooperative peer-to-peer information exchange in network coding enabled wireless networks[J]. IEEE Transactions on Wireless Communications, 2010,9(3): 945-950.
[13]	XU X L , KUMAR M P , GUAN Y L ,et al. Two-phase cooperative broadcasting based on batched network code[J]. IEEE Transactions on Communications, 2016,64(2): 706-714.
[14]	欧莽, 汪继文 . VANETs中基于分布式TDMA的协作网络编码方法[J]. 华南理工大学学报(自然科学版), 2020,48(1): 104-113.
	OU M , WANG J W . Cooperative network coding in VANETs based on distributed TDMA[J]. Journal of South China University of Technology (Natural Science Edition), 2020,48(1): 104-113.
[15]	AHLSWEDE R , CAI N , LI S Y R ,et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000,46(4): 1204-1216.

参数	含义	取值范围
M/个	协作簇内节点数量	10～25
N/个	源数据包数量	5～15
q	编码有限域F_q/GF(q)的阶	2～2¹⁶
e_sr	广播阶段数据包删除率	0.1～0.9
e_rd	协作阶段数据包删除率	0.1～0.9

参数	值	参数	值
微处理器	MC9S08GB60	闪存/KB	512
RAM/KB	4	工作电压/V	3.4
有限域阶	2⁴,2⁸	时钟频率/MHz	40
e_sr	0.5	源数据包数	32
数据包载荷/ksymbol	1	实验重复次数	10⁶

基于网络编码的协作恢复机制线性可解性研究

Research on linear solvability of network coding based cooperative recovery scheme

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 15

相关文章 15

Metrics

推荐阅读 0

[1]	赖恪, 雷菁, 刘伟, 文磊. 基于网络编码的稀疏码分多址接入HARQ方案[J]. 通信学报, 2022, 43(9): 57-69.
[2]	杨君一, 李博, 张钦宇. 基于物理层网络编码的无人机中继网络资源优化[J]. 通信学报, 2021, 42(9): 12-20.
[3]	刘光军, 郭网媚, 熊金波, 刘西蒙, 董长宇. 适用于再生编码分布式存储的轻量型隐私保护审计方案[J]. 通信学报, 2021, 42(7): 220-230.
[4]	蒲保兴,莫智懿. 双单播网络编码的构造方法[J]. 通信学报, 2020, 41(9): 92-103.
[5]	俞惠芳,李雯. 单/多源网络编码同态签名方案[J]. 通信学报, 2019, 40(11): 112-121.
[6]	陈越,王龙江,严新成,张馨月. 基于再生码的拟态数据存储方案[J]. 通信学报, 2018, 39(4): 21-34.
[7]	肖帅芳,郭云飞,黄开枝,金梁. 面向物联网多跳中继系统的协作密钥生成方法[J]. 通信学报, 2018, 39(3): 86-94.
[8]	吴昊,赖成喆,范九伦,刘建华. 云环境下基于安全网络编码的数据更新算法[J]. 通信学报, 2017, 38(5): 121-127.
[9]	王龙江,陈越,严新成,黄恺翔. 网络编码云存储系统差分数据更新方案[J]. 通信学报, 2017, 38(3): 154-164.
[10]	高锐锋,吉晓东,包志华,张士兵,徐晨. 多中继去噪重传物理层网络编码自适应分集策略[J]. 通信学报, 2017, 38(2): 81-93.
[11]	陈志刚,沈小建,刘立. 无线mesh网中最小编码代价低时延多播路由[J]. 通信学报, 2016, 37(1): 10-16.
[12]	尚凤军,龚文娟,耿哲. 基于链路预测和网络编码的MAC机制[J]. 通信学报, 2016, 37(1): 17-27.
[13]	沈小建,陈志刚,刘立. 无线mesh网络中编码感知且负载均衡的多播路由[J]. 通信学报, 2015, 36(4): 90-95.
[14]	冀保峰,宋康,王毅,黄永明,杨绿溪. 联合网络编码和中继选择的协作传输方案及其性能分析[J]. 通信学报, 2015, 36(3): 41-51.
[15]	吴大鹏,楼芃雯,刘乔寿,熊余,王汝言. 带有编码冗余控制的机会网络数据转发机制[J]. 通信学报, 2015, 36(3): 63-74.