Search

For the emerging Internet of Things (IoT), one of the most critical problems is the real-time reconstruction of signals from a set of aged measurements. During the reconstruction, distortion occurs between the observed signal and the reconstructed signal due to sampling and queuing delay. We focus on minimizing the average distortion defined as the 1- $norm$ of the difference of the two signals under the scenario that a Poisson counting process is reconstructed in real-time on a remote monitor. We consider the reconstruction under three special sampling policies. For each of the policy, we derive the closed-form expression of the average distortion by dividing the overall distortion area into polygons and analyzing their structures. It turns out that the polygons are built up by sub-polygons that account for distortions caused by sampling and queuing delay. The closed-form expressions of the average distortion help us find the optimal sampling parameters that achieve the minimum distortion. In addition, we propose an interpolation algorithm to further decrease the average distortion and give its lower-bound on distortion for one of the three sampling policies. Simulation results are provided to validate our conclusion.

We study the age of information , which is a measure of the freshness of a continually updated piece of information as observed at a remote monitor. The age of information metric has been studied for a variety of different queueing systems, and in this paper, we introduce a packet deadline as a control mechanism to study its impact on the average age of information for an M/M/1/2 queueing system. We analyze the system for the cases of a fixed deadline and a random exponential deadline and derive closed-form expressions for the average age. We also derive a closed-form expression for the optimal average deadline for the random exponential case. Our numerical results show the relationship of the age performance to that of the M/M/1/1 and M/M/1/2 systems, and we demonstrate that using a deadline can outperform both the M/M/1/1 and M/M/1/2 without deadline.

This paper focuses on status age, which is a metric for measuring the freshness of a continually updated piece of information (i.e., status) as observed at a remote monitor. In paper, we study a system in which a sensor sends random status updates over a dynamic network to a monitor. For this system, we consider the impact of having messages take different routes through the network on the status age. First, we consider a network with plentiful resources (i.e., many nodes that can provide numerous alternate paths), so that packets need not wait in queues at each node in a multihop path. This system is modeled as a single queue with an infinite number of servers, specifically as an $M/M/\infty $ queue. Packets routed over a dynamic network may arrive at the monitor out of order, which we account for in our analysis for the $M/M/\infty $ model. We then consider a network with somewhat limited resources, so that packets can arrive out of order but also must wait in a queue. This is modeled as a single queue with two servers, specifically an $M/M/2$ queue. We present the exact approach to computing the analytical status age, and we provide an approximation that is shown to be close to the simulated age. We also compare both models with $M/M/1$ , which corresponds to severely limited network resources, and we demonstrate the tradeoff between the status age and the unnecessary network resource consumption.

This paper characterizes the performance of interference alignment (IA) technique taking into account the dynamic traffic pattern and the probing/feedback cost. We consider a time-division duplex (TDD) system where transmitters acquire their channel state information (CSI) by decoding the pilot sequences sent by the receivers. Since global CSI knowledge is required for IA, the transmitters have also to exchange their estimated CSIs over a backhaul of limited capacity (i.e. imperfect case). Under this setting, we characterize in this paper the stability region of the system under both the imperfect and perfect (i.e. unlimited backhaul) cases, then we examine the gap between these two resulting regions. Further, under each case, we provide a centralized probing algorithm (policy) that achieves the max stability region. These stability regions and scheduling policies are given for the symmetric system where all the path loss coefficients are equal to each other, as well as for the general system. For the symmetric system, we compare the stability region of IA with the one achieved by a time division multiple access (TDMA) system where each transmitter applies a simple singular value decomposition technique (SVD). We then propose a scheduling policy that consists in switching between these two techniques, leading the system, under some conditions, to achieve a bigger stability region. Under the general system, the adopted scheduling policy is of a high computational complexity for moderate number of pairs, consequently we propose an approximate policy that has a reduced complexity but that achieves only a fraction of the system stability region. A characterization of this fraction is provided., 66 pages, 13 figures, 1 table, submitted to IEEE Transactions on Information Theory

We consider a set of transmitter-receiver pairs, or links, that share a wireless medium and address the problem of emptying backlogged queues with given initial size at the transmitters in minimum time. The problem amounts to determining activation subsets of links, and their time durations, to form a minimum-time schedule. Scheduling in wireless networks has been studied under various formulations before. In this paper, we present fundamental insights and solution characterizations that include: 1) showing that the complexity of the problem remains high for any continuous and increasing rate function; 2) formulating and proving sufficient and necessary optimality conditions of two baseline scheduling strategies that correspond to emptying the queues using one-at-a-time or all-at-once strategies; and 3) presenting and proving the tractability of the special case in which the transmission rates are functions only of the cardinality of the link activation sets. These results are independent of physical-layer system specifications and are valid for any form of rate function. We then develop an algorithmic framework for the solution to this problem. The framework encompasses exact as well as sub-optimal, but fast, scheduling algorithms, all under a unified principle design. Through computational experiments, we finally investigate the performance of several specific algorithms from this framework.

