Search

Describes 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. Details on the fundamental measure of network congestion; Problem of QoS estimation; Value of the buffer overflow probability.

Presents a power-control framework called utility-based power control by reformulating the problem using a softened signal-to-interference ratio requirement and adding a penalty on power consumption. Characteristics of a wireless networks; Component of the resource management problem in wireless networks; Difference between a utility function and a cost function.

Introduces an opportunistic transmission scheduling policy that exploits time-varying channel conditions and maximizes the system performance stochastically under a certain resource allocation constraint in wireless networks. Roles of resource allocation schemes and scheduling policies in providing quality of service; Details of the opportunistic scheduling policy and its properties; Numerical results from simulations of the proposed scheduling scheme.

The efficient management of wireless resource is essential to the success of wireless systems. While power control is traditionally considered as a means to counteract the detrimental effects of channel fading, it is also a flexible mechanism to provide Quality of Service to individual users, and can be used as a platform for radio resource management. In this paper, we review the developments of distributed power control and related resource management problems in cellular wireless systems. We highlight the feasibility issue in a power-controlled system, which enables us to push the system toward high efficiency, and prevent the system from collapsing at the same time. Considering the unique features of multimedia traffic to be supported in future wireless systems, we also review power and rate control schemes proposed for wireless data, and present a framework for utility-based power control as a possible candidate for distributed power control of multimedia wireless systems. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Presents a study that examined the use of the sample-adaptive product quantizer to reduce encoding complexity. Background on the application of vector quantization in data compression; Analysis of the relationship between distortion and encoding complexity; Results and implications.

Presents information on a study which proposed a novel feedforward adaptive quantization scheme called the sample-adaptive product quantizer (SAPQ). Description of the proposed adaptive quantization scheme; Theoretical observations on SAPQ; Codebook design for nonuniform SAPQ; Simulation results and discussion.

In this paper, we investigate scheduling policies that minimize the age of information in single-hop queueing systems. We propose a Last-Generated, First-Serve (LGFS) scheduling policy, in which the packet with the earliest generation time is processed with the highest priority. If the service times are i.i.d. exponentially distributed, the preemptive LGFS policy is proven to be age-optimal in a stochastic ordering sense. If the service times are i.i.d. and satisfy a New-Better-than-Used (NBU) distributional property, the non-preemptive LGFS policy is shown to be within a constant gap from the optimum age performance. These age-optimality results are quite general: (i) they hold for arbitrary packet generation times and arrival times (including out-of-order packet arrivals); (ii) they hold for multi-server packet scheduling with the possibility of replicating a packet over multiple servers; (iii) and they hold for minimizing not only the time-average age and mean peak age, but also for minimizing the age stochastic process and any non-decreasing functional of the age stochastic process. If the packet generation time is equal to the packet arrival time, the LGFS policies reduce to the Last-Come, First-Serve (LCFS) policies. Hence, the age optimality results of LCFS-type policies are also established. [ABSTRACT FROM AUTHOR]

Communications in the millimeter wave (mmWave) band faces significant challenges due to variable channels, intermittent connectivity, and high energy usage. Moreover, speeds for electronic processing of data is of the same order as typical rates for mmWave interfaces, making the use of complex algorithms for tracking channel variations and adjusting resources impractical. In order to mitigate some of these challenges, we propose an architecture that integrates the sub-6 GHz and mmWave technologies. Our system exploits the spatial correlations between the sub-6 GHz and mmWave interfaces for beamforming and data transfer. Based on extensive experimentation in indoor and outdoor settings, we demonstrate that analog beamforming can be used in mmWave without incurring large overhead, thanks to the spatial correlations with sub-6 GHz. In addition, we incorporate the sub-6 GHz interface as a fallback (secondary) data transfer mechanism such that: 1) the negative effects of highly intermittent mmWave connectivity are mitigated and 2) the abundant mmWave capacity is fully exploited. To achieve these goals, we consider the problem of scheduling the arrival traffic over the mmWave or sub-6 GHz in order to maximize the mmWave throughput while delay (due to mmWave outages) is guaranteed to be bounded. We prove using subadditivity analysis that the optimal scheduling policy is based on a single threshold that can be easily adopted despite high link variations. Numerical results demonstrate that our scheduler provides a bounded mmWave delay performance, while it achieves a similar throughput performance as the throughput-optimal policies (e.g., MaxWeight). [ABSTRACT FROM PUBLISHER]

