Age of Information (AoI) has proven to be a useful metric in networked systems where timely information updates are of importance. In the literature, minimizing “average age” has received considerable attention. However, various applications pose stricter age requirements on the updates which demand knowledge of the AoI distribution. Furthermore, the analysis of AoI distribution in a multi-hop setting, which is important for the study of Wireless Networked Control Systems (WNCS), has not been addressed before. Toward this end, we study the distribution of AoI in a WNCS with two hops and devise a problem of minimizing the tail of the AoI distribution with respect to the frequency of generating information updates, i.e., the sampling rate of monitoring a process, under first-come-first-serve (FCFS) queuing discipline. We argue that computing an exact expression for the AoI distribution may not always be feasible; therefore, we opt for computing upper bounds on the tail of the AoI distribution. Using these upper bounds, we formulate Upper Bound Minimization Problems (UBMP), namely, Chernoff-UBMP and α-relaxed Upper Bound Minimization Problem (α-UBMP), where α > 1 is an approximation factor, and solve them to obtain “good” heuristic rate solutions for minimizing the tail. We demonstrate the efficacy of our approach by solving the proposed UBMPs for three service distributions: geometric, exponential, and Erlang. Simulation results show that the rate solutions obtained are near optimal for minimizing the tail of the AoI distribution for the considered distributions.

In this article, we investigate the transient behavior of a sequence of packets/bits traversing a multi-hop wireless network under static routing. Our work is motivated by novel applications from the domain of process automation, Machine-Type Communication (MTC) and cyber-physical systems, where short messages are communicated and statistical guarantees need to be provided on a per-message level. In order to optimize such a network, apart from understanding the stationary system dynamics, an understanding of the short-term dynamics (i.e. transient behavior) is also required. To this end, we derive novel Wireless Transient Bounds (WTB) for end-to-end delay and backlog in a multi-hop wireless network using stochastic network calculus approach. We start by analyzing a single end-to-end path, i.e. a line topology, and then we show how the obtained results can be applied to a mesh network with static routing using a concept called 'leftover service'. WTB depends on the initial backlog at each node as well as the instantaneous channel states. We numerically compare WTB with Kernel-Based-Transient Bound (KBTB), which can be obtained by adapting existing stationary bound, as well as simulated end-to-end delay of the investigated network. While KBTB and stationary bounds are not able to capture the short-term system dynamics well, WTB provides relatively tight upper bound and has a decay rate that closely matches the simulation. This is achieved by WTB only with a slight increase in the computational complexity, by a factor of O(T + N), where T is the duration of the arriving sequence and N is the number of hops in the network. We believe that the presented analysis and the bounds are necessary tools for future work on transient network optimization for many important emerging applications, e.g., massive MTC, critical MTC, edge computing and autonomous vehicle.

Since Age of Information (AoI) has been proposed as a metric that quantifies the freshness of information updates in a communication system, there has been a constant effort in understanding and optimizing different statistics of the AoI process for classical queueing systems. In addition to classical queuing systems, more recently, systems with no queue or a unit capacity queue storing the latest packet have been gaining importance as storing and transmitting older packets do not reduce AoI at the receiver. Following this line of research, we study the distribution of AoI for the GI/GI/1/1 and GI/GI/1/2* systems, under non-preemptive scheduling. For any single-source-single-server queueing system, we derive, using sample path analysis, a fundamental result that characterizes the AoI violation probability, and use it to obtain closed-form expressions for D/GI/1/1, M/GI/1/1 as well as systems that use zero-wait policy. Further, when exact results are not tractable, we present a simple methodology for obtaining upper bounds for the violation probability for both GI/GI/1/1 and GI/GI/1/2* systems. An interesting feature of the proposed upper bounds is that, if the departure rate is given, they overestimate the violation probability by at most a value that decreases with the arrival rate. Thus, given the departure rate and for a fixed average service, the bounds are tighter at higher utilization.

We study the detection and delay performance impacts of a feature-based physical layer authentication (PLA) protocol in mission-critical machine-type communication (MTC) networks. The PLA protocol uses generalized likelihood-ratio testing based on the line-of-sight (LOS), single-input multiple-output channel-state information in order to mitigate impersonation attempts from an adversary node. We study the detection performance, develop a queueing model that captures the delay impacts of erroneous decisions in the PLA (i.e., the false alarms and missed detections), and model three different adversary strategies: data injection, disassociation, and Sybil attacks. Our main contribution is the derivation of analytical delay performance bounds that allow us to quantify the delay introduced by PLA that potentially can degrade the performance in mission-critical MTC networks. For the delay analysis, we utilize tools from stochastic network calculus. Our results show that with a sufficient number of receive antennas (approximately 4-8) and sufficiently strong LOS components from legitimate devices, PLA is a viable option for securing mission-critical MTC systems, despite the low-latency requirements associated to corresponding use cases. Furthermore, we find that PLA can be very effective in detecting the considered attacks, and in particular, it can significantly reduce the delay impacts of disassociation and Sybil attacks.

