In Reinforcement Learning (RL), tasks with instantaneous hard constraints present significant challenges, particularly when the decision space is non-convex or non-star-convex. This issue is especially relevant in domains like autonomous vehicles and robotics, where constraints such as collision avoidance often take a non-convex form. In this paper, we establish a regret bound of $\tilde{\mathcal{O}}((1 + \tfrac{1}{\tau}) \sqrt{\log(\frac{1}{\tau}) d^3 H^4 K})$, applicable to both star-convex and non-star-convex cases, where $d$ is the feature dimension, $H$ the episode length, $K$ the number of episodes, and $\tau$ the safety threshold. Moreover, the violation of safety constraints is zero with high probability throughout the learning process. A key technical challenge in these settings is bounding the covering number of the value-function class, which is essential for achieving value-aware uniform concentration in model-free function approximation. For the star-convex setting, we develop a novel technique called *Objective–Constraint Decomposition* (OCD) to properly bound the covering number. This result also resolves an error in a previous work on constrained RL. In non-star-convex scenarios, where the covering number can become infinitely large, we propose a two-phase algorithm, Non-Convex Safe Least Squares Value Iteration (NCS-LSVI), which first reduces uncertainty about the safe set by playing a known safe policy. After that, it carefully balances exploration and exploitation to achieve the regret bound. Finally, numerical simulations on an autonomous driving scenario demonstrate the effectiveness of NCS-LSVI.

Reinforcement learning (RL) holds great promise for network control problems, yet its deployment in real-world systems remains limited due to the instability and unpredictability of RL policies during training. To address this challenge, we propose a two-phase conservative RL framework that combines domain expertise from classical network optimization with modern deep RL techniques. Our key idea is to initialize the learning process with a stable base policy, derived from expert knowledge, and then apply conservative fine-tuning under a Kullback–Leibler (KL) divergence constraint to safely explore improved behaviors. We apply this framework to the problem of covert multi-hop routing, where the objective is to optimize data throughput while minimizing detectability by adversaries. In Phase I, we construct a reliable base policy by imitating the back-pressure algorithm, which guarantees throughput-optimal behavior and stable queue dynamics. Phase II fine-tunes this policy to improve covert performance, as measured by the Detection Error Probability (DEP), while preserving training-time stability. Empirical evaluations on a grid network show that our method enables more reliable learning than pure RL. While pure RL (e.g., PPO) can sometimes achieve higher covert performance, it frequently suffers from large queues and collapsed throughput during training. In our experiments, our conservative RL framework reduces the worst-case training-time queue length by over 99% while maintaining comparable covert communication performance.

We consider a real-time monitoring system where a source node (with energy limitations) aims to keep the information status at a destination node as fresh as possible by scheduling status update transmissions over a set of channels. The freshness of information at the destination node is measured in terms of the Age of Information (AoI) metric. In this setting, a natural tradeoff exists between the transmission cost (or equivalently, energy consumption) of the source and the achievable AoI performance at the destination. This tradeoff has been optimized in the existing literature under the assumption of having a complete knowledge of the channel statistics. In this work, we develop online learning-based algorithms with finite-time guarantees that optimize this tradeoff in the practical scenario where the channel statistics are unknown to the scheduler. In particular, when the channel statistics are known, the optimal scheduling policy is first proven to have a threshold-based structure with respect to the value of AoI (i.e., it is optimal to drop updates when the AoI value is below some threshold). This key insight was then utilized to develop the proposed learning algorithms that surprisingly achieve an order-optimal regret (i.e., O(1)) with respect to the time horizon length.

As the demand for vehicle-to-everything communication (V2X) band in the 5.9 GHz increases, the millimeter-wave spectrum offers alternative options in unlicensed or radar-dedicated bands with wider bandwidth. Joint radar-communication (JRC) systems emerge as a comprehensive solution to effectively utilize these bands by integrating both functions within the same waveform and hardware. In this work, we present a multiple-input and multiple-output (MIMO) JRC testbed, operating in the 24 GHz mmWave band, utilizing orthogonal frequency division multiplexing (OFDM) waveform that simultaneously carries data across all subcarriers. In particular, we develop a real-time operating, full-duplex JRC prototype with a fully-digital front-end and software-defined radios, providing enhanced flexibility and capability. Additionally, for systems with high computational power, we introduce a high-resolution range-angle processing method based on the MUSIC algorithm. Through mobile experiments with multiple targets, we showcase simultaneous data transmission and high-resolution radar processing capabilities enabled by the fully-digital MIMO architecture. By leveraging radar’s tracking capability, we propose a radar-assisted precoding approach, offering a low-complexity beamforming solution with reduced feedback overhead. Our experimental results demonstrate that the proposed precoding method achieves comparable performance compared to the conventional precoding method.

Licensed spectrum of Long Term Evolution (LTE) is being strained with the increased traffic demand. To cope with this problem, mobile operators use the unlicensed spectrum to complement the available licensed spectrum. However, using LTE in unlicensed spectrum introduces new problems, such as the coexistence between LTE and other unlicensed communication technologies (e.g., Wi-Fi). This paper proposes a new coexistence mechanism to provide a fair coexistence between LTE and Wi-Fi networks on unlicensed bands. The proposed mechanism assigns resource blocks in eNodeB to LTE users in such a way that it provides efficient and fair usage of unlicensed spectrum for all LTE users and the Wi-Fi networks. We formulate the wireless resource allocation and fair coexistence problem between LTE and Wi-Fi as a non-linear integer programming. Then, we propose an approximation algorithm, which is a Polynomial-Time Approximation Scheme (PTAS), to solve this problem. Our numerical results validate the proposed mechanism's performance vis-a-vis other existing solutions.

Large-scale deployment of connected vehicles with cooperative sensing technologies increases the demand on the vehicular communication spectrum in 5.9 GHz allocated for the exchange of safety messages. To support the high data rates needed by such applications, the millimeter-wave (mmWave) automotive radar spectrum at 76–81 GHz can be utilized for wideband communication as well. For this purpose, various joint automotive radar-communication (JARC) systems have been proposed in the literature to perform both functions using the same wideband waveform. However, the wideband joint waveforms encounter frequency-selectivity in both radar and communication channels due to multi-path propagation. In this paper, we address the optimal joint waveform design problem to exploit the frequency-selectivity for wideband JARC operations via orthogonal frequency-division multiplexing (OFDM) wherein subcarrier coefficients are designed for optimal power allocation and phase coding. We show that the problem is a non-convex quadratically constrained quadratic programming (QCQP) problem which is known to be NP-hard. Existing approaches to solve QCQP include semidefinite relaxation (SDR) which incurs high time complexity. Instead, we propose approximation methods to solve QCQP more efficiently by leveraging structured matrices and using convex approximations. Finally, we demonstrate the efficacy of the proposed approaches through numerical simulations.

Large MIMO transceivers are integral components of next-generation wireless networks. However, for such systems to be practical, their channel estimation process needs to be fast and reliable. Although several solutions for fast estimation of sparse channels do exist, there is still a gap in understanding the fundamental limits governing this problem. Specifically, we need to better understand the lower bound on the number of measurements under which accurate channel estimates can be obtained. This work bridges that knowledge gap by deriving a tight asymptotic lower bound on the number of measurements. This not only helps develop a better understanding for the sparse MIMO channel estimation problem, but it also provides a benchmark for evaluating current and future solutions.

Large-scale deployment of connected vehicles equipped with multiple automotive radar systems increases the demand on both the millimeter-wave (mmWave) automotive radar spectrum in 76–81 GHz and the vehicle-to-everything (V2X) communication spectrum in 5.9 GHz that is mainly allocated for the exchange of safety messages. To supplement V2X communication and support high data rates needed by broadband applications, the automotive radar spectrum with up to 4 GHz of contiguous bandwidth can be leveraged. For this purpose, various joint automotive radar-communication (JARC) systems have been proposed in the literature to perform both functions using the same radio-frequency (RF) signal and transceiver hardware. Combined with the high mobility in traffic, the directionality of RF transmission in mmWave spectrum and interference from other systems prevent JARC systems to achieve optimal communication and radar performance. In this work, we propose a dedicated neighbor discovery and medium access control (MAC) protocol for JARC systems to establish reliable communication links and improve the robustness of radar functionalities without requiring a separate control channel.

