Scheduling for Stable and Reliable Communication Over Multiaccess Channels and Degraded Broadcast Channels

We model communication of bursty sources: 1) over multiaccess channels, with either independent decoding or joint decoding and 2) over degraded broadcast channels, by a discrete-time multiclass processor sharing queue. We utilize error exponents to give a characterization of the processor sharing queue. We analyze the processor sharing queue model for the stable region of message arrival rates, and show the existence of scheduling policies for which the stability region converges to the information-theoretic capacity region in an appropriate limiting sense.

Robust Reentry Guidance of a Reusable Launch Vehicle Using Model Predictive Static Programming

A robust suboptimal reentry guidance scheme is presented for a reusable launch vehicle using the recently developed, computationally efficient model predictive static programming. The formulation uses the nonlinear vehicle dynamics with a spherical and rotating Earth, hard constraints for desired terminal conditions, and an innovative cost function having several components with associated weighting factors that can account for path and control constraints in a soft constraint manner, thereby leading to smooth solutions of the guidance parameters. The proposed guidance essentially shapes the trajectory of the vehicle by computing the necessary angle of attack and bank angle that the vehicle should execute. The path constraints are the structural load constraint, thermal load constraint, bounds on the angle of attack, and bounds on the bank angle. In addition, the terminal constraints include the three-dimensional position and velocity vector components at the end of the reentry. Whereas the angle-of-attack command is generated directly, the bank angle command is generated by first generating the required heading angle history and then using it in a dynamic inversion loop considering the heading angle dynamics. Such a two-loop synthesis of bank angle leads to better management of the vehicle trajectory and avoids mathematical complexity as well. Moreover, all bank angle maneuvers have been confined to the middle of the trajectory and the vehicle ends the reentry segment with near-zero bank angle, which is quite desirable. It has also been demonstrated that the proposed guidance has sufficient robustness for state perturbations as well as parametric uncertainties in the model.

Fair Scheduling in Cellular Systems in the Presence of Noncooperative Mobiles

We consider the problem of ``fair'' scheduling the resources to one of the many mobile stations by a centrally controlled base station (BS). The BS is the only entity taking decisions in this framework based on truthful information from the mobiles on their radio channel. We study the well-known family of parametric alpha-fair scheduling problems from a game-theoretic perspective in which some of the mobiles may be noncooperative. We first show that if the BS is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. If the BS is aware of the noncooperative mobiles, a new game arises with BS as an additional player. It can then do better by neglecting the signals from the noncooperative mobiles. The BS, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). This new policy along with the truthful signals from mobiles forms a Nash equilibrium (NE) that we call a Truth Revealing Equilibrium. Finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise nonrobust (in presence of noncooperation) alpha-fair scheduling algorithms.

Curvature-constrained trajectory generation for waypoint following for miniature air vehicle

This paper addresses trajectory generation problem of a fixed-wing miniature air vehicle, constrained by bounded turn rate, to follow a given sequence of waypoints. An extremal path, named as g-trajectory, that transitions between two consecutive waypoint segments (obtained by joining two waypoints in sequence) in a time-optimal fashion is obtained. This algorithm is also used to track the maximum portion of waypoint segments with the desired shortest distance between the trajectory and the associated waypoint. Subsequently, the proposed trajectory is compared with the existing transition trajectory in the literature to show better performance in several aspects. Another optimal path, named as loop trajectory, is developed for the purpose of tracking the waypoints as well as the entire waypoint segments. This paper also proposes algorithms to generate trajectories in the presence of steady wind to meet the same objective as that of no-wind case. Due to low computational burden and simplicity in the design procedure, these trajectory generation approaches are implementable in real time for miniature air vehicles.

Two timescale convergent Q-learning for sleep-scheduling in wireless sensor networks

