This paper presents several approximate formulas for the Wiener filter (WF), the optimal linear filter minimizing the mean-squared error. Compared to the WF, our formulas do not directly involve inverting the observation covariance matrix. An important consequence is that our approximate filters do not suffer from the ill-conditioning of the covariance matrix and are numerically reliable to compute. In addition, we prove that the approximate formulas converge to the WF as certain approximate terms vanish. Finally, our performance-complexity tradeoff analysis with empirical data show that our filters are two orders of magnitude faster than the WF without compromising any accuracy.

Occupancy grids encode for hot spots on a map that is represented by a two dimensional grid of disjoint cells. The problem is to recursively update the probability that each cell in the grid is occupied, based on a sequence of sensor measurements from a moving platform. In this paper, we provide a new Bayesian framework for generating these probabilities that does not assume statistical independence between the occupancy state of grid cells. This approach is made analytically tractable through the use of binary asymmetric channel models that capture the errors associated with observing the occupancy state of a grid cell. Binary-valued measurement vectors are the thresholded output of a sensor in a radar, sonar, or other sensory system. We compare the performance of the proposed framework to that of the classical formulation for occupancy grids. The results show that the proposed framework identifies occupancy grids with lower false alarm and miss detection rates, and requires fewer observations of the surrounding area, to generate an accurate estimate of occupancy probabilities when compared to conventional formulations.

In mobile wireless networks, mobility management (MM) is an important process to track and locate user equipments (UEs), including Internet-of-Things (IoT) devices, while moving throughout the network. In long term evolution (LTE) and fifth generation (5G) wireless networks, the two MM procedures are known as tracking area update (TAU) and Paging, which are burdensome for both mobile IoT/UEs and network-the IoT/UEs and network always initiate the TAU and Paging, respectively. Because of potentially very high-volume traffic and increasing density of high-mobility IoT/UEs, the TAU/Paging procedure increases the accompanied signaling overhead and the power consumption in the battery-limited IoT/UEs. Hence, this problem will become even worse in 5G because the latter is expected to accommodate exceptional services (e.g., longer IoT/UE battery lifetime). We propose a new solution to solve this problem, named gNB-based UE mobility tracking (gNB-based UeMT). This solution has four features achieving 5G goals. First, the mobile IoT/UEs will no longer trigger the TAU to report their location changes, giving much higher power savings with no signaling overhead. Instead, second, the network elements, gNBs, take over the responsibility of Tracking and Locating these IoT/UEs, giving always-known IoT/UE locations. Third, our Paging procedure is markedly improved over the conventional one, providing very fast IoT/UE reachability with no Paging messages being sent simultaneously. Fourth, this solution guarantees lightweight signaling overhead with very low Paging delay; it achieves about 92% reduction in the corresponding signaling overhead. To this end, our solution adds no implementation complexity; instead, it exploits the already existing LTE/5G communication protocols, functions, and measurement reports.

We develop polynomial-time heuristic methods to solve unimodular quadratic programming (UQP) approximately, which is known to be NP-hard. In the UQP framework, we maximize a quadratic function of a vector of complex variables with unit modulus. Several problems in active sensing and wireless communication applications boil down to UQP. With this motivation, we present two new heuristic methods with polynomial complexity to solve the UQP approximately. The first method is called dominant-eigenvector-matching; here the solution is picked that matches the complex arguments of the dominant eigenvector of the Hermitian matrix in the UQP formulation. We also provide a performance guarantee for this method. The second heuristic method, a greedy strategy, is shown to provide a performance guarantee of (1 - 1/e) with respect to the optimal objective value given that the objective function possesses a property called string submodularity. We also present results from simulations to demonstrate the performance of these heuristic methods.

Resource management for large-scale high performance computing systems pose difficult challenges to system administrators. The extreme scale of these modern systems require task scheduling algorithms that are capable of handling at least millions of tasks and thousands of machines. These large computing systems consume vast amounts of electricity leading to high operating costs. System administrators try to simultaneously reduce operating costs and offer state-of-the-art performance; however, these are often conflicting objectives. Highly scalable algorithms are necessary to schedule tasks efficiently and to help system administrators gain insight into energy/performance trade-offs of the system. System administrators can examine this trade-off space to quantify how much a difference in the performance level will cost in electricity, or analyze how much performance can be expected within an energy budget. In this study, we design a novel linear programming based resource allocation algorithm for a heterogeneous computing system to efficiently compute high quality solutions for simultaneously minimizing energy and makespan. These solutions are used to bound the Pareto front to easily trade-off energy and performance. The new algorithms are highly scalable in both solution quality and computation time compared to existing algorithms, especially as the problem size increases.

