This paper studies a continuous-time joint sampling-and-preemption problem, incorporating sampling and preemption penalties under general service-time distributions. We formulate the system as an impulse-controlled piecewise-deterministic Markov process (PDMP) and derive coupled integral average-cost optimality equations via the dynamic programming principle, thereby avoiding the smoothness assumptions typically required for an average-cost Hamilton-Jacobi-Bellman quasi-variational inequality (HJB-QVI) characterization. A key invariance in the busy phase collapses the dynamics onto a one-dimensional busy-start boundary, reducing preemption control to an optimal stopping problem. Building on this structure, we develop an efficient policy iteration algorithm with heavy-tail acceleration, employing a hybrid (uniform/log-spaced) action grid and a far-field linear closure. Simulations under Pareto and log-normal service times demonstrate substantial improvements over AoI-optimal non-preemptive sampling and zero-wait baselines, achieving up to a 30x reduction in average cost in heavy-tailed regimes. Finally, simulations uncover a counterintuitive insight: under preemption, delay variance, despite typically being a liability, can become a strategic advantage for information freshness.

We study a setting where an intelligent model (e.g., a pre-trained neural network) infers the real-time value of a target signal using data samples transmitted from a remote source. The transmission scheduler decides (i) the freshness of packets, (ii) their length (i.e., the number of samples they contain), and (iii) when they should be transmitted. The freshness is quantified using the Age of Information (AoI), and the inference quality for a given packet length is a general function of AoI. Previous works assumed i.i.d. transmission delays with immediate feedback or were restricted to the case where inference performance degrades as the input data ages. Our formulation, in addition to capturing non-monotone age dependence, also covers Markovian delay on both forward and feedback links. We model this as an infinite-horizon average-cost Semi-Markov Decision Process. We obtain a closed-form solution that decides on (i) and (iii) for any constant packet length. The solution for when to transmit is an index-based threshold policy, where the index function is expressed in terms of the delay state and AoI at the receiver. In contrast, the freshness of the selected packet is a function of only the delay state. We then separately optimize the value of the constant packet length. Moreover, we also develop an indexbased threshold policy for the time-variable packet length case, which allows a complexity reduction. In simulation results, we observe that our goal-oriented scheduler drops inference error down to one-sixth with respect to the age-based scheduling of unit-length packets.

This study focuses on downlink transmissions of a low earth orbit (LEO) satellite, assisted by a beyond diagonal reconfigurable intelligent surface (BD-RIS) to serve ground terminals. Toward optimizing the performance of this system, we formulate the minimization of the average age of information (AoI) achieved at ground terminals. Our formulation respects the power budget of the LEO satellite and guarantees the quality-of-service of ground terminals by optimizing the downlink transmit power at the LEO satellite and reflection coefficients at the BD-RIS as decision variables. Owing to its non-convex and tightly-coupled nature, we reformulate the problem as a Markov decision process which effectively captures its dynamics. Next, a Q-learning propagation (Q-Prop) agent is trained to optimize the decision variables. In light of the mobility of ground terminals as well as LEO satellite, this communication system is highly dynamic. Therefore, we enhance the trained Q-Prop model with meta-learning strategy, which augments its adaptability and generalization to system variances. Numerical results indicate that, in comparison to RIS-lacking and RIS-assisted counterparts, our optimised solution achieves 38% and 26% lower average AoI, respectively.

In this paper, we extend the freshness-oriented sampling problem by incorporating controlled delay statistics through heterogeneous routing options, where the Age of Information (AoI) serves as the metric for data freshness. Our objective is to jointly optimize sampling and routing policies to minimize the long-term average AoI, where the sender can choose to forward each status update over one of the available routes, which have distinct delay statistics. This problem is an infinite-horizon Semi-Markov Decision Process (SMDP) with an uncountable state space and a hybrid action space, consisting of discrete routing choices and continuous waiting times. We develop an efficient algorithm to solve this problem and theoretically establish that the optimal policy exhibits a threshold structure, characterized by: (i) a threshold-based monotonic handover mechanism for optimal routing, where the switching order aligns with the decreasing order of mean delays; and (ii) a multi-threshold piecewise linear waiting mechanism for optimal sampling, where the total number of thresholds is upper bounded by 2N – 1, given N selectable routes. We implement the proposed algorithm in a satellite-terrestrial integrated routing scenario, and simulation results reveal an intriguing insight: routes with higher average delay or variance can still contribute to minimizing AoI.

