In this paper, we investigate a model relevant to semantics-aware goal-oriented communications, and propose a new metric that incorporates the utilization of information in addition to its timelines. We consider the transmission of observations from an external process to a battery-powered receiver through status updates. These updates inform the receiver about the process status and enable actuation if sufficient energy is available. We focus on a wireless power transfer (WPT) model, where the receiver receives energy from a dedicated power transmitter.We analyze the Age of Information (AoI) and propose a new metric, theAge of Actuation (AoA), which is relevant when the receiver utilizes the status updates to perform actions in a timely manner. We provide analytical characterizations of the average AoA and the violation probability of the AoA, demonstrating that AoA generalizes AoI. Moreover, we introduce and analytically characterize the Probability ofMissing Actuation (PoMA); this metric becomes relevant also toquantify the incurred cost of a missed action. We formulate unconstrained and constrained optimization problems for all the metrics and present numerical evaluations of our analytical results. This proposed set of metrics goes beyond the traditional timeliness metrics since the synergy of different flows is now considered.

We study the problem of optimizing the decisions of a preemptively capable transmitter to minimize the Age of Incorrect Information (AoII) when the communication channel has a random delay. We consider a slotted-time system where a transmitter observes a Markovian source and makes decisions based on the system status. In each time slot, the transmitter decides whether to preempt or skip when the channel is busy. When the channel is idle, the transmitter decides whether to send a new update. A remote receiver estimates the state of the Markovian source based on the update it receives. We consider a generic transmission delay and assume that the transmission delay is independent and identically distributed for each update. This paper aims to optimize the transmitter’s decision in each time slot to minimize the AoII with generic time penalty functions. To this end, we first use the Markov decision process to formulate the optimization problem and derive the analytical expressions of the expected AoIIs achieved by two canonical preemptive policies. Then, we prove the existence of the optimal policy and provide a feasible value iteration algorithm to approximate the optimal policy. However, the value iteration algorithm will be computationally expensive if we want considerable confidence in the approximation. Therefore, we analyze the system characteristics under two canonical delay distributions and theoretically obtain the corresponding optimal policies using the policy improvement theorem. Finally, numerical results are presented to illustrate the performance improvements brought about by the preemption capability.

We study the real-time remote tracking of a two-state Markov process powered by an energy harvesting source. The source dynamically decides whether to transmit over an unreliable channel based on the state of the system. This problem is formulated as a Markov decision process (MDP) to determine the optimal transmission policy that minimizes the average Version Innovation Age (VIA) as a key performance metric. We demonstrate that the optimal transmission policy is threshold-based, determined by the battery level, source state, and VIA value. We numerically validate the analytical structure of the optimal policy and compare its performance against two baseline policies under various system parameters, establishing the superior performance of our approach.

We consider the problem of real-time remote monitoring of a two-state Markov process, where a sensor observes the source state and decides whether to transmit updates over an unreliable channel. We introduce a change-aware randomized stationary policy, in which the source is sampled probabilistically whenever its state changes, and a semantics-aware randomized stationary policy, in which sampling is performed probabilistically based on the current source state and whether the system was in sync in the previous time slot. We then propose two new performance metrics:the Version Innovation Age (VIA), which measures significant changes in content between versions, andthe Age of Incorrect Version (AoIV), which quantifies the outdated versions at the receiver compared to the source when the system is in an incorrect state. We analyze their performance under the proposed and other state-of-the-art sampling policies. Specifically, we derive closed-form expressions for the distributions and averages of VIA, AoIV, and the Age of Incorrect Information (AoII), and formulate three constrained optimization problems to minimize them while accounting for constraints on the time-averaged sampling cost and the reconstruction error. Finally, we compare various sampling and transmission policies and identify the conditions under which each policy performs best.

The Age of Incorrect Information (AoII) is a recently proposed metric for real-time remote monitoring systems. In particular, AoII measures the time the information at the monitor is incorrect, weighted by the magnitude of this incorrectness, thereby combining the notions of freshness and distortion. This paper addresses the definition of an AoII-optimal transmission policy in a discrete-time communication scheme with a resource constraint and a hybrid automatic repeat request (HARQ) protocol. Considering an N-ary symmetric Markov source, the problem is formulated as an infinite-horizon average-cost constrained Markov decision process (CMDP). Interestingly, it is proved that, under some conditions, the optimal transmission policy is to never transmit. This reveals a region of the source dynamics where communication is inadequate in reducing the AoII. Elsewhere, there exists an optimal transmission policy, which is a randomized mixture of two discrete threshold-based policies that randomize on at most one state. The optimal threshold and the randomization component are derived analytically. Numerical results illustrate the impact of the source dynamics, channel conditions, and resource constraints on the average AoII.

In this paper, we extend the metric of Age of Actuation (AoA), and we propose the Age of Actuated Information (AoAI) within a discrete-time system that integrates data caching and energy harvesting (EH). AoA evaluates the timeliness of actions irrespective of the age of the information, while AoAI considers the freshness of the utilized data packet. We analytically characterize the performance of AoA and AoAI for the system at hand. Our findings show that while AoAI consistently decreases with increased data and energy packet arrival rates, AoA shows a counter-intuitive behavior, with a potential increase under limited data or energy availability. These metrics go towards the semantics of information and goal-oriented communications since they consider the timeliness of the utilized information to perform an action.

The Age of Incorrect Information (AoII) is studied within the context of remote monitoring a Markov source using variable-length stop-feedback (VLSF) coding. Leveraging recent results on the non-asymptotic channel coding rate, we consider sources with small cardinality, where feedback is non-instantaneous as the transmitted information and feedback message have comparable lengths. We focus on the feedback sequence, i.e. the times of feedback transmissions, and derive AoII-optimal and delay-optimal feedback sequences. Our results showcase the impact of the feedback sequence on the AoII, revealing that a lower average delay does not necessarily correspond to a lower average AoII. We discuss the implications of our findings and suggest directions for coding scheme design.

We examine a simplified distributed collaborative beamforming (DCB) system with two transmitters sending data over independent channels with significant time-varying phase distortion. The transmitters sample the state of their respective channels using a periodic sounding waveform sent by the receiver and use the last sensed state along with the sample age to correct for the channel phase distortion. As the age of the last sampled channel state increases, the transmitters are correctly estimating the current state with decreasing likelihood, leading to reduced beamforming gain. However, because sensing and transmitting must occur on the same channel, the transmitters cannot both send data and sample the channel at the same time. As a result, the cost associated with channel sensing is the transmitters not sending data for some duration; this compromise is embodied by the frame-averaged expected beamforming gain. Expressions for instantaneous and averaged expected gain are developed, and an example is presented to demonstrate finding the optimal sensing period and how the optimal sensing period can change depending on the last sensed states of the channels.

Control over networks is envisioned to be one of the driving applications of future mobile networks. Networked control systems contain sensors and controllers exchanging time-sensitive information to fulfill a particular control goal. In this work, we consider$N$heterogeneous feedback control loops closed over a wireless star network. A centralized scheduler located at the central node, i.e., base station (BS), determines the transmission schedule of sensor-to-BS and BS-to-controller communication links. We assume that each link can accommodate a single transmission at a time and is prone to data losses with time-varying probability. Moreover, each controller estimates the system state remotely based on available information. In such a setting, we formulate an optimization problem to minimize the network-induced estimation error at the controller. In particular, we determine the optimal transmission schedule on each link that leads to the minimum normalized mean squared error (nMSE) in a given finite horizon (FH). We compare the performance of our proposed FH scheduler to various schedulers from the existing literature. Our simulation results show that by solving the finite horizon problem optimally, we are able to reduce the nMSE by$10\%$when compared to the best performing scheduling policy among the selected policies from the state-of-the-art. Moreover, the linear-quadratic Gaussian (LQG) cost is reduced by more than$13\%$indicating a control performance improvement in the network.

We consider a transmitter-receiver pair in a slotted-time system. The transmitter observes a dynamic source and sends updates to a remote receiver through an error-free communication channel that suffers a random delay. We consider two cases. In the first case, the update is guaranteed to be delivered within a certain number of time slots. In the second case, the update is immediately discarded once the transmission time exceeds a predetermined value. The receiver estimates the state of the dynamic source using the received updates. In this paper, we adopt the Age of Incorrect Information (AoII) as the performance metric and investigate the problem of optimizing the transmitter’s action in each time slot to minimize AoII. We first characterize the optimization problem using the Markov decision process and investigate the performance of the threshold policy, under which the transmitter transmits updates only when the transmission is allowed and the AoII exceeds the threshold$\tau $. By delving into the characteristics of the system evolution, we precisely compute the expected AoII achieved by the threshold policy using the Markov chain. Then, we prove that the optimal policy exists. Furthermore, by leveraging the policy improvement theorem, we theoretically prove that, under an easily verifiable condition, the optimal policy is the threshold policy with$\tau =1$. Finally, numerical results are presented to highlight the performance of the optimal policy.

In this work, we consider mixed traffic with time-sensitive users; a deadline-constrained user, and an AoI-oriented user. To develop an efficient scheduling policy, we cast a novel optimization problem formulation for minimizing the average AoI while satisfying the timely throughput constraints. The optimization problem is a Constrained Markov Decision Process (CMDP). We relax the constrained problem to an unconstrained Markov Decision Process (MDP) problem by utilizing Lyapunov optimization theory. The unconstrained problem is solved for each frame by applying backward dynamic programming. Simulation results show that the timely throughput constraints are satisfied while minimizing the average AoI. Also, simulation results show the convergence of the algorithm for different values of the weighted factor and the trade-off between the AoI and the timely throughput.

We consider a time slotted communication network with a base station (BS) and a user. At each time slot a fresh update packet arrives at the BS with probability$p > 0$. When the BS transmits an update packet for the first time, it goes through with a success probability of$q_1$. In all subsequent re-transmissions, the packet goes through with a success probability of$q_{2}$where$q_{2} > q_1$, due to the accumulation of observations at the receiver used to decode the packet. When the packet goes through the first time, the age of the user drops to 1, while when the packet goes through in subsequent transmissions, the age of the user drops to the age of the packet since its generation. Thus, when the BS is in the process of re-transmitting an old packet, if it receives a new packet, it has to decide whether to re-transmit the old packet with higher probability of successful transmission but resulting in higher age, or to transmit the new packet which will result in a lower age upon successful reception but this will happen with lower probability. In this paper, we provide an optimal algorithm to solve this problem.

In 5G and beyond communication systems, the notion of latency gets great momentum in wireless connectivity as a metric for serving real-time communications requirements. However, in many applications, research has pointed out that latency could be inefficient to handle applications with data freshness requirements. Recently, Age of Information (AoI) metric, which can capture the freshness of the data, has attracted a lot of attention. In this work, we consider mixed traffic with time-sensitive users; a deadline-constrained user, and an AoI-oriented user. To develop an efficient scheduling policy, we cast a novel optimization problem formulation for minimizing the average AoI while satisfying the timely throughput constraints. The formulated problem is cast as a Constrained Markov Decision Process (CMDP). We relax the constrained problem to an unconstrained Markov Decision Process (MDP) problem by utilizing the Lyapunov optimization theory and it can be proved that it is solved per frame by applying backward dynamic programming algorithms with optimality guarantees. In addition, we provide a low-complexity algorithm guaranteeing that the timely-throughput constraint is satisfied. Simulation results show that the timely throughput constraints are satisfied while minimizing the average AoI. Simulation results show the convergence of the algorithms for different values of the weighted factor and the trade-off between the AoI and the timely throughput.

Extremely low-latency communication has attracted considerable recent attention because it holds the promise of supporting emerging real-time applications such as autonomous driving, smart grids, and Industrial Internet of Things (IIoT). Owing to the limited bandwidth in wireless environments, the sub-packets or even bits have to be transmitted successively, thereby inducing non-negligible delay-induced cost for real-time remote monitoring, estimation, decision making, and control. In this paper, we present a unified incremental decoding framework for real-time applications, the costs of which are extremely sensitive to the latency of each individual sub-packet or bit. In contrast to conventional methods, in which a decision is made after fully decoding the entire packet, the incremental decoding strategy allows monitors or actors to make their decisions in real time based on partially received packet. By this means, there is no need to wait for the whole packet to be decoded, thereby reducing the delay-induced costs substantially. To minimize cumulative cost during the real-time monitoring and control, we design source coding and decision making algorithms jointly, in which a backward induction property is found. Furthermore, we conceive a dynamic programming algorithm for a given source codebook to significantly reduce the cumulative decision costs while maintaining low computational complexity.

In this paper, we introduce the Age of Incorrect Information (AoII) as an enabler for semantics-empowered communication, a newly advocated communication paradigm centered around data’s role and its usefulness to the communication’s goal. First, we shed light on how the traditional communication paradigm, with its role-blind approach to data, is vulnerable to performance bottlenecks. Next, we highlight the shortcomings of several proposed performance measures destined to deal with the traditional communication paradigm’s limitations, namely the Age of Information (AoI) and the error-based metrics. We also show how the AoII addresses these shortcomings and captures more meaningfully the purpose of data. Afterward, we consider the problem of minimizing the average AoII in a transmitter-receiver pair scenario. We prove that the optimal transmission strategy is a randomized threshold policy, and we propose an algorithm that finds the optimal parameters. Furthermore, we provide a theoretical comparison between the AoII framework and the standard error-based metrics counterpart. Interestingly, we show that the AoII-optimal policy is also error-optimal for the adopted information source model. Concurrently, the converse is not necessarily true. Finally, we implement our policy in various applications, and we showcase its performance advantages compared to both the error-optimal and the AoI-optimal policies.

In this paper, we introduce the Age of Incorrect Information (AoII) as an enabler for semantics-empowered communication, a newly advocated communication paradigm centered around data’s role and its usefulness to the communication’s goal. First, we shed light on how the traditional communication paradigm, with its role-blind approach to data, is vulnerable to performance bottlenecks. Next, we consider the problem of minimizing the average AoII in a transmitter-receiver pair scenario. We prove that the optimal transmission strategy is a randomized threshold policy, and we propose an algorithm that finds the optimal parameters. Finally, we implement our policy in a real-life application, and we showcase its performance advantages compared to both the error-optimal and the AoI-optimal policies.

In the emerging Industrial Internet of Things (IIoT), real-time control is expected to play a key role. How to minimize the cost to be paid due to the transmission delay of digital signaling in real-time control system becomes a challenging problem. In this paper, we study incremental decoding based low latency communication for a real-time control system. The real-time control action will be updated, whenever a new bit is received instead of the entire codeword. In other words, when the controller obtains partial information of the digital signaling, it executes the control action immediately instead of waiting until the complete information is obtained, which is in contrast to the conventional real-time control. Our aim is to minimize the expected cumulative control cost over the control process by joint design of source coding and its corresponding real-time control scheme. To this end, we first show a recursive structure that reveals the relationship of minimal expected cumulative control cost among two adjacent decision epochs. Based on such structure, the optimal solution can be obtained by a recursive algorithm presented by us. Finally, our numerical results also demonstrate that the cumulative control cost over the control process can be significantly reduced by implementing the source codebook we proposed, compared with traditional source coding.

In this paper, we provide an analysis of a status update system modeled through the Stochastic Hybrid Systems (SHSs) tool. Contrary to previous works, which assumed constant transition rates, we allow the system’s transition dynamics to be functions of the Age of Information (AoI). This dependence allows us to encapsulate many applications and opens the door for more sophisticated systems to be studied. However, this same dependence on the AoI engenders technical and analytical difficulties. Our paper provides a first step in addressing these difficulties. Specifically, we first showcase the regularity and other critical characteristics of the age process in our system of interest. Then, we provide a framework to establish the Lagrange stability and positive recurrence of the process. Building on these results, we provide an approach, dubbed as the moment closure technique, to compute the m-th moment of the age process for any m≥1. Interestingly, this technique allows us to approximate the average age of various systems by solving a simple set of linear equations.

This work studies the role of Age of Information (AoI) in the network state updating process for wireless software defined networks (SDN). The SDN routers must routinely update their knowledge of the network state, which is used as a basis for making routing and scheduling decisions. However, the network updates require communication resources, so there is a tradeoff between the frequency of updates and maximum network throughput. We assume the network state is Markovian and no new observations are received in between updates, so the AoI of the network state information impacts the ability of the network to optimize its performance. We formulate the problem as a finite-horizon Partially Observable Markov Decision Process (POMDP) for each period. For a symmetric fading model of the network, we derive the limiting performance and an upper bound. To generate policies for a range of fixed time horizons, we use Monte Carlo planning-based POMDP solvers. Simulation of these policies show that there is a finite optimal update period that maximizes network throughput. In addition, we study non-uniform update intervals, which can yield even higher throughput if the interval is chosen based on the state observed. We conclude that AoI itself is not sufficient to characterize performance, but what matters is the AoI for the specific network state information.

In this paper, we consider a scheduling problem, in which several streams of status update packets with different priority levels are sent through a shared channel to their destinations. We introduce a notion oflexicographic age optimality, or simplylex-age-optimality, to evaluate the performance of multi-class status update policies. In particular, a lex-age-optimal scheduling policy first minimizes the Age of Information (AoI) metrics for high-priority streams, and then, within the set of optimal policies for high-priority streams, achieves the minimum AoI metrics for low-priority streams. We propose a new scheduling policy named Preemptive Priority, Maximum Age First, Last-Generated, First-Served (PP-MAF-LGFS), and prove that the PP-MAF-LGFS scheduling policy is lex-age-optimal. This result holds (i) for minimizing any time-dependent, symmetric, and non-decreasing age penalty function; (ii) for minimizing any non-decreasing functional of the stochastic process formed by the age penalty function; and (iii) for the cases where different priority classes have distinct arrival traffic patterns, age penalty functions, and age penalty functionals. For example, the PP-MAF-LGFS scheduling policy is lex-age-optimal for minimizing the probability of age violation of a high-priority stream and the time-average age of a low-priority stream. Numerical results are provided to illustrate our theoretical findings.

Age of Incorrect Information (AoII) is a newly introduced performance metric that considers communication goals. Therefore, comparing with traditional performance metrics and the recently introduced metric - Age of Information (AoI), AoII achieves better performance in many real-life applications. However, the fundamental nature of AoII has been elusive so far. In this paper, we consider the AoII in a system where a transmitter sends updates about a multi-state Markovian source to a remote receiver through an unreliable channel. The communication goal is to minimize AoII subject to a power constraint. We cast the problem into a Constrained Markov Decision Process (CMDP) and prove that the optimal policy is a mixture of two deterministic threshold policies. Afterward, by leveraging the notion of Relative Value Iteration (RVI) and the structural properties of threshold policy, we propose an efficient algorithm to find the threshold policies as well as the mixing coefficient. Lastly, numerical results are laid out to highlight the performance of AoII-optimal policy.