In this paper, we examine adaptive compression policies, when the sequence of vector-valued measurements to be compressed is noisy and the compressed variables are themselves noisy. The optimization criterion is information gain. In the case of sequential scalar compressions, the unit-norm compression vectors that greedily maximize per-stage information gain are eigenvectors of an a priori error covariance matrix, and the greedy policy selects them according to eigenvalues of a posterior covariance matrix. These eigenvalues depend on all previous compressions and are computed recursively. A water-filling solution is given for the optimum compression policy that maximizes net information gain, under a constraint on the average norm of compression vectors. We provide sufficient conditions under which the greedy policy for maximizing stepwise information gain actually is optimal in the sense of maximizing the net information gain. In the case of scalar compressions, our examples and simulation results illustrate that the greedy policy can be quite close to optimal when the noise sequences are white.

Each of a large number of nodes takes a measurement in sequence to decide between two hypotheses about the state of the world. Each node also has available the decisions of some of its immediate predecessors and uses these and its own measurement to make its decision. Each node broadcasts its decision through a binary symmetric channel, which randomly flips the decision. The question treated here is whether there exists a decision strategy consisting of a sequence of likelihood ratio tests such that the decisions approach the true hypothesis as the number of nodes increases. We show that if each node learns from bounded number of predecessors, then the decisions cannot converge to the underlying truth. We show that if each node learns from all predecessors then the decisions converge in probability to the underlying truth when the flipping probabilities are bounded away from 1/2. We also derive, in the case when the flipping probabilities tend to 1/2, a condition on the convergence rate of the flipping probabilities that is required for the decisions to converge to the true hypothesis in probability.

We present an approach to adaptive measurement selection in compressive sensing for estimating sparse signals. Given a fixed number of measurements, we consider the sequential selection of the rows of a compressive measurement matrix to maximize the mutual information between the measurements and the sparse signal's support. We formulate this problem as a partially observable Markov decision process (POMDP), which enables the application of principled reasoning for sequential measurement selection based on Bellman's optimality condition.

We study the detection error probability associated with a balanced binary relay tree, where the leaves of the tree correspond toNidentical and independent sensors. The root of the tree represents a fusion center that makes the overall detection decision. Each of the other nodes in the tree is a relay node that combines two binary messages to form a single output binary message. Only the leaves are sensors. In this way, the information from the sensors is aggregated into the fusion center via the relay nodes. In this context, we describe the evolution of the Type I and Type II error probabilities of the binary data as it propagates from the leaves toward the root. Tight upper and lower bounds for the total error probability at the fusion center as functions ofNare derived. These characterize how fast the total error probability converges to 0 with respect toN, even if the individual sensors have error probabilities that converge to 1/2.

Wireless sensor networks are considered in which sensors convey binary decisions over fading channels to a common fusion center. The fusion center first takes each received signal and makes an estimate of the transmitted bit. The average of the estimated bits is compared to a threshold to make a global decision. Exponential error bounds are derived that allow one to trade off signal-to-noise ratio versus the number of sensors to achieve desired average error levels. An attractive feature of the bounds is that they do not require exact knowledge of the wireless channel statistics; approximations are sufficient.

This research investigates the problem of robust dynamic resource allocation for heterogeneous distributed computing systems operating under imposed constraints. Often, such systems are expected to function in an environment where uncertainty in system parameters is common. In such an environment, the amount of processing required to complete an application may fluctuate substantially. Determining a resource allocation that accounts for this uncertainty-in a way that can provide a probability that a given level of service is achieved-is an important area of research. We define a mathematical model of stochastic robustness appropriate for a dynamic environment that can be used during resource allocation to aid heuristic decision making. In addition, we design a novel technique for maximizing stochastic robustness in this environment. Our performance results for this technique are compared with several well known resource allocation techniques in a simulated environment that models a heterogeneous distributed computing system.

The problem of finding efficient workload distribution techniques is becoming increasingly important today for heterogeneous distributed systems where the availability of compute nodes may change spontaneously over time. Therefore, the resource-allocation policy must be designed to be robust with respect to absence and re-emergence of compute nodes so that the performance of the system is maximized. Such a policy is developed in this work, and its performance is evaluated on a model of a dedicated system composed of a limited set of heterogeneous Web servers. Assuming that each HTML request results in a rdquorewardrdquo if completed before its hard deadline, the goal is to maximize a cumulative reward obtained in the system. A failure rate for each server is set relatively high to simulate its operation under harsh conditions. The results demonstrate that the proposed approach based on the concepts of the Derman-Lieberman-Ross theorem outperforms other policies compared in our experiments for inconsistent, processor-consistent, and task-processor-consistent types of heterogeneity.

We present a decentralized market-based approach to resource allocation in a heterogeneous overlay network. The presented resource allocation strategy assigns overlay network resources to traffic dynamically based on current utilization, thus, enabling the system to accommodate fluctuating demand for its resources. We present a mathematical model of our resource allocation environment that treats the allocation of system resources as a constrained optimization problem. Our presented resource allocation strategy is based on solving the dual of this centralized optimization problem. The solution to the dual of our centralized optimization problem suggests a simple decentralized algorithm for resource allocation that is extremely efficient. Our results demonstrate the near optimality of the proposed approach through extensive simulation of a real-world environment. That is, the conducted simulation study utilizes components taken from a real-world middleware application environment and clearly demonstrates the practicality of the approach in a realistic setting.