We consider a source node broadcasting to two receivers over a general erasure channel with receiver feedback. We characterize the capacity region of the channel and construct algorithms based on linear network coding (either randomized or depending on channel dynamics) that achieve this capacity. We then consider stochastic arrivals at the source for the two destinations and characterize the stable throughput region achieved by adapting the same algorithms that achieve capacity. Next, we modify these algorithms to improve their delay performance and characterize their stable throughput regions. Although the capacity and stability regions obtained by the algorithms are not always identical (because of the extra overhead needed for the algorithms to handle stochastic traffic), they are within a few bits of each other and have similar forms. This example exhibits an unusual relationship between capacity and stability regions and extends similar prior studies for multiple access channels.

We investigate the impact of a protocol-level cooperation idea in a wireless multiple-access system. By dynamically and opportunistically exploiting spatial diversity among the $N$ source users, a packet is delivered to the common destination through either a direct link or through cooperative relaying by intermediate source nodes that have a statistically better channel to the destination. The traffic burstiness at the source is taken into account, and the performance metrics of the stable throughput region and delay are evaluated for the case of packet-erasure channels. We consider conflict-free, work-conserving transmission policies as well as plain time-division multiple-access policy. We establish that the stable throughput regions under both classes of cooperative policies are the same, which strictly contain the stable throughput regions achieved without cooperation. Moreover, the optimal policy for minimizing the average delay among the class of all cooperative work-conserving policies is determined. Then, in the case of two users, the closed-form delay expressions are explicitly derived as well. Our results indicate that cooperation can significantly reduce delay for both users.

This paper applies Information Theoretic analysis to packet-based random multiple access communication systems. A new channel coding approach is proposed for coding within each data packet with built-in support for bursty traffic properties, such as message underflow, and for random access properties, such as packet collision detection. The coding approach does not require joint communication rate determination either among the transmitters or between the transmitters and the receiver. Its performance limitation is characterized by an achievable region defined in terms of communication rates, such that reliable packet recovery is supported for all rates inside the region and reliable collision detection is supported for all rates outside the region. For random access communication over a discrete-time memoryless channel, it is shown that the achievable rate region of the introduced coding approach equals the Shannon information rate region without a convex hull operation. Further connections between the achievable rate region and the Shannon information rate region are developed and explained., submitted to IEEE Transactions on Information Theory

We analyze the queueing delay performance when random linear coding is performed over packets randomly arriving at a source node for multicast transmission over packet erasure channels. We model random coding of packets as a bulk-service queueing system, where packets are served and depart the queue in groups. In this framework, we analyze two different block-based random linear coding schemes. The first scheme involves coding over a fixed blocksize, which leads to simpler analysis but also to a delay penalty for lightly-loaded systems. The second scheme adapts to the traffic load by allowing for a variable blocksize, thereby removing the delay penalty at low loads. We provide results on the maximum stable arrival rate of packets at the source and on the queueing delay as a function of the arrival rate.

In this paper, we investigate some cross-layer cooperative strategies for cognitive Time-Division Multiple-Access relay channels with bursty arrivals. The proposed schemes adopt an advanced physical (PHY) layer cooperation and an “intelligent” cognitive network-layer cooperation in order to improve the stable throughput region of the system. In contrast to previously reported work, where relaying is only enabled on periods of source silence, here, we incorporate a Dynamic Decode-and-Forward (DDF) policy which allows relaying assistance also during the source transmission. The enhancement of cognitive relaying with DDF provides more cooperative opportunities which results in faster emptying of the user queues and higher stable throughput compared to the conventional approaches. In addition to this PHY-layer relaying, the cognitive cooperation is supported by an adaptive/non-adaptive superposition scheme which allows the relay node to simultaneously forward packets from different users. We demonstrate that superposition can further increase the transmission opportunities and significantly improve the stable throughput region. The proposed schemes are studied from a networking perspective and their advantages are shown through both theoretical results and computer simulations.