Random Access Channel (RACH) has been identified as one of the major bottlenecks for accommodating massive number of Machine-to-Machine (M2M) devices in LTE networks, especially in the case of bursty arrivals of connection requests. As a consequence, the burst resolution problem has sparked a large number of works analyzing and optimizing the expected performance of RACH. In this paper, we go beyond the study of performance in expectation by investigating the probabilistic performance limits of RACH with access class barring. We model RACH as a queuing system, and apply stochastic network calculus to derive probabilistic performance bounds for burst resolution time, i.e., the time it takes to connect a burst of M2M devices to the base station. We illustrate the accuracy of the proposed methodology and its potential applications in performance assessment and system dimensioning.

With the rise of critical machine-to-machine applications, next generation wireless communication systems must meet challenging requirements with respect to latency and reliability. A key question in this context relates to channel state estimation, which allows the transmitter to adapt the code rate to the channel state. In this paper, we characterize the tradeoff between the training sequence length and data codeword length: shorter channel estimation leaves more time for the payload transmission but reduces the estimation accuracy and causes more decoding errors. Using lower coding rates can mitigate this effect, but may result in a higher backlog of data at the transmitter. In order to optimize the training sequence length and the rate adaptation scheme with respect to the delay performance, we employ queuing analysis on top of accurate models of the physical layer. We obtain an analytically tractable solution to the problem by deriving a closed-form approximation for the decoding error probability due to imperfect channel knowledge and finite-blocklength channel coding. The optimized training sequence length and rate adaptation strategy can reduce the delay violation probability by an order of magnitude, compared with suboptimal strategies that do not consider the delay constraints.

The abundance of spectrum in the millimeter-wave (mm-wave) bands makes it an attractive alternative for future wireless communication systems. Such systems are expected to provide data transmission rates in the order of multi-gigabits per second in order to satisfy the ever-increasing demand for high rate data communication. Unfortunately, mm-wave radio is subject to severe path loss, which limits its usability for long-range outdoor communication. In this paper, we propose a multi-hop mm-wave wireless network for outdoor communication, where multiple full-duplex buffered relays are used to extend the communication range, while providing end-to-end performance guarantees to the traffic traversing the network. We provide a cumulative service process characterization for the mm-wave propagation channel with self-interference in terms of the moment generating function of its channel capacity. Then, we then use this characterization to compute probabilistic upper bounds on the overall network performance, i.e., total backlog and end-to-end delay. Furthermore, we study the effect of self-interference on the network performance and propose an optimal power allocation scheme to mitigate its impact in order to enhance network performance. Finally, we investigate the relation between relay density and network performance under a sum power constraint. We show that increasing relay density may have adverse effects on network performance, unless the self-interference can be kept sufficiently small.

Feature-based authentication schemes that verify wireless transmitter identities based on physical-layer features allow for fast and efficient authentication with minimal overhead. Hence, they are interesting to consider for safety-critical applications where low latency and high reliability is required. However, as erroneous authentication decisions will introduce delays, we propose to study the impact of feature-based schemes on the system-level performance. In this paper, we therefore study the queuing performance of a line-of-sight wireless link that employs a feature- based authentication scheme based on the complex channel gain. Using stochastic networks calculus, we provide bounds on the delay performance which are validated by numerical simulations. The results show that the delay and authentication performance is highly dependent on the SNR and Rice factor. However, under good channel conditions, a missed-detection rate of 10E-8 can be achieved without introducing excessive delays in the system.

In this paper, we investigate the performance of the wiretap Rayleigh fading channel in the presence of statistical delay constraints. We invoke tools from stochastic network calculus to derive probabilistic bounds on the delay. This method requires a statistical characterization of the wiretap fading service process, which we derive in closed form. We then validate these analytical bounds via simulations. Interestingly, the analysis of the wiretap fading channel reveals close structural similarities with the interference channel in terms of service process characterization, which is derived in our prior work. In our numerical evaluations, we show that the delay performance of the wiretap fading channel is in particular sensitive to bursty arrival processes due to the high variance of the service process.