We study the problem of target tracking in a sensor network environment. In particular, we consider a target that moves according to a Markov chain, and a tracker that queries sets of sensors to obtain tracking information. We are interested in finding the minimum number of queries per time step such that a target is trackable under three different requirements. First we investigate the case where the tracker is required to know the exact location of the target at each time step. We then relax this requirement and explore the case where the tracker may lose track of the target at a given time step, but it is able to ";catch-up"; at a later time, regaining up-to-date information about the target's track. Finally, we consider the case where tracking information is only known after a delay of d time steps. We provide necessary and sufficient conditions on the number of queries per time step to track in the above three cases. These conditions are stated in terms of the entropy rate of the target's Markov chain.

In this paper, we show that random variables mapped under group homomorphisms from a uniformly distributed background random variable satisfy the Ingleton inequality. As corollaries, we recover two previous known results. The first is that the network throughput of linear network codes is, in general, constrained by the Ingleton inequality. The second and related result is that the network throughput of Abelian-group network codes - group network codes that are restricted to Abelian groups - is also constrained by the Ingleton inequality.

Minimizing energy consumption is crucial for portable wireless stations because they operate on a limited battery supply. The mechanism called power-saving mode (PSM) allows a network interface on a wireless station to enter the sleep mode whenever possible to reduce its energy consumption. At the same time, there has been a growing popularity in multi-rate wireless systems that can exploit the time-varying nature of the radio environment to increase the overall performance of the system under certain QoS/fairness requirements of users. The primary objective in these so-called systems is to increase the system throughput by giving priority to a mobile station experiencing better channel condition. In this work, we propose an opportunistic Power-Saving Mode and a corresponding scheduler design for wireless local area networks, which improves the energy consumption of PSM stations while maintaining throughput maximization, by exploiting time-varying channel conditions. We identify the challenges in the design and implementation of the PSM and the scheduler. We design a channel probing scheme and a scheduler called OEES (Opportunistic Energy Efficient Scheduler), which considers throughput maximization first and then focuses on minimizing energy consumption. Extensive simulations show that our scheme saves a significant amount of energy while maintaining throughput maximization.

Gupta and Kumar (2000) showed that the throughput capacity of static ad hoc networks with n randomly positioned nodes is /spl Theta/(/spl radic/(n/log n)). Grossglauser and Tse showed that node mobility increases the capacity to /spl Theta/(n), a substantial improvement. Achieving maximum capacity requires nodes to relay transmissions through other nodes. Each node must have a relay buffer for temporarily storing packets before forwarding them to their destination. We establish that if relay buffer sizes are bounded above by a constant, then mobility does not substantially increase the throughput capacity of mobile ad hoc networks. In particular, we show that the capacity of mobile networks with finite buffers is at most /spl Theta/(/spl radic/n). Finally we establish a scaling law relationship that characterizes the fundamental tradeoff between throughput capacity and relay buffer size. In particular, we show that the throughput capacity is at most /spl Theta/(/spl radic/(nb/sub n/)), where b/sub n/ is the size of the relay buffers.

We consider the problem of downlink scheduling for multiuser OFDM (orthogonal frequency division multiplexing) systems. We derive optimal scheduling policies under three QoS/fairness constraints - temporal fairness, utilitarian fairness, and minimum-performance guarantees. To calculate these optimal policies, we interpret the problem as a maximal bipartite matching problem. To solve this problem, we apply the modified Hungarian algorithm and a practical suboptimal algorithm. The simulation results show that our schemes achieve significant improvement in system performance compared with a non-opportunistic scheme.

We present a general framework for the problem of quality-of-service (QoS) routing with resource allocation for data networks. The framework represents the QoS parameters as functions rather than static metrics. The formulation incorporates the hardware/software implementation and its relation to the allocated resources into a single framework. The proposed formulation allows intelligent adaptation of QoS parameters and allocated resources during a path search, rather than decoupling the path search process from resource allocation. We present a dynamic programming algorithm that, under certain conditions, finds an optimal path between a source and destination node and computes the amount of resources needed at each node so that the end-to-end QoS requirements are satisfied. We present jitter and data droppage analyzes of various rate-based service disciplines and use the dynamic programming algorithm to solve the problem of QoS routing with resource allocation for networks that employ these service disciplines.

