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

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

摘要/Abstract

摘要：

网络编码已被验证是改善无线网络吞吐量、可靠性等性能的有效手段，但其对业务流时延性能影响的研究还不充分。针对得到广泛应用的随机线性网络编码，提出了一种基于马尔可夫状态转移的方法对单跳场景下单播业务流时延的期望值以及概率分布进行了分析，同时给出了相应的递推解析式，然后数值分析了有限域大小、信道丢失率、编码批次大小等编码参数对时延的影响。结果表明，随着有限域q的增大，时延的方差不断变小；时延的期望值与信道丢失率、编码批次大小几乎都成线性关系。

关键词: 网络编码, 马尔可夫链, 时延分布, 时延期望值

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

屈毓锛,陈晨,董超,王海. 基于Markov状态转移方法的网络编码时延分析[J]. 通信学报, 2013, 34(9): 77-83.

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.

图/表 9

图1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献 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.