The proliferation of mobile devices and real-time status updating applications has motivated the optimization of data freshness in the context of age of information (AoI). Meanwhile, increasing computational demands have inspired research on CPU scheduling. Since prior CPU scheduling strategies have ignored data freshness and prior age-minimization strategies have considered only constant CPU speed, we formulate the first CPU scheduling problem as a constrained semi-Markov decision process (SMDP) problem with uncountable space, which aims to minimize the long-term average age of information, subject to an average CPU power constraint. We optimize strategies that specify when the CPU sleeps and adapt the CPU speed (clock frequency) during the execution of update-processing tasks. We consider the age-minimal CPU scheduling problem for both predictable task size (PTS) and unpredictable task size (UTS) cases, where the task size is realized at the start (PTS) or at the completion (UTS) of the task, respectively. To address the non-convex objective, we employ Dinkelbach's fractional programming method to transform our problem into an average cost SMDP. We develop a value-iteration-based algorithm and prove its convergence to obtain optimal policies and structural results for both the PTS and UTS systems. Compared to constant CPU speed, numerical results show that our proposed scheme can reduce the AoI by 50\% or more, with increasing benefits under tighter power constraints. Further, for a given AoI target, the age-minimal CPU scheduling policy can reduce the energy consumption by 50\% or more, with greater AoI reductions when the task size distribution exhibits higher variance.

We consider a status update system consisting of one source, one server, and one sink. The source generates packets according to a Poisson process and the packets are served according to a generally distributed service time. We consider a system with a capacity of one packet, i.e., there is no waiting buffer in the system, and model it as an M/G/1/1 queueing system. We introduce a probabilistically preemptive packet management policy and calculate the moment generating functions (MGFs) of the age of information (AoI) and peak AoI (PAoI) under the policy. According to the probabilistically preemptive policy, when a packet arrives, the possible packet in the system is replaced by the arriving packet with a fixed probability. Numerical results show the effectiveness of the packet management policy.

Received samples of a stochastic process are processed by a server for delivery as updates to a monitor. Each sample belongs to a class that specifies a distribution for its processing time and a function that describes how the value of the processed update decays with age at the monitor. The class of a sample is identified when the processed update is delivered. The server implements a form of M/G/1/1 blocking queue; samples arriving at a busy server are discarded and samples arriving at an idle server are subject to an admission policy that depends on the age and class of the prior delivered update. For the delivered updates, we characterize the average age of information (AoI) and average value of information (VoI). We derive the optimal stationary policy that minimizes the convex combination of the AoI and (negative) VoI. It is shown that the policy has a threshold structure, in which a new sample is allowed to arrive to the server only if the previous update's age and value difference surpasses a certain threshold that depends on the specifics of the value function and system statistics.

The proliferation of real-time status updating applications and ubiquitous mobile devices have motivated the analysis and optimization of data freshness in the context of age of information. At the same time, increasing requirements on computer performance have inspired research on CPU scheduling, with a focus on reducing energy consumption. However, since prior CPU scheduling strategies have ignored data freshness, we formulate the first CPU scheduling problem that aims to minimize the long-term average age of information, subject to an average power constraint. In particular, we optimize CPU scheduling strategies that specify when the CPU sleeps and adapt the CPU speed (clock frequency) during the execution of update-processing tasks. We formulate the age-minimal CPU scheduling problem as a constrained semi-Markov decision process (SMDP) problem with uncountable space. We develop a value-iteration-based algorithm and further prove its convergence in infinite space to obtain the optimal policy. Compared with existing benchmarks in terms of long-term average AoI, numerical results show that our proposed scheme can reduce the AoI by up to 53%, and obtains greater benefits when faced with a tighter power constraint. In addition, for a given AoI target, the age-minimal CPU scheduling policy can save more than 50% on energy consumption.

This paper investigates the optimization of memory sampling in status updating systems, where source updates are published in shared memory, and reader process samples the memory for source updates by paying a sampling cost. We formulate a discrete-time decision problem to find a sampling policy that minimizes average cost comprising age at the client and the cost incurred due to sampling. We establish that an optimal policy is a stationary and deterministic threshold-type policy, and subsequently derive optimal threshold and the corresponding optimal average cost.

Future real-time applications like smart cities will use complex Machine Learning (ML) models for a variety of tasks. Timely status information is required for these applications to be reliable. Offloading computation to a mobile edge cloud (MEC) can reduce the completion time of these tasks. However, using the MEC may come at a cost such as related to use of a cloud service or privacy. In this paper, we consider a source that generates time-stamped status updates for delivery to a monitor after processing by the mobile device or MEC. We study how a scheduler must forward these updates to achieve timely updates at the monitor but also limit MEC usage. We measure timeliness at the monitor using the age of information (AoI) metric. We formulate this problem as an infinite horizon Markov decision process (MDP) with an average cost criterion. We prove that an optimal scheduling policy has an age-threshold structure that depends on how long an update has been in service.

We present the age control protocol ACP$+$, a transport layer protocol that regulates the rate at which update packets carrying information from a source are sent over the Internet to a monitor. The source would like to minimize the average age of information at the monitor. Extensive experimentation helps shed light on age control over the current Internet and its implications for sources sending updates over a shared wireless access to monitors in the cloud. Surprisingly, age minimizing rates over fast Internet paths are about 0.5 Mbps, which is a small fraction, for example, of link rates supported by WiFi wireless access technology. We also show that congestion control algorithms employed by the Transmission Control Protocol (TCP), including hybrid approaches that achieve higher throughputs at lower delays than traditional loss-based congestion control, are unsuitable for age control.

We examine status updating systems in which time-stamped status updates are stored/written in shared-memory. Specifically, we compare Read-Copy-Update (RCU) and Readers-Writer lock (RWL) as shared-memory synchronization primitives on the update freshness. To demonstrate the tension between readers and writers accessing shared-memory, we consider a network scenario with a pair of coupled updating processes. Location updates of a mobile terminal are written to a shared-memory Forwarder Information Base (FIB) at a network forwarder. An application server sends "app updates" to the mobile terminal via the forwarder. Arriving app updates at forwarder are addressed (by reading the FIB) and forwarded to the mobile terminal. If a FIB read returns an outdated address, the misaddressed app update is lost in transit. We redesign these reader and writer processes using preemption mechanisms that improve the timeliness of updates. We present a Stochastic Hybrid System (SHS) framework to analyze location and app update age processes and show how these two age processes are coupled through synchronization primitives. Our analysis shows that using a lock-based primitive (RWL) can serve fresher app updates to the mobile terminal at higher location update rates while lock-less (RCU) mechanism favors timely delivery of app updates at lower location update rates.

We consider a system where the updates from independent sources are disseminated via a publish-subscribe mechanism. The sources are the publishers and a decision process (DP), acting as a subscriber, derives decision updates from the source data. We derive the stationary expected age of information (AoI) of decision updates delivered to a monitor. We show that a lazy computation policy in which the DP may sit idle before computing its next decision update can reduce the average AoI at the monitor even though the DP exerts no control over the generation of source updates. This AoI reduction is shown to occur because lazy computation can offset the negative effect of high variance in the computation time.

We study status updating under two-way delay in a system consisting of a sampler, a sink, and a controller residing at the sink. The controller drives the sampling process by sending request packets to the sampler. Upon receiving a request, the sampler generates a sample and transmits the status update packet to the sink. Transmissions of both request and status update packets encounter random delays. We develop optimal control policies to minimize the average age of information (AoI) using the tools of Markov decision processes in two scenarios. We begin with the system having at most one active request, i.e., a generated request for which the sink has not yet received a status update packet. Then, as the main distinctive feature of this paper, we initiate pipelined-type status updating by studying a system having at most two active requests. Furthermore, we conduct AoI analysis by deriving the average AoI expressions for the Zero-Wait-1, Zero-Wait-2, and Wait-1 policies. According to the Zero-Wait-1 policy, whenever a status update packet is delivered to the sink, a new request packet is inserted into the system. The Zero-Wait-2 policy operates similarly, except that the system can hold two active requests. According to the Wait-1 policy, whenever a status update packet is delivered to the sink, a new request is sent after a waiting time which is a function of the current AoI. Numerical results illustrate the performance of each status updating policy under varying system parameter values.

A source generates time-stamped update packets that are sent to a server and then forwarded to a monitor. This occurs in the presence of an adversary that can infer information about the source by observing the output process of the server. The server wishes to release updates in a timely way to the monitor but also wishes to minimize the information leaked to the adversary. We analyze the trade-off between the age of information (AoI) and the maximal leakage for systems in which the source generates updates as a Bernoulli process. For a time slotted system in which sending an update requires one slot, we consider three server policies: (1) Memoryless with Bernoulli Thinning (MBT): arriving updates are queued with some probability and head-of-line update is released after a geometric holding time; (2) Deterministic Accumulate-and-Dump (DAD): the most recently generated update (if any) is released after a fixed time; (3) Random Accumulate-and-Dump (RAD): the most recently generated update (if any) is released after a geometric waiting time. We show that for the same maximal leakage rate, the DAD policy achieves lower age compared to the other two policies but is restricted to discrete age-leakage operating points.

A source node updates its status as a point process and also forwards its updates to a network of observer nodes. Within the network of observers, these updates are forwarded as point processes from node to node. Each node wishes its knowledge of the source to be as timely as possible. In this network, timeliness is measured by a discrete form of age of information: each status change at the source is referred to as a version and the age at a node is how many versions out of date is its most recent update from the source. This work introduces a method for evaluating the average version age at each node in the network when nodes forward updates using a memoryless gossip protocol. This method is then demonstrated by version age analysis for a collection of simple networks. For gossip on a complete graph with symmetric updating rates, it is shown that each node has average age that grows as the logarithm of the network size.

We summarize recent contributions in the broad area of age of information (AoI). In particular, we describe the current state of the art in the design and optimization of low-latency cyberphysical systems and applications in which sources send time-stamped status updates to interested recipients. These applications desire status updates at the recipients to be as timely as possible; however, this is typically constrained by limited system resources. We describe AoI timeliness metrics and present general methods of AoI evaluation analysis that are applicable to a wide variety of sources and systems. Starting from elementary single-server queues, we apply these AoI methods to a range of increasingly complex systems, including energy harvesting sensors transmitting over noisy channels, parallel server systems, queueing networks, and various single-hop and multi-hop wireless networks. We also explore how update age is related to MMSE methods of sampling, estimation and control of stochastic processes. The paper concludes with a review of efforts to employ age optimization in cyberphysical applications.

Leader-based data replication improves consistency in highly available distributed storage systems via sequential writes to the "leader" nodes. After a write has been committed by the leaders, "follower" nodes are written by a multicast mechanism and are only guaranteed to be eventually consistent. With Age of Information (AoI) as the freshness metric, we characterize how the number of leaders affects the freshness of the data retrieved by an instantaneous read query. In particular, we derive the average age of a read query for a deterministic model for the leader writing time and a probabilistic model for the follower writing time. We obtain a closed-form expression for the average age for exponentially distributed follower writing time. Our numerical results show that, depending on the relative speed of the write operation to the two groups of nodes, there exists an optimal number of leaders which minimizes the average age of the retrieved data, and that this number increases as the relative speed of writing on leaders increases.

