摘要
网络编码打破了通信网络中传统的信息处理方式,网络节点对信息进行编码等处理,使得信息传输速率达到网络的最大流,提升网络的吞吐量、节约传输带宽和均衡负载等。但是,网络编码系统中的编解码操作,必将给网络带来额外的开销。因此,减少网络编码操作的额外开销,对网络编码的传输过程进行优化,对推动网络编码的实际应用有重要的意义。
论文以网络编码理论及其优化机制为基础,对网络编码优化及其在不同领域下的应用进行了研究。研究成果包括以下几方面:
基于遗传算法的网络编码优化:针对网络编码的单目标优化建立了优化模型,并在模型基础上设计了基于简单遗传算法的最小化编码节点的优化算法MCN。仿真结果表明,算法有效地减少了参与编码的节点数量。针对网络编码的多目标优化问题,综合考虑编码消耗和链路消耗问题,设计了基于NSGA-II算法的网络编码的多目标优化算法MOONC。仿真结果表明,该算法能有效得到Pareto解,并降低了网络的整体开销。
结合机会路由的部分网络编码优化:针对无线网络中广播通信能量效率、网络编码延迟问题,设计了部分网络编码优化算法。考虑当前链路状况和节点的能量状况,提出了基于部分网络编码的能量约束机会路由协议PNCOR。仿真结果表明,部分网络编码与机会路由相结合,在降低网络延迟、提高网络吞吐量方面均有显著的优势。同传统的路由机制相比,吞吐量提高了22%,投递率提高了23%左右,网络延迟降低25%左右,提高了无线网络传输性能。
基于确定性网络编码的文件分发:以P2P文件分发系统为研究背景,设计了一种新的网络编码文件分发模型及算法DLNCCD。该模型在保证编码解码成功的前提下,采用确定性编码方法降低了网络编码的复杂度。同时,将该编码方法应用在特定的网络拓扑结构上,在保证达到最大的网络编码增益的前提下,有效地解决了拓扑带来的线性相关编码块的问题。仿真结果表明,以该模型建立的文件分发系统同传统的文件分发系统相比吞吐量提高20%左右,平均下载时间节省了20%左右,提高了文件分发系统的性能。
Network coding has reformed the traditional information processing in communication networks. It has lots of advantages, such as increasing the information transmission rate to the maximum network flow rate, improving the network throughput, saving the bandwidth and balancing load. But, the encoding and decoding operation of the nodes in network coding system will bring overhead to the network. Hence, it will be extremely important to reduce the overhead of the network coding operation and optimize the network coding transmission for promoting the practical application of the network coding. This paper studies on the optimization of the network coding and its application in different field based on the network coding theory and optimization mechanism. The research achievements include:
Genetic algorithm based network coding optimization. Aiming at the single objective optimization of the network coding, the paper proposes the network coding optimization model. The paper designs the optimization algorithm MCN for minimization of the coding nodes based on simple genetic algorithm. The simulation results show that this algorithm reduces the network coding nodes. Aiming at the multi-objective optimization of the network coding, after considering the encoding overhead and link overhead, this paper proposes multi-objective optimization algorithm MOONC for network coding based on NSGA-II algorithm. The simulation results show that the algorithm can computer the Pareto optimal solution effectively and reduce the network overhead.
Partial network coding optimization combined with opportunistic routing. The paper proposes the partial network coding optimization algorithm to improve the radio communication energy efficiency and decrease the network coding delays in wireless network. Moreover the energy constraint opportunistic routing protocol PNCOR is also proposed based on the partial network coding after considering the current link status and the energy status of nodes. The simulation results show that the partial network coding has advantages of reducing the network delay and increasing network throughput. It can improve throughput about 22%, delivery rate about 23% and reduce the delay about 25% after combining with the opportunistic routing and improve the transmission performance.
File distribution strategy based on deterministic network coding. Based on the research background of P2P file distribution system, this paper designs a new kind of network coding file distribution model and algorithm DLNCCD. This model could reduce the complexity of network coding through using the deterministic coding method, when it guarantees the success of encoding and decoding. Meanwhile, this network coding method could be applied to the specific network topology, which could ensure the maximum network coding gain and could solve the linearly related coding block problems brought by topology. The simulation and results show that the throughput of the file distribution system with network coding based on this model can improve about 20% and the average download time can reduce about 20% and improve the file distribution performance.
引文
[1] Ahlswede R., Cai N., Li S.-Y. R., and et al., Network Information Flow, IEEE Transactions on Information Theory, 2000, 46(4):1204~1216
[2] Yeung R.W., Li S.-Y. R., Cai N., and et al., Network Coding Theory, Now Publishers Inc, 2006,12~18
[3] Wang D., Zhang Q., Liu J., Partial network coding:Theory and Application in Continuous Sensor Data Collection, The l4th IEEE International Workshop on Quality of Service(IWQoS2006), New Haven,CT, 2006, 93~101
[4] Park J.-S., Lun D. S., Gerla M., and et al., Performance of Network Coding in Ad Hoc Networks, The 25th Military Communica-tions Conf(MILCOM 2006), Washington D C, 2006 ,1~6
[5]Yan Y., Zhang B., Mouftah H.T., and et al., Practical Coding-Aware Mechanism for Opportunistic Routing in Wireless Mesh Networks, IEEE International Conference on Communications ICC 2008, Beijing, 19-23 May 2008, 2871~2876
[6] Kim M., Lima L., Zhao F., and et al., On Counteracting Byzantine Attacks in Network Coded Peer-to-Peer Networks, the IEEE Journal on Selected Areas in Communications, 2010, 28(5): 692~702
[7] Ho T., Leong B., Koetter R. and et al., Byzantine Modification Detection in Multicast Networks Using Randomized Network Coding,The International Symposium on Information Theory (ISIT 2004), Chicago, IL, USA, 2004,144
[8] Chekuri C., Fragouli C., Soljanin E., and et al.,On Average Throughput and Alphabet Size in Network Coding, IEEE Transactions Information Theory, 2006, 52(6): 2410~2424
[9] Wu Y., Chou P.A., Jain K., A Comparison of Network Coding and Tree Packing, International Symposium on Information Theory (ISIT2004), Chicago, 27 June-2 July 2004,143
[10] Li Z., Li B., Network Coding in Undirected Networks, The 38th Annual Conference on Information Science and Systems (CISS 2004), 2004, 257~262
[11] Li S.-Y. R., Yeung R.W., On Convolutional Network Coding, IEEE Information Symposium on Information Theory, Seattle, WA, 2006, 1743~1747
[12] Li S.-Y.R., Yeung R.W., Cai N., Linear Network Coding, IEEE Transactions on Information Theory, 2003, 49(2):371~381
[13]Koetter R., Medard M., An Algebraic Approach to Network Coding, IEEE/ACM Transactions On Networking, 2003, 11(5): 782~795
[14]Koetter R., Medard M., Beyond Routing:An Algebraic Approach to Network Coding, Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2002),2002, 1:122~130
[15] Jaggi S., Sanders P., Chou P.A., and et al., Polynomial Time Algorithms for Multicast Network Code Construction, IEEE Transactions on Information Theory,2005,51(6):1973~1982
[16] Ho T., Medard M., Shi J., and et al., On Randomized Network Coding, 41st Annual Allerton Conference on Communication, Control and Computing, Oct 2003
[17] Ho T., Medard M., Koetter R., and et al., A Random Linear Network Coding Approach to Multicast, IEEE Transactions on Information Theory, 2006,52(10):4413~4430
[18] Katabi D., Katti S., Hu W., and et al.,On Practical Network Coding for Wireless Environments, International Zurich Seminar on Communications,Zurich,2006,84~85
[19] Gkantsidis C., Rodriquez P. R., Network Coding for Large Scale Content Distribution, Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM2005),2005,4: 2235~2245
[20]Avalanche: File swarming with network coding http://research.microsoft.com/pablo/avalanche.aspx
[21] Ma G., Xu Y., Ou K., and et al., How Can Network Coding Help P2P Content Distribution? IEEE International Conference on Communications ICC 2009, Dresden,14-18 June 2009,1~5
[22] Ma G., Xu Y., Lin M., and et al., A Content Distribution System Based on Sparse Linear Network Coding, The 3th Workshop on Network Coding (NETCOD2007), 2007
[23]雷迎春,程实,吴产乐等,应用网络编码的P2P内容分发,计算机研究与发展,2009, 46(1):108~119
[24] Wu Y., Chou P.A., Kung S.-Y., Minimum-energy Multicast in Mobile Ad-hoc Networks using Network Coding, IEEE Transactions on Communications,2005,53(11):1906~1918
[25] Prasad R.,Wu H.,Perkins D.,and et al., Local Topology Assisted XOR Coding in Wireless Mesh Networks, The 28th IEEE International Conference on Distributed Computing Systems (ICDCS2008),Beijing, 2008,156~161
[26] Cui T., Chen L., Ho T.,Energy Efficient Opportunistic Network Coding for Wireless Networks, The 27th IEEE International Conference on Computer Communications (INFOCOM 2008),Phoenix,AZ, 2008, 361~365
[27] Cai N., Yeung R.W., Secure Network Coding, The IEEE International Symposium on Information Theory (ISIT2002), 2002,323
[28] Feldman J., Malkin T., Servedio R.A., and et al., On the Capacity of Secure Network Coding, The 42th Annual Allerton Conference on Communication,Control,and Computing, USA, 2004
[29]樊平毅,网络信息论,北京:清华大学出版社,2009,117~123
[30] Snaders P., Egner S., Tolhuizen L.,Polynomial Time Algorithms for Network Information Flow,The 15th ACM Symposium on Parallel Algorithms and Architecture (SPAA2003), San Diego,California,USA,2003, 286~293 [3l] Fragouli C., Soljanin E., Subtree Decomposition for Network Coding, International Symposium on Information Theory (ISIT 2004), 2004,145
[32] Fragouli C., Soljanin E., Shokrollahi A., Network Coding as A Coloring Problem, IEEE Annual Conference on Information Sciences and Systems, Princeton,NJ,USA, 2004,1~6
[33] Fragouli C., Soljanin E., Information Flow Decomposition for Network Coding, IEEE Transactions on Information Theory, 2006, 52(3): 829~848
[34] Fragouli C., Soljanin E., Decentralized Network Coding, 2004 IEEE Information Theory Workshop, 24-29 Oct 2004, 310~314
[35] Zhang J., Fan P., On Network Coding in Wireless Ad-hoc Networks, International Journal of Ad Hoc and Ubiquitous Computing , 2007 2(3) :140 ~ 148
[36] Ho T., Koetter R., Medard M., and et al.,The Benefits of Coding Over Routing in a Randomized Setting, IEEE International Symposium on Information Theory(ISIT’04),Chicago,IL,27 June-2 July,2004,442~446
[37] Li Z., Li B., Jiang D., and et al.,On Achieving Optimal Throughput With Network Coding, IEEE INFOCOM 2005,Miami: IEEE Computer Society, 2005,2184~2194
[38] Li Z., Li B., Efficient and Distributed Computation of Maximum Multicast Rates, IEEE INFOCOM 2005, Miami:IEEE Computer Society, 2005,1618~1628
[39] Widmer J., Fragouli C., Boudec J.-Y. L., Low-Complexity Energy-Efficient Broadcasting in Wireless Ad Hoc Networks Using Network Coding,NETCOD 2005, Workshops, Apr, 2005
[40] Deb S., Effros M., Ho T., and et al, Network Coding for Wireless Applications: A Brief Tutorial, London, UK, May, 2005
[41] Hamra A.A., Barakat C., Turletti T., Network Coding for Wireless Mesh Networks: A Case Study, IEEE International Symposium on a World of Wireless,Mobile and Multimedia Networks(WoWMoM), USA, June 26-29 2006,109~114
[42] Lu F., Geng L., Chia L.-T., and et al, Secure Multi-path in Sensor Networks, The 5th International Conference on Embedded Networked Sensor Systems (SenSys’07), Sydney, Australia, 6-9 November 2007
[43] Jaggi S., Langberg M., Katti S., and et al., Resilient Network Coding in The Presence of Byzantine Adversaries, The 26th Annual IEEE Conference on Computer Communications (INFOCOM 2007), Anchorage, 2007
[44] Jaggi S., Langberg M., Ho T., and et al., Correction of Adversarial Errors in Networks, The 2005 Symp on Information Theory and its Applications, Adelaide, Australia, 2005
[45] Fragouli C., Soljanin E., A Connection Between Network Coding and Convolutional Codes, IEEE International Conference on Communications, 20-24 June 2004,2:661~662
[46]黄政,王新,网络编码中的优化问题研究,软件学报,2009,20(5):1349~1361
[47] Langberg M., Sprintson A., Bruck J., The Encoding Complexity of Network Coding, IEEE Transactions on Information Theory, 2006, 52(6):2386~2397
[48] Bhattad K., Ratnakar N., Koetter R., and et al., Minimal Network Coding for Multicast, IEEE International Symposium on Information Theory (ISIT 2005), Adelaide,SA,4-9 Sept,2005,1730~1734
[49] Kim M., Ahn C.W., Medard M., and et al., On Minimizing Network Coding Resources: An Evolutionary Approach, In: Proc of the NETCOD 2006, 2006
[50] Kim M., Medard M., Aggarwal V., and et al.,Evolutionary Approaches to Minimizing Network Coding Resources,The 26th IEEE International Conference on Computer Communications(INFOCOM 2007),Anchorage,AK,6-12 May, 2007, 1991~1999
[51] Kim M., Medard M., O’Reilly U.-M., and et al.,An Evolutionary Approach to Inter-Session Network Coding, IEEE INFOCOM 2009, 19~25 April,2009,450~458
[52]邓亮,赵进,王新,基于遗传算法的网络编码优化,软件学报,2009,20(8):2269~2279
[53]马冠骏,许胤龙,林明宏等,基于网络编码的P 2 P内容分发性能分析,中国科学技术大学学报,2006,36(11):1237~1240
[54] Lun D.S.,Ratnakar N.,Medard M., and et al., Minimum-Cost Multicast over Coded Paeket Networks, IEEE Transactions on Information Theory, June, 2006,52(6):1~17
[55] Lun D.S.,Ratnakar N., Koetter R., and et al., Achieving Minimum-cost Multicast: A Decentralized Approach Based on Network Coding,IEEE INFOCOM 2005, Miami,FL,Mar 2005,1607~1617
[56]王小平,曹立明,遗传算法—理论、应用与软件实现,西安交通大学出版社,2006,7~15
[57]杨启文,蒋静平,张国宏,遗传算法优化速度的改进,软件学报, 2001.12(2),270~275
[58] http://www.cs.bu.edu/brite
[59] Kim M., Medard M., Aggarwal V., and et al., On the Coding-Link Cost Tradeoff in Multicast Network Coding, Military Communications Conference(MILCOM2007),Orlando,FL,USA, 29-31 Oct 2007, 1~7
[60]邓亮,赵进,王新,网络编码下的编码开销-链路开销联合优化,计算机研究与发展,2010,47(3):390~397
[61] Fonseca C.M., Fleming P.J., Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization, The 5th International Conference on Genetic Algorithms, San Francisco, CA,USA,1993,416~423
[62] Deb K., Pratap A., Agrawal S., and et al., A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, Apr 2002, 6(2):182~197
[63]崔逊学,多目标进化算法及其应用,北京:国防工业出版社,2006:6~10
[64] Wu Y., Kung S.-Y., Reduced Complexity Network Coding for Multicasting Over Ad Hoc Networks, IEEE International Conference on Acoustics, Speech,and Signal Processing (ICASSP2005),18-23 March 2005, 3:501~504
[65] Yuan J., Li Z., Yu W., and et al., A Cross-Layer Optimization Framework for Multicast in Multi-hop Wireless Networks, First International Conference on Wireless Internet, 10-14 July 2005, 47~54
[66] Wu Y., Chou P. A., Zhang Q., and et al., Network Planning in Wireless Ad Hoc Networks: A Cross-layer Approach, IEEE Journal on Selected Areas in Communication, 2005, 23(1):136~150
[67] Wu Y., Chou P. A., Kung S.-Y., Minimum Energy Multicast in Mobile Ad Hoc Networks Using Network Coding, IEEE Transactions on Communications, 2005, 53(11): 1906~1918
[68] Lun D.S., Medard M.,Kotter R., Efficient Operation of Wireless Packet Networks Using Network Coding, International Workshop on Convergent Technologies (IWCT2005), 2005
[69] Lun D.S., Medard M., Koetter R., On Coding for Reliable Communication Over Packet Networks,42nd Annual Allerton Conference on Communication, Control and Computing, 2004
[70] Lun D.S., Medard M., Koetter R., and et al., Further Results on Coding for Reliable Communication Over Packet Networks, International Symposium on Information Theory (ISIT 2005), Adelaide,SA,4-9 Sept 2005, 1848~1852
[71] Ahluwalia A.S., Modiano E.H., On The Complexity and Distributed Construction of Energy Efficient Broadcast Trees in Wireless Ad Hoc Networks, IEEE Transactions on Wireless Communications,2005,4(5): 2136~2147
[72] Liang W., Constructing Minimum Energy Broadcast Trees in Wireless Ad Hoc Networks, 3rd ACM International Symposium on Mobile Ad Hoc Networking&Computing, 2002, 112~122
[73] Wieselthier J.E., Nguyen G.D., Energy Efficient Broadcast and Multicast Trees in Wireless Networks, Mobile Networks and Applications, 2002, 7(6):481~ 492
[74] Widmer J.,Fragouli C.,Le Boudec J.-Y.,Low-Complexity Energy Efficient Broadcasting in Wireless Ad Hoc Networks Using Network Coding, First Workshop on Network Coding, Theory, and Applications(NETCOD 2005), Riva del Garda, Italy,2005
[75] Chachulski S., Jennings M., Katti S., and et al., Trading Structure for Randomness in Wireless Opportunistic Routing, In ACM SIGCOMM, Kyoto, Japan, 2007, 169~180
[76]Biswas S., Morris R., Opportunistic Routing in Multi-Hop Wireless Networks, SIGCOMM 2005, 2005, 34(1),69~74
[77] Wang Y., Garcia-Luna-Aceves J.J.,Collision Avoidance in Multihop Ad Hoc Networks, The 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS’02), TX, USA, 2002,145~154
[78] Wang D., Zhang Q., Liu J., Partial Network Coding: Theory and Application for Continuous Sensor Data Collection, The 14th lEEE International Workshop on Quality of Service (IWQoS 2006), 2006,93~101
[79]霍广城,移动无线传感器网络中机会主义路由研究:[硕士学位论文],北京;国防科技大学,2008
[80] Cooper C., On The Distribution of Rank of A Random Matrix Over a Finite Field, Random Structures and Algorithms, 2000,17(3-4):197~212
[81] Le J., Lui J.C.S.,Chiu D. M., How Many Packets Can We Encode? An Analysis of Practical Wireless Network Coding, INFOCOM 2008, Phoenix, AZ,13-18 April,2008,371~375
[82] Katti S., Katabi D., Hu W., and et al., The Importance of Being Opportunistic: Practical Network coding for Wireless Environments, INFOCOM 2007, 2007,569~578
[83] Lun D.S., Medard M.,Koetter R., Efficient Operation of Wireless Packet Networks Using Network Coding, International Workshop on Convergent Technologies (IWCT), 2005
[84] Katti S., Rahul H., Hu W., and et al., XORs in The Air: Practical Wireless Network Coding, IEEE/ACM Transactions on Networking, 2008, 16(3):497~510
[85] Karagiannis T., Broido A.,Faloutsos M.,and et al., Transport Layer Identification of P2P Traffic, The 4th ACM SIGCOMM conference on Internet Measurement,2004,121~134
[86] Karagiannis T., Broido A., Brownlee N., and et al., Is P2P Dying or Just Hiding?,IEEE Global Telecommunications Conference,GLOBECOM 2004,29 Nov-3 Dec,2004,3:1532~1538
[87]Parker A., The True Picture of Peer-to-Peer File Sharing, 2004, http://www.cachelogic.com
[88] Legout A., Urvoy-Keller G., Michiardi P., Rarest First And Choke Algorithms Are Enough, The 6th ACM SIGCOMM conference on Internet Measurement, 2006, 203~216
[89] Wang M., Li B., R2:Random Push With Random Network Coding in Live Peer-to-Peer Streaming, IEEE Journal on Selected Areas in Communications, Special Issue on Advances in Peer-to-Peer Streaming Systems, December 2007,25(9):1655~1666
[90] Wang M., Li B., Network Coding in Live Peer-to-Peer Streaming, IEEE Transactions on Multimedia, Special Issue on Content Storage and Delivery in Peer-to-Peer Networks, December 2007, 9(8), 1554~1567
[91] Lee S., Lee U., Lee K., and et al., Content Distribution in VANETs Using Network Coding: The Effect of Disk I/O and Processing O/H, The 5th Annual IEEE Communications Society Sensor, Mesh and Ad Hoc Communications and Networks SECON 2008, California, USA,16-20 June 2008, 117~125
[92]Lee U., Lee S., Lee K., and et al., Understanding Processing Overheads of Network Coding Based Content Distribution in VANETs, http://netlab.cs.ucla.edu/wiki/files/jsac-nc.pdf
[93] Lee U., Park J.-S., Lee S.,and et al., Efficient Peer-to-peer File Sharing using Network Coding in MANET, http://www.cs.ucla.edu/~shlee/papers/CodeTorrentJCN.pdf
[94] Wang M., Li B., How Practical is Network Coding?, The 14th IEEE International Workshop on Quality of Service(IWQOS 2006),June, 2006,274~278
[95] Chiu D.M., Yeung R.W., Huang J. and et al., Can Network Coding Help in P2P Networks?, The 4th International Symposium on Moding and Optimization in Mobile, Ad Hoc and Wireless Networks, 03-06 April,2006,1~5
[96]马冠骏,基于网络编码的P2P文件分发的研究:[博士学位论文],合肥;中国科学技术大学,2009
[97] Niu D., Li B., On the Resilience-Complexity Tradeoff of Network Coding in Dynamic P2P Networks, 2007 Fifteenth IEEE International Workshop on Quality of Service, Evanston,IL,21-22 June 2007, 38~46
[98] Alouf S., Dandoush A., Nain P., Performance Analysis of Peer-to-Peer Storage Systems, 20th International Teletraffic Conference on Managing Traffic Performance in Converged Networks, 2007, 642~653
[99] Ngai C.K., Yeung R.W., Network Coding Gain of Combination Networks, IEEE Information Theory Workshop, Oct. 2004, 283~287
[100]Yang M., Yang Y., Peer-to-Peer File Sharing Based on Network Coding, The 28th International Conference on Distributed Computing System, Beijing, 17-20 June 2008, 168~175
[101]Gkantsidis C., Miller J., Rodriguez P., Anatomy of a P2P Content Distribution System With Network Coding, The 5th International Workshop on Peer-to-Peer Systems (IPTPS 2006), 2006
[102] Xu J., Zhao J., Wang X., and et al.,Swifter:Chunked Network Coding for Peer-to-Peer Content Distribution, IEEE International Conference on Communications (ICC 2008), Beijing,China, 19-23 May, 2008, 5603~5608
[103] Wang M., Li B., Lava:A Reality Check of Network Coding in Peer-to-Peer Live Streaming, IEEE INFOCOM, Anchorage, Alaska, USA, 2007,1082~1090
[104] Eger K., Hosfeld T., Binzenhofer A.,and et al., Efficient Simulation of Large-Scale P2P Networks: Packet-level vs Flow-level Simulations, 2nd Workshop on the Use of P2P, GRID and Agents for the Development of Content Networks (UPGRADE’07), Monterey Bay, USA,June, 2007
[105]陶少国,面向数据分发的网络编码研究:[博士学位论文],武汉;华中科技大学,2008