We study the design of a goal-oriented sampling and scheduling strategy through a channel with highly variable two-way random delay, which can exhibit memory (e.g., Delay and Disruption Tolerant Networks). The objective of the communication is to optimize the performance of remote inference, where an inference algorithm (e.g., a trained neural network) on the receiver side predicts a time-varying target signal using the data samples transmitted by a sensor. Previous formulations to this problem either assumed a channel with IID transmission delay, neglecting feedback delay or considered the monotonic relation that the performance only gets worse as the input information ages. We show how, with delayed feedback, one can effectively exploit the knowledge about delay memory through an index-based threshold policy. This policy minimizes the expected time-average inference error that can be monotone or non-monotone in age. The index function is expressed in terms of the Age of Information (AoI) on the receiver side and a parameter regarding the distribution of subsequent transmission delay, both of which can readily be tracked.

URLLC (Ultra-reliable low-latency communication) is one of the more challenging modes for 5G for resource allocation (RA). Most of the previous studies for RA for wireless access in URLLC assumed known packet arrival processes, and focused on maximizing average rates or throughput. The objective of this paper is to present a formulation of allocating resource blocks, modulation and coding rates to multiple short packet machine-type information flows to provide information age and delay violation guarantees. The scenario is motivated by the scheduling of URLLC flows among users served by a common 5G base station. The problem involves the selections of frequency allocation policy and modulation and coding scheme (MCS) under estimated CSI. Moreover, the sensitivity of the information packet size on the choice of modulation and coding parameters as well as the number of resource blocks and the choice of the number of pilot symbols is demonstrated. The results of this formulation are compared with resource allocation algorithms in the literature.

We introduce Mini Slotted ALOHA and MuMiSTA as novel reservation based random access policies focused on the scalable and timely delivery of status updates in a dense network. In mini slotted ALOHA, each data slot is preceded by multiple mini slots and active users compete for the use of the data slot, by becoming the only user to transmit in one of the mini slots. MuMiSTA is an age-aware modification of mini slotted ALOHA where the set of active users is limited to the users with age larger than a fixed threshold. Users with smaller ages do not congest the channel while conserving energy. In this paper, we derive the throughput of mini slotted ALOHA along with the set of optimal parameters, under finite and infinite node assumptions. We express the ideal number of mini slots in terms of the throughput, depending on the ratio between the lengths of the data slot and the mini slot. A steady state distribution of the number of active nodes under MuMiSTA is derived and an efficient method of obtaining MuMiSTA parameters is described. It is shown that it can approach a ideal round-robin policy with a throughput of 1. In a practical scenario, MuMiSTA is shown to achieve a throughput increase of 141% over slotted ALOHA, and an average AoI reduction by 79%.

This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. We study a communication system in which a source node is to send status updates over a channel to a remote destination. The update packets will be received error-free, however the channel imposes independent and identically distributed transmission delay on each transmission. The destination node will utilize the upcoming update packets at certain instants that are referred to as query instants. The Query Age of Information (QAoI) at the destination is defined to be the time-average Age of Information (AoI) measured at query instants. We define the problem where the receiver decides when to send requests to "pull" data from the source, to minimize the QAoI, as the pull-or-wait (PoW) problem. We contrast the solution of the PoW problem with that of the update-or-wait (UoW) problem, where the source decides when to generate updates to minimize the time-average AoI. We show that when the query instants occur according to a Poisson process, the solution of the PoW problem is equivalent to that of the UoW problem; however, under periodic query arrivals, the optimal QAoI is always less than or equal to the time average AoI under the same power constraint. We believe this motivates using QAoI as an objective instead of plain AoI in many applications requiring time-sensitive updates.

We introduce minislotted threshold ALOHA (MiSTA), a slotted ALOHA modification designed to minimize the network-wide time average Age of Information (AoI). In MiSTA, sources whose ages are below a certain threshold stay silent. A node with the age above the threshold becomes active in the next time frame with a certain probability. The active node first transmits a short control sequence in a minislot ahead of actual data transmission, and if collision is sensed, it backs off with a certain probability. We derive the steady-state distribution of the number of active sources and analyze its limiting behavior. We show that MiSTA probabilistically converges to a enquote thinned slotted ALOHA, where the number of active users at steady state adjusts to optimize age. With an optimal selection of parameters, MiSTA achieves an AoI scaling with the number of sources,$n$, as$0.9641n$, which is an improvement over the threshold ALOHA policy proposed earlier (for which the lowest possible scaling is$1.4169n$). While achieving this reduction in age, MiSTA also increases the theoretically achievable throughput to approximately 53%, from the 37% achievable by threshold ALOHA and regular slotted ALOHA.