Sensor sources submit updates to a monitor through an unslotted, uncoordinated, unreliable multiple access collision channel. The channel is unreliable; a collision-free transmission is received successfully at the monitor with some transmission success probability. For an infinite-user model in which the sensors collectively generate updates as a Poisson process and each update has an independent exponential transmission time, a stochastic hybrid system (SHS) approach is used to derive the average age of information (AoI) as a function of the offered load and the transmission success probability. The analysis is then extended to evaluate the individual age of a selected source. When the number of sources and update transmission rate grow large in fixed proportion, the limiting asymptotic individual age is shown to provide an accurate individual age approximation, even for a small number of sources.

We consider updating strategies for a local cache which downloads time-sensitive files from a remote server through a bandwidth-constrained link. The files are requested randomly from the cache by local users according to a popularity distribution which varies over time according to a Markov chain structure. We measure the freshness of the requested time-sensitive files through their Age of Information (AoI). The goal is then to minimize the average AoI of all requested files by appropriately designing the local cache’s downloading strategy. To achieve this goal, the original problem is relaxed and cast into a Constrained Markov Decision Problem (CMDP), which we solve using a Lagrangian approach and Linear Programming. Inspired by this solution for the relaxed problem, we propose a practical cache updating strategy that meets all the constraints of the original problem. Under certain assumptions, the practical updating strategy is shown to be optimal for the original problem in the asymptotic regime of a large number of files. For a finite number of files, we show the gain of our practical updating strategy over the traditional square-root-law strategy (which is optimal for fixed non time-varying file popularities) through numerical simulations.

A source provides status updates to monitors through a network with state defined by a continuous-time finite Markov chain. An age of information (AoI) metric is used to characterize timeliness by the vector of ages tracked by the monitors. Based on a stochastic hybrid systems (SHS) approach, first order linear differential equations are derived for the temporal evolution of both the moments and the moment generating function (MGF) of the age vector components. It is shown that the existence of a non-negative fixed point for the first moment is sufficient to guarantee convergence of all higher order moments as well as a region of convergence for the stationary MGF vector of the age. The stationary MGF vector is then found for the age on a line network of preemptive memoryless servers. From this MGF, it is found that the age at a node is identical in distribution to the sum of independent exponential service times. This observation is then generalized to linear status sampling networks in which each node receives samples of the update process at each preceding node according to a renewal point process. For each node in the line, the age is shown to be identical in distribution to a sum of independent renewal process age random variables.

A source submits status update jobs to a service facility for processing and delivery to a monitor. The status updates belong to service classes with different service requirements. We model the service requirements using a hyperexponential service time model. To avoid class-specific bias in the service process, the system implements an M/G/1/1 blocking queue; new arrivals are discarded if the server is busy. Using an age-of-information (AoI) metric to characterize timeliness of the updates, a stochastic hybrid system (SHS) approach is employed to derive the overall average AoI and the average AoI for each service class. We observe that both the overall AoI and class-specific AoI share a common penalty that is a function of the second moment of the average service time and they differ chiefly because of their different arrival rates. We show that each high-probability service class has an associated age-optimal update arrival rate while low-probability service classes incur an average age that is always decreasing in the update arrival rate.

Internet-of-Things (IoT) applications have sources sense and send their measurement updates over the Internet to a monitor (control station) for real-time monitoring and actuation. Ideally, these updates would be delivered fresh, at a high rate constrained only by the supported sensing rate. However, such a rate may lead to network congestion related delays in delivery of updates at the monitor that make the freshest update at the monitor unacceptably old for the application. Alternately, at low rates, while updates arrive at the monitor with smaller delays, new updates arrive infrequently. Thus, both low and high rates may lead to an undesirably aged freshest update at the monitor. We propose a novel transport layer protocol, namely the Age Control Protocol (ACP), which enables timely delivery of such updates to monitors over the Internet in a network-transparent manner. ACP adapts the rate of updates from a source such that the average age of updates at the monitor is minimized. We detail the protocol and the proposed control algorithm. We demonstrate its efficacy using extensive simulations and realworld experiments, including wireless access for the sources and an end-to-end connection with multiple hops to the monitor.

We examine multiple independent sources providing status updates to a monitor through simple queues. We formulate an age of information (AoI) timeliness metric and derive a general result for the AoI that is applicable to a wide variety of multiple source service systems. For first-come first-served and two types of last-come first-served systems with Poisson arrivals and exponential service times, we find the region of feasible average status ages for multiple updating sources. We then use these results to characterize how a service facility can be shared among multiple updating sources. A new simplified technique for evaluating the AoI in finite-state continuous-time queuing systems is also derived. Based on stochastic hybrid systems, this method makes AoI evaluation to be comparable in complexity to finding the stationary distribution of a finite-state Markov chain.

Independent sources send their status updates to a server for delivery to a monitor. We analyze an age of information timeliness metric when sources are assigned different priorities. We consider two service facilities (a) there is no waiting room and an update in service is preempted on arrival of an equal or higher priority update, and (b) there is a waiting room for at most one update and preemption is allowed in waiting but not in service. We model the age process as a stochastic hybrid system.

A source submits status updates to a network for delivery to a destination monitor. Updates follow independent routes such that updates may arrive out of order. Each network route is modeled as a memoryless preemptive last-come-first-served queue. Using a stochastic hybrid systems approach, we evaluate the average age of information at the monitor, including a simplified characterization of the benefits of route and server diversity.

We consider a cache refresh system where a local server is connected to multiple remote sources and maintains local copies of the data items at the sources. The data at each source is updated randomly and independently without notifying the local server, while the local server refreshes the corresponding cached data periodically. The freshness of the local cache is measured by two different freshness metrics,age of synchronization(AoS) andage of information(AoI). We address the following problem: given a constrained total refresh rate, how does the local server allocate the refresh rate for each source to maintain overall data freshness? We derive the AoI optimal policy which depends only on the square root of the source popularity. For a large refresh rate, we propose an AoS near-optimal rate allocation policy that is proportional to the cube root of both the source update rate and the source popularity. For small refresh rates, we also prove that the square root law with respect to the popularity minimizes both AoS and AoI.

We consider a real-time streaming source coding system in which an encoder observes a sequence of randomly arriving symbols from an i.i.d. source, and feeds binary code-words to a FIFO buffer that outputs one bit per time unit to a decoder. Each source symbol represents a status update by the source, and the timeliness of the system is quantified by the age of information (AoI), defined as the time difference between the present time and the generation time of the most up-to-date symbol at the output of the decoder. When the FIFO buffer is allowed to be empty, we propose an optimal prefix-free lossless coding scheme that minimizes the average peak age based on the analysis of discrete-time Geo/G/1 queue. For more practical scenarios in which a special codeword is reserved for indicating an empty buffer, we propose an encoding scheme that assigns a codeword to the empty buffer state based on an estimate of the buffer idle time.

Real-time monitoring is characterized by a source repeatedly sending updates over the Internet to a monitor, which desires the sensed information at it to be as fresh (of small age) as possible, given network constraints. We propose the Age Control Protocol (ACP), which, in a network-transparent manner, enables a source to keep the age at the monitor small. We evaluate it using simulations and real-world experiments.

This work introduces a new model for cloud gaming systems aimed at optimizing the timeliness of video frames based on an age of information (AoI) metric. Mobile clients submit actions through an access network to a game server. The game server generates video frames at a constant frame rate. At the mobile device, the display of these frames represent game status updates. We develop a Markov model to characterize the frame delivery process in low-latency edge cloud gaming systems. Based on this model, we derive a simple formula for the average status age of a tightly synchronized low-latency mobile gaming system in which the inter-frame period is a significant contributor to the system latency. We validate the model by ns-3 simulation of a low-latency edge cloud gaming system. Our evaluation scenarios included single-player games as well as multi-player games in which the game processing was conducted by a combination of a centralized game server and edge cloud renderers.

We consider a system where randomly generated updates are to be transmitted to a monitor, but only a single update can be in the system at a time. Therefore, the source has to prioritize between the two possible transmission policies: preempting the current update or discarding the new one. We consider Poisson arrivals and general service time, and refer to this system as the M/G/1/1 queue. We start by studying the average status update age and the optimal update arrival rate for these two schemes under general service time distribution. We then apply these results on two practical scenarios in which updates are sent through an erasure channel using (a) an infinite incremental redundancy (IIR) HARQ system and (b) a fixed redundancy (FR) HARQ system. We show that in both schemes the best strategy would be not to preempt. Moreover, we also prove that, from an age point of view, IIR is better than FR.

We consider a system where a local cache maintains a collection of N dynamic content items that are randomly requested by local users. A capacity-constrained link to a remote network server limits the ability of the cache to hold the latest version of each item at all times, making it necessary to design an update policy. Using an age of information metric, we show under a relaxed problem formulation that an asymptotically optimal policy updates a cached item in proportion to the square root of the item's popularity. We then show experimentally that a physically realizable policy closely approximates the asymptotic optimal policy.

Applications like environmental sensing, and health and activity sensing, are supported by networks of devices (nodes) that send periodic packet transmissions over the wireless channel to a sink node. We look at simple abstractions that capture the following commonalities of such networks (a) the nodes send periodically sensed information that is temporal and must be delivered in a timely manner, (b) they share a multiple access channel and (c) channels between the nodes and the sink are unreliable (packets may be received in error) and differ in quality. We consider scheduled access and slotted ALOHA-like random access. Under scheduled access, nodes take turns and get feedback on whether a transmitted packet was received successfully by the sink. During its turn, a node may transmit more than once to counter channel uncertainty. For slotted ALOHA-like access, each node attempts transmission in every slot with a certain probability. For these access mechanisms we derive the age of information (AoI), which is a timeliness metric, and arrive at conditions that optimize AoI at the sink. We also analyze the case of symmetric updating, in which updates from different nodes must have the same AoI. We show that ALOHA-like access, while simple, leads to AoI that is worse by a factor of about 2e, in comparison to scheduled access.

Using an age of information (AoI) metric, we examine the transmission of coded updates through a binary erasure channel to a monitor/receiver. We start by deriving the average status update age of an infinite incremental redundancy (IIR) system in which the transmission of a k-symbol update continues until k symbols are received. This system is then compared to a fixed redundancy (FR) system in which each update is transmitted as an n symbol packet and the packet is successfully received if and only if at least k symbols are received. If fewer than k symbols are received, the update is discarded. Unlike the IIR system, the FR system requires no feedback from the receiver. For a single monitor system, we show that tuning the redundancy to the symbol erasure rate enables the FR system to perform as well as the IIR system. As the number of monitors is increased, the FR system outperforms the IIR system that guarantees delivery of all updates to all monitors.

The end-to-end delay of streaming source coding is characterized by an age of information (AoI) metric that measures the number of symbol periods the decoder output lags behind the encoder input. The source encoder receives input source symbols one per unit time and sequentially outputs binary codewords to a constant rate channel that transmits bits to the decoder. We examine a system in which knowledge of the busy/idle state at the channel interface enables the encoder to switch among codebooks with different source blocklengths based on the backlog of symbols at the encoder. We start by introducing two source sequence parsing policies and show that in each of them the blocklength process can be modeled by a Markov chain. We show by experiments that blocklength adjustment based on the channel interface state provides lower average age than codes with fixed blocklength. Aiming to avoid unnecessary frequent blocklength changes by the encoder backlog, we propose maximum blocklength control scheme at the encoder to further reduce the average age.

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