Large-scale deployment of connected vehicles with cooperative awareness technologies increases the demand for vehicle-to-everything (V2X) communication spectrum in 5.9 GHz that is mainly allocated for the exchange of safety messages. To supplement V2X communication and support the high data rates needed by broadband applications, the millimeter-wave (mmWave) automotive radar spectrum at 76-81 GHz can be utilized. For this purpose, joint radar-communication systems have been proposed in the literature to perform both functions using the same waveform and hardware. While multiple-input and multiple-output (MIMO) communication with multiple users enables independent data streaming for high throughput, MIMO radar processing provides high-resolution imaging that is crucial for safety-critical systems. However, employing conventional precoding methods designed for communication generates directional beams that impair MIMO radar imaging and target tracking capabilities during data streaming. In this paper, we propose a MIMO joint automotive radar-communication (JARC) framework based on orthogonal frequency division multiplexing (OFDM) waveform. First, we show that the MIMO-OFDM preamble can be exploited for both MIMO radar processing and estimation of the communication channel. Then, we propose an optimal precoder design method that enables high accuracy target tracking while transmitting independent data streams to multiple receivers. The proposed methods provide high-resolution radar imaging and high throughput capabilities for MIMO JARC networks. Finally, we evaluate the efficacy of the proposed methods through numerical simulations.

The speed at which millimeter-Wave (mmWave) channel estimation can be carried out is critical for the adoption of mmWave technologies. This is particularly crucial because mmWave transceivers are equipped with large antenna arrays to combat severe path losses, which consequently creates large channel matrices, whose estimation may incur significant overhead. This paper focuses on the mmWave channel estimation problem. Our objective is to reduce the number of measurements required to reliably estimate the channel. Specifically, channel estimation is posed as a “source compression” problem in which measurements mimic an encoded (compressed) version of the channel. Decoding the observed measurements, a task which is traditionally computationally intensive, is performed using a deep-learning-based approach, facilitating a high-performance channel discovery. Our solution not only outperforms state-of-the-art compressed sensing methods, but it also determines the lower bound on the number of measurements required for reliable channel discovery.

In this paper, we study an optimal user scheduling with minimum beam alignment overhead in millimeter wave networks. The problem is posed as constrained Markov decision process (CMDP) with the goal of minimizing the average beam alignment overhead subject to the average rate constraint on each user. Under a certain assumption on the rate function of the users, by using a structural result derived from the Lagrangian formulation of the CMDP, we show that the optimal policy should keep scheduling the users that are scheduled in the previous time slot unless an abrupt change in the beam direction occurs. Using this result, the complexity of the problem decreases to polynomial in the number of users. In addition, we provide a heuristic deterministic algorithm that achieves$({1}+\epsilon)$approximation of the optimal solution, with smaller$\epsilon $at the cost of longer transmission interval of each user. Lastly, to deal with the case where the assumption on the rate function does not hold due to beam conflicts between the users, we consider a system model that accounts for an angular channel information. A new CMDP is formulated for the problem and a heuristic algorithm based on the age information is proposed.

The emergence of bandwidth-intensive latency-critical traffic in 5G Networks, such as Virtual Reality and Cloud Gaming, has motivated interest in wireless resource allocation problems for flows with hard-deadlines. Attempting to solve this problem brings about the following two key challenges: (i) The flow arrival and the wireless channel state information are not known to the Base Station (BS) apriori, thus, the allocation decisions need to be made in an online manner. (ii) Resource allocation algorithms that attempt to maximize a reward in the wireless setting will likely be unfair, causing unacceptable service for some users. In the first part of this paper, we model the problem of allocating resources to deadline-sensitive traffic as an online convex optimization problem, where the BS acquires a per-request reward that depends on the amount of traffic transmitted within the required deadline. We address the question of whether we can efficiently solve that problem with low complexity. In particular, whether we can design a constant-competitive scheduling algorithm that is oblivious to requests' deadlines. To this end, we propose a primal-dual Deadline-Oblivious (DO) algorithm, and show it is approximately 3.6-competitive. Furthermore, we show via simulations that our algorithm tracks the prescient offline solution very closely, significantly outperforming several algorithms that were previously proposed. Our results demonstrate that even though a scheduler may not know the deadlines of each flow, it can still achieve good theoretical and empirical performance. In the second part, we impose a stochastic constraint on the allocation, requiring a guarantee that each user achieves a certain timely throughput (amount of traffic delivered within the deadline over a period of time). We propose a modified version of our algorithm, called the Long-term Fair Deadline Oblivious (LFDO) algorithm for that setup. We combine the Lyapunov framework for stochastic optimization with the Primal-Dual analysis of online algorithms, to show that LFDO retains the high-performance of DO, while satisfying the long-term stochastic constraints.

Large scale deployment of connected vehicles with cooperative sensing technologies increases the demand on the vehicular communication spectrum in 5.9 GHz allocated for the exchange of safety messages. To support high data rates needed by such applications, the millimeter-wave (mmWave) automotive radar spectrum at 76-81 GHz can be utilized for communication. For this purpose, joint automotive radar-communication (JARC) system designs have been proposed in the literature to perform both functions using the same waveform. However, employing a large band in the mmWave spectrum deteriorates the performance of both radar and communication functions due to frequency-selectivity. In this paper, we address the optimal joint waveform design problem for wideband JARC systems via Orthogonal Frequency-Division Multiplexing (OFDM). We show that the problem is a non-convex quadratically constrained quadratic fractional programming (QCQFP) problem, which is known to be NP-hard. Existing approaches to solve QCQFP include Semidefinite Relaxation (SDR) and randomization approaches, which have high time complexity. Instead, we propose an approximation method to solve QCQFP more efficiently by leveraging structured matrices in the quadratic fractional objective function. Finally, we evaluate the efficacy of the proposed approach through numerical results.

In this paper, we study the effect of predictive caching on the delay of wireless networks. We explore the possibility of caching at wireless end-users where caches are typically very small, orders of magnitude smaller than the catalog size. We develop a predictive multicasting and caching scheme, where the Base Station (BS) in a wireless cell proactively multicasts popular content for end-users to cache, and access locally if requested. We analyze the impact of this joint multicasting and caching on the delay performance. Our analysis uses a novel application of Heavy-Traffic theory under the assumption of vanishing caches to show that predictive caching fundamentally alters the asymptotic throughput-delay scaling. This in turn translates to a several-fold delay improvement in simulations over the on-demand unicast baseline as the network operates close to the full load. We highlight a fundamental delay-memory trade-off in the system and identify the correct memory scaling to fully benefit from the network multicasting gains.

In this paper, we study beam alignment in a millimeter wave (mmWave) network with multiple users, and consider an optimal transmission scheduling algorithm. The problem is posed as an infinite horizon average cost constrained Markov decision process (CMDP) with the goal of minimizing the average beam alignment overhead subject to the average rate constraint on each user. By using a structural result derived from the Lagrangian formulation of the CMDP, we show that the optimal policy should keep scheduling the users that are scheduled in the previous time slot unless an abrupt change in the beam direction happens. Using this result, the complexity of the problem decreases to polynomial in the number of users. We also provide a heuristic deterministic algorithm that achieves (1+ ϵ) approximation of the optimal solution, with smaller ϵ at the cost of longer transmission interval of each user.

The surge in mobile broadband data demands is expected to surpass the available spectrum capacity below 6 GHz. This expectation has prompted the exploration of millimeter wave (mm-wave) frequency bands as a candidate technology for next generation wireless networks. However, numerous challenges to deploying mm-wave communication systems, including channel estimation, need to be met before practical deployments are possible. This paper addresses the mm-wave channel estimation problem and treats it as a beam discovery problem in which locating beams with strong path reflectors is analogous to locating errors in linear block codes. We show that a significantly small number of measurements (compared to the original dimensions of the channel matrix) is sufficient to reliably estimate the channel. We also show that this can be achieved using a simple and energy-efficient transceiver architecture.

The surge in mobile broadband data demands is expected to surpass the available spectrum capacity below 6 GHz. This expectation has prompted the exploration of millimeter wave (mm-wave) frequency bands as a candidate technology for next generation wireless networks. However, numerous challenges to deploying mm-wave communication systems, including channel estimation, need to be met before practical deployments are possible. This work addresses the mm-wave channel estimation problem and treats it as a beam discovery problem in which locating beams with strong path reflectors is analogous to locating errors in linear block codes. We show that a significantly small number of measurements (compared to the original dimensions of the channel matrix) is sufficient to reliably estimate the channel. We also show that this can be achieved using a simple and energy-efficient transceiver architecture.