A communication receiver that wants to pull data from a remote sensor by exploiting wireless energy transfer is considered. The receiver has a long-term average energy budget for this operation, and its goal is to keep the time average of a general age penalty function as small as possible. The channel from the source to the receiver is a two-state (ON/OFF) communication link whose state is IID or Markovian, and known instantaneously by the receiver. Modeling the problem as a constrained Markov decision problem, we obtain a randomized threshold-based decision policy that achieves the minimum possible average age penalty. We determine the optimal time average Age of Information and age violation probabilities by exploiting the optimality of the derived policy.

We present a comprehensive steady-state analysis of threshold-ALOHA, a distributed age-aware modification of slotted ALOHA proposed in recent literature. In threshold-ALOHA, each terminal suspends its transmissions until the Age of Information (AoI) of the status update flow it is sending reaches a certain threshold Γ. Once the age exceeds Γ, the terminal attempts transmission with constant probability τ in each slot, as in standard slotted ALOHA. We analyze the time-average expected AoI attained by this policy, and explore its scaling with network size, n. We derive the probability distribution of the number of active users at steady state, and show that as network size increases the policy converges to one that runs slotted ALOHA with fewer sources: on average about one fifth of the users is active at any time. We obtain an expression for steady-state expected AoI and use this to optimize the parameters Γ and τ, resolving the conjectures in previous literature by confirming that the optimal age threshold and transmission probability are 2.2n and 4.69/n, respectively. We find that the optimal AoI scales with the network size as 1.4169n, which is almost half the minimum AoI achievable with slotted ALOHA, while the loss from the maximum throughput of e-1remains below 1%. We compare the performance of this rudimentary algorithm to that of the SAT policy [2] that dynamically adapts its transmission probabilities.

We consider the problem of tracking an unstable stochastic process Xtby using causal knowledge of another stochastic process Yt. We obtain necessary conditions and sufficient conditions for maintaining a finite tracking error. We provide necessary conditions as well as sufficient conditions for the success of this estimation, which is defined as order m moment trackability. By-products of this study are connections between statistics such as Rényi entropy, Gallager’s reliability function, and the concept of anytime capacity.

In this paper, we consider a problem of sampling a Wiener process, with samples forwarded to a remote estimator over a channel that is modeled as a queue. The estimator reconstructs an estimate of the real-time signal value from causally received samples. We study the optimal online sampling strategy that minimizes the mean square estimation error subject to a sampling rate constraint. We prove that the optimal sampling strategy is a threshold policy, and find the optimal threshold. This threshold is determined by how much the Wiener process varies during the random service time and the maximum allowed sampling rate. Further, if the sampling times are independent of the observed Wiener process, the above sampling problem for minimizing the estimation error is equivalent to a sampling problem for minimizing the age of information. This reveals an interesting connection between the age of information and remote estimation error. Our comparisons show that the estimation error achieved by the optimal sampling policy can be much smaller than those of age-optimal sampling, zero-wait sampling, and periodic sampling.

This paper investigates the probability that the delay and the peak-age of information exceed a desired threshold in a point-to-point communication system with short information packets. The packets are generated according to a stationary memoryless Bernoulli process, placed in a single-server queue and then transmitted over a wireless channel. A variable-length stop-feedback coding scheme-a general strategy that encompasses simple automatic repetition request (ARQ) and more sophisticated hybrid ARQ techniques as special cases-is used by the transmitter to convey the information packets to the receiver. By leveraging finite-blocklength results, the delay violation and the peak-age violation probabilities are characterized without resorting to approximations based on larg-deviation theory as in previous literature. Numerical results illuminate the dependence of delay and peak-age violation probability on system parameters such as the frame size and the undetected error probability, and on the chosen packet-management policy. The guidelines provided by our analysis are particularly useful for the design of low-latency ultra-reliable communication systems.

We study the problem of minimizing the time-average expected Age of Information for status updates sent by an energy-harvesting source with a finite-capacity battery. In prior literature, optimal policies were observed to have a threshold structure under Poisson energy arrivals, for the special case of a unit-capacity battery. In this paper, we generalize this result to any (integer) battery capacity, and explicitly characterize the threshold structure. We provide the expressions relating the threshold values on the age to the average age. One of these results, that we derive from these expressions, is the unexpected equivalence of the minimum average AoI and the optimal threshold for the highest energy state.

This paper investigates the distribution of delay and peak age of information in a communication system where packets, generated according to an independent and identically distributed Bernoulli process, are placed in a single-server queue with first-come first-served discipline and transmitted over an additive white Gaussian noise (AWGN) channel. When a packet is correctly decoded, the sender receives an instantaneous error-free positive acknowledgment, upon which it removes the packet from the buffer. In the case of negative acknowledgment, the packet is retransmitted. By leveraging finite-blocklength results for the AWGN channel, we characterize the delay violation and the peak-age violation probability without resorting to approximations based on large deviation theory as in previous literature. Our analysis reveals that there exists an optimum blocklength that minimizes the delay violation and the peak-age violation probabilities. We also show that one can find two blocklength values that result in very similar average delay but significantly different delay violation probabilities. This highlights the importance of focusing on violation probabilities rather than on averages.