We examine lossless data compression from an average delay perspective. An encoder receives input symbols one per unit time from an i.i.d. source and submits binary codewords to a FIFO buffer that transmits bits at a fixed rate to a receiver/decoder. Each input symbol at the encoder is viewed as a status update by the source and the system performance is characterized by the status update age, defined as the number of time units (symbols) the decoder output lags behind the encoder input. An upper bound on the average status age is derived from the exponential bound on the probability of error in streaming source coding with delay. Apart from the influence of the error exponent that describes the convergence of the error, this upper bound also scales with the constant multiplier term in the error probability. However, the error exponent does not lead to an accurate description of the status age for small delay and small blocklength. An age optimal block coding scheme is proposed based on an approximation of the average age by converting the streaming source coding system into a D/G/1 queue. We compare this scheme to the error exponent optimal coding scheme which uses the method of types. We show that maximizing the error exponent is not equivalent to minimizing the average status age.

In this work we study how to manage the freshness of status updates sent from a source to a remote monitor via a network server. A proper metric of data freshness at the monitor is the age-of-information, which is defined as how old the freshest update is since the moment this update was generated at the source. A logical policy is the zero-wait policy, i.e., the source submits a fresh update once the server is free, which achieves the maximum throughput and the minimum average delay. Surprisingly, this zero-wait policy does not always minimize the average age. This motivates us to study how to optimally control the status updates to keep data fresh and to understand when the zero-wait policy is optimal. We introduce a penalty function to characterize the level of “dissatisfaction” on data staleness, and formulate the average age penalty minimization problem as a constrained semi-Markov decision process (SMDP) with an uncountable state space. Despite of the difficulty of this problem, we develop efficient algorithms to find the optimal status update policy. We show that, in many scenarios, the optimal policy is to wait for a certain amount of time before submitting a new update. In particular, the zero-wait policy can be far from the optimum if (i) the penalty function grows quickly with respect to the age, and (ii) the update service times are highly random and positive correlated. To the best of our knowledge, this is the first optimal control policy which is proven to minimize the age-of-information in status update systems.

In a time-varying fading channel, opportunistic transmission when the channel is strong is known to yield a significant gain. A similar result appears in the context of multiuser channels where multiuser diversity gain is achieved by serving users with the strongest channels. In contrast, in this paper, we exploit opportunistic channel selection to reduce the processing energy at the receiver side. This saving is derived by increasing the gap between the instantaneous capacity and the code rate, which in turn reduces the required decoding energy. The savings in the processing energy then enables the receiver to sample and process a larger fraction of the packets. We first analyze the single-user case, and propose a signaling scheme that achieves the optimum rate. We then extend this result to a multiuser system.

We consider a communication system with energy harvesting at a receiver for which the processing energy is the bottleneck. We propose using hybrid automatic retransmission request (HARQ) with soft combining to reduce the processing energy and improve the throughput under limited receiver energy. In this protocol, the receiver keeps requesting additional redundancy in order to increase the gap between transmission rate and the overall accumulated mutual information (so-called capacity gap), which in turn reduces the processing energy. We compare the performance of two HARQ schemes: (1) incremental redundancy (IR) HARQ, which incrementally increases the code-length by sending additional coded symbols (parity symbols) in each retransmission and (2) Repetition-HARQ, which simply repeats transmitting the same coded message (codeword) in response to the retransmission requests, and applies maximum ratio combining (MRC) at the receiver. In these systems, the decoding energy is a decreasing function of the capacity gap but an increasing function of the code-length. The IR-HARQ protocol yields a better capacity gap, but increases the code-length, while Repetition-HARQ offers less improvement in the capacity gap, but does not increase the effective code-length. Thus, contrary to systems without an energy constraint on receiver processing in which IR-HARQ always performs better, here, depending on the system parameters, repetition-HARQ can outperform IR-HARQ.

A source submits status updates to a service facility for delivery to a monitor. Each update requires energy and the source is powered by a stochastic energy harvesting system. With knowledge of the service facility state, the source avoids queue-induced delays by submitting a fresh update only after the service completion of a prior update. For a source with a large battery, we evaluate updating policies using a status age timeliness metric. We show that an optimal policy is lazy; following a service completion, the service facility is frequently left idle even though the server may have sufficient energy to submit an update.

The prevalence of mobile devices especially smartphones has attracted research on mobile content delivery techniques. In this paper, we propose to take advantage of the storage available at wireless access points to bring content closer to mobile devices, hence improving the downloading performance. Specifically, we propose to have a separate popularity based cache and a prefetch buffer at the network edge to capture both long-term and short-term content access patterns. Further, we point out that it is insufficient to rely on a device's past history to predict when and where to prefetch, especially in urban settings; instead, we propose to derive a prediction model based on the aggregated network-level statistics. We discuss the proposed mobile content caching/prefetching method in the context of the MobilityFirst future Internet architecture. In MobilityFirst, when mobile clients move between network attachment points (e.g., Wi-Fi access points), their network association records are logged by the network, which then naturally facilitates the network-level mobility prediction. Through detailed simulations with real taxi mobility traces, we show that such a strategy is more effective than earlier schemes in satisfying content requests at the edge (higher cache hit ratios), leading to shorter content download latencies. Specifically, the fraction of requests satisfied at the edge increases by a factor of 2.9 compared to a caching only approach, and by 45% compared to individual user-based prediction and prefetching.

When receivers rely on stochastic energy harvesting, power outages will reduce the reliable communication rate. To model the receiver, we decompose the processing tasks in two parts: (1) sampling or Analog-to-Digital Conversion (ADC), which includes all RF front-end processing, and (2) decoding. This work considers a time-slotted system in which a source transmits coded packets through a time-invariant channel to a receiver with a finite battery and a decoder whose energy consumption can be adapted from slot to slot. Based on the relative energy costs of sampling and decoding and a stochastic model for the energy harvesting, we determine sampling and decoding policies that maximize the packet throughput. When the receiver is battery-constrained, we show that the throughput is maximized by a deferred decoding policy that samples packets at every opportunity but decodes backlogged packets using only excess energy that would otherwise be discarded. This result is shown to hold for Markov-modulated energy harvesting processes with arbitrary memory. In addition, when the average energy harvesting rate is not sufficient to decode all packets, a modified policy that defers decoding only when the backlog is below a threshold is shown to perform well when the threshold is carefully chosen.

There has been a considerable interest in quantifying the influence that one node exerts on another in a social network. Using directed information, we study the problem for a simple, two-node network that models two users in a Twitter network in which one user (Alice) influences the other user (Bob) through her tweets. Under this setup, we relate the problem of direction of influence to the calculation of directed information from the input to the output in a bufferless single-server timing queue. Based on this relationship, we compute the directed information rate from Alice to Bob and, under simplifying assumptions, relate that rate to the distributions of Alice's tweet timings and Bob's action timings.

Base stations with a large number of transmit antennas can potentially serve a large number of users at high rates. However, the receiver processing in the uplink relies on channel estimates, which are known to suffer from pilot interference. In this paper, making use of the similarity of the uplink received signal in CDMA with that of a multi-cell multi-antenna system, we perform a large system analysis when the receiver employs an MMSE filter with a pilot contaminated estimate. We assume a Rayleigh fading channel with different received powers from users. We find the asymptotic signal to interference plus noise ratio (SINR) as the number of antennas and number of users per base station grow larger while maintaining a fixed ratio. Through the SINR expression we explore the scenario where the number of users being served are comparable to the number of antennas at the base station. The SINR explicitly captures the effect of pilot contamination and is found to be the same as that employing a matched filter with a pilot contaminated estimate. We also find the exact expression for the interference suppression obtained using an MMSE filter, which is an important factor when there are a significant number of users in the system as compared to the number of antennas. In a typical set up, in terms of the five percentile SINR, the MMSE filter is shown to provide significant gains over matched filtering and is within 5 dB of MMSE filter with perfect channel estimate. Simulation results for achievable rates are close to large system limits for even a 10-antenna base station with 3 or more users per cell.

When receivers rely on energy harvesting, energy outages will constrain reliable communication. To model the harvesting receiver, we decompose the processing tasks in two parts: first is sampling or Analog-to-Digital-Conversion (ADC) stage which includes all RF front-end processing, and second is decoding. We propose a model in which, for a given code rate, channel capacity, and battery size, the receiver can choose the sampling rate to balance the sampling and decoding energy costs. We then characterize the maximum reliable communication rate over the choice of sampling rate and code rate and we verify that the sampling rate should be maximized. In addition, we consider the fixed-timing transmission system and show that under some conditions the same rates can also be achieved.

Recent technology advances are poised to enable low-cost, low-power communications in the 7 GHz of unlicensed spectrum at 60 GHz millimeter wave (mmW) frequencies. In 60 GHz networks, transmitters and receivers employ directional antennas and point their main beams toward each other to overcome high propagation losses and achieve high data rates. However, CSMA based directional MAC (DMAC) protocols suffer from the "deafness" problem which causes unfairness and low channel utilization. This paper examines the deafness problem from a new perspective and shows that unfairness and low channel utilization are caused by the exponential backoff mechanism. We propose an enhanced DMAC (EDMAC) protocol that does not use an exponential backoff mechanism, instead employing a low control overhead protocol that enables receivers to adaptively tune senders' contention window sizes. NS-2 simulation results are given to demonstrate that EDMAC compares favorably to DMAC, achieving similar capacity and lower delay jitter in single hop networks, and significantly higher capacity in multi-hop ad hoc network scenarios.

Resource sharing among mobile network operators is a promising way to tackle growing data demand by increasing capacity and reducing costs of network infrastructure deployment and operation. In this work, we evaluate sharing options that range from simple approaches that are feasible in the near-term on traditional infrastructure to complex methods that require specialized/virtualized infrastructure. We build a simulation testbed supporting two geographically overlapped 4G LTE macro cellular networks and model the sharing architecture/process between the network operators. We compare Capacity Sharing (CS) and Spectrum Sharing (SS) on traditional infrastructure and Virtualized Spectrum Sharing (VSS) and Virtualized PRB Sharing (VPS) on virtualized infrastructure under light, moderate and heavy user loading scenarios in collocated and noncollocated E-UTRAN deployment topologies. We also study these sharing options in conservative and aggressive sharing participation modes. Based on simulation results, we conclude that CS, a generalization of traditional roaming, is the best performing and simplest option, SS is least effective and that VSS and VPS perform better than spectrum sharing with added complexity.

Increasingly ubiquitous communication networks and connectivity via portable devices have engendered a host of applications in which sources, for example people and environmental sensors, send updates of their status to interested recipients. These applications desire status updates at the recipients to be as timely as possible; however, this is typically constrained by limited network resources. In this paper, we employ a time-average age metric for the performance evaluation of status update systems. We derive general methods for calculating the age metric that can be applied to a broad class of service systems. We apply these methods to queue-theoretic system abstractions consisting of a source, a service facility and monitors, with the model of the service facility (physical constraints) a given. The queue discipline of first-come-first-served (FCFS) is explored. We show the existence of an optimal rate at which a source must generate its information to keep its status as timely as possible at all its monitors. This rate differs from those that maximize utilization (throughput) or minimize status packet delivery delay. While our abstractions are simpler than their real-world counterparts, the insights obtained, we believe, are a useful starting point in understanding and designing systems that support real time status updates.

