无线网络中的机会网络编码技术研究
|
摘要
无线网络编码是网络编码技术研究的一个重要方向，而具有本地化特性的机会网络编码则是无线网络编码技术领域中一个简单实用的分支。针对无线机会网络编码吞吐性能优化的基础性问题，本文从理论框架、调度算法和应用改良三个层次系统性地展开了理论和应用研究，主要的研究内容和贡献包括：
1通过研究无线网络编码的最大多流问题，提出了一套理论框架，解决了在任意机会网络编码设置下的任意无线网络拓扑中，计算任意多个单播流所能达到的最大吞吐的难题。在这个理论框架中，针对确定无线机会网络编码容量区域的NP难问题，提出了一种贪婪启发式算法，能够高效地确定无线机会网络编码的一个近似容量区域。此外，针对在无线机会网络编码中寻求最优调度的NP难问题，提出了一种多项式复杂度的调度算法，并且论证了该算法具有常数近似界保障。实验结果和数学分析表明，基于本文所提出的理论框架，上述两种算法都具有很好的性能，所取得的最大吞吐数值结果能够逼近最优值。
2通过研究物理干扰模型下无线网络编码的调度问题，提出了一个有常数界保障的近似算法。与传统物理干扰模型下的单播/多播调度不同，无线网络编码的调度可能会对多个接收节点产生不同的干扰要求，因此本文首先针对不同的无线网络编码场景提出了不同的调度优化问题。其中，针对适用于无线机会网络编码调度的MIMS优化问题，提出了一个近似调度算法，并且通过严格的数学证明论证了这个算法具有常数近似界保障。本文初步探索了在真实的物理干扰模型下支持网络编码的调度问题，为后续的研究提供了参考。
3通过研究无线机会网络编码系统的译码缓存问题，提出了一套实用的译码缓存管理机制。在实际的无线机会网络编码系统中，有限的译码缓存条件可能引起编码机会流失而降低网络编码的吞吐增益。本文基于译码分组的流量特性，提出了一种由译码缓存过滤功能和分组信息分发功能组成的译码缓存管理机制DBM。仿真结果表明，DBM能够极大的提高译码缓存利用率、降低带宽开销，并且在译码缓存受限的情况下，比传统的COPE方法拥有更多的编码机会，确保网络编码的吞吐增益真正可达。
Wireless network coding is an important part of the network coding technology,and the localized opportunistic network coding is one of the most simple and practicalbranches of the wireless network coding. To address the basic problem of the through-put performance of the wireless opportunistic network coding, this thesis focuses on thethroughput performance optimization, and systematically conducts theory and applica-tion research from the following three levels: theory framework, scheduling algorithmand system improvement. The main research contents and contributions of this thesis areas follows:
Firstly, by studying the classical problem of maximum multi-commodity flow, wepropose a theory framework for computing the maximum throughput of any given multi-ple unicast flows supported by a multihop wireless network with any given opportunisticnetwork coding setting. In this framework, we show that determining the capacity regionof a multihop wireless network with opportunistic network coding is an NP-hard prob-lem, and thus develop a greedy heuristic algorithm to determine a capacity subregion.We also show that finding an optimal schedule in a multihop wireless network with op-portunistic network coding is NP-hard, and thus develop a polynomial algorithm to findan approximate schedule with constant approximation bound. A numerical analysis ispresented to demonstrate the efciencies of the algorithms based on the framework.
Secondly, we focus on the network coding schedule under the real physical inter-ference model, and develop a scheduling algorithm with constant approximation bound.Since that it is the first time to investigate the network coding schedule under the physi-cal interference model, we define several scheduling optimization problems for diferentwireless network coding scenarios. The MIMS problem, as one of these scheduling opti-mization problems, applies to the opportunistic network coding scenario. We then devel-op a polynomial algorithm with constant approximation bound for the MIMS problem.This thesis initially explores the research field of network coding schedule under the realphysical interference model, providing a reference for subsequent research.
Finally, we investigate the problem of decoding bufer in opportunistic network cod-ing systems, and introduce a mechanism for decoding bufer management. In a practicalopportunistic network coding system, limited decoding bufer may result in the loss of coding opportunities, as well as the reduction of the throughput gain brought by net-work coding. Based on the flow characteristics of those decoding packets, we introducea mechanism called decoding bufer management (DBM) in practical opportunistic net-work coding systems, which consisting of the decoding bufer filtering function and thepacket information distributing function. The simulation results show that, DBM cangreatly improve the utilization level of decoding bufer while reducing the bandwidthoverhead, and provide more coding opportunities than the traditional COPE method whendecoding bufer is limited.
1通过研究无线网络编码的最大多流问题，提出了一套理论框架，解决了在任意机会网络编码设置下的任意无线网络拓扑中，计算任意多个单播流所能达到的最大吞吐的难题。在这个理论框架中，针对确定无线机会网络编码容量区域的NP难问题，提出了一种贪婪启发式算法，能够高效地确定无线机会网络编码的一个近似容量区域。此外，针对在无线机会网络编码中寻求最优调度的NP难问题，提出了一种多项式复杂度的调度算法，并且论证了该算法具有常数近似界保障。实验结果和数学分析表明，基于本文所提出的理论框架，上述两种算法都具有很好的性能，所取得的最大吞吐数值结果能够逼近最优值。
2通过研究物理干扰模型下无线网络编码的调度问题，提出了一个有常数界保障的近似算法。与传统物理干扰模型下的单播/多播调度不同，无线网络编码的调度可能会对多个接收节点产生不同的干扰要求，因此本文首先针对不同的无线网络编码场景提出了不同的调度优化问题。其中，针对适用于无线机会网络编码调度的MIMS优化问题，提出了一个近似调度算法，并且通过严格的数学证明论证了这个算法具有常数近似界保障。本文初步探索了在真实的物理干扰模型下支持网络编码的调度问题，为后续的研究提供了参考。
3通过研究无线机会网络编码系统的译码缓存问题，提出了一套实用的译码缓存管理机制。在实际的无线机会网络编码系统中，有限的译码缓存条件可能引起编码机会流失而降低网络编码的吞吐增益。本文基于译码分组的流量特性，提出了一种由译码缓存过滤功能和分组信息分发功能组成的译码缓存管理机制DBM。仿真结果表明，DBM能够极大的提高译码缓存利用率、降低带宽开销，并且在译码缓存受限的情况下，比传统的COPE方法拥有更多的编码机会，确保网络编码的吞吐增益真正可达。
Wireless network coding is an important part of the network coding technology,and the localized opportunistic network coding is one of the most simple and practicalbranches of the wireless network coding. To address the basic problem of the through-put performance of the wireless opportunistic network coding, this thesis focuses on thethroughput performance optimization, and systematically conducts theory and applica-tion research from the following three levels: theory framework, scheduling algorithmand system improvement. The main research contents and contributions of this thesis areas follows:
Firstly, by studying the classical problem of maximum multi-commodity flow, wepropose a theory framework for computing the maximum throughput of any given multi-ple unicast flows supported by a multihop wireless network with any given opportunisticnetwork coding setting. In this framework, we show that determining the capacity regionof a multihop wireless network with opportunistic network coding is an NP-hard prob-lem, and thus develop a greedy heuristic algorithm to determine a capacity subregion.We also show that finding an optimal schedule in a multihop wireless network with op-portunistic network coding is NP-hard, and thus develop a polynomial algorithm to findan approximate schedule with constant approximation bound. A numerical analysis ispresented to demonstrate the efciencies of the algorithms based on the framework.
Secondly, we focus on the network coding schedule under the real physical inter-ference model, and develop a scheduling algorithm with constant approximation bound.Since that it is the first time to investigate the network coding schedule under the physi-cal interference model, we define several scheduling optimization problems for diferentwireless network coding scenarios. The MIMS problem, as one of these scheduling opti-mization problems, applies to the opportunistic network coding scenario. We then devel-op a polynomial algorithm with constant approximation bound for the MIMS problem.This thesis initially explores the research field of network coding schedule under the realphysical interference model, providing a reference for subsequent research.
Finally, we investigate the problem of decoding bufer in opportunistic network cod-ing systems, and introduce a mechanism for decoding bufer management. In a practicalopportunistic network coding system, limited decoding bufer may result in the loss of coding opportunities, as well as the reduction of the throughput gain brought by net-work coding. Based on the flow characteristics of those decoding packets, we introducea mechanism called decoding bufer management (DBM) in practical opportunistic net-work coding systems, which consisting of the decoding bufer filtering function and thepacket information distributing function. The simulation results show that, DBM cangreatly improve the utilization level of decoding bufer while reducing the bandwidthoverhead, and provide more coding opportunities than the traditional COPE method whendecoding bufer is limited.
引文
[1] Ahlswede R, Cai N, Li S Y, et al. Network Information Flow. IEEE Transactions on Informa-tion Theory,2000,46(4):1204–1216.
[2] Li S Y, Yeung R, Cai N. Linear Network Coding. IEEE Transactions on Information Theory,2003,49(2):371–381.
[3] Koetter R, Medard M. An Algebraic Approach to Network Coding. IEEE/ACM Transactionson Networking,2003,11(5):782–795.
[4] Ho T, Medard M, Koetter R, et al. A Random Linear Network Coding Approach to Multicast.IEEE Transactions on Information Theory,2006,52(10):4413–4430.
[5] Katti S, Rahul H, Hu W, et al. XORs in the Air: Practical Wireless Network Coding.IEEE/ACM Transactions on Networking,2008,16(3):497–510.
[6] Zhang S, Liew S C, Lam P K. Physical Layer Network Coding. Proceedings of the12th ACMInternational Conference on Mobile Computing and Networking(MOBICOM), Los Angeles,USA,2006.
[7] Wang C C, Shrof N. Beyond the Butterfly-A Graph-theoretic Characterization of the Feasibil-ity of Network Coding with Two Simple Unicast Sessions. Proceedings of IEEE InternationalSymposium on Information Theory(ISIT), Nice, France,2007.
[8] Li Z, Li B. Network Coding in Undirected Networks. Proceedings of the38th Annual Confer-ence on Information Sciences and Systems(CISS), Princeton, USA,2004.
[9] Karandey S, Wang Z, Sadjadpoury H R, et al. Network Coding Does Not Change The Mul-ticast Throughput Order of Wireless Ad hoc Networks. Proceedings of IEEE InternationalConference on Communications(ICC), Santa Cruz, USA,2009.
[10] Liu J, Goeckel D, Towsley D. The Throughput Order of Ad-hoc Networks Employing NetworkCoding and Broadcasting. Proceedings of Military Communications Conference (MILCOM),Washington DC, USA,2006.
[11] Liu J, Goeckel D, Towsley D. Bounds on the Gain of Network Coding and Broadcastingin Wireless Networks. Proceedings of the26th IEEE International Conference on ComputerCommunications(INFOCOM), Anchorage, USA,2007.
[12] Lu K, Fu S, Qian Y. Capacity of Random Wireless Networks: Impact of Physical-layer Net-work Coding. Proceedings of IEEE International Conference on Communications(ICC), Bei-jing, China,2008.
[13] Katti S, Gollakota S, Katabi D. Embracing Wireless Interference: Analog Network Coding.Proceedings of ACM SIGCOMM, Kyoto, Japan,2007.
[14] Cui T, Chen L, Ho T. On Distributed Scheduling in Wireless Networks Exploiting Broadcastand Network Coding. IEEE Transactions on Communications,2010,58(4):1223–1234.
[15] Traskov D, Heindlmaier M, Medard M, et al. Scheduling for Network-Coded Multicast.IEEE/ACM Transactions on Networking,2012,20(5):1479–1488.
[16] Sagduyu Y E, Ephremides A. Crosslayer Design for Distributed MAC and Network Codingin Wireless Ad hoc Networks. Proceedings of IEEE International Symposium on InformationTheory(ISIT),2005.
[17]王静.一种网络编码的多播路由算法.西安电子科技大学学报,2008,35(1):71–75.
[18] Seferoglu H, Markopoulou A, Kozat U. Network Coding-Aware Rate Control and Schedulingin Wireless Networks. Proceedings of IEEE international conference on Multimedia and Expo,New York, USA,2009.
[19] Scalia L, Soldo F, Gerla M. PiggyCode: A MAC Layer Network Coding Scheme to ImproveTCP Performance over Wireless Networks. Proceedings of IEEE Global TelecommunicationsConference, Washington, DC, USA,2007.
[20] Sundararajan J, Shah D, Medard M, et al. Network Coding Meets TCP. Proceedings of the28th IEEE International Conference on Computer Communications(INFOCOM),2009.
[21] Seferoglu H, Markopoulou A. Video-aware Opportunistic Network Coding over Wireless Net-works. IEEE Journal on Selected Areas in Communications,2009,27(5):713–728.
[22] Lun D S, Medard M, Koetter R. Efcient Operation of Wireless Packet Networks Using Net-work Coding. Proceedings of International Workshop on Convergent Technologies (IWCT),2005.
[23] Wu Y, Chou P, Kung S. Minimum-energy Multicast in Mobile Ad hoc Networks Using Net-work Coding. IEEE Transactions on Communications,2005,56(11):1906–1918.
[24] Nguyen D, Tran T, Nguyen T, et al. Wireless Broadcast Using Network Coding. IEEE Trans-actions on Vehicular Technology,2009,58(1):914–925.
[25] Ghaderi M, Towsley D, Kurose J. Network Coding Performance for Reliable Multicast. Pro-ceedings of IEEE Military Communications Conference,2007.
[26] Ghaderi M, Towsley D, Kurose J. Reliability Gain of Network Coding in Lossy WirelessNetworks. Proceedings of the27th IEEE Conference on Computer Communications, Beijing,China,2008.
[27] Tran T, Nguyen T, Bose B. A Joint Network-Channel Coding Technique for Single-Hop Wire-less Networks. Proceedings of the4th Workshop on Network Coding, Theory, and Applica-tions, San Diego, USA,2008.
[28] Eryilmaz A, Ozdaglar A, Medard M. On Delay Performance Gains from Network Coding.Proceedings of IEEE International Symposium on Information Theory(ISIT), Princeton, USA,2006.
[29] Hausl C, Dupraz P. Joint Network-Channel Coding for the Multiple-Access Relay Chan-nel. Proceedings of IEEE Communications Society Sensor and Ad Hoc Communications andNetworks, New Orleans, USA,2006.
[30] Sengupta S, Rayanchu S, Banerjee S. An Analysis of Wireless Network Coding for UnicastSessions: The Case for Coding-Aware Routing. Proceedings of the26th IEEE InternationalConference on Computer Communications(INFOCOM), Anchorage, USA,2007.
[31] Ni B, Santhapuri N, Zhong Z, et al. Routing with Opportunistically Coded Exchanges inWireless Mesh Networks. Proceedings of the2nd IEEE Workshop on Wireless Mesh Net-works(WiMesh), Reston, USA,2006.
[32] Wu Y, Das S, Chandra R. Routing with a Markovian Metric to Promote Local Mixing. Proceed-ings of the26th IEEE International Conference on Computer Communications(INFOCOM),Anchorage, USA,2007.
[33] Le J, Lui J S, Chiu D M. DCAR: Distributed Coding-Aware Routing in Wireless Networks.IEEE Transactions on Mobile Computing,2010,9(4):596–608.
[34] Fan K, Wei X, Long D. A Load-Balanced Route Selection for Network Coding in WirelessMesh Networks. Proceedings of IEEE International Conference on Communications(ICC),Dresden, Germany,2009.
[35] Han S, Zhong Z, Li H, et al. Coding-aware Multi-path Routing in Multi-hop Wireless Net-works. Proceedings of the27th IEEE Conference on Performance,Computing, and Communi-cations, TX, USA,2008.
[36] Yan Y, Zhao Z, Zhang B, et al. Rate-Adaptive Coding-Aware Multiple Path Routingfor Wireless Mesh Networks. Proceedings of IEEE Global Telecommunications Confer-ence(GLOBECOM), New Orleans, USA,2008.
[37] Omiwade S, Zheng R, Hua C. Practical Localized Network Coding in Wireless Mesh Net-works. Proceedings of the5th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks(SECON), San Francisco, USA,2008.
[38] Wang H, Xue K, Hong P, et al. Impact of Trafc Pattern on Benefits of Practical Multi-hopNetwork coding in Wireless Networks. Proceedings of IEEE Consumer Communications andNetworking Conference(CCNC), Las Vegas, USA,2011.
[39] Scalia L, Soldo F, Gerla M. PiggyCode: A MAC Layer Network Coding Scheme to ImproveTCP Performance over Wireless Networks. Proceedings of IEEE Global TelecommunicationsConference(GLOBCOM), Washington DC, USA,2007.
[40] Rayanchu S, Sen S, Wu J, et al. Loss-aware Network Coding for Unicast Wireless Session-s: Design, Implementation, and Performance Evaluation. Proceedings of ACM internationalconference on Measurement and modeling of computer systems(SIGMETRICS), Annapolis,USA,2008.
[41] Rozner E, Iyer A P, Mehta Y, et al. ER: Efcient Retransmission Scheme for Wireless LANs.Proceedings of ACM CONEXT,2007.
[42] Cui T, Chen L, Ho T. Energy Efcient Opportunistic Network Coding for Wireless Net-works. Proceedings of the27th IEEE International Conference on Computer Communica-tions(INFOCOM), Phoenix, USA,2008.
[43] Dana A, Gowaikar R, Palanki R, et al. Capacity of Wireless Erasure Networks. IEEE Trans-actions on Information Theory,2006,52(3):789–804.
[44] Jiang C, Smith B, Hassibi B, et al. Multicast in Wireless Erasure Networks with Feedback.Proceedings of IEEE Symposium Computer and Communications,2008.
[45] Smith B, Hassibi B. Wireless Erasure Networks with Feedback. Proceedings of IEEE Interna-tional Symposium on Information Theory(ISIT),2008.
[46] Dougherty R, Freiling C, Zeger K. Insufciency of Linear Coding in Network InformationFlow. IEEE Transactions on Information Theory,2005,51(8):2745–2759.
[47] Dougherty R, Freiling C, Zeger K. Networks, Matroids, and Non-Shannon Information In-equality. IEEE Transactions on Information Theory,2007,53(6):1949–1969.
[48] Dougherty R, Freiling C, Zeger K. Linear Network Codes and Systems of Polynomial Equa-tions. IEEE Transactions on Information Theory,2008,54(5):2303–2316.
[49] Lehman A. Network Coding[博士学位论文]. Cambridge, MA: MIT,2005.
[50] Chaporkar P, Proutiere A. Adaptive Network Coding and Scheduling for Maximizing Through-put in Wireless Networks. Proceedings of the13th Annual ACM International Conference onMobile Computing and Networking, Montreal, Canada,2007.
[51] Le J, Lui J S, Chiu D M. How Many Packets Can We Encode?-An Analysis of Practical Wire-less Network Coding. Proceedings of the27th IEEE International Conference on ComputerCommunications(INFOCOM), Phoenix, USA,2008.
[52] Tarasak P, Sethakaset U, Sun S. Capacity Analysis of Two-user Opportunistic Schedulingfor Wireless Network Coding. Proceedings of IEEE International Symposium on InformationTheory(ISIT), Seoul, Korea,2009.
[53] Zhao F, Medard M. On Analyzing and Improving COPE Performance. Proceedings of Infor-mation Theory and Applications Workshop(ITA)., San Diego, USA,2010.
[54] Jain K, Padhye J, Padmanabhan V, et al. Impact of Interference on Multi-hop Wireless NetworkPerformance. ACM/Springer Wireless Networks,2005,11:471–487.
[55] Ephremides A, Truong T. Scheduling Broadcasts in Multihop Radio Networks. IEEE Trans-actions on Communications,1990,38(4):456–460.
[56] Arikan E. Some Complexity Results about Packet Networks. IEEE Transaction on InformationTheory,1984,30(4):681–685.
[57] Wu Y, Chou P, Zhang Q, et al. Network Planning in Wireless Ad-Hoc Networks: A Cross-LayerApproach. IEEE Journal on Selected Areas in Communications,2005,23(1):136–150.
[58] Park J, Lun D, Soldo F, et al. Performance of Network Coding in Ad hoc Networks. Pro-ceedings of IEEE Military Communications Conference(MILCOM), Washington, DC, USA,2006.
[59] Sagduyu Y, Ephremides A. Joint Scheduling and Wireless Network Coding. Proceedings ofthe First Workshop on Network Coding, Theory and Applications, Riva del Garda, Italy,2005.
[60] Sagduyu Y E, Ephremides A. On Joint MAC and Network Coding in Wireless Ad Hoc Net-works. IEEE Transactions on Information Theory,2007,53(10):3697–3713.
[61] Cloud J, Zeger L, Medard M. MAC Centered Cooperation-Synergistic Design of NetworkCoding, Multi-Packet Reception, and Improved Fairness to Increase Network Throughput.IEEE Journal on Selected Areas in Communications,2012,30(2):341–349.
[62] Yan Y, Zhao Z, Zhang B, et al. Mechanism for Maximizing Area-centric Coding Gains inWireless Multihop Networks. Proceedings of IEEE International Conference on Communica-tions(ICC), Dresden, Germany,2009.
[63] Chi K, Jiang X, Horiguchi S. A More Efcient COPE Architecture for Network Coding inMultihop Wireless Networks. IEICE Transactions on Communications,2009, E92-B(3):766–775.
[64] Sengupta S, Rayanchu S, Banerjee S. Network Coding-aware Routing in Wireless Networks.IEEE/ACM Transactions on Networking,2010,18(4):1158–1170.
[65] Derhami V, Pahlavani P, Bidoki A. FENC: Fast and Efcient Opportunistic Network Coding inWireless Networks. KSII Transactions on Internet and Information Systems,2011,5(1):52–67.
[66] Wang Y, Lu H, Hong P, et al. Practical Wireless Network Coding with Constrained DecodingBufers. Proceedings of IEEE International Symposium on Network Coding(NetCod), Toronto,Canada,2010.
[67] Argyriou A. Wireless Network Coding with Improved Opportunistic Listening. IEEE Trans-actions on Wireless Communications,2009,8(4):2014–2023.
[68] Nage T, Yu F R, St-Hilaire M. Adaptive Control of Packet Overhead in XOR Network Coding.Proceedings of IEEE International Conference on Communications(ICC), Cape Town, SouthAfrica,2010.
[69] Wan P J. Multiflows in Multihop Wireless Networks. Proceedings of ACM MOBIHOC, NewOrleans, USA,2009.
[70] Gupta P, Kumar P. The Capacity of Wireless Networks. IEEE Transactions on InformationTheory,2000,46(2):388–404.
[71] Shi Y, Hou Y T, Kompella S. How to Correctly Use the Protocol Interference Model for Multi-hop Wireless Networks. Proceedings of the10th ACM International Symposium Mobile Adhoc Networking and Computing(MOBIHOC), Phoenix, USA,2009.
[72] Wan P J, Cheng Y, Wang Z, et al. Multiflows in Multi-channel Multi-radio Multihop WirelessNetworks. Proceedings of the30th IEEE International Conference on Computer Communica-tions(INFOCOM), Shanghai, China,2011.
[73] Garey M R, Johnson D S. Computers and Intracctability: A Guide to the Theory of NP Com-pletness. W.H. Freeman and Company,1979.
[74] Li H K, Cheng Y, Zhou C, et al. Multi-dimensional Conflict Graph Based Computing for Opti-mal Capacity in MR-MC Wireless Networks. Proceedings of the30th International Conferenceon Distributed Computing Systems(ICDCS), Genoa, Italy,2010.
[75] Ahuja R, Magnanti T, Orlin J. Network flows: Theory, Algorithms, and Applications. PrenticeHall,1993.
[76] IBM ILOG CPLEX Optimizer. http://www.ibm.com/software/integration/optimization/cplex-optimizer/.
[77] Kumar V, Marathe M, Parthasarathy S, et al. Algorithmic Aspects of Capacity in WirelessNetworks. SIGMETRICS Perform. Eval. Rev.,2005,33(1):133–144.
[78] Goussevskaia O, Oswald Y, Wattenhofer R. Complexity in Geometric SINR. Proceed-ings of the8th ACM International Symposium Mobile Ad-Hoc Networking and Comput-ing(MOBIHOC),2007.
[79] Goussevskaia O, Halldorsson M, Wattenhofer R, et al. Capacity of Arbitrary Wireless Net-works. Proceedings of the28th IEEE International Conference on Computer Communication-s(INFOCOM),2009.
[80] Xu X, Tang S. A Constant Approximation Algorithm for Link Scheduling in Arbitrary Net-works under Physical Interference Model. Proceedings of the2nd ACM International Work-shop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing,2009.
[81] Wan P J, Jia X, Yao F. Maximum Independent Set of Links under Physical Interference Mod-el. Proceedings of the4th International Conference on Wireless Algorithms, Systems, andApplications(WASA),2009.
[82] Xu X, Tang S, Wan P J. Maximum Weighted Independent Set of Links under Physical In-terference Model. Proceedings of the5th International Conference on Wireless Algorithms,Systems, and Applications(WASA),2010.
[83] Halldorsson M, Mitra P. Wireless Capacity with Oblivious Power in General Metrics. Pro-ceedings of the22th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA),2011.
[84] Kesselheim T. A Constant-factor Approximation for Wireless Capacity Maximization withPower Control in the SINR Model. Proceedings of the22th Annual ACM-SIAM Symposiumon Discrete Algorithms(SODA),2011.
[85] Wan P J, Chen D, Dai G, et al. Maximizing Capacity with Power Control under PhysicalInterference Model in Duplex Mode. Proceedings of the31th IEEE International Conferenceon Computer Communications(INFOCOM),2012.
[86] Bateman P, Erdos P. Geometrical Extrema Suggested by A Lemma of Besicovitch. AmericanMathematical Monthly,1951.306–314.
[87] Groemer H. Uber die Einlagerung von Kreisen in einen konvexen Bereich. Math. Zeitschrift,1960,73:285–294.
[88] Yomo H, Popovski P. Opportunistic Scheduling for Wireless Network Coding. Proceedings ofIEEE International Conference on Communications(ICC), Glasgow, Scotland,2007.
[89] Gkelias A, Leung K. A Distributed Opportunistic Scheduling Scheme for Wireless NetworkCoding. Proceedings of the6th International Symposium on Wireless Communication Sys-tems(ISWCS), Siena-Tuscany, Italy,2009.
[2] Li S Y, Yeung R, Cai N. Linear Network Coding. IEEE Transactions on Information Theory,2003,49(2):371–381.
[3] Koetter R, Medard M. An Algebraic Approach to Network Coding. IEEE/ACM Transactionson Networking,2003,11(5):782–795.
[4] Ho T, Medard M, Koetter R, et al. A Random Linear Network Coding Approach to Multicast.IEEE Transactions on Information Theory,2006,52(10):4413–4430.
[5] Katti S, Rahul H, Hu W, et al. XORs in the Air: Practical Wireless Network Coding.IEEE/ACM Transactions on Networking,2008,16(3):497–510.
[6] Zhang S, Liew S C, Lam P K. Physical Layer Network Coding. Proceedings of the12th ACMInternational Conference on Mobile Computing and Networking(MOBICOM), Los Angeles,USA,2006.
[7] Wang C C, Shrof N. Beyond the Butterfly-A Graph-theoretic Characterization of the Feasibil-ity of Network Coding with Two Simple Unicast Sessions. Proceedings of IEEE InternationalSymposium on Information Theory(ISIT), Nice, France,2007.
[8] Li Z, Li B. Network Coding in Undirected Networks. Proceedings of the38th Annual Confer-ence on Information Sciences and Systems(CISS), Princeton, USA,2004.
[9] Karandey S, Wang Z, Sadjadpoury H R, et al. Network Coding Does Not Change The Mul-ticast Throughput Order of Wireless Ad hoc Networks. Proceedings of IEEE InternationalConference on Communications(ICC), Santa Cruz, USA,2009.
[10] Liu J, Goeckel D, Towsley D. The Throughput Order of Ad-hoc Networks Employing NetworkCoding and Broadcasting. Proceedings of Military Communications Conference (MILCOM),Washington DC, USA,2006.
[11] Liu J, Goeckel D, Towsley D. Bounds on the Gain of Network Coding and Broadcastingin Wireless Networks. Proceedings of the26th IEEE International Conference on ComputerCommunications(INFOCOM), Anchorage, USA,2007.
[12] Lu K, Fu S, Qian Y. Capacity of Random Wireless Networks: Impact of Physical-layer Net-work Coding. Proceedings of IEEE International Conference on Communications(ICC), Bei-jing, China,2008.
[13] Katti S, Gollakota S, Katabi D. Embracing Wireless Interference: Analog Network Coding.Proceedings of ACM SIGCOMM, Kyoto, Japan,2007.
[14] Cui T, Chen L, Ho T. On Distributed Scheduling in Wireless Networks Exploiting Broadcastand Network Coding. IEEE Transactions on Communications,2010,58(4):1223–1234.
[15] Traskov D, Heindlmaier M, Medard M, et al. Scheduling for Network-Coded Multicast.IEEE/ACM Transactions on Networking,2012,20(5):1479–1488.
[16] Sagduyu Y E, Ephremides A. Crosslayer Design for Distributed MAC and Network Codingin Wireless Ad hoc Networks. Proceedings of IEEE International Symposium on InformationTheory(ISIT),2005.
[17]王静.一种网络编码的多播路由算法.西安电子科技大学学报,2008,35(1):71–75.
[18] Seferoglu H, Markopoulou A, Kozat U. Network Coding-Aware Rate Control and Schedulingin Wireless Networks. Proceedings of IEEE international conference on Multimedia and Expo,New York, USA,2009.
[19] Scalia L, Soldo F, Gerla M. PiggyCode: A MAC Layer Network Coding Scheme to ImproveTCP Performance over Wireless Networks. Proceedings of IEEE Global TelecommunicationsConference, Washington, DC, USA,2007.
[20] Sundararajan J, Shah D, Medard M, et al. Network Coding Meets TCP. Proceedings of the28th IEEE International Conference on Computer Communications(INFOCOM),2009.
[21] Seferoglu H, Markopoulou A. Video-aware Opportunistic Network Coding over Wireless Net-works. IEEE Journal on Selected Areas in Communications,2009,27(5):713–728.
[22] Lun D S, Medard M, Koetter R. Efcient Operation of Wireless Packet Networks Using Net-work Coding. Proceedings of International Workshop on Convergent Technologies (IWCT),2005.
[23] Wu Y, Chou P, Kung S. Minimum-energy Multicast in Mobile Ad hoc Networks Using Net-work Coding. IEEE Transactions on Communications,2005,56(11):1906–1918.
[24] Nguyen D, Tran T, Nguyen T, et al. Wireless Broadcast Using Network Coding. IEEE Trans-actions on Vehicular Technology,2009,58(1):914–925.
[25] Ghaderi M, Towsley D, Kurose J. Network Coding Performance for Reliable Multicast. Pro-ceedings of IEEE Military Communications Conference,2007.
[26] Ghaderi M, Towsley D, Kurose J. Reliability Gain of Network Coding in Lossy WirelessNetworks. Proceedings of the27th IEEE Conference on Computer Communications, Beijing,China,2008.
[27] Tran T, Nguyen T, Bose B. A Joint Network-Channel Coding Technique for Single-Hop Wire-less Networks. Proceedings of the4th Workshop on Network Coding, Theory, and Applica-tions, San Diego, USA,2008.
[28] Eryilmaz A, Ozdaglar A, Medard M. On Delay Performance Gains from Network Coding.Proceedings of IEEE International Symposium on Information Theory(ISIT), Princeton, USA,2006.
[29] Hausl C, Dupraz P. Joint Network-Channel Coding for the Multiple-Access Relay Chan-nel. Proceedings of IEEE Communications Society Sensor and Ad Hoc Communications andNetworks, New Orleans, USA,2006.
[30] Sengupta S, Rayanchu S, Banerjee S. An Analysis of Wireless Network Coding for UnicastSessions: The Case for Coding-Aware Routing. Proceedings of the26th IEEE InternationalConference on Computer Communications(INFOCOM), Anchorage, USA,2007.
[31] Ni B, Santhapuri N, Zhong Z, et al. Routing with Opportunistically Coded Exchanges inWireless Mesh Networks. Proceedings of the2nd IEEE Workshop on Wireless Mesh Net-works(WiMesh), Reston, USA,2006.
[32] Wu Y, Das S, Chandra R. Routing with a Markovian Metric to Promote Local Mixing. Proceed-ings of the26th IEEE International Conference on Computer Communications(INFOCOM),Anchorage, USA,2007.
[33] Le J, Lui J S, Chiu D M. DCAR: Distributed Coding-Aware Routing in Wireless Networks.IEEE Transactions on Mobile Computing,2010,9(4):596–608.
[34] Fan K, Wei X, Long D. A Load-Balanced Route Selection for Network Coding in WirelessMesh Networks. Proceedings of IEEE International Conference on Communications(ICC),Dresden, Germany,2009.
[35] Han S, Zhong Z, Li H, et al. Coding-aware Multi-path Routing in Multi-hop Wireless Net-works. Proceedings of the27th IEEE Conference on Performance,Computing, and Communi-cations, TX, USA,2008.
[36] Yan Y, Zhao Z, Zhang B, et al. Rate-Adaptive Coding-Aware Multiple Path Routingfor Wireless Mesh Networks. Proceedings of IEEE Global Telecommunications Confer-ence(GLOBECOM), New Orleans, USA,2008.
[37] Omiwade S, Zheng R, Hua C. Practical Localized Network Coding in Wireless Mesh Net-works. Proceedings of the5th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks(SECON), San Francisco, USA,2008.
[38] Wang H, Xue K, Hong P, et al. Impact of Trafc Pattern on Benefits of Practical Multi-hopNetwork coding in Wireless Networks. Proceedings of IEEE Consumer Communications andNetworking Conference(CCNC), Las Vegas, USA,2011.
[39] Scalia L, Soldo F, Gerla M. PiggyCode: A MAC Layer Network Coding Scheme to ImproveTCP Performance over Wireless Networks. Proceedings of IEEE Global TelecommunicationsConference(GLOBCOM), Washington DC, USA,2007.
[40] Rayanchu S, Sen S, Wu J, et al. Loss-aware Network Coding for Unicast Wireless Session-s: Design, Implementation, and Performance Evaluation. Proceedings of ACM internationalconference on Measurement and modeling of computer systems(SIGMETRICS), Annapolis,USA,2008.
[41] Rozner E, Iyer A P, Mehta Y, et al. ER: Efcient Retransmission Scheme for Wireless LANs.Proceedings of ACM CONEXT,2007.
[42] Cui T, Chen L, Ho T. Energy Efcient Opportunistic Network Coding for Wireless Net-works. Proceedings of the27th IEEE International Conference on Computer Communica-tions(INFOCOM), Phoenix, USA,2008.
[43] Dana A, Gowaikar R, Palanki R, et al. Capacity of Wireless Erasure Networks. IEEE Trans-actions on Information Theory,2006,52(3):789–804.
[44] Jiang C, Smith B, Hassibi B, et al. Multicast in Wireless Erasure Networks with Feedback.Proceedings of IEEE Symposium Computer and Communications,2008.
[45] Smith B, Hassibi B. Wireless Erasure Networks with Feedback. Proceedings of IEEE Interna-tional Symposium on Information Theory(ISIT),2008.
[46] Dougherty R, Freiling C, Zeger K. Insufciency of Linear Coding in Network InformationFlow. IEEE Transactions on Information Theory,2005,51(8):2745–2759.
[47] Dougherty R, Freiling C, Zeger K. Networks, Matroids, and Non-Shannon Information In-equality. IEEE Transactions on Information Theory,2007,53(6):1949–1969.
[48] Dougherty R, Freiling C, Zeger K. Linear Network Codes and Systems of Polynomial Equa-tions. IEEE Transactions on Information Theory,2008,54(5):2303–2316.
[49] Lehman A. Network Coding[博士学位论文]. Cambridge, MA: MIT,2005.
[50] Chaporkar P, Proutiere A. Adaptive Network Coding and Scheduling for Maximizing Through-put in Wireless Networks. Proceedings of the13th Annual ACM International Conference onMobile Computing and Networking, Montreal, Canada,2007.
[51] Le J, Lui J S, Chiu D M. How Many Packets Can We Encode?-An Analysis of Practical Wire-less Network Coding. Proceedings of the27th IEEE International Conference on ComputerCommunications(INFOCOM), Phoenix, USA,2008.
[52] Tarasak P, Sethakaset U, Sun S. Capacity Analysis of Two-user Opportunistic Schedulingfor Wireless Network Coding. Proceedings of IEEE International Symposium on InformationTheory(ISIT), Seoul, Korea,2009.
[53] Zhao F, Medard M. On Analyzing and Improving COPE Performance. Proceedings of Infor-mation Theory and Applications Workshop(ITA)., San Diego, USA,2010.
[54] Jain K, Padhye J, Padmanabhan V, et al. Impact of Interference on Multi-hop Wireless NetworkPerformance. ACM/Springer Wireless Networks,2005,11:471–487.
[55] Ephremides A, Truong T. Scheduling Broadcasts in Multihop Radio Networks. IEEE Trans-actions on Communications,1990,38(4):456–460.
[56] Arikan E. Some Complexity Results about Packet Networks. IEEE Transaction on InformationTheory,1984,30(4):681–685.
[57] Wu Y, Chou P, Zhang Q, et al. Network Planning in Wireless Ad-Hoc Networks: A Cross-LayerApproach. IEEE Journal on Selected Areas in Communications,2005,23(1):136–150.
[58] Park J, Lun D, Soldo F, et al. Performance of Network Coding in Ad hoc Networks. Pro-ceedings of IEEE Military Communications Conference(MILCOM), Washington, DC, USA,2006.
[59] Sagduyu Y, Ephremides A. Joint Scheduling and Wireless Network Coding. Proceedings ofthe First Workshop on Network Coding, Theory and Applications, Riva del Garda, Italy,2005.
[60] Sagduyu Y E, Ephremides A. On Joint MAC and Network Coding in Wireless Ad Hoc Net-works. IEEE Transactions on Information Theory,2007,53(10):3697–3713.
[61] Cloud J, Zeger L, Medard M. MAC Centered Cooperation-Synergistic Design of NetworkCoding, Multi-Packet Reception, and Improved Fairness to Increase Network Throughput.IEEE Journal on Selected Areas in Communications,2012,30(2):341–349.
[62] Yan Y, Zhao Z, Zhang B, et al. Mechanism for Maximizing Area-centric Coding Gains inWireless Multihop Networks. Proceedings of IEEE International Conference on Communica-tions(ICC), Dresden, Germany,2009.
[63] Chi K, Jiang X, Horiguchi S. A More Efcient COPE Architecture for Network Coding inMultihop Wireless Networks. IEICE Transactions on Communications,2009, E92-B(3):766–775.
[64] Sengupta S, Rayanchu S, Banerjee S. Network Coding-aware Routing in Wireless Networks.IEEE/ACM Transactions on Networking,2010,18(4):1158–1170.
[65] Derhami V, Pahlavani P, Bidoki A. FENC: Fast and Efcient Opportunistic Network Coding inWireless Networks. KSII Transactions on Internet and Information Systems,2011,5(1):52–67.
[66] Wang Y, Lu H, Hong P, et al. Practical Wireless Network Coding with Constrained DecodingBufers. Proceedings of IEEE International Symposium on Network Coding(NetCod), Toronto,Canada,2010.
[67] Argyriou A. Wireless Network Coding with Improved Opportunistic Listening. IEEE Trans-actions on Wireless Communications,2009,8(4):2014–2023.
[68] Nage T, Yu F R, St-Hilaire M. Adaptive Control of Packet Overhead in XOR Network Coding.Proceedings of IEEE International Conference on Communications(ICC), Cape Town, SouthAfrica,2010.
[69] Wan P J. Multiflows in Multihop Wireless Networks. Proceedings of ACM MOBIHOC, NewOrleans, USA,2009.
[70] Gupta P, Kumar P. The Capacity of Wireless Networks. IEEE Transactions on InformationTheory,2000,46(2):388–404.
[71] Shi Y, Hou Y T, Kompella S. How to Correctly Use the Protocol Interference Model for Multi-hop Wireless Networks. Proceedings of the10th ACM International Symposium Mobile Adhoc Networking and Computing(MOBIHOC), Phoenix, USA,2009.
[72] Wan P J, Cheng Y, Wang Z, et al. Multiflows in Multi-channel Multi-radio Multihop WirelessNetworks. Proceedings of the30th IEEE International Conference on Computer Communica-tions(INFOCOM), Shanghai, China,2011.
[73] Garey M R, Johnson D S. Computers and Intracctability: A Guide to the Theory of NP Com-pletness. W.H. Freeman and Company,1979.
[74] Li H K, Cheng Y, Zhou C, et al. Multi-dimensional Conflict Graph Based Computing for Opti-mal Capacity in MR-MC Wireless Networks. Proceedings of the30th International Conferenceon Distributed Computing Systems(ICDCS), Genoa, Italy,2010.
[75] Ahuja R, Magnanti T, Orlin J. Network flows: Theory, Algorithms, and Applications. PrenticeHall,1993.
[76] IBM ILOG CPLEX Optimizer. http://www.ibm.com/software/integration/optimization/cplex-optimizer/.
[77] Kumar V, Marathe M, Parthasarathy S, et al. Algorithmic Aspects of Capacity in WirelessNetworks. SIGMETRICS Perform. Eval. Rev.,2005,33(1):133–144.
[78] Goussevskaia O, Oswald Y, Wattenhofer R. Complexity in Geometric SINR. Proceed-ings of the8th ACM International Symposium Mobile Ad-Hoc Networking and Comput-ing(MOBIHOC),2007.
[79] Goussevskaia O, Halldorsson M, Wattenhofer R, et al. Capacity of Arbitrary Wireless Net-works. Proceedings of the28th IEEE International Conference on Computer Communication-s(INFOCOM),2009.
[80] Xu X, Tang S. A Constant Approximation Algorithm for Link Scheduling in Arbitrary Net-works under Physical Interference Model. Proceedings of the2nd ACM International Work-shop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing,2009.
[81] Wan P J, Jia X, Yao F. Maximum Independent Set of Links under Physical Interference Mod-el. Proceedings of the4th International Conference on Wireless Algorithms, Systems, andApplications(WASA),2009.
[82] Xu X, Tang S, Wan P J. Maximum Weighted Independent Set of Links under Physical In-terference Model. Proceedings of the5th International Conference on Wireless Algorithms,Systems, and Applications(WASA),2010.
[83] Halldorsson M, Mitra P. Wireless Capacity with Oblivious Power in General Metrics. Pro-ceedings of the22th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA),2011.
[84] Kesselheim T. A Constant-factor Approximation for Wireless Capacity Maximization withPower Control in the SINR Model. Proceedings of the22th Annual ACM-SIAM Symposiumon Discrete Algorithms(SODA),2011.
[85] Wan P J, Chen D, Dai G, et al. Maximizing Capacity with Power Control under PhysicalInterference Model in Duplex Mode. Proceedings of the31th IEEE International Conferenceon Computer Communications(INFOCOM),2012.
[86] Bateman P, Erdos P. Geometrical Extrema Suggested by A Lemma of Besicovitch. AmericanMathematical Monthly,1951.306–314.
[87] Groemer H. Uber die Einlagerung von Kreisen in einen konvexen Bereich. Math. Zeitschrift,1960,73:285–294.
[88] Yomo H, Popovski P. Opportunistic Scheduling for Wireless Network Coding. Proceedings ofIEEE International Conference on Communications(ICC), Glasgow, Scotland,2007.
[89] Gkelias A, Leung K. A Distributed Opportunistic Scheduling Scheme for Wireless NetworkCoding. Proceedings of the6th International Symposium on Wireless Communication Sys-tems(ISWCS), Siena-Tuscany, Italy,2009.