We consider a fading communication link where the transmitter is powered by the receiver through wireless energy transfer (WET). A typical application scenario for this is the transmitter being a simple sensor while the demand for data is created by an application running at the receiver side and pulled from the transmitter as needed. We formulate two offline transmission scheduling problems: the transmitter-centric WET transmission optimization problem, where the schedule is computed by the transmitter, and the receiver-centric WET transmission optimization problem, where the receiver computes the schedule. We provide explicit solutions of both problems and propose online policies that rely on using the estimated water level values for each case. Our formulation allows direct optimization of energy efficiency in contrast to other EH transmission scheduling formulations in the literature. We prove some equivalence results under the special case of fixed channels.

In this paper, we consider a wireless broadcast network with a base station sending time-sensitive information to a number of clients through unreliable channels. The Age of Information (AoI), namely the amount of time that elapsed since the most recently delivered packet was generated, captures the freshness of the information. We formulate a discrete-time decision problem to find a transmission scheduling policy that minimizes the expected weighted sum AoI of the clients in the network. We first show that in symmetric networks, a greedy policy, which transmits the packet for the client with the highest current age, is optimal. For general networks, we develop three low-complexity scheduling policies: a randomized policy, a Max-Weight policy and a Whittle's Index policy, and derive performance guarantees as a function of the network configuration. To the best of our knowledge, this is the first work to derive performance guarantees for scheduling policies that attempt to minimize AoI in wireless networks with unreliable channels. Numerical results show that both the Max-Weight and Whittle's Index policies outperform the other scheduling policies in every configuration simulated, and achieve near optimal performance.

We present the project SpEnD, a complete SPARQL endpoint discovery and analysis portal. In a previous study, the SPARQL endpoint discovery and analysis steps of the SpEnD system were explained in detail. In the SpEnD portal, the SPARQL endpoints are extracted from the web by using web crawling techniques, monitored and analyzed by live querying the endpoints systematically. After many sustainability improvements in the SpEnD project, the SpEnD system is now online as a portal. SpEnD portal currently serves 1487 SPARQL endpoints, out of which 911 endpoints are uniquely found by SpEnD only when compared to the other existing SPARQL endpoint repositories. In this portal, the analytic results and the content information are shared for every SPARQL endpoint. The endpoints stored in the repository are monitored and updated continuously.

Age of Information is a measure of the freshness of status updates in monitoring applications and update-based systems. We study a real-time sensing scenario with a sensor which is restricted by time-varying energy constraints and battery limitations. The sensor sends updates over a packet erasure channel with no feedback. The problem of finding an age-optimal threshold policy, with the transmission threshold being a function of the energy state and the estimated current age, is formulated. The average age is analyzed for the unit battery scenario under a memoryless energy arrival process. Somewhat surprisingly, for any finite arrival rate of energy, there is a positive age threshold for transmission, which corresponding to transmitting at a rate lower than that dictated by the rate of energy arrivals. A lower bound on the average age is obtained for general battery size.

In this paper, we consider a problem of sampling a Wiener process, with samples forwarded to a remote estimator via a channel that consists of a queue with random delay. The estimator reconstructs a real-time estimate of the signal from causally received samples. Motivated by recent research on age-of-information, we study the optimal sampling strategy that minimizes the mean square estimation error subject to a sampling frequency constraint. We prove that the optimal sampling strategy is a threshold policy, and find the optimal threshold. This threshold is determined by the sampling frequency constraint and how much the Wiener process varies during the channel delay. An interesting consequence is that even in the absence of the sampling frequency constraint, the optimal strategy is not zero-wait sampling in which a new sample is taken once the previous sample is delivered; rather, it is optimal to wait for a non-zero amount of time after the previous sample is delivered, and then take the next sample. Further, if the sampling times are independent of the observed Wiener process, the optimal sampling problem reduces to an age-of-information optimization problem that has been recently solved. Our comparisons show that the estimation error of the optimal sampling policy is much smaller than those of age-optimal sampling, zero-wait sampling, and classic uniform sampling.

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

In this paper, energy-efficient transmission schemes achieving maximal throughput over a finite time interval are studied in a problem setting, including energy harvests, data arrivals, and channel variation. The goal is to express the offline optimal policy in a way that facilitates a good online solution. We express any throughput maximizing energy-efficient offline schedule (EE-TM-OFF) explicitly in terms of water levels. This allows per-slot real-time evaluation of transmit power and rate decisions, using estimates of the associated offline water levels. To compute the online power level, we construct a stochastic dynamic program that incorporates the offline optimal solution as a stochastic process. We introduce the immediate fill measure, which provides a lower bound on the efficiency of any online policy with respect to the corresponding optimal offline solution. The online algorithms obtained this way exhibit performance close to the offline optimal, not only in the long run but also in short problem horizons, deeming them suitable for practical implementations.

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.