We examine multiple independent sources providing status updates to a monitor through a first-come-first-served M/M/1 queue. We formulate a status-age timeliness metric and find the region of feasible average status ages for a pair of updating sources. In the presence of interfering traffic with a given offered load, we show the existence of an optimal rate at which a source should generate its updates.

Despite considerable progress, the capacity region of fading broadcast channels with channel state known at the receivers but unknown at the transmitter remains unresolved. We address this subject by introducing a layered erasure broadcast channel model in which each component channel has a state that specifies the received signal levels in an instance of a deterministic binary expansion channel. We find the capacity region of this class of broadcast channels. The capacity achieving strategy assigns each signal level to the user that derives the maximum weighted expected rate. The outer bound is based on a channel enhancement that creates a degraded broadcast channel for which the capacity region is known. This same approach is then used to find inner and outer bounds to the capacity region of fading Gaussian broadcast channels. The achievability scheme employs a superposition of binary inputs. For intermittent additive white Gaussian noise (AWGN) channels and for Rayleigh fading channels, the achievable rates are observed to be within 1–2 bits of the outer bound at high SNR. We also prove that the achievable rate region is within 6.386 bits/s/Hz of the capacity region for all fading AWGN broadcast channels.

We investigate bandwidth allocation in next generation cellular systems employing relays similar to LTE advanced systems with type-I relays. We jointly optimize the bandwidth and power usage under constraints on required rate, bandwidth and transmit power. We study scenarios wherein, the relay acts as a forwarder for multiple User Equipments (UEs/users) in both uplink and/or downlink. This includes scenarios when the relay has its own data to send along with forwarding the data of other users. We examine the weighted power minimization problem for relaying with multiple users. We also show specific results with N user scenario and also single user case in order to understand how the bandwidth and power are allocated. Numerical evaluations with N users on a three sector LTE-A cell employing Fractional Frequency Reuse (FFR) indicate that power savings of at least 3 dB can be achieved by optimizing over both bandwidth and power.

This work is motivated by network applications that require nodes to disseminate their state to others. In particular, vehicular nodes will host applications that periodically disseminate time-critical state across the network to help improve on-road safety. In this work, we want to minimize the average age of state information that a node observes from any other node in networks with hundreds to thousands of nodes. We explore the benefits, vis-a-vis reducing age, of a multi-hop wireless network over a fully-connected one, for a physical network of on-road vehicles, by allowing nodes to piggyback other nodes' states. We show that for a large road network and a chosen schedule, there exists an optimal fraction of connected neighbor nodes, which, for a fixed signal-to-noise ratio between most distant nodes, is invariant to the size of the network. Via simulation we confirm that significant reductions in age are obtained via piggybacking for network sizes of interest.

We examine the capacity region of the K-user Gaussian fading broadcast channel with channel state known at the receivers but unknown at the transmitter. For binary expansion superposition signaling, we derive a new achievable rate based on soft decision decoding of the binary inputs. The approach is based on a simple tight bound on the output entropy of a high-SNR AWGN channel with a continuous uniform input. We show that a binary superposition signaling scheme is for each user within a constant gap of 5.443 b/s/Hz of the broadcast channel capacity for all fading state distributions.

The fully connectedK-user interference channel is studied in a multipath environment with bandwidthW. We show that when each link consists ofDphysical paths, the total spectral efficiency can grow linearly withK. This result holds not merely in the limit of large transmit powerP, but for any fixedP, and is, therefore, a stronger characterization than degrees of freedom. It is achieved via a form of interference alignment in the time domain. A caveat of this result is thatWmust grow withK, a phenomenon we refer to as bandwidth scaling. Our insight comes from examining channels with single path links (D=1), which we refer to as line-of-sight (LOS) links. For such channels, we build a time-indexed interference graph and associate the communication problem with finding its maximum independent set. This graph has a stationarity property that we exploit to solve the problem efficiently via dynamic programming. Additionally, the interference graph enables us to demonstrate the necessity of bandwidth scaling for any scheme operating over LOS interference channels. Bandwidth scaling is then shown to also be a necessary ingredient for interference alignment in theK-user interference channel.

We compare the performance of half-duplex relays in downlink cellular system against a baseline system without relays. We simulate the performance of (i) a collaborative power addition scheme, where the relay boosts the received power (P-CPA) at the mobile locations, and (ii) a CPA scheme with power control (PC-CPA) at the base station and relays. Evaluations are done in the context of a 19-cell, 57-sector set-up in which each of the served users must be delivered a message. The user messages are taken to have the same size and 90% of users in the network must be served. Improvements over the baseline due to relay deployments are measured in terms of increase in common rate of users as well as power savings in terms of reduction in peak or average power transmitted by base stations. In the CPA schemes with base stations and relays transmitting at full power, the peak power saving is 1.46 dB, alternately, the throughput improvement over a 1 bit/sec/Hz baseline rate is 21%. In the PC-CPA scheme, the peak power saving is 2.6 dB and the average total power in the system can be reduced by 3 dB.

Achievable rates with amplify-and-forward (AF) and decode-and-forward (DF) cooperative strategies are examined for relay networks. Motivated by sensor network applications, power-constrained networks with large bandwidth resources and a large number of nodes are considered. It is shown that AF strategies do not necessarily benefit from the available bandwidth. Rather, transmitting in the optimum AF bandwidth allows the network to operate in the linear regime where the achieved rate increases linearly with the available network power. The optimum power allocation among the AF relays, shown to be a form of maximal ratio combining, indicates the favorable relay positions. Orthogonal node transmissions are also examined. While the same optimum bandwidth result still holds, the relay power allocation in this case can be viewed as a form of water-filling. In contrast, the DF strategy will optimally operate in the wideband regime and is shown to require a different choice of relays. Thus, in a large scale network, the choice of a coding strategy goes beyond determining a coding scheme at a node; it also determines the operating bandwidth, as well as the set of relays and best distribution of the relay power.

We consider a secret communication scenario where Alice wants to transmit secretly to Bob in presence of a passive eavesdropper Eve. The Alice-Bob channel is a fixed-SNR AWGN channel, while the Alice-Eve channel is a fast Rayleigh fading channel, with the channel states only known to Eve. Alice knows the statistics of Alice-Eve channel, but not the exact realizations. We investigate the achievable secrecy rates for this channel model with Gaussian signaling and discrete signaling. For Gaussian signaling, several transmission strategies according to the main channel's relative channel gain are proposed and evaluated. For discrete signaling, achievable secrecy rates with Quadrature Amplitude Modulation (QAM) are evaluated. When Bob's channel is much better than Eve's channel, simple Gaussian signaling can perform close to the upper bound, and is better than the rate achieved with M-QAM. When Bob's channel gain is on average worse than the eavesdropper's average channel gain, positive secrecy rate can still be achieved for Gaussian signaling with artificial noise injection and a burst signaling strategy. Moreover, M-QAM can outperform Gaussian signaling. The key factor that enables secret communication in this case is that both M-QAM and artificial noise limit the leakage of information when Eve's channel is unusually good.

Generally, the capacity-achieving signaling design for a specific channel should consider the joint optimization of channel coding and modulation. Nevertheless, coding theorists and practitioners have recognized that a well-designed LDPC code can achieve capacity-approaching performance universally across a range of data transmission and storage channels. A pronounced example is the forward error correction scheme adopted recently by the second generation standards for digital video broadcasting (DVB), wherein the same LDPC codes are expected to be reused over satellite, terrestrial and cable channels. However, to accommodate the spectral efficiency of different channel type, the coded bits should be mapped to the modulator judiciously. The well-known BICM strategy employs a large random bit interleaver, which typically yields good performance for an arbitrary choice of constellation mapper. However, it is problematic for high-speed coding and modulation due to the large amount of memory and circuits routing required. This motivates us to impose structural simplicity on the bit interleaver configuration so that the coded bits are de-multiplexed systematically into parallel groups to feed the constellation mapper. In this paper, we focus on the design of bit demultiplexers for multi-level modulations by applying the framework of multi-edge type (MET) LDPC. Since the channel-dependence of a given code ensemble is dominated by the mutual information between the input and output of the effective channel, we propose to simplify the analysis of the decoding behavior by using a set of surrogate binary erasure channels (BEC). Simulation results indicate that the proposed bit demultiplexer surpasses the performance of the heuristic interleaving strategy specified in second generation DVB standard for terrestrial channels (DVB-T2).

This paper presents an evaluation of in-network caching strategies for efficient delivery of content to mobile devices that are intermittently connected to the network. Placement of content into in-network caches is formulated as an optimization problem that minimizes access latency under certain cost constraints. Several heuristic solutions (longest lifetime, split & longest lifetime and proportional probability to lifetime) are investigated via numerical examples and simulations. The results show that the proposed methods offer significant performance improvement over random caching and can approach the performance of exhaustive caching at every node with reduced storage cost.

For wireless sensor networks with many locationunaware nodes, which can be modeled as a planar Poisson point process, we investigate a protocol, dubbed BeSpoken, which steers data transmissions along a straight path called a spoke. BeSpoken implements a simple, spatially recursive process, where a basic set of control packets and a data packet are exchanged repeatedly among daisy-chained relays that constitute the spoke. Hence, a data packet originated by the first relay makes a forward progress in the direction of the spoke. Despite the simplicity of the protocol engine, modeling the spoke process is a significant challenge. Bespoken directs data transmissions by randomly selecting relays to retransmit data packets from crescent-shaped areas along the spoke axis. The resulting random walk of the spoke hop sequence may be modeled as a two dimensional Markov process. Based on this model, we propose design rules for protocol parameters that minimize energy consumption while ensuring that spokes propagate far enough and have a limited wobble with respect to the spoke axis. The energy efficiency is demonstrated through simulations of the BeSpoken-based data search, and a comparison with the energy consumption of a search based on directed diffusion.

The capacity of mobile Infostation network can be greatly increased, if, in addition to direct short-range communications between mobile nodes and fixed infostations, nodes also communicate amongst themselves whenever they meet. However, this requires cooperation among mobile nodes that are not necessarily spontaneous for commercial applications. We propose means to create opportunistic cooperation in the context of contention distribution in selfish mobile infostation networks. First, we assume that all nodes have a common interest in all files. We stipulate a social contract such that a bilateral file exchange takes place only when either node obtains something it wants from the exchange. Resulting capacity depends on mobility, the number of files being disseminated, and node density. In addition to the existence of multiuser diversity, our results indicate the existence of data diversity-throughput increases as the number of files of interest to all nodes increases. We also consider the case where nodes have dissimilar interests. Results show that as the level of interest overlap decreases, network performance degrades dramatically. We propose an alternate user strategy in the partially overlapping-interests case and show that network throughput is significantly improved by allowing better use of multiuser diversity. We conclude that through opportunistic cooperation, both data and multiuser diversities exist in noncooperative mobile infostation networks.

Dynamic allocation of spectrum prior to transmission is an important feature for next generation wireless networks. In this work, we develop and analyze a model for dynamic spectrum allocation, that is applicable for a broad class of practical systems. We consider multiple service providers (SPs), in the same geographic region, that share a fixed spectrum, on a non-interference basis. This spectrum is allocated to their customer end users for transmission to the SPs. Assuming that a user can obtain service from all the SPs, this work develops an efficient algorithm for spectrum allocation. The quality of service depends on system parameters such as number of users and SPs, the channel conditions between the users and SPs and the total transmit power of each user. The SPs have different efficiencies of reception. We adopt a user utility maximization framework to analyze this system. We develop the notion of spectrum price that enables a simple distributed spectrum allocation with minimal coordination among the SPs and users. Given the user utility functions and the system parameters, we characterize the spectrum price and the users' optimal bandwidth allocations. Our work provides theoretical bounds on performance limits of practical operator to user based dynamic spectrum allocation systems and also gives insights to actual system design.