Motivated by emerging vision-based intelligent services, we consider the problem of rate adaptation for high-quality and low-delay visual information delivery over wireless networks using scalable video coding. Rate adaptation in this setting is inherently challenging due to the interplay between the variability of the wireless channels, the queuing at the network nodes, and the frame-based decoding and playback of the video content at the receiver at very short time scales. To address the problem, we propose a low-complexity model-based rate adaptation algorithm for scalable video streaming systems, building on a novel performance model based on stochastic network calculus. We validate the analytic model using extensive simulations. We show that it allows fast near-optimal rate adaptation for fixed transmission paths, as well as cross-layer optimized routing and video rate adaptation in mesh networks, with less than 10% quality degradation compared to the best achievable performance.

To meet the ever-increasing demands on higher throughput and better network delay performance, 60 GHZ networking is proposed as a promising solution for the next generation of wireless communications. To successfully deploy such networks, its important to understand their performance first. However, due to the unique fading characteristic of the 60 GHz channel, the characterization of the corresponding service process, offered by the channel, using the conventional methodologies may not be tractable. In this work, we provide an alternative approach to derive a closed-form expression that characterizes the cumulative service process of the 60 GHz channel in terms of the moment generating function (MGF) of its instantaneous channel capacity. We then use this expression to derive probabilistic upper bounds on the backlog and delay that are experienced by a flow traversing this network, using results from the MGF-based network calculus. The computed bounds are validated using simulation. We provide numerical results for different networking scenarios and for different traffic and channel parameters and we show that the 60 GHz wireless network is capable of satisfying stringent quality-of-Service (QoS) requirements, in terms of network delay and reliability. With this analysis approach at hand, a larger scale 60 GHz network design and optimization is possible.

We consider the effective capacity performance measure of persistent- and truncated-retransmission schemes that can involve any combination of multiple transmissions per packet, multiple communication modes, or multiple packet communication. We present a structured unified analytical approach, based on a random walk model and recurrence relation formulation, and give exact effective capacity expressions for persistent hybrid automatic repeat request (HARQ) and for truncated-retransmission schemes. For the latter, effective capacity expressions are given for systems with finite (infinite) time horizon on an algebraic (spectral radius-based) form of a special block companion matrix. In contrast to prior HARQ models, assuming infinite time horizon, the proposed method does not involve a non-trivial per case modeling step. We give effective capacity expressions for several important cases that have not been addressed before, e.g., persistent-HARQ, truncated-HARQ, network-coded ARQ, two-mode-ARQ, and multilayer-ARQ. We propose an alternative quality-of-service-parameter (instead of the commonly used moment generating function parameter) that represents explicitly the target delay and the delay violation probability. This also enables the closed-form expressions for many of the studied systems. Moreover, we use the recently proposed matrix-exponential distributed modeling of wireless fading channels to provide the basis for numerous new effective capacity results for HARQ.

A fundamental problem for the delay and backlog analysis across multihop paths in wireless networks is how to account for the random properties of the wireless channel. Since the usual statistical models for radio signals in a propagation environment do not lend themselves easily to a description of the available service rate, the performance analysis of wireless networks has resorted to higher-layer abstractions, e.g., using Markov chain models. In this paper, we propose a network calculus that can incorporate common statistical models of fading channels and obtain statistical bounds on delay and backlog across multiple nodes. We conduct the analysis in a transfer domain, where the service process at a link is characterized by the instantaneous signal-to-noise ratio at the receiver. We discover that, in the transfer domain, the network model is governed by a dioid algebra, which we refer to as the (min, ×) algebra. Using this algebra, we derive the desired delay and backlog bounds. Using arguments from large deviations theory, we show that the bounds are asymptotically tight. An application of the analysis is demonstrated for a multihop network of Rayleigh fading channels with cross traffic at each hop.

Multi-hop wireless networks are increasingly becoming more relevant to current and emerging wireless network deployment. The need for understanding the performance of such networks in order to be able to provide quantifiable end-to-end quality of service is apparent. Until recently, only asymptotic results that describe the scaling of the delay in the size of the network under numerous conformity conditions were available. Recently, a new methodology for wireless networks performance analysis based on stochastic network calculus was presented [1]. This methodology enables the computation of end-to-end probabilistic delay bound of multi-hop wireless networks in terms of the underlying fading channel parameters. However, the approach assumes identically distributed channel gain which applies to a very specific class of networks. In this work, we seek to develop an end-to-end probabilistic delay bound for multi-hop wireless networks with non-identically distributed channel gains. We show that the delay bound for such networks can be computed recursively. We validate the resulting bound by means of simulation and discuss various numerical examples.