Lazy scheduling, i.e. setting transmit power and rate in response to data traffic as low as possible while satisfying delay constraints, is a known formulation of energy efficient transmission. Solutions exist for offline and infinite-horizon online versions of the problem. This paper addresses the finite horizon online transmission scheduling problem under stochastic packet arrival, energy harvesting and channel variation processes. The main contribution is a mechanism to obtain an online algorithm using explicit closed form expressions of the derived offline optimal policy. The resulting low complexity online algorithm attains near-optimal performance, not only asymptotically, but also in the practically interesting short term.

A single-hop network where a fusion center (FC) collects data from a set of energy harvesting nodes is considered. If a node that is scheduled has data and sufficient energy, it makes a successful transmission. Otherwise, the channel allocated to the node remains idle. The goal is to make efficient use of channel resources in order to either (1) use all the energy that is harvested by nodes, or (2) stabilize all data buffers. In the absence of feedback from nodes about buffers or battery states, or prior knowledge of the statistics of energy harvest and data arrival processes, this is a Restless Multi-Armed Bandit (RMAB) problem. Despite the hardness of RMAB problems in general, a simple randomized policy achieves near optimality for this problem under a broad class of arrival processes for unlimited battery capacity. Moreover, there is almost no loss of optimality under a reasonable-sized finite battery assumption.

This paper considers a single-hop wireless network where a fusion center (FC) collects data from a set of m energy harvesting (EH) sensors. In each time slot, k of m nodes can be scheduled by the FC for transmission over k communication channels. FC has no knowledge about the EH processes and current battery states of sensors; however, it knows the outcomes of previous transmission attempts. Also, battery leakage is ignored since it is very small. The objective is to find a low complexity scheduling policy that maximizes the total throughput of the data backlogged system for general case of EH process in finite or infinite horizon. A low-complexity and near-optimal policy UROP (Uniformizing Random Ordered Policy) is proposed for a general case of EH process under infinite battery assumption. Simulations indicate that under a reasonable-sized finite battery assumption, there is almost no loss in throughput.

This paper considers the allocation of time slots in a frame, as well as power and rate to multiple receivers on an energy harvesting downlink. Energy arrival times that will occur within the frame are known at the beginning of the frame. The goal is to optimize throughput in a proportionally fair way, taking into account the inherent differences of channel quality among users. Analysis of structural characteristics of the problem reveals that it can be formulated as a biconvex optimization problem, and that it has multiple optima. Due to the biconvex nature of the problem, a Block Coordinate Descent (BCD) based optimization algorithm that converges to an optimal solution is presented. However, finding the optimal allocation with BCD entails a computational complexity that increases sharply in terms of the number of users or slots. Therefore, certain structural characteristics of the optimal power-time allocation policy are derived. Building on those, two simple and computationally scalable heuristics, PTF and ProNTO are proposed. Simulation results suggest that PTF and ProNTO can closely track the performance of BCD which achieves a good balance between total throughput and fairness.

Information-theoretic broadcast channels (BCs) and multiple-access channels (MACs) enable a single node to transmit data simultaneously to multiple nodes, and multiple nodes to transmit data simultaneously to a single node, respectively. In this paper, we address the problem of link scheduling in multihop wireless networks containing nodes with BC and MAC capabilities. We first propose an interference model that extends protocol interference models, originally designed for point-to-point channels, to include the possibility of BCs and MACs. Due to the high complexity of optimal link schedulers, we introduce the Multiuser Greedy Maximum Weight algorithm for link scheduling in multihop wireless networks containing BCs and MACs. Given a network graph, we develop new local pooling conditions and show that the performance of our algorithm can be fully characterized using the associated parameter, the multiuser local pooling factor. We provide examples of some network graphs, on which we apply local pooling conditions and derive the multiuser local pooling factor. We prove optimality of our algorithm in tree networks and show that the exploitation of BCs and MACs improve the throughput performance considerably in multihop wireless networks.

We consider the minimization of packet transmission duration on an energy harvesting broadcast channel (BC). Energy and data arrivals are assumed to occur at arbitrary but known instants. An achievable rate region with structural properties satisfied by the two-user AWGN BC capacity region is assumed. Structural properties of power and rate allocation in an optimal policy are established, as well as the uniqueness of the optimal policy under the condition that all the data of the “weaker” user are available at the beginning. An iterative algorithm, DuOpt, based on block coordinate descent that achieves the same structural properties as the optimal is described.

