Robust Packet Scheduling in Wireless Cellular Networks

This paper addresses the following robust scheduling problem: Given that only coarse-grained channel state information (i.e., bounds on channel errors, but not the fine-grained error pattern) is available, how to design a robust scheduler that ensures worst-case optimal performance? To solve this problem, we consider two coarse-grained channel error models and take a zero-sum game theoretic approach, in which the scheduler and the channel error act as non-cooperative adversaries in the scheduling process. Our results show that in the heavy channel error case, the optimal scheduler adopts a threshold form. It does not schedule a flow if the price (the flow is willing to pay) is too small, in order to maximize the system revenue. Among the scheduled flows, the scheduler schedules a flow with a probability inversely proportional to the flow price such that the risk of being caught by the channel error adversary is minimized. We also show that in the mild channel error model, the robust scheduling policy exhibits a balanced trade-off between a greedy decision and a conservative policy. The scheduler is likely to take a greedy decision if it evaluates the risk of encountering the channel error adversary now to be small. Therefore, robust scheduling does not always imply conservative decision. The scheduler is willing to take “risks” to expect higher gain in some scenarios. Our solution also shows that probabilistic scheduling may lead to higher worst-case performance compared to traditional deterministic policies. Finally, the current efforts show the feasibility to explore a probabilistic approach to cope with dynamic channel error conditions.     

一种在无线衰落信道上支持实时业务的分组调度算法

无线分组调度算法能为蜂窝网络中的移动用户提供服务质量的保证。在此问题上,以前的研究工作中一个经典的假设是基站与用户之间的信道条件变化为一平稳随机过程。但在实际情况中,这样的平稳假设并非总是合理的。研究表明基于平稳假设的调度算法,如流行的M-LWDF和EXP-rule算法,在非平稳信道上的性能下降明显。在CDMA蜂窝通信系统中,为在时变衰落信道上支持实时数据业务,该文提出一种基于模糊逻辑控制的分组调度算法,简称FROS。它能在保证用户QoS要求的同时,考虑到无线信道的快衰落特性而充分利用多用户分集(Multiuser diversity)所带来的增益,从而提高系统容量。系统级仿真证明,FROS算法能在优化系统分组时延性能和优化系统吞吐量性能之间保持良好的平衡和折衷,在平稳信道和非平稳信道的条件下都能获得比M-LWDF和EXP-rule算法更好的性能。     

无线移动网络环境中混合式任务调度策略的研究与实现

无线移动网络具有性能不稳、易受外界干扰等特点,要求实时调度必须考虑网络变化影响.因为网络性能变化可直接导致网络延时变化,即任务耗费在网络传输上的时间发生变化,从而对任务集可调度性产生影响.传统调度算法大多未考虑网络因素.由此提出适应于网络性能不稳定环境下的混合式任务调度策略,测试结果表明该策略有利于提高混合实时任务在网络性能动态变化环境下的可调度性.     

A Packet Scheduling Approach to QoS Support in Multihop Wireless Networks

Providing packet-level quality of service (QoS) is critical to support both rate-sensitive and delay-sensitive applications in bandwidth-constrained, shared-channel, multihop wireless networks. Packet scheduling has been a very popular paradigm to ensure minimum throughput and bounded delay access for packet flows. This work describes a packet scheduling approach to QoS provisioning in multihop wireless networks. Besides minimum throughput and delay bounds for each flow, our scheduling disciplines seek to achieve fair and maximum allocation of the shared wireless channel bandwidth. However, these two criteria can potentially be in conflict in a generic-topology multihop wireless network where a single logical channel is shared among multiple contending flows and spatial reuse of the channel bandwidth is possible. In this paper, we propose a new scheduling model that addresses this conflict. The main results of this paper are the following: (a) a two-tier service model that provides a minimum fair allocation of the channel bandwidth for each packet flow and additionally maximizes spatial reuse of bandwidth, (b) an ideal centralized packet scheduling algorithm that realizes the above service model, and (c) a practical distributed backoff-based channel contention mechanism that approximates the ideal service within the framework of the CSMA/CA protocol.     

Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks

The question of providing throughput guarantees through distributed scheduling, which has remained an open problem for some time, is addressed in this paper. It is shown that a simple distributed scheduling strategy, maximal scheduling, attains a guaranteed fraction of the maximum throughput region in arbitrary wireless networks. The guaranteed fraction depends on the ldquointerference degreerdquo of the network, which is the maximum number of transmitter-receiver pairs that interfere with any given transmitter-receiver pair in the network and do not interfere with each other. Depending on the nature of communication, the transmission powers and the propagation models, the guaranteed fraction can be lower-bounded by the maximum link degrees in the underlying topology, or even by constants that are independent of the topology. The guarantees are tight in that they cannot be improved any further with maximal scheduling. The results can be generalized to end-to-end multihop sessions. Finally, enhancements to maximal scheduling that can guarantee fairness of rate allocation among different sessions, are discussed.     

Content-Aware Resource Allocation and Packet Scheduling for Video Transmission over Wireless Networks

A cross-layer packet scheduling scheme that streams pre-encoded video over wireless downlink packet access networks to multiple users is presented. The scheme can be used with the emerging wireless standards such as HSDPA and IEEE 802.16. A gradient based scheduling scheme is used in which user data rates are dynamically adjusted based on channel quality as well as the gradients of a utility function. The user utilities are designed as a function of the distortion of the received video. This enables distortion-aware packet scheduling both within and across multiple users. The utility takes into account decoder error concealment, an important component in deciding the received quality of the video. We consider both simple and complex error concealment techniques. Simulation results show that the gradient based scheduling framework combined with the content-aware utility functions provides a viable method for downlink packet scheduling as it can significantly outperform current content-independent techniques. Further tests determine the sensitivity of the system to the initial video encoding schemes, as well as to non-real-time packet ordering techniques.     

Downlink Wireless Packet Scheduling with Deadlines

Next-generation cellular wireless communication networks aim to provide a variety of quality-of-service (QoS)-sensitive packet-based services to downlink users. Included among these are real-time multimedia services, which have stringent delay requirements. Downlink packet scheduling at the base station plays a key role in efficiently allocating system resources to meet the desired level of QoS for various users. In this paper, we employ dynamic programming (DP) to study the design of a downlink packet scheduler capable of supporting real-time multimedia applications. Under well-justified modeling reductions, we extensively characterize structural properties of the optimal control associated with the DP problem. We leverage intuition gained from these properties to propose a heuristic scheduling policy, namely, Channel-Aware Earliest Due Date (CA-EDD), which is based on a "quasi- static" approach to scheduling. The per-time-slot implementation complexity of CA-EDD is only O(K) for a system with K downlink users. Experimental results show that CA-EDD delivers up to 50 percent of performance gains over benchmark schedulers. CA-EDD achieves these performance gains by using channel and deadline information in conjunction with application layer information (relative importance of packets) in a systematic and unified way for scheduling.     

分组网络中包调度算法研究

下一代因特网要支持QoS(quality of service)实现,而包调度又是QoS实现的关键技术之一。文中对现有的包调度算法进行了分类,分析和比较了各类算法的技术特点与性能优劣,讨论了包调度算法研究今后的发展方向。     

Combinatorial Interleavers for Systematic Regular Repeat-Accumulate Codes [Transactions Letters]

This paper proposes novel interleaver and accumulator structures for systematic, regular repeat-accumulate (RA) codes. It is well known that such codes are amenable to iterative (sum-product) decoding on the Tanner graph of the code, yet are as readily encodable as turbo codes. In this paper, interleavers for RA codes are designed using combinatorial techniques as a basis for deterministic interleaver constructions, yielding RA codes whose Tanner graphs are free of 4-cycles. Further, a generalized RA code accumulator structure is proposed, leading to codes, termed w3RA codes, whose parity-check matrices have many fewer weight-2 columns than conventional RA codes. The w3RA codes retain the low-complexity encoding of conventional RA codes and exhibit improved error-floor performance.     

A Distributed Packet Scheduling Scheme with Interference Avoidance for Non Real-Time Applications in CDMA Networks

In this paper, a packet scheduling scheme based on real-time channel conditions and dominant intercell interferer avoidance is proposed, studied and evaluated for reverse links in a time-slotted code division multiple access (CDMA) system. This scheme is implemented by distribution of tags by receivers among transmitters. Each base station issues M(1) tags to M mobile users based on the ranked reverse link gains in every slot. M=1 corresponds to spread-spectrum time division multiplexing mode operation and M1 corresponds to scheduling multiple simultaneous transmissions as in the traditional CDMA systems. The number of issued tags is a system parameter which depends on the expected traffic, the number of cells and the propagation conditions in the network. In the proposed scheme, users who not only have stronger channel gains to their respective home base stations but also cause relatively lower intercell interference are scheduled for transmissions. Different classes of tags can be issued and various scheduling decision rules can be implemented giving flexibility in interference management. Simulation results in shadow and multipath fading environment are presented to show the performance advantage of the proposed scheme.     