Real-time monitoring and remote control of stochastic systems have attracted considerable attention due to their potential in task-oriented communications and industrial Internet of Things (IIoT). How to achieve ultra high-freshness in real-time monitoring and remote control becomes a challenging problem. In this paper, we are interested in the freshness oriented source coding with incremental decoding. This is contrast to con-ventional source encoding/decoding, in which a random sample is estimated after its entire codeword is received. Incremental decoding, however, allows the real-time estimation of a random sample once a new bit or channel coding block is decoded in the physical layer. Its source codebook is then optimized, based on which we further conceive a real-time decision policy. Our policies minimize the average mean square error (MSE) or decision cost by judiciously designed codebook for source encoding. Numerical results show that the incremental decoding substantially reduces the MSE and decision cost in real-time monitoring.

Age of information is often studied as a primary objective to be optimized, but for problems where age is not the primary objective, it can still have a major role that can be utilized. This work studies a two-user, single-channel cognitive radio network, where the primary user’s transmit/idle dynamics are modeled as a binary Markov chain, and the secondary user decides to either sense or transmit. Under this setup, the age of the information sensed by the secondary user has a direct impact on its performance. The secondary user aims to maximize its throughput subject to a constraint on the probability of collision experienced by the primary. Using the Markov chain model of the primary user, the secondary user decides on its transmission and sensing strategy based on the estimated evolution of the primary user transmission state. For a stationary randomized transmission policy that depends on the sensed state, we derive the secondary throughput and the collision probability. Due to the complexity of the resulting expressions, we develop an alternative formulation of the problem by recognizing that the throughput and collision probability are functions of the age of each type of sensed information. Therefore, we transform the problem by converting the randomized policy to its induced age distribution function. As a result, the age distribution-based formulation results in a linear program, which can be solved efficiently. We include numerical results and simulations, and discuss the role of the age distribution and other related qualities of the information.

A typical Internet-of-Things (IoT) system consists of three major layers: 1) sensing; 2) communication; and 3) application (i.e., actuation and control) layers. The co-design of these layers has been studied for over two decades, dating back to the concept of communication, computing, and control, i.e., 3C, convergence in the 1990s. Nowadays, with the emergence of wireless-networked machine-type applications, such as connected autonomous driving and factory automation, this co-design is more urgently desired than ever to meet the stringent quality-of-service requirements thereof. To realize this goal, the 5G wireless network of today has mainly focused on the communication part and strived to reliably achieve low air-interface communication delay, i.e., ultra-reliable and low-latency communications (uRLLC). However, more and more wireless communications in IoT are based on status updates instead of general content delivery. The current uRLLC design is insufficient to characterize the status update quality, and thus is unable to optimize for timely status update with constrained wireless resources. Therefore, the performance of computing and control in IoT networks that rely highly on wireless communications is suboptimal.

In this work, we investigate information freshness in a status update communication system consisting of a source-destination link. Initially, we study the properties of a sample path of the age of information (AoI) process at the destination. We obtain a general formula of the stationary distribution of the AoI, under the assumption of ergodicity. We relate this result to a discrete time queueing system and provide a general expression of the generating function of AoI in relation with the system time and the peak age of information (PAoI) metric. Furthermore, we consider three different single-server system models and we obtain closed-form expressions of the generating functions and the stationary distributions of the AoI and the PAoI. The first model is a first-come-first-served (FCFS) queue, the second model is a preemptive last-come-first-served (LCFS) queue, and the last model is a bufferless system with packet dropping. We build upon these results to provide a methodology for analyzing general non-linear age functions for this type of systems, using representations of functions as power series.

In this article, we consider the average age minimization problem where a central entity schedules M users among the N available users for transmission over unreliable channels. It is well-known that obtaining the optimal policy, in this case, is a difficult task. Accordingly, the Whittle's index policy has been suggested in earlier works as a heuristic for this problem. However, the analysis of its performance remained elusive. In the sequel, we overcome these difficulties and provide rigorous results on its asymptotic optimality in the many-users regime. Specifically, we first establish its optimality in the neighborhood of a specific system's state. Next, we extend our proof to the global case under a recurrence assumption, which we verify numerically. These findings showcase that the Whittle's index policy has analytically provable optimality in the many-users regime for the AoI minimization problem. Finally, numerical results that showcase its performance and corroborate our theoretical findings are presented.

This paper considers a status update communication system consisting of a source-destination link with timeliness requirements. First, we study the properties of a sample path of the age of information (AoI) process at the destination. Under the assumption of ergodicity, we obtain a general formula of the stationary distribution of the AoI. We relate this result to a discrete time queueing system and provide a general expression of the generating function of AoI in relation with the system time and the peak age of information (PAoI). Furthermore, we consider the first-come-first-served (FCFS) Geo/Geo/1 queue and we obtain closed-form expressions of the generating functions and the stationary distributions of the AoI and the PAoI. We built upon these results to provide a methodology for analyzing general non-linear age functions for this type of systems.

In this paper, we consider the average age minimization problem where a central entity schedules M users among the N available users for transmission over unreliable channels. It is well-known that obtaining the optimal policy, in this case, is out of reach. Accordingly, the Whittle's index policy has been suggested in earlier works as a heuristic for this problem. However, the analysis of its performance remained elusive. In the sequel, we overcome these difficulties and provide rigorous results on its asymptotic optimality in the many-users regime. Specifically, we first establish its optimality in the neighborhood of a specific system's state. Next, we extend our proof to the global case under a recurrence assumption, which we verify numerically. These findings showcase that the Whittle's index policy has analytically provable optimality in the many-users regime for the AoI minimization problem. Finally, numerical results that showcase its performance and corroborate our theoretical findings are presented.

In this work, we combine the two notions of timely delivery of information to study their interplay; namely, deadline-constrained packet delivery due to latency constraints and freshness of information. More specifically, we consider a two-user multiple access setup with random-access, in which user 1 is a wireless device with a queue and has external bursty traffic which is deadline-constrained, while user 2 monitors a sensor and transmits status updates to the destination. We provide analytical expressions for the throughput and drop probability of user 1, and an analytical expression for the average Age of Information (AoI) of user 2 monitoring the sensor. The relations reveal that there is a trade-off between the average AoI of user 2 and the drop rate of user 1: the lower the average AoI, the higher the drop rate, and vice versa. Simulations corroborate the validity of our theoretical results.

We consider a status update communication system consisting of a source-destination link. A stochastic process is observed at the source, where samples are extracted at random time instances, and delivered to the destination, thus, providing status updates for the source. In this paper, we expand the concept of information ageing by introducing the cost of update delay (CoUD) metric to characterize the cost of having stale information at the destination. The CoUD captures the freshness of the information at the destination and can be used to reflect the information structure of the source. Moreover, we introduce the value of information of update (VoIU) metric that captures the reduction of CoUD upon reception of an update. Using the CoUD, its by-product metric called peak cost of update delay (PCoUD), and the VoIU, we evaluate the performance of an M/M/1 system in various settings that consider exact expressions and bounds. The optimal server utilization policy is to minimize the time average CoUD and maximize the time average VoIU. Our results indicate that the performance of CoUD differs depending on the cost assigned per time unit, however the optimal policy remains the same for linear ageing and varies for non-linear ageing. When it comes to the VoIU the performance difference appears only when the cost increases non-linearly with time. The study illustrates the importance of the newly introduced variants of age, furthermore supported in the case of VoIU by its tractability.

Link scheduling, i.e., which links should transmit together and for how long, has been and remains a cornerstone optimization problem in wireless networking. In minimum-time scheduling, the task is to minimize the amount of time before emptying the data demand residing at the source nodes. We derive a complete structural characterization of the solution that unifies and significantly extends the known results. First, we approach link scheduling with a general system model without restrictions on the shape of the achievable rate region. Then, we give and prove a solution characterization of optimality that is conceptually simple yet powerful. We demonstrate several applications of this characterization for analysis of optimality and problem tractability. Next, we consider a significant extension by including deadline constraints, under which optimal scheduling becomes much more complex. Yet, we show how our formulation yields a solution description for that problem as well.

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.

In this paper, we investigate a network where $N$ links contend for the channel using the well-known carrier sense multiple access scheme. By leveraging the notion of stochastic hybrid systems, we find: 1) a closed-form expression of the average age when links generate packets at will 2) an upperbound of the average age when packets arrive stochastically to each link. This upperbound is shown to be generally tight, and to be equal to the average age in certain scenarios. Armed with these expressions, we formulate the problem of minimizing the average age by calibrating the back-off time of each link. Interestingly, we show that the minimum average age is achieved for the same back-off time in both the sampling and stochastic arrivals scenarios. Then, by analyzing its structure, we convert the formulated optimization problem to an equivalent convex problem that we find its optimal solution. Insights on the interaction between links and numerical implementations of the optimized Carrier Sense Multiple Access (CSMA) scheme in an IEEE 802.11 environment are presented. Next, to further improve the performance of the optimized CSMA scheme, we propose a modification to it by giving each link the freedom to transition to SLEEP mode. The proposed approach provides a way to reduce the burden on the channel when possible. This leads, as will be shown in the paper, to an improvement in the performance of the network. Simulations results are then laid out to highlight the performance gain offered by our approach in comparison to the optimized standard CSMA scheme.

In this paper, we introduce a new performance metric in the framework of status updates that we will refer to as the Age of Incorrect Information (AoII). This new metric deals with the shortcomings of both the Age of Information (AoI) and the conventional error penalty functions as it neatly extends the notion of fresh updates to that of fresh “informative” updates. The word informative in this context refers to updates that bring new and correct information to the monitor side. After properly motivating the new metric, and with the aim of minimizing its average, we formulate a Markov Decision Process (MDP) in a transmitter-receiver pair scenario where packets are sent over an unreliable channel. We show that a simple “always update” policy minimizes the aforementioned average penalty along with the average age and prediction error. We then tackle the general, and more realistic case, where the transmitter cannot surpass a specific power budget. The problem is formulated as a Constrained Markov Decision Process (CMDP) for which we provide a Lagrangian approach to solve. After characterizing the optimal transmission policy of the Lagrangian problem, we provide a rigorous mathematical proof to showcase that a mixture of two Lagrange policies is optimal for the CMDP in question. Equipped with this, we provide a low complexity algorithm that finds the AoII-optimal operating point of the system in the constrained scenario. Lastly, simulation results are laid out to showcase the performance of the proposed policy and highlight the differences with the AoI framework.

For the emerging Internet of Things (IoT), one of the most important basic problems is how to reconstruct signals in real-time from a set of under-sampled and delayed samples. The sampling omits the details of the signals of interest and the delayed samples against the requirement of real-time. As a result, distortion occurs between the interested signal and the reconstructed signal. In this paper, 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 derive the average distortion-sampling rate function, with which the optimal sampling rate can be obtained as well as the minimum average distortion. To further decrease the average distortion, an algorithm is proposed by sacrificing the real-time requirement in a small degree.

We consider a system consisting of a source-destination communication link. At the transmitter of the source there is a buffer that stores packets containing status information. These randomly generated packets should keep the destination timely updated and they can be discarded to avoid wasting network resources for the transmission of stale information. In this setup, we provide an analysis of the age of information (AoI) and peak age of information (PAoI) performance of the system, with and without packet management at the transmission queue of the source node. The analysis indicates the potential performance gains obtained with the use of packet management.

In this paper, we consider N information streams sharing a common service facility. The streams are supposed to have different priorities based on their sensitivity. A higher priority stream will always preempt the service of a lower priority packet. By leveraging the notion of Stochastic Hybrid Systems (SHS), we investigate the Age of Information (AoI) in the case where each stream has its own waiting room; when preempted by a higher priority stream, the packet is stored in the waiting room for future resume. Interestingly, it will be shown that a "no waiting room" scenario, and consequently discarding preempted packets, is better in terms of average AoI in some cases. The exact cases where this happen are discussed and numerical results that corroborate the theoretical findings and highlight this trade-off are provided.

In this paper, we investigate a network of N interfering links contending for the channel to send their data by employing the well-known Carrier Sense Multiple Access (CSMA) scheme. By leveraging the notion of stochastic hybrid systems, we find a closed form of the total average age of the network in this setting. Armed with this expression, we formulate the optimization problem of minimizing the total average age of the network by calibrating the back-off time of each link. By analyzing its structure, the optimization problem is then converted to an equivalent convex problem that can be solved efficiently to find the optimal back-off time of each link. Insights on the interaction between the links are provided and numerical implementations of our optimized CSMA scheme in an IEEE 802.11 environment are presented to highlight its performance. We also show that, although optimized, the standard CSMA scheme still lacks behind other distributed schemes in terms of average age in some special cases. These results suggest the necessity to find new distributed schemes to further minimize the average age of any general network.

This paper is motivated by the observation that the average queueing delay can be decreased by sacrificing power efficiency in wireless communications. In this sense, we naturally wonder what the minimum queueing delay is when the available power is limited and how to achieve the minimum queueing delay. To answer these two questions in the scenario where randomly arriving packets are transmitted over multi-state wireless fading channel, a probabilistic cross-layer scheduling policy is proposed in this paper, and characterized by a constrained Markov decision process. Using the steady-state probability of the underlying Markov chain, we are able to derive the mathematical expressions of the concerned metrics, namely, the average queueing delay and the average power consumption. To describe the delay-power tradeoff, we formulate a non-linear programming problem, which, however, is very challenging to solve. By analyzing its structure, this optimization problem can be converted into an equivalent linear programming problem via variable substitution, which allows us to derive the optimal delay-power tradeoff as well as the optimal scheduling policy. The optimal scheduling policy turns out to be dual-threshold-based, which means transmission decisions should be made based on the optimal thresholds imposed on the queue length and the channel state.

Carrier sense multiple access (CSMA) is widely used as a medium access control (MAC) in wireless networks due to its simplicity and distributed nature. This motivated researchers to find CSMA schemes that achieve throughput optimality. In 2008, it has been shown that a simple CSMA-type algorithm is able to achieve optimality in terms of throughput and has been given the name “adaptive” CSMA. Later, new technologies emerged where a prolonged battery life is crucial such as environment and industrial monitoring. This inspired the foundation of new CSMA-based MAC schemes, where links are allowed to transition into a sleep mode to reduce the power consumption. However, the throughput optimality of these schemes was not established. This paper, therefore, aims to find a new CSMA scheme that combines both throughput optimality and energy efficiency by adapting to the throughput and power consumption needs of each link. This is done by controlling operational parameters, such as back-off and sleeping timers, with the aim of optimizing a certain objective function. The resulting CSMA scheme is characterized by being asynchronous, completely distributed and being able to adapt to different power consumption profiles required by each link while still ensuring throughput optimality. The performance gain in terms of energy efficiency compared with the conventional adaptive CSMA scheme is demonstrated through computer simulations.

Wireless devices need to adapt their transmission power according to the fluctuating wireless channel in order to meet constraints of delay sensitive applications. In this paper, we consider delay sensitivity in the form of strict packet deadlines arriving in a transmission queue. Packets missing the deadline while in the queue are dropped from the system. We aim at minimizing the packet drop rate under average power constraints. We utilize tools from Lyapunov optimization to find an approximate solution by selecting power allocation. We evaluate the performance of the proposed algorithm and show that it achieves the same performance in terms of packet drop rate with that of the Earliest Deadline First (EDF) when the available power is sufficient. However, our algorithm outperforms EDF regarding the trade-off between packet drop rate and average power consumption.

We consider a cognitive shared access scheme consisting of a high priority primary node and a low priority network with N secondary nodes accessing the spectrum. Assuming bursty traffic at the primary node, saturated queues at the secondary nodes, and multipacket reception capabilities at the receivers, we derive analytical expressions of the time average age of information of the primary node and the throughput of the secondary nodes. We formulate two optimization problems, the first aiming to minimize the time average age of information of the primary node subject to an aggregate secondary throughput requirement. The second problem aims to maximize the aggregate secondary throughput of the network subject to a maximum time average staleness constraint. Our results provide guidelines for the design of a multiple access system with multipacket reception capabilities that fulfills both timeliness and throughput requirements.

Communication over an interference channel, which is fundamental and pervasive in the wireless and wireline environment, is often intended to carry information among different transmitter-receiver pairs. For applications that require time critical updates, it is desirable to maintain the freshness of the received information, which is quantified by the age metric (unlike the familiar delay metric). In this paper, we consider the case of two transmitter-receiver pairs, and address the impact of interference on information freshness by formulating a two-player “interference” game, in which each player is a transmitter desiring to maintain the freshness of the information updates it sends to its receiver. The strategy of a player is the choice of power level at which it will transmit. We then derive both Nash and Stackelberg strategies for the game. Our analysis shows that the Stackelberg strategy uses less power than the Nash strategy, and that it dominates the Nash strategy (i.e., the Stackelberg total cost function is lower than the Nash total cost function). Our obtained Nash and Stackelberg strategies are desirable user operating points in competitive situations.

In this paper, we examine a system where status updates are generated by a source and are forwarded in a First-Come-First-Served (FCFS) manner to the monitor. We consider the case where the server has other tasks to fulfill referred to as vacations, a simple example being relaying the packets of another non age-sensitive stream. Due to the server's necessity to go on vacations, the age process of the stream of interest becomes complicated to evaluate. By leveraging specific queuing theory tools, we provide a closed form of the average age of the stream which enables us to optimize its packet generation rate and achieve the minimum possible average age. Numerical results are provided to corroborate the theoretical findings and highlight the interaction between the stream and the vacations in question.

In this paper, we consider the two-user broadcast channel and we characterize its stable throughput region. We start the analysis by providing the stability region for the general case without any specific considerations on transmission and reception mechanisms. We also provide conditions for the stable throughput region to be convex. Subsequently, we study the case where the transmitter uses superposition coding and we consider two special cases for the receivers. The first one is when both receivers treat interference as noise. The second is when the user with a better channel uses successive decoding and the other receiver treats interference as noise.

This paper characterizes the performance in terms of queueing stability of a network composed of multiple MIMO transmitter-receiver pairs taking into account the dynamic traffic pattern and the probing/feedback cost. We adopt a centralized scheduling scheme that selects a number of active pairs in each time-slot. We consider that the transmitters apply interference alignment (IA) technique if two or more pairs are active, whereas in the special case where one pair is active point-to-point MIMO singular value decomposition (SVD) is used. 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 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 provide the conditions under which IA yields a queueing stability gain compared to SVD. Under the general system, the adopted scheduling policy is of a high computational complexity for moderate numbers 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.

Information age is a recently introduced metric to represent the freshness of information in communication systems. We investigate age minimization in a wireless network and propose a novel approach of optimizing the scheduling strategy to deliver all messages as fresh as possible. Specifically, we consider a set of links that share a common channel. The transmitter at each link contains a given number of packets with time stamps from an information source that generated them. We address the link transmission scheduling problem with the objective of minimizing the overall age. This minimum age scheduling problem (MASP) is different from minimizing the time or the delay for delivering the packets in question. We model the MASP mathematically and prove it is NP-hard in general. We also identify tractable cases as well as optimality conditions. An integer linear programming formulation is provided for performance benchmarking. Moreover, a steepest age descent algorithm with better scalability is developed. Numerical study shows that, by employing the optimal schedule, the overall age is significantly reduced in comparison to other scheduling strategies.

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 studies the problem of feedback allocation and scheduling for a multichannel downlink cellular network under limited and delayed feedback. We propose two efficient algorithms that select the link states that should be reported to the base station (BS). A novelty here is that these feedback allocation algorithms are performed at the users' side to take advantage of their local channel state information knowledge in order to achieve higher gains. The first algorithm is suitable for a continuous-time contention scheme and requires only one feedback per channel, whereas the second one is adapted for a discrete-time contention scheme and adopts a threshold-based concept. For this second algorithm, we study some implementation aspects related to the feedback period and investigate the tradeoff between knowing at the BS a small number of accurate link states and a larger but outdated number of link states. We show that these algorithms, combined with the Max-Weight scheduling, achieve good stability performance compared with the ideal system.

