摘要
近年来,无线Ad hoc网络凭借其便捷性、及时性和移动性等特点得到了广泛关注与应用。而这些特点也为Ad hoc网络协议与算法的设计带来了难度。为了保证服务质量(Quality of Service, QoS),需要在开放式系统互联(Open System Interconnection, OSI)模型中为每一层设计适合Ad hoc网络的算法和层间协议。传统的无线网络媒体接入控制机制IEEE802.11MAC协议无法提供实时业务的QoS保证,因此需要在802.11协议框架下设计基于QoS保证的分组业务调度策略以提高Ad hoc网络系统整体性能。调度策略设计作为Ad hoc网络及下一代无线网络通信发展的一项关键技术,有效地减少了链路干扰和冲突,控制了队列拥塞,增大了网络容量,以全局的方式实现网络资源的优化配置。因此,在无线网络中,基于优化的思想,在保证特定QoS性能指标的前提下分时隙的完成分组调度,对有效改善无线Ad hoc网络性能具有重要意义。本论文以排队论和资源分配理论为基础,提出一套基于吞吐量和端到端平均时延保证的调度性能评估方法,并从理论分析和实际应用两方面对调度策略原理进行深入研究,考虑各种网络环境,针对不同实现方式提出基于不同QoS保证的调度算法。此外,在多跳多路径业务流情况下,提出了基于吞吐量保证的跨层联合方案,为下一代无线通信网络协议设计提供了一定的理论依据和技术基础。本论文的主要工作和技术创新如下：
第一,针对单跳信息传输网络,根据分组调度不同的实现方式,分别就集中式与分布式调度策略进行数学建模。而后,针对多跳多路径网络环境,建立了基于吞吐量保证的跨网络层路由选择和链路层调度的跨层联合方案模型。该模型将网络层与链路层联系起来,通过层与层之间的相互合作提高系统整体性能。建立调度模型之后,以排队论、马尔科夫理论为基础,基于李雅普诺夫分析法提出了一套调度策略性能评估理论框架,通过对整个网络系统的稳定性分析考察调度算法或跨层联合方案的吞吐量和端到端平均时延这两项重要的QoS性能指标。此框架是分组调度研究的方法论,用于分析在不同网络环境和流量模型下网络系统的稳定性、调度算法的吞吐量和平均时延性能,具有重要的理论指导意义。
第二,根据集中式调度模型和调度算法性能评估理论框架,在无线单跳Ad hoc网络环境中,提出了基于时延改进的最大权重调度算法(Delay-enhanced Maxmum Weight Scheduler, DMWS).该算法基于系统负载因子ρ优化了调度权重。通过使用李雅普诺夫分析法,证明了DMWS可以保证较之经典的最大权重调度(Maximum Weight Scheduler, MWS)更紧的端到端平均时延。同时DMWS被证明可实现最大吞吐量容量区域,即吞吐量最优。
第三,考虑单接口多信道网络场景和单跳流量模型,提出了基于随机接入和退避时间技术的低复杂度分布式信道分配与调度联合控制策略(Low-complexity Distributed Channel-assignment and Scheduling Algorithm, LDCSA)。在LDCSA中,采用速率比分配方式进行数据流量分配,将数据包合理的分配至各信道队列。在信道分配与调度阶段,采用一种基于概率的竞争接入策略,该策略需要链路之间的信息交互,这种信息交互可由RTS/CTS机制实现。使用李雅普诺夫分析法可以证明LDCSA可以保证稳定的吞吐量容量区域。同时,LDCSA的实现复杂度不随网络规模大小和可用信道个数的改变而改变,适合大规模网络系统应用。
最后,在无线多信道Ad hoc网络中考虑多跳多路径流量环境,即每个数据源节点到目的节点有多个备选多跳路径供数据传输。在这种环境下,需要将网络层路由选择与链路层调度策略结合起来,设计基于QoS保障的跨层联合方案,以保证系统整体性能。根据本文提出的跨层联合方案理论框架,分别针对多接口多信道网络和单接口多信道网络设计了基于吞吐量保证的跨层联合方案：改进版多路径(Multi-Path, MP)方案、分布式路由与信道分配与调度(Distributed Routing, Channel-assignment and Scheduling, DRCS)方案和多路径LDCSA方案(Milti-path LDCSA, M-LDCSA)。其中改进版MP方案是对现有多接口多信道网络跨层MP方案的一般性改进,取消了原始MP方案中不合理的假设条件。而针对单接口多信道网络,DRCS和M-LDCSA分别是对现有的基于单跳网络的速率比最大多信道调度算法(Rate-Proportional Maximal Multi-Channel Scheduler, RPMMC)和LDCSA调度的多跳多路径扩展。本文提出的跨层联合方案综合考虑了路由选择问题和调度问题,基于调度算法合理的设计了路由选择机制,保证了整体吞吐量性能。
Recently, wireless Ad hoc networks have received wide attention and application because of their characteristics such as convenience, timeliness and mobility. These features also brought difficult designing of network protocols and algorithms for Ad hoc networks. To guarantee Quality of Service (QoS), it is required to design algorithms and layer-to-layer protocols that fit Ad hoc networks for each layer of the Open System Interconnection (OSI) model. Traditional wireless networks media access control mechanism IEEE802.11MAC is unable to provide QoS guarantee for real-time services. Therefore, it is required to design packet scheduling policies based on QoS guarantees in the framework of802.11to improve the overall performance of Ad hoc network systems. Scheduling policy, as a key technology for the development of Ad hoc netwokrs and the next-generation wireless network communications, effectively reduced link interference and conflict, controled the queue congestion, increased network capacity, optimized the allocation of network resources in a global approach. Therefore, in wireless networks, based on the idea of optimization, completing packet scheduling in each time-slot on the premise of ensuring specific QoS performance requirements, has great significance for improving the performance of Ad hoc networks. On the basis of queuing theory and the theory of resource allocation, this dissertation put forward a set of evaluation methods for scheduling performances based on throughput region and end-to-end expected delay, conducted thorough research of the principle of scheduling policies from aspects of both theory analysis and practical application, proposed scheduling algorithms according to different implementations, different QoS indicators and various network environments. In addition, in the case of multi-hop multi-path traffic flows, this dissertation put forward cross-layer joint scheme based on throughput guarantees, and provided a certain theory basis and technology foundation for the designing of the next-generation wireless communication networks. The main contributions and innovations of this dissertation are as follows:
Firstly, in single-hop cases, based on different methods of implementation, mathematic models of both centralized and distributed scheduling policies are established. Then, for multi-hop multi-path network environment, a model of cross-layer scheme crossing network layer and link layer is built based considering throughput guarantees. This model combines the network and link layer to improve the overall system performance. After modeling the scheduling policies, based on queuing theory, Markov theory and Lyapunov analysis, a set of performance evaluation theory frameworks of scheduling algorithms is proposed, which investigates the throughput and end-to-end expected delay of the scheduling policies or the cross-layer schemes through analyzing the stability of the whole network system. This framework is the methodology of packet scheduling research and provides important theoretical guidance.
Secondly, according to the centralized scheduling model and the theory framework of scheduling performance evaluation, in wireless Ad hoc networks with single-hop flows, a Delay-enhanced Maximum Weight Scheduler, named DMWS, is put forward. This scheduler optimizes the scheduling weights based on the system loading factor. Using Lyapunov analysis, DMWS is proved to achieve a tighter delay upper bound than traditional Maximum Weight Scheduler (MWS) as well as maximum throughput region.
Thirdly, considering multichannel wireless networks with single-interface nodes and single-hop traffic flows, a Low-complexity Distributed Channel-assignment and Scheduling Algorithm, named LDCSA, is proposed based on random access and backoff time technology. Under LDCSA, a rate-proportional data allocation is adopted to assign data packets to each channel queue reasonably. For channel-assignment and scheduling, a novel access strategy based on probability is put forward. Such strategy requires information exchange between links, which can be implemented by RTS/CTS mechanism. LDCSA is shown to be provably efficient with low complexity independent of both network size and the number of available channels.
Finally, considering multi-hop multi-path traffic flows in multichannel Ad hoc networks, each source node has multiple alternative paths to route packets to destination. Under such circumstances, it is required to combine the network layer and the link layer to design QoS-guaranteed cross-layer scheme. According to the principle framework of the cross-layer scheme proposed in this dissertation, three thoughput-guaranteed schemes, respectively named modified MP, DRCS and M-LDCSA, are put forward for multichannel wireless networks with both single-interface and multi-interface nodes. Modified Multi-Path (MP) scheme is a general version of the original MP scheme. For single-interface cases, Distributed Routing, Channel-assignment and Scheduling (DRCS) and Multi-path LDCSA (M-LDCSA) are respectively the multi-hop multi-path extension of Rate-Proportional Maximal Multi-Channel Scheduler (RPMMC) and LDCSA. The cross-layer schemes proposed combines the routing selection and the scheduling, ensures stable throughput capacity region.
引文
[1]H. S. Chhaya and S. Gupta, "Performance of asynchronous data transfer methods of IEEE 802.11 MAC protocol," IEEE Personal Communications, vol.3, issue 5, pp.8-15.1996.
[2]T. E. Anderson, S. S. Owicki, J. B. Saxe, and C. P. Thacker. "High speed switch scheduling for local area networks." ACM Transactions on Computer Systems, vol. 11, pp.319-352, Nov.1993.
[3]W. J. Dally and B. P. Towles, Principles and Practices of Interconnection Networks. Elsevier, Inc.,2004.
[4]N. McKeown, "The iSLIP scheduling algorithm for input-queued switches,' IEEE/ACM Trans on Networking, vol.7, pp.188-201, April 1999.
[5]Y. Tamir and G. L. Frazier. "Dynamically-allocated multi-queue buffers for VLSI communication switches," IEEE Transactions on Computers, vol.41, No.6. pp. 725-737, June 1992.
[6]L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Autom. Control, vol.37, no.12. pp.1936-1948,1992.
[7]P. Kumar and S. Meyn, "Stability of queueing networks and scheduling policies,' IEEE Trans. on Automatic Control, Feb.1995.
[8]L. Tassiulas, "Scheduling and performance limits of networks with constantly changing topology." IEEE Trans. Inf. Theory, vol.43, no.3. pp.1067-1073,1997.
[9]L. Tassiulas, "Linear complexity algorithms for maximum throughput in radio networks and input queued switches," in Proceedings of IEEE INFOCOM, April 1998.
[10]X. Lin and N B. Shroff, "The Impact of Imperfect Scheduling on Cross-Layer Congestion Control in Wireless Networks," IEEE/ACM Trans. Netw,, vol.14, no. 2, pp.302-315,2006.
[11]M. J. Neely and E. Modiano, "Improving delay in ad-hoc mobile networks via redundant packet transfers," in Proceedings of Conference on Information Sciences and Systems, March 2003.
[12]H. Kim, K. Kim, Y. Han and J. Lee, "An efficient scheduling algorithm for QoS in wireless packet data transmission", in Proceedings of the 13th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications. Sep.2002.
[13]S. Shakkottai, "Effective Capacity and QoS for Wireless Scheduling", IEEE Transactions on Automatic Control, vol.53, no.3, pp.749-761, Apr.2008.
[14]D. Shah and M. Kopikare. "Delay bounds for the approximate maximum weight matching algorithm for input queued switches," in Proceedings of IEEE INFOCOM. June 2002.
[15]A. Charny and J. L. Boudec, "Delay Bounds in a Network with Aggregate Scheduling", Quality of Future Internet Services, Lecture Notes in Computer Science, vol.1922, pp.1-13,2000.
[16]Abbas, A. M, and O. Kure, "Quality of service in mobile ad hoc networks:A survey," International Journal of Ad Hoc and Ubiquitous Computing, vol.6, pp. 75-98,2010.
[17]Fu Z, Meng X and Lu S, "How bad TCP can perform in mobile ad hoc networks.' in Proceedings of 7th International Symposium on Computers and Communications (ISCC),2002.
[18]Kashibuchi. K., Jamalipour. and Kato. N.. "Channel Occupancy Time Based TCP Rate Control for Improving Fairness in IEEE 802.11 DCF," IEEE Trans. Vehicular Technology, vol.59, no.6, pp.2974-2985,2010.
[19]Xia Li, Peng-Yong Kong, Kee-Chaing Chua, "TCP Performance in IEEE 802.11-Based Ad Hoc Networks with Multiple Wireless Lossy Links," IEEE Trans. Mobile Computing, vol.6, no.12, pp.1329-1342,2007.
[20]V. Anantharaman and S. J. Park, "TCP performance over Mobile Ad hoc Networks: A Quantitative Study," Wireless Communications and Mobile Computing, vol.4, pp.203-222,2004.
[21]D. B. Johnson, David A. Maltz, and Josh Broch. "The Dynamic Source Routing Protocol for Multihop Wireless Ad Hoc Networks," Ad Hoc Networking, edited by Charles E. Perkins, chapter 5, pp.139-172,2001.
[22]C. E. Perkins and E. M, Royer, "Ad hoc on-demand distance vector routing," in Proc. WMCSA, New Orleans, LA, pp.90-100, Feb.1999.
[23]Sansa-Otim J, Rai I.A and Hulst. J, "A Delay-Based Protocol with Fair Co-existence," in Proceedings of 9th IEEE Intrernational Conference on Networks (ICN), pp.34-41,2010.
[24]V Tsaoussidis and H Badr, "TCP-probing:towards an error control schema with energy and throughput performance gains." in Proceedings of International Conference on Network Protocols, Osaka, pp.12-21,2000.
[25]Gerla M, Sanadidi M.Y and Ren Wang, "TCP Westwood:congestion window control using bandwidth estimation," in Proceedings of IEEE Global Telecommunications Conference, pp.1698-1702,2001.
[26]Zanella A, Procissi G and Gerla M, "TCP Westwood:analytic model and performance evaluation," Proceedings of IEEE Global Telecommunications Conference, pp.1703-1707,2001.
[27]Perkins C E, Bhagwat and P. Highly, "Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," in Proceedings of ACM SIGCOMM'94, pp.234-244,1994.
[28]J.G. Jetcheva and David B. Johnson, "Adaptive demand-driven multicast routing in multi-hop wireless ad hoc networks." in Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), October 2001.
[29]S.J. Lee, M. Gerla. and Chian, "On-demand multicast routing protocol," in Proceedings of WCNC, September 1999.
[30]E. Royer and C. Perkins, "Multicast operation of the ad hoc on-demand distance vector routing protocol," in Proceedings of MOBICOM, August 1999.
[31]R.Vaishampayan and J.J. Garcia-Luna-Aceves. "Efficient and Robust Multicast Routing in Mobile Ad Hoc Networks," in Proceedings of the 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), October 2004.
[32]GG Peng, J.H Yang and C.S Gao, "A QoS routing protocol based on path stability in mobile ad hoc network," Journal of Computer Research and Development, vol. 41, no.6. pp.916-922,2004.
[33]L. M. Feeney, "An energy-consumption model for performance analysis of routing protocols for mobile ad hoc networks," Mobile Netw. Applicat., vol.6, no.3, pp. 239-249.2001.
[34]Fan Zhang and Yewen Cao, "A Novel Routing Algorithm based on Path Stability and Energy Aware," Advanced Research on Industry, Information System and Material Engineering, vol.204-210, pp.1477-1480,2011.
[35]T. Brown. Q. Zhang, and H. Gabow. "Maximum flow life curve for a wireless ad hoc network," in Proceedings of at the ACM Symp. Mobile Ad Hoc Networking and Computing. Oct.2001.
[36]C. Zhu and M.S. Corson, "QoS Routing for Mobile Ad Hoc Networks," in Proceedings of IEEE INFOCOM, pp.958-967.2002.
[37]C-Y. Chiu. Y-L. Kuo, E. H-K. Wu and G-H. Chen, "Bandwidth Constrained Routing Problem in Wireless Ad Hoc Networks" IEEE Trans on Parallel and Distributed Systems, vol.19, no.1, pp.4-14,2008.
[38]E. Leonardi. M. Mellia, F. Neri and M. A. Marsan,"On the stability of input-queued switches with speed-up," IEEE/ACM Trans. Netw., vol.9, (1), pp. 104-118.2001.
[39]X. Wu, R. Srikant, and J. R. Perkins, "Queue-length stability of maximal greedy schedules in wireless network," in Proc. Inf. Theory Appl. Inaugural Workshop, Feb.2006.
[40]X. Wu, R. Srikant, and J. R. Perkins, "Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks," IEEE Trans. Mobi. Comput., vol.6, no.6, pp.595-605.2007.
[41]P. Chaporkar, K. Kar, X. Luo and S. Sarkar, "Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks," IEEE Trans. Inf. Theory, vol. 54, no.2, pp.572-594,2008.
[42]C. Joo, X. Lin, and N. Shroff, "Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm," IEEE/ACM Trans. Netw.. vol.17, no.4, pp. 1132-1145,2009.
[43]A. Gupta, X. Lin and R. Srikant, "Low-Complexity Distributed Scheduling Algorithms for Wireless Networks, " IEEE/ACM Trans. Netw., vol.17, no.6, pp. 1846-1859,2009.
[44]X. Lin and S. B. Rasool, "Constant-time distributed scheduling policies for ad hoc wireless networks," IEEE Trans. Autom. Control, vol.54, no.2, pp.231-242,2009.
[45]M. J. Neely, "Delay Analysis for Maximal Scheduling in Wireless Networks with Bursty Traffic," in Proceedings of IEEE INFOCOM, Phoenix, AZ, Apr.2008.
[46]M. J. Neely, "Delay Analysis for Max Weight Opportunistic Scheduling in Wireless Systems," IEEE Trans. Autom. Control., vol.54, no.9, pp.2137-2150,2009.
[47]L. B. Le. K. Jagannathan, and E. Modiano. "Delay Analysis of Maximum Weight Scheduling in Wireless Ad Hoc Networks,'" in Proceedings of 43rd Annual Conference on Information Sciences and Systems,2009.
[48]K. Kar, X. Luo, and S. Sarkar, "Delay guarantees for throughput-optimal wireless link scheduling." in Proceedings of IEEE INFOCOM. pp.2331-2339, Apr.2009.
[49]A. Ghiasian, H. Saidi, B. Omoomi and S. Amiri, "The impact of network topology on delay bound in wireless Ad hoc networks," Springer. Wireless Networks, vol. 19, no.2, pp.237-246,2013.
[50]K. Kar, S. Sarkar, A. Ghavami, and X. Luo, "Delay guarantees for throughput-optimal wireless link scheduling," IEEE Trans. Autom. Control., vol. 57, no.11, pp.2906-2911,2012.
[51]J. Abouei, A. Bayesteh and AK. Khandani, "On the Delay-Throughput Tradeoff in Distributed Wireless Networks," IEEE/ACM Trans. Netw., vol.58, no.4, pp. 2159-2174,2012.
[52]N H. Tran, C S. Hong and S. Lee, "Distributed throughput-optimal scheduling framework with delay analysis in multi-hop wireless networks," ELSEVIER. Mathematical and Computer Modelling, vol.53, pp.2149-2161,2011.
[53]G. R. Gupta and N. B. Shroff, "Delay Analysis and Optimality of Scheduling Policies for Multihop Wireless Networks," IEEE/ACM Trans. Netw., vol.19, no.1, pp.129-141.2011.
[54]L. Bui, R. Srikant and A. Stolyar, "Novel Architectures and Algorithms for Delay Reduction in Back-pressure Scheduling and Routing," in Proceedings of IEEE INFOCOM, Rio de Janeiro, pp.2936-2940,2009.
[55]L. Huang and M. Neely, "Delay reduction via lagrange multipliers in stochastic network optimization," in Proc. Intl. Symposium on Modelling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt),2009.
[56]Q. Liu, S. Zhou and G. B. Giannakis, "Cross-layer Combining of Adaptive Modulation and Coding with Truncated ARQ over Wireless Links," IEEE Transactions on Wireless Communications, vol.3, pp.1746-1755, Sept.2004.
[57]Q. Liu, S. Zhou and G. B. Giannakis, "Queuing with adaptive modulation and coding over wireless links:Cross-layer analysis and design," IEEE Transactions on Wireless Communications, vol.4, no.3, pp.1142-1153,2005.
[58]Q. Liu, S. Zhou and G. B. Giannakis, "Cross-layer scheduling with prescribed QoS guarantees in adaptive wireless networks," IEEE Journal on Selected Areas in Communications, vol.23, issue 5, pp.1056-1066,2005.
[59]J. Ryu, L. Ying and S. Shakkottai, "Back-pressure routing for intermittently connected networks," in Proceedings of IEEE INFOCOM, pp.1-5,2010.
[60]L. Ying, S. Shakkottai. A. Reddy and S. Liu, "On Combining Shortest-Path and Back-Pressure Routing Over Multihop Wireless Networks," IEEE/ACM Trans. Netw., vol.19, no.3, pp.841-854, June 2011.
[61]E. Athanasopoulou, L. Bui, T. Ji, R. Srikant and A. Stolyar, "Backpressure-based Packet-by-Packet Adaptive Routing in Communication Networks," IEEE/ACM Transactions on Networking, vol.21, no.1, pp.244-257, Feb.2013.
[62]A. Eryilmaz and R. Srikant, "Joint Congestion Control, Routing, and MAC for Stability and Fairness in Wireless Networks," IEEE Journal on Selected Area in Communications, vol.24, issue 8, pp.1514-1524, Aug.2006.
[63]T. Bonald and L. Massoulie,"Impact of fairness on Internet performance," in Proceedings of ACM Sigmetrics, Cambridge, MA, pp.82-91, June 2001.
[64]J.Mo and J.Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Netw., vol.8, no.5, pp.556-567, Oct.2000.
[65]L. Chen, S. H. Low, M. Chiang and J. C. Doyle, "Joint optimal congestion control, routing, and scheduling in wireless ad hoc networks," in Proceedings of IEEE INFOCOM.2006.
[66]M. J. Neely, "Delay-Based Network Utility Maximization," IEEE/ACM Trans. Netw., vol.21, no.1, pp.41-54, Feb.2013.
[67]F. P. Kelly, A. Maulloo, D. Tan, "Rate control for communication networks: shadow prices, proportional fairness and stability," Journal of Operations Research Society, vol.49, issue 3, pp.237-252, Mar.1998.
[68]张光澄,非线性最优化计算方法,高等教育出版社,2006.
[69]王倩,无线通信系统中基于跨层优化的TCP协议研究,山东大学博士学位论文,2010.
[70]X. Lin, N. B. Shroff and R. Srikant, "A Tutorial on Cross-Layer Optimization in Wireless Networks," IEEE/ACM Tran. Netw., vol.24, no.8, pp.1452-1463, Aug. 2006.
[71]P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, vol.46, no.2, pp.388-404,2000.
[72]C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization:Algorithms and Complexity. Englewood Cliffs, NJ:Prentice-Hall,1982.
[73]K. Jung and D. Shah, "A distributed matching algorithm," MIT, Cambridge, MA. 2006, Tech. Report.
[74]A. Israeli and A. Itai. "A fast and simple randomized parallel algorithm for maximal matching,'" Inf. Process. Lett., vol.22, no.2, pp.77-80,1986.
[75]X. Lin and N. B. Shroff, "Joint rate control and scheduling in multihop wireless networks," in Proc. IEEE Conf. Decision and Control, Paradise Island, Bahamas, pp.1484-1489,2004.
[76]G. Sharma, N. Shroff, and R. Mazumdar, "Joint congestion control and distributed scheduling for throughput guarantees in wireless networks," ACM Transactions on Modeling and Computer Simulation, vol.21, no.1,2010.
[77]Po-Kai. Huang, X. Lin and Chih-Chun. Wang. "A Low-Complexity Congestion Control and Scheduling Algorithm for Multihop Wireless Networks with Order-Optimal Per-Flow Delay," IEEE/ACM Trans. Netw., vol.21, no.2, pp.495-508,2013.
[78]S. Merlin, N. Vaidya, and M. Zorzi,"Resource allocation in multi-radio multi-channel multi-hop wireless networks," in Proceedings of IEEE INFOCOM. 2008.
[79]X. Lin and Shahzada Rasool, "A Distributed Joint Channel-Assignment, Scheduling and Routing Algorithm for Multi-Channel Ad Hoc Wireless Networks," Proc. IEEE INFOCOM,2007.
[80]X. Lin and Shahzada Rasool, "Distributed and Provably-Efficient Algorithms for Joint Channel- Assignment, Scheduling and Routing in Multi-Channel Ad Hoc Wireless Networks," IEEE/ACM Trans. Netw., vol.17, no.6, pp 1874-1887,2009.
[81]J. G. Choi and G. S. Choi, "Optimal Scheduler with Simplified Queue Structure for Multi-Channel Wireless Networks," IEEE Commun. Lett., vol.15, no.9, pp. 962-964,2011.
[82]S. Bodas, S. Shakkotta, L. Ying, and R. Srikant, "Scheduling for small delay in multi-rate multi- channel wireless networks," Proc. IEEE Infocom. Conf., pp. 1251-1259,2011.
[83]S. Bodas, S. Shakkotai, L. Ying, and R. Srikant, "Low-complexity scheduling algorithms for multi-channel downlink wireless networks," IEEE/ACM Transactions on Networking, vol.20, no.5, pp.1608-1621.2012.
[84]V. Bhandari and N. H. Vaidya,"Scheduling in multichannel wireless networks.' Springer. Distrib. Comput. Netw.,5935,pp.6-17,2010.
[85]K. Li, F. Wang, Y. Zhang, F. Zhang, and X. Xie, "Distributed Joint Resource Allocation in Multi-Radio Multi-Channel Wireless Mesh Networks," Proc. IEEE Global Telecommunications. Conf., Honolulu, HI, pp.1-6,2009.
[86]L. Zhou, X. Wang, W. Tu, GM. Muntean, and B. Geller, "Distributed scheduling scheme for video streaming over multi-channel multi-radio multi-hopwireless networks," IEEE Journal on Selected Areas in Communications, vol.28, no.3, pp. 409-419,2010.
[87]N. Chakchouk and B. Hamdaoui, "Traffic and interference aware scheduling for multi-radio multi-channel wireless mesh networks," IEEE Tran. Vehicular Tech., vol.60, no.2, pp.555-565,2011.
[88]C. Hua and R. Zheng, "Robust topology engineering in multiradio multichannel wireless networks," IEEE Trans. Mobile Comput., vol.11, no.3, pp.492-503. 2012.
[89]R. Nelson, Probability, Stochastic Processes, and Queueing Theory. Springer-Verlag,1995.
[90]P. P. Bocharov, C. D' Apice. A. V. Pechinkin and S. Salerno, Queueing Theory. Koninklijke Brill N. V.,2004.
[91]G. Bolch, S. Greiner, H. d. Meer and K. S. Trivedi, Queueing Networks and Markov Chains:Modeling and Performance Evluation with Computer Science Applications. John Wiley & Sons, Inc., Hoboken, New Jersey,2006.
[92]S. Asmussen, Applied Probability and Queues. New York:Spring-Verlag, Second ed.,2003.
[93]S. Meyn and R. Tweedie, Markov Chains and Stochastic Stability. NY: Springer-Verlag.
[94]P. P. Bhattacharya, L. Georgiadis, P. Tsoucas, and I. Viniotis, "Adaptive lexicographic optimization in multi-class M/Gl/1 queues," Mathematics of Operations Research, vol.18, no.3, pp.705-740,1993.
[95]P. P. Bhattacharya, L. Georgiadis, and P. Tsoucas, "Problems of adaptive optimization in multiclass M/GI/1 queues with bernoulli feedback," Mathematics of Operations Research, vol.20, pp.356-380, May 1995.
[96]1. Keslassy and N. McKeown, "Analysis of scheduling algorithms that provide 100% throughput in input-queued switches," in Proceedings of the 39th Annual Allerton Conf. on Communication, Control, and Computing. Oct.2001.
[97]E. Leonardi, M. Mellia, F. Neri, and M. A. Marsan, "Bounds on average delays and queue size averages and variances in input-queued cell-based switches." in Proceedings of IEEE INFOCOM, April 2001.
[98]N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, "Achieving 100% throughput in an input-queued switch," IEEE Transactions on Communications, vol.47, pp.1260-1272, August 1999.
[99]M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, and P. Whiting, "Providing quality of service over a shared wireless link," IEEE Communications Magazine, vol.39, no.2, pp.150-154,2001.
[100]N. Kahale and P. E. Wright, "Dynamic global packet routing in wireless networks," in Proceedings of IEEE INFOCOM,1997.
[101]M. J. Neely, E. Modiano, and C. E. Rohrs. "Dynamic power allocation and routing for time varying wireless networks," IEEE Journal on Selected Areas in Communications, Special Issue on Wireless Ad-hoc Networks, vol.23, No.1, pp. 89-103, January 2005.
[102]L. Tassiulas and A. Ephremides, "Dynamic server allocation to parallel queues with randomly varying connectivity," IEEE Transactions on Information Theory, vol.39, No.2, pp.466-478,1993.
[103]L. Tassiulas, "Scheduling and performance limits of networks with constantly changing topology," IEEE Transactions on Information Theory, vol.43, No.3, pp. 1067-1073,1997.
[104]V. Tsibonis and L. Georgiadis, "An adaptive framework for addressing fairness issues in wireless networks," Computer Communications, vol.28, pp.1167-1178, 2005.
[105]V. J. Venkataramanan and X. Lin, "Structural properties of ldp for queue-length based wireless scheduling algorithms," presented at the 44th Annu. Allerton Conf. Commun., Control, Comput., Sep.2006.
[106]A. L. Stolyar, "Maxweight scheduling in a generalized switch:State space collapse and workload minimization in heavy traffic," Ann. Appl. Probab., vol.14, no.1, pp.1-53,2004.
[107]H. Balakrishnan, C. Barrett. V. Kumar. M. Marathe, and S. Thite, "The distance-2 matching problem and its relationship to the maclayer capacity of ad hoc networks," IEEE J. Sel. Areas Commun., vol.22. no.6, pp.1069-1079,2004.
[108]G Sharma, R. R. Mazumdar, and N. B. Shroff, "On the complexity of scheduling in wireless networks," in Proc. MobiCom, pp.227-238.2006.
[109]F. Baccelli and P. Bremaud, Elements of Queueing Theory. Berlin:Springer,2nd ed.,2003.
[110]M. El-Taha and S. Stidham Jr., Sample-Path Analysis of Queueing Systems. Boston:Kluwer Academic Publishers,1999.
[111]F. M. Guillemin and R. R. Mazumdar, "On pathwise analysis and existence of empirical distributions for G/G/1 queues," Stochastic Processes and their Applications, vol.67, pp.55-67, April 1997.
[112]P. Chaporkar, K. Kar, and S. Sarkar, "Throughput Guarantees in Maximal Scheduling in Allerton Networks," Proc.43rd Ann. Allerton Conf. Comm., Control, and Computing,2005.
[113]G. R. Gupta and N. B. Shroff, "Delay Analysis of Scheduling Policies in Wireless Networks," in Proceedings of 42nd Asilomar Conference on Signals. Systems and Computers,2008.
[114]G. Fayolle, V. A. Malyshev, and M. V. Menshikov, Topics in the Constructive Theory of Countable Markov Chains. Cambridge, U.K.:Cambridge Univ. Press, 1995.
[115]M. J. Neely, E. Modiano, and C. E. Rohrs, "Power allocation and routing in multibeam satellites with time-varying channels," IEEE/ACM Trans. Netw., vol. 11, pp.138-152, Feb.2003.
[116]J.G. Dai and B. Prabhakar, "The Throughput of Data Switches with and without Speedup," Proc. IEEE INFOCOM, pp.556-564,2000.
[117]M. J. Neely, "Delay Analysis for Maximal Scheduling with Flow Control in Wireless Networks with Bursty Traffic," IEEE/ACM Trans. Netw., vol.17, no.4, pp.1146-1159, Aug.2009.
[118]T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, 2000.
[119]L. Georgiadis, M. Neely, and L. Tassiulas, Resource Allocation and Cross-Layer Control in Wireless Networks. Ser. Foundations and Trends in Networking, NOW Publishers.2006.
[120]B. A. Miller and C. Bisdikian, Bluetooth revealed:The Insider's Guide to an Open Specification for Global Wireless Communications. Upper Saddle River, NJ: Prentice-Hall,2001.
[121]B. Hajek and G. Sasaki. "Link scheduling in polynomial time," IEEE Trans. Inf. Theory, vol.34, no.5, pp.910-917,1988.
[122]F. Juraschek, M. Gune,s, M. Philipp, B. Blywis, and O. Hahm, "DES-Chan:A Framework for Distributed Channel Assignment in Wireless Mesh Networks," in Proceedings of Australasian Telecommunication Networks and Applications. Conf., Melbourne, VIC, pp.1-6, Nov 2011.
[123]H. Chen and J. S. Baras, "A distributed opportunistic scheduling protocol for multi-channel wireless ad-hoc networks," Proc. IEEE Global Communications. Conf., pp.274-279, Dec.2012.
[124]R. Knopp and P. Humblet, "Information capacity and power control in single-cell multiuser communications," Proc. IEEE Int. conf. on Communications, pp. 331-335,June 1995.
[125]S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.: Cambridge Univ. Press,2004.
[126]R. Motwani and P. Raghavan, Randomized Algorithms. New York:Cambridge Univ. Press,1995.
[127]P. Kyasanur and Nitin H. Vaidya,"Capacity of Multi-Channel Wireless Networks: Impact of Number of Channels and Interfaces," in Proceedings of the 11th annual international conference on Mobile computing and networking, pp.43-57,2005.
[128]L. Bui, R. Srikant and A. Stolyar, "A Novel Architecture for Reduction of Delay and Queueing Structure Complexity in the Back-pressure Algorithm," IEEE/ACM Transactions on Networking, vol.19, issue 6, Dec.2011.
[129]X. Lin and N. B. Shroff, "Utility maximization for communication networks with multipath routing," IEEE Trans. Autom. Control, vol.51, no.5, pp.766-781, May 2006.