In this paper, we consider an intrusion detection application for Wireless Sensor Networks. We study the problem of scheduling the sleep times of the individual sensors, where the objective is to maximize the network lifetime while keeping the tracking error to a minimum. We formulate this problem as a partially-observable Markov decision process (POMDP) with continuous stateaction spaces, in a manner similar to Fuemmeler and Veeravalli (IEEE Trans Signal Process 56(5), 2091-2101, 2008). However, unlike their formulation, we consider infinite horizon discounted and average cost objectives as performance criteria. For each criterion, we propose a convergent on-policy Q-learning algorithm that operates on two timescales, while employing function approximation. Feature-based representations and function approximation is necessary to handle the curse of dimensionality associated with the underlying POMDP. Our proposed algorithm incorporates a policy gradient update using a one-simulation simultaneous perturbation stochastic approximation estimate on the faster timescale, while the Q-value parameter (arising from a linear function approximation architecture for the Q-values) is updated in an on-policy temporal difference algorithm-like fashion on the slower timescale. The feature selection scheme employed in each of our algorithms manages the energy and tracking components in a manner that assists the search for the optimal sleep-scheduling policy. For the sake of comparison, in both discounted and average settings, we also develop a function approximation analogue of the Q-learning algorithm. This algorithm, unlike the two-timescale variant, does not possess theoretical convergence guarantees. Finally, we also adapt our algorithms to include a stochastic iterative estimation scheme for the intruder's mobility model and this is useful in settings where the latter is not known. Our simulation results on a synthetic 2-dimensional network setting suggest that our algorithms result in better tracking accuracy at the cost of only a few additional sensors, in comparison to a recent prior work.

Rollover-Preventive Force Synthesis at Active Suspensions in a Vehicle Performing a Severe Maneuver With Wheels Lifted Off

Among the intelligent safety technologies for road vehicles, active suspensions controlled by embedded computing elements for preventing rollover have received a lot of attention. The existing models for synthesizing and allocating forces in such suspensions are conservatively based on the constraints that are valid until no wheels lift off the ground. However, the fault tolerance of the rollover-preventive systems can be enhanced if the smart/active suspensions can intervene in the more severe situation in which the wheels have just lifted off the ground. The difficulty in computing control in the last situation is that the vehicle dynamics then passes into the regime that yields a model involving disjunctive constraints on the dynamics. Simulation of dynamics with disjunctive constraints in this context becomes necessary to estimate, synthesize, and allocate the intended hardware realizable forces in an active suspension. In this paper, we give an algorithm for the previously mentioned problem by solving it as a disjunctive dynamic optimization problem. Based on this, we synthesize and allocate the roll-stabilizing time-dependent active suspension forces in terms of sensor output data. We show that the forces obtained from disjunctive dynamics are comparable with existing force allocations and, hence, are possibly realizable in the existing hardware framework toward enhancing the safety and fault tolerance.

A Distributed TDMA Slot Scheduling Algorithm for Spatially Correlated Contention in WSNs

In WSNs the communication traffic is often time and space correlated, where multiple nodes in a proximity start transmitting simultaneously. Such a situation is known as spatially correlated contention. The random access method to resolve such contention suffers from high collision rate, whereas the traditional distributed TDMA scheduling techniques primarily try to improve the network capacity by reducing the schedule length. Usually, the situation of spatially correlated contention persists only for a short duration, and therefore generating an optimal or suboptimal schedule is not very useful. Additionally, if an algorithm takes very long time to schedule, it will not only introduce additional delay in the data transfer but also consume more energy. In this paper, we present a distributed TDMA slot scheduling (DTSS) algorithm, which considerably reduces the time required to perform scheduling, while restricting the schedule length to the maximum degree of interference graph. The DTSS algorithm supports unicast, multicast, and broadcast scheduling, simultaneously without any modification in the protocol. We have analyzed the protocol for average case performance and also simulated it using Castalia simulator to evaluate its runtime performance. Both analytical and simulation results show that our protocol is able to considerably reduce the time required for scheduling.

Low Complexity Power and Scheduling Policies for Wireless Networks to Provide Quality of Service

We consider optimal power allocation policies for a single server, multiuser system. The power is consumed in transmission of data only. The transmission channel may experience multipath fading. We obtain very efficient, low computational complexity algorithms which minimize power and ensure stability of the data queues. We also obtain policies when the users may have mean delay constraints. If the power required is a linear function of rate then we exploit linearity and obtain linear programs with low complexity.

Performance of OFDM Systems With Best-m Feedback, Scheduling, and Delays for Uniformly Correlated Subchannels

