基于预测的机会式网络编码

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

摘要/Abstract

摘要：

针对理论网络编码在实际应用上的缺陷，以及现有机会式网络编码完全依赖于消息偷听导致应用场合的局限性，以完全不同于网络编码优化问题的思路，提出了基于预测的机会式网络编码的方法。其主要思想是：基于网络流量的自相似性，利用EMD（经验模式分解）和ARMA（自回归滑动平均）预测下一个报文的到达时间，综合计算编码时间、为了编码而等待的时间、传输时间等要素，从而决定是否编码。推导出了网络编码在不同情况下要实现吞吐量正增益可以等待的时间上界。仿真实验结果显示，在吞吐量上，提出的方法相对于理论网络编码平均提高15%左右，相对于当前的存储转发平均提高21%左右。在提高吞吐量的基础上，提出方法也可有效地降低网络的能量消耗。

关键词: 机会式网络编码, 预测, 吞吐量, 最长等待时间, 经验模式分解

Abstract:

Since pure theory network coding had some drawbacks in practical network,however current opportunistic network coding fully depends on overheard information.Thus,in a radically different way from network coding optimization,a novel opportunistic network coding scheme was proposed which was based on prediction (ONCP).The main idea of ONCP was firstly,arrival time of next packet in a node was predicted for the self-similarity of network traffic;:secondly,encoding time,waiting time for coding,transmission time and other factors were taken into account together to determine whether this packet was coded in this node.A theorem—maximum waiting time for was proved network coding in order to obtain throughput gain.Simulation results show that ONCP improves throughput by 15% compared to pure theory network coding and by 21% compared to traditional store-forward.ONCP can also effectively reduce energy consumption while improving throughput.

Key words: opportunistic network coding, prediction, throughput, maximum waiting time, EMD

刘外喜,余顺争,高鹰,胡晓. 基于预测的机会式网络编码[J]. 通信学报, 2013, 34(4): 36-46.

Wai-xi LIU,Shun-zheng YU,Ying GAO,Xiao HU. Opportunistic network coding based on prediction[J]. Journal on Communications, 2013, 34(4): 36-46.

图/表 10

图1

图2

图3

表1

图4

图5

表2

图6

图7

图8

参考文献 31