In this paper, we study delay optimal scheduling of bursty data traffics over multi-state time-varying wireless channels, where bursty packet arrival in the network layer, queueing behavior in the data link layer, and rate adaptive transmission with flexible modulation in the physical layer are jointly considered from a cross-layer perspective. To achieve a minimum queueing delay under a power constraint, a probabilistic queue-aware and channel- aware cross-layer scheduling policy is proposed, and characterized by a Markov chain model, where the transmission rate, i.e., the number of packets delivered in each slot, is selected with probabilities based on the buffer and channel states in this slot. To reveal the optimal delay-power tradeoff, we formulate a non-linear optimization problem, which, however, is very challenging to solve. To make it tractable, we convert the optimization problem equivalently into a Linear Programming (LP) problem, which helps us achieve the optimal three-dimensional threshold-based scheduling policy analytically. It is found that the source should select one transmission rate jointly based on the channel state and the backlog in the queue.

We consider link scheduling in wireless networks for emptying the queues at the transmitters in minimum time, with time constraints, or deadlines, for one or multiple individual links. We formulate the minimum-time scheduling problem with deadlines (MTSD) mathematically and derive the optimal activation order of the link sets in a schedule solution. Theoretical results are obtained, showing that the MTSD can be treated as the conventional minimum-time scheduling problem by “absorbing” the deadline constraints into the rate region where the scheduling problem is defined. By this approach, optimality characterization and geometric interpretation for the MTSD are provided. Furthermore, we extend the results to the MTSD in a general form that accommodates an arbitrary rate region.

We propose a model for mobile caching in which the rate of requests for content is dependent on the popularity and the freshness of the information. We model popularity based on the history of requests and freshness based on the age of the content. We consider a discrete time (slotted) system in which new packets arrive at a limited capacity cache at discrete times. We prove that the optimal policy for choosing the set of packets to reside in a full cache when a packet arrives is to reject the one with the lowest request rate in that particular slot. Thus, there is no advantage to separately knowing the history of requests or the age of the content. Since the optimal policy depends on the profile of the request process, we also study the expected behavior of the request model. We provide a sufficient condition under which the change in the request rate goes to zero and provide some numerical examples that illustrate this behavior. We also consider a slight alteration to the model, in which only the recent history of requests is used for determining the request rate. In this case, we provide a sufficient condition for when the rate is equal to zero, which approximates the duration of requests for content.

We consider a real-time status update system consisting of a source-destination network. A stochastic process is observed at the source, and samples, so called status updates, are extracted at random time instances, and delivered to the destination. In this paper, we expand the concept of information ageing by introducing the Cost of Update Delay (CoUD) metric to characterize the cost of having stale information at the destination. We introduce the Value of Information of Update (VoIU) metric that captures the reduction of CoUD upon reception of an update. The importance of the VoIU metric lies on its tractability which enables an alternative performance criterion in status update systems.

We consider the Gaussian interference channel as a non-cooperative game taking into account the cost of the transmission. We study the conditions of the existence of a pure Nash equilibrium. Particularly, for the many-user case we give sufficient conditions that lead to a Nash equilibrium, and for the two-user case we exhaustively describe the conditions of the existence and the uniqueness of a pure Nash equilibrium and we show the existence of best-response dynamics that converge to one of them.

For time critical updates, it is desirable to maintain the freshness of the received information. We address the impact of hostile interference on information freshness by formulating a non-zero-sum two-player game, in which one player is the transmitter aiming to maintain the freshness of the information updates it sends to its receiver, and the other player is the interferer aiming to prevent this. The strategy of a player is the power level transmitted by that player. We then derive the equilibria for both Nash and Stackelberg strategies. We show that both players have the same power cost at Nash equilibrium. In addition, the Stackelberg strategy dominates the Nash strategy, i.e., the Stackelberg utility function exceeds the Nash utility function.

We address the maximum link activation problem in wireless networks with new features, namely when the transmitters can perform cooperative transmission, and the receivers are able to perform successive interference cancellation. In this new problem setting, which transmitters should transmit and to whom, as well as the optimal cancellation patterns at the receivers, are strongly intertwined. We present contributions along three lines. First, we provide a thorough tractability analysis, proving the NP-hardness as well as identifying tractable cases. Second, for benchmarking purposes, we deploy integer linear programming for achieving global optimum using off-the-shelf optimization methods. Third, to overcome the scalability issue of integer programming, we design a suboptimal but efficient optimization algorithm for the problem in its general form, by embedding maximum-weighted bipartite matching into local search. Numerical results are presented for performance evaluation, to validate the benefit of cooperative transmission and interference cancellation for maximum link activation, and to demonstrate the effectiveness of the proposed algorithm.

Freshness of information is of critical importance for a host of applications of wireless communications. In order to deliver information from multiple sources in a timely and fair fashion through a wireless channel, we propose optimizing the link scheduling strategy in respect of age of information, which is a newly introduced metric that measures how fresh information is. Specifically, we consider a set of co-channel links, each having a number of packets to be delivered, and address the problem that aims to find the optimal scheduling solution, such that the maximum peak age of information is minimized. We mathematically formulate this so-called min-max peak age scheduling problem (MPASP), and prove it is NP-hard. Theoretical insights including tractable cases and optimality properties are derived. For problem solution, an integer linear programming (ILP) formulation is proposed. We also develop a sub-optimal, but fast, algorithm to solve the problem with better scalability. Numerical study shows that, by employing the optimal schedule, the maximum peak age is significantly reduced in comparison to other classic scheduling strategies such as minimum-time scheduling.

Dynamic spectrum sensing and opportunistic access in cognitive communications enable secondary users to recognize and utilize the white spaces of the licensed bandwidth. Our prior work proposed a non-uniform scheme of bandwidth partition and traffic allocation with the aim of regularizing the primary user's (PU's) bandwidth occupancy pattern, which was able to improve the performance of the secondary user (SU). In the current paper, we study the non-uniform scheme under fading situations. The optimal bandwidth allocation under fading situations is defined as maximizing the spare capacity for the SU subject to satisfying the PU's demand. The problem is proved to be NP-hard. To lower the computational overhead, we further study the problem of maximizing the spare subcarriers for the SU, and propose an optimal algorithm for the PU traffic allocation with polynomial time complexity. By numerical simulations, we demonstrate that the algorithm is able to achieve almost identical performance to that of the optimal solution of the original problem. In addition, the non-uniform scheme, which is based on that algorithm, exhibits better performance than the uniform one even under fading situations.

We consider link scheduling in wireless networks for emptying the queues of the source nodes, and provide a unified mathematical formulation that accommodates all meaningful settings of link transmission rates and network configurations. We prove that, any scheduling problem is equivalent to solving a convex problem defined over the convex hull of the rate region. Based on the fundamental insight, a general optimality condition is derived, that yields a unified treatment of optimal scheduling. Furthermore, we demonstrate the implications and usefulness of the result. Specifically, by applying the theoretical insight to optimality characterization and complexity analysis of scheduling problems, we can both unify and extend previously obtained results.

We study the age of information, which is a recently introduced metric for measuring 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 queuing systems. In this work, we introduce a packet deadline as a control mechanism and study its impact on the average age of information for an M/M/1/2 queuing system. We analyze the system for a fixed deadline and derive a mathematical expression for the average age. We numerically evaluate the expression and show the relationship of the age performance to that of the M/M/1/1 and M/M/1/2 systems. We show that the system with a deadline constraint can outperform both the M/M/1/1 and M/M/1/2 without such a deadline.

There is a growing interest in age of information, which is a newly introduced metric that measures the freshness of information in communication systems. We investigate the age of information in wireless networks and propose the novel approach of optimizing the scheduling strategy to deliver the information as timely as possible. We consider a set of links that share a common channel, each containing a number of packets with time stamps, and address the scheduling problem with the objective of minimizing the overall information age. We model this problem mathematically and prove it is NP-hard in general. Fundamental insights including tractable cases and optimality conditions are presented. An integer linear programming formulation is provided for performance benchmarking. Moreover, a steepest age decent algorithm with better scalability is developed. Numerical study shows that, by employing the optimal schedule, the overall information age is significantly reduced in comparison to other scheduling strategies.

We formulate the interaction between communication and hostile interference in wireless systems as a non-zero-sum two-player game. One player is the transmitter aiming to establish or maintain the communication to its receivers, and the other player is the interferer aiming to prevent or disrupt the communication. The strategy of the transmitter is a transmission power level, while the strategy of the interferer is an interfering power level. We provide closed-form equilibria for both Nash and Stackelberg models. We show that, while a Stackelberg equilibrium always exists, a Nash equilibrium exists only when the wireless channel is affected by fading. In addition, for the case of Rayleigh channel fading, we show that both players have the same power cost at Nash equilibrium.

Energy efficiency is a critical issue in wireless networks, not only due to the technological limitations on energy supplies, but also due to the environmental impact caused by the information and communication technologies. This work discusses performance tradeoffs related to the energy efficiency, providing insightful results on the intricate relationship between system parameters. We propose a new parametrization to study a network in which users with different priorities to access the network resources can interfere and cooperate among themselves. A non-cooperative model is analyzed under three different spectrum sharing schemes, and we discuss important tradeoffs between energy efficiency and throughput, and between energy efficiency and the spectrum sensing accuracy. We also propose a cooperative model, in which a low-priority user relays packets for the high-priority user as repayment for interference. The energy-throughput tradeoff is analyzed in the case of cooperation, both in the case of half-duplex and full-duplex relays with different degrees of self-interference cancellation.

We consider a communication system in which status updates arrive at a source node, and should be transmitted through a network to the intended destination node. The status updates are samples of a random process under observation, transmitted as packets, which also contain the time stamp to identify when the sample was generated. The age of the information available to the destination node is the time elapsed, since the last received update was generated. In this paper, we model the source-destination link using the queuing theory, and we assume that the time it takes to successfully transmit a packet to the destination is an exponentially distributed service time. We analyze the age of information in the case that the source node has the capability to manage the arriving samples, possibly discarding packets in order to avoid wasting network resources with the transmission of stale information. In addition to characterizing the average age, we propose a new metric, called peak age, which provides information about the maximum value of the age, achieved immediately before receiving an update.

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/∞ 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/∞ 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.

In this paper, we asses the benefits of using partial relaying in energy-harvesting networks. We consider a system composed of a source, a relay, and a destination. Each of the source and the relay has energy-harvesting capability and generates its own traffic. The source is helped by the relay through a partial relaying network-level cooperation protocol. The relay regulates the arrivals from the source by accepting only a proportion of the successfully received packets at the relay. The relaying parameter, which determines the proportion of packets to be accepted, is selected based on the parameters of the network to ensure the stability of the source and the relay data queues. In this work, we provide an exact characterization of the stability region of the network. We derive the optimal value of the relaying parameter to maximize the stable throughput of the source for a given data arrival rate to the relay. Also, we compare the stability region of the proposed strategy with partial relaying to the stability regions of simple transmission strategies. Finally, we consider the problem of network utility optimization in which we optimize over the value of the relaying parameter for a given pair of data arrival rates for the source and the relay.

In this work, we analyze the effect of outdated channel information on the performance of a non-reciprocal wireless link. We introduce a model of channel information age for a Finite-State Markov Channel. Then, we use this model to analyze the probability of a channel estimation error and to express utility as a function of channel information age and cost of periodic feedback. This utility function allows us to analyze the trade-off between performance and timeliness of the channel information. Applying this general model to the example of Rayleigh fading, provides interesting insight into the performance and design of channel adaptation functions and feedback protocols.

In cognitive communication, dynamic sensing and opportunistic accessing enable secondary users to recognize and utilize the white spaces of the licensed bandwidth. Most present efforts focus on designing smarter channel sensing and access algorithms for secondary users to optimize the overall throughput and bandwidth utilization efficiency, without interfering with primary users' communication. However, the transmission of the primary users are basically random and unpredictable, which usually makes the cognitive process complex and ineffective. In this paper, a non-uniform bandwidth allocation scheme is proposed, in order to regularize primary users' bandwidth occupancy, which can in turn improve the sensing efficiency and throughput of the secondary users. The performance benefits are demonstrated analytically and verified by numerical simulations. In comparison to the conventional uniform bandwidth allocation scheme, the non-uniform scheme shows a higher sensing efficiency and spectrum utilization due to less bandwidth loss and lower sensing cost.

We study the minimum latency broadcast scheduling problem, in which a single source has a quantity of data that must be transmitted to all other nodes in a multi-hop network in minimum time. Aside from the obvious application to classical communications, this problem also relates to some more general problems in the field of network science. Previous approaches to scheduling have assumed a simplistic collision model of interference, while others have studied the more realistic physical model of total received interference power. Existing suboptimal approaches for transmitting the data typically assume a collision-free, fixed-rate, single packet transmission. In this work, we devise an optimal approach for broadcast under a physical interference model with fixed-rate, single packet transmission by converting it to a shortest path problem for an unweighted, undirected graph. Since this optimal approach does not scale well, we also consider a suboptimal layered approach which separates the routing and scheduling functions, but relaxes the fixed-rate, single packet assumption. This goes beyond the signal-to-interference-plus-noise (SINR) threshold model to allow for rate adaptation as a function of SINR. We include improvements on previous routing approaches, and we formulate a linear programming approach to the variable-rate scheduling for broadcast. Simulations show that in some special cases, this variable-rate layered approach can even outperform the optimal fixed-rate, single packet approach.

We present a framework to study the effect of outdated Channel State Information (CSI) on the performance of a non-reciprocal wireless link. The proposed framework is based on the new concept of age of information. We adopt the Gilbert-Elliot channel model to obtain analytic results regarding the use of periodic CSI feedback and investigate the effect of the age of CSI when multiple orthogonal resource blocks are assigned to a communication link. A general utility function is defined as performance metric, which accounts for the cost of feedback. Our work improves the comprehension about the age of channel state information and its effect on the performance of communication links, which is fundamental for designing efficient adaptation functions and feedback protocols.

We consider a wireless network consisting of source-destination pairs, in which each source is required to transmit a given bit volume to its destination. The goal is for all the sources to transmit the given bit volumes, under a time constraint, so that the total transmission energy is minimized. Our approach is the joint optimization of link scheduling and power control for minimum energy. We show that TDMA scheduling is appropriate for this goal, in the sense that TDMA is asymptotically optimal when the time constraint approaches infinity. When the time constraint is strictly bounded, we show that TDMA is also optimal for the case of equal channel gains.

In this paper, we consider random access by nodes that have energy harvesting capability. Each node is equipped with both a queue for storing the arriving packets and a battery for storing the harvested energy chunks, where the packet arrival and the energy harvesting events are all modeled as discrete-time stochastic processes. In each time slot, each node attempts to transmit the head-of-the-line packet in the queue with some probability if its battery is non-empty, and each transmission consumes one chunk of energy. Therefore, the transmission by one node is not just limited by the availability of packets in the queue but also by the availability of energy chunks in the battery. In most of related previous work, it was implicitly assumed that there exists unlimited energy for transmission, which is impractical in many distributed systems. In this work, we characterize the exact stability region when a pair of bursty nodes, which are harvesting energy from the environment, are randomly accessing a common receiver. The analysis takes into account the compound effects of multi-packet reception capability at the receiver. The contributions in the paper are twofold. First, we accurately assess the effect of limited, but renewable, energy availability due to harvesting on the stability region by comparing against the case of having unlimited energy. Second, the impact of the finite capacity batteries on the achieved stability region is also quantified.

In cognitive communication, dynamic sensing and opportunistic access enable secondary users to recognize and utilize the white spaces of the licensed bandwidth. Most present efforts focus on designing smarter channel sensing and access algorithms for secondary users, with the aim of optimizing the overall throughput and bandwidth utilization efficiency, under the condition of not interfering with primary users' communication. However, as the transmissions of the primary users are inherently random and unpredictable, sensing and sharing spectrum with the primary users inevitably make the cognitive process of the secondary users complex and ineffective. In this paper, a non-uniform bandwidth allocation scheme is proposed that regularizes the primary users' bandwidth occupancy pattern. The regularization is not designed to reshape the primary users's traffic, but to improve the sensing efficiency and throughput of the secondary users by optimizing the spectrum allocation. After the description of the new allocation scheme, we demonstrate its performance by theoretic analysis. Then we verify the validity of the non-uniform scheme with numerical simulations under non-fading and fading situations respectively. Through comparisons with the conventional uniform bandwidth allocation scheme, the non-uniform one shows higher sensing efficiency and better spectrum utilization due to lower sensing cost and reduced bandwidth loss.

The effect of full-duplex cooperative relaying in a random access multiuser network is investigated here. First, we model the self-interference incurred due to full-duplex operation, assuming multi-packet reception capabilities for both the relay and the destination node. Traffic at the source nodes is considered saturated and the cooperative relay, which does not have packets of its own, stores a source packet that it receives successfully in its queue when the transmission to the destination has failed. We obtain analytical expressions for key performance metrics at the relay, such as arrival and service rates, stability conditions, and average queue length, as functions of the transmission probabilities, the self interference coefficient, and the links' outage probabilities. Furthermore, we study the impact of the relay node and the self-interference coefficient on the per-user and aggregate throughput, and the average delay per packet. We show that perfect self-interference cancelation plays a crucial role when the SINR threshold is small, since it may result to worse performance in throughput and delay comparing with the half-duplex case. This is because perfect self-interference cancelation can cause an unstable queue at the relay under some conditions.

We consider a system in which random status updates arrive at a source node, and should be transmitted through a wireless network to the intended destination node. The status updates are samples of a random process, transmitted as packets, containing the time stamp to identify the moment the sample was generated. The time it takes to successfully transmit a packet to the destination is modeled as an exponentially distributed service time. The status update age at the receiver is the time elapsed since the last received update was generated. In this paper, we analyze the age in the case that the source node has the capability to manage the arriving samples and decide which packets will be transmitted to the destination. In addition to the average age, we investigate the average of a new metric, called peak age, which provides information about the maximum value of the Age, achieved immediately before receiving an update.