Contemporary cellular standards, such as Long Term Evolution (LTE) and LTE-Advanced, employ orthogonal frequency-division multiplexing (OFDM) and use frequency-domain scheduling and rate adaptation. In conjunction with feedback reduction schemes, high downlink spectral efficiencies are achieved while limiting the uplink feedback overhead. One such important scheme that has been adopted by these standards is best-m feedback, in which every user feeds back its m largest subchannel (SC) power gains and their corresponding indices. We analyze the single cell average throughput of an OFDM system with uniformly correlated SC gains that employs best-m feedback and discrete rate adaptation. Our model incorporates three schedulers that cover a wide range of the throughput versus fairness tradeoff and feedback delay. We show that, for small m, correlation significantly reduces average throughput with best-m feedback. This result is pertinent as even in typical dispersive channels, correlation is high. We observe that the schedulers exhibit varied sensitivities to correlation and feedback delay. The analysis also leads to insightful expressions for the average throughput in the asymptotic regime of a large number of users.

An Implementation of Partitioned Scheduling Scheme for Hard Real-Time Tasks in Multicore Linux with Fair Share for Linux Tasks

The correctness of a hard real-time system depends its ability to meet all its deadlines. Existing real-time systems use either a pure real-time scheduler or a real-time scheduler embedded as a real-time scheduling class in the scheduler of an operating system (OS). Existing implementations of schedulers in multicore systems that support real-time and non-real-time tasks, permit the execution of non-real-time tasks in all the cores with priorities lower than those of real-time tasks, but interrupts and softirqs associated with these non-real-time tasks can execute in any core with priorities higher than those of real-time tasks. As a result, the execution overhead of real-time tasks is quite large in these systems, which, in turn, affects their runtime. In order that the hard real-time tasks can be executed in such systems with minimal interference from other Linux tasks, we propose, in this paper, an integrated scheduler architecture, called SchedISA, which aims to considerably reduce the execution overhead of real-time tasks in these systems. In order to test the efficacy of the proposed scheduler, we implemented partitioned earliest deadline first (P-EDF) scheduling algorithm in SchedISA on Linux kernel, version 3.8, and conducted experiments on Intel core i7 processor with eight logical cores. We compared the execution overhead of real-time tasks in the above implementation of SchedISA with that in SCHED_DEADLINE's P-EDF implementation, which concurrently executes real-time and non-real-time tasks in Linux OS in all the cores. The experimental results show that the execution overhead of real-time tasks in the above implementation of SchedISA is considerably less than that in SCHED_DEADLINE. We believe that, with further refinement of SchedISA, the execution overhead of real-time tasks in SchedISA can be reduced to a predictable maximum, making it suitable for scheduling hard real-time tasks without affecting the CPU share of Linux tasks.

Wireless scheduling with partial channel state information: large deviations and optimality

We consider a server serving a time-slotted queued system of multiple packet-based flows, where not more than one flow can be serviced in a single time slot. The flows have exogenous packet arrivals and time-varying service rates. At each time, the server can observe instantaneous service rates for only a subset of flows ( selected from a fixed collection of observable subsets) before scheduling a flow in the subset for service. We are interested in queue length aware scheduling to keep the queues short. The limited availability of instantaneous service rate information requires the scheduler to make a careful choice of which subset of service rates to sample. We develop scheduling algorithms that use only partial service rate information from subsets of channels, and that minimize the likelihood of queue overflow in the system. Specifically, we present a new joint subset-sampling and scheduling algorithm called Max-Exp that uses only the current queue lengths to pick a subset of flows, and subsequently schedules a flow using the Exponential rule. When the collection of observable subsets is disjoint, we show that Max-Exp achieves the best exponential decay rate, among all scheduling algorithms that base their decision on the current ( or any finite past history of) system state, of the tail of the longest queue. To accomplish this, we employ novel analytical techniques for studying the performance of scheduling algorithms using partial state, which may be of independent interest. These include new sample-path large deviations results for processes obtained by non-random, predictable sampling of sequences of independent and identically distributed random variables. A consequence of these results is that scheduling with partial state information yields a rate function significantly different from scheduling with full channel information. In the special case when the observable subsets are singleton flows, i.e., when there is effectively no a priori channel state information, Max-Exp reduces to simply serving the flow with the longest queue; thus, our results show that to always serve the longest queue in the absence of any channel state information is large deviations optimal.

Performance of New Dynamic Benefit-Weighted Scheduling Scheme in DiffServ Networks

