Opportunistic Multi-Access: Multiuser Diversity, Relay-Aided Opportunistic Scheduling, and Traffic-Aided Smooth Admission Control

We study multi-access control in opportunistic communication systems, and propose two new schemes to address channel asymmetry and throughput-guaranteed admission control, respectively. We first devise a relay-aided opportunistic scheduling (RAOS) scheme, in which a user can choose to communicate with the base station either directly or using multiple hops (relay transmissions). We develop relay/direct link construction algorithms using either a channel-capacity-based criterion or a throughput-based criterion, and devise opportunistic scheduling schemes accordingly. Our results show that in the presence of channel asymmetry across users, the RAOS scheme performs significantly better than Qualcomm's HDR scheme. Next, we propose a traffic-aided smooth admission control (SAC) scheme that aims to guarantee throughput provisioning. Simply put, in the SAC scheme, the admission decision is spread over a trial period, by increasing gradually the amount of the time resource allocated to incoming users. Specifically, using the modified weighted proportional fair (WPF) scheduling, we devise a QoS driven weight adaptation algorithm, and the weights assigned to new users are increased in a guarded manner. Then an admission decision is made based on the measured throughput within a time-out window. A key feature is that we exploit explicitly the traffic information and throughput requirements in devising the back-off time. Our results show that the proposed SAC scheme works well in opportunistic communication systems.     

MAC and Interworking Layers for an ATM Wireless System

High speed Asynchronous Transfer Mode (ATM) wireless networks are assuming a growing interest in the personal communication area [1–6]. This paper describes the design of a wireless ATM system, which is being implemented in the MEDIAN project belonging to the European Community (EC) Advance Communications Technologies and Services (ACTS) programme. The Medium Access Control (MAC) aims at providing a simple and efficient transport for ATM cells from a Base Station (BS), interfaced with the ATM Broadband Integrated Service Digital Network (B-ISDN), to ATM Portable Stations (PSs) and vice versa. A Time Division Duplex (TDD) scheme is adopted in which uplink and downlink frame durations can be varied frame-by-frame, in order to fit the present uplink/downlink traffic mix. Moreover, in the uplink, a contention-free based technique is considered in which the slots are assigned to the calls depending on the present load of the PS uplink buffers. The proposed interworking with the ATM network is based on the concept of intercepting the ATM Signalling and Management Cells at the BS, in order to deduce from the ATM Q.2931 messages information relevant to the registration, the call set-up and the MAC procedures.     

Ranking and adaptive ranking CDMA

This paper develops an uplink transmission scheduling scheme, referred to as Ranking CDMA, which selects a subset of users for transmission at each time slot. We introduce long- and short-term metrics that characterize its performance, and devise analytical methods for evaluating these performance measures. It turns out that, although Ranking CDMA has excellent long-term power efficiency compared to traditional CDMA, it suffers from a lack of short-term fairness, which is quantified in our calculations. To alleviate this deficiency, we propose Adaptive Ranking CDMA and analytically show that it yields moderate power-efficiency improvement over traditional CDMA, while maintaining short-term fairness.     

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.     

On the performance of packet-switched cellular networks for wireless data communications

Cellular frequency reuse is known to be an efficient method to allow many wireless telephone subscribers to share the same frequency band. However, for wireless data and multi-media communications optimum cell layouts differ essentially from typical solutions for telephone systems. We argue that wireless radio systems for bursty message traffic preferably use the entire bandwidth in each cell. Packet queuing delays are derived for a network with multipath fading channels, shadowing, path loss and discontinuously transmitting base stations. Interference between cells can be reduced by appropriately scheduling transmissions or by spatial collision resolution.Portions of this paper have been presented at the IEEE International Conferences on Personal Indoor Mobile Radio Communications (PIMRC) of 1993 in Yokohama and 1994 in The Hague.     

Scheduling and bandwidth allocation for the distribution of archived video in VOD systems

Providing costeffective videoondemand (VOD) services necessitates reducing the required bandwidth for transporting video over highspeed networks. In this paper, we investigate efficient schemes for transporting archived MPEGcoded video over a VOD distribution network. A video stream is characterized by a timevarying traffic envelope, which provides an upper bound on the bit rate. Using such envelopes, we show that video streams can be scheduled for transmission over the network such that the perstream allocated bandwidth is significantly less than the source peak rate. In a previous work [13], we investigated stream scheduling and bandwidth allocation using global traffic envelopes and homogeneous streams. In this paper, we generalize the scheduling scheme in [13] to include the heterogeneous case. We then investigate the allocation problem under windowbased traffic envelopes, which provide tight bounds on the bit rate. Using such envelopes, we introduce three streamscheduling schemes for multiplexing video connections at a server. The performance of these schemes is evaluated under static and dynamic scenarios. Our results indicate a significant reduction in the perstream allocated bandwidth when stream scheduling is used. While this reduction is obtained through statistical multiplexing, the transported streams are guaranteed stringent, deterministic quality of service (i.e., zero loss rate and small, bounded delay). In contrast to video smoothing, our approach requires virtually no buffer at the settop box since frames are delivered at their playback rate.     

