Asymptotically Optimal Energy-Aware Routing for Multihop Wireless Networks With Renewable Energy Sources

In this paper, we develop a model to characterize the performance of multihop radio networks in the presence of energy constraints and design routing algorithms to optimally utilize the available energy. The energy model allows us to consider different types of energy sources in heterogeneous environments. The proposed algorithm is shown to achieve a competitive ratio (i.e., the ratio of the performance of any offline algorithm that has knowledge of all past and future packet arrivals to the performance of our online algorithm) that is asymptotically optimal with respect to the number of nodes in the network. The algorithm assumes no statistical information on packet arrivals and can easily be incorporated into existing routing schemes (e.g., proactive or on-demand methodologies) in a distributed fashion. Simulation results confirm that the algorithm performs very well in terms of maximizing the throughput of an energy-constrained network. Further, a new threshold-based scheme is proposed to reduce the routing overhead while incurring only minimum performance degradation.     

On updating signal subspaces

The authors develop an algorithm for adaptively estimating the noise subspace of a data matrix, as is required in signal processing applications employing the `signal subspace' approach. The noise subspace is estimated using a rank-revealing QR factorization instead of the more expensive singular value or eigenvalue decompositions. Using incremental condition estimation to monitor the smallest singular values of triangular matrices, the authors can update the rank-revealing triangular factorization inexpensively when new rows are added and old rows are deleted. Experiments demonstrate that the new approach usually requires O(n²) work to update an n×n matrix, and that it accurately tracks the noise subspace     

Channel carrying: a novel handoff scheme for mobile cellularnetworks

We present a new scheme that addresses the call handoff problem in mobile cellular networks. Efficiently solving the handoff problem is important for guaranteeing quality of service to already admitted calls in the network. Our scheme is based on a new approach called channel carrying: when a mobile user moves from one cell to another, render certain mobility conditions, the user is allowed to carry its current channel into the new cell. We propose a new channel assignment scheme to ensure that this movement of channels will not lead to any extra co-channel interference or channel locking. In our scheme, the mobility of channels relies entirely on localized information, and no global coordination is required. Therefore, the scheme is simple and easy to implement. We further develop a hybrid channel carrying scheme that allows us to maximize performance under various constraints     

A central-limit-theorem-based approach for analyzing queue behaviorin high-speed networks

In this paper, we study P(𝒬>x), the tail of the steady-state queue length distribution at a high-speed multiplexer. In particular, we focus on the case when the aggregate traffic to the multiplexer can be characterized by a stationary Gaussian process. We provide two asymptotic upper bounds for the tail probability and an asymptotic result that emphasizes the importance of the dominant time scale and the maximum variance. One of our bounds is in a single-exponential form and can be used to calculate an upper bound to the asymptotic constant. However, we show that this bound, being of a single-exponential form, may not accurately capture the tail probability. Our asymptotic result on the importance of the maximum variance and our extensive numerical study on a known lower bound motivate the development of our second asymptotic upper bound. This bound is expressed in terms of the maximum variance of a Gaussian process, and enables the accurate estimation of the tail probability over a wide range of queue lengths. We apply our results to Gaussian as well as multiplexed non-Gaussian input sources, and validate their performance via simulations. Wherever possible, we have conducted our simulation study using importance sampling in order to improve its reliability and to effectively capture rare events. Our analytical study is based on extreme value theory, and therefore different from the approaches using traditional Markovian and large deviations techniques     

Distributed admission control for power-controlled cellularwireless systems

It is well known that power control can help to improve spectrum utilization in cellular wireless systems. However, many existing distributed power control algorithms do not work well without an effective connection admission control (CAC) mechanism, because they could diverge and result in dropping existing calls when an infeasible call is admitted. In this work, based on a system parameter defined as the discriminant, we propose two distributed CAC algorithms for a power-controlled system. Under these CAC schemes, an infeasible call is rejected early, and incurs only a small disturbance to existing calls, while a feasible call is admitted and the system converges to the Pareto optimal power assignment. Simulation results demonstrate the performance of our algorithms     

A measurement-analytic approach for QoS estimation in a network based on the dominant time scale

We describe a measurement-analytic approach for estimating the overflow probability, an important measure of the quality of service (QoS), at a given multiplexing point in the network. A multiplexing point in the network could be a multiplexer or an output port of a switch or router where resources such as bandwidth and buffers are shared. Our approach impinges on using the notion of the dominant time scale (DTS), which corresponds to the most probable time scale over which overflow occurs. The DTS provides us with a measurement window for the statistics of the traffic, but is in fact itself defined in terms of the statistics of the traffic over all time. This, in essence, results in a chicken-and-egg type of unresolved problem. For the DTS to be useful for on-line measurements, we need to be able to break this chicken-and-egg cycle, and to estimate the DTS with only a bounded window of time over which the statistics of the traffic are to be measured. We present a stopping criterion to successfully break this cycle and find a bound on the DTS. Thus, the result has significant implications for network measurements. Our approach is quite different from other works in the literature that require off-line measurements of the entire trace of the traffic. In our case, we need to measure only the statistics of the traffic up to a bound on the DTS. We also investigate the characteristics of this upper bound on the DTS, and provide numerical results to illustrate the utility of our measurement analytic approach.     

Queueing properties of feedback flow control systems

In this paper, we consider a network with both controllable and uncontrollable flows. Uncontrollable flows are typically generated from applications with stringent QoS requirements and are given high priority. On the other hand, controllable flows are typically generated by elastic applications and can adapt to the available link capacities in the network. We provide a general model of such a system and analyze its queueing behavior. Specially, we obtain a lower bound and an asymptotic upper bound for the tail of the workload distribution at each link in the network. These queueing results provide us with guidelines on how to design a feedback flow control system. Simulation results show that the lower bound and asymptotic upper bound are quite accurate and that our feedback control method can effectively control the queue length in the presence of both controllable and uncontrollable traffic. Finally, we describe a distributed strategy that uses the notion of Active Queue Management (AQM) for implementing our flow control solution.     

A utility-based power-control scheme in wireless cellular systems

Distributed power-control algorithms for systems with hard signal-to-interference ratio (SIR) constraints may diverge when infeasibility arises. We present a power-control framework called utility-based power control (UBPC) by reformulating the problem using a softened SIR requirement (utility) and adding a penalty on power consumption (cost). Under this framework, the goal is to maximize the net utility, defined as utility minus cost. Although UBPC is still noncooperative and distributed in nature, some degree of cooperation emerges: a user will automatically decrease its target SIR (and may even turn off transmission) when it senses that traffic congestion is building up. This framework enables us to improve system convergence and to satisfy heterogeneous service requirements (such as delay and bit error rate) for integrated networks with both voice users and data users. Fairness, adaptiveness, and a high degree of flexibility can be achieved by properly tuning parameters in UBPC.     

Admission control for statistical QoS: theory and practice

In networks that support quality of service, an admission control algorithm determines whether or not a new traffic flow can be admitted to the network such that all users will receive their required performance. Such an algorithm is a key component of future multiservice networks because it determines the extent to which network resources are utilized and whether the promised QoS parameters are actually delivered. The goals in this article are threefold. First, we describe and classify a broad set of proposed admission control algorithms. Second, we evaluate the accuracy of these algorithms via experiments using both on-off sources and long traces of compressed video; we compare the admissible regions and QoS parameters predicted by our implementations of the algorithms with those obtained from trace-driven simulations. Finally, we identify the key aspects of an admission control algorithm necessary for achieving a high degree of accuracy and hence a high statistical multiplexing gain