Optimal control of arrivals to queues with delayed queue length information

We consider discrete-time versions of two classical problems in the optimal control of admission to a queueing system: i) optimal routing of arrivals to two parallel queues and ii) optimal acceptance/rejection of arrivals to a single queue. We extend the formulation of these problems to permit a k step delay in the observation of the queue lengths by the controller. For geometric inter-arrival times and geometric service times the problems are formulated as controlled Markov chains with expected total discounted cost as the minimization objective. For problem i) we show that when k = 1, the optimal policy is to allocate an arrival to the queue with the smaller expected queue length (JSEQ: Join the Shortest Expected Queue). We also show that for this problem, for k greater than or equal to 2, JSEQ is not optimal. For problem ii) we show that when k = 1, the optimal policy is a threshold policy. There are, however, two thresholds m(0) greater than or equal to m(1) > 0, such that mo is used when the previous action was to reject, and mi is used when the previous action was to accept.

Saturation throughput analysis of an input queueing ATM switch with multiclass bursty traffic

In this paper we consider an N x N non-blocking, space division ATM switch with input cell queueing. At each input, the cell arrival process comprises geometrically distributed bursts of consecutive cells for the various outputs. Motivated by the fact that some input links may be connected to metropolitan area networks, and others directly to B-ISDN terminals, we study the situation where there are two classes of inputs with different values of mean burst length. We show that when inputs contend for an output, giving priority to an input with smaller expected burst length yields a saturation throughput larger than if the reverse priority is given. Further, giving priority to less bursty traffic can give better throughput than if all the inputs were occupied by this less bursty traffic. We derive the asymptotic (as N --> infinity) saturation throughputs for each priority class.

Some Algorithms for Eigensubspace Estimation

An important tool in signal processing is the use of eigenvalue and singular value decompositions for extracting information from time-series/sensor array data. These tools are used in the so-called subspace methods that underlie solutions to the harmonic retrieval problem in time series and the directions-of-arrival (DOA) estimation problem in array processing. The subspace methods require the knowledge of eigenvectors of the underlying covariance matrix to estimate the parameters of interest. Eigenstructure estimation in signal processing has two important classes: (i) estimating the eigenstructure of the given covariance matrix and (ii) updating the eigenstructure estimates given the current estimate and new data. In this paper, we survey some algorithms for both these classes useful for harmonic retrieval and DOA estimation problems. We begin by surveying key results in the literature and then describe, in some detail, energy function minimization approaches that underlie a class of feedback neural networks. Our approaches estimate some or all of the eigenvectors corresponding to the repeated minimum eigenvalue and also multiple orthogonal eigenvectors corresponding to the ordered eigenvalues of the covariance matrix. Our presentation includes some supporting analysis and simulation results. We may point out here that eigensubspace estimation is a vast area and all aspects of this cannot be fully covered in a single paper. (C) 1995 Academic Press, Inc.

Performance analysis of the random early detection algorithm

In this article we consider a finite queue with its arrivals controlled by the random early detection algorithm. This is one of the most prominent congestion avoidance schemes in the Internet routers. The aggregate arrival stream from the population of transmission control protocol sources is locally considered stationary renewal or Markov modulated Poisson process with general packet length distribution. We study the exact dynamics of this queue and provide the stability and the rates of convergence to the stationary distribution and obtain the packet loss probability and the waiting time distribution. Then we extend these results to a two traffic class case with each arrival stream renewal. However, computing the performance indices for this system becomes computationally prohibitive. Thus, in the latter half of the article, we approximate the dynamics of the average queue length process asymptotically via an ordinary differential equation. We estimate the error term via a diffusion approximation. We use these results to obtain approximate transient and stationary performance of the system. Finally, we provide some computational examples to show the accuracy of these approximations.

Cramer-Rao bounds for source localization in shallow ocean with generalized Gaussian noise

Localization of underwater acoustic sources is a problem of great interest in the area of ocean acoustics. There exist several algorithms for source localization based on array signal processing.It is of interest to know the theoretical performance limits of these estimators. In this paper we develop expressions for the Cramer-Rao-Bound (CRB) on the variance of direction-of-arrival(DOA) and range-depth estimators of underwater acoustic sources in a shallow range-independent ocean for the case of generalized Gaussian noise. We then study the performance of some of the popular source localization techniques,through simulations, for DOA/range-depth estimation of underwater acoustic sources in shallow ocean by comparing the variance of the estimators with the corresponding CRBs.