Energy harvesting from the working environment has received increasing attention in the research of wireless sensor networks. Recent developments in this area can be used to replenish the power supply of sensors. However, power management is still a crucial issue for such networks due to the uncertainty of stochastic replenishment. In this paper, we propose a generic mathematical framework to characterize the policy for single hop transmission over a replenishable sensor network. Firstly, we introduce a Markov chain model to describe different modes of energy renewal. Then, we derive the optimal transmission policy for sensors with different energy budgets. Depending on the energy status of a sensor and the reward for successfully transmitting a message, we prove the existence of optimal thresholds that maximize the average reward rate. Our results are quite general since the reward values can be made application-specific for different design objectives. Compared with the unconditional transmit-all policy, which transmits every message as long as the energy storage is positive, the proposed optimal transmission policy is shown to achieve significant gains in the average reward rate.

Network simulation packages such as NS-2 and OPNET have been shown to be a limited option for cross-layer experimentation in wireless networking because they cannot faithfully capture the propagation and interference characteristics of wireless channels [1]. Recent research on network cross-layer optimizations further raises this concern due to the close interaction between physical layer feedback and higher layer protocols. To overcome this shortcoming, wireless testbeds have been used wherein novel protocols and application concepts can be assessed in a realistic environment under controlled and repeatable conditions. Since average signal-to-noise-ratio (SNR) often determines the performance of a wireless link, our goal is to seek link SNR mapping methods that replicate real-world link SNRs onto an indoor testbed. Specifically, we devise and assess link SNR mapping methodologies for two different applications: hierarchical networks with a fixed access point (AP), and mesh networks. For the AP-based networks, we employ the minimum weight matching algorithm to minimize the root-mean-square (RMS) mapping error between the testbed and real-world SNRs. For the mesh networks, to avoid the technical difficulties inherent in “forward mapping”, we develop a “reverse mapping” method by which we turn a testbed configuration with specified link SNRs into a real-world configuration. By inducing the link gain difference between the testbed and the real-world distance-dependent path loss to have a log-normal distribution, a very close approximation to real-world shadow fading is achieved. We present results for a variety of indoor and outdoor real-world scenarios to demonstrate the generality of our method.

In the planning of large-scale distributed wireless networks, the knowledge about the link gain matrix is required to facilitate a better match between system design and channel characteristics. Nevertheless, stochastic path loss models fail to produce an accurate estimation of link gains since they cannot faithfully capture the propagation characteristics of a specific environment. Furthermore, exhaustive measurement of all links in a large-scale network is unrealistic due to the complexity involved. This motivates us to develop an accurate link gain estimation methodology based on a small fraction of measurements. We propose here to partition all transmit-receive links into mutually exclusive categories - with each category defined by the number of obstructions on the direct path - and then derive a separate link gain model (equivalently, pathloss model) for each category. Thus, for each category, one would measure only a subset of all transmit-receive paths (selected on the basis of a "maximum entropy" principle) and, for each such path, record the link gain and distance. A least-squares linear fit of dB gain vs. long-distance for the measured links produces the model for that category, which can then be used to predict the remaining "unmeasured" path gains. We use ray- tracing programs to evaluate this approach for different network geometries, and we discuss its superiority to spatial interpolation methods for determining the network's link gains.

We study the formation of ad-hoc networks among selfish energy-constrained wireless devices that are primarily interested in beingconnectedwith other devices. We use a non-cooperative bilateral connection game (BCG) framework to study network formation. For a BCG in which devices choose their individual strategies to remain connected by minimizing only their direct transmission power costs, we show that the price-of-anarchy is unbounded in the network size. We propose a BCG with an alternate cost structure in which each device additionallypaysthe transmission power costs incurred by other devices for its own traffic. We show that a unique network structure emerges in this game that is stable as well as socially efficient. We then study the achievable throughput for random point-to-point traffic in this stable energy-efficient network. When the nodes of a network are located in a bounded planar region the distribution of point- to-point flows through the nodes exhibits a scale-free behavior.

We derive an outer bound for the secrecy capacity region of a class of one-sided interference channel. The transmitters are assumed to be trustworthy while the message is secure against the non-intended receiver. The outer bound is applied to a deterministic channel in which the outer bound is showed to be tight, and to a Gaussian one-sided interference channel where a scheme is proposed that can come within one bit of the outer bound.

We examine secret communication over interference channels, starting with a model in which communication is semi-secret in that secrecy may depend on other transmitters to follow an agreed-upon signaling strategy. We compare this to robustly-secret communication, in which each user must allow for other users to deviate unilaterally from an agreed-upon strategy to enable better overhearing, as long as that alternate strategy impairs neither the secrecy rate of its own link nor the reliability of any other communicating links. For a particular two-user binary expansion deterministic interference channel, we find and compare the semi-secret and robustly-secret capacity regions.

The eight papers in this special issue focus on delay and disruption tolerant wireless communication. The papers cover routing and network coding for spare mobile ad hoc networks, cross-layer design for sensor networks, satellite communication, and DTN architectural issues.

We studyinformation-theoretic securityfor discrete memorylessinterferenceandbroadcastchannels with independent confidential messages sent to two receivers. Confidential messages are transmitted to their respective receivers while ensuring mutual information-theoretic secrecy. That is, each receiver is kept in total ignorance with respect to the message intended for the other receiver. The secrecy level is measured by the equivocation rate at the eavesdropping receiver. In this paper, we present inner and outer bounds on secrecy capacity regions for these two communication systems. The derived outer bounds have an identical mutual information expression that applies to both channel models. The difference is in the input distributions over which the expression is optimized. The inner bound rate regions are achieved byrandom binningtechniques. For the broadcast channel, adouble-binningcoding scheme allows for both joint encoding and preserving of confidentiality. Furthermore, we show that, for a special case of the interference channel, referred to as theswitchchannel, derived bounds meet. Finally, we describe several transmission schemes for Gaussian interference channels and derive their achievable rate regions while ensuring mutual information-theoretic secrecy. An encoding scheme in which transmitters dedicate some of their power to createartificial noiseis proposed and shown to outperform both time-sharing and simple multiplexed transmission of the confidential messages.

We consider a cognitive radio system like the future 802.22 networks where license-exempt service providers (SPs) will share a fixed spectrum in a non-interference basis to each other and also to the licensed users in that spectrum. The percentage of spectrum utilized by one SP depends on how many users it is serving and how much spectrum each user application demands. We assume that an user can obtain service from all the SPs. The quality of service depends on system parameters such as number of users and SPs, the channel conditions between the users and SPs and the total power available at each user. We adopt an user utility maximization framework to analyze this system. Given the user utility functions, and the above mentioned system parameters we derive optimal values of spectrum that the users should obtain from the SPs. We also introduce the notion of spectrum price and use it to demonstrate several key results about spectrum allocation. The spectrum price proves to be the regulatory mechanism that brings about coordination amongst the SPs with minimal control messaging. Our approach thus strikes a balance between a centralized network and a fully uncoordinated open access network.

We investigate optimum zero-forcing beamforming in multiple antenna broadcast channels with per-antenna power constraints. We show that standard zero-forcing techniques, such as the Moore-Penrose pseudo-inverse, considered mainly in the context of sum-power constrained systems are suboptimal when there are per-antenna power constraints. We formulate convex optimization problems to find the optimum zero-forcing beamforming vectors. Our results indicate that optimizing the antenna outputs based on the per-antenna constraints may improve the rate considerably when the number of transmit antennas is larger the number of receive antennas. Having more transmit antennas gives rise to additional signal space dimensions that may be exploited effectively to reduce transmit power at particular antennas with limited power budget.

We investigate the achievable secrecy rate with Gaussian random codes when the main channel is an AWGN channel, while the eavesdropper's channel is Rayleigh fading with additive Gaussian noise. Several transmission strategies according to the main channel's relative channel gain are proposed and evaluated. We show that even if the main channel channel gain is arbitrarily worse than the eavesdropper's average channel gain, positive secrecy rate can still be achieved with artificial noise injection and a burst signaling strategy.

Capacity regions are established for several two-sender, two-receiver channels with partial transmitter cooperation. First, the capacity regions are determined for compound multiple- access channels (MACs) with common information and compound MACs with conferencing. Next, two interference channel models are considered: an interference channel with common information (ICCI) and an interference channel with unidirectional cooperation (ICUC) in which the message sent by one of the encoders is known to the other encoder. The capacity regions of both of these channels are determined when there is strong interference, i.e., the interference is such that both receivers can decode all messages with no rate penalty. The resulting capacity regions coincide with the capacity region of the compound MAC with common information.

We quantify the ultimate performance limits of inter-cell coordinatation in a cellular downlink network. The goal is to achieve fairness by maximizing the minimum rate in the network subject to per base power constraints. We first solve the max-min rate problem for a particular zero-forcing dirty paper coding scheme so as to obtain an achievable max-min rate, which serves as a lower bound on the ultimate limit. We then obtain a simple upper bound on the max-min rate of any scheme, and show that the rate achievable by the zero-forcing dirty paper coding scheme is close to this upper bound. We also extend our analysis to coordinated networks with multiple antennas.

We consider a centralized Spectrum Server that coordinates the transmissions of a group of links sharing a common spectrum. Links employ on-off modulation with fixed transmit power when active. In the on state, a link obtains a data rate determined by the signal-to-interference ratio on the link. With knowledge of the link gains in the network, the spectrum server schedules the on/off periods of the links so as to satisfy constraints on link fairness and efficiency. We express fairness constraints as lower bounds on the average minimum rate for each link. Efficiency constraints are expressed as lower bounds on the ratio of the average rate to the average transmit power for each link. Subject to fairness and efficiency constraints, the spectrum server finds a schedule that maximizes the average sum rate. Using a graph theoretic model for the network and a linear programming formulation, the resulting schedules are a collection of time shared transmission modes (sets of active links). In the special case when there is no minimum rate constraint, varying the efficiency constraint can cause the optimal policy to vary from a fixed dominant mode with highest sum rate being operated all the time to time sharing among singleton modes in which just one link is active. We also address the case of maximum common rate scheduling under efficiency constraints. Simulation results are presented to substantiate our findings.

A multiple-access channel is considered in which messages from one encoder are confidential. Confidential messages are to be transmitted with perfect secrecy, as measured by equivocation at the other encoder. The upper bounds and the achievable rates for this communication situation are determined.

We compare the rates of one-shot and iterative conferencing in a cooperative Gaussian relay channel. The relay and receiver cooperate via a conference, as introduced by Willems, in which they exchange a series of communications over orthogonal links. Under one-shot conferencing, decode-and-forward (DF) is capacity-achieving when the relay has a strong channel. On the other hand, Wyner-Ziv compress-and-forward (CF) approaches the cut-set bound when the conference link capacity is large. To contrast with one-shot conferencing, we consider a two-round iterative conference scheme; it comprises CF in the first round, and DF in the second. When the relay has a weak channel, the iterative scheme is disadvantageous. However, when the relay channel is strong, iterative cooperation, with optimal allocation of conferencing resources, outperforms one-shot cooperation provided that the conference link capacity is large. When precise allocation of conferencing resources is not possible, we consider iterative cooperation with symmetric conference links, and show that the iterative scheme still surpasses one-shot cooperation, albeit under more restricted conditions.