Upcoming low-latency machine-to-machine (M2M) applications are currently attracting a significant amount of interest from the wireless networking research community. The design challenge with respect to such future applications is to allow wireless networks to operate extremely reliably at very short deadlines for rather small packets. To date, it is unclear how to design wireless networks efficiently for such novel requirements. One reason is that existing performance models for wireless networks often assume that the rate of the channel code is equal to the Shannon capacity. However, this model does not hold anymore when the packet size and thus blocklength of the channel code is small. Although it is known that finite blocklength has a major impact on the physical layer performance, we lack higher-layer performance models which account in particular for the queueing effects under the finite blocklength regime.

Nodes in a sensor network are traditionally used for sensing and data forwarding. However, with the increase of their computational capability, they can be used for in-network data processing, leading to a potential increase of the quality of the networked applications as well as the network lifetime. Visual analysis in sensor networks is a prominent example where the processing power of the network nodes needs to be leveraged to meet the frame rate and the processing delay requirements of common visual analysis applications. The modeling of the end-to-end performance for such networks is, however, challenging, because in-network processing violates the flow conservation law, which is the basis for most queuing analysis. In this work we propose to solve this methodological challenge through appropriately scaling the arrival and the service processes, and we develop probabilistic performance bounds using stochastic network calculus. We use the developed model to determine the main performance bottlenecks of networked visual processing. Our numerical results show that an end-to-end delay of 2-3 frame length is obtained with violation probability in the order of 10-6. Simulation shows that the obtained bounds overestimates the end-to-end delay by no more than 10%.

A fundamental problem for the delay and backlog analysis across multi-hop paths in wireless networks is how to account for the random properties of the wireless channel. Since the usual statistical models for radio signals in a propagation environment do not lend themselves easily to a description of the available service rate, the performance analysis of wireless networks has resorted to higher-layer abstractions, e.g., using Markov chain models. In this work, we propose a network calculus that can incorporate common statistical models of fading channels and obtain statistical bounds on delay and backlog across multiple nodes. We conduct the analysis in a transfer domain, which we refer to as the SNR domain, where the service process at a link is characterized by the instantaneous signal-to-noise ratio at the receiver. We discover that, in the transfer domain, the network model is governed by a dioid algebra, which we refer to as (min, ×) algebra. Using this algebra we derive the desired delay and backlog bounds. An application of the analysis is demonstrated for a simple multi-hop network with Rayleigh fading channels.

In this work, we investigate the optimal dynamic packet scheduling policy in a wireless relay network (WRN). We model this network by two sets of parallel queues, that represent the subscriber stations (SS) and the relay stations (RS), with random link connectivity. An optimal policy minimizes, in stochastic ordering sense, a cost function of the SS and RS queue sizes. We prove that, in a system with symmetrical connectivity and arrival distributions, a policy that tries to balance the lengths of all the system queues, at every time slot, is optimal. We use stochastic dominance and coupling arguments in our proof. We also provide a low-overhead algorithm for optimal policy implementation.

We present an algorithm to implement “most balancing” packet scheduling policies in a discrete-time multi-server system of parallel queues with independent random queue-server connectivity. The MB policies are characterized by minimizing the total difference in queue lengths at every time slot. The proposed algorithm produces the server allocation strategy that achieves the minimum “imbalance index” at every time slot. This algorithm has a reduced computational complexity compared to a full-search through the set of all feasible policies. We also provide a low-complexity approximate implementation algorithm that performs close to the exact algorithm. Simulation results confirm our claims.

In this work, we investigate the optimal key generation problem for a threshold security scheme in mobile ad hoc networks. The nodes in these networks are assumed to have limited power and critical security states. We model this problem using a closed discrete-time queuing system with L queues (one per node) randomly connected to K servers (where K nodes need to be contacted to construct a key). In this model, each queue length represents the available security-related credits of the corresponding node. We treat this problem as a resource allocation problem where the resources to be allocated are the limited power and security credits. We introduce the class of Most Balancing Credit Conserving (MBCC) policies and provide their mathematical characterization. We prove, using dynamic coupling arguments, that MBCC policies are optimal among all key generation policies; we define optimality as maximization, in a stochastic ordering sense, of a random variable representing the number of keys generated for a given initial system state.