Scheduling for information gathering on sensor network

We investigate a unique wireless sensor network scheduling problem in which all nodes in a cluster send exactly one packet to a designated sink node in an effort to minimize transmission time. However, node transmissions must be sufficiently isolated either in time or in space to avoid collisions. The problem is formulated and solved via graph representation. We prove that an optimal transmission schedule can be obtained efficiently through a pipeline-like schedule when the underlying topology is either line or tree. The minimum time required for a line or tree topology with nodes is . We further prove that our scheduling problem is NP-hard for general graphs. We propose a heuristic algorithm for general graphs. Our heuristic tries to schedule as many independent segments as possible to increase the degree of parallel transmissions. This algorithm is compared to an RTS/CTS based distributed algorithm. Preliminary simulated results indicate that our heuristic algorithm outperforms the RTS/CTS based distributed algorithm (up to 30%) and exhibits stable behavior.

The effects of asymmetry on TCP performance

In this paper, we study the effects of network asymmetry on endtoend TCP performance and suggest techniques to improve it. The networks investigated in this study include a wireless cable modem network and a packet radio network, both of which can form an important part of a mobile ad hoc network. In recent literature (e.g., [18]), asymmetry has been considered in terms of a mismatch in bandwidths in the two directions of a data transfer. We generalize this notion of bandwidth asymmetry to other aspects of asymmetry, such as latency and mediaaccess, and packet error rate, which are common in widearea wireless networks. Using a combination of experiments on real networks and simulation, we analyze TCP performance in such networks where the throughput achieved is not solely a function of the link and traffic characteristics in the direction of data transfer (the forward direction), but depends significantly on the reverse direction as well. We focus on bandwidth and latency asymmetries, and propose and evaluate several techniques to improve endtoend performance. These include techniques to decrease the rate of acknowledgments on the constrained reverse channel (ack congestion control and ack filtering), techniques to reduce source burstiness when acknowledgments are infrequent (TCP sender adaptation), and algorithms at the reverse bottleneck router to schedule data and acks differently from FIFO (acksfirst scheduling).     

Scheduling Real-Time Traffic With Deadlines over a Wireless Channel

Recently, there has been widespread interest in the extension of data networks to the wireless domain. However, scheduling results from the wireline domain do not carry over to wireless systems because wireless channels have unique characteristics not found in wireline channels, namely, limited bandwidth, bursty channel errors and location-dependent channel errors.In this paper, we study the problem of scheduling multiple real-time streams with deadlines, over a shared channel. We show that, in general, unlike the wireline case, the earliest due date (EDD) or shortest time to extinction (STE) policy is not always the optimal policy, even if the channel state is perfectly known and EDD is implemented only over channels in a Good state. Here, optimality is measured with respect to the number of packets lost due to deadline expiry. However, for most values of the channel parameters that are of practical interest, we show through analytical and numerical results that the EDD policy over Good channels is nearly optimal. Finally, through simulations, we also show that by combining this policy with fair scheduling mechanisms would result in scheduling algorithms that provide some degree of isolation between the sources as well as provide a natural way of compensating channels that see prolonged error bursts.     

Immediate neighbor scheduling (INS): An adaptive protocol for mobile ad hoc networks using direct-sequence spread-spectrum modulation

We investigate a new approach for scheduling transmissions in a mobile ad hoc network employing direct-sequence spread-spectrum (DSSS). Multiple-access interference may be better tolerated in these systems, allowing higher levels of spatial reuse and a reduction in the overhead required to schedule transmissions. We present a protocol which leverages these features of DSSS to support greater end-to-end throughput and terminal mobility rates. A protocol extension allows terminals to adjust protocol overhead in order to preserve network connectivity in sparse networks. For each transmission, terminals use a combination of common and transmitter-oriented spreading sequences in a format which allows for discovery of nearby terminals and adaptation of transmission rates to maximize throughput. The protocol does not operate over an artificial network graph, nor does it require an initialization phase or two-way exchange of information during a transmission slot. Through simulations, we evaluate the performance of the transmission scheduling protocol in a variety of static and mobile scenarios. For comparison, we also simulate a centralized transmission scheduling protocol with perfect knowledge of topology.