This work examines a transmission system which adapts a finite set of code rates and a continuously varying transmit power. We propose a technique for finding the average reliable throughput (ART)-maximizing policy satisfying an average power constraint for a slow fading additive white Gaussian noise (AWGN) channel. ART is a measure motivated by the information outage and can, for example, be argued to characterize the long-term average throughput of a data packet transmission system with a transmit queue and a feedback protocol which requests retransmission of erroneously received packets. Given the size of the code rate set L, the ART-maximizing policy has the following properties. 1. For a given set of code rates, the optimum allocation policy suggests quantizing the fading state space into a set of L+1 corresponding intervals. For each quantization interval the optimal policy specifies a minimum transmitted power assignment which guarantees zero information outage. The optimum average power assignments across quantization intervals have a waterfilling relationship with respect to the interval channel quality measure. 2. The joint optimization of quantization intervals and the corresponding rate assignments are shown to have multiple local maxima. Nevertheless, this optimization problem can be reduced to a simple one-dimensional search over a parameter which determines the outage interval. Numerical results show that, in a Rayleigh-fading channel, there is only a 1-dB gap between the ergodic capacity and the throughput of a two-rate adaptive transmission system when the throughput is less than 6 bits/s/Hz. A special case of our optimal policy assignment is the optimal power and rate policy for an adaptive M-QAM system.

We investigate optimum rate assignment scheme maximizing network throughput on the downlink of a multirate CDMA wireless network. Systems employing orthogonal variable spreading factor (OVSF) codes as well as systems employing multiple codes have been studied. Our objective is to maximize the network throughput under constraints on total transmit power, total bandwidth and individual QoS requirements specified in terms of minimum rates. First, users are ordered based on their transmit energy per bit requirements to achieve the target received energy per bit to interference power spectral density ratio at the receivers. Based on the initial ordering, we prove that for systems employing multiple codes, greedy rate assignment yields maximum network throughput. For systems employing variable spreading codes, we show that greedy rate assignment is optimal if the minimum rate requirement of a user is larger than or equal to the minimum rate requirement of any other user with a larger transmit energy per bit requirement. Simulation results verify the superiority of the greedy algorithm under various system and channel assumptions

A multi-access problem is considered where two encoders wish to communicate their messages to two decoders. The encoders can further cooperate via a conference, as introduced by Willems for multi-access channels. The capacity region of this channel is shown to be the intersection of the capacity regions of two multi-access channels with partially cooperating encoders

We consider cooperative data multicast in a wireless network with the objective to maximize the network lifetime. We present the maximum lifetime accumulative broadcast (MLAB) algorithm that specifies the nodes' order of transmission and transmit power levels. We prove that the solution found by MLAB is optimal but not necessarily unique. The power levels found by the algorithm ensure that the lifetimes of the active relays are the same, causing them to fail simultaneously. For the same battery levels at all the nodes, the optimum transmit powers become the same. The simplicity of the solution is made possible by allowing the nodes that are out of the transmission range of a transmitter to collect the energy of unreliably received overheard signals. As a message is forwarded through the network, nodes will have multiple opportunities to reliably receive the message by collecting energy during each retransmission. We refer to this cooperative strategy as accumulative multicast. Cooperative multicast not only increases the multicast energy-efficiency by allowing for more energy radiated in the network to be collected, but also facilitates load balancing by relaxing the constraint that a relay has to transmit with power sufficient to reach its most disadvantaged child. When the message is to be delivered to all network nodes this cooperative strategy becomes accumulative broadcast (Maric and Yates, 2002). Simulation results demonstrate that cooperative broadcast significantly increased network lifetime compared with conventional broadcast. We also present the distributed MLAB algorithm for accumulative broadcast that determines the transmit power levels locally at the nodes.

The service outage based allocation problem explores variable-rate transmission schemes and combines the concepts of ergodic capacity and outage capacity for fading channels. A service outage occurs when the transmission rate is below a given basic rate r/sub o/. The allocation problem is to maximize the expected rate subject to the average power constraint and the constraint that the outage probability is less than /spl epsi/. A general class of probabilistic power allocation schemes is considered for an M-parallel fading channel model. The optimum power allocation scheme is derived and shown to be deterministic except at channel states of a boundary set. The resulting service outage achievable rate ranges from 1-/spl epsi/ of the outage capacity up to the ergodic capacity with increasing average power. Two near-optimum schemes are also derived by exploiting the fact that the outage probability is usually small. The second near-optimum scheme significantly reduces the computational complexity of the optimum solution; moreover, it has a simple structure for the implementation of transmission of mixed real-time and non-real-time services.

For reliable and unreliable forwarding in a parallel-relay network that allows orthogonal transmissions, we maximize the achievable rate under the total power constraint over all nodes. In such a network, the energy cost per information bit [S. Verdu, 1990] during the reliable forwarding is minimized in the wideband regime. For the wideband decode-and-forward (DF) strategy, we show that the optimum parallel-relay solution is to send the data through one relay that is in the "best" position. On the other hand, as observed in [B.E. Schein, 2001], the benefit of unreliable amplify-and-forward (AF) strategy diminishes in the wideband regime. We characterize the optimum bandwidth for AF and show that transmitting in the optimum bandwidth allows the network to operate in the linear regime where the achieved rate increases linearly with transmit power. We identify the best subset of AF relay nodes and characterize the optimum power allocation per dimension among relays.

We address the minimum-energy broadcast problem under the assumption that nodes beyond the nominal range of a transmitter can collect the energy of unreliably received overheard signals. As a message is forwarded through the network, a node will have multiple opportunities to reliably receive the message by collecting energy during each retransmission. We refer to this cooperative strategy as accumulative broadcast. We seek to employ accumulative broadcast in a large scale loosely synchronized, low-power network. Therefore, we focus on distributed network layer approaches for accumulative broadcast in which loosely synchronized nodes use only local information. To further simplify the system architecture, we assume that nodes forward only reliably decoded messages. Under these assumptions, we formulate the minimum-energy accumulative broadcast problem. We present a solution employing two subproblems. First, we identify the ordering in which nodes should transmit. Second, we determine the optimum power levels for that ordering. While the second subproblem can be solved by means of linear programming, the ordering subproblem is found to be NP-complete. We devise a heuristic algorithm to find a good ordering. Simulation results show the performance of the algorithm to be close to optimum and a significant improvement over the well known BIP algorithm for constructing energy-efficient broadcast trees. We then formulate a distributed version of the accumulative broadcast algorithm that uses only local information at the nodes and has performance close to its centralized counterpart.

For a symbol-asynchronous (but chip-synchronous) single-cell code-division multiple-access (CDMA) system, we define a system-wide quantity called the total squared asynchronous correlation (TSAC) which, for arbitrary signature sets, depends on the users' delay profile. We develop a lower bound for TSAC that is independent of the users' delays. We show that if the signature set achieves this TSAC lower bound, then the user capacity of the asynchronous CDMA system using matched filters becomes the same as that of a single-cell synchronous CDMA system; in this case, there is no loss in user capacity due to asynchronism. We present iterative signature adaptation algorithms, which, when executed sequentially by the users, appear to converge to these optimum signature sequences; however, the existence, for all user delay profiles, of signature sequences achieving this lower bound remains a significant open problem.

Without perfect channel state information at the transmitter, it is possible for adaptive transmission systems to experience information outage. In this paper, we formulate the throughput maximization with both an average power constraint and an information outage constraint. It is verified that, for the optimal transmission policy, the transmission only needs to adapt to a sufficient statistic for the channel state. For a Rayleigh fading channel with a simple training scheme, numerical results show that, with a reasonable amount of training and a small set of code rates, the adaptive transmission can achieve a performance very close to the ergodic capacity.

The service outage based allocation problem explores variable rate transmission schemes and combines the concepts of ergodic capacity and capacity versus outage for fading channels. A service outage occurs when the transmission rate is below a given basic rate r/sub o/. The allocation problem is to maximize the expected rate subject to the average power constraint and the constraint that the outage probability is less than /spl epsiv/. A general class of probabilistic power allocation schemes is considered in this problem. In an M-parallel fading channel model, the optimum power allocation scheme is derived and is shown to be deterministic except at channel states of a boundary set. The resulting service outage average rate is between the outage capacity times 1-/spl epsiv/ and the ergodic capacity.

A mobile infostation network stipulates all transmissions to occur when nodes are in proximity. In this paper, the effect of transmit range on the capacity of four transmission strategies is studied. We show that a stipulated transmit range improves the capacity compared to the Grossglauser-Tse strategy with an unconstrained transmit range by 25%, and outperforms the non rate-adaptive strategy by 68%. This indicates an optimal trade-off exists between spatial transmission concurrency and spectral efficiency on individual links. The optimal number of neighbors is invariant to node density, and is between 0.6 to 1.2 for our transmission strategies. This should be contrasted to a magic number of 6 to 8 neighbors for multihop networks, where the expected forward progress per hop is maximized. This reflects the different optimization criteria of mobile infostation and multihop ad hoc networks. In addition, the capacity per unit area increases linearly with node density. This is counter-intuitive but can be explained using a rescaling argument drawn from percolation theory.

A mobile infostation network stipulates all transmissions to occur when nodes are in proximity. We evaluate the effect of mobility on highway mobile infostation networks. Each node enters a highway segment at a Poisson rate with a constant speed drawn from a known but arbitrary distribution. Both forward and reverse traffic are considered. For node speed that is uniformly distributed, the expected fraction of connection time, or expected number of connections in queueing terminology, is independent of observer node speed for reverse traffic, while it increases with observer node speed for forward traffic. We also extend our mobility model such that each node changes speed at each highway segment. The long run fraction of connection time of an observer node is dependent on the ratio of transmit range and connection time limit. Forward traffic connection yields better performance when the ratio is small and vice versa. We also compute the optimal transmit range and the corresponding data rate for both traffic types. We conclude that forward traffic connections yield much higher data rate in most scenarios.

In wireless networks, it is often assumed that all nodes cooperate to relay packets for each other. Although this is a plausible model for military or mission based networks, it is unrealistic for commercial networks and future pervasive computing environments. We address the issue of noncooperation between nodes in the context of content distribution in mobile infostation networks. We assume all nodes have common interest in all files cached in the fixed infostations. In addition to downloading files from the fixed infostations, nodes act as mobile infostations and exchange files when they are in proximity. We stipulate a social contract such that an exchange occurs only when each node can obtain something it wants from the exchange. Our social contract enables much higher system efficiency compared to downloading from fixed infostations only while not requiring true cooperation among nodes. We show by analysis and simulations that network performance depends on the node density, mobility and the number of files that are being disseminated. Our results point to the existence of data diversity for mobile infostation networks. The achievable throughput increases as the number of files of interest to all users increases. We have also extended the common interest model to the case where nodes have dissimilar interests. Our simulation results show that as mobile nodes change from having identical interests to mutually exclusive interests, the network performance degrades dramatically. We propose an alternative user strategy when nodes have partially overlapping interests and show that the network capacity can be significantly improved by exploiting multiuser diversity inherent in mobile infostation networks. We conclude that data diversity and multiuser diversity exist in noncooperative mobile infostation networks and can be exploited.