[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]	LI S Y R , YEUNG R W , CAI N . Linear network coding[J]. IEEE Transactions on Information Theory, 2003,49(2): 371-381.
[3]	CHU X , JIANG Y . Random linear network coding for peer-to-peer applications[J]. Network,IEEE, 2010,24(4): 35-39.
[4]	刘外喜，余顺争，蔡君．安全的网络编码所面临的挑战和对策[J]．计算机科学， 2011,38(6):20-27. LIU W X , YU S Z , CAI J . Secure network coding:challenges and solution[J]. Computer Science, 2011,38(6):20-27.
[5]	HO T , LUN D S . Network Coding:an Introduction[M]. Cambridge Univ Pr, 2008.
[6]	CHAPORKAR P , PROUTIERE A . Adaptive network coding and scheduling for maximizing throughput in wireless networks[A]. Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking[C]. Montreal,QC,Canada, 2007. 135-146.
[7]	KATTI S , RAHUL H , HU W , et al. XORs in the air:practical wireless network coding[J]. IEEE/ACM Transactions on Networking (TON), 2008,16(3): 497-510.
[8]	LE J , LUI J , CHIU D M . DCAR:Distributed coding-aware routing in wireless networks[J]. IEEE Transactions on Mobile Computing, 2010,9(4): 596-608.
[9]	YOMO H , POPOVSKI P . Opportunistic scheduling for wireless network coding[A]. Proceedings of IEEE International Conference on Communications (ICC'07)[C]. Glasgow,Scotland, 2007. 5610-5615.
[10]	CUI T , CHEN L , HO T . Energy efficient opportunistic network coding for wireless networks[A]. Proceedings of the 27th Conference on Computer Communications[C]. Phoenix,AZ,USA, 2008. 361-365.
[11]	KIM Y , DE VECIANA G . Is rate adaptation beneficial for inter-session network coding[J]. IEEE Journal on Selected Areas in Communications, 2009,27(5): 635-646.
[12]	SENGUPTA S , RAYANCHU S , BANERJEE S . An analysis of wireless network coding for unicast sessions:the case for coding-aware routing[A]. Proceedings of 26th IEEE International Conerence on Computer Communications.IEEE(INFOCOM 2007)[C]. Anchorage,Alaska,USA, 2007. 1028-1036.
[13]	杨林，郑刚 . 无线多跳网中具有网络编码意识的机会路由协议[J]. 清华大学学报：自然科学版， 2011(10):1713-1717. YANG L , ZHENG G . Network coding aware opportunistic ro ing protocol in wireless multihop networks[J]. J Tsing hua Univ(Sci ＆Tech), 2011,50(10):1713-1717.
[14]	KIM T S , VURAL S , BROUSTIS I , et al. A framework for joint network coding and transmission rate control in wireless networks[A]. Proceedings of The 29th Conference on Computer Communications.IEEE (INFOCOM 2010)[C]. San Diego,CA,USA, 2010. 1-9.
[15]	KUMAR R , TATI S , DE MELLO F , et al. Network coding aware rate selection in multi-rate IEEE 802.11[A]. Proceedings of 18th IEEE International Conference on Network Protocols(ICNP 2010)[C]. Kyoto,Japan, 2010. 92-102.
[16]	CHEN W , LETAIEF K B , CAO Z . Opportunistic network codi g for wireless networks[A]. Proceedings of IEEE Internationa Conference on Communications (ICC'07)[C]. Glasgow,Scotland, 2007. 4634-4639.
[17]	Kim M , Médard M , O'Reilly U M , et al. An evolutionary approach to inter-session network coding[A]. Proceedings of The 28th Con nce on Computer Communications.IEEE (INFOCOM 2009)[C]. Rio de Janeiro,Brazil, 2009. 450-458.
[18]	黄政，王新 . 网络编码中的优化问题研究[J]．软件学报. 2009,20(5):1349-1361. HUANG Z , WANG X . Research on the optimization problems in network coding[J]. Journal of Software, 2009,20(5):1349-1361.
[19]	邓亮, 赵进, 王新 . 网络编码下的编码开销-链路开销联合优化[J]. 计算机研究与发展， 2010,47(3):390-397. DENG L , ZHAO J , et al. On the joint optimization of coding cost and link cost with network coding[J]. Journal of Computer h and Development, 2010,47(3):390-397.
[20]	LELAND W E , TAQQU M S , WILLINGER W , et al. On the self-similar nature of Ethernet traffic (extended version)[J]. IEEE/ACM Transactions on Networking, 1994,2(1): 1-15.
[21]	PAXSON V , FLOYD S . Wide area traffic:the failure of Poisson modeling[J]. IEEE/ACM Transactions on Networking(ToN), 1995,3(3): 226-244.
[22]	ABRY P , BORGNAT P , RICCIATO F , et al. Revisiting an old friend:on the observability of the relation between long range dependence and heavy tail[J]. Telecommunication Systems. 2010,43(3): 147-165.
[23]	LIU J , SHU Y , ZHANG L , et al. Traffic modeling based on FARIMA models[A]. Proceedings of the 1999 IEEE Canadian Conference on Electrical and Computer Engineering[C]. 1999. 162-167.
[24]	HUANG N E , SHEN Z , LONG S R , et al. The empirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary time series analysis[J]. Proceedings of the Royal Society of London.Series A:Mathematical,Physical and Engineering Sciences, 1998,454(1971): 903-995.
[25]	高波，张钦宇，梁永生等. 基于 EMD 及 ARMA 的自相似网络流量预测[J]．通信学报, 2011,32(4):47-56. GAO B , ZHANG Q Y , LZANG Y S , et al. Predicting self-similar networking traffic based on EMD and ARMA[J]. Journal on Communications, 2011,32(4):47-56.
[26]	王婷 . EMD 算法研究及其在信号去噪中的应用[D]．哈尔滨: 哈尔滨工业大学, 2010. WANG T . Research on EMD Algorithm and Its Application in Signal denoising[D]. Harbin: Harbin Engineering University, 2010.
[27]	[EB/OL].
[28]	BORGNAT P , DEWAELE G , FUKUDA K , et al. Seven years and one day:sketching the evolution of internet traffic[A]. Proceedings of The 28th Conference on Computer Communications.IEEE (INFOCOM 2009)[C]. Rio de Janeiro,Brazil, 2009. 711-719.
[29]	LIU W , YAN Y . Self-similarity and heavy-tail of ICMP traffic[J]. Journal of Computers. 2012,7(12): 2948-2954.
[30]	PEZAROS D P , SIFALAKIS M , HUTCHISON D . On the long-range dependent behaviour of unidirectional packet delay of ireless traffic[A]. Global Telecommunications Conference(GLOBECOM'07).IEEE[C]. Washington,DC,USA, 2007. 2655-2660.
[31]	FLANDRIN P . Wavelet analysis and synthesis of fractional Brownian motion[J]. IEEE Transactions on Information Theory, 1992,38(2): 910-917.

case	w与t- c的关系	w与w’的关系	w’与t- c的关系	等待时间	备注
1	w>t- c	w'<w	w'<t- c	w'=w-v	可以避免“错失编码机会”
2	w>t- c	w'<w	w'>t- c	0
3	w>t- c	w'>w	w'>t- c	0
4	w>t- c	w'>w	w'<t- c		不成立
5	w<t- c	w'<w	w'<t- c	w'=w-v
6	w<t- c	w'<w	w'>t- c		不成立
7	w<t- c	w'>w	w'>t- c	0	可以避免“无效等待”
8	w<t- c	w'>w	w'<t- c	w'= w+v

模块	计算时间开销/s	计算速度/(Mbit·s^{- 1})
EMD	10.203 7	47.041 8
ARMA Modeling	0.424 3	1 131.275 5
Predicting	0.186 6	2 572.347 3