The rapid growth of mobile data traffic is straining cellular networks. A natural approach to alleviate cellular networks congestion is to use, in addition to the cellular interface, secondary interfaces such as WiFi, Dynamic spectrum and mmWave to aid cellular networks in handling mobile traffic. The fundamental question now becomes: How should traffic be distributed over different interfaces, taking into account different application QoS requirements and the diverse nature of radio interfaces. To this end, we propose the Discounted Rate Utility Maximization (DRUM) framework with interface costs as a means to quantify application preferences in terms of throughput, delay, and cost. The flow rate allocation problem can be formulated as a convex optimization problem. However, solving this problem requires non-causal knowledge of the time-varying capacities of all radio interfaces. To this end, we propose an online predictive algorithm that exploits the predictability of wireless connectivity for a small look-ahead window w. We show that, under some mild conditions, the proposed algorithm achieves a constant competitive ratio independent of the time horizon T. Furthermore, the competitive ratio approaches 1 as the prediction window increases. We also propose another predictive algorithm based on the "Receding Horizon Control" principle from control theory that performs very well in practice. Numerical simulations serve to validate our formulation, by showing that under the DRUM framework: the more delay-tolerant the flow, the less it uses the cellular network, preferring to transmit in high rate bursts over the secondary interfaces. Conversely, delay-sensitive flows consistently transmit irrespective of different interfaces' availability. Simulations also show that the proposed online predictive algorithms have a near-optimal performance compared to the offline prescient solution under all considered scenarios.

In this paper, we consider a jammed wireless scenario where a network operator aims to schedule users to maximize network performance while guaranteeing a minimum performance level to each user. We consider the case where no information about the position and the triggering threshold of the jammer is available. We show that the network performance maximization problem can be modeled as a finite-horizon joint power control and user scheduling problem, which is NP-hard. To find the optimal solution of the problem, we exploit dynamic programming techniques. We show that the obtained problem can be decomposed, i.e., the power control problem and the user scheduling problem can be sequentially solved at each slot. We investigate the impact of uncertainty on the achievable performance of the system and we show that such uncertainty leads to the well-known exploration-exploitation tradeoff. Due to the high complexity of the optimal solution, we introduce an approximation algorithm by exploiting state aggregation techniques. We also propose a performance-aware online greedy algorithm to provide a low-complexity sub-optimal solution to the joint power control and user scheduling problem under minimum quality-of-service requirements. The efficiency of both solutions is evaluated through extensive simulations, and our results show that the proposed solutions outperform other traditional scheduling policies.

Many studies show that the dedicated short range communication band allocated to vehicular communications is insufficient to carry the wireless traffic generated by emerging vehicular applications. A promising bandwidth expansion possibility presents itself through the release of large TV band spectra (i.e., the TV white space spectrum) by the Federal Communications Commission for cognitive access. One primary challenge of the so-called TV white space (TVWS) spectrum access in vehicular networks is the design of efficient channel allocation mechanisms in face of spatial-temporal variations of TVWS channels. In this paper, we address the channel allocation problem for multi-channel cognitive vehicular networks with the objective of system-wide throughput maximization. We show that the problem is an NP-hard non-linear integer programming problem, to which we present three efficient algorithms. We first propose a probabilistic polynomial-time (1-1/e)-approximation algorithm based on linear programming. Next, we prove that the objective function can be written as a submodular set function, based on which we develop a deterministic constant-factor approximation algorithm with a more favorable time complexity. Then, we further modify the second algorithm to improve its approximation ratio without increasing its time complexity. Finally, we show the efficacy of our algorithms through numerical examples.

Many studies show that the dedicated short range communication (DSRC) band is insufficient to carry increasing wireless traffic demands in vehicular networks. The release of TV white space band by the Federal Communications Commission (FCC) for cognitive access provides additional bandwidth to solve the DSRC spectrum scarcity problem. However, FCC requires portable devices to use significantly lower transmitting power than fixed devices, which creates a challenging coexistence environment for portable (e.g., vehicular) and fixed (e.g., IEEE 802.22) networks. In this paper, we address the coexistence problem between a vehicular and an 802.22 network via resource allocation. We first formulate the coexistence problem as a mixed-integer nonlinear programming (MINLP) problem, to which three algorithms are developed. The first algorithm converts the MINLP into a convex program and obtains a near-optimal solution to the initial MINLP. In the other two algorithms, we first convert the MINLP into an integer programming (IP) problem. Then, we solve the linear program relaxation of the IP and obtain a fractional solution. Thereafter, two rounding algorithms are developed to round the fractional solution based on column-sparse packing and dependent rounding techniques, respectively. Finally, we compare the performance of the proposed algorithms with an optimal MINLP solver through numerical examples.

Jamming attacks are able to partially or completely disrupt wireless communications. To overcome such a harmful attack, optimal scheduling of user transmissions should be achieved. Providing effective scheduling policies is a hard task which is made more complicated when reactive jamming attacks triggered by user transmissions are considered and no information about the jammer is available, e.g., the triggering threshold is not known. In this paper, we address the problem of maximizing network performance and guaranteeing minimum QoS requirements when reactive jamming attacks are ongoing. Specifically, to maximize network performance and avoid the triggering of the jammer, we formulate and solve a joint user scheduling and power control problem. The proposed solution is then assessed through numerical simulations.

Recent studies in wireless scheduling have shown that CSMA can be made throughput optimal by optimizing over activation rates. However, those throughput optimal CSMA algorithms were found to suffer from poor delay performance, especially at high throughputs where the delay can potentially grow exponentially in the size of the network. Motivated by these shortcomings, in this paper we propose a node-based version of the throughput optimal CSMA (NB-CSMA) as opposed to previous link-based CSMA algorithms, where links were treated as separate entities. Our algorithm is fully distributed and corresponds to Glauber dynamics with "Block updates". We show analytically and via simulations that NB-CSMA outperforms conventional link-based CSMA in terms of delay for any fixed-size network. We also characterize the fraction of the capacity region for which the average queue lengths (and the average delay) grow polynomially in the size of the network, for networks with bounded-degree conflict graphs. This fraction is no smaller than the fraction known for link-based CSMA, and is significantly larger for a special class of wireless ad-hoc networks.

Due to rapid growth of wireless traffic demands in vehicular networks, spectrum scarcity is becoming urgent in the Dedicated Short Range Communication (DSRC) band. One solution is reusing automotive radar bands without degrading radar performance. Despite having massive bandwidths, imaging accuracy of automotive radars is still low due to correlations between sequential target observations of single radar. A solution is that vehicles exchange imaging information through vehicle-to-vehicle communications. Since observations of different vehicles are less correlated, Joint Automotive Radar and Communication (JARC) network is able to improve imaging accuracy. More importantly, some spectrum resources can be left to alleviate the DSRC spectrum scarcity problem. In this paper, we derive the Cramer-Rao bound for parameter estimation in JARC networks. Then, we formulate the spectrum utilization problem as an NP-complete integer quadratic program, to which we propose an optimal (in expectation) algorithm with low complexity. Finally, efficacy of the algorithm is illustrated through numerical results.

Cognitive Radio (CR) approaches constitute one of the most promising ways to solve the inefficiency of the static spectrum allocation procedures. Distributed and self-enforcing methods for multiple access/allocation have also become increasingly attractive for their scalability and robustness. In the light of this reality, we present in this work a game-based distributed algorithm for the multiple access of secondary users (SUs) in a multichannel CR environment. The main idea behind our method is to provide means for SUs to independently select a set of secondary channels to use for transmission, while achieving close-to-optimal equilibrium performance in a Signal-to-Interference-plus-Noise-Ratio (SINR) regime. Additionally, we analytically derive explicit performance bounds on the optimality and the convergence speed of the proposed algorithm. We corroborate the efficacy of our multiple access algorithm as well as the main conclusions on the optimality/convergence speed tradeoff through numerical results.

Many studies show that the Dedicated Short Range Communication band is insufficient to carry increasing wireless data traffic in vehicular networks. The release of large TV spectra by FCC for cognitive access provides additional spectrum resources to solve the spectrum scarcity problem. However, FCC allows fixed devices to use high transmitting powers, while requiring portable devices to use significantly lower powers. This power asymmetry policy leads to a challenging coexistence environment for portable (e.g., vehicular) and fixed (e.g., IEEE 802.22) networks. In this paper, we address the coexistence problem between vehicular and 802.22 networks via resource allocation. We show that the problem is an NP-hard mixed-integer nonlinear programming problem, to which we propose two algorithms. First, we convert it to a convex programming problem, and propose a near-optimal primal-dual algorithm. Next, we reformulate the problem as a packing problem, and present a constant-factor approximation algorithm. Finally, we evaluate the algorithms through numerical examples.