We consider the situation where multiple transportation service providers cooperate to offer an integrated multi-modal platform to enhance the convenience to the passengers through ease in multi-modal journey planning, payment, and first and last mile connectivity. This market structure allows the multi-modal platform to coordinate profits across modes and also provide incentives to the passengers. Accordingly, in this paper, we use cooperative game theory coupled with the hyperpath-based stochastic user equilibrium framework to study such a market. We assume that the platform sets incentives (price discount or excess charge on passengers) along every edge in the transportation network. We derive the continuity and monotonicity properties of the equilibrium flow with respect to the incentives along every edge. The optimal incentives that maximize the profit of the platform are obtained through a two time-scale stochastic approximation algorithm. We use the asymmetric Nash bargaining solution to design a fair profit sharing scheme among the service providers. We show that the profit for each service provider increases after cooperation on such a platform. Finally, we complement the theoretical results through two numerical simulations. [ABSTRACT FROM AUTHOR]

Recent studies have shown that retransmissions can cause heavy-tailed transmission delays even when packet sizes are light tailed. In addition, the impact of heavy-tailed delays persists even when packets size are upper bounded. The key question we study in this paper is how the use of coding techniques to transmit information, together with different system configurations, would affect the distribution of delay. To investigate this problem, we model the underlying channel as a Markov modulated binary erasure channel, where transmitted bits are either received successfully or erased. Erasure codes are used to encode information prior to transmission, which ensures that a fixed fraction of the bits in the codeword can lead to successful decoding. We use incremental redundancy codes, where the codeword is divided into codeword trunks and these trunks are transmitted one at a time to provide incremental redundancies to the receiver until the information is recovered. We characterize the distribution of delay under two different scenarios: 1) decoder uses memory to cache all previously successfully received bits and 2) decoder does not use memory, where received bits are discarded if the corresponding information cannot be decoded. In both cases, we consider codeword length with infinite and finite support. From a theoretical perspective, our results provide a benchmark to quantify the tradeoff between system complexity and the distribution of delay. [ABSTRACT FROM AUTHOR]

In an unreliable single-hop broadcast network setting, we investigate the throughput and decoding-delay performance of random linear network coding as a function of the coding window size and the network size. Our model consists of a source transmitting packets of a single flow to a set of n users over independent time-correlated erasure channels. The source performs random linear network coding (RLNC) over k (coding window size) packets and broadcasts them to the users. We note that the broadcast throughput of RLNC must vanish with increasing n, for any fixed k. Hence, in contrast to other works in the literature, we investigate how the coding window size k must scale for increasing n. Our analysis reveals that the coding window size of \Theta (\ln (n)) represents a phase transition rate, below which the throughput converges to zero, and above which, it converges to the broadcast capacity. Further, we characterize the asymptotic distribution of decoding delay and provide approximate expressions for the mean and variance of decoding delay for the scaling regime of k=\omega (\ln (n)). These asymptotic expressions reveal the impact of channel correlations on the throughput and delay performance of RLNC. We also show that how our analysis can be extended to other rateless block coding schemes such as the LT codes. Finally, we comment on the extension of our results to the cases of dependent channels across users and asymmetric channel model. [ABSTRACT FROM AUTHOR]

We consider a joint sampling and scheduling problem for optimizing data freshness in multi-source systems. Data freshness is measured by a non-decreasing penalty function of age of information, where all sources have the same age-penalty function. Sources take turns to generate update packets, and forward them to their destinations one-by-one through a shared channel with random delay. There is a scheduler, that chooses the update order of the sources, and a sampler, that determines when a source should generate a new packet in its turn. We aim to find the optimal scheduler-sampler pairs that minimize the total-average age-penalty at delivery times (Ta-APD) and the total-average age-penalty (Ta-AP). We prove that the Maximum Age First (MAF) scheduler and the zero-wait sampler are jointly optimal for minimizing the Ta-APD. Meanwhile, the MAF scheduler and a relative value iteration with reduced complexity (RVI-RC) sampler are jointly optimal for minimizing the Ta-AP. The RVI-RC sampler is based on a relative value iteration algorithm whose complexity is reduced by exploiting a threshold property in the optimal sampler. Finally, a low-complexity threshold-type sampler is devised via an approximate analysis of Bellman’s equation. This threshold-type sampler reduces to a simple water-filling sampler for a linear age-penalty function. [ABSTRACT FROM AUTHOR]