Scheduling resources on Grids is a well-known problem. The extension of Grids, to LambdaGrids requires scheduling of lambdas, i.e., end-to-end high-speed circuits. In this paper we propose an heuristic for the scheduling of lambdas specifically for file transfers, given that many eScience applications require high-throughput transfers of large files. We call this heuristic varying-bandwidth list scheduling (VBLS) because the scheduler returns a time-range-capacity (TRC) allocation vector with varying banchwidth levels assigned for different time ranges within the duration of a transfer. The advantage of VBLS over a fixed-bandwidth allocation scheme is that it allows the scheduler to backfill any holes left in resource allocations. Such a scheme is enabled by end host applications specifying the file size in their transfer requests. To characterize VBLS, we used analytical models and ran simulations. Our results show that VBLS performance is close to packet-switching performance, which means that file transfers can take advantage of bandwidth that becomes available subsequent to the start of transfers, a critical drawback of typical fixed-bandwidth allocation schemes in circuit-switched networks.

Time-Division Multiplexing/Frequency-Division Multiplexing (TDM/FDM) schemes are typically used in a fixed-bandwidth allocation mode, which means a call is assigned a fixed amount of bandwidth for its whole duration. For file transfers, such schemes compare unfavorably against statistical multiplexing schemes such as packet switching. This is because in fixed-bandwidth TDM/FDM schemes, once a file transfer is allocated a certain bandwidth, it cannot take advantage of bandwidth that becomes available as a result of other transfers completing. In this paper, we propose a Varying-Bandwidth List Scheduling (VBLS) heuristic for TDM/FDM networks in which a sender specifies the file size, maximum bandwidth limit and a desired start time, and the network returns a time-range-capacity allocation vector assigning varying bandwidth levels in different time ranges for the transfer. Simulation results show that VBLS performance is indistinguishable from packet-switching performance, and hence superior to the fixed-bandwidth allocation mode.

Most previous schemes for survivable routing assume that the maximum number of simultaneous link failures is known. In this paper, we take an alternative approach by introducing link failure probabilities to the routing problem, and allowing each link to be used for several channels. Based on these assumptions, we formulate a survivable multipath routing problem for point-to-point communications. We then develop two heuristic multipath routing schemes for this problem: CPMR (conditional-penalization multipath routing) and SPMR (successive-penalization multipath routing). To deal with the difficulty that link-sharing causes, our schemes use "link penalization" methods to control (but not prohibit) link-sharing. We show via simulation that our schemes have significantly higher routing success rates than a routing scheme that searches for disjoint paths.

A novel certified e-mail protocol that is particularly suitable for mobile environments is described. Our protocol uses an off-line trusted third party (TTP). Protocols with an off-line TTP-also known as optimistic protocols-have numerous practical advantages over protocols with an on-line TTP. Nonetheless, many protocols adopt an on-line TTP primarily because optimistic protocols often entail intricate cryptographic primitives that incur considerable overhead. By using a novel signature paradigm, which we call gradational signatures, we show that it is possible to construct optimistic protocols that are comparable to on-line protocols in terms of computation and communication overhead. This makes our scheme especially desirable in the mobile setting.

Proxy servers can be used to stream video stored at a geographically separate location. This separation between the proxy server and the storage introduces a non-negligible delay in retrieving video frames in real time. We develop an effective scheme to achieve consistent, high streaming quality under such delays. Central to the scheme is the control of buffer occupancy at the proxy server. We model the buffer as a bilinear dynamical system disturbed by a point process with stochastic state-dependent intensity, reflecting the behavior of an additive-increase/multiplicative-decrease transport protocol. Using the buffer model, we construct two controllers based on prediction of future system states, taking into account both the delay and the state-dependent disturbance. Our empirical study illustrates the effectiveness of the scheme and shows that the controllers exploiting the buffer model perform well in overcoming the adverse impact of the retrieval delay.

Applications such as e-commerce payment protocols, elec-tronic contract signing, and certified e-mail delivery require that fair exchange be assured. A fair-exchange protocol al-lows two parties to exchange items in a fair way so that either each party gets the other's item, or neither party does. We describe a novel method of constructing very ef-ficient fair-exchange protocols by distributing the computa-tion of RSA signatures. Specifically, we employ multisig-natures based on the RSA-signature scheme. To date, the vast majority of fair-exchange protocols require the use of zero-knowledge proofs, which is the most computationally intensive part of the exchange protocol. Using the intrinsic features of our multisignature model, we construct protocols that require no zero-knowledge proofs in the exchange proto-col. Use of zero-knowledge proofs is needed only in the pro-tocol setup phase--this is a one-time cost. Furthermore, our scheme uses multisignatures that are compatible with the underlying standard (single-signer) signature scheme, which makes it possible to readily integrate the fair-exchange fea-ture with existing e-commerce systems.

We describe a novel method for authenticating multicast packets that is robust against packet loss. Our focus is to minimize the size of the communication overhead required to authenticate the packets. Our approach is to encode the hash values and the signatures with Rabin's Information Dispersal Algorithm (IDA) to construct an authentication scheme that amortizes a single signature operation over multiple packets. This strategy is especially efficient in terms of space overhead, because just the essential elements needed for authentication (i.e., one hash per packet and one signature per group of packets) are used in conjunction with an erasure code that is space optimal. Using asymptotic techniques, we derive the authentication probability of our scheme using two different bursty loss models. A lower bound of the authentication probability is also derived for one of the loss models. To evaluate the performance of our scheme, we compare our technique with four other previously proposed schemes using empirical results.

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.