We investigate an optimal scheduling problem for a discrete-time system of two parallel queues with infinite capacity, sharing two symmetrical servers. This model can be used to study a variety of scheduling problems in wireless networks. At any time slot, a queue can be served by one or two connected servers; the queue-server connectivity is assumed to be random and modeled by a two-state Markov chain. The arrivals to each queue are assumed to be independent and identically distributed. A scheduled packet completes service successfully with a given probability. Otherwise, it has to be retransmitted in a later time slot. The optimal scheduling policy is defined as the server allocation policy that minimizes, in a stochastic ordering sense, the total number of packets in the system. We prove, using a dynamic coupling method, that a "Most Balancing" policy, a policy that attempts to balance the lengths of the two queues, is optimal. We also compare the performance of the optimal policy to that of a few other policies via simulations.

We investigate an optimal scheduling problem in a discrete-time system of L parallel queues that are served by K identical servers. This model has been widely used in studies of emerging 3G/4G wireless systems. We introduce the class of Most Balancing (MB) policies and provide their mathematical characterization. We prove that MB policies are optimal among all work conserving policies; we define optimality as minimization, in stochastic ordering sense, of a range of cost functions of the queue lengths, including the process of total number of packets in the system. We use dynamic coupling arguments for our proof. We also introduce the Least Connected Server First/Longest Connected Queue (LCSF/LCQ) policy as an approximate implementation of MB policies. We conduct a simulation study to compare the performance of several work conserving policies to that of the optimal one. In the simulations we relax some of the mathematical assumptions we required for the analytical proofs. The simulation results show that: (a) in all cases, MB policies outperform the other policies, (b) randomized policies perform fairly close to the optimal one, and, (c) the performance advantage of the optimal policy over the other work conserving policies increases as the channel connectivity decreases.

This paper presents a novel methodology for finding the network connectivity in wireless mesh networks while taking into account dependencies between links of geometrically co- located nodes, as well as the reduced connectivity of boundary nodes. A closed form expression to find the upper bound for the network connectivity of a triangular lattice topology was derived. A comparison study between models that assume independent nodes' connectivities and our model shows that the commonly used assumption of link independence almost always underestimate the network connectivity. This work also shows that the effect of boundary nodes on the network connectivity can not be eliminated by assuming an infinitely large network since the assumption overestimates the network connectivity by a non negligible amount. The analysis also shows that the error due to either assumption depends on the link connectivity as well as the network size, and can be very significant.

In this paper, a discrete stochastic dynamic programming model for the high speed downlink packet access (HSDPA) downlink scheduler when using finite-state Markov channel (FSMC) model is presented. The model then solved numerically (using value iteration) to find the optimal policy for the case of two users sharing the same cell using a 3-state channel. The optimal policy is the one that maximizes the system throughput while maintaining a level of fairness between users. Simulation is used to study the performance of the resulted optimal policy and compared with Round Robin (RR) scheduler. The effects of the allowable number of channel states and the fairness factor on the optimal policy performance were also studied.

This paper presents a novel methodology for finding the network connectivity in wireless mesh networks. This methodology takes into account link dependencies in neighboring nodes. The methodology was used to determine the upper bound for the connectivity in a one-dimensional chain topology as well as in the two-dimensional triangular lattice topology. We show that the assumption of link independence almost always underestimates the network connectivity. Our derived closed form expressions hence serve as more accurate upper bounds for network connectivity. The conducted comparison studies show that the error due to the assumption of node independence depends on the link connectivity, and can be very significant. The devised methodology can also be used to quantify the error and define the range of link connectivities within which the assumption of link independence can be used.

In this paper, we present an analytic model and methodology to determine optimal scheduling policy that involves two dimension space allocation: time and code, in high speed downlink packet access (HSDPA) system. A discrete stochastic dynamic programming model for the HSDPA downlink scheduler is presented. Value iteration is then used to solve for optimal policy. This framework is used to find the optimal scheduling policy for the case of two users sharing the same cell. Simulation is used to study the performance of the resulted optimal policy using round robin (RR) scheduler as a baseline. The policy granularity is introduced to reduce the computational complexity by reducing the action space. The results showed that finer granularity (down to 5 codes) enhances the performance significantly. However, the enhancement gained when using even finer granularity was marginal and does not justify the added complexity. The behaviour of the value function was observed to characterize the optimal scheduling policy. These observations is then used to develop a heuristic scheduling policy. The devised heuristic policy has much less computational complexity which makes it easy to deploy and with only slight reduction in performance compared to the optimal policy according to the simulation results.