Cognitive radio networks allow unlicensed users to access licensed spectrum opportunistically without disrupting primary user (PU) communication. Developing a distributed implementation that can fully utilize the spectrum opportunities for secondary users (SUs) has so far remained elusive. Although throughput optimal algorithms based on the well-known maximal weight scheduling (MWS) algorithm exist for cognitive radio networks, they require central processing of network-wide SU information. In this paper, a new distributed algorithm is introduced that asymptotically achieves the capacity region of the cognitive radio systems. The proposed algorithm achieves the full SU capacity region while adapting to the channel availability dynamics caused by unknown primary user activity. Extensive simulation results are provided to illustrate the efficacy of the algorithm.

In this paper, we propose a distributed cross-layer scheduling algorithm for wireless networks with single-hop transmissions that can guarantee finite buffer sizes and meet minimum utility requirements. The algorithm can achieve a utility arbitrarily close to the optimal value with a tradeoff in the buffer sizes. The finite buffer property is not only important from an implementation perspective, but, along with the algorithm, also yields superior delay performance. In addition, another extended algorithm is provided to help construct the upper bounds of per-flow average packet delays. A novel structure of Lyapunov function is employed to prove the utility optimality of the algorithm with the introduction of novel virtual queue structures. Unlike traditional back-pressure-based optimal algorithms, our proposed algorithm does not need centralized computation and achieves fully local implementation without global message passing. Compared to other recent throughput/utility-optimal CSMA distributed algorithms, we illustrate through rigorous numerical and implementation results that our proposed algorithm achieves far better delay performance for comparable throughput/utility levels.

Current TV whitespace regulations mainly benefit rural areas where large amounts of TV whitespace exist. Thus, the spectrum scarcity problem is yet to be addressed in urban locations, where it is most experienced. To further improve the spectrum efficiency, a new framework for cognitive radio network operation is presented, which can coexist with current broadcast TV networks. Through geographical evaluations based on distribution of TV towers and population dynamics, it is shown that by leveraging the TV viewership statistics, 5.6-7.7-fold increase in available channels can be provided to mobile users in populated areas such as New York City. Furthermore, daily dynamics of TV viewership can be exploited to provide up to 96 MHz additional bandwidth during prime time and 162-228 MHz additional bandwidth during non-peak hours. The additional TV spectrum can provide additional channel capacities in both rural and urban areas. To the best of our knowledge, this is the first work that analyzes TV whitespace availability based on TV viewership statistics in space and time.

Recent studies show that the Dedicated Short Range Communication (DSRC) band allocated to vehicular networks is insufficient to carry the wireless traffic load generated by emerging applications for vehicular systems. A promising bandwidth expansion possibility presents itself through the release of large TV band spectra by FCC for cognitive access. One of the primary challenges of the so-called TV White Space (TVWS) access in vehicular networks is the design of efficient channel allocation mechanisms in face of high vehicular mobility and spatial-temporal variations of TVWS. In this paper, we address the channel allocation problem for multi-channel cognitive vehicular networks with the objective of system-wide throughput maximization. We show that the problem is a NP-hard combinatorial optimization problem, to which we present two solution approaches. We first propose a probabilistic polynomial-time (1 - 1/e)-approximation algorithm based on linear programming. Next, we prove that our objective function can be written as a submodular set function, based on which we develop a deterministic polynomial-time constant-factor approximation algorithm with a more favorable time complexity. Finally, we show the efficacy of our algorithms through numerical examples.

Cognitive radio networks (CRNs) allow unlicensed users to opportunistically access the licensed spectrum without causing disruptive interference to the primary users (PUs). One of the main challenges in CRNs is the ability to detect PU transmissions. Recent works have suggested the use of secondary user (SU) cooperation over individual sensing to improve sensing accuracy. In this paper, we consider a CRN consisting of multiple PUs and SUs to study the problem of maximizing the total expected system throughput. First, we study the sensing decision problem for maximizing the system throughput subject to a constraint on the PU throughput, and we design a Bayesian decision rule-based algorithm. The problem is shown to be strongly NP-hard and solved via a greedy algorithm with time complexity O([(N5)/(log2[1/(1-ε)])]), where N is the total number of SUs. The algorithm achieves a throughput strictly greater than 1/2(1-ε) of the optimal solution and results in a small constraint violation that goes to zero with ε. We then investigate the more general problem with constraints on both PU throughput and the sensing time overhead, which limits the number of SUs that can participate in cooperative sensing. We illustrate the efficacy of the performance of our algorithms and provide sensitivity analysis via a numerical investigation.

This paper focuses on scheduling in multihop wireless networks where flows are associated with fixed routes. The well-known back-pressure scheduling algorithm is throughput-optimal, but requires constant exchange of queue length information among neighboring nodes for calculating the “back-pressure.” Moreover, previous research shows that the total queue length along a route increases quadratically as the route length under the back-pressure algorithm, resulting in poor delay performance. In this paper, we propose a self-regulated MaxWeight scheduling, which does not require back-pressure calculation. We prove that the self-regulated MaxWeight scheduling is throughput-optimal (an algorithm is said to be throughput-optimal if it can stabilize any traffic that can be stabilized by any other algorithm). In the simulation part, we show that the self-regulated MaxWeight scheduling has a much better delay performance than the back-pressure algorithm.

In this paper, analytical models are proposed to study the performance of amplify-and-forward (AF) multi-branch multi-hop (MBMH) wireless relay systems (WRS) over log-normal fading channels. The presented analytical models are used to estimate the end-to-end performance of the MBMH WRS with maximal ratio combining (MRC) and selection combining (SC) schemes. In particular, we derive closed-form expressions for the parameters of the end-to-end signal-to-noise ratio (SNR) of an AF multi-hop chain relay link. Further, we characterize the distribution of the end-to-end SNR and derive closed-form expressions for the mean and standard deviation of the end-to-end SNR's natural logarithm for AF MBMH WRS with MRC scheme, and the probability density function (pdf) for the end-to-end SNR of AF MBMH WRS with SC scheme. Then, under MRC and SC schemes, we analyze the diversity gain by adopting asymptotical relative diversity order (ARDO) and develop accurate analytical expressions for average bit error probability, outage probability, and ergodic capacity, respectively. Our analysis reveals that the computational complexity of the proposed models is acceptably low for practical applications. Numerical and Monte Carlo simulation results are presented to substantiate the accuracy of the proposed analytical models.

In this paper, a multidimensional-correlation-based sensing scheduling algorithm, (CORN)2, is developed for cognitive radio networks to minimize energy consumption. A sensing quality metric is defined as a measure of the correctness of spectral availability information based on the fact that spectrum sensing information at a given space and time can represent spectrum information at a different point in space and time. The scheduling algorithm is shown to achieve a cost of sensing (e.g., energy consumption, sensing duration) arbitrarily close to the possible minimum, while meeting the sensing quality requirements. To this end, (CORN)2utilizes a novel sensing deficiency virtual queue concept and exploits the correlation between spectrum measurements of a particular secondary user and its collaborating neighbors. The proposed algorithm is proved to achieve a distributed and arbitrarily close to optimal solution under certain, easily satisfied assumptions. Furthermore, a distributed Selective-(CORN)2(S-(CORN)2) is introduced by extending the distributed algorithm to allow secondary users to select collaboration neighbors in densely populated cognitive radio networks. In addition to the theoretically proved performance guarantees, the algorithms are evaluated through simulations.

In Cognitive Radio Networks (CRNs), secondary users (SUs) are allowed to opportunistically access the unused/under-utilized channels of primary users (PUs). To utilize spectrum resources efficiently, an auction scheme is often applied where an operator serves as an auctioneer and accepts spectrum requests from SUs. Most existing works on spectrum auctions assume that the operator has perfect knowledge of PU activities. In practice, however, it is more likely that the operator only has statistical information of the PU traffic when it is trading a spectrum hole, and it is acquiring more accurate information in real time. In this paper, we distinguish PU channels that are under the control of the operator, where accurate channel states are revealed in real-time, and channels that the operator acquires from PUs out of its control, where a sense-before-use paradigm has to be followed. Considering both spectrum uncertainty and sensing inaccuracy, we study the social welfare maximization problem for serving SUs with various levels of delay tolerance. We first model the problem as a finite horizon Markov decision process when the operator knows all spectrum requests in advance, and propose an optimal dynamic programming based algorithm. We then investigate the case when spectrum requests are submitted online, and propose a greedy algorithm that is 1/2-competitive for homogeneous channels and is comparable to the offline algorithm for more general settings. We further extend the online algorithm to an online auction scheme, which ensures incentive compatibility for the SUs and also provides a way for trading off social welfare and revenue.