In this paper, delay-optimal and energy-efficient communication is studied for a single link under Markov random arrivals. We present the optimal tradeoff between delay and power over Additive White Gaussian Noise (AWGN) channels and extend the optimal tradeoff for block fading channels. Under time-correlated traffic arrivals, we develop a cross-layer solution that jointly considers the arrival rate, the queue length, and the channel state in order to minimize the average delay subject to a power constraint. For this purpose, we formulate the average delay and power problem as a Constrained Markov Decision Process (CMDP). Based on steady-state analysis for the CMDP, a Linear Programming (LP) problem is formulated to obtain the optimal delay-power tradeoff. We further show the optimal transmission strategy using a Lagrangian relaxation technique. Specifically, the optimal adaptive transmission is shown to have a threshold type of structure, where the thresholds on the queue length are presented for different transmission rates under the given arrival rates and channel states. By exploiting the result, we develop a threshold-based algorithm to efficiently obtain the optimal delay-power tradeoff. We show how a trajectory-sampling version of the proposed algorithm can be developed without the prior need of arrival statistics. [ABSTRACT FROM AUTHOR]

In networked systems such as communication networks or power grids, graph separation from node failures can damage the overall operation severely. One of the most important goals of network attackers is thus to separate nodes so that the sizes of connected components become small. In this work, we consider the problem of finding a minimum α -separator, that partitions the graph into connected components of sizes at most αn , where n is the number of nodes. To solve the α -separator problem, we develop a random walk algorithm based on Metropolis chain. We characterize the conditions for the first passage time (to find an optimal solution) of our algorithm. We also find an optimal cooling schedule, under which the random walk converges to an optimal solution almost surely. Furthermore, we generalize our algorithm to non-uniform node weights. We show through extensive simulations that the first passage time is less than O ( n 3 ), thereby validating our analysis. The solution found by our algorithm allows us to identify the weakest points in the network that need to be strengthened. Simulations in real topologies show that attacking a dense area is often not an efficient solution for partitioning a network into small components. [ABSTRACT FROM AUTHOR]

We study the stochastic multi-armed bandit (MAB) problem in the presence of sideobservations across actions that occur as a result of an underlying network structure. In our model, a bipartite graph captures the relationship between actions and a common set of unknowns such that choosing an action reveals observations for the unknowns that it is connected to. This models a common scenario in online social networks where users respond to their friends' activity, thus providing side information about each other's preferences. Our contributions are as follows: 1) We derive an asymptotic lower bound (with respect to time) as a function of the bi-partite network structure on the regret of any uniformly good policy that achieves the maximum long-term average reward. 2) We propose two policies - a randomized policy; and a policy based on the well-known upper confidence bound (UCB) policies - both of which explore each action at a rate that is a function of its network position. We show, under mild assumptions, that these policies achieve the asymptotic lower bound on the regret up to a multiplicative factor, independent of the network structure. Finally, we use numerical examples on a real-world social network and a routing example network to demonstrate the benefits obtained by our policies over other existing policies. [ABSTRACT FROM AUTHOR]

In this paper, we study how to optimally manage the freshness of information updates sent from a source node to a destination via a channel. A proper metric for data freshness at the destination is the age-of-information, or simply age, which is defined as how old the freshest received update is, since the moment that this update was generated at the source node (e.g., a sensor). A reasonable update policy is the zero-wait policy, i.e., the source node submits a fresh update once the previous update is delivered, which achieves the maximum throughput and the minimum delay. Surprisingly, this zero-wait policy does not always minimize the age. This counter-intuitive phenomenon motivates us to study how to optimally control information updates to keep the data fresh and to understand when the zero-wait policy is optimal. We introduce a general age penalty function to characterize the level of dissatisfaction on data staleness and formulate the average age penalty minimization problem as a constrained semi-Markov decision problem with an uncountable state space. We develop efficient algorithms to find the optimal update policy among all causal policies and establish sufficient and necessary conditions for the optimality of the zero-wait policy. Our investigation shows that the zero-wait policy is far from the optimum if: 1) the age penalty function grows quickly with respect to the age; 2) the packet transmission times over the channel are positively correlated over time; or 3) the packet transmission times are highly random (e.g., following a heavy-tail distribution). [ABSTRACT FROM PUBLISHER]