The minimization of transmission completion time for a given number of bits per user in an energy harvesting communication system, where energy harvesting instants are known in an offline manner is considered. An achievable rate region with structural properties satisfied by the 2-user AWGN Broadcast Channel capacity region is assumed. It is shown that even though all data are available at the beginning, a non-negative amount of energy from each energy harvest is deferred for later use such that the transmit power starts at its lowest value and rises as time progresses. The optimal scheduler ends the transmission to both users at the same time. Exploiting the special structure in the problem, the iterative offline algorithm, FlowRight, from earlier literature, is adapted and proved to solve this problem. The solution has polynomial complexity in the number of harvests used, and is observed to converge quickly on numerical examples.

This paper presents a wireless multicast tree construction algorithm, SWIM (Source-initiated WIreless Multicast). SWIM constructs a tree on which each multicast destination has the minimum possible depth (number of hops from the nearest source). It is proved that SWIM is fully distributed, with a worst case complexity upper-bounded by O(N3), and an empirically found average complexity of only O(N2). SWIM forms one shared tree from source(s) to the multicast destinations; yet, as a by-product, it creates a multicast mesh structure by maintaining alternative branches at every tree node, thus providing robustness to link failures. This makes it suitable for both ad hoc networks and access networks with multiple gateways. In terms of minimizing the number of forwarding nodes, SWIM is optimal for unicast and competitive with the state of the art for multicast, outperforming the best known distributed approaches from the literature except for the multicast ad hoc on demand distance vector (MAODV) algorithm. However, simulations of the MAODV algorithm alongside SWIM on a large set of network instances show that the depth minimality of SWIM leads to lower average delay per multicast destination. It is also shown that the delay performance of SWIM is virtually unaffected by the presence of low mobility in the network.

The minimization of transmission completion time for a given number of bits per user in an energy harvesting communication system, where energy harvesting instants are known in an offline manner is considered. An achievable rate region with structural properties satisfied by the 2-user AWGN Broadcast Channel capacity region is assumed. It is shown that even though all data are available at the beginning, a non-negative amount of energy from each energy harvest is deferred for later use such that the transmit power starts at its lowest value and rises as time progresses. The optimal scheduler ends the transmission to both users at the same time. Exploiting the special structure in the problem, the iterative offline algorithm, FlowRight, from earlier literature, is adapted and proved to solve this problem. The solution has polynomial complexity in the number of harvests used, and is observed to converge quickly on numerical examples.

Information theoretic Broadcast Channels (BC) and Multiple Access Channels (MAC) enable a single node to transmit data simultaneously to multiple nodes, and multiple nodes to transmit data simultaneously to a single node respectively. In this paper, we address the problem of link scheduling in multihop wireless networks containing nodes with BC and MAC capabilities. We first propose an interference model that extends protocol interference models, originally designed for point to point channels, to include the possibility of BC and MAC. Due to the high complexity of optimal link schedulers, we introduce the Multiuser Greedy Maximum Weight algorithm for link scheduling in multihop wireless networks containing BCs and MACs. Given a network graph, we develop new local pooling conditions} and show that the performance of our algorithm can be fully characterized using the associated parameter, the multiuser local pooling factor. We provide examples of some network graphs, on which we apply local pooling conditions and derive the multiuser local pooling factor. We prove optimality of our algorithm in tree networks and show that the exploitation of BCs and MACs improve the throughput performance considerably in multihop wireless networks.

In this work we consider the allocation of buffer space to data streams sharing a common high-speed wireless transmitter. As an example, we focus on an OFDMA-based downlink system scenario. Scheduling for maximum throughput has been extensively studied in the literature. However, the practically interesting case of a finite buffer has not been sufficiently addressed before. Especially in the case of overloaded packet queues, the choice of buffer management policy substantially affects the throughput performance. We consider a physicallayer scheduling scheme that allocates users to subcarriers based on channel state, in order to make the most use of multiuser diversity. We then consider optimal buffer partitioning to accommodate the resulting rates. We study the system throughput by simulations. As a benchmark, we also simulate MaxWeight, a well-known cross-layer channel and queue-aware scheduling policy that is throughput-optimal in the absence of a finite buffer constraint. We observe that a suitable buffer management policy with a simple channel-aware queuing policy achieves cross-layer scheduling performance, and can exceed it.