We study from a network-layer perspective a simple cognitive network consisting of one primary user (PU) and one secondary user (SU) sharing the spectrum with the primary. We propose and analyze two different access schemes at the SU aiming at maximizing its stable throughput while guaranteeing the stability of the PU's queue. These schemes exploit the SU's knowledge of the statistics of the channels as well as the average arrival rate to the PU. The first scheme is where the SU does not perform any sensing but accesses the channel at all slots with fixed probability p*. The second scheme is where the SU senses the channel at all slots and accesses the channel with probabilities p1* and p2* when the PU is sensed to be idle and busy respectively. We also compare these schemes to the traditional opportunistic spectrum access (OSA) where the SU accesses the channel with probability one only if the channel is sensed to be idle. The analysis shows that if the PU and/or SU receivers can decode simultaneous transmissions with high success probability, then schemes with no sensing are preferred as they provide to the SU more duration for data transmission and they outperform schemes with sensing. In this case, the OSA scheme is over- protective. Otherwise, schemes with sensing are preferred since sensing is crucial for PU protection. Therefore, using complex receivers that can handle simultaneous transmissions successfully alleviates the need of complex SU transmitters with strong sensing capability which might be preferred in some circumstances.

We investigate the performance of a status monitoring system, in which a sensor sends random status updates over a network to a remote monitor. Specifically, we analyze the status age metric, which characterizes how old the information at the monitor is from the last received status update. The system on which we focus is a single queue with 2 servers (specifically, an M/M/2). In a dynamic network, different status packets may take different routes to the monitor, which allows for the possibility of packets arriving out of order. In the case of the status monitoring system, only the latest status is useful. Studying a system with 2 servers allows for the possibility of packets to arrive out-of-order while still having to queue. We present the exact approach to computing the analytical status age, and we provide an approximation that matches very closely with the simulated age. We also compare with the M/M/∞ and M/M/1, and we demonstrate the tradeoff between status age and network resource consumption.

Wireless systems of rechargeable nodes have extended lifetime and are self-sufficient. The transmission policies in these systems need to adapt to the harvested energy availability. In this work, we investigate the interaction between relaying, energy harvesting, and stability. We introduce the problem of general relaying cost minimization for cooperative energy harvesting networks. We consider a simple network in which a source transmits to a destination through network-level cooperation with a number of relay nodes. The source and the relays have energy harvesting capability. To adapt the relaying process to the available harvested energy, we exploit partial relay cooperation in which the flows through the relays are controlled. The relaying cost minimization problem is feasible when the data queues of the source and the relays are stable. The stability conditions of the data queues are derived. Then, we introduce the energy consumption as a cost criterion for the optimization problem to find an energy-efficient partial relaying protocol. We assess the effect of partial relay cooperation compared to the cases of no cooperation and full relay cooperation.

We study the energy-efficient transmission problem for a time-varying interference channel. Assume that each source transmits in each time slot according to a transmission probability, which is a continuous value between 0 and 1. Our goal is to determine the values of the transmission probabilities and the transmission power levels so that the network energy efficiency is maximized. We show that the energy efficiency is maximized when the transmission probabilities are either 0 or 1. We also show that simultaneous transmissions reduce energy efficiency. We then address the impact of the accuracy and timeliness of channel state information (CSI) on energy efficiency. The following cases are considered: perfect CSI, erroneous CSI, delayed CSI, and unknown CSI.

We consider the problem of reliable spectrum sensing and opportunistic access on channels with stochastic traffic in batch processing systems such as network coding (NC). We show how a secondary user (SU) can leverage the structure induced by block-based NC on primary users' (PUs) channels to mitigate the effects of channel sensing errors and improve the detection of idle PU spectrum and the throughput. NC is known to improve the transmission efficiency and therefore when applied on a PU channel, it can extend the spectrum availability for the SUs. We refer to the additional gain of spectrum predictability from NC and show that under possible sensing errors the SU can more reliably detect the idle spectrum if the PUs' channels carry network-coded transmissions even when the channel utilization is fixed. We consider two different objectives at the SU. For quickest detection, the SU applies the Cumulative Summation (CUSUM) algorithm to detect idle slots on a PU channel and further improves the detection capability with the Viterbi algorithm, if the PU spectrum dynamics are known. For throughput maximization, the SU tracks the PU spectrum with the Partially Observable Markov Decision Process (POMDP) approach. Our results show that NC renders the spectrum more predictable, which can be used by the SUs to mitigate the effects of sensing errors and improve the throughput. We validate these results with real radio measurements taken in software-defined radio based wireless network tests.

In this paper, we study the stability property of a cognitive radio system comprised of a set of source-destination pairs having different priorities. In particular, we focus attention on the effect of imperfect sensing on the stability region of the system, which has been overlooked in most of related previous work. The adopted cognitive access protocol allows the secondary user not only to exploit the idle slots of the primary user but also to transmit along with the primary user with some probability. This is aimed at achieving the full utilization of the shared channel with capture, i.e., a transmission can be correctly decoded at the destination, even in the presence of other transmissions, if the received signal-to-interference-plus-noise ratio (SINR) exceeds a certain threshold for successful decoding. The abolition of strong primacy, however, requires the secondary user to properly regulate its multi-access probability in order not to impede the primary user's stability guarantee. To this end, the maximum stability region of the system is characterized which describes the theoretical limit on rates that can be pushed into the system while maintaining the queues stable. Interestingly, we found that even with non-zero sensing error rates, there exists a condition for which we can achieve the identical stability region that is achieved with perfect sensing. This is when the destinations enjoy fairly strong capture, and if then sensing errors do not affect the stability region for the queueing system. For the case when the specified condition does not hold, we precisely quantify the loss due to the imperfect sensing in terms of the size of the stability region. Finally, we study the problem of controlling the operating point of the sensing device over its receiver operating characteristic (ROC) and summarize some key aspects observed in the control.

We consider the problem of streaming a file by exchanging information over wireless channels in the presence of an eavesdropper. We utilize private and public channels and wish to minimize the use of the (more expensive) private channel subject to a required level of security. We consider both single and multiple users and compare simple ARQ and deterministic network coding as methods of transmission.

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.

This paper addresses fundamental issues in a shared channel where the users have different priority levels. In particular, we study a two-user cognitive shared channel consisting of a primary (higher-priority) and a secondary user, operating in the cognitive underlay fashion, but in a novel way where interference suffered by the primary user is compensated by requiring the secondary user to cooperatively relay some of the primary's packets. We start by analyzing the case of no node cooperation, where nodes transmit their own packets to their respective destinations. We then extend the analysis to a system in which the secondary node acts as a relay for the primary user, in addition to serving its own packets. Specifically, in the cognitive cooperation case, the secondary node forwards those packets to the primary destination that it receives successfully from the primary source. In such cognitive shared channels, a tradeoff arises in terms of activating the secondary along with the primary so that both transmissions may be successful, but with a lower probability, compared to the case of the secondary node staying idle when the primary user transmits. Results show the benefits of relaying for both the primary as well as the secondary nodes in terms of the stable-throughput region.

We study from a cross-layer perspective a cognitive network consisting of one primary user (PU) and one secondary user (SU). In contrast with the oversimplified collision channel model, we assume that simultaneous PU and SU transmissions are successful with some positive probability. We propose and analyze two access schemes at the SU aiming at maximizing its stable throughput while guaranteeing the stability of the PU's queue. These schemes exploit the SU's knowledge of the channel statistics and of the average arrival rate to the PU. In the first scheme, the SU accesses the channel at all slots with fixed probability p^* without sensing. In the second scheme, the SU accesses the channel with probabilities p_1^* and p_2^* when the PU is sensed to be idle and busy, respectively. The analysis shows that if simultaneous PU and SU transmissions are likely to be successful, schemes with no sensing outperform schemes with sensing. Otherwise, schemes with sensing are preferred. Therefore, using complex receivers capable of handling interference, alleviates the need of complex SU transmitters with strong sensing capabilities. We then extend the analysis to the case where the PU has an average delay constraint which is more restrictive than the stability constraint.

In this work, we investigate the queue stability of a two-user cognitive radio system with multicast traffic. We study the impact of network-level cooperation, in which one of the nodes can relay the packets of the other user that are not received at the destinations. Under this approach, if a packet transmitted by the primary user is not successfully received by the destination set but is captured by the secondary source, then the secondary user assumes responsibility for completing the transmission of the packet; therefore, the primary releases it from its queue, enabling it to process the next packet. We demonstrate that the stability region of this cooperative approach is larger than that of the noncooperative approach, which translates into a benefit for both users of this multicast system. Our system model allows for the possibility of multipacket reception, and the optimal transmission strategies for different levels of multipacket reception capability are observed in our numerical results.

In this work, we consider a hybrid of interweave and underlay modes of operation for cognitive radio systems with random connectivity and bursty packet arrivals. Under the designed hybrid access policy, the secondary communication system is allowed to operate in the interweave mode only when its transmission has no harm on the primary communication. This is when the primary communication system is idle or the interference link from the secondary source to the primary destination is disconnected. The secondary communication system can optionally operate in the underlay mode, although when it is inevitable to interfere with the primary communication. The underlay mode is activated with some probability, called the hybrid rate. We analyze the stability of the hybrid access policy and show that it is not always beneficial when compared against the interweave-only mode. Thus, the condition for which the hybrid access policy can outperform is specified.

We consider the system where a source randomly generates status update messages and transmits them via a network cloud to the intended destination. These update message can take different times to traverse the network, which we model as exponential service times, and may result in packets reaching the destination out of order, rendering some of the earlier transmissions obsolete. We analyze the status update age for such a system, and show that it tracks well with simulation results.

The stable throughput region of the two-user interference channel is investigated here. First, the stability region for the general case is characterized. Second, we study the cases where the receivers treat interference as noise or perform successive interference cancelation. Finally, we provide conditions for the convexity/concavity of the stability region and for which a certain interference management strategy leads to broader stability region.

In this paper we study the impact of a relay node in a two-user network. We assume a random access collision channel model with erasures. In particular we obtain an inner and an outer bound for the stability region.

We study, from a network layer perspective, the effect of an Ad-Hoc secondary network with N nodes accessing the spectrum licensed to a primary node. If the sensing is perfect, then the secondary nodes do not interfere with the primary node and thus do not affect its stable throughput. In case of imperfect sensing, it is shown that if the primary node's arrival rate is less than some calculated value, then the secondary transmissions do not affect its queueing stability; otherwise, the secondary nodes should regulate their transmission parameters to reduce their interference on the primary. It is also shown that in contrast with the primary user's maximum stable throughput rate which strictly decreases with increased sensing errors, the throughput of the secondary nodes might increase with sensing errors as more transmission opportunities become available to them. Finally, we explore the use of the secondary nodes as relays of the primary node's traffic to compensate for the interference they might cause. In this case, for appropriate modulation scheme and under perfect sensing, it is shown that the more secondary nodes in the system, the better for the primary user in terms of his stable throughput. Meanwhile, the secondary nodes might benefit from relaying by having access to a larger number of idle slots becoming available to them due to the increase of the service rate of the primary. For the case of a single secondary node, the proposed relaying protocol guarantees that either both the primary and the secondary benefit from relaying or none of them does.

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.

The underwater acoustic channel is characterized by a path loss that is dependent on both the distance and the frequency of communication. Given this dependence, it has been previously demonstrated that for a given communication distance, there is an optimal operating frequency, where conditions for signal propagation and noise are most favorable. In this work, we consider extending this optimal frequency concept to scenarios in which the frequencies that can be employed by the system are constrained. Such constraints are important considerations for practical system design. The first problem we study is to find a single frequency that minimizes the energy over a number of links of varying lengths. An approximate model for this frequency is proposed that is very close to the true optimal. We then generalize this problem to finding the best frequency band, within which the frequency can be tuned for different link lengths. We demonstrate how our model is applied to a 2-D network scenario. We simulate random node placement for such a network, and we observe that the optimal frequencies are very close to the proposed model.

In this paper, we consider the problem of calculating the stability region of a two-user cognitive shared channel where the secondary (lower priority) user, whose channel is modeled as a two-state Gilbert-Elliott channel, utilizes the channel state information to adapt its transmission probabilities accordingly. The analysis also takes into account the compound effects of multipacket reception at the receiver as well as the cooperative relaying capability of the secondary node, on the stability region of the cognitive network. Results clearly illustrate that the knowledge of the secondary channel state benefits not only the secondary user, but also the primary user as well.

We consider N transmitter-receiver pairs that share a wireless channel and we address the problem of obtaining a schedule for activating subsets of these links so as to empty the transmitter queues in minimum time. Our aim is to provide theoretical insights for the optimality characterization of the problem, using both a cross-layer model formulation, which takes into account the effect of interference on achievable transmission rates, as well as a collision-based model, which does not incorporate the physical layer realities into the problem. We present the basic linear programming formulation of the problem and establish that the optimal schedule need not consist of more than N subset activation frames. We then prove that the problem is NP-hard for all reasonable continuous rate functions. Finally, we obtain sufficient and/or necessary conditions for optimality in a number of special cases.

We consider a cognitive network consisting of one primary source-destination pair and N secondary cognitive source-destination pairs that randomly access the channel during the primary user's idle slots. We first study the effect of the secondary nodes' transmission parameters such as power and channel access probabilities on the stable throughput of the primary node. If the sensing is perfect, then the secondary nodes do not interfere with the primary node and thus do not affect its stable throughput. In case of imperfect sensing, it is shown that if the primary node's arrival rate is less than some calculated value, then the secondary transmissions do not affect its queueing stability; otherwise, the secondary nodes should regulate their transmission parameters to reduce their interference on the primary. Finally, we propose a multinode relaying protocol based on distributed space-time orthogonal block codes, that uses the secondary nodes as relays of the primary node's traffic to compensate for the interference they might cause. In this case, for appropriate modulation scheme and under perfect sensing, it is shown that the more secondary nodes in the system, the better for the primary user in terms of his stable throughput. Meanwhile, the secondary nodes might benefit from relaying by having access to a larger number of idle slots becoming available to them due to the increase of the service rate of the primary.

In this work, we consider a system with time-varying channels and random access that exploits the channel state information (CSI). The CSI is not directly available to each node but estimated with some errors. An exact stability analysis is carried out for the considered model when a pair of bursty sources are competing for a shared channel and the receiver has multipacket reception capability. The contributions in the paper are twofold: first, we identify the effect of channel estimation errors on the achievable stability region of the channel-aware random access protocol. Secondly, we make a comparison with the class of stationary scheduling policies.

In this paper, we evaluate the benefits of using one user of a two-user random access system to relay traffic of the other user.

In cellular systems, base stations are considered the components that mostly drain energy. Hence, recent attempts have been made to reduce the power consumed by base stations by several methods such as "micro" sleep modes, where some parts of the transceiver can be temporarily switched off in short intervals where no information is transmitted. The objective of this study is to exploit the sleep mode feature of base stations and to use rate allocation techniques in order to minimize the energy spent to satisfy the demands of its users and their QoS requirements such as delay. In order to understand the behavior of the rate allocation method, the case where there is only a single active user in the cell is first considered. Then, the problem is extended to the case when several active users are present.

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.

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.

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.

Cooperation enhances the performance of wireless networks with fading channels. In this paper, we develop joint physical and network layer cooperative techniques in a simple network composed of a single source, a relay, and a destination, and focus on energy consumption as the performance criterion. Two transmission schemes are used at the network layer: (i) Simple Automatic Repeat Request (ARQ) and (ii) Random Network Coding (RNC). We also consider the use of Alamouti Space-time codes at the physical layer. For each of the proposed cooperative schemes, we consider the energy consumed per successfully delivered packet, and then find the optimal power values used by the source and the relay that minimize the energy consumed. Finally, we use the obtained optimal power values to compute the minimum stable throughput achieved at the source. Our results show that cooperation using Random Network Coding combined with Alamouti Coding at the physical layer achieves the best performance among the proposed schemes.

This paper addresses fundamental issues in a shared channel where the users have different priority levels. In particular, we characterize the stable-throughput region in a two user cognitive shared channel where the primary (higher priority) user transmits whenever it has packets to transmit while the secondary (cognitive) node transmits its packets with probability p. Therefore, in this system, the secondary link is allowed to share the channel along with the primary link, in contrast to the traditional notion of cognitive radio, in which the secondary user is required to relinquish the channel as soon as the primary is detected. The analysis also takes into account the compound effects of multi-packet reception as well as of the relaying capability on the stability region of the network. We start by analyzing the non-cooperation case where nodes transmit their own packets to their respective destinations. We then extend the analysis to a system where the secondary node cooperatively relays some of the primary's packets. Specifically, in the cooperation case, the secondary node relays those packets that it receives successfully from the primary, but are not decoded properly by the primary destination. In such cognitive shared channels, a tradeoff arises in terms of activating the secondary along with the primary so that both transmissions may be successful, but with a lower probability, compared to the case of the secondary node staying idle when the primary user transmits. Results show the benefits of relaying for both the primary as well as the secondary nodes in terms of the stable-throughput region.

In this paper, we consider the problem of calculating the stability region and average delay of two user slotted ALOHA over a Gilbert-Elliott channel, where users have channel state information and adapt their transmission probabilities according to the channel state. Each channel has two states, namely, the `good' and `bad' states. In the `bad' state, the channel is assumed to be in deep fade and the transmission fails with probability one, while in the `good' state, there is some positive success probability. We calculate the stability region with and without Multipacket Reception capability as well as the average delay without MPR. Our results show that the stability region of the controlled S-ALOHA is always a superset of the stability region of uncontrolled S-ALOHA. Moreover, if the channel tends to be in the `bad' state for long proportion of time, then the stability region is a convex polygon strictly containing the TDMA stability region and the optimal transmission strategy is to transmit with probability one whenever the nodes have packets and it is shown that this strategy is delay optimal. On the other hand, if the channel tends to be in the `good' state more often, then the boundary of the stability region is characterized by a convex curve and is strict subset of the TDMA stability region. We also show that enhancing the physical layer by allowing MPR capability can significantly enhance the performance while simplifying the MAC Layer design by the lack of the need of scheduling under some conditions. Furthermore, it is shown that transmission control not only allows handling higher stable arrival rates but also leads to lower delay for the same arrival rate compared with ordinary S-ALOHA.

In this paper, we consider the random access of nodes having energy harvesting capability and a battery to store the harvested energy. Each node attempts to transmit the head-of-line packet in the queue if its battery is nonempty. The packet and energy arrivals into the queue and the battery are all modeled as a discrete-time stochastic process. The main contribution of this paper is the exact characterization of the stability region of the packet queues given energy harvesting rates for the two-node slotted ALOHA system. By stability, we refer the ability of a system to keep the queues in a bounded region, or more precisely, the existence of the limiting distribution for the joint queue length process. The analysis is non-trivial even for the two-node case because it involves the interaction between nodes of having both the packet queue and the battery. The result is obtained for both scenarios in which the capacity of batteries is infinite and also finite.

We consider the problem of MaxWeight scheduling in wireless multihop networks. This problem is known to be NP-hard. We propose a solution method, based on the branch and bound technique, which solves globally the MaxWeight scheduling problem with an optimality certificate. Efficient analytic bounding techniques are introduced as well.

