# Analysis and Optimization of Resource Control in High-Speed Railway Wireless Networks

Authors: Shengfeng Xu; Gang Zhu; Chao Shen; Yan Lei; Zhangdui Zhong
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper considers a joint optimal design of admission control and resource allocation for multimedia services delivery in high-speed railway (HSR) wireless networks. A stochastic network optimization problem is formulated which aims at maximizing the system utility while stabilizing all transmission queues under the average power constraint. By introducing virtual queues, the original problem is equivalently transformed into a queue stability problem, which can be naturally decomposed into three separate subproblems: utility maximization, admission control, and resource allocation. A threshold-based admission control strategy is proposed for the admission control subproblem. And a distributed resource allocation scheme is developed for the mixed-integer resource allocation subproblem with guaranteed global optimality. Then a dynamic admission control and resource allocation algorithm is proposed, which is suitable for distributed implementation. Finally, the performance of the proposed algorithm is evaluated by theoretical analysis and numerical simulations under realistic conditions of HSR wireless networks.


---

## Body

## 1. Introduction

With the rapid development of high-speed railway (HSR) around the world, the wireless communication in HSR networks plays an important role in the recent years [1]. On the one hand, more and more data related with the railway controlling information needs to be transmitted between the train and the ground such that the safety can be guaranteed and the transportation efficiency can be significantly improved. On the other hand, the passengers in the train have an increasingly high demand on multimedia services. However, these requirements on high throughput impose a great challenge over the HSR communication designs due to the fast-varying channel, train penetration loss, and so forth.There have been some recent works to improve the throughput in HSR wireless networks. A two-hop HSR network architecture was proposed in [2] to provide high data-rate services. A HSR communication system based on radio over fiber technology was proposed in [3], which can increase the system throughput and help to reduce the number of handoffs. Multi-input multi-output (MIMO) antennas were employed to improve the throughput performance of the HSR wireless networks [4, 5]. However, these works were carried out only to improve the throughput performance in HSR wireless networks. Since the buffering is involved at network devices, for example, content servers, it is necessary to consider not only the throughput performance but also the queue stability in HSR wireless networks.Admission control and resource allocation, as critical parts of radio resource management, play important roles in improving the throughput and ensuring queue stability. In the literature, the energy constrained control algorithm was proposed in [6] to stabilize the queue and maximize the throughput by Lyapunov optimization theory. Paper [7] studied the joint scheduling and admission control problem in a single user scenario and an online learning algorithm was proposed based on the Markov decision process approach and stochastic control theory. However, these existing schemes designed for general communication systems are not easily extended to the scenario considered in this paper, due to the following reasons: (1) in HSR wireless networks, the channel condition cannot remain at the same level because of the fast-varying distance between the base station and the train, which causes that the power control along the time has a large influence on system transmission performance [8]; (2) many types of services with different quality-of-service (QoS) requirements and priorities should be supported [9], which makes the admission control and resource allocation for multiple services more challenging.In HSR wireless networks, few studies have been conducted on admission control and resource allocation. A scheduling and resource allocation mechanism was presented in [10] to maximize the service rate in HSR networks with a cell array architecture. In [11], a multidimensional resource allocation strategy was proposed in downlink orthogonal frequency-division multiplexing (OFDM) system for HSR communications. The optimal resource allocation problem in a cellular/infostation integrated HSR network was investigated in [12], which considered the intermittent network connectivity and multiservice demands. In a relay-assisted HSR network, [13] studied delay-aware fair downlink service scheduling problem with heterogeneous packet arrivals and delay requirements for the services. Paper [14] proposed an effective admission control scheme considering different service priorities for HSR communications with MIMO antennas. However, to the best of our knowledge, the joint admission control and resource allocation problem under the average power constraint in HSR wireless networks is still an open problem.The main contribution of this paper is a stochastic optimization framework for transmitting multimedia services in HSR wireless networks, which focuses on the joint admission control and resource allocation problem under the average power constraint. Firstly, the joint admission control and resource allocation problem is formulated as a stochastic optimization problem, and then the problem is transformed into a queue stability problem with the help of virtual queues. By the drift-plus-penalty approach [15], the transformed problem can be decomposed into three separate subproblems: utility maximization, admission control, and resource allocation. The former two subproblems are easy to handle and the distributed solutions can be obtained directly, while the mixed-integer resource allocation subproblem is transformed into a single variable problem and a distributed packet loading scheme is developed with guaranteed global optimality. We further propose a dynamic admission control and resource allocation algorithm, which is suitable for distributed implementation in HSR wireless networks. Finally, we present the analysis of algorithm performance by theoretical derivations and simulations under realistic conditions for HSR wireless networks.


### 1.1. Relation to Prior Work

The Lyapunov drift theory has a long history in the field of discrete stochastic processes and Markov chains [16]. It can be used to directly analyze the characteristics of the control policies in the stochastic stability sense and plays important roles in the dynamic control strategies in queuing networks [17]. Stabilizing queuing networks by minimizing Lyapunov drift was pioneered by Tassiulas and Ephremides in [18]. The Lyapunov drift theory was then extended to the Lyapunov optimization theory [6], which enables optimization of time averages of general network utilities subject to queue stability. A general framework for solving the stochastic network optimization problem based on Lyapunov optimization theory was developed in [15]. This framework has been extended to minimizing a drift-plus-penalty expression in [6, 7, 17, 19, 20] for joint queue stability and time average utility optimization. For the engineering applications of Lyapunov optimization theory, interested readers are referred to the aforementioned references for the details.Our approach in the present paper treats the joint admission control and resource allocation problem associated with average power constraint using Lyapunov drift and Lyapunov optimization theory from [15]. This is the first time, to the best of our knowledge, that the Lyapunov optimization theory is extended into the HSR wireless networks. Considering the features of HSR wireless networks, the Lyapunov optimization theory is successfully applied for solving the joint admission control and resource allocation problem in HSR wireless network.


### 1.2. Outline of Paper

The rest of the paper is organized as follows. Section2 describes the system model. The problem formulation and transformation are provided in Section 3. A distributed dynamic admission control and resource allocation algorithm is proposed in Section 4. Some numerical results and discussions are shown in Section 5. Finally, conclusions are drawn in Section 6.Notations. In this paper, 𝔼[·] denotes expectation. ⌊x⌋=max⁡{n∈ℤ∣n≤x}. max⁡[x,y] and min⁡[x,y] mean the maximum and minimum between x and y, respectively.


## 1.1. Relation to Prior Work

The Lyapunov drift theory has a long history in the field of discrete stochastic processes and Markov chains [16]. It can be used to directly analyze the characteristics of the control policies in the stochastic stability sense and plays important roles in the dynamic control strategies in queuing networks [17]. Stabilizing queuing networks by minimizing Lyapunov drift was pioneered by Tassiulas and Ephremides in [18]. The Lyapunov drift theory was then extended to the Lyapunov optimization theory [6], which enables optimization of time averages of general network utilities subject to queue stability. A general framework for solving the stochastic network optimization problem based on Lyapunov optimization theory was developed in [15]. This framework has been extended to minimizing a drift-plus-penalty expression in [6, 7, 17, 19, 20] for joint queue stability and time average utility optimization. For the engineering applications of Lyapunov optimization theory, interested readers are referred to the aforementioned references for the details.Our approach in the present paper treats the joint admission control and resource allocation problem associated with average power constraint using Lyapunov drift and Lyapunov optimization theory from [15]. This is the first time, to the best of our knowledge, that the Lyapunov optimization theory is extended into the HSR wireless networks. Considering the features of HSR wireless networks, the Lyapunov optimization theory is successfully applied for solving the joint admission control and resource allocation problem in HSR wireless network.