Efficient scheduling of wireless resources has always been one of the most challenging tasks for wireless networks. To achieve throughput-optimality, traditional back-pressure algorithms calculate a maximal weight matching at each time slot. However, these algorithms need centralized scheduling with high complexity, and thus are not suitable for practical distributed implementations. A class of distributed queue-length-based CSMA algorithms have been proposed that achieve throughput optimality, which we refer to as regular throughput-optimal. These algorithms suffer from two problems: large delays, and temporal starvation. In this demo we demonstrate the operation of the v(t)-regulated CSMA algorithm that mitigates these two problems while provably retaining throughput optimality. The demo allows the participants to see the the performance advantage of v(t)-regulated CSMA over queue-length-based CSMA algorithms and change the different system parameters.

In this paper, a cross-layer optimal scheduling algorithm for cooperative multi-hop Cognitive Radio Networks (CRNs) is presented, where secondary users (SUs) assist primary users' (PUs') multi-hop transmissions and in return gain an immediate time-share of the channel proportional to their assistance. While providing deterministic upper-bounds for PU queue backlogs, the proposed algorithm approaches the optimal PU throughput arbitrarily close, with a tradeoff in the average delay upper-bounds of flows. The analysis is further extended to a model with a more general "long-term reward mechanism", where a time-averaged share of the channel is guaranteed for SUs. The proposed algorithm provides order-optimal delay for the primary traffic. Distributed implementation issues have also been investigated. The properties of the proposed algorithm have also been illustrated through simulation studies.

Cognitive radio networks (CRNs) are composed of frequency-agile radio devices that allow licensed (primary) and unlicensed (secondary) users to coexist, where secondary users opportunistically access channels without interfering with the operation of primary ones. From the perspective of secondary users, spectrum availability is a time-varying network resource over which multihop end-to-end connections must be maintained. In this paper, a theoretical outlook on the problem of routing secondary user flows in a CRN is provided. The investigation aims to characterize optimal sequences of routes over which a secondary flow is maintained. The optimality is defined according to a novel metric that considers the maintenance cost of a route as channels, and/or links must be switched due to the primary user activity. Different from the traditional notion of route stability, the proposed approach considers subsequent path selections, as well. The problem is formulated as an integer programming optimization model. Properties of the problem are also formally introduced and leveraged to design a heuristic algorithm when information on primary user activity is not complete. Numerical results are presented to assess the optimality gap of the heuristic routing algorithm in realistic CRN scenarios.

In this paper, optimal resource allocation policies are characterized for wireless cognitive networks under the spectrum leasing model. We propose cooperative schemes in which secondary users share the time-slot with primary users in return for cooperation. Cooperation is feasible only if the primary system's performance is improved over the non-cooperative case. First, we investigate a scheduling problem where secondary users are interested in immediate rewards. Here, we consider both infinite and finite backlog cases. Then, we formulate another problem where the secondary users are guaranteed a portion of the primary utility, on a long-term basis, in return for cooperation. Finally, we present a power allocation problem where the goal is to maximize the expected net benefit defined as utility minus cost of energy. Our proposed scheduling policies are shown to outperform non-cooperative scheduling policies, in terms of expected utility and net benefit, for a given set of feasible constraints. Based on Lyapunov optimization techniques, we show that our schemes are arbitrarily close to the optimal performance at the price of reduced convergence rate.

In this paper, we propose a cross-layer scheduling algorithm that achieves a throughput “ ε-close” to the optimal throughput in multihop wireless networks with a tradeoff of O([1/(ε)]) in average end-to-end delay guarantees. The algorithm guarantees finite buffer sizes and aims to solve a joint congestion control, routing, and scheduling problem in a multihop wireless network while satisfying per-flow average end-to-end delay constraints and minimum data rate requirements. This problem has been solved for both backlogged as well as arbitrary arrival rate systems. Moreover, we discuss the design of a class of low-complexity suboptimal algorithms, effects of delayed feedback on the optimal algorithm, and extensions of the proposed algorithm to different interference models with arbitrary link capacities.

Cognitive Radio Networks allow unlicensed users to opportunistically access the licensed spectrum without causing disruptive interference to the primary users (PUs). One of the main challenges in CRNs is the ability to detect PU transmissions. Recent works have suggested the use of secondary user (SU) cooperation over individual sensing to improve sensing accuracy. In this paper, we consider a CRN consisting of a single PU and multiple SUs to study the problem of maximizing the total expected system throughput. We propose a Bayesian decision rule based algorithm to solve the problem optimally with a constant time complexity. To prioritize PU transmissions, we re-formulate the throughput maximization problem by adding a constraint on the PU throughput. The constrained optimization problem is shown to be strongly NP-hard and solved via a greedy algorithm with pseudo-polynomial time complexity that achieves strictly greater than 1/2 of the optimal solution. We also investigate the case for which a constraint is put on the sensing time overhead, which limits the number of SUs that can participate in cooperative sensing. We reveal that the system throughput is monotonic over the number of SUs chosen for sensing. We illustrate the efficacy of the performance of our algorithms via a numerical investigation.

In this letter, we propose an analytical model to study the performance of cooperative links for time hopping ultra wideband (UWB) systems under two relay models: amplify-and-forward (AF) and decode-and-forward (DF). The effects of multi-user interference (MUI) are considered when deriving closed-form expressions for outage probability and average bit error probability (BEP) over single-path model. Simulation results show that the presented analytical model can accurately predict the link performance.

Cognitive radio systems allow secondary users to operate on underutilized licensed spectrum. When considering highly congested communication channels, however, opportunities for channel access based on time or frequency division can be limited for secondary user networks. In this research, we consider leveraging enhanced spatial diversity through directional steerable antennas to allow secondary user channel access in parallel with licensed spectrum users. Furthermore, we consider effects of mobility on directional secondary user networks and introduce a mechanism for maintaining point-to-point directional communication links in the presence of mobility. We study the trade-offs between spatial diversity and coordination overhead to motivate the use of directional antennas, even in highly mobile cognitive radio networks.

In this paper, we develop a cross-layer algorithm to minimize energy consumption in multi-hop wireless networks with finite buffers. Our algorithm guarantees a flow-based minimum data rate and a deterministic buffer size upper-bound for individual flows at network nodes. The algorithm jointly integrates congestion control, power allocation, routing and link rate scheduling. In addition, the algorithm achieves a power expenditure "epsilon-close" to the optimal value, with a tradeoff of order O(1/epsilon) in the buffer size. Finally, numerical results are presented to show the proximity to optimality with a significant reduction in queue backlog.

In this paper, the power control problem is considered for access-point based wireless networks under the SINR interference model. This problem is NP hard in terms of the number of APs in the network, and if not designed properly can have high polynomial complexity in terms of the power levels. We first separate the overall problem into two sub-problems using the primal-dual method. We then develop an efficient algorithm under the SINR-interference model that uses only two power levels to solve a subproblem of the overall power control problem, which we call the utility-independent power control (UIPC) subproblem. This approach allows the optimality gap of the UIPC subproblem to be bounded. Moreover, a two-stage iterative algorithm is developed that solves the overall power control problem within a small neighborhood of the global optimum. This offline algorithm has a significantly lower computational complexity than the globally optimal algorithm. Further, based on the structure of the iterative algorithm, an efficient heuristic two-stage greedy algorithm is proposed with low polynomial time complexity. Finally, numerical results are provided to demonstrate the efficacy of our solution.

Optimal transmission scheduling in wireless cognitive networks is considered under the spectrum leasing model. We propose a cooperative scheme in which secondary nodes share the time slot with primary nodes in return for cooperation. Cooperation is feasible only if the system's performance is improved over the non-cooperative case. First, we investigate a scenario where secondary users are interested in immediate rewards. Then, we formulate another problem where the secondary users are guaranteed a portion of the primary utility, on a long term basis, in return for cooperation. In both scenarios, our proposed schemes are shown to outperform non-cooperative scheduling schemes, in terms of both individual and total expected utility, for a given set of feasible constraints. Based on Lyapunov Optimization techniques, we show that our schemes are arbitrarily close to the optimal performance at the price of reduced convergence rate.