Channel state information (CSI) is important for achieving large rates in MIMO channels. However, in time-varying MIMO channels, there is a tradeoff between the time/energy spent acquiring channel state information (CSI) and the time/energy remaining for data transmission. This tradeoff is accentuated in the MIMO multiple access channel (MAC), since the number of channel vectors to be estimated increases with the number of users. Furthermore, the problem of acquiring CSI is tightly coupled with the problem of exploiting CSI through multiuser scheduling. This paper considers a block-fading MAC with coherence timeT, n uncoordinated users-each with one transmit antenna and the same average power constraint, and a base station withMreceive antennas and no a priori CSI. For this scenario, a training-based communication scheme is proposed and the training and multiuser-scheduling aspects of the scheme are jointly optimized. In the high-SNR regime, the sum capacity of the non-coherent SIMO MAC is characterized and used to establish the SNR-scaling-law optimality of the proposed scheme. In the low-SNR regime, the sum-rate of the proposed scheme is found to decay linearly with vanishing SNR when flash signaling is incorporated. Furthermore, this linear decay is shown to be order-optimal through comparison to the low-SNR sum capacity of the non-coherent SIMO MAC. A by product of these SNR-asymptotic analyses is the observation that non-trivial scheduling (i.e., scheduling a strict subset of trained users) is advantageous at low SNR, but not at high SNR. The sum-rate and per-user throughput are also explored in the large-nand large-Mregimes. Non-coherent capacity, training, multiple access channel, multiuser scheduling, opportunistic scheduling.

We develop and analyze a simple, low-complexity system architecture for scheduling over a Gaussian multiple-input multiple-output (MIMO) broadcast channel with infinite message backlogs. In the system of interest, there is a transmitter with m antennas, and n receiving users, where n Gt m. We show that the proposed architecture is strongly asymptotically optimal with respect to average throughput. We further characterize the feedback requirements of the architecture, and highlight various tradeoffs available to the system designer

For energy-constrained stationary wireless networks of sensors, selection of links with high quality rate helps to ensure reliable long-term operation. During the implementation of a protocol targeting industrial applications of such systems, it was found that it is advantageous to acquire accurate information about the availability and quality of the RF communication links prior to the network topology formation. "Link assessment" as part of the initialization process, accomplishes this task by assessing a sufficient number of packets exchanged between neighboring nodes. This paper introduces and analyzes two different approaches to link assessment: The first approach is a random nondeterministic scheme that allows for a probabilistic guarantee of collision-free packet exchange. An alternative method is described which employs 'constant-weight codes' and provides a deterministic guarantee of success. In particular, a special class of constant-weight codes, known as optical orthogonal codes, are considered. Since, these codes are cyclically permutable, they make the link assessment process simpler, and therefore they are preferred over other codes. We evaluate the performance of these methods based on their energy consumption, time duration, and implementation complexity.

This paper investigates the problem of energy-efficient transmission of data packets in a wireless network by jointly adapting to backlog and channel condition. Specifically, we consider minimum-energy scheduling problems over multiple-access channels, broadcast channels, and channels with fading, when packets of all users need to be transmitted before a deadline T. Earlier work has considered a similar setup and demonstrated significant transmission energy saving by adapting to backlog for channels that are time invariant and when transmission is restricted to time-division. For concreteness, throughout the paper, rates and powers corresponding to optimal coding over discrete-time additive white Gaussian noise (AWGN) channels are assumed. The results, however, hold for more general channels and coding schemes where the total transmitted power is convex in the transmission rates. The offline scheduling problems for all the channels considered are shown to reduce to convex optimization problems with linear constraints. An iterative algorithm, referred to as FlowRight, that finds optimal offline schedules is presented. A heuristic online algorithm that we call look-ahead water-filling, which jointly adapts to both channel fading state and backlog is described. By the use of a small buffer which introduces an almost fixed delay, this algorithm achieves a considerable reduction in energy relative to water filling solely on channel states.

In wireless sensor networks, a good cost metric encapsulating wireless link quality is essential to an energy-efficient routing topology. For many wireless network scenarios, rapid variation in the channel precludes an efficient mechanism for knowing instantaneous link quality at the time of transmission, thus making it difficult to estimate the instantaneous value of the cost metric. This paper explores what a good cost metric may be and how it can be measured in an energy-efficient way. We present an experimental study of wireless link quality variation over a period of several days in a sensor network placed in two different indoor office environments. The nodes are equipped with low power transceivers operating in the 900 MHz band. Results are documented for several different link configurations, i.e., relative placement of the transmitter and receiver. Based on detailed observations of link quality variation, we form quantitative measures of link quality, and propose a cost metric. We find that reasonably few channel measurements are sufficient to obtain a good estimate of the cost metric, hence even during the initialization phase one can obtain sufficient information about links in order to design an efficient topology. The estimate can be improved further as more measurements are taken during the normal operation of the network.