## 1.2. Outline of Paper

The rest of the paper is organized as follows. Section2 describes the system model. The problem formulation and transformation are provided in Section 3. A distributed dynamic admission control and resource allocation algorithm is proposed in Section 4. Some numerical results and discussions are shown in Section 5. Finally, conclusions are drawn in Section 6.Notations. In this paper, 𝔼[·] denotes expectation. ⌊x⌋=max⁡{n∈ℤ∣n≤x}. max⁡[x,y] and min⁡[x,y] mean the maximum and minimum between x and y, respectively.


## 2. System Model

In this paper, a two-hop HSR wireless network architecture is considered, as shown in Figure1, which consists of a backbone network, K content servers (CSs), several base stations (BSs), a relay station (RS), and some users in the train. The BSs deployed along the rail line can provide continuous data packets delivery. The distributed CSs connected to the BSs via wireline links are deployed in the backbone network to offload the data traffic [21]. The RS with powerful antennas installed on the top of the train is used for communicating with the BSs so that the large train penetration loss can be well resolved. The RS is further connected to the access points (APs) which can be accessed by the users inside the train. Thus, there is a two-hop wireless link, consisting of the BS-RS link and the AP-Users link. If the users on the train request multimedia services during a trip, the data packets of the requested services are then delivered from the corresponding CS to the RS via a BS. Suppose that the data transmission rate in the AP-Users link is sufficiently large; hence the data packet can be successfully received if it has been delivered to the RS.Figure 1
System model.


### 2.1. Time-Distance Mapping