Cognitive radio networks enable opportunistic sharing of bandwidth/spectrum. In this paper, we introduce optimal control and scheduling algorithms for multi-hop cognitive radio networks to maximize the throughput of secondary users while stabilizing the cognitive radio network subject to collision rate constraints required by primary users. We show that by employing our proposed optimal algorithm, the achievable network throughput can be arbitrarily close to the optimal value. To reduce complexity, we propose a class of feasible suboptimal algorithms that can achieve at least a fraction of the optimal throughput. In addition, we also analyze the optimal algorithm in the fixed-routing scenario and deduce the corresponding lower-bound of average end-to-end delay across a link set.

We investigate the problem of designing delay-aware joint flow control, routing, and scheduling algorithms in general multi-hop networks for maximizing network utilization. Since the end-to-end delay performance has a complex dependence on the high-order statistics of cross-layer algorithms, earlier optimization-based design methodologies that optimize the long term network utilization are not immediately well-suited for delay-aware design. This motivates us in this work to develop a novel design framework and alternative methods that take advantage of several unexploited design choices in the routing and the scheduling strategy spaces. In particular, we reveal and exploit a crucial characteristic of back pressure-type controllers that enables us to develop a novel link rate allocation strategy that not only optimizes long-term network utilization, but also yields loop free multi-path routes between each source-destination pair. Moreover, we propose a regulated scheduling strategy, based on a token-based service discipline, for shaping the per-hop delay distribution to obtain highly desirable end-to-end delay performance. We establish that our joint flow control, routing, and scheduling algorithm achieves loop-free routes and optimal network utilization. Our extensive numerical studies support our theoretical results, and further show that our joint design leads to substantial end-to-end delay performance improvements in multi-hop networks compared to earlier solutions.

Analytical models for IEEE 802.11 Distributed Coordination Function (DCF) play important roles in performance estimation, protocol optimization and admission control for wireless networks utilizing this MAC protocol. While a myriad of models for IEEE 802.11 DCF channel access delay and throughput exist, such models' accuracy is generally limited to rather narrow ranges of scenario parameters. Our investigations single out the inaccuracy in modeling the backoff process as the primary reason for the said deviations. In this paper, we introduce two highly accurate models for IEEE 802.11 DCF protocol in a single-hop setting under both saturated and unsaturated traffic loads. First, a crucial augmentation to the classical model proposed by Bianchi is presented for the saturation load analysis to account for channel state during the backoff countdown process, resulting in a highly accurate estimation of collision probability, channel throughput and channel access delay. We then extend this accurate model to unsaturated traffic cases through an iterative approach which similarly results in highly accurate performance metric estimations for a wide range of parameters. Both models have been evaluated through simulations and in comparison with existing analytical models.

Dynamic spectrum access (DSA) is proposed to deal with the growing shortage of available leased spectrum for wireless communication. We investigate a subset of DSA referred to as Dynamic Spectrum Leasing (DSL). At its core, DSL allows spectrum lease holders and cognitive radios to cooperate in an effort to leverage spatial diversity to improve channel utilization for both parties. In this research, cognitive radios offer their services as an intermediate relay node in an effort to improve throughput of primary users utilizing a 802.11-based channel access mechanism. In return, the cognitive radio 'piggy-backs' some of its own data while acting as a relay. In this paper, a simple coordination scheme is introduced that allows a network of Secondary Users to coordinate with a Primary User network's access point. This scheme does not require any modification to the primary users' 802.11-based protocol stack as our protocol is implemented only at the access point and the secondary users. Analytical insights into the overhead required for this coordination and the optimization of the overhead are presented. It is shown that, given sufficient relay channel conditions, forwarding packets through a secondary relay channel can be beneficial to both parties in terms of saturation throughput.

Cognitive radio networks enable opportunistic sharing of bandwidth/spectrum. In this paper, we propose a new Opportunistic Periodic MAC protocol (OP-MAC), a protocol that aims at improving the coexistence of licensed primary users and unlicensed secondary users in cognitive radio networks. Under OP-MAC, secondary users cooperate to periodically sense channels, report channel states and exchange control signals, in such a way that we can avoid the common control channel problem and the multi-channel hidden terminal problem. Analysis is provided for an ON/OFF channel scenario and is shown to be consistent with simulation results. With the requirement of only one transceiver per secondary user, OP-MAC is shown to provide higher capacity than a Random-MAC and a control-channel-based CO-MAC.

In this paper, a new spectrum management scheme for CRNs called Voluntary Spectrum Handoff (VSH) is introduced. The two mechanisms proposed under VSH estimate opportune times to initiate unforced spectrum handoff events to facilitate setup and signaling of alternative channels without having communication disruption, which occurs when a secondary user is forced out of an operating spectrum due to primary user activity. VSH has been evaluated through extensive simulations. Simulation results indicate that VSH significantly reduces the communication disruption duration due to handoffs.

In this work, an Adaptive Channel Hopping (ACH) mechanism for sensor networks is proposed to avoid interference from other sources and narrow-band jamming. Under unfavorable channel conditions, ACH lets sensors switch to a new operating channel. ACH reduces the channel scanning and selection latency by ordering available channels using link quality indicator measurements and weights. The proposed ACH scheme is evaluated through simulations and a hardware implementation, which suggest low latency and high channel selection quality even in very adverse conditions.

Directional antennas offer many potential advantages for wireless networks such as increased network capacity, extended transmission range and reduced energy consumption. Exploiting these advantages, however, requires new protocols and mechanisms at various communication layers to intelligently control the directional antenna system. With directional antennas, many trivial mechanisms, such as neighbor discovery, become more challenging since communicating parties must agree on where and when to point their directional beams to enable communication. In this paper, we propose a fully directional neighbor discovery protocol called Sectored-Antenna Neighbor Discovery (SAND) protocol. SAND is designed for sectored-antennas, a low-cost and simple realization of directional antennas, that utilize multiple limited beamwidth antennas. Unlike many proposed directional neighbor discovery protocols, SAND depends neither on omnidirectional antennas nor on time synchronization. In addition, SAND performs neighbor discovery in a serialized fashion allowing individual nodes to discover all potential neighbors within a predetermined time. Moreover, SAND guarantees the discovery of the best sector combination on both communication ends allowing more robust and higher reliability links. Finally, SAND gathers the neighborhood information in a centralized location, if needed, to be used by centralized networking protocols. The effectiveness of SAND has been assessed via simulation studies and real hardware implementation.

Wireless sensor networks have been used to gather data and information in many diverse application settings. The capacity of such networks remains a fundamental obstacle toward the adaptation of sensor network systems for advanced applications that require higher data rates and throughput. In this paper, we explore potential benefits of integrating directional antennas into wireless sensor networks. While the usage of directional antennas has been investigated in the past for ad hoc networks, their usage in sensor networks bring both opportunities as well as challenges. In this paper, Sectored-Antenna Medium Access Control (SAMAC), an integrated cross-layer protocol that provides the communication mechanisms for sensor network to fully utilize sectored antennas, is introduced. Simulation studies show that SAMAC delivers high energy efficiency and predictable delay performance with graceful degradation in performance with increased load.

Location and intersensor distance estimations are important functions for the operation of wireless sensor networks, especially when protocols can benefit from the distance information prior to network deployment. The maximum multihop distance that can be covered in a given number of hops in a sensor network is one such parameter related with coverage area, delay, and minimal multihop transmission energy consumption estimations. In randomly deployed sensor networks, intersensor distances are random variables. Hence, their evaluations require probabilistic methods, and distance models should involve investigation of distance distribution functions. Current literature on analytical modeling of the maximum distance distribution is limited to 1D networks using the Gaussian pdf. However, determination of the maximum multihop distance distribution in 2D networks is a quite complex problem. Furthermore, distance distributions in 2D networks are not accurately modeled by the Gaussian pdf. Hence, we propose a greedy method of distance maximization and evaluate the distribution of the obtained multihop distance through analytical approximations and simulations.

Cognitive Radio Networks (CRNs) are composed of frequency-agile radio devices that allow licensed (primary) and unlicensed (secondary) users to coexist, where secondary users opportunistically access channels without interfering with the operation of primary ones. From the perspective of secondary users, spectrum availability is a time varying network resource over which multi-hop end-to-end connections must be maintained. In this work, a theoretical outlook on the problem of routing secondary user flows in a CRN is provided. The investigation aims to characterize optimal sequences of routes over which a secondary flow is maintained. The optimality is defined according to a novel metric that considers the maintenance cost of a route as channels and/or links must be switched due to the primary user activity. Different from the traditional notion of route stability, the proposed approach considers subsequent path selections, as well. The problem is formulated as an integer programming optimization model and shown to be of polynomial time complexity in case of full knowledge of primary user activity. Properties of the problem are also formally introduced and leveraged to design a heuristic algorithm to solve the minimum maintenance cost routing problem when information on primary user activity is not complete. Numerical results are presented to assess the optimality gap of the heuristic routing algorithm.