In a mobile infostation network, any two nodes communicate when they are in proximity. Under this transmission constraint, any pair of nodes is intermittently connected as mobility shuffles the node locations. In this paper, we evaluate the effect of node mobility on highway mobile infostation networks. Each node enters a highway segment at a Poisson rate with a random speed drawn from a known but arbitrary distribution. Moreover, each node changes speed at each highway segment. Since nodes have different speed, a node may overtake other nodes or be overtaken as time evolves. Using arguments from renewal reward theory, the long run fraction of time an observer node is connected, and the long run average data rate can be derived. In this paper, however, we consider the special case of no speed change in each highway segment. In this case, the performance metrics are functions of the observer node speed. We consider both forward traffic scenarios, in which two nodes moving in the same direction have a transient connection when they are within range from each other, and reverse traffic scenarios in which two nodes travelling in opposite directions are connected transiently when they are in range. For node speed that is uniformly distributed, we reveal that the expected fraction of connection time, or expected number of connections in queuing terminology, is independent of the observer node speed in reverse traffic. In forward traffic, on the other hand, the fraction of connection time increases with observer speed. That is, the network performance improves with node mobility, which is unique to the mobile infostation networking paradigm.

We propose a rate scheduling algorithm to maximize the network throughput of a variable data rate CDMA system and prove its optimality. The system uses OVSF (orthogonal variable spreading factor) codes and the algorithm finds the optimum rate assignments on the binary code tree under constraints on the total transmit power and minimum QoS (rate) requirement of each user. The algorithm is optimal in the sense that it maximizes the total network throughput within the constraints and achieves this with minimum possible power. The algorithm works in a greedy fashion and has a polynomial time complexity of O(N), where N is the number of users. We also extend our results to a more general set of combinatorial optimization problems where the user rates can be any integer multiples of a basic rate (such as multi-code CDMA), not necessarily the set of rates on the binary tree structure, but the optimal solutions are still greedy achievable.

In wireless networks, it is often assumed that all nodes cooperate to relay packets for each other. Although this is a plausible model for military or mission-based networks, it is unrealistic for commercial networks and future pervasive computing environments. We address the issue of noncooperation between nodes in the context of content distribution in mobile infostation networks. All nodes have common interest in all files cached in the fixed infostations. In addition to downloading files from the fixed infostations, nodes act as mobile infostations and exchange files when they are in proximity. We stipulate a social contract such that an exchange occurs only when each node can obtain something it wants from the exchange. We show by analysis and simulations that network performance depends on node density, mobility and the number of files that are being disseminated. Our results point to the existence of data diversity for mobile infostation networks. As the number of files of interest to all users increases, the achievable throughput increases. Moreover, each user has a fairer share of the total network throughput. In particular, the transmission of each channel is only limited by contention, indicating the noncooperation strategy achieves near optimum resource utilization.

Throughput maximization of an adaptive transmission system with a finite number of transmission power levels and code rates for communication over slow fading channels is analyzed, based on the concept of information outage. Properties of throughput maximizing policies lead to an iterative algorithm that yields good system designs. Numerical results show that carefully designed discrete adaptive transmission systems with a small number of power levels and code rates can achieve throughput values close to ergodic capacity.

This article combines the concepts of ergodic capacity and capacity versus outage for fading channels, and explores variable-rate transmissions under a service outage constraint in a block flat-fading channel model. A service outage occurs when the transmission rate is below a given basic rate. We solve the problem of maximizing the expected rate subject to the average power constraint and the service outage probability constraint. When the problem is feasible, the optimum power policy is shown to be a combination of water filling and channel inversion allocation, where the outage occurs at a set of channel states below a certain threshold. The service outage approach resolves the conflicting objectives of high average rate and low outage probability.

This work examines an adaptive transmission system that supports a discrete set of code rates and continuously variable transmit power. Based on the concept of information outage, we maximize the system throughput over a slow fading channel. Properties of the throughput maximizing policies result in an iterative algorithm that yields good system designs. Numerical results show that in a Rayleigh fading channel, there is only a gap of 1 dB between the ergodic capacity and the throughput of a 2-rate adaptive transmission system when the throughput is less than 4 bits/sec/Hz.

For a multicell code-division multiple-access (CDMA) system, we propose a partial decorrelator that decodes a user by suppressing only the in-cell interferers. As a result, each user suffers only from other-cell interference and enhanced receiver noise. By analysis, we show that in random CDMA systems, the partial decorrelator outperforms the conventional receiver, within the operating regime of the conventional receiver. In simulation, we observe that when users have equal received powers at their respective receivers, a multicell system with partial decorrelator receivers yields roughly 1.5 times the capacity of the conventional system.

The optimum receiver to detect the bits of multiple code-division multiple access (CDMA) users has an exponential complexity in the number of active users in the system. Consequently, many suboptimum receivers have been developed to achieve good performance with less complexity. We take the approach of approximating the solution of the optimum multiuser detection problem (OMUD) using nonlinear programming relaxations. First, we observe that some popular suboptimum receivers indeed correspond to relaxations of the optimal detection problem. In particular, one proposed approximation method yields to iterative solutions which correspond to previously proposed heuristic nonlinear detectors. Using a nonlinear programming approach, we identify the convergence properties of these iterative detectors. Secondly, we propose a relaxation that yields a receiver which we call the generalized minimum mean squared error detector. We give a simple iterative implementation of the detector. Its performance is evaluated and comparisons to other suboptimum detection schemes are given.

Motivated by the emergence of programmable radios, we seek to understand a new class of communication system where pairs of transmitters and receivers can adapt their modulation/demodulation method in the presence of interference to achieve better performance. Using signal to interference ratio as a metric and a general signal space approach, we present a class of iterative distributed algorithms for synchronous systems which results in an ensemble of optimal waveforms for multiple users connected to a common receiver (or colocated independent receivers). That is, the waveform ensemble meets the Welch (1974) bound with equality and, therefore, achieves minimum average interference over the ensemble of signature waveforms. We derive fixed points for a number of scenarios, provide examples, look at ensemble stability under user addition and deletion as well as provide a simplistic comparison to synchronous code-division multiple-access. We close with suggestions for future work.

In this work, we address optimal adaptive transmission policies in slow varying wireless environments. Continuous rate and power assignments that achieve the ergodic capacity for these channels have been derived previously. Nevertheless, from a practical point of view, use of a finite number of power and rate levels is imperative. Here, we address the mapping from channel states of an arbitrary distribution to a discrete set of power level and code rate pairs. Unlike earlier work, our design does not require that the transmitter knows the exact value of the current channel state. We show that our design yields results close to the well-known water-filling result.

We characterize the user capacity, i.e., the maximum number of supportable users at a common SIR target level for a fixed processing gain, of a single-cell symbol asynchronous CDMA system. We show that the user capacity of an asynchronous system is the same as the user capacity of a synchronous system; that is there is no loss in user capacity due to asynchrony. Optimum signature sequences are those that minimize the total squared asynchronous correlation (TSAC) among the users, and depend on users' delay profile. Optimum received powers of the users are equal, and the optimum linear receiver filters in any observation window of size M/spl ges/1 symbols (i.e., M-shot MMSE filters) are one-shot matched filters. We present iterative and distributed signature adaptation algorithms where, at each iteration, only one user updates its signature sequence to decrease the TSAC of the set.

This paper evaluates the performance of an MC-MFSK (multicarrier multilevel frequency shift keying) based system in the presence of Rayleigh fading. MC-MFSK is a new spread spectrum multiple access technology with the desirable properties of frequency diversity, near-far resistance, and multipath resolvability. The MC-MFSK scheme transmits a symbol in parallel over multiple sub-channels using OFDM (orthogonal frequency division multiplexing). We assume that each sub-channel has an independent flat fading process. Since the MC-MFSK receiver employs threshold detection, the selection of a suitable threshold is also discussed. Finally, comparisons with other MFSK-based spread spectrum systems are made to demonstrate the higher capacity of this new scheme.

Among the ambitious challenges to be met by the third-generation systems is to provide high-capacity flexible services. Code-division multiple access (CDMA) emerges as a promising candidate to meet these challenges. It is well known that CDMA systems are interference-limited, and interference management is needed to maximally utilize the potential gains of this access scheme. Several methods of controlling and/or suppressing the interference through power control, multiuser detection (temporal filtering), and receiver beamforming (spatial filtering) have been proposed to increase the capacity of CDMA systems up to date. We investigate the capacity increase that is possible by combining power control with intelligent temporal and spatial receiver filter design. The signal-to-interference ratio maximizing joint temporal-spatial receiver filters in unconstrained and constrained filter spaces are derived. Two-step iterative power control algorithms that converge to the optimum powers and the joint temporal and spatial receiver filters in the corresponding filter domains are given. A power control algorithm with a less complex filter update procedure is also given. We observe that significant savings in total transmit power are possible if filtering in both domains is utilized compared with conventional power control and joint optimal power control and filtering in only one domain.

Optimum signature sequence sets that maximize the capacity of single-cell synchronous code division multiple access (CDMA) systems have been identified. Optimum signature sequences minimize the total squared correlation (TSC); they form a set of orthogonal sequences, if the number of users is less than or equal to the processing gain, and a set of Welch (1994) bound equality (WBE) sequences, otherwise. We present an algorithm where users update their transmitter signature sequences sequentially, in a distributed fashion, by using available receiver measurements. We show that each update decreases the TSC of the set, and produces better signature sequence sets progressively. We prove that the algorithm converges to a set of orthogonal signature sequences when the number of users is less than or equal to the processing gain. We observe and conjecture that the algorithm converges to a WBE set when the number of users is greater than the processing gain. At each step, the algorithm replaces one signature sequence from the set with the normalized minimum mean squared error (MMSE) receiver corresponding to that signature sequence. Since the MMSE filter can be obtained by a distributed algorithm for each user, the proposed algorithm is amenable to distributed implementation.

We consider connectionless packet switched CDMA systems where all users have to share a common bandwidth and signature sequence on a contention basis. Multiple access is achieved by the simultaneous acquisition of different users' spread spectrum transmissions. The throughput of a pure random access system of this kind suffers from acquisition errors and timing mismatches of the active users as well as instability issues. We consider schemes that use information available at the physical layer, i.e., at the output of the multiuser access detector (MUAD) designed for this random access system, to improve and stabilize the throughput. We consider timing randomization, pseudo-Bayesian stabilization and collision resolution algorithms and report the corresponding numerical results.

This paper studies the effects of user mobility and handoff path rerouting on the traffic distributions in a mobile network environment. In mobile ATM networks, extra traffic load may be added to network links due to user mobility and handoff path rerouting. This requires higher network link capacity and possible topology reengineering in order to support the same quality of service (QoS) for mobile services. To capture the dynamic variations in mobile ATM networks, we propose to use a flow model. The model represents the mobile-generated traffic as a set of stochastic flows over a set of origin-destination (OD) pairs. The user mobility is defined by transfer probabilities of the flows and the handoff path rerouting algorithm is modeled by a transformation between the routing functions for traffic flows. The analysis shows that user mobility may cause temporal variations as well as smoothing effects on the network traffic. Using the flow network model, typical handoff path rerouting algorithms are evaluated through both analytical and experimental approaches. The evaluation methodology can be used for either redesigning the network topology for a given path rerouting algorithm or selecting a path rerouting algorithm for a given network topology under a specific mobile service scenario.