基于OFDM的无线分组调度机制研究

采用OFDM技术的无线接口是新一代移动通信系统的候选方案之一,然而OFDM技术的特点也给面向多媒体应用并采用全IP网络结构的未来移动通信系统带来了新的问题.在探讨了OFDM无线链路的特性及其对于调度机制的影响之后,分析了PF、ODRR、MRR和Maximum C/I等主流无线调度机制与OFDM技术相结合的性能特点并指出不足之处,最后展望了基于OFDM的无线分组调度机制的发展趋势.     

一种具有小尺度公平的无线分组调度算法

本文在调度判决时考虑到用户的访问时延限制,比例公平调度算法基础上提出了M-PF算法。本文建立了无线分组调度系统模型,通过仿真对新算法在小尺度服务时间保证、大尺度服务时间公平和系统吞吐量等方面的性能进行分析,研究了系统参数对算法性能的影响。结果证明,新算法在保证系统吞吐量和大尺度公平性的同时可以提供更好的小尺度服务时间保证。     

TD-HSUPA无线分组调度算法研究

首先介绍了在TD-HSUPA系统中调度算法对无线资源管理的重要影响及Node B调度的基本原理.然后分析了几种常用的无QoS保证的调度算法和两种保证多业务QoS的调度算法,并通过公平性、吞吐量等性能指标对它们进行分析比较.最后引入了经济学中的效用函数思想,分析了基于效用函数的调度算法,它能够结合相应业务的QoS要求,更加真实地反应用户的满意情况,为调度算法的改进提供依据,从而使网络能够承载更高的数据服务容量,增强网络建设的有效性.     

Packet Scheduling Algorithm for Real-Time Services in Broadband WMAN

Packet scheduling algorithm is the key technology to guarantee Quality of Service (QoS) and balance the fairness between users in broadband Wireless Metropolitan Area Network (WMAN). Based on the research of Proportional Fairness (PF) algorithm and Modified Largest Weighted Delay First (M-LWDF) algorithm, a new packet scheduling algorithm for real-time services in broadband WMAN, called Enhanced M-LWDF (EM-LWDF), was proposed. The algorithm phases in new information to measure the load of service queues and updates the state parameters in real-time way, which remarkably improves system performance.Simulation results show that comparing with M-LWDF algorithm, the proposed algorithm is advantageous in performances of queuing delay and fairness while guaranteeing system throughput.     

一种适用于宽带无线城域网实时业务的分组调度算法

对宽带无线城域网（WMAN）而言,分组调度算法是保证用户服务质量（QoS）、平衡用户间公平性的关键。在研究比例公平调度算法（PF）算法与修正的最大加权时延优先算法（M-LWDF）的基础上,一种新的适用于宽带无线城域网实时业务的分组调度算法被提出,此算法引入了新的衡量服务队列负载的信息,能够实时地更新状态参数,提高了系统性能。仿真结果表明,此算法在保证系统吞吐量的同时,比M-LWDF算法具有更好的时延特性和公平性。     

Delay-Sensitive Packet Scheduling for a Wireless Access Link

As the delay is a critical QoS factor, packet scheduling over a wireless access link that often becomes congested needs to have the objective of meeting each user's delay requirement. To incorporate the delay into the scheduler design, we consider the objective of maximizing the total utility (U_T). However, since a utility-based scheduler that concerns delay requires high complexity, we introduce the concept of marginal utility. Representing the objective as minimizing the total marginal utility (M_T), we develop some related properties for maximizing U_T and minimizing M_T. For the case with fixed service time, we show that the outcome of M_T minimization becomes equivalent to that of U_T maximization. For the more complicated case of varying service time, the M_T minimization sheds light on the design of a simple scheduler. Overall, the marginal utility requires significantly low complexity for packet scheduling compared to the ordinary utility. Through simulations, we confirm that the marginal utility gives a way of flexible scheduling in meeting various delay requirements.     

Adaptive Rate System for Wireless Packet Networks

The severe channel and interference condition can limit the throughput of the wireless packet networks. We thus propose an adaptive rate system to increase the throughput of the wireless packet networks. In this system, the data rate is adapted to the channel and interference condition. By optimizing the data rate for a given channel and interference condition, we establish the optimal adaptive rate system. It can be shown that the optimal adaptive rate system provides higher throughput than the fixed rate system.