In this work we examine the operation of a node relaying packets from a number of users to a destination node. We assume multi-packet reception capabilities for the relay and the destination node and that the relay node can transmit and receive at the same time, so the problem of self interference arises. The relay does not have packets of its own and the traffic at the source nodes are assumed saturated. The relay node stores a source packet that it receives successfully in its queue when the transmission to the destination node has failed. We obtain analytical expressions for the characteristics of the relay's queue (such as arrival and service rate), the stability condition and the average length of the queue as functions of the probabilities of transmissions, the self interference coefficient and the outage probabilities of the links. We study the impact of the relay node and the self interference coefficient on the throughput per user-source as well as the aggregate throughput.

This paper considers the scenario in which a set of nodes share a common channel. Some nodes have a rechargeable battery and the others are plugged to a reliable power supply and, thus, have no energy limitations. We consider two source-destination pairs and apply the concept of cognitive radio communication in sharing the common channel. Specifically, we give high-priority to the energy-constrained source-destination pair, i.e., primary pair, and low-priority to the pair which is free from such constraint, i.e., secondary pair. In contrast to the traditional notion of cognitive radio, in which the secondary transmitter is required to relinquish the channel as soon as the primary is detected, the secondary transmitter not only utilizes the idle slots of primary pair but also transmits along with the primary transmitter with probability p. This is possible because we consider the general multipacket reception model. Given the requirement on the primary pair's throughput, the probability p is chosen to maximize the secondary pair's throughput. To this end, we obtain two-dimensional maximum stable throughput region which describes the theoretical limit on rates that we can push into the network while maintaining the queues in the network to be stable. The result is obtained for both cases in which the capacity of the battery at the primary node is infinite and also finite.

We consider the problem of weighted sum-rate maximization (WSRMax) in wireless networks. This problem is known to be NP-hard and it plays a central role in resource allocation, link scheduling or in finding achievable rate regions for both singlecast and multicast networks. We propose a solution method, based on the branch and bound technique, which solves globally the WSRMax problem with an optimality certificate. Efficient bounding techniques are introduced as well.

In this paper, we consider the backpressure-based control for wireless multihop networks with time-correlated arrivals. The arrival process considered in this work is fairly general in the sense that it may exhibit long-range dependence depending on the asymptotic shape of the autocorrelation function. We first show that the original backpressure policy is still throughput-optimal even with correlated arrivals if the autocorrelation functions are monotonically decreasing. The resulting upper bound on average network delay is expressed in terms of the autocorrelation parameters. After that, we extend our model to include the case where the arrival rate vector is possibly outside the stability region and take the method of joint flow control and backpressure policy that is known to perform arbitrarily close to the utility-optimal throughput point with a corresponding tradeoff in average network delay. The effect of correlated arrivals appears again in the tradeoff in terms of the autocorrelation parameters.

In this work, we study the impact of a relay node to a network with a finite number of users-sources and a destination node. We assume that the users have saturated queues and the relay node does not have packets of its own; we have random access of the medium and the time is slotted. The relay node stores a source packet that it receives successfully in its queue when the transmission to the destination node has failed. The relay and the destination nodes have multi-packet reception capabilities. We obtain analytical equations for the characteristics of the relay's queue such as average queue length, stability conditions etc. We also study the throughput per user and the aggregate throughput for the network.

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.

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.

The problem of optimal scheduling of multicast traffic in time-varying wireless networks is studied in the framework of utility maximization. Since the wireless channel cannot be known exactly, only scheduling policies that take decisions based on a possibly inaccurate estimate of the wireless channel state are considered. A stationary, on-line, gradient-based scheduling and rate control policy is introduced which identifies at every decision instant the sources that should access the wireless medium along with their respective transmission rates. Furthermore, in the case that more than one optimal rate allocation is possible, the one that requires the minimum sum-power expenditure is selected by the policy. The optimality of the proposed policy among all policies that have access to the same estimate of the current wireless channel state is established through stochastic approximation arguments.

In the above titled paper (ibid., vol. 57, no. 7, pp. 4333-4343, July 2011), the following corrections are necessary.

We study transmission strategies in a multiple-source, multiple-destination wireless network. Each source transmits packets that are intended for a particular destination. However, a transmitted packet can cause interference at other destinations. Our primary performance measure is throughput, which we define to be the average number of packets that are successfully received per intended destination per time slot. The sources are first divided into groups, based on the intended destination of their packets. In our parallel method, each group operates according to its own local protocol (e.g., TDMA), concurrently with and independently of the other groups. Our results show the impact of transmission schedules, channel fading, receiver noise, and other-user interference on network performance. We then show that, for given channel statistics and topology configurations, the network performance can be significantly improved when the groups in the network coordinate their transmissions according to an optimal schedule. Further, in many cases, even the use of randomly generated parallel schedules can provide considerably higher performance than traditional TDMA.

In this paper, we examine the operation of a node relaying packets from a number of users to a destination node. We assume that the relay does not have packets of its own, the traffic from the users is saturated and we have random access of the medium with slotted time. We study the impact of the relay node on the throughput per user and the aggregate throughput for the group of users. We obtain analytical expressions for the arrival and service rate of the queue of the relay, the stability conditions and the average length of the queue. We quantify the above, analytically and through simulations, for different numbers of users and different transmission characteristics of the users and the relay and give the conditions under which there are significant advantages from the deployment of the relay.

We extend Information Theoretic analysis to time-slotted packet random access communication with bursty sources. A new channel coding approach for coding within each packet is proposed with built-in support for bursty sources phenomena, such as message underflow, and for random access mechanisms, such as packet collision detection. The coding approach does not require joint communication rate determination either between 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 within the region and reliable collision detection is supported for all rates outside the region. For random access communication over a discrete-time memoryless channel using a class of random coding schemes, it is shown that the maximum achievable rate region of the introduced coding approach equals the Shannon information rate region without a convex hull operation.

Due to the broadcast nature of the wireless medium, wireless networks are highly susceptible to jamming attacks. Such attacks are often studied in a game theoretic framework under the assumption of uninterrupted traffic subject to continuous jamming opportunities. Instead, we analyze the effect of dynamically changing traffic on jamming games for power controlled medium access. Random packet arrivals raise the possibility that the transmitter queues may be empty when jamming attacks start and thus waste the energy of jammers. We consider a non-cooperative game in which transmitters and jammers select their transmission power to balance the transmission cost subject to delay and energy constraints. We show that jammers incur a significant performance loss when they do not have knowledge of transmitter queue states. Dynamic traffic increases the immunity to jamming attacks and gives insights into defense mechanisms.

In this paper, we investigate the impact of network coding at the relay node on the stable throughput rate in multicasting cooperative wireless networks. The proposed protocol adopts Network-level cooperation, as in contrast to the traditional physical layer cooperative protocols; and in addition, it uses random linear network coding at the relay node. The traffic is assumed to be bursty and the relay node forwards its packets during the idle periods of the source which allows better utilization of channel resources. Our results show that cooperation leads to higher stable throughput rates than conventional retransmission policies. Moreover, the use of random linear network coding at the relay can further enhance the stable throughput with increasing network coding field size or increasing the number of packets over which encoding is performed.

In a wireless network, the problem of self interference arises whenever a node transmits and receives simultaneously in the same frequency band. So far only two extreme approaches to circumvent this problem were thoroughly investigated in the literature. The first one prevents any node to transmit and receive simultaneously which may lead to a too conservative design. The second one assumes perfect self interference cancelation which can be too optimistic since it ignores all possible technological limitations. To fill this gap, we provide a method to evaluate the network layer benefits from simultaneous transmission and reception when the network nodes employ self interference cancelation techniques with different degrees of accuracy. From a network design perspective, the provided method can be used to find the required level of accuracy for the self interference cancelation such that certain gains are achieved at the network layer. Numerical results suggest that the accuracy of existing self interference cancelation techniques can provide significant gains for certain network setups.

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.

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 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.

In this paper, we revisit the problem of determining the minimum-length schedule that satisfies certain traffic demands in a wireless network. Traditional approaches for the determination of minimum-length schedules are based on a collision channel model, in which neighboring transmissions cause destructive interference if and only if they are within the “interference region” of the receiving nodes. By contrast, we adopt here a more realistic model for the physical layer by requiring that a threshold be exceeded by the signal-to-interference-plus-noise ratio (SINR) for a transmission to be successful. We present a novel formulation of the problem that incorporates various power and rate adaptation schemes while seamlessly integrating the generation of “matchings” (i.e., sets of links that can be activated simultaneously) by taking into consideration the SINR constraints at the receivers. For the formulated problem, we propose a column-generation-based solution method and show that it theoretically converges to a globally optimal solution, with a potential advantage of not having to enumerate all the feasible matchings a priori. We also discuss the influence of power control, spatial reuse, and variable transmission rates on network performance. Furthermore, we include aspects of the routing problem and provide computational results for our proposed column-generation-based solution procedure.

We consider the problem of minimum-length scheduling of point-to-point links in a spatial TDMA (STDMA) based wireless network with Rayleigh fading of both desired and interference signals. The problem formulation integrates the activation of multiple sets of links in the network, while taking into account their explicit statistical variations. We assume uniform (fixed) transmission power at all nodes and propose an algorithm based on a column generation approach, which takes into consideration the signal-to-interference and noise ratio (SINR) constraints at the receivers in order to generate a link schedule that minimizes the schedule length. For the formulated problem, we show that this column generation based approach can converge to a globally optimal solution.

We consider a set of multicast sources, each multicasting a finite amount of data to its corresponding destinations. The objective is to minimize the time to deliver all traffic, i.e., to obtain schedules of minimum length. We consider time-varying wireless networks with imperfect side information at the sources. We model the minimum-length scheduling problem through partially observable stochastic shortest paths and provide an optimal solution. Due to the high complexity of computing the optimal solution, we finally provide a set of heuristics and illustrate their performance through numerical experiments.

In this paper, we investigate the effects of ldquonetwork-levelrdquo cooperation in a wireless three-node network with packet erasure links. Cooperation is achieved through the relaying of packets from the node farthest away from the destination by the intermediate node. We consider both scheduled access and random access, and compare the performance metrics of ldquostability regionrdquo and ldquothroughput regionrdquo. We observe that the throughput region depends on the priority choices at the relay node, and may or may not be equal to the stability region, which is shown to be independent of the priority choices. By contrast, in the non-cooperative random access system, the stability region and the throughput region are proved to be identical. Furthermore, if we apply network coding at the relay node, there is no improvement either in the stability region or in the throughput region over plain store-and-forward routing.

In this paper we study the problem of scheduling through rate and power control for multicast traffic. Our objective is to maximize the total user utility where user utilities are measured in terms of the long term average received rates. Considering the fact that accurate knowledge of the wireless channel conditions may not be always available, we focus on policies that take decisions based only on inaccurate estimates of the wireless channel state. We introduce an on-line, stationary scheduling and rate control policy. We establish its optimality among all policies with the same knowledge regarding the current channel state through stochastic approximation arguments.

We study the rate region of a simplified wireless network for a given degree of interference, considered as noise, and power constrains. The network nodes use a specific modulation scheme with a specific bit error rate and a constant bandwidth. We define the necessary conditions that maximize the system's sum rate for a 2-link interference channel and provide criteria under which simultaneous link operation outperforms timesharing. We identify critical points in the rate region where higher sum rates can be achieved in practical band limited channels at the expense of higher power expenditure. In case of light interference the relation between the maximum achieved rate and power is shown to be almost linear, but in case of strong interference, there is need for disproportionally high total power. Finally, for higher order modulations, we give the condition on the maximum individual transmission power for switching to the next higher modulation level in order to achieve higher aggregate rate.

Cooperative Techniques in Wireless Networking have been developed mostly at the physical layer and are based on the notion of relaying and space-time codes. However, it is possible to also use the idea of cooperation at the MAC and Network layers in very simple ways that provide further performance improvements. We focus on the objective of stable throughput region which requires that delays are finite when packet arrivals are random and demonstrate how simple relaying can increase the region of arrival rates that can be accommodated with finite delays. The reasons for the improvement are subtle and suggest far-reaching ossibilities regarding “stable capacity regions”. Also, we consider another form of cooperative routing for the case of sensor networks and again demonstrate how cooperation can be thought of in a much broader sense than the one that has prevailed until now.

We study the impact of user cooperation in wireless networks on improving the stable throughput and delay performance. Specifically, we consider a multiaccess system in which a set of source users generate packets to deliver to a common destination. A cooperation strategy is proposed at the protocol level, where users with a better channel to the destination have the option to relay packets from users that are farther afield. For the case of erasure channels with single-packet reception, we derive the stable throughput regions under different multiple access policies based on such cooperation strategy. Then we prove that the stable throughput region of the cooperative system strictly contains the stable throughput region achieved without cooperation. We also assess the delay performance, and show that cooperation significantly reduces the delay of all users. Finally, we characterize the effect of inter-user channel quality on performance, and show that the gain in performance through cooperation increases as the channel quality improves. Our work offers an innovative perspective by implementing cooperation at the network protocol level, while taking into consideration of fading and attenuation at the physical layer as well as the nature of traffic burstiness in a network.

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 this work we propose an efficient resource allocation algorithm for OFDMA based wireless systems supporting heterogeneous traffic. The proposed algorithm provides proportionally fairness to data users and short term rate guarantees to real-time users. Based on the QoS requirements, buffer occupancy and channel conditions, we propose a scheme for rate requirement determination for delay constrained sessions. Then we formulate and solve the proportional fair rate allocation problem subject to those rate requirements and power/bandwidth constraints. Simulations results show that the proposed algorithm provides significant improvement with respect to the benchmark algorithm.

We characterize the stability region of wireless, single-hop networks with time-varying imperfect channels. We define a joint scheduling and transmission rate control policy that maximizes the set of stable rates the network can support. Since obtaining the optimal policy is computationally complex, we confine our attention on the specific case of pure time division multiple access (TDMA) based scheduling of the transmitters one at a time, combined with rate control and we identify the exact conditions under which a pure TDMA scheduling and rate control approach maximizes the stability region of the network.

The problem of minimum cost in-network fusion of measurements, collected from distributed sensors via multihop routing is considered. A designated fusion center performs an optimal statistical-inference test on the correlated measurements, drawn from a Markov random field. Conditioned on the delivery of a sufficient statistic for inference to the fusion center, the structure of optimal routing and fusion is shown to be a Steiner tree on a transformed graph. This Steiner-tree reduction preserves the approximation ratio, which implies that any Sterner- tree approximation can be employed for minimum cost fusion with the same approximation ratio. The proposed fusion scheme involves routing packets of two types viz., raw measurements sent for local processing, and aggregates obtained on combining these processed values. The performance of heuristics for minimum cost fusion are evaluated through theory and simulations, showing a significant saving in routing costs, when compared to routing all the raw measurements to the fusion center.

The problem of distributed fusion for binary hypothesis testing in a multihop network is considered. The sensor measurements are spatially correlated according to a Markov random field (MRF) under both the hypotheses. A fusion scheme for detection involves selection and localized processing of a subset of sensor measurements, fusion of these processed values to form a sufficient statistic, and its delivery to the fusion center. The goal is to find a fusion scheme that achieves optimal linear tradeoff between the total routing costs and the resulting detection error exponent at the fusion center. The Neyman-Pearson error exponent, under a fixed type-I bound, is shown to be the limit of the normalized sum of the Kullback-Leibler distances (KLD) over the maximal cliques of the MRF under some convergence conditions. It is shown that optimal fusion reduces to a prize- collecting Steiner tree (PCST) with the approximation factor preserved when the cliques of the MRF are disjoint. The PCST is found over an expanded communication graph with virtual nodes added for each non-trivial maximal clique of the MRF and their KLD assigned as the node penalty.

We consider a problem of managing separate multicast sessions from a single transmitter. Each of K sessions has an associated packet stream, and a single transmitter must transmit these packet streams to a group of receivers. The multicast sessions are separate in the sense that each receiver only wants packets from one of the K streams. We will compare the maximum stable arrival rates that can be supported with and without using random linear coding across the K sessions. Intuitively, it seems that coding across sessions is not beneficial. Coding across sessions appears to introduce unnecessary additional delay since each receiver does not receive its next packet until it can decode the head-of-line packets from all K streams. However, we show that in many cases the maximum stable arrival rate that can be supported when coding across sessions is significantly greater than maximum stable arrival rate that can be supported when not coding across sessions. We provide a sufficient condition that indicates when coding across sessions is preferable. This condition is expressed in terms of the number of sessions, the number of receivers per session, and the reliability of the channels connecting the transmitter to the receivers.

In this work we perform a queueing analysis of an OFDMA-based and channel-aware resource allocation scheme. We estimate the service characteristics of the queues using extreme value theory and estimate the tail probability of queue size distribution using generating function approach. Based on numerical evaluations it is seen that our estimates are very close to the values obtained by simulations.

This paper shows that, under certain conditions, a wireless network can bemodeled by a directed configuration graph with possible hyperarc links if the transmission schedule is given. Assume single multicast session. The maximum achievable multicast throughput equals the max-flow min-cut bound of the configuration graph. An optimization framework is proposed to maximize the multicast throughput via iterative updates of the transmission schedule. It is demonstrated that the optimal multicast throughput can be obtained without exploring either a large number of hyperarc links or a large number of cuts, although efficient suboptimal algorithm is needed to avoid searching link combinations and to reduce the complexity further to polynomial in the number of nodes. It is also shown that, when the configuration graph has hyperarc links, the minimum cut can no longer be obtained using the well-known flow augmenting path algorithm. An alternative algorithm is proposed.

We investigate the problem of finding minimum-distortion policies for streaming delay-sensitive but distortion-tolerant data. We consider cross-layer approaches which exploit the coupling between presentation and transport layers. We make the natural assumption that the distortion function is convex and decreasing. We focus on a single source-destination pair and analytically find the optimum transmission policy when the transmission is done over an error-free channel. This optimum policy turns out to be independent of the exact form of the convex and decreasing distortion function. Then, for a packet-erasure channel, we analytically find the optimum open-loop transmission policy, which is also independent of the form of the convex distortion function. We then find computationally efficient closed-loop heuristic policies and show, through numerical evaluation, that they outperform the open-loop policy and have near optimal performance.

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.

We study power-based capture, under which a transmission is correctly decoded at the destination, even in the presence of other transmissions, if the received signal-to-interference-plus-noise ratio (SINR) exceeds a threshold bges0. Most previous studies have expressed throughput in terms of packets per slot as a function of b. However, since the value of b is a function of parameters such as data rate and the specified value of bit-error rate (BER), it is actually more appropriate to consider throughput in terms of bits per second per Hz at a specified value of BER. In this paper, we address the relationships between the throughput that can be achieved (using a specific modulation scheme and BER criterion) and the threshold value b.

We assess the practicality of random network coding by illuminating the issue of overhead and considering it in conjunction with increasingly long packets sent over the erasure channel. We show that the transmission of increasingly long packets, consisting of either of an increasing number of symbols per packet or an increasing symbol alphabet size, results in a data rate approaching zero over the erasure channel. This result is due to an erasure probability that increases with packet length. Numerical results for a particular modulation scheme demonstrate a data rate of approximately zero for a large, but finite-length packet. Our results suggest a reduction in the performance gains offered by random network coding.