We describe a novel method for authenticating multicast packets that is robust against packet loss. Our main focus is to minimize the size of the communication overhead required to authenticate the packets. Our approach is to encode the hash values and the signatures with Rabin's Information Dispersal Algorithm (IDA) to construct an authentication scheme that amortizes a single signature operation over multiple packets. This strategy is especially efficient in terms of space overhead, because just the essential elements needed for authentication (i.e., one hash per packet and one signature per group of packets) are used in conjunction with an erasure code that is space optimal. To evaluate the performance of our scheme, we compare our technique with four other previously proposed schemes using analytical and empirical results. Two different bursty loss models are considered in the analyses.

We explore the performance of minimum mean-square error (MMSE) multiuser receivers in wireless systems where the signatures are modeled as random and take values in complex space. First we study the conditional distribution of the output multiple-access interference (MAI) of the MMSE receiver. By appealing to the notion of conditional weak convergence, we find that the conditional distribution of the output MAI, given the received signatures and received powers, converges in probability to a proper complex Gaussian distribution that does not depend on the signatures. This result indicates that, in a large system, the output interference of the MMSE receiver is approximately Gaussian with high probability, and that systems with MMSE receivers are robust to the randomness of the signatures. Building on the Gaussianity of the output interference, we then take the quality of service (QoS) requirements as meeting the signal-to-interference ratio (SIR) constraints and identify the network capacity of single-class systems with random spreading. The network capacity is expressed uniquely in terms of the SIR requirements and received power distributions. Compared to the network capacity corresponding to the optimal signature allocation, we conclude that at the cost of transmission power, the gap between the network capacity corresponding to optimal signatures and that corresponding to random signatures can be made arbitrarily small. Therefore, from the viewpoint of the network capacity, systems with MMSE receivers are robust to the randomness of signatures.

Bandwidth allocation is a fundamental problem in communication networks. The problem of bandwidth allocation is further intensified when the requested bandwidth exceeds the available unused bandwidth and so not all requests can be completely served. This research examines on-line bandwidth allocation, where the decision for acceptance or rejection of the request has to be made when future requests and their arrival statistics are not known. A request can be defined as a flow of information from a source to a destination with a certain amount of bandwidth, a priority level, a utility function that is based on the bandwidth received and a worth that is based on the utility function and the priority level. The goal of this research is to develop a scheduling heuristic for an overloaded system that attempts to schedule the requests such that the sum of the worths of the requests satisfied in a fixed interval of rime is the maximum. The scheduling heuristic can preempt or degrade already-scheduled requests. Three different types of utility functions (step, linear, and concave) are examined. Other parameters being considered include network loading and the relative weights of the different priority levels. The heuristic variations developed are shown to perform well compared to a complete sharing policy and an upper bound.

We present an "opportunistic" transmission scheduling policy that exploits time-varying channel conditions and maximizes the system performance stochastically under a certain resource allocation fairness constraint. We establish the optimality of the scheduling scheme and also describe a practical scheduling procedure to implement our scheme. Through simulation results, we show that the scheme also works well for nonstationary scenarios and results in performance improvements of 20-150% compared with a scheduling scheme that does not take into account channel conditions. Furthermore, we note that in wireless networks, an important role of resource allocation is to balance the system performance and fairness among "good" and "bad" users. We propose three heuristic time-fraction assignment schemes, which approach the problem from different viewpoints.

We consider the congestion control problem in a communication network with multiple traffic sources, each modeled as a fully-controllable stream of fluid traffic. The controlled traffic shares a common bottleneck node with high-priority cross traffic described by a Markov-modulated fluid (MMF). Each controlled source is assumed to have a unique round-trip delay. We wish to maximize a linear combination of the throughput, delay, traffic loss rate, and a fairness metric at the bottleneck node. We introduce an online sampling-based burst-level congestion control scheme capable of performing effectively under rapidly-varying cross traffic by making explicit use of the provided MMF model of that variation. The control problem is posed as a finite-horizon Markov decision process and is solved heuristically using a technique called hindsight optimization. We provide a detailed derivation of our congestion control algorithm based on this technique. The distinguishing feature of our scheme relative to conventional congestion control schemes is that we exploit a stochastic model of the cross traffic. Our empirical study shows that our control scheme significantly outperforms the conventional proportional-derivative (PD) controller, achieving higher utilization, lower delay, and lower loss under reasonable fairness. The performance advantage of our scheme over the PD scheme grows as the rate variance of cross traffic increases, underscoring the effectiveness of our control scheme under variable cross traffic.

Distributed power control algorithms for systems with hard 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 non-cooperative 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 the 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.