In this paper, we aim to obtain the optimal tradeoff between the average delay and the average power consumption in a communication system. In our system, the arrivals occur at each timeslot according to a Bernoulli arrival process, and are buffered at the transmitter waiting to be scheduled. We consider a finite buffer and allow the scheduling decision to depend on the buffer occupancy. In order to capture the realism in communication systems, the transmission power is assumed to be an increasing and convex function of the number of packets transmitted in each timeslot. This problem is modeled as a constrained Markov decision process (CMDP). We first prove that the optimal policy of the Lagrangian relaxation of the CMDP is deterministic and threshold-based. We then show that the optimal delay-power tradeoff curve is convex and piecewise linear, and the optimal policies of the original problem are also threshold-based. Based on the results, we propose an algorithm to obtain the optimal policy and the optimal tradeoff curve. We also show that the proposed algorithm is much more efficient than using general methods. The theoretical results and the algorithm are validated by linear programming and simulations. [ABSTRACT FROM PUBLISHER]

We study opportunistic multiuser scheduling in downlink networks with Markov-modeled outage channels. We consider the scenario that the scheduler does not have full knowledge of the channel state information, but instead estimates the channel state by exploiting the memory inherent in the Markov channels along with Automatic-Repeat-reQues-styled-styled feedback from the scheduled users. Opportunistic scheduling is optimized in two stages: 1) channel estimation and rate adaptation are performed to maximize the short-term throughput, i.e., the successful transmission rate of the scheduled user in the current slot and 2) user scheduling is performed, based on the short-term throughput, to maximize the overall long-term sum-throughput of the downlink. The scheduling problem is a partially observable Markov decision process with the classic exploitation versus exploration tradeoff that is difficult to quantify. We, therefore, study the problem in the framework of restless multiarmed bandit processes, and perform a Whittle’s indexability analysis. Whittle’s indexability is traditionally known to be hard to establish and the index policy derived based on Whittle’s indexability is known to have optimality properties in various settings. We show that the problem of downlink scheduling under imperfect channel state information is Whittle indexable and derive the Whittle’s index policy in closed form. Through extensive numerical experiments, we show that the Whittle’s index policy has near-optimal performance and is robust against various imperfections in channel state feedback. Our work reveals that, under incomplete channel state information, exploiting channel memory for opportunistic scheduling can result in significant system-level performance gains and that almost all of these gains can be realized using the polynomial-complexity Whittle’s index policy. [ABSTRACT FROM AUTHOR]

This paper considers point-to-point secure communication over flat fading channels under an outage constraint. More specifically, we extend the definition of outage capacity to account for the secrecy constraint and obtain sharp characterizations of the corresponding fundamental limits under two different assumptions on the transmitter channel state information (CSI). First, we find the outage secrecy capacity assuming that the transmitter has perfect knowledge of the legitimate and eavesdropper channel gains. In this scenario, the capacity achieving scheme relies on opportunistically exchanging private keys between the legitimate nodes. These keys are stored in a key buffer and later used to secure delay sensitive data using the Vernam's one time pad technique. We then extend our results to the more practical scenario where the transmitter is assumed to know only the legitimate channel gain. Here, our achievability arguments rely on privacy amplification techniques to generate secret key bits. In the two cases, we also characterize the optimal power control policies which, interestingly, turn out to be a judicious combination of channel inversion and the optimal ergodic strategy. Finally, we analyze the effect of key buffer overflow on the overall outage probability. [ABSTRACT FROM AUTHOR]

This paper introduces the vector sparse matrix transform (vector SMT), a new decorrelating transform suitable for performing distributed processing of high-dimensional signals in sensor networks. We assume that each sensor in the network encodes its measurements into vector outputs instead of scalar ones. The proposed transform decorrelates a sequence of pairs of vector outputs, until these vectors are decorrelated. In our experiments, we simulate distributed anomaly detection by a network of cameras, monitoring a spatial region. Each camera records an image of the monitored environment from its particular viewpoint and outputs a vector encoding the image. Our results, with both artificial and real data, show that the proposed vector SMT transform effectively decorrelates image measurements from the multiple cameras in the network while maintaining low overall communication energy consumption. Since it enables joint processing of the multiple vector outputs, our method provides significant improvements to anomaly detection accuracy when compared with the baseline case when the images are processed independently.