基于Markov状态转移方法的网络编码时延分析

doi:10.3969/j.issn.1000-436x.2013.09.010

Abstract

Abstract:

Network coding has been validated as an effective means to improve network throughput and reliability,but the study of its delay performance is not enough.Agai the widely used random linear network coding,the proposed method,based on the Markov state transfer,analyzed the delay expectation and probability distribution of the unicast flow in a single hop scene,and presented the exact recursions.Then according to numerical simulation,the effect of the encoding parameters were analyzed such as the finite f eld size,the channel loss rate and the encoding batch size on the delay.The results show that,as the finite field q increases,the delay variance continues to become smaller; the average delay is almost linear with the channel loss rate and the encoding batch size individually.

Key words: network coding, Markov chain, delay distribution, delay expectation

Yu-ben QU,Chen CHEN,Chao DONG,Hai WANG. Analysis of network coding delay:a Markov state transfer approach[J]. Journal on Communications, 2013, 34(9): 77-83.

Figures/Tables 9

References 20

[1]	AHLSWEDE R , CAI N , LI S R . Network information flow[J]. IEEE Transactions on Information Theory, 2000,46(4): 1204-1216.
[2]	ALIREZA K H , RUDOLF R . Bounds of benefit of network coding:throughput and energy saving in wireless networks[A]. Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM 2008)[C]. Phoenix,AZ,USA, 2008.
[3]	MAJID G , DON T , JIM K . Reliability gain of network coding in lossy wireless networks[A]. Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM 2008)[C]. Phoenix,AZ,USA, 2008.
[4]	CHACHULSKI S , JENNINGS M , KATTI S . Trading structure for randomness in wireless opportunistic routing[A]. Proceedings of International Conference on Special Interest Group on Data Communications (SIGCOMM 2007)[C]. Kyoto,Japan, 2007.
[5]	HO T , KOETTER R , MEDARD M . The benefits of coding over routing in a randomized setting[A]. Proceedings of ISIT 2003[C]. Yokohama,Japan, 2003.
[6]	HO T , LUN D . Network Coding:an Introduction[M]. Cambridge University Press, 2008.
[7]	FRAGOULI C , SOLJANIN E . Network coding applications[J]. Foundations and Trends in Networking, 2007,2(2): 135-269.
[8]	董超, 田畅, 倪明放 . Ad hoc 网络时钟同步研究[J]. 通信学报, 2006,27(9): 110-117. DONG C , TIAN C , NI M F . Research on clock synchronization of ad hoc networks[J]. Journal on Communications, 2006,27(9): 110-117.
[9]	CHOU P , WU Y , JAIN K . Practical network coding[A]. Proceedings of 43rd Allerton Conference on Communication Control and Computing[C]. Illinois,USA. 2005.
[10]	KATTI S , RAHUL H , HU W . XORs in the air:practical wireless network coding[A]. Proceedings of International Conference on Special Interest Group on Data Communications (SIGCOMM 2006)[C]. Pisa,Italy, 2006.
[11]	LI X H , WANG C C , LIN X J . Throughput and delay analys on uncoded and coded wireless broadcast with hard deadline constraints[A]. Proceedings of 29th IEEE International Conference on Computer Communications (INFOCOM 2010)[C]. San Diego,CA,USA, 2010.
[12]	ZHANG C , FANG Y U , ZHU X Y . Throughput-delay tradeoffs in large-scale manets with network coding[A]. Proceedings of 28th IEEE International Conference on Computer Communications (INFOCOM 2009)[C]. Rio de Janeiro,Barzil, 2009.
[13]	ERYILMAZ A , OZDAGLAR A , MEDARD M . On delay performance gains from network coding[A]. Proceedings of 40th Annual Conference on Information Sciences and Systems (CISS 2006)[C]. Princeton,NJ,USA, 2006.
[14]	BARROS J , COSTA R , MUNARETTO D . Effective delay control in online network coding[A]. Proceedings of 28th IEEE International Conference on Computer Communications (INFOCOM 2009)[C]. Rio de Janeiro,Barzil, 2009.
[15]	NISTOR M , COSTA R , VINHOZA T . Non-asymptotic analysis of network coding delay[A]. Proceedings of 2010 IEEE International Symposium on Network Coding (NetCod 2010)[C]. Toronto,Cana, 2010.
[16]	COSTA R , MUNARETTO D , WIDMER J . Informed network coding for minimum decoding delay[A]. Proceedings of 5th IEEE International Conference on Mobile Ad Hoc and Sensor Systems (MASS 2008)[C]. Atlanta,Georgia, 2008.
[17]	SADEGHI P , SHAMS R , TRASKOV D . An optimal adaptive network coding scheme for minimizing decoding delay in broadcast erasure channels[J]. EURASIP Journal on Wireless Communications and Networking, 2010,(4): 1-14.
[18]	SUNDARARAJAN J , SHAH D , MEDARD M . Online network coding for optimal throughput and delay–the three-receiver case[A]. Proceedings of International Symposium on Information Theory Its Applications (ISITA 2008)[C]. Auckland,New Zealand, 2008.
[19]	SHARMA G , MAZUMDAR R , SHROFF N . Delay and capacit trade-offs in mobile ad hoc networks:a global perspective[J]. IEEE/ACM Transactions on Networking, 2007,15(5): 981-992.
[20]	MORAES R , SADJADPOUR H , GARCIA J . Throughput-delay analysis of mobile ad hoc networks with a multi-copy relaying strategy[A]. Proceedings of First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON 2004)[C]. Santa,Clara,USA, 2004.