In this paper, we design a new dynamic packet scheduling scheme suitable for differentiated service (DiffServ) network. Designed dynamic benefit weighted scheduling (DBWS) uses a dynamic weighted computation scheme loosely based on weighted round robin (WRR) policy. It predicts the weight required by expedited forwarding (EF) service for the current time slot (t) based on two criteria; (i) previous weight allocated to it at time (t-1), and (ii) the average increase in the queue length of EF buffer. This prediction provides smooth bandwidth allocation to all the services by avoiding overbooking of resources for EF service and still providing guaranteed services for it. The performance is analyzed for various scenarios at high, medium and low traffic conditions. The results show that packet loss is minimized, end to end delay is minimized and jitter is reduced and therefore meet quality of service (QoS) requirement of a network.

Nonlinear control of an air-breathing engine including its validation with vehicle guidance

An implementable nonlinear control design approach is presented for a supersonic air-breathing ramjet engine. The primary objective is to ensure that the thrust generated by the engine tracks the commanded thrust without violating the operational constraints. An important constraint is to manage the shock wave location in the intake so that it neither gets detached nor gets too much inside the intake. Both the objectives are achieved by regulating the fuel flow to the combustion chamber and by varying the throat area of the nozzle simultaneously. The design approach accounts for the nonlinear cross-coupling effects and nullifies those. Also, an extended Kalman filter has been used to filter out the sensor and process noises as well as to make the states available for feedback. Furthermore, independent control design has been carried out for the actuators. To test the performance of the engine for a realistic flight trajectory, a representative trajectory is generated through a trajectory optimization process, which is augmented with a newly-developed finite-time state dependent Riccati equation technique for nullifying the perturbations online. Satisfactory overall performance has been obtained during both climb and cruise phases. (C) 2015 Elsevier Masson SAS. All rights reserved.

PLAStiCC: Predictive Look-Ahead Scheduling for Continuous dataflows on Clouds

Scalable stream processing and continuous dataflow systems are gaining traction with the rise of big data due to the need for processing high velocity data in near real time. Unlike batch processing systems such as MapReduce and workflows, static scheduling strategies fall short for continuous dataflows due to the variations in the input data rates and the need for sustained throughput. The elastic resource provisioning of cloud infrastructure is valuable to meet the changing resource needs of such continuous applications. However, multi-tenant cloud resources introduce yet another dimension of performance variability that impacts the application's throughput. In this paper we propose PLAStiCC, an adaptive scheduling algorithm that balances resource cost and application throughput using a prediction-based lookahead approach. It not only addresses variations in the input data rates but also the underlying cloud infrastructure. In addition, we also propose several simpler static scheduling heuristics that operate in the absence of accurate performance prediction model. These static and adaptive heuristics are evaluated through extensive simulations using performance traces obtained from Amazon AWS IaaS public cloud. Our results show an improvement of up to 20% in the overall profit as compared to the reactive adaptation algorithm.

A Fast and Fault-Tolerant Distributed Algorithm for Near-Optimal TDMA Scheduling in WSNs

The time division multiple access (TDMA) based channel access mechanisms perform better than the contention based channel access mechanisms, in terms of channel utilization, reliability and power consumption, specially for high data rate applications in wireless sensor networks (WSNs). Most of the existing distributed TDMA scheduling techniques can be classified as either static or dynamic. The primary purpose of static TDMA scheduling algorithms is to improve the channel utilization by generating a schedule of smaller length. But, they usually take longer time to schedule, and hence, are not suitable for WSNs, in which the network topology changes dynamically. On the other hand, dynamic TDMA scheduling algorithms generate a schedule quickly, but they are not efficient in terms of generated schedule length. In this paper, we propose a novel scheme for TDMA scheduling in WSNs, which can generate a compact schedule similar to static scheduling algorithms, while its runtime performance can be matched with those of dynamic scheduling algorithms. Furthermore, the proposed distributed TDMA scheduling algorithm has the capability to trade-off schedule length with the time required to generate the schedule. This would allow the developers of WSNs, to tune the performance, as per the requirement of prevalent WSN applications, and the requirement to perform re-scheduling. Finally, the proposed TDMA scheduling is fault-tolerant to packet loss due to erroneous wireless channel. The algorithm has been simulated using the Castalia simulator to compare its performance with those of others in terms of generated schedule length and the time required to generate the TDMA schedule. Simulation results show that the proposed algorithm generates a compact schedule in a very less time.