Consider a train traveling from an origin station to a destination station within the time duration[0,T]. The whole time is divided into slots of equal duration Ts. Without loss of generality, we assume that the train starts at the centre of the first cell and the train moving speed during the slot t keeps constant, denoted by v(t); thus the traveled distance until slot t is given by s(t)=∑τ=0t‍v(τ)Ts. The train location between two adjacent BSs at slot t is s1(t)=s(t)mod⁡2R, where R is the cell radius. Define a time-distance mapping function d(t) as the distance between BS and RS at slot t; that is, d(t):[0,T]→[d0,dmax⁡], where dmax⁡=R2+d02 and d0 is the distance between each BS and the rail line as shown in Figure 1. The mapping function d(t) can be expressed by
(1)d(t)={s1(t)2+d02,if0≤s1(t)<R,(2R-s1(t))2+d02,ifR≤s1(t)<2R.
Here we assume that the distance d(t) does not change within slot t since Ts is very small.


### 2.2. Physical Layer Model

For HSR wireless networks, the channel condition cannot remain at the same level due to the fast-varying distance between BS and RS. Only the line-of-sight (LOS) path in the BS-RS link is available at most of the time, which was confirmed by engineering measurements [22, 23]. The service provided by the independent identical distributed (i.i.d.) fading channels is a deterministic time-linear function, just like the AWGN channel [24]. Therefore, the wireless channel in the BS-RS link can be assumed to be an additive white Gaussian noise channel (AWGN) with LOS path loss [8]. At the same time, the power control along the travel time in HSR wireless networks is important. Denote by P(t) the transmit power of the BS at slot t, which is limited by the maximum value Pmax⁡ and average value Pav. With the help of mapping function d(t) and according to Shannon's theorem [25], the transmission rate of the wireless channel between BS and RS at slot t can be expressed by
(2)R(t)=Wlog⁡2(1+P(t)N(t))bits/s,
where N(t)=WN0dα(t), W is the system bandwidth, N0 is the noise power spectral density, and α is the path loss exponent. Suppose that the packets have equal size of L bits; hence the link capacity C(t) at slot t can be denoted as the maximum number of packets; that is, C(t)=⌊R(t)Ts/L⌋. Note that the maximum capacity Cmax⁡ can be obtained when d(t)=d0 and P(t)=Pmax⁡.


### 2.3. Service Model

Assume that there areK types of services in the HSR wireless networks and the service type set is denoted by 𝒦≜{1,…,K}. We further assume that CSk is equipped with a buffer and can provide service k, for k∈𝒦. Let A(t)=[A1(t),…,AK(t)]T represent the packet arrival vector, where Ak(t) denotes the number of new arrival packets of service k at slot t. The packet arrival process for each service is assumed to be i.i.d. across slots. Suppose that, in general, Ak(t) follows a truncated Poisson distribution fk(b) with average arrival rate λk=𝔼[Ak(t)] for service k, and the distribution fk(b) can be written as
(3)fk(b)=exp⁡(-λk)λkbb!,b=0,…,Bk,
where Bk denotes the maximum number of arrival packets per slot for service k and can be found assuming fk(Bk)→0.LetQ(t)=[Q1(t),…,QK(t)]T represent the vector of current queue backlogs, where Qk(t) denotes the number of packets at the beginning of slot t in the buffer of CSk. The dynamics of each buffer are controlled by admission control (AC) and resource allocation (RA) actions. Specifically, at each slot, the AC action determines the number of packets from the newly arriving packets to be stored into the buffer. And the RA action determines the number of packets removed from the buffer for transmission. Let rk(t)∈[0,Ak(t)] and μk(t)∈[0,Qk(t)] denote the AC action and RA action for service k at slot t, respectively. Thus, the queue dynamics can be characterized by
(4)Qk(t+1)=Qk(t)-μk(t)+rk(t),∀k∈𝒦.
Notice that for any slot t, without AC actions, rk(t)=Ak(t). Here we assume that the arrival packets at slot t can only be transmitted at slot t+1.


## 2.1. Time-Distance Mapping

Consider a train traveling from an origin station to a destination station within the time duration[0,T]. The whole time is divided into slots of equal duration Ts. Without loss of generality, we assume that the train starts at the centre of the first cell and the train moving speed during the slot t keeps constant, denoted by v(t); thus the traveled distance until slot t is given by s(t)=∑τ=0t‍v(τ)Ts. The train location between two adjacent BSs at slot t is s1(t)=s(t)mod⁡2R, where R is the cell radius. Define a time-distance mapping function d(t) as the distance between BS and RS at slot t; that is, d(t):[0,T]→[d0,dmax⁡], where dmax⁡=R2+d02 and d0 is the distance between each BS and the rail line as shown in Figure 1. The mapping function d(t) can be expressed by
(1)d(t)={s1(t)2+d02,if0≤s1(t)<R,(2R-s1(t))2+d02,ifR≤s1(t)<2R.
Here we assume that the distance d(t) does not change within slot t since Ts is very small.


## 2.2. Physical Layer Model

For HSR wireless networks, the channel condition cannot remain at the same level due to the fast-varying distance between BS and RS. Only the line-of-sight (LOS) path in the BS-RS link is available at most of the time, which was confirmed by engineering measurements [22, 23]. The service provided by the independent identical distributed (i.i.d.) fading channels is a deterministic time-linear function, just like the AWGN channel [24]. Therefore, the wireless channel in the BS-RS link can be assumed to be an additive white Gaussian noise channel (AWGN) with LOS path loss [8]. At the same time, the power control along the travel time in HSR wireless networks is important. Denote by P(t) the transmit power of the BS at slot t, which is limited by the maximum value Pmax⁡ and average value Pav. With the help of mapping function d(t) and according to Shannon's theorem [25], the transmission rate of the wireless channel between BS and RS at slot t can be expressed by
(2)R(t)=Wlog⁡2(1+P(t)N(t))bits/s,
where N(t)=WN0dα(t), W is the system bandwidth, N0 is the noise power spectral density, and α is the path loss exponent. Suppose that the packets have equal size of L bits; hence the link capacity C(t) at slot t can be denoted as the maximum number of packets; that is, C(t)=⌊R(t)Ts/L⌋. Note that the maximum capacity Cmax⁡ can be obtained when d(t)=d0 and P(t)=Pmax⁡.


## 2.3. Service Model

Assume that there areK types of services in the HSR wireless networks and the service type set is denoted by 𝒦≜{1,…,K}. We further assume that CSk is equipped with a buffer and can provide service k, for k∈𝒦. Let A(t)=[A1(t),…,AK(t)]T represent the packet arrival vector, where Ak(t) denotes the number of new arrival packets of service k at slot t. The packet arrival process for each service is assumed to be i.i.d. across slots. Suppose that, in general, Ak(t) follows a truncated Poisson distribution fk(b) with average arrival rate λk=𝔼[Ak(t)] for service k, and the distribution fk(b) can be written as
(3)fk(b)=exp⁡(-λk)λkbb!,b=0,…,Bk,
where Bk denotes the maximum number of arrival packets per slot for service k and can be found assuming fk(Bk)→0.LetQ(t)=[Q1(t),…,QK(t)]T represent the vector of current queue backlogs, where Qk(t) denotes the number of packets at the beginning of slot t in the buffer of CSk. The dynamics of each buffer are controlled by admission control (AC) and resource allocation (RA) actions. Specifically, at each slot, the AC action determines the number of packets from the newly arriving packets to be stored into the buffer. And the RA action determines the number of packets removed from the buffer for transmission. Let rk(t)∈[0,Ak(t)] and μk(t)∈[0,Qk(t)] denote the AC action and RA action for service k at slot t, respectively. Thus, the queue dynamics can be characterized by
(4)Qk(t+1)=Qk(t)-μk(t)+rk(t),∀k∈𝒦.
Notice that for any slot t, without AC actions, rk(t)=Ak(t). Here we assume that the arrival packets at slot t can only be transmitted at slot t+1.


## 3. Problem Formulation and Transformation

### 3.1. Problem Formulation

In this paper, the objective of the joint AC and RA problem is to maximize a sum of utility functions under time average constraints by designing a dynamic algorithm over a trip of the train. We define thatϕk(rk) is a utility function to present throughput benefit for service k, which is nondecreasing concave continuous with rk. Throughout this work, the following notation for the long-term time average expectation of any quantity z is defined:
(5)z¯:=lim⁡t→∞1t∑τ=0t-1‍𝔼[z(τ)].
In particular, Q¯k represents the average queue backlog in the buffer of CSk and P¯ represents the average power consumption along the travel time. Here we introduce the definitions of queue stability as follows [15].Definition 1.
A single queueQ(t) is mean rate stable if lim⁡t→∞(𝔼[Q(t)]/t)=0.Definition 2.
A single queueQ(t) is strongly stable if Q¯<∞.From Definition2, a queue is strongly stable if it has a bounded time average backlog. Strong stability implies mean rate stability according to [15]. Throughout this paper, we use the term “stability” to refer to strong stability. Define Ω(t)≜(A(t),C(t)) as the observed network event at slot t. For each slot t, observing the event Ω(t) and the queue state Q(t), the AC actions rk(t) and RA actions μk(t) should be made for k∈𝒦. The joint AC and RA problem is formulated as(6a)(P1)maximize∑k∈𝒦‍ϕk(r¯k)(6b)subjecttoP¯≤Pav,P(t)≤Pmax⁡,∀t∈[0,T],(6c)Q¯k<∞,∀k∈𝒦,(6d)0≤∑k∈𝒦‍μk(t)≤C(t),∀t∈[0,T],(6e)μk(t)∈[0,Qk(t)],∀t∈[0,T],(6f)rk(t)∈[0,Ak(t)],∀t∈[0,T],(6g)variablesrk(t),μk(t),P(t),∀k∈𝒦,t∈[0,T],where (6b) corresponds to the power constraint and (6c) corresponds to the queue stability constraints for all queues. Problem (P1) is a stochastic optimization problem [15], but it cannot be solved efficiently owing to the difficulty from the objective function (6a) and the average power constraint in (6b). In order to better characterize the problem (P1) and develop an efficient algorithm, we consider the problem transformation, which consists of two steps, that is, objective function transformation and average power constraint transformation as presented in the following subsections.


### 3.2. Objective Function Transformation

Since problem (P1) involves maximizing a function of time averages, it is hard to handle. Based on the dynamic stochastic optimization theory [15], it can be transformed into an equivalent problem that involves maximizing a single time average of a function. This transformation is achieved through the use of auxiliary variables γk(t) and corresponding virtual queues Zk(t) with queue evolutions:
(7)Zk(t+1)=max⁡[Zk(t)-rk(t),0]+γk(t),∀k∈𝒦,
where the initial condition is assumed that Zk(0)=0,∀k∈𝒦. Intuitively, the auxiliary variables γk(t) can be viewed as the “arrivals” of virtual queues Zk(t), while rk(t) can be viewed as the service rate of such virtual queues.Then, we consider the following transformed problem:(8a)(P2)maximize∑k∈𝒦‍ϕk(γk)¯(8b)subjecttoγ¯k≤r¯k,∀k∈𝒦,(8c)0≤γk(t)≤Bk,∀k∈𝒦,t∈[0,T],(8d)(6b)–(6f),(8e)variablesγk(t),rk(t),μk(t),P(t),∀k∈𝒦,t∈[0,T]. Constraint (8b) corresponds to the stability of the virtual queue Zk(t), since γ¯k and r¯k are regarded as the time-averaged arrival rate and the time-averaged service rate for the virtual queue Zk(t), respectively. Specifically, from (7) we can obtain that Zk(t+1)≥Zk(t)-rk(t)+γk(t). By summing this inequality over time slots τ∈{0,1,…,t-1} and then dividing the result by t, we have that (Zk(t)-Zk(0))/t+(1/t)∑τ=0t-1‍rk(τ)≥(1/t)∑τ=0t-1‍γk(t). With Zk(0)=0, taking expectations of both sides yields that lim⁡t→∞(𝔼[Zk(t)]/t)+r¯k≥γ¯k. If the virtual queues Zk(t) are mean rate stable, then lim⁡t→∞(𝔼[Zk(t)]/t)=0, so that constraint (8b) can be satisfied. Notice that we will prove the strong stability of the virtual queues Zk(t) in Lemma 7 later.Lemma 3.
Problem (P1) and problem (P2) are equivalent.Proof.
The proof of Lemma3 follows [26] and a sketch of the proof is provided in Appendix A.


### 3.3. Average Power Constraint Transformation

To handle the average power constraint in (6b), we define a virtual queue Xk(t) for each k∈𝒦, which has the following dynamic update equation:
(9)Xk(t+1)=max⁡[Xk(t)-Pav,0]+P(t),
where P(t) and Pav can be viewed as the “arrivals” and “offered service” at slot t, respectively.Based on [15, Chapter 4], if the virtual queue Xk(t) is mean rate stable for k∈𝒦, that is, lim⁡t→∞(𝔼[Xk(t)]/t)=0, then the average power constraint P¯≤Pav can be satisfied. This holds because if the backlog in the virtual queue is stabilized, it must be the case that the time average arrival rate (corresponding to P¯) is not larger than the service rate (corresponding to Pav). Therefore, the average power constraint in (6b) can be transformed into a single queue stability problem.


## 3.1. Problem Formulation

In this paper, the objective of the joint AC and RA problem is to maximize a sum of utility functions under time average constraints by designing a dynamic algorithm over a trip of the train. We define thatϕk(rk) is a utility function to present throughput benefit for service k, which is nondecreasing concave continuous with rk. Throughout this work, the following notation for the long-term time average expectation of any quantity z is defined:
(5)z¯:=lim⁡t→∞1t∑τ=0t-1‍𝔼[z(τ)].
In particular, Q¯k represents the average queue backlog in the buffer of CSk and P¯ represents the average power consumption along the travel time. Here we introduce the definitions of queue stability as follows [15].Definition 1.
A single queueQ(t) is mean rate stable if lim⁡t→∞(𝔼[Q(t)]/t)=0.Definition 2.
A single queueQ(t) is strongly stable if Q¯<∞.From Definition2, a queue is strongly stable if it has a bounded time average backlog. Strong stability implies mean rate stability according to [15]. Throughout this paper, we use the term “stability” to refer to strong stability. Define Ω(t)≜(A(t),C(t)) as the observed network event at slot t. For each slot t, observing the event Ω(t) and the queue state Q(t), the AC actions rk(t) and RA actions μk(t) should be made for k∈𝒦. The joint AC and RA problem is formulated as(6a)(P1)maximize∑k∈𝒦‍ϕk(r¯k)(6b)subjecttoP¯≤Pav,P(t)≤Pmax⁡,∀t∈[0,T],(6c)Q¯k<∞,∀k∈𝒦,(6d)0≤∑k∈𝒦‍μk(t)≤C(t),∀t∈[0,T],(6e)μk(t)∈[0,Qk(t)],∀t∈[0,T],(6f)rk(t)∈[0,Ak(t)],∀t∈[0,T],(6g)variablesrk(t),μk(t),P(t),∀k∈𝒦,t∈[0,T],where (6b) corresponds to the power constraint and (6c) corresponds to the queue stability constraints for all queues. Problem (P1) is a stochastic optimization problem [15], but it cannot be solved efficiently owing to the difficulty from the objective function (6a) and the average power constraint in (6b). In order to better characterize the problem (P1) and develop an efficient algorithm, we consider the problem transformation, which consists of two steps, that is, objective function transformation and average power constraint transformation as presented in the following subsections.


## 3.2. Objective Function Transformation

Since problem (P1) involves maximizing a function of time averages, it is hard to handle. Based on the dynamic stochastic optimization theory [15], it can be transformed into an equivalent problem that involves maximizing a single time average of a function. This transformation is achieved through the use of auxiliary variables γk(t) and corresponding virtual queues Zk(t) with queue evolutions:
(7)Zk(t+1)=max⁡[Zk(t)-rk(t),0]+γk(t),∀k∈𝒦,
where the initial condition is assumed that Zk(0)=0,∀k∈𝒦. Intuitively, the auxiliary variables γk(t) can be viewed as the “arrivals” of virtual queues Zk(t), while rk(t) can be viewed as the service rate of such virtual queues.Then, we consider the following transformed problem:(8a)(P2)maximize∑k∈𝒦‍ϕk(γk)¯(8b)subjecttoγ¯k≤r¯k,∀k∈𝒦,(8c)0≤γk(t)≤Bk,∀k∈𝒦,t∈[0,T],(8d)(6b)–(6f),(8e)variablesγk(t),rk(t),μk(t),P(t),∀k∈𝒦,t∈[0,T]. Constraint (8b) corresponds to the stability of the virtual queue Zk(t), since γ¯k and r¯k are regarded as the time-averaged arrival rate and the time-averaged service rate for the virtual queue Zk(t), respectively. Specifically, from (7) we can obtain that Zk(t+1)≥Zk(t)-rk(t)+γk(t). By summing this inequality over time slots τ∈{0,1,…,t-1} and then dividing the result by t, we have that (Zk(t)-Zk(0))/t+(1/t)∑τ=0t-1‍rk(τ)≥(1/t)∑τ=0t-1‍γk(t). With Zk(0)=0, taking expectations of both sides yields that lim⁡t→∞(𝔼[Zk(t)]/t)+r¯k≥γ¯k. If the virtual queues Zk(t) are mean rate stable, then lim⁡t→∞(𝔼[Zk(t)]/t)=0, so that constraint (8b) can be satisfied. Notice that we will prove the strong stability of the virtual queues Zk(t) in Lemma 7 later.Lemma 3.
Problem (P1) and problem (P2) are equivalent.Proof.
The proof of Lemma3 follows [26] and a sketch of the proof is provided in Appendix A.


## 3.3. Average Power Constraint Transformation

To handle the average power constraint in (6b), we define a virtual queue Xk(t) for each k∈𝒦, which has the following dynamic update equation:
(9)Xk(t+1)=max⁡[Xk(t)-Pav,0]+P(t),
where P(t) and Pav can be viewed as the “arrivals” and “offered service” at slot t, respectively.Based on [15, Chapter 4], if the virtual queue Xk(t) is mean rate stable for k∈𝒦, that is, lim⁡t→∞(𝔼[Xk(t)]/t)=0, then the average power constraint P¯≤Pav can be satisfied. This holds because if the backlog in the virtual queue is stabilized, it must be the case that the time average arrival rate (corresponding to P¯) is not larger than the service rate (corresponding to Pav). Therefore, the average power constraint in (6b) can be transformed into a single queue stability problem.


## 4. The Distributed Dynamic AC and RA Algorithm

In this section, the dynamic stochastic optimization approach is applied to solve problem (P2), which seeks to maximize the sum of time-averaged utility functions subject to queue stability constraints. Firstly, the problem (P2) is decomposed into three separate subproblems by the drift-plus-penalty approach. Then a distributed dynamic AC and RA algorithm is proposed. Finally, the performance of the proposed algorithm is analyzed by theoretical derivations.


### 4.1. Lyapunov Drift

DefineX(t) and Z(t) as a vector of all virtual queues Xk(t) and Zk(t) for k∈𝒦, respectively. We denote by Θ(t) the combined vector of all virtual queues and all actual queues; namely,
(10)Θ(t)≜[QT(t),XT(t),ZT(t)]T.
The quadratic Lyapunov function is defined as [15]
(11)L(Θ(t))≜12∑k∈𝒦‍(Qk(t)2+Xk(t)2+Zk(t)2).
Then the one-slot conditional Lyapunov drift Δ(Θ(t)) at slot t is given by
(12)Δ(Θ(t))=𝔼[L(Θ(t+1))-L(Θ(t))∣Θ(t)],
which admits the following lemma.Lemma 4.
Under any AC actions and RA actions at slott, and for any value of Θ(t), we have
(13)Δ(Θ(t))≤D+𝔼[G(t)∣Θ(t)],
where D is a finite constant defined by
(14)D≜12∑k∈𝒦‍[Pmax⁡2+Pav2+3Bk2+Cmax⁡2],
and G(t) is defined by
(15)G(t)≜∑k∈𝒦‍Qk(t)[rk(t)-μk(t)]+∑k∈𝒦‍Zk(t)(γk(t)-rk(t))+∑k∈𝒦‍Xk(t)[P(t)-Pav].Proof.
The proof of Lemma4 is provided in Appendix B.


### 4.2. The Drift-Plus-Penalty Expression

Instead of directly minimizing the upper bound𝔼[G(t)] by taking AC actions and RA actions, we desire to jointly stabilize all queues and maximize the sum of utility ∑k∈𝒦‍ϕk(γk(t)). The drift-plus-penalty theory in [6] approaches this by greedily minimizing the following “drift-plus-penalty” expression:
(16)𝔼[G(t)-V∑k∈𝒦‍ϕk(γk(t))],
where V≥0 is a parameter that represents the weight on how much we emphasize the sum utility maximization.We observe that the objective function in (16) is of separable structure, which motivates us to determine the auxiliary variables γk(t) and AC actions rk(t) as well as RA actions μk(t) in an alternative optimization fashion. The overall minimization problem (16) is decomposed into three separate subproblems. Specifically, isolating the γk(t) variables from (16) gives the followingutility maximization subproblem:
(17a)max⁡{γk(t)}∑k∈𝒦‍[Vϕk(γk(t))-Zk(t)γk(t)](17b)s.t.0≤γk(t)≤Bk,∀k∈𝒦,t∈[0,T].Similarly, isolating the AC actions rk(t) from (16) leads to the followingadmission control subproblem:
(18a)max⁡{rk(t)}∑k∈𝒦‍[(Zk(t)-Qk(t))rk(t)](18b)s.t.0≤rk(t)≤Ak(t),∀k∈𝒦,t∈[0,T].Also, isolating the RA actions μk(t) from (16) gives the followingresource allocation subproblem:
(19a)max⁡{μk(t)},P(t)∑k∈𝒦‍[Qk(t)μk(t)-Xk(t)P(t)](19b)s.t.0≤μk(t)≤Qk(t),μk(t)∈ℕ,∀k∈𝒦,t∈[0,T],(19c)∑k∈𝒦‍μk(t)≤C(t),t∈[0,T],(19d)P(t)≤Pmax⁡,t∈[0,T],where P(t) is related to μk(t) since a larger μk(t) requires more power consumption. These separate subproblems can be computed in a decentralized fashion, as stated below.


### 4.3. Utility Maximization

The utility maximization subproblem ((17a) and (17b)) can be decoupled into K separate maximization problems. Specifically, CSk keeps track of Zk(t) and determines the optimum γk(t) by solving the following problem:
(20a)max⁡γk(t)Vϕk(γk(t))-Zk(t)γk(t)(20b)s.t.0≤γk(t)≤Bk,t∈[0,T].Notice that the key point to solve (20a) and (20b) is the choice of the utility function, which is contingent on the purpose of the networking application or the prerogative of HSR network designer. For example, in order to represent the maximum desired delivery ratio for each service, the piecewise linear utility function can be considered for service k as follows:
(21)ϕk(γk)=νkmin⁡[γk,xkλk],
where νk>0 and xk>0 represent the priority and the maximum desired delivery ratio of service k, respectively. In general, 0≤xk≤1 and xkλk≤Bk for k∈𝒦. Thus the optimal solution to problem (20a) and (20b) is given by
(22)γk(t)={xkλk,ifZk(t)≤Vνk,0,otherwise.
Alternatively, the following strictly concave function can serve as the utility function for service k:
(23)ϕk(γk)=ln⁡(1+νkγk),
which can be regarded as an accurate approximation of the proportionally fair utility function if the same νk is selected with a large value for all k∈𝒦. In this case, the optimal solution to problem (20a) and (20b) can be obtained by
(24)γk(t)=[VZk(t)-1νk]0Bk,
where the operation [y]0a is equal to y if 0<y<a, 0 if y≤0, and a if y≥a.


### 4.4. Admission Control

The admission control subproblem ((18a) and (18b)) can be also decoupled into K separate maximization problems. Specifically, CSk chooses the AC action rk(t) by solving the following optimization problem:
(25)max⁡rk(t)(Zk(t)-Qk(t))rk(t)s.t.0≤rk(t)≤Ak(t),t∈[0,T].
It is immediate to see that the optimal solution depends on the queue backlog of Zk(t) and Qk(t), which is given by
(26)rk(t)={Ak(t),ifZk(t)≥Qk(t),0,otherwise.
We note that (26) is a simple threshold-based admission control strategy. On the one hand, when the queue backlog Qk(t) is not larger than the threshold Zk(t), then all the newly arriving packets are admitted into the buffer in CSk. Essentially, this not only reduces the value of Zk(t+1) so as to push γ¯k closer to r¯k, but also increases the average throughput r¯k so as to improve the utility. On the other hand, when the queue backlog Qk(t) is larger than the threshold Zk(t), then all the newly arriving packets will be dropped to ensure the network stability. Finally, we emphasize that the AC actions for all services are made in a distributed manner with only local queue backlog information and packet arrival information.


### 4.5. Resource Allocation

The resource allocation subproblem ((19a)–(19d)) at slot t can be explicitly expressed as(27a)max⁡{μk(t)},P(t)M(t)≜∑k∈𝒦‍[Qk(t)μk(t)-Xk(t)P(t)](27b)s.t.0≤μk(t)≤Qk(t),μk(t)∈ℕ,∀k∈𝒦,(27c)∑k∈𝒦‍μk(t)≤C(t)=⌊TsWlog⁡2(1+P(t)/N(t))L⌋,(27d)P(t)≤Pmax⁡. The problem (27a)–(27d) is a mixed-integer programming (MIP) problem, including a continuous variable P(t) and K integer variables μk(t), which cannot be solved efficiently [27]. The main difficulty of problem (27a)–(27d) comes from the integer nature of μk(t). However, we will show that problem (27a)–(27d) can be transformed into a single variable problem, which is easy to handle. In the sequel of this subsection, we will omit the time index for brevity.Firstly, as for constraint (27c), when the optimal RA actions are achieved, it can be shown that
(28)∑k‍μk=C=1ηlog⁡2(1+PN),
where η=L/TsW>0. Otherwise we can reduce the value of C and P such that the objective function can be further maximized without any violation of the constraints in (27b)–(27d). From (28), we have the following power consumption of C:
(29)P=N(2ηC-1),
and constraints (27b) and (27d) further imply that
(30)0≤C≤min⁡(∑k∈𝒦‍Qk,C~max⁡),
where C~max⁡≜(1/η)log⁡2(1+Pmax⁡/N).Secondly, the resource allocation subproblem (27a)–(27d) can be equivalently transformed into a single variable problem as follows:
(31a)max⁡C∈ℕM^(C)≜g1(C)-g2(C)(31b)s.t.(30),where g1(C) is given by(32a)g1(C)≜max⁡{μk}∑k∈𝒦‍Qkμk(32b)s.t.0≤μk≤Qk,μk∈ℕ,∀k∈𝒦,(32c)∑k∈𝒦‍μk=C,and g2(C) is given by
(33)g2(C)≜∑k=1K‍XkP=∑k=1K‍Xk(2ηC-1)N=ρ(2ηC-1),
with ρ≜N∑k=1K‍Xk.Now let us focus on the problem (32a)–(32c) with any given C. Clearly, the maximum objective value of (32a)–(32c) can always be achieved by allocating link capacity C to the services in the descending order of their backlogs, which is similar to the max-weight algorithm in [15]. Hence, we sort all the services in descending order of Qk and denote the ordered set by {k1,k2,…,kK}. For convenience, we define f(m)=∑n=0m‍Qkn(t) for m=0,1,…,K, where Qk0(t)=0. One can see that f(m) is an increasing function of m, and 0≤C≤f(K) from (30). Therefore the optimal solutions to the problem (32a)–(32c) are given by
(34)μkn={Qkn,if1≤n<m,C-f(n-1),ifn=m,0,ifm<n≤K,
where m∈{1,…,K} such that C∈(f(m-1),f(m)] if C>0; otherwise μkn=0 for all n.Next, let us focus on problem (31a)-(31b). Indeed, we have the following lemma.Lemma 5.
M
^
(
C
) is a unimodal function of C over [0,f(K)].Proof.
On the one hand, sinceΔg1(C)=g1(C+1)-g1(C)=Qkm for f(m-1)≤C(t)<f(m),∀m∈[1,K], Δg1(C) is a monotonically nonincreasing function of C. On the other hand, since Δg2(C)=ρ(2η-1)2ηC, Δg2(C) is a monotonically increasing function of C. Therefore ΔM^(C)=Δg1(C)-Δg2(C), which is a monotonically decreasing function of C. For any C∈[1,f(K)-1], ΔM^(C-1)>ΔM^(C), which implies M^(C)>(1/2)(M^(C-1)+M^(C+1)), so M^(C) is concave on [0,f(K)]. Based on [28], if M^(C) is concave, then M^(C) is unimodal.Based on Lemma5, since M^(C) is a unimodal function of C over [0,min⁡{C~max⁡,f(K)}], the golden section search method [29] can be used to obtain the global optimal solution to the problem (31a)-(31b). However, this method requires the knowledge of all queue backlog information. When the center controller is not available, a distributed resource allocation scheme is highly desirable. Relying on the insights from Lemma 5, we propose a distributed resource allocation scheme, where each CS can communicate with all other CSs, and the network resources are allocated packet by packet.The proposed packet loading resource allocation scheme is detailed in Algorithm1. For each slot, each CS exchanges the backlog information with all other CSs and the order of the backlogs is obtained by all CSs (step 2). Then the packets of the services are fetched from the corresponding CS in descending order of their backlogs. When one CS fetches a new packet (step 5), M^(C) is calculated (step 6). This will be repeated until the optimal condition in step 7 is satisfied, which implies that M^(C-1) is the maximum or constraint (30) is violated, and thus step 8 should be performed since the last packet cannot be transmitted. When one CS empties its buffer, it should send the value information of C to the next CS (step 12), and the next CS should continue the resource allocation. Here we remark that the optimal solutions can be achieved by the proposed scheme, which can be readily proved by Lemma 5.Algorithm 1:Packet loading resource allocation scheme for problem (27a) – (27d).
(1) Initializeμk=0 for k∈𝒦; M^(0)=0; C=0;
(2)  Sort services in descending ofQk and obtain the ordered set {k1,k2,…,kK};
(3)forn=1 to Kdo
(4)forμkn=1 to Qkn do
(5)C:=C+1;
(6)   CalculateM^(C);
(7)ifM^(C)<M^(C-1) or C>C~max⁡(t)then
(8)μkn:=μkn-1, C:=C-1;
(9)    go to Step  14;
(10)end if
(11)end for
(12) SendC to the next CS;
(13)end for
(14)returnP by  (29), and μk∀k∈𝒦.


### 4.6. Distributed Dynamic AC and RA Algorithm

Based on the above three separate subproblems, we propose a distributed dynamic AC and RA algorithm as shown in Algorithm2. All system parameters should be initialized before the trip begins. At each slot, each CS solves three subproblems in steps 4, 5, and 6. At the end of each slot, the queue vector Θ(t+1) is updated according to (4), (7), and (9). This algorithm will be repeated when the train travels from the origin station to the destination station.Algorithm 2:Distributed dynamic AC and RA algorithm for (P2).
(1) InitializeV, Cmax⁡, Θ(0)=0;
(2)whilet∈[0,T]do
(3)fork=1 to Kdo
(4)  Obtainγk(t) by solving (20a) and (20b);
(5)  Obtain AC actionsrk(t) by solving (25);
(6)  Obtain RA actionsμk(t) by solving problem  (27a) – (27d);
(7)  UpdateΘ(t+1) according to (4), (7) and (9);
(8)end for
(9)end while.Remark 6 (utility-backlog tradeoff).
Based on [15], the achieved utility differs from optimality by 𝒪(1/V), in the sense that
(35)ϕ1*-lim⁡inf⁡t→∞∑k∈𝒦‍ϕk(r¯k)≤𝒪(1V),
where ϕ1* is the maximal utility for the problem (P1). It implies that the proposed algorithm can achieve a utility which is arbitrarily close to ϕ1* by increasing V. In addition, the actual queue backlog of each service grows linearly with V, which is given by
(36)lim⁡sup⁡t→∞Q¯k≤Dϵ+𝒪(V),
where ϵ>0 is a parameter and D is defined in (14). Therefore, the above expressions (35) and (36) present a utility-backlog tradeoff of [𝒪(1/V),𝒪(V)].
Recalling the utility functions (21) and (23), we observe that they have the maximum right derivatives νk>0 over the interval 0≤γk(t)≤Bk. Based on this observation, we obtain the boundedness property on the virtual queue Zk(t) in the following lemma.Lemma 7.
If the utility functionϕk(γk) has maximum right derivatives νk>0, then the backlog of virtual queue Zk(t) satisfies
(37)0≤Zk(t)≤Vνk+Bk,∀t∈[0,T],
provided that this inequality holds for Zk(0).Proof.
The proof of Lemma7 is provided in Appendix C.


## 4.1. Lyapunov Drift

DefineX(t) and Z(t) as a vector of all virtual queues Xk(t) and Zk(t) for k∈𝒦, respectively. We denote by Θ(t) the combined vector of all virtual queues and all actual queues; namely,
(10)Θ(t)≜[QT(t),XT(t),ZT(t)]T.
The quadratic Lyapunov function is defined as [15]
(11)L(Θ(t))≜12∑k∈𝒦‍(Qk(t)2+Xk(t)2+Zk(t)2).
Then the one-slot conditional Lyapunov drift Δ(Θ(t)) at slot t is given by
(12)Δ(Θ(t))=𝔼[L(Θ(t+1))-L(Θ(t))∣Θ(t)],
which admits the following lemma.Lemma 4.
Under any AC actions and RA actions at slott, and for any value of Θ(t), we have
(13)Δ(Θ(t))≤D+𝔼[G(t)∣Θ(t)],
where D is a finite constant defined by
(14)D≜12∑k∈𝒦‍[Pmax⁡2+Pav2+3Bk2+Cmax⁡2],
and G(t) is defined by
(15)G(t)≜∑k∈𝒦‍Qk(t)[rk(t)-μk(t)]+∑k∈𝒦‍Zk(t)(γk(t)-rk(t))+∑k∈𝒦‍Xk(t)[P(t)-Pav].Proof.
The proof of Lemma4 is provided in Appendix B.


## 4.2. The Drift-Plus-Penalty Expression

Instead of directly minimizing the upper bound𝔼[G(t)] by taking AC actions and RA actions, we desire to jointly stabilize all queues and maximize the sum of utility ∑k∈𝒦‍ϕk(γk(t)). The drift-plus-penalty theory in [6] approaches this by greedily minimizing the following “drift-plus-penalty” expression:
(16)𝔼[G(t)-V∑k∈𝒦‍ϕk(γk(t))],
where V≥0 is a parameter that represents the weight on how much we emphasize the sum utility maximization.We observe that the objective function in (16) is of separable structure, which motivates us to determine the auxiliary variables γk(t) and AC actions rk(t) as well as RA actions μk(t) in an alternative optimization fashion. The overall minimization problem (16) is decomposed into three separate subproblems. Specifically, isolating the γk(t) variables from (16) gives the followingutility maximization subproblem:
(17a)max⁡{γk(t)}∑k∈𝒦‍[Vϕk(γk(t))-Zk(t)γk(t)](17b)s.t.0≤γk(t)≤Bk,∀k∈𝒦,t∈[0,T].Similarly, isolating the AC actions rk(t) from (16) leads to the followingadmission control subproblem:
(18a)max⁡{rk(t)}∑k∈𝒦‍[(Zk(t)-Qk(t))rk(t)](18b)s.t.0≤rk(t)≤Ak(t),∀k∈𝒦,t∈[0,T].Also, isolating the RA actions μk(t) from (16) gives the followingresource allocation subproblem:
(19a)max⁡{μk(t)},P(t)∑k∈𝒦‍[Qk(t)μk(t)-Xk(t)P(t)](19b)s.t.0≤μk(t)≤Qk(t),μk(t)∈ℕ,∀k∈𝒦,t∈[0,T],(19c)∑k∈𝒦‍μk(t)≤C(t),t∈[0,T],(19d)P(t)≤Pmax⁡,t∈[0,T],where P(t) is related to μk(t) since a larger μk(t) requires more power consumption. These separate subproblems can be computed in a decentralized fashion, as stated below.


## 4.3. Utility Maximization

The utility maximization subproblem ((17a) and (17b)) can be decoupled into K separate maximization problems. Specifically, CSk keeps track of Zk(t) and determines the optimum γk(t) by solving the following problem:
(20a)max⁡γk(t)Vϕk(γk(t))-Zk(t)γk(t)(20b)s.t.0≤γk(t)≤Bk,t∈[0,T].Notice that the key point to solve (20a) and (20b) is the choice of the utility function, which is contingent on the purpose of the networking application or the prerogative of HSR network designer. For example, in order to represent the maximum desired delivery ratio for each service, the piecewise linear utility function can be considered for service k as follows:
(21)ϕk(γk)=νkmin⁡[γk,xkλk],
where νk>0 and xk>0 represent the priority and the maximum desired delivery ratio of service k, respectively. In general, 0≤xk≤1 and xkλk≤Bk for k∈𝒦. Thus the optimal solution to problem (20a) and (20b) is given by
(22)γk(t)={xkλk,ifZk(t)≤Vνk,0,otherwise.
Alternatively, the following strictly concave function can serve as the utility function for service k:
(23)ϕk(γk)=ln⁡(1+νkγk),
which can be regarded as an accurate approximation of the proportionally fair utility function if the same νk is selected with a large value for all k∈𝒦. In this case, the optimal solution to problem (20a) and (20b) can be obtained by
(24)γk(t)=[VZk(t)-1νk]0Bk,
where the operation [y]0a is equal to y if 0<y<a, 0 if y≤0, and a if y≥a.


## 4.4. Admission Control

The admission control subproblem ((18a) and (18b)) can be also decoupled into K separate maximization problems. Specifically, CSk chooses the AC action rk(t) by solving the following optimization problem:
(25)max⁡rk(t)(Zk(t)-Qk(t))rk(t)s.t.0≤rk(t)≤Ak(t),t∈[0,T].
It is immediate to see that the optimal solution depends on the queue backlog of Zk(t) and Qk(t), which is given by
(26)rk(t)={Ak(t),ifZk(t)≥Qk(t),0,otherwise.
We note that (26) is a simple threshold-based admission control strategy. On the one hand, when the queue backlog Qk(t) is not larger than the threshold Zk(t), then all the newly arriving packets are admitted into the buffer in CSk. Essentially, this not only reduces the value of Zk(t+1) so as to push γ¯k closer to r¯k, but also increases the average throughput r¯k so as to improve the utility. On the other hand, when the queue backlog Qk(t) is larger than the threshold Zk(t), then all the newly arriving packets will be dropped to ensure the network stability. Finally, we emphasize that the AC actions for all services are made in a distributed manner with only local queue backlog information and packet arrival information.


## 4.5. Resource Allocation

The resource allocation subproblem ((19a)–(19d)) at slot t can be explicitly expressed as(27a)max⁡{μk(t)},P(t)M(t)≜∑k∈𝒦‍[Qk(t)μk(t)-Xk(t)P(t)](27b)s.t.0≤μk(t)≤Qk(t),μk(t)∈ℕ,∀k∈𝒦,(27c)∑k∈𝒦‍μk(t)≤C(t)=⌊TsWlog⁡2(1+P(t)/N(t))L⌋,(27d)P(t)≤Pmax⁡. The problem (27a)–(27d) is a mixed-integer programming (MIP) problem, including a continuous variable P(t) and K integer variables μk(t), which cannot be solved efficiently [27]. The main difficulty of problem (27a)–(27d) comes from the integer nature of μk(t). However, we will show that problem (27a)–(27d) can be transformed into a single variable problem, which is easy to handle. In the sequel of this subsection, we will omit the time index for brevity.Firstly, as for constraint (27c), when the optimal RA actions are achieved, it can be shown that
(28)∑k‍μk=C=1ηlog⁡2(1+PN),
where η=L/TsW>0. Otherwise we can reduce the value of C and P such that the objective function can be further maximized without any violation of the constraints in (27b)–(27d). From (28), we have the following power consumption of C:
(29)P=N(2ηC-1),
and constraints (27b) and (27d) further imply that
(30)0≤C≤min⁡(∑k∈𝒦‍Qk,C~max⁡),
where C~max⁡≜(1/η)log⁡2(1+Pmax⁡/N).Secondly, the resource allocation subproblem (27a)–(27d) can be equivalently transformed into a single variable problem as follows:
(31a)max⁡C∈ℕM^(C)≜g1(C)-g2(C)(31b)s.t.(30),where g1(C) is given by(32a)g1(C)≜max⁡{μk}∑k∈𝒦‍Qkμk(32b)s.t.0≤μk≤Qk,μk∈ℕ,∀k∈𝒦,(32c)∑k∈𝒦‍μk=C,and g2(C) is given by
(33)g2(C)≜∑k=1K‍XkP=∑k=1K‍Xk(2ηC-1)N=ρ(2ηC-1),
with ρ≜N∑k=1K‍Xk.Now let us focus on the problem (32a)–(32c) with any given C. Clearly, the maximum objective value of (32a)–(32c) can always be achieved by allocating link capacity C to the services in the descending order of their backlogs, which is similar to the max-weight algorithm in [15]. Hence, we sort all the services in descending order of Qk and denote the ordered set by {k1,k2,…,kK}. For convenience, we define f(m)=∑n=0m‍Qkn(t) for m=0,1,…,K, where Qk0(t)=0. One can see that f(m) is an increasing function of m, and 0≤C≤f(K) from (30). Therefore the optimal solutions to the problem (32a)–(32c) are given by
(34)μkn={Qkn,if1≤n<m,C-f(n-1),ifn=m,0,ifm<n≤K,
where m∈{1,…,K} such that C∈(f(m-1),f(m)] if C>0; otherwise μkn=0 for all n.Next, let us focus on problem (31a)-(31b). Indeed, we have the following lemma.Lemma 5.
M
^
(
C
) is a unimodal function of C over [0,f(K)].Proof.
On the one hand, sinceΔg1(C)=g1(C+1)-g1(C)=Qkm for f(m-1)≤C(t)<f(m),∀m∈[1,K], Δg1(C) is a monotonically nonincreasing function of C. On the other hand, since Δg2(C)=ρ(2η-1)2ηC, Δg2(C) is a monotonically increasing function of C. Therefore ΔM^(C)=Δg1(C)-Δg2(C), which is a monotonically decreasing function of C. For any C∈[1,f(K)-1], ΔM^(C-1)>ΔM^(C), which implies M^(C)>(1/2)(M^(C-1)+M^(C+1)), so M^(C) is concave on [0,f(K)]. Based on [28], if M^(C) is concave, then M^(C) is unimodal.Based on Lemma5, since M^(C) is a unimodal function of C over [0,min⁡{C~max⁡,f(K)}], the golden section search method [29] can be used to obtain the global optimal solution to the problem (31a)-(31b). However, this method requires the knowledge of all queue backlog information. When the center controller is not available, a distributed resource allocation scheme is highly desirable. Relying on the insights from Lemma 5, we propose a distributed resource allocation scheme, where each CS can communicate with all other CSs, and the network resources are allocated packet by packet.The proposed packet loading resource allocation scheme is detailed in Algorithm1. For each slot, each CS exchanges the backlog information with all other CSs and the order of the backlogs is obtained by all CSs (step 2). Then the packets of the services are fetched from the corresponding CS in descending order of their backlogs. When one CS fetches a new packet (step 5), M^(C) is calculated (step 6). This will be repeated until the optimal condition in step 7 is satisfied, which implies that M^(C-1) is the maximum or constraint (30) is violated, and thus step 8 should be performed since the last packet cannot be transmitted. When one CS empties its buffer, it should send the value information of C to the next CS (step 12), and the next CS should continue the resource allocation. Here we remark that the optimal solutions can be achieved by the proposed scheme, which can be readily proved by Lemma 5.Algorithm 1:Packet loading resource allocation scheme for problem (27a) – (27d).
(1) Initializeμk=0 for k∈𝒦; M^(0)=0; C=0;
(2)  Sort services in descending ofQk and obtain the ordered set {k1,k2,…,kK};
(3)forn=1 to Kdo
(4)forμkn=1 to Qkn do
(5)C:=C+1;
(6)   CalculateM^(C);
(7)ifM^(C)<M^(C-1) or C>C~max⁡(t)then
(8)μkn:=μkn-1, C:=C-1;
(9)    go to Step  14;
(10)end if
(11)end for
(12) SendC to the next CS;
(13)end for
(14)returnP by  (29), and μk∀k∈𝒦.


## 4.6. Distributed Dynamic AC and RA Algorithm

Based on the above three separate subproblems, we propose a distributed dynamic AC and RA algorithm as shown in Algorithm2. All system parameters should be initialized before the trip begins. At each slot, each CS solves three subproblems in steps 4, 5, and 6. At the end of each slot, the queue vector Θ(t+1) is updated according to (4), (7), and (9). This algorithm will be repeated when the train travels from the origin station to the destination station.Algorithm 2:Distributed dynamic AC and RA algorithm for (P2).
(1) InitializeV, Cmax⁡, Θ(0)=0;
(2)whilet∈[0,T]do
(3)fork=1 to Kdo
(4)  Obtainγk(t) by solving (20a) and (20b);
(5)  Obtain AC actionsrk(t) by solving (25);
(6)  Obtain RA actionsμk(t) by solving problem  (27a) – (27d);
(7)  UpdateΘ(t+1) according to (4), (7) and (9);
(8)end for
(9)end while.Remark 6 (utility-backlog tradeoff).
Based on [15], the achieved utility differs from optimality by 𝒪(1/V), in the sense that
(35)ϕ1*-lim⁡inf⁡t→∞∑k∈𝒦‍ϕk(r¯k)≤𝒪(1V),
where ϕ1* is the maximal utility for the problem (P1). It implies that the proposed algorithm can achieve a utility which is arbitrarily close to ϕ1* by increasing V. In addition, the actual queue backlog of each service grows linearly with V, which is given by
(36)lim⁡sup⁡t→∞Q¯k≤Dϵ+𝒪(V),
where ϵ>0 is a parameter and D is defined in (14). Therefore, the above expressions (35) and (36) present a utility-backlog tradeoff of [𝒪(1/V),𝒪(V)].
Recalling the utility functions (21) and (23), we observe that they have the maximum right derivatives νk>0 over the interval 0≤γk(t)≤Bk. Based on this observation, we obtain the boundedness property on the virtual queue Zk(t) in the following lemma.Lemma 7.
If the utility functionϕk(γk) has maximum right derivatives νk>0, then the backlog of virtual queue Zk(t) satisfies
(37)0≤Zk(t)≤Vνk+Bk,∀t∈[0,T],
provided that this inequality holds for Zk(0).Proof.
The proof of Lemma7 is provided in Appendix C.


## 5. Numerical Results and Discussions

In this section, we implement the proposed distributed dynamic AC and RA algorithm using MATLAB and present simulation results to illustrate the performance of it. We use the piecewise linear utility functions (21) for all services and summarize the simulation parameters in Table 1. The packet size L is set to 240 bits according to [12, 30], and the slot duration Ts is set to 1 ms according to [31]. A single simulation runs the proposed algorithm when the train moves through a cell (30,000 slots).Table 1
Parameters in simulation.
Parameter
Description
Value
P
av
Average power constraint
35 W
B
System bandwidth
5 MHz
L
Packet size
240 bits
T
s
Slot duration
1 ms
α
Pathloss exponent
4
P
max
⁡
Maximum transmit power
45 W
v
Constant moving speed
100 m/s
R
Cell radius
1.5 km
d
0
Distance between BS and rail
50 m
K
Number of services
6Figures2 and 3 explore the throughput-backlog tradeoff with different V. In the simulations, we use the same parameters λk=25 and xk=1 and different priorities for all services. As shown in Figure 2, the average throughput for each service increases as V is increased and the service with high priority gets the large average throughput. Figure 3 presents that the average queue backlogs of all services are linearly increasing with V, which demonstrates the 𝒪(V) behavior in (36). Furthermore, the proposed algorithm can ensure that the average queue backlogs of the services with different priorities are almost the same.Figure 2
Average throughput with differentV.Figure 3
Average queue backlog with differentV.Figure4 illustrates the achieved delivery ratios for the services with different maximum desired delivery ratios and same arrival rate λk=25 as well as priority νk=10. It can be observed that the large V will result in the improvement of the delivery ratio performance. This can be explained as follows: since a larger V gives a higher priority on throughput, more packets will be admitted into the buffers, which causes the higher delivery ratio performance. In addition, the delivery ratio for each service is close to its maximum desired delivery ratio when V is larger than 40, which implies that the proposed algorithm can archive different maximum desired delivery ratios when a large V is chosen.Figure 4
Delivery ratio with differentV.Figure5 compares the average power consumption under different arrival rate conditions. In this simulation, we set the same parameters νk=10, xk=1, and λk=λ for all services. From this figure, we can see that the average power consumption increases as V is increased. This is exactly what happens. A larger V results in more packets admitted into buffers, while transmitting these packets will cost more power. As for the same V, a larger λ will cause more power consumption, since more packets will be admitted into buffers based on (26). In addition, the average power consumption can satisfy the average power constraint when the arrival rate is λk=25, which is reasonably set in the previous simulations.Figure 5
Power consumption with differentV.Figure6 describes the backlog update processes of virtual queues Zk(t) for three types of services. In the simulation, we set the same parameters νk=10, xk=1, and λk=35 for all services and V=100. From the figure, we can see 0≤Zk(t)≤Vνk+Bk for all services at all slots, which illustrates the boundedness property on queue backlogs in Lemma 7.Figure 6
The backlog update processes of virtual queuesZk(t).


## 6. Conclusion

In this paper, we formulate the joint admission control and resource allocation problem under average power constraint for multimedia services delivery in HSR wireless networks. With the help of virtual queues, the original stochastic optimization problem is transformed into a queue stability problem, which is decomposed into three separate subproblems by the drift-plus-penalty approach. It is worth noting that the optimal solution to the resource allocation subproblem can be obtained by the packet loading resource allocation scheme. Based on the stochastic optimization technique, the dynamic admission control and resource allocation algorithm is proposed, which is suitable for distributed implementation in HSR wireless networks. Furthermore, the performance of the proposed algorithm is analyzed theoretically and validated by numerical simulations under realistic conditions for HSR wireless networks. For future work, we will further investigate the effects of the nonmentioned parts in the communication system, such as frame error check blocks and adaptive channel equalizers.



---

*Source: 781654-2014-04-06.xml*