面向无线网络的高效网络编码方法研究
|
摘要
在无线网络中,无线传输的广播特性以及网络拓扑的多跳性,使得无线网络中存在大量冗余报文,直接影响着无线网络的传输性能。近年来的研究表明,网络编码技术能够通过有效利用无线网络中的冗余报文,提升网络性能。然而,网络编码增加了额外计算开销,其性能增益通常受限于无线信道广播速率及无线节点的计算能力,同时还会受到无线节点移动性的影响。如何面向这些无线网络的关键特征,设计合理高效的网络编码方法是无线网络性能优化中的重要问题。
针对上述问题,本文从适应无线信道广播速率限制的角度研究了多信道环境中网络编码方法,并从适应无线节点计算能力与移动性的角度分别对面向数据传送及面向数据广播的网络编码方法开展了研究。论文主要贡献包括以下三个方面：
(1)针对多信道无线网络吞吐率性能优化,以OFDMA中继网络为应用背景,对适应无线信道广播速率的网络编码方法进行了探讨。首先以优化性能与负载为切入点,提出了用于支持编码感知的信道调度策略的全局方法和局部方法。进一步地,针对全局方法下的网络编码感知的信道调度问题,证明了该问题是NP难的且不存在多项式时间近似方案(polynomial time approximation scheme),并提出了一种具有低时间复杂度的启发式算法。针对局部方法下的网络编码感知的信道调度问题,证明了该问题是NP难的,并提出了一种多项式时间近似方案及一种具有1／2近似率的贪婪算法。仿真实验结果表明所提算法相比于无网络编码的机制,能够极大地提高网络吞吐率。
(2)针对无线移动网络中数据传送性能优化,对具有常数复杂度的分块随机线性网络编码(简称分块码)方法进行了研究。首先证明了预编码(precoding)在分块码达到正码率中的不可或缺性。在预编码的前提下,对无重叠分块码的可达码率进行了紧(tight)的分析,并进一步地提出了采用扩展图(expander graph)生成重叠报文块的扩展分块码。通过基于树的分析以及扩展论证刻画了扩展分块码的可达码率,从而明确了扩展分块码是第一类具有非平凡性能保证的重叠分块码。数值分析结果显示扩展分块码性能接近最优,其可达码率极大地超出了无重叠分块码。此外,仿真实验结果表明,当输入报文个数有限时,扩展分块码相比于其他重叠分块码具有低得多的传输负载和解码错误概率。
(3)针对无线移动网络中数据广播性能优化,提出了一种新颖的基于随机线性网络编码的广播协议。该协议将需要广播的消息分割成多个子消息,并将子消息以随机线性网络编码的方式进行传输。随机线性网络编码的应用使得无线节点易于收集有效信息,从而减轻了因一个或多个节点过晚接收到消息所致的时延瓶颈。与此同时,节点传输采用了随机调度机制,即每一个网络节点随机独立地使用无线信道。随机调度的使用能够在利用无线媒介广播特性的同时,有效应对并发传输所致的冲突问题。理论分析表明,该协议在任意的节点移动速度下,均能够达到渐进最优的广播时延。相反地,纯粹的随机调度策略在节点快速移动时不足以达到最优性。
Due to the broadcast nature of wireless medium as well as the multi-hop network topologies, there are a lot of redundant packets in wireless networks, which affect the network performance directly. In recent years, it has been shown that network coding can be used to enhance the performance of wireless networks by exploiting the redundant packets. However, network coding incurs extra computational cost, and its performance gain is usually limited by the broadcast rate of wireless channels as well as the computational capabilities of wireless nodes, and also affected by the mobility of wireless nodes. Therefore, network coding schemes should be designed and applied to meet the requirements of these characteristics of wireless networks.
In this dissertation, we conduct a comprehensive study on the methods of efficient network coding in wireless networks considering the applications of network coding in multi-channel scenarios and for reliable data transmission and broadcast in wireless mobile networks. The contributions of this dissertation are summarized as follows:
(1) We investigate the network coding methods subject to the broadcast rate constraint in OFDMA relay networks. Considering the tradeoff between performance and overhead, we propose two approaches, global approach (GA) and local approach (LA) for the support of coding-aware scheduling decision making. For the coding-aware multi-channel scheduling problem, we show it is NP-hard under both the GA model and the LA model. For the GA model, we also show that it does not admit any polynomial time approximation scheme (PTAS), and then propose a heuristic algorithm with low time complexity, while for the LA model, we present a PTAS and also introduce a practical greedy algorithm with an approximation ratio of1/2. Simulation results show that both proposed practical algorithms can achieve significant throughput improvement over a state-of-the-art noncoding scheme.
(2) We investigate the methods for chunked random linear network codes (chunked codes) with a constant computational complexity for reliable data transmission in wireless mobile networks. We first highlight the importance of precoding for chunked codes to achieve non-vanishing rates, and then present a tight analysis on the achievable rates of non-overlapped chunked codes with precoding. We further introduce the first class of overlapped chunked codes with non-trivial performance guarantee, called expander chunked codes, which use expander graphs to form overlapped chunks, and then characterize their achievable rates using a tree-based analysis as well as some expander arguments. Numerical results reveal that expander chunked codes perform near-optimally, and achieve significantly higher rates than non-overlapped chunked codes. Also, simulation results show that for a finite number of input packets expander chunked codes incur much lower transmission overhead to recover the whole input packets than all other state-of-the-art chunked codes.
(3) We investigate the methods of data broadcast with network coding in wireless mobile networks by proposing a novel random linear network coding based broadcast protocol name R2. In this protocol, the message to be broadcast is divided into multiple mini-messages, while the mini-messages are transmitted in a fashion of random linear network coding. The use of random linear network coding makes nodes easier to accumulate useful information and thus mitigates the bottleneck for completing the broadcast process due to the very late reception of the message by one or more nodes. Meanwhile, R2employs random scheduling, that is, each network node uses the wireless channel randomly and independently, which on one hand exploits the broadcast nature of wireless medium and on the other hand combats the interference due to concurrent transmissions efficiently. Theoretical analyses show that R2performs optimally in terms of broadcast latency in order sense, no matter how fast nodes move around the network. In contrast, the pure random scheduling strategy is insufficient to achieve the order-optimality when nodes move very fast.
针对上述问题,本文从适应无线信道广播速率限制的角度研究了多信道环境中网络编码方法,并从适应无线节点计算能力与移动性的角度分别对面向数据传送及面向数据广播的网络编码方法开展了研究。论文主要贡献包括以下三个方面：
(1)针对多信道无线网络吞吐率性能优化,以OFDMA中继网络为应用背景,对适应无线信道广播速率的网络编码方法进行了探讨。首先以优化性能与负载为切入点,提出了用于支持编码感知的信道调度策略的全局方法和局部方法。进一步地,针对全局方法下的网络编码感知的信道调度问题,证明了该问题是NP难的且不存在多项式时间近似方案(polynomial time approximation scheme),并提出了一种具有低时间复杂度的启发式算法。针对局部方法下的网络编码感知的信道调度问题,证明了该问题是NP难的,并提出了一种多项式时间近似方案及一种具有1／2近似率的贪婪算法。仿真实验结果表明所提算法相比于无网络编码的机制,能够极大地提高网络吞吐率。
(2)针对无线移动网络中数据传送性能优化,对具有常数复杂度的分块随机线性网络编码(简称分块码)方法进行了研究。首先证明了预编码(precoding)在分块码达到正码率中的不可或缺性。在预编码的前提下,对无重叠分块码的可达码率进行了紧(tight)的分析,并进一步地提出了采用扩展图(expander graph)生成重叠报文块的扩展分块码。通过基于树的分析以及扩展论证刻画了扩展分块码的可达码率,从而明确了扩展分块码是第一类具有非平凡性能保证的重叠分块码。数值分析结果显示扩展分块码性能接近最优,其可达码率极大地超出了无重叠分块码。此外,仿真实验结果表明,当输入报文个数有限时,扩展分块码相比于其他重叠分块码具有低得多的传输负载和解码错误概率。
(3)针对无线移动网络中数据广播性能优化,提出了一种新颖的基于随机线性网络编码的广播协议。该协议将需要广播的消息分割成多个子消息,并将子消息以随机线性网络编码的方式进行传输。随机线性网络编码的应用使得无线节点易于收集有效信息,从而减轻了因一个或多个节点过晚接收到消息所致的时延瓶颈。与此同时,节点传输采用了随机调度机制,即每一个网络节点随机独立地使用无线信道。随机调度的使用能够在利用无线媒介广播特性的同时,有效应对并发传输所致的冲突问题。理论分析表明,该协议在任意的节点移动速度下,均能够达到渐进最优的广播时延。相反地,纯粹的随机调度策略在节点快速移动时不足以达到最优性。
Due to the broadcast nature of wireless medium as well as the multi-hop network topologies, there are a lot of redundant packets in wireless networks, which affect the network performance directly. In recent years, it has been shown that network coding can be used to enhance the performance of wireless networks by exploiting the redundant packets. However, network coding incurs extra computational cost, and its performance gain is usually limited by the broadcast rate of wireless channels as well as the computational capabilities of wireless nodes, and also affected by the mobility of wireless nodes. Therefore, network coding schemes should be designed and applied to meet the requirements of these characteristics of wireless networks.
In this dissertation, we conduct a comprehensive study on the methods of efficient network coding in wireless networks considering the applications of network coding in multi-channel scenarios and for reliable data transmission and broadcast in wireless mobile networks. The contributions of this dissertation are summarized as follows:
(1) We investigate the network coding methods subject to the broadcast rate constraint in OFDMA relay networks. Considering the tradeoff between performance and overhead, we propose two approaches, global approach (GA) and local approach (LA) for the support of coding-aware scheduling decision making. For the coding-aware multi-channel scheduling problem, we show it is NP-hard under both the GA model and the LA model. For the GA model, we also show that it does not admit any polynomial time approximation scheme (PTAS), and then propose a heuristic algorithm with low time complexity, while for the LA model, we present a PTAS and also introduce a practical greedy algorithm with an approximation ratio of1/2. Simulation results show that both proposed practical algorithms can achieve significant throughput improvement over a state-of-the-art noncoding scheme.
(2) We investigate the methods for chunked random linear network codes (chunked codes) with a constant computational complexity for reliable data transmission in wireless mobile networks. We first highlight the importance of precoding for chunked codes to achieve non-vanishing rates, and then present a tight analysis on the achievable rates of non-overlapped chunked codes with precoding. We further introduce the first class of overlapped chunked codes with non-trivial performance guarantee, called expander chunked codes, which use expander graphs to form overlapped chunks, and then characterize their achievable rates using a tree-based analysis as well as some expander arguments. Numerical results reveal that expander chunked codes perform near-optimally, and achieve significantly higher rates than non-overlapped chunked codes. Also, simulation results show that for a finite number of input packets expander chunked codes incur much lower transmission overhead to recover the whole input packets than all other state-of-the-art chunked codes.
(3) We investigate the methods of data broadcast with network coding in wireless mobile networks by proposing a novel random linear network coding based broadcast protocol name R2. In this protocol, the message to be broadcast is divided into multiple mini-messages, while the mini-messages are transmitted in a fashion of random linear network coding. The use of random linear network coding makes nodes easier to accumulate useful information and thus mitigates the bottleneck for completing the broadcast process due to the very late reception of the message by one or more nodes. Meanwhile, R2employs random scheduling, that is, each network node uses the wireless channel randomly and independently, which on one hand exploits the broadcast nature of wireless medium and on the other hand combats the interference due to concurrent transmissions efficiently. Theoretical analyses show that R2performs optimally in terms of broadcast latency in order sense, no matter how fast nodes move around the network. In contrast, the pure random scheduling strategy is insufficient to achieve the order-optimality when nodes move very fast.
引文
[1]R. Ahlswede, N. Cai, S.-Y. Li, and R. W. Yeung, "Network information flow," IEEE Trans-actions on Information Theory, vol.46, no.4, pp.1204-1216,2000.
[2]M. Alicherry, R. Bhatia, and L. E. Li, "Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks," in Proc. ACM MobiCom,2005, pp. 58-72.
[3]R. Bhatia and L. Li, "Throughput optimization of wireless mesh networks with mimo links," in Proc. IEEE INFOCOM,2007, pp.2326-2330.
[4]S. Katti, S. Gollakota, and D. Katabi, "Embracing wireless interference:analog network coding," in Proc. ACM SIGCOMM, vol.37, no.4,2007, pp.397-408.
[5]S. Biswas and R. Morris, "Opportunistic routing in multi-hop wireless networks," ACM SIGCOMM Computer Communication Review, vol.34, no.1, pp.69-74,2004.
[6]D. S. Lun, M. Medard, R. Koetter, and M. Effros, "On coding for reliable communication over packet networks," Physical Communication, vol.1, no.1, pp.3-20,2008.
[7]S.-Y. Li, R. W. Yeung, and N. Cai, "Linear network coding," IEEE Transactions on Infor-mation Theory, vol.49, no.2, pp.371-381,2003.
[8]R. Koetter and M. Medard, "An algebraic approach to network coding," IEEE/ACM Trans-actions on Networking, vol.11, no.5, pp.782-795,2003.
[9]S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. M. Tolhuizen, "Poly-nomial time algorithms for multicast network code construction," IEEE Transactions on Information Theory, vol.51, no.6, pp.1973-1982,2005.
[10]T. Ho, R. Koetter, M. Medard, D. Karger, and M. Effros, "The benefits of coding over routing in a randomized setting," in Proc. IEEE ISIT,2003, p.442.
[11]T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, "A random linear network coding approach to multicast," IEEE Transactions on Information Theory, vol.52, no.10, pp.4413-4430,2006.
[12]E. Erez and M. Feder, "Efficient network code design for cyclic, networks," IEEE Transactions on Information Theory, vol.56, no.8, pp.3862-3878,2010.
[13]C. Fragouli and E. Soljanin, "Information flow decomposition for network coding," IEEE Transactions on Information Theory, vol.52, no.3, pp.829-848,2006.
[14]A. I. Barbero and (?). Ytrehus, "Cycle-logical treatment for "cyclopathic" networks," IEEE/ACM Transactions on Networking, vol.14, no. SI, pp.2795-2804,2006.
[15]S.-Y. Li and S. T. Ho, "Ring-theoretic foundation of convolutional network coding," in Proc. IEEE NetCod,2008, pp.1-6.
[16]M. Medard, M. Effros, D. Karger, and T. Ho, "On coding for non-multicast networks," in Proc. Allerton, vol.41, no.1,2003, pp.21-29.
[17]A. R. Lehman and E. Lehman, "Complexity classification of network information flow prob-lems," in Proc. ACM-SIAM SODA,2004, pp.142-150.
[18]S. Riis, "Linear versus non-linear boolean functions in network flow," in Proc. IEEE CISS, 2004.
[19]R. Dougherty, C. Fretting, and K. Zeger, "Insufficiency of linear coding in network information flow," IEEE Transactions on Information Theory, vol.51, no.8, pp.2745-2759,2005.
[20]T. H. Chan, "On the optimality of group network codes," in Proc. IEEE ISIT,2005, pp. 1992-1996.
[21]S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, "Xors in the air: practical wireless network coding," in Proc. ACM SIGCOMM, vol.36, no.4,2006, pp.243-254.
[22]S. Rayanchu, S. Sen, J. Wu, S. Banerjee, and S. Sengupta, "Loss-aware network coding for unicast wireless sessions:design, implementation, and performance evaluation," in Proc. ACM SIGMETRICS, vol.36, no.1,2008, pp.85-96.
[23]Q. Dong, J. Wu, W. Hu, and J. Crowcroft, "Practical network coding in wireless networks," in Proc. ACM MobiCom,2007, pp.306-309.
[24]S. Sengupta, S. Rayanchu, and S. Banerjee, "An analysis of wireless network coding for unicast sessions:The case for coding-aware routing," in Proc. IEEE INFOCOM,2007, pp. 1028-1036.
[25]J. Le, J. C. Lui, and D.-M. Chiu, "Dcar:Distributed coding-aware routing in wireless net-works," IEEE Transactions on Mobile Computing, vol.9, no.4, pp.596-608,2010.
[26]P. Chaporkar and A. Proutiere, "Adaptive network coding and scheduling for maximizing throughput in wireless networks," in Proc. ACM MobiCom,2007, pp.135-146.
[27]J. Liu, D. Goeckel, and D. Towsley, "Bounds on the gain of network coding and broadcasting in wireless networks," in Proc. IEEE INFOCOM,2007, pp.724-732.
[28]J. Le, J. C. Lui, and D. M. Chiu, "How many packets can we encode?-an analysis of practical wireless network coding," in Proc. IEEE INFOCOM,2008, pp.371-375.
[29]D. Nguyen, T. Tran, T. Nguyen, and B. Bose, "Wireless broadcast using network coding," IEEE Transactions on Vehicular Technology, vol.58, no.2, pp.914-925,2009.
[30]L. Li, R. Ramjee, M. Buddhikot, and S. Miller, "Network coding-based broadcast in mobile ad-hoc networks," in Proc. IEEE INFOCOM,2007, pp.1739-1747.
[31]X. Zhang and B. Li, "Network-coding-aware dynamic subcarrier assignment in ofdma-based wireless networks," IEEE Transactions on Vehicular Technology, vol.60, no.9, pp.4609-4619,2011.
[32]H. Xu and B. Li, "Xor-assisted cooperative diversity in ofdma wireless networks:optimization framework and approximation algorithms," in Proc. IEEE INFOCOM,2009, pp.2141-2149.
[33]Y. Xu, J. Lui, and D.-M. Chiu, "Analysis and scheduling of practical network coding in ofdma relay networks," Computer Networks, vol.53, no.12, pp.2120-2139,2009.
[34]Y. Liu, M. Tao, B. Li, and H. Shen, "Optimization framework and graph-based approach for relay-assisted bidirectional ofdma cellular networks," IEEE Transactions on Wireless Communications, vol.9, no.11, pp.3490-3500,2010.
[35]B.-G. Kim and J.-W. Lee, "Opportunistic resource scheduling for ofdma networks with net-work coding at relay stations," IEEE Transactions on Wireless Communications, vol.11, no.1, pp.210-221,2012.
[36]C. Gkantsidis and P. R. Rodriguez, "Network coding for large scale content distribution," in Proc. IEEE INFOCOM, vol.4,2005, pp.2235-2245.
[37]M. Wang and B. Li, "How practical is network coding?" in Proc. IEEE IWQoS,2006, pp. 274-278.
[38]D. M. Chiu, R. W. Yeung, J. Huang, and B. Fan, "Can network coding help in p2p networks?" in Proc. IEEE WiOpt,2006, pp.1-5.
[39]R. W. Yeung, "Avalanche:A network coding analysis," Communications in Information & Systems, vol.7, no.4, pp.353-358,2007.
[40]M. Wang and B. Li, "R2:Random push with random network coding in live peer-to-peer streaming," IEEE Journal on Selected Areas in Communications, vol.25, no.9, pp.1655-1666,2007.
[41]Z. Liu, C. Wu, B. Li, and S. Zhao, "Uusee:large-scale operational on-demand streaming with random network coding," in Proc. IEEE INFOCOM,2010, pp.1-9.
[42]L. Keller, A. Le, B. Cici, H. Seferoglu, C. Fragouli, and A. Markopoulou, "Microcast:Coop-erative video streaming on smartphones," in Proc. ACM SenSys,2012, pp.57-70.
[43]N. Abedini, S. Sampath, R. Bhattacharyya, S. Paul, and S. Shakkottai, "Realtime streaming with guaranteed qos over wireless d2d networks," in Proc. ACM MobiHoc,2013, pp.197-206.
[44]S. Deb, M. Medard, and C. Choute, "On random network coding based information dissem-ination," in Proc. IEEE ISIT,2005, pp.278-282.
[45]S. Deb, M. Medard, and C. Choute, "Algebraic gossip:A network coding approach to optimal multiple rumor mongering," IEEE Transactions on Information Theory, vol.52, no.6, pp. 2486-2507,2006.
[46]D. Mosk-Aoyama and D. Shah, "Information dissemination via network coding," in Proc. IEEE ISIT,2006, pp.1748-1752.
[47]M. Borokhovich, C. Avin, and Z. Lotker, "Tight bounds for algebraic gossip on graphs," in Proc. IEEE ISIT,2010, pp.1758-1762.
[48]C. Avin, M. Borokhovich, K. Censor-Hillel, and Z. Lotker, "Order optimal information spreading using algebraic gossip," in Proc. ACM SIGACT-SIGOPS PODC,2011, pp.363-372.
[49]B. Haeupler, "Analyzing network coding gossip made easy," in Proc. ACM STOC,2011, pp. 293-302.
[50]B. Haeupler and D. Karger, "Faster information dissemination in dynamic networks via network coding," in Proc. ACM SIGACT-SIGOPS PODC,2011, pp.381-390.
[51]S. Chachulski, M. Jennings, S. Katti, and D. Katabi, "Trading structure for randomness in wireless opportunistic routing," in Proc. ACM SIGCOMM,2007, pp.169-180.
[52]S. Chachulski, Trading structure for randomness in wireless opportunistic routing. M.S. Thesis,2007.
[53]Y. Li, W. Chen, and Z.-L. Zhang, "Optimal forwarder list selection in opportunistic routing," in Proc. IEEE MASS,2009, pp.670-675.
[54]R. Laufer, H. Dubois-Ferriere, and L. Kleinrock, "Multirate anypath routing in wireless mesh networks," in Proc. IEEE INFOCOM,2009, pp.37-45.
[55]C. Gkantsidis, W. Hu, P. Key, B. Radunovic, P. Rodriguez, and S. Gheorghiu, "Multipath code casting for wireless mesh networks," in Proc. ACM CoNEXT,2007, p.10.
[56]X. Zhang and B. Li, "Optimized multipath network coding in lossy wireless networks," IEEE Journal on Selected Areas in Communications, vol.27, no.5, pp.622-634,2009.
[57]B. Radunovic, C. Gkantsidis, P. Key, and P. Rodriguez, "An optimization framework for opportunistic multipath routing in wireless mesh networks," in Proc. IEEE INFOCOM, 2008, pp.2252-2260.
[58]Y. Lin, B. Li, and B. Liang, "Codeor:Opportunistic routing in wireless mesh networks with segmented network coding," in Proc. IEEE ICNP,2008, pp.13-22.
[59]J. K. Sundararajan, D. Shah, M. Medard, S. Jakubczak, M. Mitzenmacher, and J. Barros, "Network coding meets tcp:Theory and implementation," Proceedings of the IEEE, vol.99, no.3, pp.490-512,2011.
[60]Y. Lin, B. Liang, and B. Li, "Slideor:Online opportunistic network coding in wireless mesh networks," in Proc. IEEE INFOCOM,2010, pp.1-5.
[61]D. Koutsonikolas, C.-C. Wang, and Y. C. Hu, "Efficient network-coding-based opportunistic routing through cumulative coded acknowledgments," IEEE/ACM Transactions on Network-ing, vol.19, no.5, pp.1368-1381,2011.
[62]X. Zhang, G. Neglia, J. Kurose, and D. Towsley, "On the benefits of random linear coding for unicast applications in disruption tolerant networks," in Proc. IEEE WiOpt,2006, pp. 1-7.
[63]Y. Lin, B. Li, and B. Liang, "Stochastic analysis of network coding in epidemic routing," IEEE Journal on Selected Areas in Communications, vol.26, no.5, pp.794-808,2008.
[64]Z. Li, D. Zeng, S. Guo, S. Lu, D. Chen, and W. Zhuang, "On the throughput of feedback-less segmented network coding in delay tolerant networks," IEEE Wireless Communication Letters, vol.1, no.2, pp.93-96,2012.
[65]P. Maymounkov, N. J. Harvey, and D. S. Lun, "Methods for efficient network coding," in Proc. Allerton, vol.6,2006.
[66]D. Silva, W. Zeng, and F. R. Kschischang, "Sparse network coding with overlapping classes," in Proc. IEEE NetCod,2009, pp.74-79.
[67]A. Heidarzadeh and A. H. Banihashemi, "Overlapped chunked network coding," in Proc. IEEE ITW,2010, pp.1-5.
[68]Y. Li, E. Soljanin, and P. Spasojevic, "Effects of the generation size and overlap on through-put and complexity in randomized linear network coding," IEEE Transactions on Informa-tion Theory, vol.57, no.2, pp.1111-1123,2011.
[69]M. Luby, "LT codes," in Proc. IEEE FOCS,2002, pp.271-280.
[70]A. Shokrollahi, "Raptor codes," IEEE Transactions on Information Theory, vol.52, no.6, pp.2551-2567,2006.
[71]S. Yang and R. W. Yeung, "Coding for a network coded fountain," in Proc. IEEE ISIT, 2011, pp.2647-2651.
[72]——, "Batched sparse codes," arXiv preprint arXiv:1206.5365,2012.
[73]K. Mahdaviani, M. Ardakani, H. Bagheri, and C. Tellambura, "Gamma codes:A low-overhead linear-complexity network coding solution," in Proc. IEEE NetCod,2012, pp.125-130.
[74]K. Mahdaviani, R. Yazdani, and M. Ardakani, "Overhead-optimized gamma network codes," in Proc. IEEE NetCod,2013.
[75]——, "Linear-complexity overhead-optimized random linear network codes," arXiv preprint arXiv:1311.2123,2013.
[76]S. Yang and R. W. Yeung, "Large file transmission in network-coded networks with packet loss:a performance perspective," in Proc. ACM ISABEL,2011, p.117.
[77]H. Yin and S. Alamouti, "Ofdma:A broadband wireless access technology," in IEEE Sarnoff Symposium,2006, pp.1-4.
[78]"802.16:Air interface for broadband wireless access systems," 2009.
[79]"3GPP, LTE release 10 and beyond (LTE advanced)." [Online]. Available: http://www.3gpp.org/LTE-Advanced,
[80]K. Sundaresan and S. Rangarajan, "On exploiting diversity and spatial reuse in relay-enabled wireless networks," in Proc. ACM MobiHoc,2008, pp.13-22.
[81]H. J. Kushner and P. A. Whiting, "Convergence of proportional-fair sharing algorithms under general conditions," IEEE Transactions on Wireless Communications, vol.3, no.4, pp.1250-1259,2004.
[82]C. Y. Wong, R. S. Cheng, K. B. Lataief, and R. D. Murch, "Multiuser ofdm with adaptive subcarrier, bit, and power allocation," IEEE Journal on Selected Areas in Communications, vol.17, no.10, pp.1747-1758,1999.
[83]D. Kivanc, G. Li, and H. Liu,"Computationally efficient bandwidth allocation and power control for ofdma," IEEE Transactions on Wireless Communications, vol.2, no.6, pp.1150-1158,2003.
[84]M. Ergen, S. Coleri, and P. Varaiya, "Qos aware adaptive resource allocation techniques for fair scheduling in ofdma based broadband wireless access systems," IEEE Transactions on Broadcasting, vol.49, no.4, pp.362-370,2003.
[85]M. Andrews and L. Zhang, "Scheduling algorithms for multi-carrier wireless data systems," in Proc. ACM MobiCom,2007, pp.3-14.
[86]S. Bodas, S. Shakkottai, L. Ying, and R. Srikant, "Low-complexity scheduling algorithms for multichannel downlink wireless networks," IEEE/ACM Transactions on Networking, vol.20, no.5, pp.1608-1621,2012.
[87]K. Sundaresan, X. Wang, and M. Madihian, "Low-overhead scheduling algorithms for ofdma relay networks," in Proc. ACM WiCON,2008, p.24.
[88]S. Deb, V. Mhatre, and V. Ramaiyan, "Wimax relay networks:opportunistic scheduling to exploit multiuser diversity and frequency selectivity," in Proc. ACM MobiCom,2008, pp. 163-174.
[89]C.-Y. Hong and A.-C. Pang, "Link scheduling with qos guarantee for wireless relay networks," in Proc. IEEE INFOCOM,2009, pp.2806-2810.
[90]R. Draves, J. Padhye, and B. Zill, "Routing in multi-radio, multi-hop wireless mesh network-s," in Proc. ACM MobiCom,2004, pp.114-128.
[91]T.-D. Nguyen and Y. Han, "A proportional fairness algorithm with qos provision in downlink ofdma systems," IEEE Communications Letters, vol.10, no.11, pp.760-762,2006.
[92]Y. Ma, "Rate maximization for downlink ofdma with proportional fairness," IEEE Transac-tions on Vehicular Technology, vol.57, no.5, pp.3267-3274,2008.
[93]O. Oyman, "Ofdm2a:A centralized resource allocation policy for cellular multi-hop net-works," in Proc. IEEE ACSSC,2006, pp.656-660.
[94]V. V. Vazirani, Approximation algorithms, springer,2001.
[95]L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Transac-tions on Automatic Control, vol.37, no.12, pp.1936-1948,1992.
[96]M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, P. Whiting, and R. Vijayakumar, "Providing quality of service over a shared wireless link," IEEE Communications Magazine, vol.39, no.2, pp.150-154,2001.
[97]M. J. Neely, E. Modiano, and C. E. Rohrs, "Power and server allocation in a multi-beam satellite with time varying channels," in Proc. IEEE INFOCOM, vol.3,2002, pp.1451-1460.
[98]A. M. Frieze and M. Clarke, "Approximation algorithms for the (?), mj/i(?)-dimensional 0-1 knapsack problem:Worst-case and probabilistic analyses," European Journal of Operational Research, vol.15, no.1, pp.100-109,1984.
[99]D. B. Shmoys and E. Tardos, "An approximation algorithm for the generalized assignment problem," Mathematical Programming, vol.62, no.1-3, pp.461-474,1993.
[100]S.-C. Fang and S. Puthenpura, Linear optimization and extensions:theory and algorithms, 1993.
[101]M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, "An analysis of approximations for maximizing submodular set functions-ii," in Polyhedral combinatorics,1978, pp.73-87.
[102]J. Gross, H.-F. Geerdes, H. Karl, and A. Wolisz, "Performance analysis of dynamic ofdma systems with inband signaling," IEEE Journal on Selected Areas in Communications, vol.24, no.3, pp.427-436,2006.
[103]J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva, "A performance comparison of multi-hop wireless ad hoc network routing protocols," in Proc. ACM MobiCom. ACM, 1998, pp.85-97.
[104]J. K. Cavers, Mobile channel characteristics. Springer,2000.
[105]Y. Wu, "A trellis connectivity analysis of random linear network coding with buffering," in Proc. IEEE ISIT,2006, pp.768-772.
[106]P. A. Chou, Y. Wu, and K. Jain, "Practical network coding," in Proc. Allerton,2003.
[107]Y. Li, W.-Y. Chan, and S. D. Blostein, "Network coding with unequal size overlapping generations," in Proc. IEEE NetCod,2012, pp.161-166.
[108]S. Yang, S.-W. Ho, J. Meng, E.-h. Yang, and R. W. Yeung, "On linear operator channels over finite fields," arXiv preprint arXiv:1002.2293,2010.
[109]D. J. Newman, "The double dixie cup problem," The American Mathematical Monthly, vol.67, no.1, pp.58-61,1960.
[110]L. Flatto, "Limit theorems for some random variables associated with urn models," The Annals of Probability, vol.10, no.4, pp.927-934,1982.
[111]M. Mitzenmacher and E. Upfal, Probability and computing:Randomized algorithms and probabilistic analysis. Cambridge University Press,2005.
[112]M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, "Efficient erasure correcting codes," IEEE Transactions on Information Theory, vol.47, no.2, pp.569-584, 2001.
[113]P. Oswald and A. Shokrollahi, "Capacity-achieving sequences for the erasure channel," IEEE Transactions on Information Theory, vol.48, no.12, pp.3017-3028,2002.
[114]S. Hoory, N. Linial, and A. Wigderson, "Expander graphs and their applications," Bulletin of the American Mathematical Society, vol.43, no.4, pp.439-561,2006.
[115]N. C. Wormald, "Models of random regular graphs," London Mathematical Society Lecture Note Series, pp.239-298,1999.
[116]G. A. Margulis, "Explicit constructions of concentrators," Problemy Peredachi Informatsii, vol.9, no.4, pp.71-80,1973.
[117]O. Reingold, S. Vadhan, and A. Wigderson, "Entropy waves, the zig-zag graph product, and new constant-degree expanders," Annals of Mathematics, pp.157-187,2002.
[118]B. D. McKay and N. C. Wormald, "Uniform generation of random regular graphs of moderate degree," Journal of Algorithms, vol.11, no.1, pp.52-67,1990.
[119]B. D. McKay, N. C. Wormald, and B. Wysocka, "Short cycles in random regular graphs," The Electronic Journal of Combinatorics, vol.11, no.1,2004.
[120]A. Nilli, "On the second eigenvalue of a graph," Discrete Mathematics, vol.91, no.2, pp. 207-210,1991.
[121]J. Friedman, "A proof of alon's second eigenvalue conjecture," in Proc. ACM STOC,2003, pp.720-724.
[122]N. Alon and F. R. Chung, "Explicit construction of linear sized tolerant networks," Discrete Mathematics, vol.72, no.1, pp.15-19,1988.
[123]R. Bar-Yehuda, O. Goldreich, and A. Itai, "On the time-complexity of broadcast in multi-hop radio networks:An exponential gap between determinism and randomization," Journal of Computer and System Sciences, vol.45, no.1, pp.104-126,1992.
[124]Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, "The broadcast storm problem in a mobile ad hoc network," Wireless networks, vol.8, no.2-3, pp.153-167,2002.
[125]Z. J. Haas, J. Y. Halpern, and L. Li, "Gossip-based ad hoc routing," IEEE/ACM Transac-tions on Networking, vol.14, no.3, pp.479-491,2006.
[126]I. Chlamtac and S. Kutten, "On broadcasting in radio networks-problem analysis and pro-tocol design," IEEE Transactions on Communications, vol.33, no.12, pp.1240-1246,1985.
[127]I. Chlamtac, "The wave expansion approach to broadcasting in multihop radio networks," IEEE Transactions on Communications, vol.39, no.3, pp.426-433,1991.
[128]A. Czumaj and W. Rytter, "Broadcasting algorithms in radio networks with unknown topol-ogy," Journal of Algorithms, vol.60, no.2, pp.115-143,2006.
[129]D. R. Kowalski and A. Pelc, "Broadcasting in undirected ad hoc radio networks," Distributed Computing, vol.18, no.1, pp.43-57,2005.
[130]L. Gasieniec, D. Peleg, and Q. Xin, "Faster communication in known topology radio net-works," Distributed Computing, vol.19, no.4, pp.289-300,2007.
[131]D. R. Kowalski and A. Pelc, "Optimal deterministic broadcasting in known topology radio networks," Distributed Computing, vol.19, no.3, pp.185-195,2007.
[132]M. Ghaffari, B. Haeupler, and M. Khabbazian, "Randomized broadcast in radio networks with collision detection," in Proc. ACM PODC,2013, pp.325-334.
[133]D. Peleg, "Time-efficient broadcasting in radio networks:a review," in Distributed Computing and Internet Technology,2007, pp.1-18.
[134]R. Gandhi, A. Mishra, and S. Parthasarathy, "Minimizing broadcast latency and redundancy in ad hoc networks," IEEE/ACM Transactions on Networking, vol.16, no.4, pp.840-851, 2008.
[135]S.-H. Huang, P.-J. Wan, X. Jia, H. Du, and W. Shang, "Minimum-latency broadcast schedul-ing in wireless ad hoc networks," in Proc. IEEE INFOCOM,2007, pp.733-739.
[136]R. Mahjourian, F. Chen, R. Tiwari, H. Zhai, and Y. Fang, "An approximation algorithm for conflict-aware broadcast scheduling in wireless ad hoc networks," in Proc. IEEE MobiHoc, 2008, pp.331-340.
[137]R. Gandhi, Y.-A. Kim, S. Lee, J. Ryu, and P.-J. Wan, "Approximation algorithms for data broadcast in wireless networks," IEEE Transactions on Mobile Computing, vol.11, no.7, pp.1237-1248,2012.
[138]Z. Kong and E. M. Yeh, "On the latency for information dissemination in mobile wireless networks," in Proc. ACM MobiHoc,2008, pp.139-148.
[139]A. Pettarin, A. Pietracaprina, G. Pucci, and E. Upfal, "Tight bounds on information dis-semination in sparse mobile networks," in Proc. ACM SIGACT-SIGOPS PODC,2011, pp. 355-362.
[140]A. Clementi, A. Monti, F. Pasquale, and R. Silvestri, "Information spreading in stationary markovian evolving graphs," IEEE Transactions on Parallel and Distributed Systems, vol.22, no.9, pp.1425-1432,2011.
[141]A. Clementi, F. Pasquale, and R. Silvestri, "Opportunistic manets:Mobility can make up for low transmission power," IEEE/ACM Transactions on Networking, vol.21, no.2, pp. 610-620,2013.
[142]A. E. Clementi and R. Silvestri, "Parsimonious flooding in geometric random-walks," in Distributed Computing,2011, pp.298-310.
[143]Y. Chen, S. Shakkottai, and J. Andrews, "On the role of mobility for multi-message gossip," IEEE Transactions on Information Theory, vol.59, no.6, pp.3953-3970,2012.
[144]M. Penrose, Random geometric graphs. Oxford University Press Oxford,2003.
[145]P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, vol.46, no.2, pp.388-404,2000.
[146]——, "Critical power for asymptotic connectivity," in Proc. IEEE CDC,1998, pp.547-566.
[147]C. Avin and G. Ercal, "On the cover time and mixing time of random geometric graphs," Theoretical Computer Science, vol.380, no.1, pp.2-22,2007.
[148]D. E. Knuth, The art of computer programming, volume 2:seminumerical algorithms. Read-ing, Mass.:Addison-Wesley,1981.
[149]Wikipedia, "Poisson distribution-wikipedia, the free encyclopedia," 2013. [Online]. Available:http://en.wikipedia.org/
[2]M. Alicherry, R. Bhatia, and L. E. Li, "Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks," in Proc. ACM MobiCom,2005, pp. 58-72.
[3]R. Bhatia and L. Li, "Throughput optimization of wireless mesh networks with mimo links," in Proc. IEEE INFOCOM,2007, pp.2326-2330.
[4]S. Katti, S. Gollakota, and D. Katabi, "Embracing wireless interference:analog network coding," in Proc. ACM SIGCOMM, vol.37, no.4,2007, pp.397-408.
[5]S. Biswas and R. Morris, "Opportunistic routing in multi-hop wireless networks," ACM SIGCOMM Computer Communication Review, vol.34, no.1, pp.69-74,2004.
[6]D. S. Lun, M. Medard, R. Koetter, and M. Effros, "On coding for reliable communication over packet networks," Physical Communication, vol.1, no.1, pp.3-20,2008.
[7]S.-Y. Li, R. W. Yeung, and N. Cai, "Linear network coding," IEEE Transactions on Infor-mation Theory, vol.49, no.2, pp.371-381,2003.
[8]R. Koetter and M. Medard, "An algebraic approach to network coding," IEEE/ACM Trans-actions on Networking, vol.11, no.5, pp.782-795,2003.
[9]S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. M. Tolhuizen, "Poly-nomial time algorithms for multicast network code construction," IEEE Transactions on Information Theory, vol.51, no.6, pp.1973-1982,2005.
[10]T. Ho, R. Koetter, M. Medard, D. Karger, and M. Effros, "The benefits of coding over routing in a randomized setting," in Proc. IEEE ISIT,2003, p.442.
[11]T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, "A random linear network coding approach to multicast," IEEE Transactions on Information Theory, vol.52, no.10, pp.4413-4430,2006.
[12]E. Erez and M. Feder, "Efficient network code design for cyclic, networks," IEEE Transactions on Information Theory, vol.56, no.8, pp.3862-3878,2010.
[13]C. Fragouli and E. Soljanin, "Information flow decomposition for network coding," IEEE Transactions on Information Theory, vol.52, no.3, pp.829-848,2006.
[14]A. I. Barbero and (?). Ytrehus, "Cycle-logical treatment for "cyclopathic" networks," IEEE/ACM Transactions on Networking, vol.14, no. SI, pp.2795-2804,2006.
[15]S.-Y. Li and S. T. Ho, "Ring-theoretic foundation of convolutional network coding," in Proc. IEEE NetCod,2008, pp.1-6.
[16]M. Medard, M. Effros, D. Karger, and T. Ho, "On coding for non-multicast networks," in Proc. Allerton, vol.41, no.1,2003, pp.21-29.
[17]A. R. Lehman and E. Lehman, "Complexity classification of network information flow prob-lems," in Proc. ACM-SIAM SODA,2004, pp.142-150.
[18]S. Riis, "Linear versus non-linear boolean functions in network flow," in Proc. IEEE CISS, 2004.
[19]R. Dougherty, C. Fretting, and K. Zeger, "Insufficiency of linear coding in network information flow," IEEE Transactions on Information Theory, vol.51, no.8, pp.2745-2759,2005.
[20]T. H. Chan, "On the optimality of group network codes," in Proc. IEEE ISIT,2005, pp. 1992-1996.
[21]S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, "Xors in the air: practical wireless network coding," in Proc. ACM SIGCOMM, vol.36, no.4,2006, pp.243-254.
[22]S. Rayanchu, S. Sen, J. Wu, S. Banerjee, and S. Sengupta, "Loss-aware network coding for unicast wireless sessions:design, implementation, and performance evaluation," in Proc. ACM SIGMETRICS, vol.36, no.1,2008, pp.85-96.
[23]Q. Dong, J. Wu, W. Hu, and J. Crowcroft, "Practical network coding in wireless networks," in Proc. ACM MobiCom,2007, pp.306-309.
[24]S. Sengupta, S. Rayanchu, and S. Banerjee, "An analysis of wireless network coding for unicast sessions:The case for coding-aware routing," in Proc. IEEE INFOCOM,2007, pp. 1028-1036.
[25]J. Le, J. C. Lui, and D.-M. Chiu, "Dcar:Distributed coding-aware routing in wireless net-works," IEEE Transactions on Mobile Computing, vol.9, no.4, pp.596-608,2010.
[26]P. Chaporkar and A. Proutiere, "Adaptive network coding and scheduling for maximizing throughput in wireless networks," in Proc. ACM MobiCom,2007, pp.135-146.
[27]J. Liu, D. Goeckel, and D. Towsley, "Bounds on the gain of network coding and broadcasting in wireless networks," in Proc. IEEE INFOCOM,2007, pp.724-732.
[28]J. Le, J. C. Lui, and D. M. Chiu, "How many packets can we encode?-an analysis of practical wireless network coding," in Proc. IEEE INFOCOM,2008, pp.371-375.
[29]D. Nguyen, T. Tran, T. Nguyen, and B. Bose, "Wireless broadcast using network coding," IEEE Transactions on Vehicular Technology, vol.58, no.2, pp.914-925,2009.
[30]L. Li, R. Ramjee, M. Buddhikot, and S. Miller, "Network coding-based broadcast in mobile ad-hoc networks," in Proc. IEEE INFOCOM,2007, pp.1739-1747.
[31]X. Zhang and B. Li, "Network-coding-aware dynamic subcarrier assignment in ofdma-based wireless networks," IEEE Transactions on Vehicular Technology, vol.60, no.9, pp.4609-4619,2011.
[32]H. Xu and B. Li, "Xor-assisted cooperative diversity in ofdma wireless networks:optimization framework and approximation algorithms," in Proc. IEEE INFOCOM,2009, pp.2141-2149.
[33]Y. Xu, J. Lui, and D.-M. Chiu, "Analysis and scheduling of practical network coding in ofdma relay networks," Computer Networks, vol.53, no.12, pp.2120-2139,2009.
[34]Y. Liu, M. Tao, B. Li, and H. Shen, "Optimization framework and graph-based approach for relay-assisted bidirectional ofdma cellular networks," IEEE Transactions on Wireless Communications, vol.9, no.11, pp.3490-3500,2010.
[35]B.-G. Kim and J.-W. Lee, "Opportunistic resource scheduling for ofdma networks with net-work coding at relay stations," IEEE Transactions on Wireless Communications, vol.11, no.1, pp.210-221,2012.
[36]C. Gkantsidis and P. R. Rodriguez, "Network coding for large scale content distribution," in Proc. IEEE INFOCOM, vol.4,2005, pp.2235-2245.
[37]M. Wang and B. Li, "How practical is network coding?" in Proc. IEEE IWQoS,2006, pp. 274-278.
[38]D. M. Chiu, R. W. Yeung, J. Huang, and B. Fan, "Can network coding help in p2p networks?" in Proc. IEEE WiOpt,2006, pp.1-5.
[39]R. W. Yeung, "Avalanche:A network coding analysis," Communications in Information & Systems, vol.7, no.4, pp.353-358,2007.
[40]M. Wang and B. Li, "R2:Random push with random network coding in live peer-to-peer streaming," IEEE Journal on Selected Areas in Communications, vol.25, no.9, pp.1655-1666,2007.
[41]Z. Liu, C. Wu, B. Li, and S. Zhao, "Uusee:large-scale operational on-demand streaming with random network coding," in Proc. IEEE INFOCOM,2010, pp.1-9.
[42]L. Keller, A. Le, B. Cici, H. Seferoglu, C. Fragouli, and A. Markopoulou, "Microcast:Coop-erative video streaming on smartphones," in Proc. ACM SenSys,2012, pp.57-70.
[43]N. Abedini, S. Sampath, R. Bhattacharyya, S. Paul, and S. Shakkottai, "Realtime streaming with guaranteed qos over wireless d2d networks," in Proc. ACM MobiHoc,2013, pp.197-206.
[44]S. Deb, M. Medard, and C. Choute, "On random network coding based information dissem-ination," in Proc. IEEE ISIT,2005, pp.278-282.
[45]S. Deb, M. Medard, and C. Choute, "Algebraic gossip:A network coding approach to optimal multiple rumor mongering," IEEE Transactions on Information Theory, vol.52, no.6, pp. 2486-2507,2006.
[46]D. Mosk-Aoyama and D. Shah, "Information dissemination via network coding," in Proc. IEEE ISIT,2006, pp.1748-1752.
[47]M. Borokhovich, C. Avin, and Z. Lotker, "Tight bounds for algebraic gossip on graphs," in Proc. IEEE ISIT,2010, pp.1758-1762.
[48]C. Avin, M. Borokhovich, K. Censor-Hillel, and Z. Lotker, "Order optimal information spreading using algebraic gossip," in Proc. ACM SIGACT-SIGOPS PODC,2011, pp.363-372.
[49]B. Haeupler, "Analyzing network coding gossip made easy," in Proc. ACM STOC,2011, pp. 293-302.
[50]B. Haeupler and D. Karger, "Faster information dissemination in dynamic networks via network coding," in Proc. ACM SIGACT-SIGOPS PODC,2011, pp.381-390.
[51]S. Chachulski, M. Jennings, S. Katti, and D. Katabi, "Trading structure for randomness in wireless opportunistic routing," in Proc. ACM SIGCOMM,2007, pp.169-180.
[52]S. Chachulski, Trading structure for randomness in wireless opportunistic routing. M.S. Thesis,2007.
[53]Y. Li, W. Chen, and Z.-L. Zhang, "Optimal forwarder list selection in opportunistic routing," in Proc. IEEE MASS,2009, pp.670-675.
[54]R. Laufer, H. Dubois-Ferriere, and L. Kleinrock, "Multirate anypath routing in wireless mesh networks," in Proc. IEEE INFOCOM,2009, pp.37-45.
[55]C. Gkantsidis, W. Hu, P. Key, B. Radunovic, P. Rodriguez, and S. Gheorghiu, "Multipath code casting for wireless mesh networks," in Proc. ACM CoNEXT,2007, p.10.
[56]X. Zhang and B. Li, "Optimized multipath network coding in lossy wireless networks," IEEE Journal on Selected Areas in Communications, vol.27, no.5, pp.622-634,2009.
[57]B. Radunovic, C. Gkantsidis, P. Key, and P. Rodriguez, "An optimization framework for opportunistic multipath routing in wireless mesh networks," in Proc. IEEE INFOCOM, 2008, pp.2252-2260.
[58]Y. Lin, B. Li, and B. Liang, "Codeor:Opportunistic routing in wireless mesh networks with segmented network coding," in Proc. IEEE ICNP,2008, pp.13-22.
[59]J. K. Sundararajan, D. Shah, M. Medard, S. Jakubczak, M. Mitzenmacher, and J. Barros, "Network coding meets tcp:Theory and implementation," Proceedings of the IEEE, vol.99, no.3, pp.490-512,2011.
[60]Y. Lin, B. Liang, and B. Li, "Slideor:Online opportunistic network coding in wireless mesh networks," in Proc. IEEE INFOCOM,2010, pp.1-5.
[61]D. Koutsonikolas, C.-C. Wang, and Y. C. Hu, "Efficient network-coding-based opportunistic routing through cumulative coded acknowledgments," IEEE/ACM Transactions on Network-ing, vol.19, no.5, pp.1368-1381,2011.
[62]X. Zhang, G. Neglia, J. Kurose, and D. Towsley, "On the benefits of random linear coding for unicast applications in disruption tolerant networks," in Proc. IEEE WiOpt,2006, pp. 1-7.
[63]Y. Lin, B. Li, and B. Liang, "Stochastic analysis of network coding in epidemic routing," IEEE Journal on Selected Areas in Communications, vol.26, no.5, pp.794-808,2008.
[64]Z. Li, D. Zeng, S. Guo, S. Lu, D. Chen, and W. Zhuang, "On the throughput of feedback-less segmented network coding in delay tolerant networks," IEEE Wireless Communication Letters, vol.1, no.2, pp.93-96,2012.
[65]P. Maymounkov, N. J. Harvey, and D. S. Lun, "Methods for efficient network coding," in Proc. Allerton, vol.6,2006.
[66]D. Silva, W. Zeng, and F. R. Kschischang, "Sparse network coding with overlapping classes," in Proc. IEEE NetCod,2009, pp.74-79.
[67]A. Heidarzadeh and A. H. Banihashemi, "Overlapped chunked network coding," in Proc. IEEE ITW,2010, pp.1-5.
[68]Y. Li, E. Soljanin, and P. Spasojevic, "Effects of the generation size and overlap on through-put and complexity in randomized linear network coding," IEEE Transactions on Informa-tion Theory, vol.57, no.2, pp.1111-1123,2011.
[69]M. Luby, "LT codes," in Proc. IEEE FOCS,2002, pp.271-280.
[70]A. Shokrollahi, "Raptor codes," IEEE Transactions on Information Theory, vol.52, no.6, pp.2551-2567,2006.
[71]S. Yang and R. W. Yeung, "Coding for a network coded fountain," in Proc. IEEE ISIT, 2011, pp.2647-2651.
[72]——, "Batched sparse codes," arXiv preprint arXiv:1206.5365,2012.
[73]K. Mahdaviani, M. Ardakani, H. Bagheri, and C. Tellambura, "Gamma codes:A low-overhead linear-complexity network coding solution," in Proc. IEEE NetCod,2012, pp.125-130.
[74]K. Mahdaviani, R. Yazdani, and M. Ardakani, "Overhead-optimized gamma network codes," in Proc. IEEE NetCod,2013.
[75]——, "Linear-complexity overhead-optimized random linear network codes," arXiv preprint arXiv:1311.2123,2013.
[76]S. Yang and R. W. Yeung, "Large file transmission in network-coded networks with packet loss:a performance perspective," in Proc. ACM ISABEL,2011, p.117.
[77]H. Yin and S. Alamouti, "Ofdma:A broadband wireless access technology," in IEEE Sarnoff Symposium,2006, pp.1-4.
[78]"802.16:Air interface for broadband wireless access systems," 2009.
[79]"3GPP, LTE release 10 and beyond (LTE advanced)." [Online]. Available: http://www.3gpp.org/LTE-Advanced,
[80]K. Sundaresan and S. Rangarajan, "On exploiting diversity and spatial reuse in relay-enabled wireless networks," in Proc. ACM MobiHoc,2008, pp.13-22.
[81]H. J. Kushner and P. A. Whiting, "Convergence of proportional-fair sharing algorithms under general conditions," IEEE Transactions on Wireless Communications, vol.3, no.4, pp.1250-1259,2004.
[82]C. Y. Wong, R. S. Cheng, K. B. Lataief, and R. D. Murch, "Multiuser ofdm with adaptive subcarrier, bit, and power allocation," IEEE Journal on Selected Areas in Communications, vol.17, no.10, pp.1747-1758,1999.
[83]D. Kivanc, G. Li, and H. Liu,"Computationally efficient bandwidth allocation and power control for ofdma," IEEE Transactions on Wireless Communications, vol.2, no.6, pp.1150-1158,2003.
[84]M. Ergen, S. Coleri, and P. Varaiya, "Qos aware adaptive resource allocation techniques for fair scheduling in ofdma based broadband wireless access systems," IEEE Transactions on Broadcasting, vol.49, no.4, pp.362-370,2003.
[85]M. Andrews and L. Zhang, "Scheduling algorithms for multi-carrier wireless data systems," in Proc. ACM MobiCom,2007, pp.3-14.
[86]S. Bodas, S. Shakkottai, L. Ying, and R. Srikant, "Low-complexity scheduling algorithms for multichannel downlink wireless networks," IEEE/ACM Transactions on Networking, vol.20, no.5, pp.1608-1621,2012.
[87]K. Sundaresan, X. Wang, and M. Madihian, "Low-overhead scheduling algorithms for ofdma relay networks," in Proc. ACM WiCON,2008, p.24.
[88]S. Deb, V. Mhatre, and V. Ramaiyan, "Wimax relay networks:opportunistic scheduling to exploit multiuser diversity and frequency selectivity," in Proc. ACM MobiCom,2008, pp. 163-174.
[89]C.-Y. Hong and A.-C. Pang, "Link scheduling with qos guarantee for wireless relay networks," in Proc. IEEE INFOCOM,2009, pp.2806-2810.
[90]R. Draves, J. Padhye, and B. Zill, "Routing in multi-radio, multi-hop wireless mesh network-s," in Proc. ACM MobiCom,2004, pp.114-128.
[91]T.-D. Nguyen and Y. Han, "A proportional fairness algorithm with qos provision in downlink ofdma systems," IEEE Communications Letters, vol.10, no.11, pp.760-762,2006.
[92]Y. Ma, "Rate maximization for downlink ofdma with proportional fairness," IEEE Transac-tions on Vehicular Technology, vol.57, no.5, pp.3267-3274,2008.
[93]O. Oyman, "Ofdm2a:A centralized resource allocation policy for cellular multi-hop net-works," in Proc. IEEE ACSSC,2006, pp.656-660.
[94]V. V. Vazirani, Approximation algorithms, springer,2001.
[95]L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Transac-tions on Automatic Control, vol.37, no.12, pp.1936-1948,1992.
[96]M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, P. Whiting, and R. Vijayakumar, "Providing quality of service over a shared wireless link," IEEE Communications Magazine, vol.39, no.2, pp.150-154,2001.
[97]M. J. Neely, E. Modiano, and C. E. Rohrs, "Power and server allocation in a multi-beam satellite with time varying channels," in Proc. IEEE INFOCOM, vol.3,2002, pp.1451-1460.
[98]A. M. Frieze and M. Clarke, "Approximation algorithms for the (?), mj/i(?)-dimensional 0-1 knapsack problem:Worst-case and probabilistic analyses," European Journal of Operational Research, vol.15, no.1, pp.100-109,1984.
[99]D. B. Shmoys and E. Tardos, "An approximation algorithm for the generalized assignment problem," Mathematical Programming, vol.62, no.1-3, pp.461-474,1993.
[100]S.-C. Fang and S. Puthenpura, Linear optimization and extensions:theory and algorithms, 1993.
[101]M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, "An analysis of approximations for maximizing submodular set functions-ii," in Polyhedral combinatorics,1978, pp.73-87.
[102]J. Gross, H.-F. Geerdes, H. Karl, and A. Wolisz, "Performance analysis of dynamic ofdma systems with inband signaling," IEEE Journal on Selected Areas in Communications, vol.24, no.3, pp.427-436,2006.
[103]J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva, "A performance comparison of multi-hop wireless ad hoc network routing protocols," in Proc. ACM MobiCom. ACM, 1998, pp.85-97.
[104]J. K. Cavers, Mobile channel characteristics. Springer,2000.
[105]Y. Wu, "A trellis connectivity analysis of random linear network coding with buffering," in Proc. IEEE ISIT,2006, pp.768-772.
[106]P. A. Chou, Y. Wu, and K. Jain, "Practical network coding," in Proc. Allerton,2003.
[107]Y. Li, W.-Y. Chan, and S. D. Blostein, "Network coding with unequal size overlapping generations," in Proc. IEEE NetCod,2012, pp.161-166.
[108]S. Yang, S.-W. Ho, J. Meng, E.-h. Yang, and R. W. Yeung, "On linear operator channels over finite fields," arXiv preprint arXiv:1002.2293,2010.
[109]D. J. Newman, "The double dixie cup problem," The American Mathematical Monthly, vol.67, no.1, pp.58-61,1960.
[110]L. Flatto, "Limit theorems for some random variables associated with urn models," The Annals of Probability, vol.10, no.4, pp.927-934,1982.
[111]M. Mitzenmacher and E. Upfal, Probability and computing:Randomized algorithms and probabilistic analysis. Cambridge University Press,2005.
[112]M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, "Efficient erasure correcting codes," IEEE Transactions on Information Theory, vol.47, no.2, pp.569-584, 2001.
[113]P. Oswald and A. Shokrollahi, "Capacity-achieving sequences for the erasure channel," IEEE Transactions on Information Theory, vol.48, no.12, pp.3017-3028,2002.
[114]S. Hoory, N. Linial, and A. Wigderson, "Expander graphs and their applications," Bulletin of the American Mathematical Society, vol.43, no.4, pp.439-561,2006.
[115]N. C. Wormald, "Models of random regular graphs," London Mathematical Society Lecture Note Series, pp.239-298,1999.
[116]G. A. Margulis, "Explicit constructions of concentrators," Problemy Peredachi Informatsii, vol.9, no.4, pp.71-80,1973.
[117]O. Reingold, S. Vadhan, and A. Wigderson, "Entropy waves, the zig-zag graph product, and new constant-degree expanders," Annals of Mathematics, pp.157-187,2002.
[118]B. D. McKay and N. C. Wormald, "Uniform generation of random regular graphs of moderate degree," Journal of Algorithms, vol.11, no.1, pp.52-67,1990.
[119]B. D. McKay, N. C. Wormald, and B. Wysocka, "Short cycles in random regular graphs," The Electronic Journal of Combinatorics, vol.11, no.1,2004.
[120]A. Nilli, "On the second eigenvalue of a graph," Discrete Mathematics, vol.91, no.2, pp. 207-210,1991.
[121]J. Friedman, "A proof of alon's second eigenvalue conjecture," in Proc. ACM STOC,2003, pp.720-724.
[122]N. Alon and F. R. Chung, "Explicit construction of linear sized tolerant networks," Discrete Mathematics, vol.72, no.1, pp.15-19,1988.
[123]R. Bar-Yehuda, O. Goldreich, and A. Itai, "On the time-complexity of broadcast in multi-hop radio networks:An exponential gap between determinism and randomization," Journal of Computer and System Sciences, vol.45, no.1, pp.104-126,1992.
[124]Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, "The broadcast storm problem in a mobile ad hoc network," Wireless networks, vol.8, no.2-3, pp.153-167,2002.
[125]Z. J. Haas, J. Y. Halpern, and L. Li, "Gossip-based ad hoc routing," IEEE/ACM Transac-tions on Networking, vol.14, no.3, pp.479-491,2006.
[126]I. Chlamtac and S. Kutten, "On broadcasting in radio networks-problem analysis and pro-tocol design," IEEE Transactions on Communications, vol.33, no.12, pp.1240-1246,1985.
[127]I. Chlamtac, "The wave expansion approach to broadcasting in multihop radio networks," IEEE Transactions on Communications, vol.39, no.3, pp.426-433,1991.
[128]A. Czumaj and W. Rytter, "Broadcasting algorithms in radio networks with unknown topol-ogy," Journal of Algorithms, vol.60, no.2, pp.115-143,2006.
[129]D. R. Kowalski and A. Pelc, "Broadcasting in undirected ad hoc radio networks," Distributed Computing, vol.18, no.1, pp.43-57,2005.
[130]L. Gasieniec, D. Peleg, and Q. Xin, "Faster communication in known topology radio net-works," Distributed Computing, vol.19, no.4, pp.289-300,2007.
[131]D. R. Kowalski and A. Pelc, "Optimal deterministic broadcasting in known topology radio networks," Distributed Computing, vol.19, no.3, pp.185-195,2007.
[132]M. Ghaffari, B. Haeupler, and M. Khabbazian, "Randomized broadcast in radio networks with collision detection," in Proc. ACM PODC,2013, pp.325-334.
[133]D. Peleg, "Time-efficient broadcasting in radio networks:a review," in Distributed Computing and Internet Technology,2007, pp.1-18.
[134]R. Gandhi, A. Mishra, and S. Parthasarathy, "Minimizing broadcast latency and redundancy in ad hoc networks," IEEE/ACM Transactions on Networking, vol.16, no.4, pp.840-851, 2008.
[135]S.-H. Huang, P.-J. Wan, X. Jia, H. Du, and W. Shang, "Minimum-latency broadcast schedul-ing in wireless ad hoc networks," in Proc. IEEE INFOCOM,2007, pp.733-739.
[136]R. Mahjourian, F. Chen, R. Tiwari, H. Zhai, and Y. Fang, "An approximation algorithm for conflict-aware broadcast scheduling in wireless ad hoc networks," in Proc. IEEE MobiHoc, 2008, pp.331-340.
[137]R. Gandhi, Y.-A. Kim, S. Lee, J. Ryu, and P.-J. Wan, "Approximation algorithms for data broadcast in wireless networks," IEEE Transactions on Mobile Computing, vol.11, no.7, pp.1237-1248,2012.
[138]Z. Kong and E. M. Yeh, "On the latency for information dissemination in mobile wireless networks," in Proc. ACM MobiHoc,2008, pp.139-148.
[139]A. Pettarin, A. Pietracaprina, G. Pucci, and E. Upfal, "Tight bounds on information dis-semination in sparse mobile networks," in Proc. ACM SIGACT-SIGOPS PODC,2011, pp. 355-362.
[140]A. Clementi, A. Monti, F. Pasquale, and R. Silvestri, "Information spreading in stationary markovian evolving graphs," IEEE Transactions on Parallel and Distributed Systems, vol.22, no.9, pp.1425-1432,2011.
[141]A. Clementi, F. Pasquale, and R. Silvestri, "Opportunistic manets:Mobility can make up for low transmission power," IEEE/ACM Transactions on Networking, vol.21, no.2, pp. 610-620,2013.
[142]A. E. Clementi and R. Silvestri, "Parsimonious flooding in geometric random-walks," in Distributed Computing,2011, pp.298-310.
[143]Y. Chen, S. Shakkottai, and J. Andrews, "On the role of mobility for multi-message gossip," IEEE Transactions on Information Theory, vol.59, no.6, pp.3953-3970,2012.
[144]M. Penrose, Random geometric graphs. Oxford University Press Oxford,2003.
[145]P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, vol.46, no.2, pp.388-404,2000.
[146]——, "Critical power for asymptotic connectivity," in Proc. IEEE CDC,1998, pp.547-566.
[147]C. Avin and G. Ercal, "On the cover time and mixing time of random geometric graphs," Theoretical Computer Science, vol.380, no.1, pp.2-22,2007.
[148]D. E. Knuth, The art of computer programming, volume 2:seminumerical algorithms. Read-ing, Mass.:Addison-Wesley,1981.
[149]Wikipedia, "Poisson distribution-wikipedia, the free encyclopedia," 2013. [Online]. Available:http://en.wikipedia.org/