We present an "opportunistic" transmission scheduling scheme that exploits time-varying channel conditions and maximizes the average system performance under minimum-performance guarantees. We establish the optimality of the scheduling scheme, and show that the proposed opportunistic scheduling scheme can provide a "no-loss" guarantee compared to non-opportunistic scheduling policies. Furthermore, we show that the feasibility region of users' requirements is convex, and discuss the associated admission control issues. Last, through simulation results, we show that the scheme results in significant performance improvement.

We present an "opportunistic" transmission scheduling policy that exploits time-varying channel conditions and maximizes the system performance stochastically under a certain resource allocation constraint. We establish the optimality of the scheduling scheme and also that every user experiences a performance improvement over any nonopportunistic scheduling policy when users have independent performance values. We demonstrate via simulation results that the scheme is robust to estimation errors and also works well for nonstationary scenarios, resulting in performance improvements of 20%-150% compared with a scheduling scheme that does not take into account channel conditions. Last, we discuss an extension of our opportunistic scheduling scheme to improve "short-term" performance.

In a mobile wireless system, fading effects can be classified into large-scale (long-term) effects and small-scale (short-term) effects. We use transmission power control to compensate for large-scale fading and exploit receiver antenna (space) diversity to combat small-scale fading. We show that the interferences across the antennas are jointly Gaussian in a large system, and then characterize the signal-to-interference ratio for both independent and correlated (across the antennas) small-scale fading cases. Our results show that when each user's small-scale fading effects are independent across the antennas, there is a clear separation between the gains of transmission power control and diversity combining, and the two gains are additive (in decibels). When each user's small-scale fading effects are correlated across the antennas, we observe that, in general, the gains of transmission power control and diversity combining are coupled. However, when the noise level diminishes to zero, using maximum ratio combining "decouples" the gains and achieves the same diversity gain as in the independent case. We then characterize the Pareto-optimal (minimum) transmission power allocation for the cases of perfect and noisy knowledge of the desired user's large-scale fading effects. We find that using antenna diversity leads to significant gains for the transmission power.

Multiple-access interference (MAI) in a code-division multiple-access (CDMA) system plays an important role in performance analysis and characterization of fundamental system limits. We study the behavior of the output MAI of the minimum mean-square error (MMSE) receiver employed in the uplink of a direct-sequence (DS)-CDMA system. We focus on imperfect power-controlled systems with random spreading, and establish that in a synchronous system (1) the output MAI of the MMSE receiver is asymptotically Gaussian, and (2) for almost every realization of the signatures and received powers, the conditional distribution of the output MAI converges weakly to the same Gaussian distribution as in the unconditional case. We also extend our study to asynchronous systems and establish the Gaussian nature of the output interference. These results indicate that in a large system the output interference is approximately Gaussian, and the performance of the MMSE receiver is robust to the randomness of the signatures and received powers. The Gaussianity justifies the use of single-user Gaussian codes for CDMA systems with linear MMSE receivers, and implies that from the viewpoints of detection and channel capacity, signal-to-interference ratio (SIR) is the key parameter that governs the performance of the MMSE receiver in a CDMA system.

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.

In a wireless system, fading effects can be classified into large-scale effects and small-scale effects. We use power control to compensate for large-scale fading and exploit spatial diversity to combat small-scale fading. We characterize the SIR and our results show that when each user's small-scale fading effects are independent across the antennas, there is a clear separation between the gains of power control and diversity combining, and the two gains are additive (in decibels). We then characterise the Pareto-optimal transmission power allocation.

In cellular wireless communication systems, uplink power control is needed to provide each mobile user with an acceptable signal to interference ratio (SIR) while simultaneously minimizing transmit power levels. We consider a class of distributed asynchronous power control algorithms based on the schemes used in IS-95 inner loop power control. Each user's received SIR is measured (using possibly outdated information) and compared to a threshold, and a single control bit is then sent to the user, indicating whether its power level should be increased or decreased. The SIR measurements and power updates do not require synchronization. We show that under certain conditions, this class of algorithms is stable and converges to a region around the optimal power assignment. We characterize this region and show that it can be made as small as desired by choosing the algorithm parameters appropriately. For an appropriate choice of algorithm parameters, we show that convergence occurs in a finite number of iterations and derive an upper bound. To illustrate our general results, we apply them to systems with fixed base station assignment, dynamic base station assignment, and macrodiversity. Finally, we give an example to illustrate the algorithm's robustness to errors in the power control commands.

In this paper, we develop a novel technique based on Markov chains to accurately estimate power sensitivities to primary inputs in CMOS sequential circuits. A key application of power sensitivities is to construct a complicated power surface in the specification-space so as to easily obtain the power dissipation under any distribution of primary inputs, thereby offering an effective power macromodel for high-level power estimation. We demonstrate that such a power surface can be approximated by only a limited number of representative points. This benefit dramatically reduces the CPU and memory requirements. We have verified the feasibility and accuracy of the new technique to estimate power sensitivities on a large number of sequential benchmark circuits. Results on the power dissipation under different distributions of primary inputs demonstrate the efficiency and effectiveness of our power macromodeling technique.

