In heterogeneous networks (HetNets), load balancing among different tiers can be effectively achieved by a biased user association scheme with which each user chooses to associate with one base station (BS) based on the biased received power. In contrast to previous studies where a BS always has packets to transmit, we assume in this paper that incoming packets intended for all the associated users form a queue in the BS. In order to find the delay limit of the network to support real-time service, we focus on the delay optimization problem by properly tuning the biasing factor of each tier. By adopting a thinned Poisson point process (PPP) model to characterize the locations of BSs in the busy state, an explicit expression of the average traffic intensity of each tier is obtained. On that basis, an optimization problem is formulated to minimize a lower bound of the network mean queuing delay. By showing that the optimization problem is convex, the optimal biasing factor of each tier can be obtained numerically. When the mean packet arrival rate of each user is small, a closed-form solution is derived. The simulation results demonstrate that the network queuing performance can be significantly improved by properly tuning the biasing factor. It is further shown that the network mean queuing delay might be improved at the cost of a deterioration of the network signal-to-interference ratio (SIR) coverage, which indicates a performance tradeoff between real-time and non-real-time traffic in HetNets.
The analysis of coupled queues is a long-standing open problem, and even solving a special case of two interacting queues is challenging @cite_18 . Zhuang @cite_24 modeled multiple interacting queues as a continuous-time Markov chain (CTMC) with fixed BS locations in the network. By minimizing the average packet queuing delay, the optimal spectrum allocation pattern was obtained for each BS. Similarly, Cheng @cite_8 optimized the average queuing delay of network subjected to the BS power constraints. They formulated a Markov decision process (MDP) problem based on the instantaneous channel state information and queue state information, and proposed an adaptive user scheduling and power control policy. However, the state space of the Markov process may become huge as the network scales up, and the analysis would become intractable. Hence, this motivates us to deal with the coupled queue problem with the tool of stochastic geometry to account for the random BS deployment, and derive the mean performance metrics analytically such that some insights can be gained for system design.
@cite_24 @cite_18 @cite_8
2836117655 2043605850
In this paper, we consider delay-optimal charging scheduling of the electric vehicles (EVs) at a charging station with multiple charge points. The charging station is equipped with renewable energy generation devices and can also buy energy from power grids. The uncertainty of the arrival of the EV, the intermittence of the renewable energy, and the variation of the grid power price are taken into account and described as independent Markov processes. Meanwhile, the required charging energy for each EV is random. The goal is to minimize the mean waiting time for EVs under the long-term constraint on the cost. We propose queue mapping to convert the EV queue to the charging demand queue, and we prove the equivalence between the minimization of the two queues' average length. Then, we focus on the minimization for the average length of the charging demand queue under the long-term cost constraint. We propose a framework of Markov decision process (MDP) to investigate this constrained stochastic optimization problem. The system state includes the charging demand queue length, the charging demand arrival, the energy level in the storage battery of the renewable energy, the renewable energy arrival, and the grid power price. Additionally, the number of charging demands and the allocated energy from the storage battery compose the 2-D policy. We derive two necessary conditions of the optimal policy. Moreover, we discuss the reduction of the 2-D policy to be the number of charging demands only. We give the sets of system states for which charging no demand and charging as many demands as possible are optimal, respectively. Finally, we investigate the proposed policies numerically. Delay-sensitive traffic services, such as live streaming video, voice over IP and multimedia teleconferencing, requires low end-to-end delay in order to maintain its interactive and streaming nature. In recent years, the popularity of delay-sensitive applications has been rapidly growing. In this study, the authors consider the delay-sensitive user scheduling and power control design for heterogeneous networks (HetNets). They model the problem as an infinite-horizon average cost Markov decision process MDP. Based on the dynamics of channel state information (CSI) and queue state information (QSI), they focus on finding an adaptive user scheduling and power control policy to minimise the average delay of network subjected to the power constraints of heterogeneous base stations. In order to reduce the computational complexity and facilitate the distributive implementation, the authors derive a distributive stochastic learning algorithm which only requires local CSI and local QSI to determine the optimal user scheduling and power control policy. The simulation results confirm that significant delay performance gain can be achieved compared with various baseline schemes. Base station (BS) sleeping is an effective way to improve the energy-efficiency of cellular networks. However, it may bring extra user-perceived delay. We conduct a theoretical study into the impact of BS sleeping on both energy-efficiency and user-perceived delay. We consider hysteresis sleep and three typical wake-up schemes, namely single sleep, multiple sleep, and @math -limited schemes. We model the system as an @math vacation queue, which captures the setup time, the mode-changing cost, as well as the counting or detection cost during the sleep mode. Closed-form expressions for the average power and the Laplace–Stieltjes transform of delay distribution are obtained. The impacts of system parameters on these expressions are analyzed. We then formulate an optimization problem to design delay-constrained energy-optimal BS sleeping policies. We show that the optimal solutions possess a special structure, thereby allowing us to obtain them explicitly or numerically by simple bisection search. In addition, the relationship between the optimal power consumption and the mean delay constraint is analyzed, so as to answer the fundamental question: how much energy can be saved by trading off a certain amount of delay? It is shown that this optimal relationship is linear only when the delay constraint is lower than a threshold. Numerical studies are also conducted, where the impact of detection or counting cost during the sleep mode is explored, and the delay distribution under the optimal policy is obtained. In this paper, we study the performance of Device-to-Device (D2D) communications with dynamic interference. In specific, we analyze the performance of frequency reuse among D2D links with dynamic data arrival setting. We first consider the arrival and departure processes of packets in a non-saturated buffer, which result in varying interference on a link based on the change of its backlogged state. The packet-level system behavior is then represented by a coupled processor queuing model, where the service rate varies with time due to both the fast fading and the dynamic interference effects. In order to analyze the queuing model, we formulate it as a Discrete Time Markov Chain (DTMC) and compute its steady-state distribution. Since the state space of the DTMC grows exponentially with the number of D2D links, we use the model decomposition and some iteration techniques in Stochastic Petri Nets (SPNs) to derive its approximate steady state solution, which is used to obtain the approximate performance metrics of the D2D communications in terms of average queue length, mean throughput, average packet delay and packet dropping probability of each link. Simulations are performed to verify the analytical results under different traffic loads and interference conditions. In this paper, a low-complexity delay-aware cross-layer scheduling algorithm for two-hop relay communication systems is proposed. The complex interactions of the queues at the source node and the M relay nodes (RSs) are modeled as an infinite horizon average reward Markov decision process (MDP), whose state space involves the joint queue state information (QSI) of the queues at the source node and the M RSs as well as the joint channel state information (CSI) of all S-R and R-D links. To address the curse of dimensionality, an equivalent MDP formulation is first proposed, where the system state depends only on global QSI. Furthermore, using approximate MDP and stochastic learning, an auction-based distributed online learning algorithm is derived, where each node iteratively estimates a per-node value function based on real-time observations of the local CSI and local QSI as well as signaling between relays. The combined distributed learning converges almost surely to a global optimal solution for large arrivals. Finally, it is showed by simulations that the proposed scheme achieves significant gain compared with various baselines such as the conventional CSIT-only control and the throughput optimal control (in stability sense). We consider the following queuing system which arises as a model of a wireless link shared by multiple users. There is a finite number N of input flows served by a server. The system operates in discrete time t = 0,1,2,…. Each input flow can be described as an irreducible countable Markov chain; waiting customers of each flow are placed in a queue. The sequence of server states m(t), t = 0,1,2,…, is a Markov chain with finite number of states M. When the server is in state m, it can serve mim customers of flow i (in one time slot).The scheduling discipline is a rule that in each time slot chooses the flow to serve based on the server state and the state of the queues. Our main result is that a simple online scheduling discipline, Modified Largest Weighted Delay First, along with its generalizations, is throughput optimal; namely, it ensures that the queues are stable as long as the vector of average arrival rates is within the system maximum stability region. Mobile-edge computing (MEC) emerges as a promising paradigm to improve the quality of computation experience for mobile devices. Nevertheless, the design of computation task scheduling policies for MEC systems inevitably encounters a challenging two-timescale stochastic optimization problem. Specifically, in the larger timescale, whether to execute a task locally at the mobile device or to offload a task to the MEC server for cloud computing should be decided, while in the smaller timescale, the transmission policy for the task input data should adapt to the channel side information. In this paper, we adopt a Markov decision process approach to handle this problem, where the computation tasks are scheduled based on the queueing state of the task buffer, the execution state of the local processing unit, as well as the state of the transmission unit. By analyzing the average delay of each task and the average power consumption at the mobile device, we formulate a power-constrained delay minimization problem, and propose an efficient one-dimensional search algorithm to find the optimal task scheduling policy. Simulation results are provided to demonstrate the capability of the proposed optimal stochastic task scheduling policy in achieving a shorter average execution delay compared to the baseline policies. This text presents a modern theory of analysis, control, and optimization for dynamic networks. Mathematical techniques of Lyapunov drift and Lyapunov optimization are developed and shown to enable constrained optimization of time averages in general stochastic systems. The focus is on communication and queueing systems, including wireless networks with time-varying channels, mobility, and randomly arriving traffic. A simple drift-plus-penalty framework is used to optimize time averages such as throughput, throughput-utility, power, and distortion. Explicit performance-delay tradeoffs are provided to illustrate the cost of approaching optimality. This theory is also applicable to problems in operations research and economics, where energy-efficient and profit-maximizing decisions must be made without knowing the future. Topics in the text include the following: - Queue stability theory - Backpressure, max-weight, and virtual queue methods - Primal-dual methods for non-convex stochastic utility maximization - Universal scheduling theory for arbitrary sample paths - Approximate and randomized scheduling theory - Optimization of renewal systems and Markov decision systems Detailed examples and numerous problem set questions are provided to reinforce the main concepts. Table of Contents: Introduction Introduction to Queues Dynamic Scheduling Example Optimizing Time Averages Optimizing Functions of Time Averages Approximate Scheduling Optimization of Renewal Systems Conclusions We consider the problem of resource allocation in downlink OFDMA systems for multi service and unknown environment. Due to users' mobility and intercell interference, the base station cannot predict neither the Signal to Noise Ratio (SNR) of each user in future time slots nor their probability distribution functions. In addition, the traffic is bursty in general with unknown arrival. The probability distribution functions of the SNR, channel state and traffic arrival density are then unknown. Achieving a multi service Quality of Service (QoS) while optimizing the performance of the system (e.g. total throughput) is a hard and interesting task since it depends on the unknown future traffic and SNR values. In this paper we solve this problem by modeling the multiuser queuing system as a discrete time linear dynamic system. We develop a robust H∞ controller to regulate the queues of different users. The queues and Packet Drop Rates (PDR) are controlled by proposing a minimum data rate according to the demanded service type of each user. The data rate vector proposed by the controller is then fed as a constraint to an instantaneous resource allocation framework. This instantaneous problem is formulated as a convex optimization problem for instantaneous subcarrier and power allocation decisions. Simulation results show small delays and better fairness among users. Microsimulation models are normally used to evaluate traffic-adaptive signal control systems. This paper develops an analytical approach for this evaluation based on queuing models. In particular, a queuing model is developed for a simplified adaptive control strategy that is based on rolling horizon scheme, in which a signal serves two movements alternatively. In this strategy, the first movement is served until the queue dissipates, then the second movement is served until the queue dissipates, then the signal goes back to serving the first movement, and this cyclic process repeats. A numerical algorithm is developed in a stochastic context to compute steady-state performance measures such as average delays and expected queue lengths. These results are compared with simulation-based results, and indeed, the analytically derived numerical method predicts well the simulation results We use fluid limits to explore the (in)stability properties of wireless networks with queue-based random-access algorithms. Queue-based random-access schemes are simple and inherently distributed in nature, yet provide the capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. Unfortunately, the type of activation rules for which throughput optimality has been established, may result in excessive queue lengths and delays. The use of more aggressive persistent access schemes can improve the delay performance, but does not offer any universal maximum-stability guarantees. In order to gain qualitative insight and investigate the (in)stability properties of more aggressive persistent activation rules, we examine fluid limits where the dynamics are scaled in space and time. In some situations, the fluid limits have smooth deterministic features and maximum stability is maintained, while in other scenarios they exihibit random oscillatory characteristics, giving rise to major technical challenges. In the latter regime, more aggressive access schemes continue to provide maximum stability in some networks, but may cause instability in others. In order to prove that, we focus on a particular network example and conduct a detailed analysis of the fluid limit process for the associated Markov chain. Specifically, we develop a novel approach based on stopping time sequences to deal with the switching probabilities governing the sample paths of the fluid limit process. Simulation experiments are conducted to illustrate and val- idate the analytical results. Keywords: Carrier-Sense Multiple Access (CSMA), fluid limits, queue-based strategies, stability issues. We consider a cognitive radio network where multiple secondary users (SUs) contend for spectrum usage, using random access, over available primary user (PU) channels. Our focus is on SUs' queueing delay performance, for which a systematic understanding is lacking. We take a fluid queue approximation approach to study the steady-state delay performance of SUs, for cases with a single PU channel and multiple PU channels. Using stochastic fluid models, we represent the queue dynamics as Poisson driven stochastic differential equations, and characterize the moments of the SUs' queue lengths accordingly. Since in practical systems, a secondary user would have no knowledge of other users' activities, its contention probability has to be set based on local information. With this observation, we develop adaptive algorithms to find the optimal contention probability that minimizes the mean queue lengths. Moreover, we study the impact of multiple channels and multiple interfaces, on SUs' delay performance. As expected, the use of multiple channels and or multiple interfaces leads to significant delay reduction. The joint spectrum partition and user association problem for multi-tier heterogeneous networks is studied in this paper, where disjoint spectrums are allocated among tiers and users are associated with each tier with a biased received power. The random placement of base-stations (BSs) of different tiers are modeled using stochastic geometry, which accounts for their practical deployment and also makes analysis tractable. We derive an upper bound of the average user proportional fair utility based on the user coverage rate, from which we formulate a network utility maximization problem. The optimization of the proposed utility bound shows that the optimal spectrum allocation for each BS tier matches the average proportion of users associated with that tier. The solution to the optimization problem also provides closed-form expressions for the optimal user associated bias factors. Compared to system-level optimization solutions based on specific network topology and channel realization, our offline analytical approach offers deployment insights. Simulation results demonstrates the effectiveness of the proposed approach. In this paper we study an optimal server allocation problem, where a single server is shared among multiple queues based on the queue backlog information. Due to the physical nature of the system this information is delayed, in that when the allocation decision is made, the server only has the backlog information from an earlier time. Queues have different arrival processes as well as different buffering holding costs. The objective is to minimize the expected total discounted holding cost over a finite or infinite horizon. We introduce an index policy where the index of a queue is a function of the state of the queue. Our primary interest is to characterize conditions under which this index policy is optimal. We present a fairly general method bounding the reward of serving one queue instead of another. Using this result, sufficient conditions on the optimality of the index policy can be derived for a variety of arrival processes and packet holding costs. These conditions are in general in the form of sufficient separation among indices, and they characterize the part of the state space where the index policy is optimal. We provide examples and derive the indices and illustrate the region where the index policy is optimal. We consider the setting of a network providing differentiated services. As is often the case in differentiated services, we assume that the packets are tagged as either being a high priority packet or a low priority packet. Outgoing links in the network are serviced by a single FIFO queue.Our model gives a benefit of α ≥ 1 to each high priority packet and a benefit of 1 to each low priority packet. A queue policy controls which of the arriving packets are dropped and which enter the queue. Once a packet enters the queue it is eventually sent. The aim of a queue policy is to maximize the sum of the benefits of all the packets it sends.We analyze and compare different queue policies for this problem using the competitive analysis approach, where the benefit of the online policy is compared to the benefit of an optimal offline policy. We derive both upper and lower bounds for the policies we consider. We believe that competitive analysis gives important insight to the performance of these queuing policies. Consider N parallel queues competing for the attention of a single server. At each time slot each queue may be connected to the server or not depending on the value of a binary random variable, the connectivity variable. Allocation at each slot; is based on the connectivity information and on the lengths of the connected queues only. At the end of each slot, service may be completed with a given fixed probability. Such a queueing model is appropriate for some communication networks with changing topology. In the case of infinite buffers, necessary and sufficient conditions are obtained for stabilizability of the system in terms of the different system parameters. The allocation policy that serves the longest connected queue stabilizes the system when the stabilizability conditions hold. The same policy minimizes the delay for the special case of symmetric queues. In a system with a single buffer per queue, an allocation policy is obtained that maximizes the throughput and minimizes the delay when the arrival and service statistics of different queues are identical. > In this paper, we consider a two-user and a three-user slotted ALOHA network with multi-packet reception (MPR) capabilities and a queue-aware transmission control. In this setting, the nodes can adapt their transmission probabilities and their transmission parameters based on the status of the other nodes. Each user has external bursty arrivals that are stored in their infinite capacity queues. We focus on the fundamental problem of characterizing the stable throughput region, as well as of investigating the queueing delay. For the two- and the three-user cases, we obtain the exact stability region, whereas in the former case, we also provide the conditions under which the stability region is a convex set. We perform a detailed mathematical analysis to study the queueing delay in the two-user case by formulating two boundary value problems, the solution of which provides the generating function of the joint stationary probability distribution of the queue size at user nodes. Furthermore, for the two-user symmetric case with MPR, we obtain a lower and an upper bound for the average delay without the need of solving a boundary value problem. In addition, we provide a closed form expression for the gap between the lower and the upper bound. The bounds as it is seen in the numerical results appear to be tight. Explicit expressions for the average delay are obtained for the symmetrical model with capture effect. We also provide a closed form expression for the optimal transmission probability that minimizes the average delay in the symmetric capture case. Finally, we evaluate numerically the presented theoretical results. Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop). In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric and show that the proposed scheme achieves optimal throughput performance. Furthermore, we conduct simulations to support our analytical results and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme. In cooperative relaying, multiple nodes cooperate to forward a packet within a network. To date, such schemes have been primarily investigated at the physical layer with the focus on communication of a single end-to-end flow. This paper considers cooperative relay networks with multiple stochastically varying flows, which may be queued within the network. Throughput optimal network control policies are studied that take into account queue dynamics to jointly optimize routing, scheduling and resource allocation. To this end, a generalization of the maximum differential backlog algorithm is given, which takes into account the cooperative gains in the network. Several structural characteristics of this policy are discussed for the special case of parallel relay networks. In this paper, a novel joint transmit power and resource allocation approach for enabling ultra-reliable low-latency communication (URLLC) in vehicular networks is proposed. The objective is to minimize the network-wide power consumption of vehicular users (VUEs) while ensuring high reliability in terms of probabilistic queuing delays. In particular, a reliability measure is defined to characterize extreme events (i.e., when vehicles' queue lengths exceed a predefined threshold with non-negligible probability) using extreme value theory (EVT). Leveraging principles from federated learning (FL), the distribution of these extreme events corresponding to the tail distribution of queues is estimated by VUEs in a decentralized manner. Finally, Lyapunov optimization is used to find the joint transmit power and resource allocation policies for each VUE in a distributed manner. The proposed solution is validated via extensive simulations using a Manhattan mobility model. It is shown that FL enables the proposed distributed method to estimate the tail distribution of queues with an accuracy that is very close to a centralized solution with up to 79 reductions in the amount of data that need to be exchanged. Furthermore, the proposed method yields up to 60 reductions of VUEs with large queue lengths, without an additional power consumption, compared to an average queue-based baseline. Compared to systems with fixed power consumption and focusing on queue stability while minimizing average power consumption, the reductions in extreme events of the proposed method is about two orders of magnitude.