In this paper, the detection of a correlated Gaussian field using a large multi-hop sensor network is investigated. A cooperative routing strategy is proposed by introducing a new link metric that characterizes the detection error exponent. Derived from the Chernoff information and Schweppe's likelihood recursion, this link metric captures the contribution of a given link to the decay rate of error probability and has the form of the capacity of a Gaussian channel with the sender transmitting the innovation of its measurement. For one-dimensional Gauss-Markov fields, the link metric can be represented explicitly as a function of the link length. Cooperative routing is achieved using the Kalman data aggregation and shortest path routing. Numerical simulations show that cooperative routing can be significantly more energy efficient than noncooperative routing for the same detection performance

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.

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.

A wireless network in which packets are broadcast to a group of receivers through use of a random access protocol is considered in this work. The relation to previous work on networks of interacting queues is discussed and subsequently, the stability and throughput regions of the system are analyzed and presented. A simple network of two source nodes and two destination nodes is considered first. The broadcast service process is analyzed assuming a channel that allows for packet capture and multipacket reception. It is proved that the stability and throughput regions coincide in this small network. The same problem for a network with N sources and M destinations is considered next. The channel model is simplified in that packet capture and multipacket reception is no longer permitted. Bounds on the stability region are developed using the concept of stability rank and the throughput region of the system is compared to the bounds. Our results show that as the number of destination nodes increases, the stability and throughput regions diminish. Additionally, a previous conjecture that the stability and throughput regions coincide for a network of arbitrarily many sources is supported for a broadcast scenario by the results presented in this work.

We investigate the optimum transmission strategy that minimizes the overall distortion for delay-sensitive but distortion-tolerant data. We consider a set of source symbols residing at the transmitter that are encoded into a set of packets using multiresolution source coding. Each packet has a given deadline after which its transmission will be useless. Since multiresolution source codes are being used, the packet lengths can be adjusted by dropping less significant bits in order to allow for the more significant bits of a larger number of packets to be transmitted before the deadline. We find the optimum number of bits that must be transmitted of every packet to minimize the overall distortion when transmissions are error-free. We show that for strictly convex distortion functions the solution is unique and independent of the form of the function, and extend this result to the case where transmitted bits can be affected by noise and find the optimum strategy that leads to the minimum expected distortion. Finally we look at the case where packets arrive according to a given deterministic arrival schedule and present an algorithm that finds the optimum transmission strategy.

Traditional voice and video-oriented networks such as the cellular and satellite networks are being increasingly used to carry data traffic. We endeavor to compare the downlink broadcast performance of the two architectures against each other on the basis of energy consumption, end-to-end delay and maximum stable throughput. The architectures are modelled as systems of Geo/G/1 queues. Queuing theory arguments and then sample-path based comparisons are used to show that the satellite architecture while being more energy-efficient has a higher delay and a lower maximum throughput than the cellular architecture.

In this paper, a new multiple access approach is proposed that takes into account the broadcast nature of the wireless channel. The new approach employs a relay to boost the system throughput. This approach is based on a new idea in which the relay utilizes the empty time slots available in a TDMA frame. The relay stores the packets that failed transmissions previous time slots. At each time slot, the relay listens to the channel and retransmits the packet at the head of its queue if the channel is free. This will better utilize the channel resources and will introduce on-demand spatial diversity into the network. Two different protocols are proposed to implement this new multiple-access scheme. The stability criteria of the associated queueing systems are studied and analytical expressions for the maximum stable throughput are provided for the symmetrical users case. Numerical results indicate a significant increase in the maximum stable throughput by using the new multiple-access protocol over pure TDMA.

This is our first step towards a holistic investigation of the minimum energy for wireless sensor network (WSN) to perform a specific function. We consider wireless sensor networks that perform an event detection function. Each sensor node will repetitively collect a 1-bit information regarding whether the event occurs or not in its neighborhood. A fusion center will make the decision on whether the event occurs based on the information provided by individual sensor nodes. Traditionally, a centralized scheme requires each sensor node to forward all its observations to the fusion center, which results in large energy in communication. A distributed scheme, on the other hand, allows each sensor node to make its own decision and then send out only its 1-bit decision. This reduces communication energy at the cost of increased processing energy and reduced detection accuracy.We propose a hybrid energy-driven scheme where each sensor node sends out its 1-bit decision if that decision exceeds a pre-determined detection accuracy threshold, and sends out all its observations otherwise. This scheme provides WSN designers the flexibility to balance detection accuracy, sensor density, and energy consumption. We develop the optimal decision rules for this scheme. We also propose methods to calculate the detection accuracy threshold for individual sensor node to guarantee the overall detection accuracy at the fusion center. The simulation results show that the hybrid scheme consumes significantly less energy than both centralized and distributed schemes to achieve the same detection accuracy.

This paper studies multiple access channels with additive Gaussian noise 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 multiple access (TDMA) scheme and the parallel multiple access scheme with single user decoding (PMAS). We consider the situation when the receiver has multiple receive antennas while each transmitter only has single antenna. We show that, due to TDMA's inefficiency in exploiting the multiuser multiplex gain, the relative spectral efficiency of PMAS over TDMA grows drastically as the number of receive antennas increase. The relative spectral efficiency of PMAS over the optimal scheme is approximately 1/2, irrespective of the number of receive antennas. Since the simplicities of PMAS and TDMA are similar, our results suggest that PMAS is a better alternative to TDMA for multiple access system in the low SNR regime

Under power-based capture, a transmission is correctly decoded at the destination, even in the presence of other transmissions, if the received signal-to-interference-plus-noise ratio (SINR) exceeds a threshold b ges 0. Studies on capture are often limited to the case b ges 1. In this paper, we study capture for systems with arbitrary b ges 0, i.e., our formulation includes both wide-band (0 les 1) and narrow-band (b > 1) systems. We also point out some ambiguity from the existing literature on capture analysis

In this paper, we compare the effects of the saturated and possibly emptying packet queues on wireless network coding (or plain routing as a special case) in a simple tandem network. We consider scheduled or random access with omnidirectional transmissions and assume the classical collision channel model without simultaneous transmission and reception by any node. For the case of multiple source nodes, we evaluate the multicast throughput rates jointly achievable by different source-destination pairs under the separate assumptions of network coding and plain routing only. Particularly, we specify the throughput region for saturated queues and stability region for possibly emptying queues. We also evaluate the fundamental trade-offs among the performance objectives of throughput and transmission and processing energy costs. Finally, we extend the analysis to non-cooperative network operation with selfish nodes competing for limited network resources. We point at the inefficiency of competitive medium access control and network coding (or plain routing) decisions at individual nodes, and introduce a pricing-based cooperation stimulation mechanism to improve the throughput and energy efficiency performance

The capacity region of an asynchronous system with two sources and two receivers is analyzed. The capacity region is first derived for a general discrete memoryless channel. The result is then applied to a random access system in which sources may either transmit information-bearing symbols or idle (empty) symbols in each time slot. The capacity region for this random access system is compared to the corresponding queueing stability region and it is demonstrated that the two regions do not coincide. This comparison is the primary contribution of our work; our result is a deviation from all previous results on the relation between information-theoretic capacity and queueing stability for random access systems

In this paper we consider the signal to interference plus noise ratio (SINR) criterion for connectivity, as a basis for a wireless ad hoc network and present a detailed study for the power performance of such a network. For this, we examine how typical wireless network parameters such as, network density and environment variables such as the path loss exponent can affect the power assigned to the transmitters and the resulting connectivity between specified nodes. We also present structural properties for the minimum power assignment. We finally examine at what cost malicious jamming nodes can harm the robustness of the network and asses whether the network can mitigate these jamming attempts by only adapting its transmission powers

We consider the problem of optimally controlling transmission power in a time-slotted wireless broadcast network. Fixed-length packets and AWGN channels are considered, and a simple ARQ scheme (Send-and-Wait) is used for error control. Packets are retransmitted until a minimum QoS requirement is met for each packet. Transmission powers are chosen from a finite set depending on the number of nodes that have received the packet successfully. The goal is to minimize the total energy expended for each successful packet transmission. The system is studied when the transmitter chooses between two distinct powers, and the results are then extended to multiple powers. It is observed that the optimal policy is always of the separation type. Also, the effect of varying the QoS requirement on the energy and service time is studied.

For original paper by Zorzi and Rao, see IEEE J. Sel. Areas Commun., vol.12, no.8, p.1289-98 (1994 October)

The problem of determining what links can be simultaneously activated in a wireless network such that a signal-to-interference-and-noise (SINR) constraint is satisfied at all receivers is considered. The term "feasible matching" is introduced to describe a set of (transmitter, receiver) pairs for which there exists some set of transmit powers which can simultaneously meet the SINR requirements at the receivers. Given disjoint equally sized sets of transmitters and receivers, it is shown that when the SINR requirement at the receivers is greater than 1, no more than one feasible matching between the transmitters and the receivers exists. Sufficient conditions are provided under which certain broad classes of matchings in a network are guaranteed to be feasible; for example all matchings involving k or fewer links. The application of these results to ad hoc wireless networks and to scheduling is discussed.

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.

This paper extends our earlier results. We assume that the receiver has the capability of capturing multiple packets so long as the signal-to-interference-plus-noise ratio (SINR) of each packet is above a designed threshold T throughout its transmission period. We prove that, compared with a multiple-power-level system, the single-power-level system in which all nodes transmit at the maximum allowable power level achieves optimal throughput, under a condition that T exceeds the value 3.33. Given a minimum throughput requirement, under the same condition on T, the single-power-level system also achieves the maximum average packet capture probability as well as the optimum energy usage efficiency. If the multiple-power-level systems are constrained such that higher power levels always have shorter packet lengths, then the above results hold for T greater than 2.

This paper studies finite-terminal random multiple access over a standard multi-packet reception (MPR) channel. In the first part of the paper, we show that if the MPR channel is standard, the throughput region of random multiple access is co-ordinate convex. We then study the information capacity region of multiple access without code synchronization and feedback. We show that the asymptotic capacity region is identical to the throughput region. In the second part of the paper, we study the stability region of ALOHA multiple access. For a class of packet arrival distributions, we show that the stationary distribution of the queues possesses the positive and strong positive correlation properties; and this consequently gives an outer bound to the stability region. We also show that if a conjectured "sensitivity monotonicity" property can be shown for the stationary distribution of the queues, then the equivalence between the closure of the stability region and the throughput region follows as a direct consequence, irrespective of the packet arrival distributions

In this paper, we address the joint design and distributed implementation of medium access control (MAC) and network coding in wireless ad hoc networks. We consider a slotted wireless network with links modeled as classical collision channels. We assume omnidirectional packet transmissions and do not allow simultaneous transmission and reception by any node. These wireless network properties demand a new formulation of time-varying network coding with additional constraints that reflect the strong interactions with the underlying MAC operation. First, we outline how to construct network coding over a predetermined set of wireless network realizations with conflict-free transmission schedules. The wireless network realizations are separately activated using a time division mechanism and the network flows are chosen to optimize the performance measures (such as stable throughput or average energy costs) through wireless network coding. Next, we follow an alternative approach of joint wireless network coding and link scheduling with a distributed implementation. The analysis is based on decomposing wireless networks into subtrees and applying graph coloring on the simplified subtree network representations to derive the wireless network codes that are further converted to the conflict-free sets of transmission schedules. Finally, we extend network coding to operate with arbitrary single-receiver MAC protocols within each receiver's area

We introduce and study the problem of broadcast stability in a network where nodes utilize the ALOHA protocol to gain random access to the channel. We make use of the dominating systems argument used in previous works and also develop a novel method for finding the region of stable arrival rates of packets. The stability region is obtained by analyzing the broadcast service process for a channel with multipacket reception. Our results exhibit the effect of probabilistic reception and multipacket reception on the broadcast stability region. We also show that the broadcast stability region is contained within the stability region for unicast transmission. Our work is applicable to the broadcast transmission that underlies communication in many wireless networks, including multihop networks. In addition, our new method for finding the stability region may be applicable to previously unsolved problems, including the stability region for arbitrarily many sources and destinations

Most studies of wireless random-access systems have addressed single-destination networks (e.g., an isolated base station in a cellular network). Here, we consider networks with many users and multiple destinations, where omnidirectional antennas are used for communication over a common channel, and transmissions intended for one destination can interfere with those intended for others. Our previous work on such networks assumed a simplified model for the physical layer, under which communication and interference ranges were characterized by fixed values and capture was not possible. In this paper, we use a more-realistic threshold model for the physical layer, under which a packet is successfully received if its received signal strength is sufficiently greater than the combined power of all other packets transmitted in the same slot. We use simulation to evaluate the maximum throughput that can be achieved by Slotted Aloha for multiple-destination networks. Throughput performance results demonstrate the impact of the degree of overlap of these clusters, as well as the impact of capture

We investigate a covert channel implemented on top of MAC protocols that are based on splitting algorithms. Covert information is embedded in nodes' splitting decisions. The covert channel can operate in three modes. The conservative mode is the safest in the sense that use of the covert channel is undetectable. The aggressive mode generates best throughput, but is more vulnerable to detection. A strategic mode is also available which allows the covert users to make a tradeoff between detectability and covert capacity. Simulation shows that the covert throughput ranges from 0 to as high as 0.3 bits per slot, depending on various parameters. It is easy to implement and very difficult to detect.

In the presence of channel fluctuation, rate adaptation is one way to maintain the quality of the link at a desired level. This is especially important in ad hoc wireless networks, where temporary channel fluctuations might create frequent needs for rerouting that would result in severe overhead and adversely affect the performance. We study an unusual method of passive rate adaptation in which some bits are dropped at the receiver end of a link. The symbol-error probability decreases as some bits are dropped. In terms of the distortion for a realtime analog signal, the tradeoff is between more reliable detection of fewer bits and less reliable detection of more bits. Our scheme achieves smaller distortion for a certain region of signal-to-noise ratio (SNR) values when compared with the original scheme without rate adaptation. Two examples, uniformly spaced, uncoded pulse amplitude modulation and quadrature amplitude modulation, are studied and compared for both a Gaussian channel and a Rayleigh fading channel. We conclude that our scheme is more suitable to use in a fading channel than in a Gaussian channel. We also verify that our scheme has a larger applicable region of SNR values when a nonuniform constellation is used, since the important bits are given additional protection.

In an energy-efficient wireless communication system, transmit powers are minimized subject to predetermined signal-to-interference ratio (SIR) requirements. In this paper, a general framework for distributed stochastic power control (PC) algorithms is proposed, where the transmit powers are updated based on stochastic approximations. The proposed algorithms are distributed in the sense that no global information is needed in the power updates. Interference to each user is estimated locally via noisy observations. Two types of stochastic PC algorithms are studied: standard stochastic PC algorithms where the interference estimator is unbiased, and quasi-standard stochastic PC algorithms where the interference estimator is biased. The conditions under which the stochastic PC algorithms converge to the unique optimal solution are identified. Corresponding to two classes of iteration step-size sequences, two types of convergence, the probability one convergence and convergence in probability, are shown for both algorithms based on recent results in the stochastic approximation literature. Based on the theoretical results, some well-known stochastic PC algorithms, such as stochastic PC with matched filter receivers, and joint stochastic PC with blind minimum mean-squared error (MMSE) interference suppression, are revisited; several new stochastic PC algorithms, such as stochastic PC with minimum-power base-station assignment, and stochastic PC with limited diversity, are proposed. It is shown that these algorithms fall into either the standard or the quasi-standard stochastic PC framework. Simulation results are given to illustrate the performance of the proposed algorithms in practical systems.

The optimal signature sequences that maximize the sum capacity of a direct sequence code-division multiple-access (CDMA) system are characterized in the general case of symbol delay profile and user power constraints. It is shown that the optimal sum capacity of the symbol asynchronous system equals that of the symbol synchronous system with the same user power constraints. With the optimal signature sequence set, the maximum sum capacity is achieved with white Gaussian input signals. The existence of the optimal signature sequence set is proved by the proposal of an explicit construction method for arbitrary user delay profiles and power constraints.

The optimal signature sequences that maximize the sum capacity of a direct sequence CDMA system are characterized in the general case of symbol delay profile and user power constraints. It is shown that the optimal sum capacity of the symbol asynchronous system equals that of the symbol synchronous system with the same user power constraints. With the optimal signature sequence set, the maximum sum capacity is achieved with white Gaussian input signals. The existence of the optimal signature sequence set is proved by the proposal of an explicit construction method for arbitrary user delay profiles and power constraints.

Scheduling is important in wireless networks for two reasons. First, a schedule of minimum length provides an upper bound on the network's throughput. Second, scheduling is necessary to avoid collisions. Collisions cost energy, making them undesirable in wireless networks whose nodes have limited energy. To produce good link schedules we need large activation sets, sets of links, which can be used concurrently. We call these "feasible matchings". The larger a matching, greater is the parallelism, and the shorter the schedule. In this work, we prove theorems that show how to infer whether certain sets of links are feasible or not, without actually computing eigenvalues.

We rediscover the value of scheduled access through a detailed foray into the questions of throughput and energy consumption for MAC protocols in ad hoc wireless networks, where the optimal channel access scheduling is NP-complete. We propose a two-layered time-division heuristic of receiver activation and Group TDMA as polynomial-time solutions to throughput and energy-efficient link scheduling and resource allocation in networks with dynamically changing transmitter-receiver pairs.

In this paper, we consider a synchronous code-division multiple-access (CDMA) system with a multiuser receiver. All users are assumed to have symmetric signature sequences, but the presence of a subset of the users is unknown to the receiver. We first calculate the signal-to-interference ratio (SIR) in this environment for the matched-filter receiver, the decorrelating receiver, and the linear minimum mean-square error (MMSE) detector. We then identify the user capacity for a single-class system, and the effective bandwidth for a multiple-class system. The result is compared to the case of random sequences and of optimum sequences. For symmetric sequences, the effective bandwidth cannot be expressed by a scalar as in , because two constraints have to be satisfied simultaneously to satisfy the SIR requirement. We introduce a two-dimensional (2-D) vector notion of effective bandwidth with and without unknown users. For both the decorrelator and the MMSE detector, the user capacity is 1 when all users are known to the receivers and is reduced to (1-N/L) when N users are unknown (with L the processing gain). The performance of these three linear detectors, with and without unknown users, is compared.

In this paper, we introduce a cross-layer design framework to the multiple access problem in contention-based wireless ad hoc networks. The motivation for this study is twofold, limiting multiuser interference to increase single-hop throughput and reducing power consumption to prolong battery life. We focus on next neighbor transmissions where nodes are required to send information packets to their respective receivers subject to a constraint on the signal-to-interference-and-noise ratio. The multiple access problem is solved via two alternating phases, namely scheduling and power control. The scheduling algorithm is essential to coordinate the transmissions of independent users in order to eliminate strong levels of interference (e.g., self-interference) that cannot be overcome by power control. On the other hand, power control is executed in a distributed fashion to determine the admissible power vector, if one exists, that can be used by the scheduled users to satisfy their single-hop transmission requirements. This is done for two types of networks, namely time-division multiple-access (TDMA) and TDMA/code-division multiple-access wireless ad hoc networks.