We study the admissibility and network capacity of imperfect power-controlled code-division multiple access (CDMA) systems with linear receivers in fading environments. In a CDMA system, a set of users is admissible if their simultaneous transmission does not result in violation of any of their quality-of-service (QoS) requirements; the network capacity is the maximum number of admissible users. We consider a single-cell imperfect power-controlled CDMA system, assuming known received power distributions. We identify the network capacities of single-class systems with matched-filter (MF) receivers for both the deterministic and random signature cases. We also characterize the network capacity of single-class systems with linear minimum-mean-square-error (MMSE) receivers for the deterministic signature case. The network capacities can be expressed uniquely in terms of the users' signal-to-interference ratio (SIR) requirements and received power distributions. For multiple-class systems equipped with MF receivers, we find a necessary and sufficient condition on the admissibility for the random signature case, but only a sufficient condition for the deterministic signature case. We also introduce the notions of effective target SIR and effective bandwidth, which are useful in determining the admissibility and hence network capacity of an imperfect power-controlled system.

For pre-orchestrated multimedia documents, the important QoS parameters are bandwidth, jitter and reliability. A data network may employ a large number of service disciplines that provide guaranteed QoS. In this paper, we propose a network model, which we call the jitter graph, to capture the bandwidth, jitter and reliability of a large number of service disciplines. The significance of this model is that it abstracts the properties of the network, which allows the design of QoS routing protocols, resource allocation policies, and traffic regulation schemes that are independent of the specific properties of each node. Based on this model, we propose a traffic regulation scheme that reduces, and possibly eliminates, jitter introduced by any service discipline that can be abstracted by the jitter graph network model. The proposed traffic regulation scheme, together with jitter graph model, are analyzed and simulated based on an existing service discipline.

We study an approach for sharing channels to improve network utilization in packet-switched cellular networks. This scheme exploits unused resources in neighboring cells without the need for global coordination. We formulate a minimax approach to optimizing the allocation of channels in this sharing scheme. We develop a distributed algorithm to achieve this objective and study its convergence. We illustrate, via simulation results, that the distributed channel sharing scheme performs better than the fixed channel scheme over a wide variety of traffic conditions.

We present a novel static power control scheme to improve system capacity in wireless cellular networks. Our basic idea is to reduce intercellular interference and improve the capture probability by coordinating transmission powers of users in different cells. This coordination is determined beforehand and no real-time coordination is required. Power control is static and fixed. We formulate and solve a generic optimal scheduling problem with our coordination scheme. We find that the optimal scheduling policy is in a simple form of bang-bang control, which is illustrated for a specific case with the uniform fairness constraint. We evaluate, via numerical analysis and simulation, both throughput and delay, and compare them with other schemes. We find that the coordination scheme can achieve significant performance improvement, in terms of both maximum throughput and throughput-delay tradeoff, over a wide range of capture ratio values.

Enhancing system capacity while maintaining quality of service is an important issue in wireless cellular networks. In this paper, we present a localized channel sharing scheme to address this problem. Our basic idea is to allow channels to be shared between adjacent cells at the expense of a smaller initial allocation of channels per cell. We show that this tradeoff results in a better utilization of network resources. An important feature of our sharing scheme is that channel management is localized between adjacent cells, and no global coordination or optimization is required, thus making it suitable for implementation. The sharing scheme can also facilitate handoff processing. We provide numerical results comparing our scheme with the channel reservation technique, and find a significant performance improvement over a wide range of traffic parameters and a variety of quality of service requirements.

Due to the fast-growing demand for network capacity in wireless networks, the characterization of network capacity has become one of the most fundamental and pressing issues. While there have been considerable efforts to study CDMA systems at both the physical layer and network layer, the network capacity of power-controlled CDMA systems with linear receivers, especially in fading environments, is not well-understood. In this paper, we study a single-cell synchronous CDMA system equipped with the matched filter receiver in fading channels, and identify the network capacity for single-class systems and the network capacity region for multiple-class systems assuming known distributions of received powers of mobile users. Both the network capacity and network capacity region can be uniquely expressed in terms of the users QoS requirements and the distributions of the received powers. We also find the tightest upper bound of the network capacity over all possible distributions of received powers, and explore the concepts of effective target SIR and effective bandwidth, which play an important role in determining the admissibility and characterizing the network capacity.

