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

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

Abstract

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

CLC Number:

TN92

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.

Figures/Tables 14

参数	含义
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	节点间协作传输信号功率

时间片	事件	解码矩阵 $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}]$

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

参数	含义	取值范围
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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 15

Related Articles 15

Metrics

Recommended 0

[1]	Ke LAI, Jing LEI, Wei LIU, Lei WEN. HARQ scheme for sparse code multiple access based on network coding [J]. Journal on Communications, 2022, 43(9): 57-69.
[2]	Junyi YANG, Bo LI, Qinyu ZHANG. Resource optimization for UAV relay networks based on physical-layer network coding [J]. Journal on Communications, 2021, 42(9): 12-20.
[3]	Guangjun LIU, Wangmei GUO, Jinbo XIONG, Ximeng LIU, Changyu DONG. Lightweight privacy protection data auditing scheme for regenerating-coding-based distributed storage [J]. Journal on Communications, 2021, 42(7): 220-230.
[4]	Baoxing PU,Zhiyi MO. Construction method of double unicast network coding [J]. Journal on Communications, 2020, 41(9): 92-103.
[5]	Huifang YU,Wen LI. Homomorphic signature schemes for single-source and multi-source network coding [J]. Journal on Communications, 2019, 40(11): 112-121.
[6]	Yue CHEN,Longjiang WANG,Xincheng YAN,Xinyue ZHANG. Mimic storage scheme based on regenerated code [J]. Journal on Communications, 2018, 39(4): 21-34.
[7]	Shuaifang XIAO,Yunfei GUO,Kaizhi HUANG,Liang JIN. Cooperative secret key generation for multi-hop relaying systems in Internet of things [J]. Journal on Communications, 2018, 39(3): 86-94.
[8]	Hao WU,Cheng-zhe LAI,Jiu-lun FAN,Jian-hua LIU. Data update algorithm based on secure network coding in cloud environment [J]. Journal on Communications, 2017, 38(5): 121-127.
[9]	Long-jiang WANG,Yue CHEN,Xin-cheng YAN,Kai-xiang HUANG. Differential data update scheme on network-coding-based cloud storage system [J]. Journal on Communications, 2017, 38(3): 154-164.
[10]	Rui-feng GAO,Xiao-dong JI,Zhi-hua BAO,Shi-bing ZHANG,Chen XU. Denoise-and-forward based adaptive diversity scheme for physical-layer network coding with multiple relay node [J]. Journal on Communications, 2017, 38(2): 81-93.
[11]	gang CHENZhi,jian SHENXiao,Li LIU. Minimal coding cost and low delay multicast routing of wireless mesh networks [J]. Journal on Communications, 2016, 37(1): 10-16.
[12]	HANGFeng-jun S,juan GONGWen,Zhe GENG. MAC mechanism based on link prediction and network coding [J]. Journal on Communications, 2016, 37(1): 17-27.
[13]	Xiao-jian SHEN,Zhi-gang CHEN,Li LIU. Load balancing multicast routing based on network coding in wireless mesh network [J]. Journal on Communications, 2015, 36(4): 90-95.
[14]	Bao-feng JI,Kang SONG,Yi WANG,Yong-ming HUANG,Lv-xi YANG. Cooperative transmission scheme of relay selection combined with network coding and its performance analysis [J]. Journal on Communications, 2015, 36(3): 41-51.
[15]	Da-peng WU,Peng-wen LOU,Qiao-shou LIU,Yu XIONG,Ru-yan WANG. Coding redundancy controlled data forwarding mechanism in opportunistic networks [J]. Journal on Communications, 2015, 36(3): 63-74.