This paper examines truncated window decorrelators for an asynchronous direct-sequence code-division multiple-access system supporting users transmitting at different bit rates. We decode a user by extending the observation window over a sufficient number of its bits. To characterize practical window sizes, simple upper and lower bounds for the asymptotic efficiency of both the truncated window and infinite window decorrelators are developed. Empirical results show that as the length of the observation window increases, the bounds converge rapidly to the asymptotic efficiency of the infinite window decorrelator. The complexity of the receiver depends strongly on the ratio of the maximum to minimum bit rates.

For code-division multiple-access (CDMA) wireless systems employing multiuser detection, the varied bit-error rate (BER) requirements of multimedia traffic dictate the use of transmitted power control. Using a decorrelator in an asynchronous multirate direct-sequence CDMA system, it may be necessary for different users to combat the noise enhancement and the propagation losses to varying degrees depending on individual requirements. In this context, we propose a power control algorithm for a multirate decorrelator that is suitable for a class of BER-based link quality objectives. If the uplink channel gain of the desired user is known, then it is straightforward for each user to choose the transmitted power needed to meet its target BER objective. In practice, however, the uplink channel gain is often difficult to measure. To avoid this measurement, we employ stochastic approximation methods to develop a simple iterative power control algorithm. In this algorithm, each mobile uses the output of its own decorrelator to update its transmitted power in order to achieve its BER objective. We show that when a user's bits have nonzero asymptotic efficiencies, the power control algorithm converges quickly in the mean square sense to the minimum power at which a user achieves its quality-of-service objective.

This paper studies mobile-generated traffic distributions in mobile ATM networks and evaluates the performance of path rerouting algorithms for handoff control. In mobile ATM networks, user mobility and handoff path rerouting may produce extra traffic load over network links, requiring larger network capacity to support the same QoS. We propose a flow model for mobile ATM networks. The model represents the mobile-generated traffic as a set of stochastic flows over a set of OD (origin-destination) pairs. The user mobility is defined by transfer probabilities of the flows and the handoff path rerouting algorithm is modeled by a transformation between the routing functions for traffic flows. The analysis shows that user mobility may cause temporal variations as well as smoothing effects on the network traffic. Using the flow network model, typical handoff path rerouting algorithms are evaluated through both analytical and experimental approaches. The evaluation methodology can be used for either redesigning the network topology for a given path rerouting algorithm or selecting a path rerouting algorithm for a given network topology under a specific mobile service scenario.

We address the use of existing cellular infrastructure as the location for Infostations, an array of isolated wireless ports delivering wireless data services. The coverage area of an Infostation, though, will be smaller than the cell area. We determine the worst-case SIR as a function of the coverage-radius-to-cell-radius ratio and the frequency-reuse cluster size. For specific modulation schemes, we identify desirable operating points and calculate the Infostations' utilization.

This paper studies handoff control mechanisms based on a 'mobile ATM' concept. Mobile ATM refers to an ATM infrastructure which supports ubiquitous mobile services through extending ATM signaling functions within the ATM backbone. In order to meet the performance criteria required by a diverse set of mobile services, we propose a unified handoff control protocol which is independent of wireless access technologies (ATM/nonATM) and path rerouting algorithms. Such a protocol can provide (1) a common software architecture for system implementation, (2) a common measurement base for performance evaluation and (3) a common signaling syntax for standardization. A prototype system is implemented based on this protocol, which provides an IP-over-ATM service with WaveLAN access.

The decorrelating detector is known to eliminate multiaccess interference when the signature sequences of the users are linearly independent, at the cost of enhancing the Gaussian receiver noise. We present a blind adaptive decorrelating detector which is based on the observation of readily available statistics. The algorithm recursively updates the filter coefficients of a desired user by using the output of the current filter. Due to the randomness of the information bits transmitted and the ambient Gaussian channel noise, the filter coefficients evolve stochastically. We prove the convergence of the filter coefficients to a decorrelating detector in the mean squared error (MSE) sense. We develop lower and upper bounds on the MSE of the receiver filter from the convergence point and show that with a fixed step size sequence, the MSE can be made arbitrarily small by choosing a small enough step size. With a time-varying step size sequence, the MSE converges to zero implying an exact convergence. The proposed algorithm is distributed, in the sense that no information about the interfering users such as their signature sequences or power levels is needed. The algorithm requires the knowledge of only two parameters for the construction of the receiver filter of a desired user: the desired user's signature sequence and the variance of the additive white Gaussian (AWG) receiver noise. This detector, for an asynchronous code division multiple access (CDMA) channel, converges to the one-shot decorrelating detector.

For wireless communication systems, iterative power control algorithms have been proposed to minimize the transmitter power while maintaining reliable communication between mobiles and base stations. To derive deterministic convergence results, these algorithms require perfect measurements of one or more of the following parameters: (1) the mobile's signal-to-interference ratio (SIR) at the receiver; (2) the interference experienced by the mobile; and (3) the bit-error rate. However, these quantities are often difficult to measure and deterministic convergence results neglect the effect of stochastic measurements. We develop distributed iterative power control algorithms that use readily available measurements. Two classes of power control algorithms are proposed. Since the measurements are random, the proposed algorithms evolve stochastically and we define the convergence in terms of the mean-squared error (MSE) of the power vector from the optimal power vector that is the solution of a feasible deterministic power control problem. For the first class of power control algorithms using fixed step size sequences, we obtain finite lower and upper bounds for the MSE by appropriate selection of the step size. We also show that these bounds go to zero, implying convergence in the MSE sense, as the step size goes to zero. For the second class of power control algorithms, which are based on the stochastic approximations method and use time-varying step size sequences, we prove that the MSE goes to zero. Both classes of algorithms are distributed in the sense that each user needs only to know its own channel gain to its assigned base station and its own matched filter output at its assigned base station to update its power.

This paper proposes a signature assignment technique for a dual rate DS/CDMA system that serves both low bit rate and high bit rate users. In an interval of duration T/sub 0/, a low rate user transmits one bit while a high rate user transmits M bits. Under the new signature sequence assignment technique, M low rate users share the signature of a single high rate user without wasting bandwidth. Based on the signature assignment technique, we propose a decorrelator that generates bit decisions for each high rate user in every subinterval of duration T/sub 0//M. In order to decode a low rate user, an orthogonal projection is applied to M separate decorrelated outputs of each low rate user. It is observed that applying a standard decorrelator to the interval of duration T/sub 0/ yields a computational complexity that grows with M. The proposed decorrelator significantly reduces the computational complexity of the standard decorrelator. Due to the structural simplicity, the proposed receiver slightly suffers in terms of bit error rate. However, it is observed that in several cases, the proposed receiver achieves the standard decorrelator performance.

Power control algorithms assume that the receiver structure is fixed and iteratively update the transmit powers of the users to provide them with an acceptable quality of service while minimizing the total transmitter power. Multiuser detection on the other hand optimizes the receiver structure with the assumption that the users have fixed transmitter powers. In this study, we combine the two approaches for a CDMA cellular system and propose an iterative and distributed power control algorithm which iteratively updates the transmitter powers and receiver filter coefficients of the users. We show that the algorithm converges to a minimum power solution for the powers, and an MMSE multiuser detector for the filter coefficients.

In packet reservation multiple access (PRMA) the receiver in the mobile terminal is required to listen continuously to monitor the acknowledgment messages broadcasted at the end of every time slot. A new scheme for the integration of voice and data based on PRMA is proposed. The voice and the data subsystems are logically separated. The total available bandwidth is divided into three regions-voice information, voice contention, and data regions. The available bandwidth is dynamically partitioned between the above three regions subject to the fulfillment of the quality of service (QoS) requirements of the voice users. The voice subsystem has been modeled as a Markov chain and an exact analytical method used to compute the voice packet dropping probability is described. A nonlinear programming problem is formulated to optimize the bandwidth allocated for the data users. Solutions to this nonlinear programming problem that are very close to optimum have been obtained heuristically. Numerical results indicate that a significant amount of data traffic can be supported without sacrificing the voice capacity of the system.

Previous work has shown that a handoff algorithm based on SIR alone (SIR based handoff) prohibits handoffs near nominal cell boundaries, causing cell dragging and unnecessarily high transmitter powers. We propose the minimum power handoff (MPH) algorithm in which mobiles constantly search for a combination of base and channel assignment that minimizes the uplink transmitted power. This algorithm is shown to reduce the average power level by 4dB compared to SIR based handoff. Results show that using received power as a handoff criterion reduces call dropping but increases the number of unnecessary handoffs significantly. To avoid a "ping pong" effect, a timer is introduced to delay the intercell handoff.

A new scheme for the integration of voice and data based on PRMA is proposed. The voice and the data subsystems are logically separated. The total available bandwidth is divided into three regions-voice information, voice contention, and data regions. The bandwidth available for the data users depends on the fulfilling of the QOS requirements for the voice users, which is assumed to be a limit on the number of dropped voice packets. The voice subsystem has been modeled as a Markov chain and an optimization problem to maximize the bandwidth allocated for the data users has been formulated. Numerical results indicate that a significant amount of data traffic can be supported without sacrificing the voice capacity of the system.

In cellular wireless communication systems, transmitted power is regulated to provide each user an acceptable connection by limiting the interference caused by other users. Several models have been considered including: (1) fixed base station assignment where the assignment of users to base stations is fixed, (2) minimum power assignment where a user is iteratively assigned to the base station at which its signal to interference ratio is highest, and (3) diversity reception where a user's signal is combined from several or perhaps all base stations. For the above models, the uplink power control problem can be reduced to finding a vector p of users' transmitter powers satisfying p/spl ges/I(p) where the jth constraint p/sub j//spl ges/I/sub j/(p) describes the interference that user j must overcome to achieve an acceptable connection. This work unifies results found for these systems by identifying common properties of the interference constraints. It is also shown that systems in which transmitter powers are subject to maximum power limitations share these common properties. These properties permit a general proof of the synchronous and totally asynchronous convergence of the iteration p(t+1)=I(p(t)) to a unique fixed point at which total transmitted power is minimized.>

The authors describe a multilayer connection control architecture for broadband communications. A graph framework is introduced to describe network layers of network design, path configurations, dynamic call routing, burst switching, and asynchronous transfer mode (ATM) cell switching. These hierarchical layers of switching are performed at decreasing time scales, respectively. Switching at the higher layer is performed to reduce blocking at the next smaller time scale. A layered notion of equivalent bandwidth for satisfying layered grade-of-service parameters is introduced for making connections at these time scales. The authors then focus on the path configuration layer. Two path setup methods, namely, physical and virtual path setup, are described. Mathematical programs minimizing path bandwidth usage subject to meeting grade-of-service requirements are formulated for both methods. The relative merits of these methods are compared. In one example, physical path setup is shown to require roughly 50% more bandwidth than virtual path setup.>

Alternative structures for the optimum detection of Gaussian signals in Gaussian noise are derived that can be interpreted in terms of minimum-mean-squared-error (MMSE) estimators of signal and noise. The realization is useful when the statistics of the signal or noise or both are unknown since the detector can be implemented in an adaptive mode by using tapped delay lines whose weights are adjusted recursively to yield the minimum-mean-squared-error estimate of certain components of the incoming waveforms.