We develop deterministic necessary and sufficient conditions on individual noise sequences of a stochastic approximation algorithm for the error of the iterates to converge at a given rate. Specifically, suppose {/spl rho//sub n/} is a given positive sequence converging monotonically to zero. Consider a stochastic approximation algorithm x/sub n+1/=x/sub n/-a/sub n/(A/sub n/x/sub n/-b/sub n/)+a/sub n/e/sub n/, where {x/sub n/} is the iterate sequence, {a/sub n/} is the step size sequence, {e/sub n/} is the noise sequence, and x* is the desired zero of the function f(x)=Ax-b. Then, under appropriate assumptions, we show that x/sub n/-x*=o(/spl rho//sub n/) if and only if the sequence {e/sub n/} satisfies one of five equivalent conditions. These conditions are based on well-known formulas for noise sequences: Kushner and Clark's (1978) condition, Chen's (see Proc. IFAC World Congr., p.375-80, 1996) condition, Kulkarni and Horn's (see IEEE Trails Automat. Contr., vol.41, p.419-24, 1996) condition, a decomposition condition, and a weighted averaging condition. Our necessary and sufficient condition on {e/sub n/} to achieve a convergence rate of {/spl rho//sub n/} is basically that the sequence {e/sub n///spl rho//sub n/} satisfies any one of the above five well-known conditions. We provide examples to illustrate our result. In particular, we easily recover the familiar result that if a/sub n/=a/n and {e/sub n/} is a martingale difference process with bounded variance, then x/sub n/-x*=o(n/sup -1/2/(log(n))/sup /spl beta//) for any /spl beta/>1/2.

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.

We present a novel reduced-power channel reuse scheme to improve the spectrum efficiency in wireless packet cellular networks. The basic idea is to reduce intercellular interference and improve the capture probability by an a priori assignment of power levels of channels used in different cells. We formulate and solve an optimal channel-selection problem for our scheme. We find that the optimal policy is in a form of bang-bang control. We illustrate our channel-selection solution by a case study with uniform fairness constraint. We evaluate, via numerical analysis and simulation, both throughput and delay of the new scheme, and compare them with other schemes. We find that our scheme can achieve significant performance improvements, in terms of both the maximum throughput and throughput-delay tradeoff, over a wide range of capture ratio values.

In this paper ~vepropose a novel technique based on Markov &tins to accurately estimate polver sensitivities to primary inputs in CLIOS sequential circuits.The po!ver sensitivity y defiues the change in average po~ver dissipation due to changes in the input signal specification.Such sensitivities are estimated a< by-products of the average po~ver estimation, leading to an efficient implementation.A key appUcat ion of po~versensitivities is to construct a polver surface in the specification space so that po~ver dissipation under any distribut ion of primary inputs can easily be obtained, thereby providing an effective po~ver macromodel for high level po~ver estimation.lVe demonstrate that such a po~ver surface can be approximated by ordy a hmited number of representative points.This ;vi~dramaticdy reduce the CPU and memory requirements.Resdts on a large number of benchmark circuits have verified the feasibihty and accuracy of this technique.

Enhancing system capacity is an important issue in wireless cellular networks. In this paper, we present a new channel sharing scheme to address this problem. Our basic idea is to allow channels to be shared between adjacent cells. We propose a fixed channel assignment scheme to maximize channel reuse efficiency while allowing channel sharing. An important feature of our sharing scheme is that channel management is localized between adjacent cells, and no global coordination or optimization is required thus simplifying implementation. We provide simulation results comparing our scheme with the fixed channel assignment scheme.

The problem of handoffs in cellular networks is compounded in a LEO (low Earth orbit) satellite-based cellular network due to the relative motion of the satellites themselves with respect to a stationary observer on Earth. Typically, the velocity of motion of mobile telephones can be ignored when compared to the very high velocity of the footprints of satellites. We exploit this property of the LEO satellite systems and propose a handoff scheme that results in a significant decrease in handoff dropping. For the same handoff dropping probability, our scheme has a significantly lower new call blocking probability than the conventional reservation scheme. We present an analytical approximation that is in very good accord with simulation results.

We investigate the convergence properties of two different stochastic approximation algorithms for principal component analysis, and analytically explain some commonly observed experimental results. In our analysis, we use the theory of stochastic approximation, and in particular the results of Fabian, to explore the asymptotic mean square errors (AMSE's) of the algorithms. This study reveals the conditions under which the algorithms produce smaller AMSE's, and also the conditions under which one algorithm has a smaller AMSE than the other. Experimental study with multidimensional Gaussian data corroborate our analytical findings. We next explore the convergence rates of the two algorithms. Our experiments and an analytical explanation reveals the conditions under which the algorithms converge faster to the solution, and also the conditions under which one algorithm converges faster than the other. Finally, we observe that although one algorithm has a larger computation in each iteration, it leads to a smaller AMSE and converges faster for the minor eigenvectors when compared to the other algorithm.

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 (QoS) to already admitted calls in the network. Our scheme is based on a new concept called channel carrying: when a mobile user moves from one cell to another, under certain mobility conditions, the user is allowed to carry its current channel. 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 the 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 the performance under various constraints. We provide numerical results comparing our scheme with the traditional channel reservation techniques. We find that our scheme outperforms the reservation scheme over a broad range of traffic parameters.