In this paper, an anti-sensor network system is proposed, aiming to protect an important area from being under surveillance by an adversary's sensor nodes. The major components of the system are a set of observing points (monitors) deployed in the area of importance. The observers try to localize sensor positions using antenna arrays to measure direction of arrival (DoA) and received signal strength of the signals emitted by sensors. Once sensors are localized, additional measures are taken to physically remove or disable localized sensors. The proposed anti-sensor network system is designed to handle additional counter-measures that can be employed by sensors, including message encryption and non-uniform transmission power levels. The simulation results show the effectiveness of the proposed system and effects of counter-measures on sensor localization performance.

In this paper we propose SPARE MAC, a TDMA based medium access control (MAC) scheme for data diffusion in wireless sensor networks (WSNs). The rationale behind SPARE MAC is to spare energy through limiting the impact of idle listening and traffic overhearing. To this extent, SPARE MAC implements a distributed scheduling solution which assigns to each sensor specific radio resources (i.e., time slots) for reception, summarized as reception schedules (RS), and spreads the information of the assigned RS to neighboring sensors. A transmitting sensor can consequently become active in correspondence of the RS of its intended receiver only. We analyze the performance of SPARE MAC in terms of throughput, power consumption, and data delivery delay both through analytical models and through detailed simulations. Moreover, we compare the performance of SPARE MAC against SMAC.

Recent computing applications such as videoconferencing and grid computing run their tasks on distributed computing resources connected through networks. For such applications, knowledge of the network status such as delay, jitter, and available bandwidth can help them select proper network resources to meet the Quality-of-Service (QoS) requirements. Also, the applications can dynamically change the resource selection if the current selection is found to experience poor performance. For such purposes, Internet Service Providers (ISPs) have started to instrument their networks with Network Measurement Infrastructures (NMIs) that run active measurement tasks periodically and/or on demand. However, one problem that most network engineers have overlooked is the measurement conflict problem, which happens when multiple active measurement tasks inject probing packets into the same network segment at the same time, resulting in misleading reports of network performance due to their combined effects. This paper proposes enhanced Earliest Deadline First (EDF) algorithms that allow "Concurrent Executions" to orchestrate offline/online measurement jobs in a conflict-free manner. The simulation study shows that our measurement scheduling mechanism can improve the schedulable utilization of offline measurement tasks up to 300 percent and the response time of on-demand jobs up to 50 percent. Further, we implement and deploy our scheduling mechanism in a real working NMI for monitoring the Internet2 Abilene network. As a case study, we show the utility of our algorithms in the widely used Network Weather Service (NWS).

Emerging Wireless Sensor Network (WSN) applications demand considerable computation capacity for in-network processing. To achieve the required processing capacity, cross-layer collaborative in-network processing among sensors emerges as a promising solution: Sensors do not only process information at the application layer, but also synchronize their communication activities to exchange partially processed data for parallel processing. However, scheduling computation and communication events is a challenging problem in WSNs due to limited resource availability and shared communication medium. In this work, an application-independent task mapping and scheduling solution in multihop homogeneous WSNs, Multihop Task Mapping and Scheduling (MTMS), is presented that provides real-time guarantees. Using our proposed application model, the multihop channel model, and the communication scheduling algorithm, computation tasks and associated communication events are scheduled simultaneously. The Dynamic Voltage Scaling (DVS) algorithm is presented to further optimize energy consumption. Simulation results show significant performance improvements compared with existing mechanisms in terms of minimizing energy consumption subject to delay constraints.

Abstract Emerging Wireless Sensor Network (WSN) applications demand considerable computation capacity for in‐network processing in resource limited WSN environments. To achieve the required processing capacity under energy consumption constraints, collaboration among sensors through parallel processing methods emerges as a promising solution. Although such methods have been extensively studied in wired networks of processors, its counterpart for WSNs remains largely unexplored. In this paper, a localized task mapping and scheduling solution for energy‐constrained applications in WSNs, Energy‐constrained Task Mapping and Scheduling (EcoMapS), is presented. EcoMapS guarantees energy consumption constraints while minimizing schedule length. EcoMapS incorporates channel modeling, concurrent task mapping, communication and computation scheduling, and sensor failure handling algorithms. Simulation results show significant performance improvements of EcoMapS over existing mechanisms in terms of minimizing schedule lengths subject to energy consumption constrains. Copyright © 2007 John Wiley & Sons, Ltd.

Security plays an important role in the ability to deploy and retrieve trustworthy data from a wireless sensor network. Location verification is an effective first line of defense against attacks which take advantage of a lack, or compromise, of location information. In this work, a probabilistic approach to location verification in dense sensor networks is proposed. The proposed Probabilistic Location Verification (PLV) algorithm leverages the probabilistic dependence of the number of hops a broadcast packet traverses to reach a destination and the Euclidean distance between source and destination. A small number of verifier nodes determine the plausibility of the claimed location, which is represented by a real number between zero and one. Using the calculated plausibility metric, it is possible to create arbitrary number of trust levels in the location claimed. Simulation studies verify that the proposed solution provides high performance in face of various types of attacks.

In this paper, a fully Ad-Hoc Multi-hop Broadcast protocol (AMB) is proposed for inter-vehicular networks. The AMB is an ad-hoc extension of the UMB protocol which handles broadcast in intersections with the help of repeaters. The AMB protocol eliminates the most important drawback - infrastructure dependence - of the UMB protocol by employing an efficient intersection broadcast mechanism. When there is an intersection in the path of the message dissemination, new directional broadcasts to all road segments are initiated by the vehicle closest to the intersection with a fully ad-hoc algorithm without apriori topology information. The simulation results confirm that our protocol has a very high success rate and efficient channel utilization. Consequently, it is concluded that there is no need for infrastructure support unless the the line-of-sight among different road segments incident to an intersection is blocked with obstacles.

With the increasing importance of energy consumption considerations and new requirements of emerging applications, in-network processing of information gains recognition as a viable solution for wireless sensor networks (WSNs). The required processing capability can be achieved through locally collaborative information processing among sensors. Task mapping and scheduling plays an important role in efficient collaborative information processing. Although task mapping and scheduling in wired networks of processors has been well studied in the past, its counterpart for WSNs remains largely unexplored. In this paper, a task mapping and scheduling solution for real-time applications in WSNs, real-time task mapping and scheduling (RT-MapS), is presented. RT-MapS incorporates wireless channel modeling, hyper-DAG extension, concurrent task mapping, communication and computation scheduling, and dynamic voltage scaling (DVS) methods. Simulation results show significant performance improvements compared with existing mechanisms in terms of providing deadline guarantee with minimum energy consumption

The performance of a multihop wireless network is typically affected by the interference caused by transmissions in the same network. In a statistical fading environment, the interference effects become harder to predict. Information sources in a multihop wireless network can improve throughput and delay performance of data streams by implementing interference-aware packet injection mechanisms. Forcing packets to wait at the head of queues and coordinating packet injections among different sources enable effective control of co-packet interference. In this paper, throughput and delay performance in interference-limited multi-hop networks is analyzed. Using non-linear probabilistic hopping models, waiting times which jointly optimize the performance are derived. Optimally coordinated injection strategies are also investigated as functions of the number of information sources and their separations. Obtained results provide guidelines for the placement of relay nodes in multihop wireless networks.

In recent years, mobile elements (MEs) have been proposed as mechanical carriers of data to prolong the lifetime of sensor networks and to overcome network partitioning problem. A scheduling approach is proposed in Y. Gu et al., (2005) for MEs to collect periodically generated data, also called regular messages (RMs), from nearby sensor nodes with no buffer overflow. However, increased delay in message delivery with ME-based communication compared to multi-hop communication may not be tolerated in some cases. Some messages can be more urgent than others due to critical values of the sensed data. Such messages maybe required to be delivered to the ME within a specified deadline. In this paper, this new problem of differentiated message delivery (DMD) considering both regular and urgent message collection is addressed. The proposed solution incorporates multi-hop communication into the ME scheduling problem. The investigated performance metrics are the minimum required ME speed to prevent data loss and guarantee the maximum tolerated urgent message delay, as well as urgent and regular message loss rates for a given ME speed. The proposed solution is shown to perform well in terms of these metrics in various network scenarios. Furthermore, comparisons with existing ME scheduling algorithms show that the proposed solution meets the urgent message delivery requirement with a reasonable increase in ME speed.