We consider a network of n sender/receiver pairs placed randomly in a region of unit area. Network capacity or maximum throughput is defined as the highest rate that can be achieved by each sender/receiver pair over a long period of time. It is known that without using relays (i.e., via only direct communication), the maximum throughput is less than O(1), that is, strictly decays as n increases. The network capacity without relaying for static or mobile networks is not known. However, a known lower bound on this capacity if O[(log (n))/n]. Our goal is to find a higher achievable rate. We show, by demonstrating a simple coding and scheduling scheme that uses mobility, that O[(log (n))/(n/sup 1/-/spl beta/)] is achievable, where /spl beta/ > 0 is a constant that depends on the power attenuation factor in the wireless medium. For example, when power decays as d/sup -4/ with distance d, O[(log (n))/(n/sup .25/)] is achievable. We assume channels to be AWGN interference channels throughput this work.

The paper explores the adaptation of transmission rate and power jointly to the data generation rate and channel fading, for minimizing transmission energy. The optimal offline adaptation problem is solved, which provides a lower-bound on the transmission energy consumed by any practical, that is, online, scheme. A heuristic online algorithm, look-ahead water-filling, is developed for adapting to the queue state as well as the channel state, and is shown through simulations to achieve transmission energy per packet close to optimal. As the packet arrival rate is varied within known limits, the average energy per packet used by look-ahead water-filling is significantly lower than that achieved by optimal adaptation to the channel only (water-filling in time). The delay per packet is larger, but is almost constant for all data arrival rates. The results can be generalized to multi-access and broadcast fading channels.

The paper develops algorithms for minimizing the energy required to transmit packets in a wireless environment. It is motivated by the following observation: In many channel coding schemes it is possible to significantly lower the transmission energy by transmitting packets over a long period of time. Based on this observation, we show that for a variety of scenarios the offline energy-efficient transmission scheduling problem reduces to a convex optimization problem. Unlike for the special case of a single transmitter-receiver pair studied by (see Prabhakar, Uysal-Biyikoglu and El Gamal. Proc. IEEE Infocom 2001), the problem does not, in general, admit a closed-form solution when there are multiple users. By exploiting the special structure of the problem, however, we are able to devise energy-efficient transmission schedules. For the downlink channel, with a single transmitter and multiple receivers, we devise an iterative algorithm, called MoveRight, that yields the optimal offline schedule. The MoveRight algorithm also optimally solves the downlink problem with additional constraints imposed by packet deadlines and finite transmit buffers. For the uplink (or multiaccess) problem MoveRight optimally determines the offline time-sharing schedule. A very efficient online algorithm, called MoveRightExpress, that uses a surprisingly small look-ahead buffer is proposed and is shown to perform competitively with the optimal offline schedule in terms of energy efficiency and delay.

The paper considers the problem of minimizing the energy used to transmit packets over a wireless link via lazy schedules that judiciously vary packet transmission times. The problem is motivated by the following observation. With many channel coding schemes, the energy required to transmit a packet can be significantly reduced by lowering transmission power and code rate and therefore transmitting the packet over a longer period of time. However, information is often time-critical or delay-sensitive and transmission times cannot be made arbitrarily long. We therefore consider packet transmission schedules that minimize energy subject to a deadline or a delay constraint. Specifically, we obtain an optimal offline schedule for a node operating under a deadline constraint. An inspection of the form of this schedule naturally leads us to an online schedule which is shown, through simulations, to perform closely to the optimal offline schedule. Taking the deadline to infinity, we provide an exact probabilistic analysis of our offline scheduling algorithm. The results of this analysis enable us to devise a lazy online algorithm that varies transmission times according to backlog. We show that this lazy schedule is significantly more energy-efficient compared to a deterministic (fixed transmission time) schedule that guarantees queue stability for the same range of arrival rates.

The paper considers the problem of minimizing the energy used to transmit packets over a wireless link via lazy schedules that judiciously vary packet transmission times. The problem is motivated by the following key observation: in many channel coding schemes, the energy required to transmit a packet can be significantly reduced by lowering the transmission power and transmitting the packet over a longer period of time. However, information is often time-critical or delay-sensitive and transmission times cannot be made arbitrarily long. We therefore consider packet transmission schedules that minimize energy subject to a deadline or a delay constraint. Specifically, we obtain an optimal offline schedule for a node operating under a deadline constraint. An inspection of the form of this schedule naturally leads us to an online schedule which is shown, through simulations, to be energy-efficient. Finally, we relax the deadline constraint and provide an exact probabilistic analysis of our offline scheduling algorithm. We then devise a lazy online algorithm that varies transmission times according to backlog and show that it is more energy efficient than a deterministic schedule that guarantees stability for the same range of arrival rates.