This paper compares scheduling and coding strategies for a multicast version of a classic downlink problem. We consider scheduling strategies where, in each time slot, a scheduler observes the lengths of all queues and the connectivities of all links and can transmit the head-of-the-line packet from a single queue. We juxtapose this to a coding strategy that is simply a form of classical random linear coding. We show that there are configurations for which the stable throughput region of the scheduling strategy is a strict subset of the corresponding throughput region of the coding strategy. This analysis is performed for both time-invariant and time-varying channels. The analysis is also performed both with and without accounting for the impact on throughput of including coding overhead symbols in each encoded packet. Additionally, we compare coding strategies that only code within individual queues against a coding strategy that codes across separate queues. The strategy that codes across queues simply sends packets from all queues to all receivers. As a result, this strategy sends many packets to unnecessary recipients. We show, surprisingly, that there are cases where the strategy that codes across queues can achieve the same throughput region achievable by coding within individual queues.

This paper studies the Gaussian multiaccess channel with multiantenna basestation in the low signal to noise ratio (SNR) regime. We compare the spectral efficiencies of the optimal superposition channel sharing scheme and two simple alternatives: the time division multiaccess (TDMA) scheme and superposition multiaccess with single-user decoding (SSD). Due to the fact that SSD, but not TDMA, exploits the multiuser multiplexing gain, the relative spectral efficiency of SSD over TDMA grows drastically as the number of antennas at the basestation increases. The results suggest that, in the low SNR regime with multiple antenna basestation, TDMA's suboptimality can no longer be offset by its simplicity since SSD can achieve much higher spectral efficiency while the simplicities of the two channel sharing schemes are similar.

The problem of joint scheduling and rate control for multicast traffic in wireless networks is considered under the performance objectives of sum throughput maximization and proportional fairness. Our results are also valid for the special cases of unicast and broadcast traffic. First, the problem of maximizing the sum throughput of the network is studied and an optimal scheduling and rate control policy is obtained. Given the combinatorial complexity of providing an optimal policy, a simple, polynomial-time, suboptimal alternative scheme is introduced that restricts the space of scheduling and rate control decisions to operation one at a time or all together. The optimal policy to the problem of maximizing the sum throughput of the network with respect to this restricted action space is found. Next, the objective of proportional fairness is considered. Under this restricted space of actions, the resulting scheduling and rate control policy is explicitly characterized analytically and the effects of the current channel conditions are incorporated into the scheduling decisions. Furthermore, it is shown that the policy under this restricted action space is of threshold type. Finally, our analytical results are verified through a set of numerical experiments.

We study cellular-like wireless networks in which the cells may overlap substantially, and a common channel is used for all cells. Thus, transmissions intended for one destination (or base station) can cause interference at neighboring destinations. We assume the use of a ?collision-channel? model, in which arbitrary communication and interference regions are associated with each destination. The interaction between such cells is best exemplified if the protocol of access in each cell is pure random access, i.e., Slotted Aloha. We derive a mathematical formula for the maximum achievable throughput for multiple-cell networks that satisfy a ?balance? condition, which is related to (but not as stringent as) symmetry. This formula implies that the throughput achieved in a cell is affected only by the degree of overlap with adjacent cells, i.e., a cell's throughput is not affected by transmissions that are outside of its interference region. Moreover, we show that, at the point of maximum throughput, the expected channel traffic is one packet per slot in each cell, an extension of the result obtained many years ago for single-destination networks.

The transmission of packets is considered from one source to multiple receivers over single-hop erasure channels. The objective is to evaluate the stability properties of different transmission schemes with and without network coding. First, the throughput limitation of retransmission schemes is discussed and the stability benefits are shown for randomly coded transmissions, which, however, need not optimize the stable throughput for finite coding field size and finite packet block size. Next, a dynamic scheme is introduced for distributing packets among virtual queues depending on the channel feedback and performing linear network coding based on the instantaneous queue contents. The difference of the maximum stable throughput from the min-cut rate is bounded as function of the order of erasure probabilities depending on the complexity allowed for network coding and queue management. This queue-based network coding scheme can asymptotically optimize the stable throughput to the max-flow min-cut bound, as the erasure probabilities go to zero. This is realized for a finite coding field size without accumulating packet blocks at the source to start network coding. The comparison of random and queue-based dynamic network coding with plain retransmissions opens up new questions regarding the tradeoffs of stable throughput, packet delay, overhead, and complexity.