In this paper, we address the collision resolution (CR) problem from an energy-efficiency point of view and develop a residual-energy-based collision resolution algorithm (CRA) for energy-limited terminals. In this algorithm, which is based on tree-splitting, packets involved in a collision are partitioned into subsets according to the amount of residual battery energy left at the corresponding terminals, and retransmissions are scheduled according to a tree structure. We extend the proposed energy-based CR approach to cases without hard energy constraints but, rather, with energy-efficiency objectives. The algorithm then utilizes the distance from the receiver as the criterion. We evaluate the proposed algorithm via simulation for communication systems ranging from simple single-cell classical collision channel models to general multihop wireless ad-hoc networks.

In this work we address the problem of multicasting connectionless (packet oriented) traffic in energy and transceiver-limited ad hoc wireless networks. We first investigate the novel trade-offs caused by connectionless traffic as opposed to session-oriented traffic. Then we develop a new multicasting heuristic that is based on a minimum incremental cost logic. We also discuss the medium access (multicast scheduling) issues and propose a multicast scheduling scheme that works together with the proposed multicasting algorithm. Simulation results show that considerable improvement in energy and delay performance can be obtained by the proposed algorithms when compared with the ones that are originally designed for session based traffic.

The problem of jointly controlling the data rates and transmit powers of users, so as to maximize throughput in cellular direct-sequence code-division multiple-access (CDMA) networks is addressed. The multicode (MC)-CDMA system, where the processing gain of each code is fixed and high-rate users use multiple codes for transmission, and the variable gain (VG)-CDMA architectures are considered. The throughout maximization problem is formulated as a classical optimization problem, modeling the constraints arising from the data rate requirements and power budgets. Optimal strategies to maximize throughput in both systems are derived. While the MC-CDMA system has a simple optimal rate-power allocation algorithm, the VG-CDMA system has a more complex solution.

In this paper we introduce power control as a solution to the multiple access problem in contention-based wireless ad-hoc networks. The motivation for this study is two fold, limiting multi-user interference to increase single-hop throughput, and reducing power consumption to increase battery life. We focus on next neighbor transmissions where nodes are required to send information packets to their respective receivers subject to a constraint on the signal-to-interference-and-noise ratio. The multiple access problem is solved via two alternating phases, namely scheduling and power control. The scheduling algorithm is essential to coordinate the transmissions of independent users in order to eliminate strong interference (e.g. self-interference) that can not be overcome by power control. On the other hand, power control is executed in a distributed fashion to determine the admissible power vector, if one exists, that can be used by the scheduled users to satisfy their single-hop transmission requirements. This is done for two types of networks, namely TDMA and TDMA/CDMA wireless ad-hoc networks.

We consider ad hoc wireless networks that use directional antennas and have limited energy resources. The performance objectives of such networks depend largely on the application. However, a robust performance measure is the total traffic volume that the network can deliver when all nodes are equipped with a finite and non-renewable amount of energy. We show that the network's lifetime can be extended significantly by incorporating a simple measure of a node's residual energy into the node's cost function. To explore quantitatively the advantage offered by the use of directional antennas over the case of omnidirectional antennas, we consider the case of connection-oriented multicast traffic. Building upon our prior work on multicasting algorithms, we introduce two protocols that exploit the use of directional antennas and evaluate their performance. We observe significant improvement with respect to the omnidirectional case.

We study the effects of limited bandwidth resources in the development of energy-efficient routing algorithms for connection-oriented traffic in fixed wireless multihop networks. A frequency division multiple access scheme is considered, in which nodes must schedule their transmissions by selecting frequency channels from a limited set in an interference free fashion. In our earlier work, we had developed a set of algorithms for determining end-to-end unicast paths based on link metrics. We argue that in order to address the effects of limited frequency resources, such algorithms must be coupled with the channel allocation mechanism for providing conflict free frequency assignments over selected routing paths. To these ends, we propose a set of link metrics for selecting candidate routing paths and a set of heuristics for frequency allocation and evaluate their performance using our detailed simulation model.

We take initial steps toward developing energy-efficient broadcast algorithms for ad hoc wireless networks that operate under changing connectivity conditions. Such algorithms need to be distributed. To be distributed these algorithms need to probe neighboring nodes to determine possible connectivities at different power levels. We proceed toward this goal by revisiting and modifying previously obtained broadcast algorithms that were centralized and in which the exact levels of minimally necessary RF power to reach neighboring nodes could be determined. Instead, we now constrain RF power to take values from a finite discrete set, and evaluate the impact on algorithm performance. We then discuss further modifications for distributed operation.

In the above paper, 1 the proof of the theorem in Section III requires a clarification. In the construction of the augmented graph, at the very beginning of the proof, we add one new node for every link ( ) of the original graph and then connect this node to nodes and , respectively, of the original graph plus to all other nodes thus added. In fact, if this is how the augmented graph is constructed, the argument of the proof is inadequate. To make the argument stand as presented, we need to slightly modify the definition of the augmented graph by requiring that each new node added (in correspondence to a link of the original graph) must be connected not only to nodes and of the original graph, but to all nodes of the original graph. With this modification every step of the presented proof is valid. That there was an inadequacy in our construction was pointed out by K. Someya and H. Matsuno of the Mitsubishi Space Software Corporation, whom we thank for their diligent reading of our paper. They pointed out a counterexample, as far as the properties of the augments graph is concerned, if the definition of the augmented graph was as mentioned in the paper. By making the simple aforementioned modification, we take care of the problem. The main result of our paper regarding the NP completeness of the scheduling problem was never in dispute. In fact there are several alternative proofs that have been provided over the years, including one suggested by Someya and Matsuno. Nonetheless, the clarification in this note is necessary to provide rigorous support for the argument used in our proof.

Multiple-power-level ALOHA has been proposed to take advantage of the capture phenomenon in order to improve the throughput of a multiple random access system. We study the effect of the use of multiple transmission power levels and of the corresponding packet lengths on the system throughput and energy efficiency. We prove that the single-power-level system in which all transmit at the maximum allowable power level achieves both optimal throughput and energy usage efficiency under a condition on the decodability threshold value.

In this paper, we address the issue of performance of linear multiuser detectors for a multicasting application in an ad hoc wireless network. Using a code-division multiple-access (CDMA) framework, we demonstrate how capacity results for multiuser detectors can be adapted to do session admission control for the multicasting problem. We then develop a multicast routing algorithm for ad hoc wireless networks. Using the session admission control mechanism and the multicast routing algorithm, we evaluate the performance of three different linear multiuser detectors for the multicasting application.

We consider ad hoc wireless networks that use directional antennas and have limited energy resources. To explore quantitatively the advantage offered by the use of directional antennas over the case of omnidirectional antennas, we consider the case of connection-oriented multicast traffic. Building upon our prior work on multicasting algorithms, we introduce two protocols that exploit the use of directional antennas and evaluate their performance, We observe significant improvement with respect to the omnidirectional case, in terms of both energy efficiency and network lifetime. Additionally, we show that further substantial increase in the network's lifetime can be achieved by incorporating a simple measure of a node's residual energy into the node's cost function.

Abstract The genesis and growth of the field of ad hoc wireless networks is put into perspective through a brief review of historical highlights and through a focused discussion of some of the fundamental traits of such networks. Copyright © 2002 John Wiley & Sons, Ltd.

Suppose that the description of a stochastic process needs to be sent to a destination through a communication network. Also assume there is a risk that the description may be lost. A technique to reduce the risk of losing such descriptions is by sending two (or more) descriptions and hoping that in this way at least one of the descriptions will get through. This problem is referred to as multiple description coding (MDC) and was first introduced by Gersho, Witsenhausen, Wolf, Wyner, Ziv and Ozarow (1979). So far, the main focus of research on this subject has been on the achievable rate-distortion functions and the related structural design issues for such encoders and decoders. Little effort has focused on the performance of such coding schemes in simple communication networks and relation of the overall distortion with respect to some network parameter such as congestion. In this paper, a double description coding (DDC) system in a simple network represented by a set of parallel queues is studied. Comparison is made with a single description coding system and it is shown that DDC significantly improves the overall average end-to-end distortion at high network loading.

In this paper, we provide a graph-based characterization of the set of indecomposable sequences that are useful in the computation of an upper bound to error probability of maximum-likelihood (ML) detection in code-division multiple-access (CDMA) multiuser systems. We apply this characterization to a K-user symmetric system and to a two-user two-rate system. It leads to a precise calculation of the bound which is then compared to the performance of a decorrelator.

The wireless networking environment presents formidable challenges to the study of broadcasting and multicasting problems. After addressing the characteristics of wireless networks that distinguish them from wired networks, we introduce and evaluate algorithms for tree construction in infrastructureless, all-wireless applications. The performance metric used to evaluate broadcast and multicast trees is energy-efficiency. We develop the broadcast incremental power algorithm, and adapt it to multicast operation as well. This algorithm exploits the broadcast nature of the wireless communication environment, and addresses the need for energy-efficient operation. We demonstrate that our algorithm provides better performance than algorithms that have been developed for the link-based, wired environment.

We address the problem of routing connection-oriented traffic in wireless ad-hoc networks under minimum energy expenditures. We outline the tradeoffs that arise by the flexibility to transmit at different power levels and propose distributed algorithms on how to select connection paths relying only on local information. We propose a set of link metrics that capture network parameters and use them for the computation of shortest paths in static topologies. The performance is measured by the call blocking probability and average consumed energy. The algorithms are evaluated by a detailed simulation model and their key characteristics are discussed.

We consider multihop packet radio networks that need to determine broadcasting transmission schedules. To provide an opportunity for increasing system throughput, it is assumed that multiple radio channels are available for exchanging messages. This multiple reception capacity of each node presents a challenging problem for channel access protocols. Variations of this problem under some restrictive assumptions have been investigated in the literature. In this paper a time-frequency scheduling algorithm is proposed that guarantees a collision-free broadcast traffic flow and ensures high slot utilization. An efficient distributed scheduling algorithm is also described for such multi-channel multi-hop packet radio networks.

Article Power control for link quality protection in cellular DS-CDMA networks with integrated (packet and circuit) services Share on Authors: Deepak Ayyagari 40 Sylvan Rd., GTE Laboratories Inc., Waltham, Ma. 40 Sylvan Rd., GTE Laboratories Inc., Waltham, Ma.View Profile , Anthony Ephremides Dept. of Electrical Engg., Institute for Systems Research, University of Maryland, College park, Md. Dept. of Electrical Engg., Institute for Systems Research, University of Maryland, College park, Md.View Profile Authors Info & Claims MobiCom '99: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networkingAugust 1999 Pages 96–101https://doi.org/10.1145/313451.313495Online:01 August 1999Publication History 8citation344DownloadsMetricsTotal Citations8Total Downloads344Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The problem of jointly controlling the data rates and transmit powers of users, so as to maximize throughput in cellular DS-CDMA networks is addressed. The multicode (MC-CDMA) system, where the processing gain of each code is fixed and high rate users use multiple codes for transmission, and the variable gain (VG-CDMA) architectures are considered. The throughout maximization problem is formulated as a classical optimization problem, modeling the constraints arising from the data rate requirements and power budgets. Optimal strategies to maximize throughput in both systems are derived. While the MC-CDMA system has a simple optimal rate-power allocation algorithm, the VG-CDMA system has a more complex solution.

We study the power consumption of several multiuser detectors in the power controlled DS-CDMA system. The matched-filter detector, linear MMSE detector, successive interference cancellation (SIC), and LMMSE-SIC are considered. Closed form analysis and numerical results show that by using a multiuser detector, system power consumption can significantly be reduced and the network capacity be increased.

This paper analyzes the capacity of a multicode direct sequence-code division multiple access (DS-CDMA) cellular architecture supporting integrated (voice and data) traffic. The capacity estimate (on the uplink) is the number of voice users and data users, at different data rates, that the system can support with quality-of-service (QoS) guarantees (frame error rates (FER), outage probability). This estimate is based on an interference analysis that considers both perfect and imperfect power control, different user distributions in the cell, and the coverage trade-off resulting from hand-set power limitations. Localized interference from high speed data (HSD) users, combined with the effects of power control, adversely impacts voice capacity. The analysis investigates the effect of two important factors on capacity: (1) received power levels for the different classes of users and (2) data user activity. The results obtained are useful in designing power allocation and burst-level admission control strategies to optimize the capacity.

We consider the extension of a cellular system by means of satellite channels. Specifically, we consider an area covered by a number of cells, that is also covered by a number of spot beams. We consider connection-oriented service, and call durations are assumed to be exponentially distributed. Also, users are mobile and, as such, they may cross cell and/or spot-beam boundaries, thus necessitating handoffs. We incorporate the possibility of call dropping due to unsuccessful handoff attempts, in addition to satellite propagation delays along with the probability of new call blocking, and formulate a specific multifaceted cost function that must be ultimately minimized. The minimization is to be carried out by choosing: (1) the optimal partitioning of channels between the cellular and the satellite systems, and (ii) the call admission and assignment policy, subject to the constraints of a demand vector that consists of an exogenous (new-call) generation process and an internal (handoff-based) process that results from the mobility model. Two subproblems of this complex optimization problem are solved by means of numerical techniques and by means of so-called standard clock simulation techniques. In this solution method, we employ the ordinal optimization approach which focuses on preserving the performance rank, rather than the performance prediction of the different control policies. We find that the "double" coverage, through both cellular and satellite resources, results in substantial improvement over pure terrestrial or pure satellite systems for parameter values that correspond to practical environments.

We revisit the stability problem of systems consisting of N buffered terminals accessing a common receiver over the collision channel by means of the standard ALOHA protocol. We find that in the slotted ALOHA system queues have "instability rank" based on their individual average arrival rates and transmission probabilities. If a queue is stable, then the queue with lower instability rank is stable as well. The instability rank is used to intelligently set up the dominant systems. And the stability inner and outer bounds can be found by bounding the idle probability of some queues in the dominant system. Through analyzing those dominant systems one by one, we are able to obtain inner and outer bounds for stability. These bounds are tighter than the known ones although they still fail to identify the exact stability region for cases of N>2. The methodology used is new and holds promise for successfully addressing other similar stability problems.

We develop and simulate a distributed dynamic routing algorithm, capable of identifying paths for establishing and maintaining connection-oriented sessions in wireless communication networks which are characterized by frequent and unpredictable changes in connectivity. Our approach is a new protocol which runs atop a protocol for connectionless datagram service and establishes circuit routes for initial connection based on a mechanism of short packets exchange and on distributed information about availability of network resources. We explore the idea of predictive rerouting in that the algorithm takes advantage of the possibility to convert a connectivity change into a "soft" failure to maintain and re-route on-going sessions. The algorithm is simulated in Opnet and results show that the "softening" of link failures can improve the performance as captured in terms of new call blocking probability and probability of forced termination of on-going sessions.

Information theory has not yet had a direct impact on networking, although there are similarities in concepts and methodologies that have consistently attracted the attention of researchers from both fields. In this paper, we review several topics that are related to communication networks and that have an information-theoretic flavor, including multiaccess protocols, timing channels, effective bandwidth of bursty data sources, deterministic constraints on datastreams, queuing theory, and switching networks.

We identify a class of optimum multiuser detection problems which can be solved with polynomial complexity in the number of users. The identification is based on transforming a quadratic 0-1 programming problem into an equivalent problem in graph theory. For a synchronous direct sequence code-division multiple access (CDMA) system, the result translates to designing a set of pseudorandom codes with the property that the cross correlation between every pair of codes in the set over one symbol period is nonpositive. We give two sets of codes with good correlation properties that fall within this class. Finally, we derive a bound on the cardinality of a signal set in an n-dimensional space, having the property that the cross correlation between every pair of signals in the set is nonpositive.

Summary form only given, as follows. From cellular networks to personal communications and from satellite systems to military and commercial multihop networks, the technology of mobile wireless networking is creating yet another revolution in the Information Age. In this article the distinguishing features of wireless networks are reviewed and the main challenges and roadblocks in their design are identified. In addition it is shown how some prevailing viewpoints (e.g. the view of some in the Internet community that wireless is just another transmission technology or the view of some communication theorists that the only issue is to overcome the wireless channel impairments between two points) represent misconceptions of the unique environment of wireless networking. Finally some specific examples of design problems in wireless networks are reviewed.

"Multicasting" refers to the transmission of the same information to several destinations. We present a loop-free, distributed multicast routing protocol for wireless networks that consist of an arbitrarily large number of nodes, each of which is mobile in an unpredictable manner. Most existing multicast protocols have been developed for non-wireless, stationary networks in which there is an abundance of bandwidth and where intended destinations initiate their connection to the multicast tree. In mobile wireless networks of the future, bandwidth may be limited if not scarce, and in addition to destination initiated connections, there will be purely source-initiated multicasts. We propose a combined multicast routing and resource reservation protocol, which is source-initiated and which uses dynamic frequency allocation to establish, and maintain, connections to desired destinations in the randomly varying topology of ad-hoc wireless networks. Power control is applied to tradeoff between routing delays and frequency reuse factor.

Satellite systems have been used recently to extend the geographical coverage of cellular service and to off-load congestion within the area covered by the cellular network. An integrated satellite-cellular network scenario is considered. An analytical model for a 1-dimensional (e.g. highway) cellular system that is augmented by multiple spot beams is presented and the call blocking probability for this system is computed. A simulation program has been developed and used to study the call blocking probability and handoff blocking rate in a planar cellular network with spot beam support. The effect of different hierarchical positions of the satellite system and the cellular system in the integrated scenario are also investigated. (i.e., the relative priority assigned to the cellular and satellite systems by the policy used to direct new call requests and handoffs).

In this paper, we address the problem of optimizing the spectral efficiency of cellular indoor wireless networks by adjusting the location and power of the base-stations. Focusing on the downlink, we derive general network access criteria for mobiles on the indoor floor for systems that employ omnidirectional antennas and adaptive antennas arrays at the base-stations, in order to show and explain the advantages of the use of spatial diversity. Multiple access capability measures that depend only on energy are defined for both schemes. They are then used as the cost function for the solution to the optimal base-station placement problem, for a single-frequency system. Both continuous and combinatorial approaches have been applied to the solution of the optimization problem, and near-optimal solutions have been obtained. We show that the use of adaptive arrays yields greater capacity when increased cell-area overlap is allowed. The optimization methods, channel prediction methods, and a graphic user interface are parts of an integrated software environment that we developed in support of our investigation and which is described.

We develop an approach to the analysis of average queueing delay in a tree network of discrete-time queues with constant service time. The analysis of such systems is pertinent to packet-switched data networks with fixed-length packets. Our solution is based on considering an equivalent network, in which at each node packets in transit are given priority over exogenous arrivals. The solution to the equivalent model is easily computed, and, hence, the solution to the original model can be obtained.

