无线网络编码的关键问题与技术研究
|
摘要
网络编码是21世纪以来信息技术领域的一项重大成果。它打破了传统路由器只能简单地存储转发这一常规。通过将多个数据包组合在一起,并利用数据包之间的相关性来解码,网络编码巧妙解决了有向网络中组播最大流等经典的理论难题,大大提高了网络容量和资源的利用效率,并在优化网络管理和提高网络的安全性等诸多方面都具有重要价值。无线信道的广播特性使得网络编码在无线网络中有很大的应用潜力。作为一个新兴的研究领域,无线网络编码面临着无线终端的移动性、无线信道的复杂多变和终端资源受限等许多挑战,有很多关键问题需要解决。本文立足研究无线网络编码的若干关键理论和技术问题,完善现有的理论框架,利用网络编码思想来改善现有无线网络的性能,并为其实用化打下基础。
在基础理论上,建立了一种无线网络的随机图模型,并给出基于无线网络编码的组播最大流路由算法,编码节点选择方法及优化的输出边容量分配策略,继而给出无线网络编码的完整实现框架。在此基础上,从理论上研究了端到端和组播的最大流容量分布,并量化分析无线网络编码的增益和实现复杂度。本文还研究了无向图中的网络编码,首次发现了信息流碰撞现象。此外针对网络编码特有的排队现象和等待延迟,本文从理论上量化分析了延时与传输效率等因素的关系,并提出相应的优化调度策略。
在工程方面,本文将网络编码思想与传统的交叉层技术结合,以改善网络性能。第一项工作是基于网络编码的无线信号干扰消除技术,该技术利用已知的数据包内容,在无需附加同步和功率控制的条件下可有效消除信号干扰,从而增强网络的空间复用性,提高传输效率。另一项工作提出一种乘积码形式的分布式网络纠错码,可显著改善组播的误码性能。
最后,为了让相关技术具有实用性,本文还探讨了网络编码在应用中需解决的实际问题,包括差错控制与重传、延时和QoS保证、及与现有系统的兼容等等,并给出相关的解决方案。基于无线局域网协议,设计并实现了无线网络编码硬件实验平台,解决方案的可行性通过实验得以验证。
Network Coding is a momentous achievement of information technology in the 21st century. It breaks the convention that a router can only simply store and forward messages. Through combining multiple packets together and using the correlation among packets for decoding, network coding solves some classical theoretical problems such as the maximum multicast flow in directed networks in a very smart way, greatly increases the network capacity and the utilizing efficiency of resources, and has remarkable significance in enhancing the robustness of network management and data security. The broadcast nature of wireless channel endows network coding with extraordinary merit and potential in wireless networks. As a newly emerging technology, wireless network coding is faced with many challenges such as the mobility of wireless node, the variance of channel and limited resources of wireless equipments, and there are a lot of key questions to answer. This work aims at solving some key theoretical and technical problems of wireless network coding, completing the current theory framework, and using the idea of network coding to improve the performance of wireless networks, which lays the foundation for its practice.
For the basic theory, the random graph model will be established for wireless networks, and put forward the strategies of maximum flow multicast routing, coding node selection as well as an optimized capacity allocation scheme on output links based on network coding, and further propose the whole framework of wireless network coding. Based on these works, we will study the distribution of the maximum flow for both end-to-end and multicast communication theoretically, and analyze the benefit and complexity of wireless network coding quantitatively. Network Coding in undirected networks will also be studied, with the original discovery on the collision phenomenon of information flows. Moreover, the relation between delay and efficiency will be investigated to the queuing and waiting delay that is peculiar to network coding, and optimized scheduling algorithms will be given.
For engineering, we combine network coding with traditional cross-layer techniques to improve the network performance. The first job is an interference eliminating technique based on network coding. Through the content of packets that is known to the receiver, this technique can effectively eliminate the interference without synchronization and power control, thus increase the space reusing and the transmission efficiency is increased. The other job is distributed network error correction code in the form of product code, which can reduce the bit error rate of multicast.
Finally, to make the concerning techniques practical, we will discuss the issues to deal with when network coding is implemented, such as error control, retransmission, delay, QoS guarantee and its compatibility with current systems, and present the corresponding solutions. The feasibility of these solutions is proved by the hardware experimental bed of wireless network coding designed in this work.
在基础理论上,建立了一种无线网络的随机图模型,并给出基于无线网络编码的组播最大流路由算法,编码节点选择方法及优化的输出边容量分配策略,继而给出无线网络编码的完整实现框架。在此基础上,从理论上研究了端到端和组播的最大流容量分布,并量化分析无线网络编码的增益和实现复杂度。本文还研究了无向图中的网络编码,首次发现了信息流碰撞现象。此外针对网络编码特有的排队现象和等待延迟,本文从理论上量化分析了延时与传输效率等因素的关系,并提出相应的优化调度策略。
在工程方面,本文将网络编码思想与传统的交叉层技术结合,以改善网络性能。第一项工作是基于网络编码的无线信号干扰消除技术,该技术利用已知的数据包内容,在无需附加同步和功率控制的条件下可有效消除信号干扰,从而增强网络的空间复用性,提高传输效率。另一项工作提出一种乘积码形式的分布式网络纠错码,可显著改善组播的误码性能。
最后,为了让相关技术具有实用性,本文还探讨了网络编码在应用中需解决的实际问题,包括差错控制与重传、延时和QoS保证、及与现有系统的兼容等等,并给出相关的解决方案。基于无线局域网协议,设计并实现了无线网络编码硬件实验平台,解决方案的可行性通过实验得以验证。
Network Coding is a momentous achievement of information technology in the 21st century. It breaks the convention that a router can only simply store and forward messages. Through combining multiple packets together and using the correlation among packets for decoding, network coding solves some classical theoretical problems such as the maximum multicast flow in directed networks in a very smart way, greatly increases the network capacity and the utilizing efficiency of resources, and has remarkable significance in enhancing the robustness of network management and data security. The broadcast nature of wireless channel endows network coding with extraordinary merit and potential in wireless networks. As a newly emerging technology, wireless network coding is faced with many challenges such as the mobility of wireless node, the variance of channel and limited resources of wireless equipments, and there are a lot of key questions to answer. This work aims at solving some key theoretical and technical problems of wireless network coding, completing the current theory framework, and using the idea of network coding to improve the performance of wireless networks, which lays the foundation for its practice.
For the basic theory, the random graph model will be established for wireless networks, and put forward the strategies of maximum flow multicast routing, coding node selection as well as an optimized capacity allocation scheme on output links based on network coding, and further propose the whole framework of wireless network coding. Based on these works, we will study the distribution of the maximum flow for both end-to-end and multicast communication theoretically, and analyze the benefit and complexity of wireless network coding quantitatively. Network Coding in undirected networks will also be studied, with the original discovery on the collision phenomenon of information flows. Moreover, the relation between delay and efficiency will be investigated to the queuing and waiting delay that is peculiar to network coding, and optimized scheduling algorithms will be given.
For engineering, we combine network coding with traditional cross-layer techniques to improve the network performance. The first job is an interference eliminating technique based on network coding. Through the content of packets that is known to the receiver, this technique can effectively eliminate the interference without synchronization and power control, thus increase the space reusing and the transmission efficiency is increased. The other job is distributed network error correction code in the form of product code, which can reduce the bit error rate of multicast.
Finally, to make the concerning techniques practical, we will discuss the issues to deal with when network coding is implemented, such as error control, retransmission, delay, QoS guarantee and its compatibility with current systems, and present the corresponding solutions. The feasibility of these solutions is proved by the hardware experimental bed of wireless network coding designed in this work.
引文
[1] Ahlswede R, Cai N, Li S, and Yeung R. Network information flow. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216.
[2] Koetter R, Médard R. Beyond Routing: An algebraic approach to network coding. Proceedings of IEEE INFOCOM, 2002:122-130.
[3] Koetter R, Médard R. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 2003, 11(5):782-795.
[4] Li S, Yeung R, Cai N. Linear network coding. IEEE Transactions on Information Theory, 2003, 49(2):371-381.
[5] Harvey N, Kleinbergy R D, Lehman R. Comparing network coding with multicommodity flow for the k-pairs communication problem. MIT report, 2004
[6] Larsson P. Analysis of multi-user ARQ with multiple unicast flows under non-iid reception probabilities. In Proc. 63rd IEEE Wireless Communications and Networking Conference (WCNC2007), 2007:348-388.
[7] Tse D, Hanly S. Linear multiuser receivers: effective interference, effective bandwidth and user capacity. IEEE Transactions on Information Theory, 1999, 45(2):641-657.
[8] AJ Goldsmith, PP Varaiya,“Capacity, Mutual Information, and Coding for Finite-state Markov channels,”IEEE Transactions on Information Theory, 1996.
[9] P. Gupta and P. R. Kumar,“The Capacity of Wireless Networks,”IEEE Trans. Inform. Theory, vol. 46, pp. 388–404, Mar. 2000.
[10] Liang-Liang Xie and P. R. Kumar,“Network Information Theory for Wireless Communication: Scaling Laws and Optimal Operation,”IEEE Trans. Inform. Theory, vol. 50, pp. 748–767, May. 2004.
[11] A. Jovicic, P. Wiswanath and S. R. Kulkarni,“Upper Bounds to Transport Capacity of Wireless Networks,”IEEE Trans. Inform. Theory, vol. 50, pp. 2555–2565, Nov. 2004.
[12] Leveque O, Telatar I. Information theoretic upper bounds on the capacity of the large extended ad-hoc wireless networks. IEEE Transactions on Information Theory, 2005, 51(3):858–865.
[13] Deb S, Médard M, Choute C. Algebraic gossip: a network coding approach to optimal multiple rumor mongering. IEEE/ACM Transactions on Networking, 2006, 52(6):2486-2507.
[14] Deb S, Médard M, Choute C. On random network coding based information dissemination. International Symposium on Information Theory, 2005:278-282.
[15] Jaggi S, Sanders P, Chou P, Effros M, Egner S, Jain K, Tolhuizen L. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, 2003, 51(6):1973-1982.
[16] Fragouli C, Soljanin E. Information flow decomposition for network coding. IEEE Transactions on Information Theory, 2006, 52(3):829-848.
[17] Langberg M, Sprintson A, Bruck J. The encoding complexity of network coding. Proceedings of ISIT, 2005:1987-1991.
[18] Fan P. On the encoding complexity of network coding for acyclic multicast networks. Technical report, Department of Electronic Engineering, Tsinghua University, 2004
[19] Ho T, Médard M, Effros M, Karger D. Toward a random operation of networks. submitted to IEEE Transactions on Information Theory, 2004.
[20] Ho T, Médard M, Effros M, Karger D. On randomized network coding. In Proceedings 41st Allerton Annual Conference on Communication, Control and Computing, 2003.
[21] Hamra A, Barakat C, Turletti T. Network Coding for Wireless Mesh Networks: A Case Study. Proc of IEEE WoWMoM 2006. June 2006.
[22] Wang J, Yang G, Lin X, He Z, Lin J. Random linear coding for file sharing in upload-limited wireless packet networks. IEEE 66th Vehicular Technology Conference, 2007(3):235-239.
[23] Yang S, Yeung R. Characterizations of network error correction/detection and erasure Correction. Network coding workshop, 2007.
[24] Yeung R, Cai N. Network error correction, part I: basic concepts and upper bounds. Communications in Information and Systems, 2006, 6(1): 19-36.
[25] Cai N, Yeung R. Network error correction, part II: lower bounds. Communications in Information and Systems, 2006, 6(1): 37-54.
[26] Shokrollahi. Raptor codes. IEEE Transactions on Information Theory, 2006, 52(6):2551-2567.
[27] MacKay D. Fountain codes. IEE Proceedings on Communications, 2005, 152(6):1062-1068.
[28] Yan X, Neely M, Zhang Z. Multicasting in time-varying wireless networks: cross-layer dynamic resource allocation. Proceedings of IEEE International Symposium on Information Theory (ISIT), 2007:2721-2725.
[29] Silva D, Kschischang F. Rank-metric codes for priority encoding transmission with network coding. IEEE Canadian Workshop on Information Theory, 2007:81-84.
[30] Chen Y, Kishore S, Li J. Wireless diversity through network coding. IEEE WCNC, 2006:1681-1686.
[31]李伟.无线自组织网络中信传输关键技术的研究[博士学位论文].北京:清华大学电子工程系,2009.
[32] Applications of network coding in LTE-A. 3GPP标准提案(R1-084130),2008.
[33] Ramamoorthy A, Shi J, Wesel R. On the capacity of network coding for random networks. IEEE Transactions on Information Theory, 2005, 51(8):2878-2885.
[34]谢政,李建平.网络算法与复杂性理论.北京:科学出版社,1995年5月.
[35]王树禾.图论.北京:科学出版社,2004年.
[36] Dieter Jungnickel. Graphs, Networks and Algorithms. Springer, 1999.
[37] Zhang J, Fan P. On network coding in wireless ad-hoc networks. 2nd International Conference on Mobile Technology, Applications and Systems, 2005.
[38] Zhang J, Fan P, Letaief K. Network coding with low complexity in wireless ad-hoc multicast networks. IEEE International Conference on Communications, 2006:3699-3704.
[39] Ma Y, Li W, Fan P, Letaief K, Liu X. On the characteristics of queuing and scheduling at encoding nodes for network coding. International Journal of Communication Systems, 2009, 22(6):755-772.
[40] Sagduyu Y, Ephremides A. Some optimization trade-offs in wireless network coding. Proceedings of Conference on Information Sciences and Systems, 2007:6-11.
[41]陆大纟金.随机过程及其应用.北京:清华大学出版社,1986.
[42] Hardy G, Wnight E. An introduction to the theory of numbers. Chapter 23, Oxford University Press, 1979.
[43]陈鑫林.现代通信中的排队论.北京:电子工业出版社,1999.
[44] Wolff R. Poisson arrivals see time averages. Operations Research, 1982, 30(2):223-231.
[45] Toh C. Ad hoc mobile wireless networks: protocols and systems. Prentice Hall, 2002.
[46] Boppana S, Shea J. Overlapped transmission in wireless ad-hoc networks. Proceedings of ICCCAS06, 2006:1309-1314.
[47] Zhang S, Liew S, Lam P. Physical-layer network coding. Proceedings of the Annual International Conference on Mobile Computing and Networking, 2006:358-365.
[48] Katti S, Katabi D. Embracing wireless interference: analog network coding. ACM SIGCOMM, 2007:397-408.
[49] Rappaport T. Wireless communications: principles and practice. Second Edition, Prentice Hall, 2002.
[50] Broersen P. Automatic autocorrelation and spectral analysis. Springer, 2006.
[51] Proakis J. Digital communications. Fourth Edition, McGraw-Hill College, 2000.
[52] Berrou C, Glavieux A, Thitimajshima P. Near Shannon limit error-correcting coding and decoding: Turbocodes. IEEE International Conference on Communications,1993:1064-1070.
[53] Burr A. Modulation and coding for wireless communications. Prentice Hall, 2001.
[54] Vucetic B, Yuan J. Turbo codes: principles and applications. London, Kluwer Academic Publishers, 2000.
[55] Chase D. A class of algorithms for decoding block codes with measurement information. IEEE Transactions on Information Theory, 1972, 18(1):170-182.
[56]马祎.网络编码的排队与调度分析[硕士学位论文].北京:清华大学电子工程系,2007.
[57] Zhu Y, Li B, Guo J. Multicast with network coding in application-layer overlay networks. IEEE Journal on Selected Areas in Communications, 2004:104-120.
[58] Lehman A, Lehman E. Complexity Classification of Network Information Flow Problems. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2004:135-143.
[59] Goldsmith A. Wireless communications. New York: Cambridge University Press, 2005.
[60] Abramowitz M,Stegun A I. Pocketbook of Mathematical Functions. Deutsch: Verlag Harri Deutsch, 1984.
[61] Shannon C E. A mathematical theory of communication. The Bell System Technical Journal, 1948, 27:379–423 and 623–656.
[62] Gallager R G. Information theory and reliable communication. New York: Wiley, January, 1968.
[63] Bollobas B. Modern graph theory. Springer, August, 2002.
[64] Gupta P, Kumar P R. The capacity of wireless networks. IEEE Transactions on Information Theory, 2000, 46(2): 388–404.
[65] Kendall D G. On the generalized“Birth-and-Death”process. The Annals of Mathematical Statistics, 1948, 19(1):1–15.
[66] Kendall D G. Some problems in the theory of queues. Journal of the Royal Statistical Society, 1951, 113(2):151–185.
[67] Lun S D, Medard M, Koetter R. Efficient operation of wireless packet networks using network coding. Proceedings of International Workshop on Convergent Technologies (IWCT), 2005.
[68] Dong N, Tuan T, Thinh N, et al. Wireless broadcast using network coding. IEEE Transactions on Vehicular Technology, 2009, 58(2):914 - 925.
[69] Abramowitz M, Stegun A I. Pocketbook of mathematical functions. Deutsch: Verlag Harri Deutsch, 1984.
[70] Cooper R B. Introduction to queueing theory. North Holland, 1981.
[71] Kleinrock L. Queueing systems (volume 1: theory). John Wiley & Sons, Inc., January, 1975.
[72] Wu Y, Chou P A, Zhang Q. Network planning in wireless ad hoc networks: a cross-layer approach. IEEE Journal on Selected Areas in Communications, 2005, 23(1):136–150.
[73] Wang H, Fan P, Letaief K B. Maximum flow and network capacity of network coding for ad hoc networks. IEEE Transactions on Wireless Communications, 2007, 6(12):4193-4198.
[74] Ho T, leong B, Koetter R, et al. Distributed asynchronous algorithms for multicast network coding. Proceedings of the First Workshop on Network Coding, Theory, and Applications, 2005.
[75] Ho T, Medard M, Koetter R. An information-theoretic view of network management. IEEE Transactions on Information Theory, 2005, 51(4):1295–1312.
[76] Cai K, Fan P. An algebraic approach to link failure of network coding. IEEE Transactions on Information Theory, 2007, 53(2):775-779.
[77] Liu H C, Xue F. Network coding for two-way relaying: rate region, sum rate and opportunistic scheduling. Proceedings of IEEE ICC, 2008: 1044-1049.
[78] Diestel R. Graph theory. Springer, July, 2005.
[79] Erlang A K. Solutions of some problems in the theory of probability of significance in automatic telephone exchanges. The Post Office Electrical Engineers’Journal, 1918, 10:189–197.
[80] Takagi H. Queueing analysis: a foundation of performance evaluation. North Holland, 1991.
[81]卢开澄.组合数学.清华大学出版社, 2006.
[82]王金龙,王呈贵,吴启晖,等.Ad Hoc移动无线网络.北京:国防工业出版社,2003.
[83]陈林星,曾曦,曹毅.移动Ad Hoc网络—自组织分组无线网络技术.北京:电子工业出版社,2006.
[84] IEEE 802.11, the working group setting the standards for wireless LANs. http://www.ieee802.org/11/.
[85] Koffman I, Roman V. Broadban wireless access solution based on OFDM access in IEEE 802.16. IEEE Commun. Mag., 2002, 40(4):96-103.
[86] Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands. IEEE Std. 802.16e, IEEE 2005.
[87]曹志刚,钱亚生.现代通信原理.北京:清华大学出版社,1992.
[88] Tolga M, Ghrayeb A. Coding for MIMO communication systems. Wiley, 2007.
[89] Joing analog network coding and relay. 3GPP标准提案(R1-084133),2008.
[90] Network coding relay and its chase combining. 3GPP标准提案(R1-092161),2008.
[91] Woldegebreal D, Holger K. Network-coding-based cooperative transmission in wireless sensor networks: Diversity-multiplexing tradeoff and coverage area extension. Wireless Sensor Networks - 5th European Conference, 2008:141-155.
[92] Larsson P, Johansson N. Multi-User ARQ. IEEE 63rd Vehicular Technology Conference, 2006:2052-2057.
[93] Sagduyu Y, Guo D, Randall B. On the delay and throughput of digital and analog network coding for wireless broadcast. The 42nd Annual Conference on Information Sciences and Systems, 2008:534-539.
[94] Li K, Wang X. Cross-layer design of wireless mesh networks with network coding. IEEE Transactions on Mobile Computing, 2008, 7(11):1363-1373.
[95] Kim T, Lim H, Hou J. Understanding and improving the spatial reuse in multihop wireless networks. IEEE Transactions on Mobile Computing, 2008, 7(10):1200-1212.
[96] Subramanian A, Andrew T. A simple algebraic formulation for the scalar linear network coding problem. 46th Annual Allerton Conference on Communication, Control, and Computing, 2008:177-184.
[97] Eryilmaz A, Ozdaglar A, Medard M, Ahmed E. On the delay and throughput gains of coding in unreliable networks. IEEE Transactions on Information Theory, 2008, 54(12):5511-5524.
[98] Ding Z, Ratnarajah T, Leung K. On the study of network coded AF transmission protocol for wireless multiple access channels. IEEE Transactions on Wireless Communications, 2008, 7(11):4568-4574.
[99] Kotter R, Kschischang F. Coding for errors and erasures in random network coding. IEEE Transactions on Information Theory, 2008, 54(8):3579-3591.
[100] Price J, Javidi T. Network coding games with unicast flows. IEEE Journal on Selected Areas in Communications, 2008, 26(7):1302-1316.
[101] Ying L, Yang S, Srikant R. Optimal delay-throughput tradeoffs in mobile Ad Hoc networks. IEEE Transactions on Information Theory, 2008, 54(9):4119-4143.
[2] Koetter R, Médard R. Beyond Routing: An algebraic approach to network coding. Proceedings of IEEE INFOCOM, 2002:122-130.
[3] Koetter R, Médard R. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 2003, 11(5):782-795.
[4] Li S, Yeung R, Cai N. Linear network coding. IEEE Transactions on Information Theory, 2003, 49(2):371-381.
[5] Harvey N, Kleinbergy R D, Lehman R. Comparing network coding with multicommodity flow for the k-pairs communication problem. MIT report, 2004
[6] Larsson P. Analysis of multi-user ARQ with multiple unicast flows under non-iid reception probabilities. In Proc. 63rd IEEE Wireless Communications and Networking Conference (WCNC2007), 2007:348-388.
[7] Tse D, Hanly S. Linear multiuser receivers: effective interference, effective bandwidth and user capacity. IEEE Transactions on Information Theory, 1999, 45(2):641-657.
[8] AJ Goldsmith, PP Varaiya,“Capacity, Mutual Information, and Coding for Finite-state Markov channels,”IEEE Transactions on Information Theory, 1996.
[9] P. Gupta and P. R. Kumar,“The Capacity of Wireless Networks,”IEEE Trans. Inform. Theory, vol. 46, pp. 388–404, Mar. 2000.
[10] Liang-Liang Xie and P. R. Kumar,“Network Information Theory for Wireless Communication: Scaling Laws and Optimal Operation,”IEEE Trans. Inform. Theory, vol. 50, pp. 748–767, May. 2004.
[11] A. Jovicic, P. Wiswanath and S. R. Kulkarni,“Upper Bounds to Transport Capacity of Wireless Networks,”IEEE Trans. Inform. Theory, vol. 50, pp. 2555–2565, Nov. 2004.
[12] Leveque O, Telatar I. Information theoretic upper bounds on the capacity of the large extended ad-hoc wireless networks. IEEE Transactions on Information Theory, 2005, 51(3):858–865.
[13] Deb S, Médard M, Choute C. Algebraic gossip: a network coding approach to optimal multiple rumor mongering. IEEE/ACM Transactions on Networking, 2006, 52(6):2486-2507.
[14] Deb S, Médard M, Choute C. On random network coding based information dissemination. International Symposium on Information Theory, 2005:278-282.
[15] Jaggi S, Sanders P, Chou P, Effros M, Egner S, Jain K, Tolhuizen L. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, 2003, 51(6):1973-1982.
[16] Fragouli C, Soljanin E. Information flow decomposition for network coding. IEEE Transactions on Information Theory, 2006, 52(3):829-848.
[17] Langberg M, Sprintson A, Bruck J. The encoding complexity of network coding. Proceedings of ISIT, 2005:1987-1991.
[18] Fan P. On the encoding complexity of network coding for acyclic multicast networks. Technical report, Department of Electronic Engineering, Tsinghua University, 2004
[19] Ho T, Médard M, Effros M, Karger D. Toward a random operation of networks. submitted to IEEE Transactions on Information Theory, 2004.
[20] Ho T, Médard M, Effros M, Karger D. On randomized network coding. In Proceedings 41st Allerton Annual Conference on Communication, Control and Computing, 2003.
[21] Hamra A, Barakat C, Turletti T. Network Coding for Wireless Mesh Networks: A Case Study. Proc of IEEE WoWMoM 2006. June 2006.
[22] Wang J, Yang G, Lin X, He Z, Lin J. Random linear coding for file sharing in upload-limited wireless packet networks. IEEE 66th Vehicular Technology Conference, 2007(3):235-239.
[23] Yang S, Yeung R. Characterizations of network error correction/detection and erasure Correction. Network coding workshop, 2007.
[24] Yeung R, Cai N. Network error correction, part I: basic concepts and upper bounds. Communications in Information and Systems, 2006, 6(1): 19-36.
[25] Cai N, Yeung R. Network error correction, part II: lower bounds. Communications in Information and Systems, 2006, 6(1): 37-54.
[26] Shokrollahi. Raptor codes. IEEE Transactions on Information Theory, 2006, 52(6):2551-2567.
[27] MacKay D. Fountain codes. IEE Proceedings on Communications, 2005, 152(6):1062-1068.
[28] Yan X, Neely M, Zhang Z. Multicasting in time-varying wireless networks: cross-layer dynamic resource allocation. Proceedings of IEEE International Symposium on Information Theory (ISIT), 2007:2721-2725.
[29] Silva D, Kschischang F. Rank-metric codes for priority encoding transmission with network coding. IEEE Canadian Workshop on Information Theory, 2007:81-84.
[30] Chen Y, Kishore S, Li J. Wireless diversity through network coding. IEEE WCNC, 2006:1681-1686.
[31]李伟.无线自组织网络中信传输关键技术的研究[博士学位论文].北京:清华大学电子工程系,2009.
[32] Applications of network coding in LTE-A. 3GPP标准提案(R1-084130),2008.
[33] Ramamoorthy A, Shi J, Wesel R. On the capacity of network coding for random networks. IEEE Transactions on Information Theory, 2005, 51(8):2878-2885.
[34]谢政,李建平.网络算法与复杂性理论.北京:科学出版社,1995年5月.
[35]王树禾.图论.北京:科学出版社,2004年.
[36] Dieter Jungnickel. Graphs, Networks and Algorithms. Springer, 1999.
[37] Zhang J, Fan P. On network coding in wireless ad-hoc networks. 2nd International Conference on Mobile Technology, Applications and Systems, 2005.
[38] Zhang J, Fan P, Letaief K. Network coding with low complexity in wireless ad-hoc multicast networks. IEEE International Conference on Communications, 2006:3699-3704.
[39] Ma Y, Li W, Fan P, Letaief K, Liu X. On the characteristics of queuing and scheduling at encoding nodes for network coding. International Journal of Communication Systems, 2009, 22(6):755-772.
[40] Sagduyu Y, Ephremides A. Some optimization trade-offs in wireless network coding. Proceedings of Conference on Information Sciences and Systems, 2007:6-11.
[41]陆大纟金.随机过程及其应用.北京:清华大学出版社,1986.
[42] Hardy G, Wnight E. An introduction to the theory of numbers. Chapter 23, Oxford University Press, 1979.
[43]陈鑫林.现代通信中的排队论.北京:电子工业出版社,1999.
[44] Wolff R. Poisson arrivals see time averages. Operations Research, 1982, 30(2):223-231.
[45] Toh C. Ad hoc mobile wireless networks: protocols and systems. Prentice Hall, 2002.
[46] Boppana S, Shea J. Overlapped transmission in wireless ad-hoc networks. Proceedings of ICCCAS06, 2006:1309-1314.
[47] Zhang S, Liew S, Lam P. Physical-layer network coding. Proceedings of the Annual International Conference on Mobile Computing and Networking, 2006:358-365.
[48] Katti S, Katabi D. Embracing wireless interference: analog network coding. ACM SIGCOMM, 2007:397-408.
[49] Rappaport T. Wireless communications: principles and practice. Second Edition, Prentice Hall, 2002.
[50] Broersen P. Automatic autocorrelation and spectral analysis. Springer, 2006.
[51] Proakis J. Digital communications. Fourth Edition, McGraw-Hill College, 2000.
[52] Berrou C, Glavieux A, Thitimajshima P. Near Shannon limit error-correcting coding and decoding: Turbocodes. IEEE International Conference on Communications,1993:1064-1070.
[53] Burr A. Modulation and coding for wireless communications. Prentice Hall, 2001.
[54] Vucetic B, Yuan J. Turbo codes: principles and applications. London, Kluwer Academic Publishers, 2000.
[55] Chase D. A class of algorithms for decoding block codes with measurement information. IEEE Transactions on Information Theory, 1972, 18(1):170-182.
[56]马祎.网络编码的排队与调度分析[硕士学位论文].北京:清华大学电子工程系,2007.
[57] Zhu Y, Li B, Guo J. Multicast with network coding in application-layer overlay networks. IEEE Journal on Selected Areas in Communications, 2004:104-120.
[58] Lehman A, Lehman E. Complexity Classification of Network Information Flow Problems. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2004:135-143.
[59] Goldsmith A. Wireless communications. New York: Cambridge University Press, 2005.
[60] Abramowitz M,Stegun A I. Pocketbook of Mathematical Functions. Deutsch: Verlag Harri Deutsch, 1984.
[61] Shannon C E. A mathematical theory of communication. The Bell System Technical Journal, 1948, 27:379–423 and 623–656.
[62] Gallager R G. Information theory and reliable communication. New York: Wiley, January, 1968.
[63] Bollobas B. Modern graph theory. Springer, August, 2002.
[64] Gupta P, Kumar P R. The capacity of wireless networks. IEEE Transactions on Information Theory, 2000, 46(2): 388–404.
[65] Kendall D G. On the generalized“Birth-and-Death”process. The Annals of Mathematical Statistics, 1948, 19(1):1–15.
[66] Kendall D G. Some problems in the theory of queues. Journal of the Royal Statistical Society, 1951, 113(2):151–185.
[67] Lun S D, Medard M, Koetter R. Efficient operation of wireless packet networks using network coding. Proceedings of International Workshop on Convergent Technologies (IWCT), 2005.
[68] Dong N, Tuan T, Thinh N, et al. Wireless broadcast using network coding. IEEE Transactions on Vehicular Technology, 2009, 58(2):914 - 925.
[69] Abramowitz M, Stegun A I. Pocketbook of mathematical functions. Deutsch: Verlag Harri Deutsch, 1984.
[70] Cooper R B. Introduction to queueing theory. North Holland, 1981.
[71] Kleinrock L. Queueing systems (volume 1: theory). John Wiley & Sons, Inc., January, 1975.
[72] Wu Y, Chou P A, Zhang Q. Network planning in wireless ad hoc networks: a cross-layer approach. IEEE Journal on Selected Areas in Communications, 2005, 23(1):136–150.
[73] Wang H, Fan P, Letaief K B. Maximum flow and network capacity of network coding for ad hoc networks. IEEE Transactions on Wireless Communications, 2007, 6(12):4193-4198.
[74] Ho T, leong B, Koetter R, et al. Distributed asynchronous algorithms for multicast network coding. Proceedings of the First Workshop on Network Coding, Theory, and Applications, 2005.
[75] Ho T, Medard M, Koetter R. An information-theoretic view of network management. IEEE Transactions on Information Theory, 2005, 51(4):1295–1312.
[76] Cai K, Fan P. An algebraic approach to link failure of network coding. IEEE Transactions on Information Theory, 2007, 53(2):775-779.
[77] Liu H C, Xue F. Network coding for two-way relaying: rate region, sum rate and opportunistic scheduling. Proceedings of IEEE ICC, 2008: 1044-1049.
[78] Diestel R. Graph theory. Springer, July, 2005.
[79] Erlang A K. Solutions of some problems in the theory of probability of significance in automatic telephone exchanges. The Post Office Electrical Engineers’Journal, 1918, 10:189–197.
[80] Takagi H. Queueing analysis: a foundation of performance evaluation. North Holland, 1991.
[81]卢开澄.组合数学.清华大学出版社, 2006.
[82]王金龙,王呈贵,吴启晖,等.Ad Hoc移动无线网络.北京:国防工业出版社,2003.
[83]陈林星,曾曦,曹毅.移动Ad Hoc网络—自组织分组无线网络技术.北京:电子工业出版社,2006.
[84] IEEE 802.11, the working group setting the standards for wireless LANs. http://www.ieee802.org/11/.
[85] Koffman I, Roman V. Broadban wireless access solution based on OFDM access in IEEE 802.16. IEEE Commun. Mag., 2002, 40(4):96-103.
[86] Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands. IEEE Std. 802.16e, IEEE 2005.
[87]曹志刚,钱亚生.现代通信原理.北京:清华大学出版社,1992.
[88] Tolga M, Ghrayeb A. Coding for MIMO communication systems. Wiley, 2007.
[89] Joing analog network coding and relay. 3GPP标准提案(R1-084133),2008.
[90] Network coding relay and its chase combining. 3GPP标准提案(R1-092161),2008.
[91] Woldegebreal D, Holger K. Network-coding-based cooperative transmission in wireless sensor networks: Diversity-multiplexing tradeoff and coverage area extension. Wireless Sensor Networks - 5th European Conference, 2008:141-155.
[92] Larsson P, Johansson N. Multi-User ARQ. IEEE 63rd Vehicular Technology Conference, 2006:2052-2057.
[93] Sagduyu Y, Guo D, Randall B. On the delay and throughput of digital and analog network coding for wireless broadcast. The 42nd Annual Conference on Information Sciences and Systems, 2008:534-539.
[94] Li K, Wang X. Cross-layer design of wireless mesh networks with network coding. IEEE Transactions on Mobile Computing, 2008, 7(11):1363-1373.
[95] Kim T, Lim H, Hou J. Understanding and improving the spatial reuse in multihop wireless networks. IEEE Transactions on Mobile Computing, 2008, 7(10):1200-1212.
[96] Subramanian A, Andrew T. A simple algebraic formulation for the scalar linear network coding problem. 46th Annual Allerton Conference on Communication, Control, and Computing, 2008:177-184.
[97] Eryilmaz A, Ozdaglar A, Medard M, Ahmed E. On the delay and throughput gains of coding in unreliable networks. IEEE Transactions on Information Theory, 2008, 54(12):5511-5524.
[98] Ding Z, Ratnarajah T, Leung K. On the study of network coded AF transmission protocol for wireless multiple access channels. IEEE Transactions on Wireless Communications, 2008, 7(11):4568-4574.
[99] Kotter R, Kschischang F. Coding for errors and erasures in random network coding. IEEE Transactions on Information Theory, 2008, 54(8):3579-3591.
[100] Price J, Javidi T. Network coding games with unicast flows. IEEE Journal on Selected Areas in Communications, 2008, 26(7):1302-1316.
[101] Ying L, Yang S, Srikant R. Optimal delay-throughput tradeoffs in mobile Ad Hoc networks. IEEE Transactions on Information Theory, 2008, 54(9):4119-4143.