In wireless networks, throughput optimization is an essential performance objective that cannot be adequately characterized by a single criterion (such as the minimum transmitted or sum-delivered throughput) and should be specified over all source-destination pairs as a rate region. For a simple and yet fundamental model of tandem networks, a cross-layer optimization framework is formulated to derive the maximum throughput region for saturated multicast traffic. The contents of network flows are specified through network coding (or plain routing) in network layer and the throughput rates are jointly optimized in medium access control layer over fixed set of conflict-free transmission schedules (or optimized over transmission probabilities in random access). If the network model incorporates bursty sources and allows packet queues to empty, the objective is to specify the stability region as the set of maximum throughput rates that can be sustained with finite packet delay. Dynamic queue management strategies are used to expand the stability region toward the maximum throughput region. Network coding improves throughput rates over plain routing and achieves the largest gains for broadcast communication and intermediate network sizes. Throughput optimization imposes fundamental tradeoffs with transmission and processing energy costs such that the throughput-optimal operation is not necessarily energy efficient.

This paper addresses network coding in wireless networks in conjunction with medium access control (MAC). It is known that coding over wired networks enables connections with rates that cannot be achieved by routing. However, the properties of wireless networks (e.g., omnidirectional transmissions, destructive interference, single transceiver per node, finite energy) modify the formulation of time-varying network coding in a way that reflects strong interactions with underlying MAC protocols and deviates from the classical approach used in wired network coding. To perform network coding over conflict-free transmission schedules, predetermined network realizations are separately activated by a time-division mechanism and the content of network flows is derived through network coding to optimize performance measures such as achievable throughput and energy costs. A systematic method is presented to construct linear wireless network codes and interactions with MAC schedules are discussed under wireless assumptions. Network coding is also extended to operate with arbitrary (random or scheduled access based) MAC protocols. Alternatively, conflict-free transmission schedules are jointly constructed with network codes by decomposing wireless networks into subtrees and employing graph coloring on simplified subtree graphs. Finally, network coding and plain routing are compared in terms of throughput, energy and delay performance under different MAC solutions.

In this paper, a novel cognitive multiple-access strategy in the presence of a cooperating relay is proposed. Exploiting an important phenomenon in wireless networks, source burstiness, the cognitive relay utilizes the periods of silence of the terminals to enable cooperation. Therefore, no extra channel resources are allocated for cooperation and the system encounters no bandwidth losses. Two protocols are developed to implement the proposed multiple-access strategy. The maximum stable throughput region and the delay performance of the proposed protocols are characterized. The results reveal that the proposed protocols provide significant performance gains over conventional relaying strategies such as selection and incremental relaying, specially at high spectral efficiency regimes. The rationale is that the lossless bandwidth property of the proposed protocols results in a graceful degradation in the maximum stable throughput with increasing the required rate of communication. On the other hand, conventional relaying strategies suffer from catastrophic performance degradation because of their inherent bandwidth inefficiency that results from allocating specific channel resources for cooperation at the relay. The analysis reveals that the throughput region of the proposed strategy is a subset of its maximum stable throughput region, which is different from random access, where both regions are conjectured to be identical.

The problem of determining a minimal length schedule to satisfy given link demands in a wireless network is considered. Links are allowed to be simultaneously active if no node can simultaneously transmit and receive, no node can transmit to or receive from more than one node at a time, and a given signal-to-interference and noise ratio (SINR) is exceeded at each receiver when transmitters use optimally chosen transmit powers. We show that a) the general problem is at least as hard as the MAX-SIR-MATCHING problem, which is easier to describe and b) when the demands have a superincreasing property the problem is tractable

This paper studies finite-terminal random multiple access over the standard multipacket reception (MPR) channel. We characterize the relations among the throughput region of random multiple access, the capacity region of multiple access without code synchronization, and the stability region of ALOHA protocol. In the first part of the paper, we show that if the MPR channel is standard, the throughput region of random multiple access is coordinate convex. We then study the information capacity region of multiple access without code synchronization and feedback. Inner and outer bounds to the capacity region are derived. We show that both the inner and the outer bounds converge asymptotically to the throughput region. In the second part of the paper, we study the stability region of finite-terminal ALOHA multiple access. For a class of packet arrival distributions, we demonstrate that the stationary distribution of the queues possesses positive and strong positive correlation properties, which consequently yield an outer bound to the stability region. We also show the major challenge in obtaining the closure of the stability region is due to the lack of sensitivity analysis results with respect to the transmission probabilities. Particularly, if a conjectured "sensitivity monotonicity" property held for the stationary distribution of the queues, then equivalence between the closure of the stability region and the throughput region follows as a direct consequence, irrespective of the packet arrival distributions.