A common task for network protocols is the broadcasting of information from one node to the rest of the nodes in the network. This task is often required during the execution of parallel algorithms in a network of processors, or other situations where the nodes of a mesh network generate packets to be broadcast at random time instances. We consider processors communicating over a mesh network with the objective of broadcasting information among each other. One instance of the problem involves a number of nodes all with the same message to be broadcasted. For that problem, a lower-bound on the time to complete the broadcast, and an algorithm which achieves this bound are presented. In another instance, every node in the mesh has packets to be broadcast arriving independently, according to a Poisson random process. The stability region for performing such broadcasts is characterized, and broadcast algorithms which operate efficiently within that region are presented. These algorithms involve interacting queues whose analysis is known to be very difficult. Toward that end we develop an approximation which models an n-dimensional infinite Markov chain as a single-dimensional infinite Markov chain together with an n-dimensional finite Markov chain. This approximate model can be analyzed and the results compare favorably with simulation.

We address the problem of "link activation" or "scheduling" in multihop packet radio networks. The objective is to determine a conflict-free schedule of minimum length that satisfies the specified end-to-end communication requirements. It is well known that this problem, in almost all of its forms, is a combinatorial-optimization problem of high complexity. We approach this problem by the use of a Hopfield neural network model in which the method of Lagrange multipliers is used to vary dynamically the values of the coefficients used in the connection weights.>

Addresses the major issues associated with channel access in integrated wireless networks, and proposes and analyzes the "wireless integrated multiple access" (WIMA) protocol. This scheme is based on a mixture of boundary ideas for integration and of previously introduced protocols for wireless access, and is well suited to either satellite or to terrestrial networks. A two-dimensional first-order Markov chain model for this scheme is presented, and techniques that exploit the structural properties of this chain to simplify the evaluation of the equilibrium state, without sacrificing accuracy, are described. Analytical models for the evaluation of data-packet delay for both fixed- and movable-boundary versions of this protocol and for voice-call blocking probability are presented. Performance results illustrate the dependence of performance on system parameters, and demonstrate the improved performance that can be achieved through the use of the movable-boundary version.>

The authors study the voice-call admission control problem in integrated voice/data multihop radio networks. They develop an efficient simulation model based on the use of the standard clock (SC) approach, which permits the simultaneous simulation of a large number of admission-control policies, thereby reducing computation time significantly. They then demonstrate the effectiveness of ordinal-optimization techniques, which provide a remarkably good ranking of admission-control policies after relatively short simulation runs, thereby facilitating the rapid determination of good policies. Moreover, they demonstrate that the use of crude and inaccurate analytical and simulation models can provide highly accurate policy rankings that can be used in conjunction with ordinal-optimization methods, provided that they incorporate the key aspects of system operation.>

We address the improvement in multiple access capability of an indoor wireless network that is achieved when equipment employing adaptive arrays is used. We specifically apply this improvement to the problem of optimal base-station placement. In the past we have considered indoor environments with conventional omnidirectional antennas. In this study we consider indoor wireless systems using adaptive arrays at the base-stations, and compare the results to those of the previous case in order to show and explain the advantages of the use of spatial diversity. The multiple access capability measures derived for the adaptive arrays scheme are used in the cost function for the solution of the optimal base-stations placement problem. We show that, in contrast to the omnidirectional case, where the minimisation of the cell-area overlap maximizes the capacity of the system, the use of an adaptive arrays scheme, achieves greater capacity when heavier cell-area overlap is allowed.

The issues of routing and scheduling the activation of links in packet radio networks are highly interdependent. The authors consider a form of the problem of routing for the minimization of congestion as a step toward the study of the joint routing-scheduling problem. They formulate this as a combinatorial-optimization problem, and they use Hopfield neural networks (NN) for its solution. The determination of the coefficients in the connection weights is the most critical issue in the design and simulation of Hopfield NN models. They use the method of Lagrange multipliers, which permits these coefficients to vary dynamically along with the evolution of the system state. Extensive software simulation results demonstrate the capability of their approach to determine good sets of routes in large heavily congested networks.>

Admission-control schemes for voice traffic in circuit-switched multihop radio networks are studied. The problem formulation is based on the methodology of multiple-service, multiple-resource (MSMR) modeling, and only those admission-control policies that yield a coordinate convex state space are considered. This restriction, in conjunction with reasonable modeling assumptions, results in a product-form stationary distribution for the system state. A recursive procedure to accelerate the evaluation of a large number of different admission-control policies and a descent-search method to minimize the number of policies that must be evaluated in searching for the optimal one are developed. Numerical examples indicate that performance can be improved by administering admission control, but the improvement is typically small unless different revenues or costs are associated with the various call types.>

An architecture for incorporating mobile data users into an existing MAP/TOP (Manufacturing Automation Protocol/Technical and Office Protocol) system is presented. The scheme attaches a small number of radio base stations to the TOP network through which the mobiles may access the system by executing a capture-based, multi-receiver extension of the traditional nonadaptive slotted Aloha protocol. A two-component capture model motivated by the factory channel is developed, and the multireceiver system's throughput performance is analyzed under two transmission models: base location independent and spatially correlated. It is seen that there is significant throughput degradation when base coverage areas overlap, indicating that this overlap should be minimized during system design. >

An approximate model for analyzing interacting queues is developed. This approximation models an N-dimensional infinite Markov chain by means of two Markov chains, one being one-dimensional and infinite and the other being N-dimensional and finite. The transition probabilities of each chain are expressed in terms of statistics of the other chain. The two chains are solved together iteratively to yield an approximation to the original N-dimensional infinite chain. The model is used to analyze systems of dependent queues which often arise in multiple access protocols. It is shown how this model can be used to analyze the ALOHA multiple access protocol as well as a previously proposed broadcast algorithm for a mesh network. The results compare very well with simulation.>

The authors present a performance analysis of the wireless integrated multiple access (WIMA) protocol, which is well suited to either satellite or terrestrial networks. A two-dimensional first-order Markov chain model for this scheme is presented, and techniques that exploit the structural properties of this chain to simplify the evaluation of the equilibrium state, without sacrificing accuracy, are described. Analytical models for the evaluation of data-packet delay for both fixed- and movable-boundary versions of this protocol and for voiceband blocking probability are presented. Performance results illustrate the dependence of performance on system parameters, and demonstrate the improved performance that can be achieved through the use of the movable-boundary version.>

Consider N parallel queues competing for the attention of a single server. At each time slot each queue may be connected to the server or not depending on the value of a binary random variable, the connectivity variable. Allocation at each slot; is based on the connectivity information and on the lengths of the connected queues only. At the end of each slot, service may be completed with a given fixed probability. Such a queueing model is appropriate for some communication networks with changing topology. In the case of infinite buffers, necessary and sufficient conditions are obtained for stabilizability of the system in terms of the different system parameters. The allocation policy that serves the longest connected queue stabilizes the system when the stabilizability conditions hold. The same policy minimizes the delay for the special case of symmetric queues. In a system with a single buffer per queue, an allocation policy is obtained that maximizes the throughput and minimizes the delay when the arrival and service statistics of different queues are identical.>

The authors propose an architecture for incorporating mobile data users into an existing MAP/TOP system. The scheme involves attaching a small number of radio base stations to the TOP network through which the mobiles may access the system. The system's central feature is a new distributed, multi-receiver, multiple access protocol used by the mobiles to access the bases. The protocol permits users to gracefully switch between single and multi-base operation while maintaining satisfactory performance characteristics. They utilize a multi-receiver multiple access model derived from the traditional single-receiver model to measure the new protocol's performance via simulation.>

A simple model of distributed computation that requires information exchange over a noisy channel is considered. A communication protocol is utilized that requires alternate bit exchanges between two processors. First, the case of a single public channel is considered and the number of bits that need to be exchanged between the processors to permit delta -accuracy in their goal is compared. For this computation, an error-detection-and-retransmission mechanism of error control and an error-correction-and-retransmission mixture that are consistent with the logical protocol that governs this exchange are considered. Second, the case of the availability of an additional secret channel is considered and interest in determining the minimum number of bits that need to be exchanged over a secret channel in order to maintain in -uncertainty about the computation for an eavesdropper on the public channel is shown. Various subcases under this case are considered and an upper bound on the number of secret bits when no error-control scheme is used is obtained.>

A multihop packet radio network is considered with a single traffic class and given end-to-end transmission requirements. A transmission schedule specifies at each time instant the set of links which are allowed to transmit. The purpose of a schedule is to prevent interference among transmissions from neighboring links. Given amounts of information are residing initially at a subset of the network nodes and must be delivered to a prespecified set of destination nodes. The transmission schedule that evacuates the network in minimum time is specified. The decomposition of the problem into a pure routing and a pure scheduling problem is crucial for the characterization of the optimal transmission schedule.>

The problem of routing is addressed for the minimization of congestion as a first step toward the solution of the joint routing-scheduling problem in packet radio networks. This is formulated as a combinatorial-optimization problem, and a Hopfield neural network model is developed for its solution. The method of Lagrange multipliers is used, which permits these coefficients to vary dynamically along with the evolution of the system state. Extensive software simulation results demonstrate the ability of this approach to determine good sets of routes in large, heavily-congested networks.>

The authors introduce a class of protocols for integrated voice/data radio networks called the voice/data interleaved-frame fixed-length (VD-IFFL) protocols. The IFFL protocols, which are similar to the interleaved-frame flush-out (IFFO) protocols (a class of schemes developed for data-only applications), except that they have a fixed frame length, a desirable feature in voice communication, are discussed. The VD-IFFL protocols use a movable-boundary mechanism to share the channel between voice and data traffic. Voice traffic is handled on a reservation basis, while data traffic is handled using a hybrid IFFL scheme that combines reservation and contention. These protocols are characterized by infinite Markov chains, whose transition probabilities have been evaluated exactly.>

A comprehensive study of the problem of scheduling broadcast transmissions in a multihop, mobile packet radio network is provided that is based on throughput optimization subject to freedom from interference. It is shown that the problem is NP complete. A centralized algorithm that runs in polynomial time and results in efficient (maximal) schedules is proposed. A distributed algorithm that achieves the same schedules is then proposed. The algorithm results in a maximal broadcasting zone in every slot.>

In frequency-hopped (FH) code-division multiple-access (CDMA) systems, a number of users can transmit their packets simultaneously by using quasi-orthogonal FH patterns (codes). In applications where time is unslotted, the symbol-error probability is not the same for each symbol because the number of interfering users varies throughout the packet duration. Packet-error probability for such systems is evaluated by first enumerating all possible interference states and then averaging the packet-error probability associated with each of these states. The use of Reed-Solomon error-control coding is assumed. The computational task for this evaluation is enormous. Therefore, upper bounds and an alternate less-detailed approximate model are developed for easier computation. This approximate model generates results that are very close to those obtained using the authors' first model (1988) for the cases in which those results are computable. The conclusions of this study confirm the observation, originally made elsewhere, that the widely used threshold-based model for other-user interference is not an accurate one.>

The M queues that interact according to a model of multiple-access transmissions over a collision channel are considered. Each queue receives messages that it attempts to transmit in a classical slotted ALOHA fashion. The steady-state behavior of such systems is unknown except in certain simple cases. A numerical approach is proposed that permits the calculation, within any desired accuracy, of the joint queue size distribution as well as of the moments. The approach uses a technique that involves auxiliary systems of queues that dominate, in a well-defined sense, the given ones. Consideration of such dominating systems in some cases permits the study of the ergodic region of the original systems. The methodology developed here is applicable to contexts more general than that of multiple-access transmissions.>

The authors present an exact analysis of framed ALOHA for the case of a finite number of users. This analysis, which is based on the use of a novel combinatorial technique, does not require any restrictive assumptions on channel traffic. This model can accommodate a general model for capture, in which the probability that one packet is received successfully depends on the number of packets involved in the collision. Performance results are presented for both uncontrolled and dynamically controlled systems.>

The authors consider multihop, mobile, packet radio networks that need to determine broadcasting transmission schedules in a distributed way with the goal of avoiding interference and achieving reasonable efficiency. Several centralized scheduling schemes have been proposed in the literature, while very few and mostly ad hoc distributed schemes have been considered that generally suffer from serious weaknesses. The authors propose a distributed scheme for scheduling broadcasts that involves very limited overhead and has very good efficiency performance.>

In some multiuser radio systems the receiver is not allowed to transmit feedback information to the senders. In other applications, the transmitters cannot receive feedback information sent by the receiver. For these cases, a multiple-access protocol is needed that maintains satisfactory performance in the absence of feedback. Such a protocol is introduced and an exact analysis and performance evaluation of it is provided. The protocol, which uses an unconventional reservation mechanism, exploits the capability of interference rejection that code-division multiple access (CDMA) provides.>

The standard discrete-time slotted ALOHA system with a finite number of buffered terminals is considered. The stability (ergodicity) region for this system is known only for the case of two terminals and for the case of any number of symmetric terminals. The stability of the system is studied by means of a simple concept of dominance. It is shown that the stability region for the case of two terminals can be obtained in a simple way. Lower (inner) bounds are obtained for the stability region of the system with an arbitrary finite number of terminals that are tighter than the ones already known. A similarity between these stability results and the achievable region of the no-feedback collision channel is pointed out that suggests a connection between the two problems.>

The design of a packet radio network must reflect the operational requirements and environmental constraints to which it is subject. In this paper, we outline those features that distinguish the High Frequency (HF) Intra Task Force (ITF) Network from other packet radio networks, and we present a design concept for this network that encompasses organizational structure, waveform design, and channel access. Network survivability is achieved through the use of distributed network control and frequency hopping spread-spectrum signaling. We demonstrate how the execution of the fully distributed Linked Cluster Algorithm can enable a network to reconfigure itself when it is affected by connectivity changes such as those resulting from jamming. Additional resistance against jamming is provided by frequency hopping, which leads naturally to the use of code division mutiple access (CDMA) techniques that permit the simultaneous successful transmission by several users. Distributed algorithms that exploit CDMA properties have been developed to schedule contention-free transmissions for much of the channel access in this network. Contention-based channel access protocols can also be implemented in conjunction with the Linked Cluster network structure. The design concept presented in this paper provides a high degree of survivability and flexibility, to accommodate changing environmental conditions and user demands.

An approximate model of coupled Markov chains is proposed and analyzed for a slotted ALOHA system with a finite number of buffered nodes. This model differs from earlier ones in that it attempts to capture the interdependence between the nodes. The analytical results lead to a set of equations that, when solved numerically, yield the average packet delay. Comparison between computational and simulation results for a small number of nodes show excellent agreement for most throughput values, except for values near saturation. Numerical comparisons for a two-node system show that a nonsymmetric loading of the system provides better delay-throughput performance than a symmetric one.

In this correspondence, a model is analyzed that was designed to study interference on satellite channels. We developed this model to obtain performance results for a coherent phase-shift keyed (CPSK) system in which RS-BCH concatenated codes and BCH singlestage codes are applied to a satellite channel corrupted by cochannel interference. These results make use of earlier work on performance analysis of anm-phase CPSK system operating in the presence of random Gaussian noise and non-Gaussian interference. Earlier work on performance evaluation of concatenated codes on an equierror channel is also used. Our model incorporates features that account for the burst behavior of the interference sources. Results indicate that the use of RS-BCH concatenated coding provides significant performance improvement over no coding as well as single-stage BCH coding.

In this paper we derive the probability of correct packet reception and the resulting channel throughput achievable in an asynchronous slow-frequency-hopped multiple user channel. Reed-Solomon coding is used to correct errors caused by other-user interference in an otherwise noiseless channel. We analyze and evaluate anM-ary FSK signaling scheme, which permits the discrimination against interfering signals that are present for a sufficiently small fraction of the hop duration, and results in substantial increases in channel throughput over previous models.

A new architecture for mobile radio networks, called the linked cluster architecture, is described, and methods for implementing this architecture using distributed control techniques are presented. We illustrate how fully distributed control methods can be combined with hierarchical control to create a network that is robust with respect to both node loss and connectivity changes. Two distributed algorithms are presented that deal with the formation and linkage of clusters and the activation of the network links. To study the performance of our network structuring algorithms, a simulation model was developed. The use of Simula to construct, software simulation tools is illustrated. Simulation results are shown for the example of a high frequency (HF) intratask force (ITF) communication network.

Most of the existing mathematical models for binary communication channels describe low error rate wire lines satisfactorily. For typical high error rate channels, like the ultrahigh frequency (UHF) or very high frequency (VHF) wideband data channel encountered in military uses, finite-state as well as denumerable infinite state Markov chain models do not achieve an accurate characterization. The above models, including some more recent compound models, are compared against data from the actual channel using the multigap distribution as a tool. A modification of a compound model is shown that allows more accurate modeling of a wider class of channels including the high error rate radio channel.

A new multiple access scheme is proposed and evaluated. The proposed scheme combines desirable features of the ordinary time-division (TDMA) and the random access (RA) schemes. It is shown that by adjusting the value of a single parameter a, the proposed access method can vary continuously from one extreme (TDMA) to the other (RA). The average delay per packet and the throughput can be improved for intermediate values of the load factor. Furthermore, the method can control the channel instability.

In this paper we consider the problem of organizing a set of mobile, radio-equipped nodes into a connected network. We require that a reliable structure be acquired and maintained in the face of arbitrary topological changes due to node motion and/or failure. We also require that such a structure be achieved without the use of a central controller. We propose and develop a self-starting, distributed algorithm that establishes and maintains such a connected architecture. This algorithm is especially suited to the needs of the HF Intra-Task Force (ITF) communication network, which is discussed in the paper.

Two distributed reservation control protocols are described, analyzed, and simulated for the transmission of datagramtype messages, encoded into fixed length packets, over a synchronous communication satellite channel. These protocols are of a hybrid form between pure random access contention protocols of the ALOHA variety and reservation control protocols such as CPODA. Simulations have shown that certain versions of these protocols can support throughput rates in excess of 97 percent of the channel capacity, maintain stability even under overload conditions, and incur waiting time delays ranging from 0.5 s under light traffic load to 0.88 s for saturated traffic conditions.

The commentors point out a problem with equation (6) of the above-named work (ibid., vol. COM-27, pp. 857-868, June 1979) that affects the subsequent values determined in the derivations presented and may make the paper's results inconclusive.

By modeling the broadcast portion of a mixed media network as a fully connected point-to-point network with link capacities varying as functions of the traffic rate it is possible to extend an adaptive distributed routing algorithm that was originally developed for point-to-point ground networks. Additional modifications for improved dynamic performance at the satellite interface message processors are also considered.

It is argued that the "Bursty Factor" is not a new measure for characterizing data traffic in that it does not really introduce a new concept of "burstiness," and that it is equally non-inherent a characteristic of the data source as the peak-to-average ratio or the duty cycle.

In the sampling and reconstruction of a random process a discrepancy may occur between its multiplicity and that of its reconstructed version. It is shown that under general conditions an error due to this discrepancy is not present in the total error due to sampling and reconstruction. The problem is studied in the more general framework of tracking a random process of arbitrary multiplicity with one of unit multiplicity; there too, the tracking error can be made arbitrarily small.