Subspace-based DOA estimation using Fractional Lower Order statistics

Direction Of Arrival (DOA) estimation, using a sensor array, in the presence of non-Gaussian noise using Fractional Lower-Order Moments (FLOM)matrices is studied. In this paper, a new FLOM based technique using the Fractional Lower Order Infinity Norm based Covariance (FLIC) Matrix is proposed. The bounded property and the low-rank subspace structure of the FLIC matrix is derived. Performance of FLIC based DOA estimation using MUSIC, ESPRIT, is shown to be better than other FLOM based methods.

Genesis of return stroke current evolution at the wavefront

The channel dynamics at the wavefront is quite complex and is basically responsible for the evolution of return stroke current. The physical processes that actually contribute to the current evolution are not very clearly known. The enhancement of channel conductance at the wavefront is necessary for the current evolution and hence, return stroke. With regard to this, several questions arise like: (i) what causes the enhancement of this conductance, (ii) as the channel core temperature and electrical conductance are closely related, does one support the other and (iii) is the increase in core temperature on the nascent section of the channel is the result of free burning arc of the wavefront just below. These questions are investigated in detail in this work with appropriate transient thermal analysis and a macroscopic physical model for the lightning return stroke. Results clearly indicate that the contribution from the thermal field of the wavefront region to the adjacent nascent channel section is negligible as compared to the field enhancement brought in by the same. In other words, the whole process of return stroke evolution is dependent on the local heat generation at the nascent section caused by the enhancement of the electric field due to the arrival of the wavefront.

State Dependent Attempt Rate modeling of single cell IEEE 802.11 WLANs with homogeneous nodes and Poisson packet arrivals

We study a State Dependent Attempt Rate (SDAR) approximation to model M queues (one queue per node) served by the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) protocol as standardized in the IEEE 802.11 Distributed Coordination Function (DCF). The approximation is that, when n of the M queues are non-empty, the (transmission) attempt probability of each of the n non-empty nodes is given by the long-term (transmission) attempt probability of n saturated nodes. With the arrival of packets into the M queues according to independent Poisson processes, the SDAR approximation reduces a single cell with non-saturated nodes to a Markovian coupled queueing system. We provide a sufficient condition under which the joint queue length Markov chain is positive recurrent. For the symmetric case of equal arrival rates and finite and equal buffers, we develop an iterative method which leads to accurate predictions for important performance measures such as collision probability, throughput and mean packet delay. We replace the MAC layer with the SDAR model of contention by modifying the NS-2 source code pertaining to the MAC layer, keeping all other layers unchanged. By this model-based simulation technique at the MAC layer, we achieve speed-ups (w.r.t. MAC layer operations) up to 5.4. Through extensive model-based simulations and numerical results, we show that the SDAR model is an accurate model for the DCF MAC protocol in single cells. (C) 2012 Elsevier B.V. All rights reserved.

Rendezvous of Multiple UAVs with Collision Avoidance Using Consensus

This paper addresses the problem of multiple unmanned aerial vehicle (UAV) rendezvous when the UAVs have to perform maneuvers to avoid collisions with other UAVs. The proposed solution consists of using velocity control and a wandering maneuver, if needed, of the UAVs based on a consensus among them on the estimated time of arrival at the point of the rendezvous. This algorithm, with a slight modification is shown to be useful in tracking stationary or slowly moving targets with a standoff distance. The proposed algorithm is simple and computationally efficient. The simulation results demonstrate the efficacy of the proposed approach. DOI: 10.1061/(ASCE)AS.1943-5525.0000145. (C) 2012 American Society of Civil Engineers.

Loss ratio of the EDF scheduling policy with early discarding technique

This paper considers a firm real-time M/M/1 system, where jobs have stochastic deadlines till the end of service. A method for approximately specifying the loss ratio of the earliest-deadline-first scheduling policy along with exit control through the early discarding technique is presented. This approximation uses the arrival rate and the mean relative deadline, normalized with respect to the mean service time, for exponential and uniform distributions of relative deadlines. Simulations show that the maximum approximation error is less than 4% and 2% for the two distributions, respectively, for a wide range of arrival rates and mean relative deadlines. (C) 2013 Elsevier B.V. All rights reserved.

Tradeoff of average service cost and average delay for the state dependent M/M/1 queue