Metrics

Recommended 0

No Suggested Reading articles found!

Analysis of network coding delay:a Markov state transfer approach

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 20

Related Articles 15

Metrics

Recommended 0

[1]	Haiyan KANG, Molan LONG. Research on network attack analysis method based on attack graph of absorbing Markov chain [J]. Journal on Communications, 2023, 44(2): 122-135.
[2]	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.
[3]	Wei SHE, Xinpeng RONG, Wei LIU, Zhao TIAN. Generative blockchain-based covert communication model based on Markov chain [J]. Journal on Communications, 2022, 43(10): 121-132.
[4]	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.
[5]	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.
[6]	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.
[7]	Baoxing PU,Zhiyi MO. Construction method of double unicast network coding [J]. Journal on Communications, 2020, 41(9): 92-103.
[8]	Xin JIAN,Yixiao WEI,Yuqin LIU,Jian SONG,Xiaoping ZENG,Xiaoheng TAN. Power consumption modeling and optimization for NB-IoT eDRX [J]. Journal on Communications, 2019, 40(4): 107-116.
[9]	Huifang YU,Wen LI. Homomorphic signature schemes for single-source and multi-source network coding [J]. Journal on Communications, 2019, 40(11): 112-121.
[10]	Yue CHEN,Longjiang WANG,Xincheng YAN,Xinyue ZHANG. Mimic storage scheme based on regenerated code [J]. Journal on Communications, 2018, 39(4): 21-34.
[11]	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.
[12]	Xin JIAN,Yuqin LIU,Yixiao WEI,Jian SONG,Fang WANG,Shu FU,Xiaoheng TAN. Performance analysis and optimization for coverage classes updating mechanism of narrow-band internet of things [J]. Journal on Communications, 2018, 39(11): 70-79.
[13]	Xian-zhong TIAN,Min GUO,Jia-cun HE,Gao LIU,Yi-nan ZHU. Multi relay node selection strategy for energy capture collaborative relay network [J]. Journal on Communications, 2017, 38(Z2): 1-7.
[14]	Feng LI,Ya-li SI,Zhen CHEN,Li-min SHEN. Lightweight opportunistic routing forwarding strategy based on Markov chain [J]. Journal on Communications, 2017, 38(5): 108-120.
[15]	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.