In this paper, we present a novel packet delivery mechanism called Multi-Path and Multi-SPEED Routing Protocol (MMSPEED) for probabilistic QoS guarantee in wireless sensor networks. The QoS provisioning is performed in two quality domains, namely, timeliness and reliability. Multiple QoS levels are provided in the timeliness domain by guaranteeing multiple packet delivery speed options. In the reliability domain, various reliability requirements are supported by probabilistic multipath forwarding. These mechanisms for QoS provisioning are realized in a localized way without global network information by employing localized geographic packet forwarding augmented with dynamic compensation, which compensates for local decision inaccuracies as a packet travels towards its destination. This way, MMSPEED can guarantee end-to-end requirements in a localized way, which is desirable for scalability and adaptability to large scale dynamic sensor networks. Simulation results show that MMSPEED provides QoS differentiation in both reliability and timeliness domains and, as a result, significantly improves the effective capacity of a sensor network in terms of number of flows that meet both reliability and timeliness requirements up to 50 percent (12 flows versus 18 flows).

We propose a novel replication-based two-phase scheduling algorithm designed to achieve DAG scheduling with small makespans and high efficiency. In the first phase, the schedule length of the application is minimized using a novel approach that utilizes partial schedules. In the second phase, the number of processors required is minimized by eliminating and merging these partial schedules. Experimental results on random DAGs show that the makespans generated by the proposed algorithm are slightly better than those generated by the well known CPFD algorithm whereas the number of processors used is less than half of what is needed by CPFD solutions.

In this paper, we present a novel packet delivery mechanism called multi-path and multi-speed routing protocol (MMSPEED) for probabilistic QoS guarantee in wireless sensor networks. The QoS provisioning is performed in two quality domains, namely, timeliness and reliability. Multiple QoS levels are provided in the timeliness domain by guaranteeing multiple packet delivery speed options. In the reliability domain, various reliability requirements are supported by probabilistic multipath forwarding. All these for QoS provisioning are realized in a localized way without global network information by employing localized geographic packet forwarding augmented with dynamic compensation, which compensates the local decision inaccuracy as a packet travels towards its destination. This way, MMSPEED can guarantee end-to-end requirements in a localized way, which is desirable for scalability and adaptability to large scale dynamic sensor networks. Simulation results show that MMSPEED provides QoS differentiation in both reliability and timeliness domains and, as a result, significantly improves the effective capacity of a sensor network in terms of number of flows that meet both reliability and timeliness requirements.

Collaboration among sensors through parallel processing mechanisms emerges as a promising solution to achieve high processing power in resource-restricted wireless sensor networks (WSN). Although task mapping and scheduling in wired networks of processors has been well studied in the past, their application to WSNs remains largely unexplored. Due to the limitations of WSNs, existing algorithms cannot be directly implemented in WSNs. In this paper, a task mapping and scheduling solution for energy-constrained applications in WSNs, energy-constrained task mapping and scheduling (EcoMapS), is presented. EcoMapS incorporates channel modeling, concurrent task mapping, communication and computation scheduling, and sensor failure handling algorithm. The performance of EcoMapS is evaluated through simulations with randomly generated directed acyclic graphs (DAG). Simulation results show significant performance improvements compared with an existing mechanism in terms of minimizing schedule lengths subject to energy consumption constrains

In spatially random sensor networks, estimating the Euclidean distance covered by a packet in a given number of hops carries a high importance for various other methods such as localization and distance estimations. The inaccuracies in such estimations motivate this study on the distribution of the Euclidean distance covered by a packet in spatially random sensor networks in a given number of hops. Although a closed-form expression of distance distribution cannot be obtained, highly accurate approximations are derived for this distribution in one dimensional spatially random sensor networks. Using statistical measures and numerical examples, it is also shown that the presented distribution approximation yields very high accuracy even for small number of hops. A discussion on how these principles can be extended to the analysis of the same problem in two dimensional networks is also provided.

In recent studies, using mobile elements (MEs) as mechanical carriers of data has been shown to be an effective way of prolonging sensor network life time and relaying information in partitioned networks. As the data generation rates of sensors may vary, some sensors need to be visited more frequently than others. In this paper, a partitioning-based algorithm is presented that schedules the movements of MEs in a sensor network such that there is no data loss due to buffer overflow. Simulation results show that the proposed Partitioning Based Scheduling (PBS) algorithm performs well in terms of reducing the minimum required ME speed to prevent data loss, providing high predictability in inter-visit durations, and minimizing the data loss rate for the cases when the ME is constrained to move slower than the minimum required ME speed.

Multiprotocol label switching (MPLS) has gained momentum in recent years as an effective tool to provide quality of service (QoS) in a variety of networks. This has in turn created active interest in the area of recovery in MPLS based networks. A number of recovery schemes for MPLS domains have been proposed in recent years. However, the current schemes lack support for recovery in dynamic network topologies. In this paper, a new flexible signaling protocol for LSP rerouting in dynamic network environments is introduced. The signaling protocol recovers from node and link failures reactively, eliminating the need for end-to-end LSP reestablishment. The performance of the signaling protocol is presented through simulations.

Overlapping coverage areas of the systems in next generation networks cause high signaling overhead if the users are tracked in multiple systems independently. Selecting the system over which paging can be done is yet another problem. In this paper, we present a general next generation wireless network architecture and propose a location registration scheme that updates the location information only in the relevant subsystems. We also propose an efficient paging scheme that exploits the location information in multiple subsystems. User preferences, network availability, and connection history are considered while determining the subsystems to be used for location registration and paging.

A new multicast routing algorithm is introduced for multi-layered satellite networks, which include GEO, MEO, and LEO layers. This scheme aims to minimize the total cost of multicast trees in the satellite network. Multicast trees are constructed and maintained in the dynamic satellite network topology in a distributed manner. Simulation results are provided to evaluate the performance of this scheme in terms of end-to-end delay and multicast tree cost.

Several IP-based routing algorithms have been developed for low-Earth orbit (LEO) satellite networks in recent years. The performance of the satellite IP networks can be improved drastically if multiple satellite constellations are used in the architecture. A multilayered satellite IP network is introduced that consists of LEO, medium-Earth orbit (MEO) and geostationary Earth orbit (GEO) satellites. A new multilayered satellite routing (MLSR) algorithm is developed that calculates routing tables efficiently using the collected delay measurements. The performance of the multilayered satellite network and MLSR is evaluated through simulations and analysis.

Satellite networks provide global coverage and support a wide range of services. Since low Earth orbit (LEO) satellites provide short round-trip delays, they are becoming increasingly important for real-time applications such as voice and video traffic. Many applications require a mechanism to deliver information to multiple recipients. A multicast routing algorithm for datagram traffic is introduced for LEO satellite IP networks. The new scheme creates multicast trees by using the datagram routing algorithm. The bandwidth utilization and delay characteristics are assessed through simulations.

To accomplish network layer integration of terrestrial and satellite IP networks, special exterior gateway protocols are needed. In this work, a new exterior gateway protocol called Border Gateway Protocol-Satellite version (BGP-S) is introduced that enables automated discovery of paths that go through the satellite network. This protocol is designed to work in only one terrestrial gateway in every autonomous system and enables the forwarding of discovered paths in the Internet using the BGP-4 protocol.

Satellite networks provide global coverage and support a wide range of services, low Earth orbit (LEO) satellites provide short round-trip delays and are becoming increasingly important. One of the challenges in LEO satellite networks is the development of specialized and efficient routing algorithms. In this work, a datagram routing algorithm for LEO satellite networks is introduced. The algorithm generates minimum propagation delay paths. The performance of the algorithm is evaluated through simulations. The robustness issues of the algorithm are also discussed.

Satellite networks provide global coverage and support a wide range of services. Low-Earth-orbit (LEO) satellites provide short round-trip delays and are becoming increasingly important. One of the challenges in LEO satellite networks is the development of specialized and efficient routing algorithms. In this work, a datagram routing algorithm for LEO satellite networks is introduced. The algorithm generates minimum propagation delay paths. The performance of the algorithm is evaluated through simulations and finally robustness issues are discussed.

One way of improving the performance of cellular networks is to build a second layer of macrocells on top of the microcell level. The system performance can further be increased by using guard channels and allowing calls to overflow to the upper layer when needed. In this study, we used simulated annealing (SA) to determine the design parameters of two-tier cellular networks for which the cost is minimized. We experimented with the SA-based technique on different example problems and obtained promising results.