The optimal tradeoff between average service cost rate and average delay, is addressed for a M/M/1 queueing model with queue-length dependent service rates, chosen from a finite set. We provide an asymptotic characterization of the minimum average delay, when the average service cost rate is a small positive quantity V more than the minimum average service cost rate required for stability. We show that depending on the value of the arrival rate, the assumed service cost rate function, and the possible values of the service rates, the minimum average delay either a) increases only to a finite value, b) increases without bound as log(1/V), or c) increases without bound as 1/V, when V down arrow 0. We apply the analysis to a flow-level resource allocation model for a wireless downlink. We also investigate the asymptotic tradeoff for a sequence of policies which are obtained from an approximate fluid model for the M/M/1 queue.

Stability analysis of aperiodic messages scheduled in the dynamic segment of flex ray protocol

In a cyber physical system like vehicles number of signals to be communicated in a network system has an increasing trend. More and more mechanical and hydraulic parts are replaced by electronic control units and infotainment and multimedia applications has increased in vehicles. Safety critical hard real time messages and aperiodic messages communicated between electronic control units have been increased in recent times. Flexray is a high bandwidth protocol consisting of static segment for supporting hard real time messages and a dynamic segment for transmitting soft and non real time messages. In this paper, a method to obtain the stability region for the random arrival of messages in each electronic control units which is scheduled in the dynamic segment of Flexray protocol is presented. Number of mini slots available in the dynamic segment of Flexray restricts the arrival rate of tasks to the micro controllers or the number of micro controllers connected to the Flexray bus. Stability region of mathematical model of the system is compared with the Flexray protocol simulation results.

Block Sparse Estimator for Grid Matching in Single Snapshot DoA Estimation

In this work, the grid mismatch problem for a single snapshot direction of arrival estimation problem is studied. We derive a Bayesian Cramer-Rao bound for the grid mismatch problem with the errors in variables model and propose a block sparse estimator for grid matching and sparse recovery.

Antelope mating strategies facilitate invasion of grasslands by a woody weed

Intra and interspecific variation in frugivore behaviour can have important consequences for seed dispersal outcomes. However, most information comes from among-species comparisons, and within-species variation is relatively poorly understood. We examined how large intraspecific differences in the behaviour of a native disperser, blackbuck antelope Antilope cervicapra, influence dispersal of a woody invasive, Prosopis juliflora, in a grassland ecosystem. Blackbuck disperse P. juliflora seeds through their dung. In lekking blackbuck populations, males defend clustered or dispersed mating territories. Territorial male movement is restricted, and within their territories males defecate on dung-piles. In contrast, mixed-sex herds range over large areas and do not create dung-piles. We expected territorial males to shape seed dispersal patterns, and seed deposition and seedling recruitment to be spatially localized. Territorial males had a disproportionately large influence on seed dispersal. Adult males removed twice as much fruit as females, and seed arrival was disproportionately high on territories. Also, because lek-territories are clustered, seed arrival was spatially highly concentrated. Seedling recruitment was also substantially higher on territories compared with random sites, indicating that the local concentration of seeds created by territorial males continued into high local recruitment of seedlings. Territorial male behaviour may, thus, result in a distinct spatial pattern of invasion of grasslands by the woody P. juliflora. An ex situ experiment showed no beneficial effect of dung and a negative effect of light on seed germination. We conclude that large intraspecific behavioural differences within frugivore populations can result in significant variation in their effectiveness as seed dispersers. Mating strategies in a disperser could shape seed dispersal, seedling recruitment and potentially plant distribution patterns. These mating strategies may aid in the spread of invasives, such as P. juliflora, which could, in turn, negatively influence the behaviour and ecology of native dispersers.

6PANview: Application performance conscious network monitoring for 6LoWPAN based WSNs

6PANview[1] is a Wireless Sensor Network(WSN) monitoring system for 6LoWPAN/RPL networks which we developed as an overlay network for a WSN application. A monitoring system, while performing its operations for maintaining the health of the monitored network, must also be conscious of its impact on the application performance, and must strive to minimize this impact. To this end, we propose a centralized scheduling algorithm within 6PANview which non-intrusively analyzes application traffic arrival patterns at the base station, identifies network idle periods and schedules monitoring activities. The proposed algorithm finds those periodic sequences which are likely to have given rise to the pattern of arrivals seen at the base station. Parts of those sequences are then extended to coarsely predict future traffic and find epochs where low traffic is predicted, in order to schedule monitoring traffic or other activities at these times. We present simulation results for the proposed prediction and scheduling algorithm and its implementation as part of 6PANview. As an enhancement, we briefly talk about using 6PANview's overlay network architecture for distributed scheduling.