# Cross-Layer Resource Allocation for Multihop V2X Communications

Authors: Yanhua He; Liangrui Tang; Yun Ren; Jonathan Rodriguez; Shahid Mumtaz
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

Inspired by the increasingly mature vehicle-to-everything (V2X) communication technology, we propose a multihop V2X downlink transmission system to improve users’ quality of experience (QoE) in hot spots. Specifically, we develop a cross-layer resource allocation algorithm to optimize the long-term system performance while guaranteeing the stability of data queues. Lyapunov optimization is employed to transform the long-term optimization problem into a series of instantaneous subproblems, which involves the joint optimization of rate control, power allocation, and mobile relay selection at each time slot. On one hand, the optimization of rate control is decoupled and carried out independently. On the other hand, a low-complexity pricing-based stable matching algorithm is proposed to solve the joint power allocation and mobile relay selection problem. Finally, simulation results demonstrate that the proposed algorithm can achieve superior performance and simultaneously guarantee queue stability.


---

## Body

## 1. Introduction

With the explosive growth of mobile Internet and the rapid expansion of massive data traffic services, mobile communication systems put forward higher requirements for network capacity, especially in hot spots with high user density. In this case, users’ quality of experience (QoE) will drop sharply due to the limited network resources and the possibility of blocking and packet loss. Consequently, the reliability of wireless communication system cannot be guaranteed [1, 2].To address this challenge, many researchers have proposed deploying more microcells, picocells, or relays, expecting to increase the capacity and coverage of the network [3]. However, these methods introduce new problems, such as large energy consumption, high deployment and maintenance cost, and so on [4–6]. Therefore, wireless communication systems urgently thirst for a solution which has flexible application range, low deployment cost, and simple network maintenance.On the other hand, the development of vehicular networks becomes more and more mature [7, 8]. Vehicle to everything (V2X), which includes vehicle-to-vehicle (V2V), vehicle-to-pedestrian (V2P), vehicle-to-infrastructure (V2I), and vehicle-to-network (V2N) communications, plays an important role in improving road safety, traffic efficiency, and service reliability [9]. Moreover, the integration of vehicular networks and cellular networks, i.e., cellular V2X (C-V2X), provides better performance guarantee under high load conditions. In other words, V2X technology also makes it possible to use vehicles as mobile relays to augment network connectivity, expand network capacity, and improve users’ QoE and quality of service (QoS) [10–12].However, establishing this V2X-based multihop relay system faces the following major challenges. First, how to control the stability of data queues considering the dynamic data arrival and departure remains an open issue. It involves not only the optimization of rate control at the network layer but also the optimization of power allocation and relay selection in the physical layer. Therefore, the traditional resource allocation of physical layer scheme will no longer be applicable, and a cross-layer resource optimization scheme is needed. Second, the joint optimization of rate control, power allocation, and relay selection is formulated as a mixed integer nonlinear optimization problem, since both binary and continuous optimization variables are involved. How to solve this nonlinear optimization problem effectively is another challenge. Last but not least, conventional resource allocation schemes mainly focus on short-term optimization and ignore long-term system performance and constraints. At each round of optimization, the resources are allocated in a greedy way without considering the future, which results in long-term performance degradation. However, it is infeasible to derive the optimal long-term optimization solution due to the absence of the future knowledge. Therefore, how to achieve low-complexity online resource allocation with guaranteed performance requires further study.To tackle these challenges, we propose a multihop V2X communication system to improve the network capacity and realize the long-term reliable transmission for users densely distributed in hot spots. It mainly involves the rate control in the network layer, as well as the mobile relay selection and power allocation in the physical layer. The objective is to optimize the long-term users’ QoE performance under the constraints of long-term power consumption and queue stability.The main contributions of this paper are summarized as follows:(i)
A multihop downlink communication system based on V2X is established. In this system, vehicles as mobile relays play the roles of transmitting traffic from BS to users. In such system, vehicles are not only extensions of base station (BS) transmission distance, but also methods for BS to expand coverage and improve system throughput.(ii)
A cross-layer long-term optimization is established for the multihop V2X communication system. Such long-term optimization cannot be resolved by existing approaches. Motivated by this, the recently-developed Lyapunov optimization approach is leveraged. With its assistance, the long-term optimization problem is transformed into a gradual optimization problem. First, the long-term optimization is formulated to obtain the optimal long-term QoE under the constraints of long-term power consumption and delay. Second, the constraints of long-term power consumption and delay are transformed into virtual queues stability problem. Finally, the long-term performance optimization is decomposed into a series of online subproblems involving trading off queue backlog and utility.(iii)
An online algorithm based on Lyapunov optimization is proposed. The above mentioned online subproblem is divided into the rate control problem in network layer and the resource allocation problem in physical layer. Faced with this, the rate control problem is solved by the convex optimization easily. However, the physical layer resource allocation problem, as a mixed integer nonlinear optimization problem, is difficult to be solved. Further, we prove that the resource allocation problem is a convex problem, given the mobile relay selection results. In the sense, the price-based matching is proposed to deal with the mobile relay selection problem. This online algorithm only needs to know the current channel and queue information, without foreknowledge of global information. These works successfully reduce the signalling overheads and computational complexity and conform to the time causality.The rest of this paper is organized as follows. The related work is introduced in Section2. The system model and problem formulation are described in Sections 3 and 4. In Section 5, Lyapunov optimization approach is applied to converting the original long-term optimization problem into a series of rate control and power allocation problems to be optimized in each timeslot, and the matching is introduced to solve the mobile relay selection problem. Simulation results and the associated discussions are presented in Section 6, and the conclusions of this paper are drawn in Section 7.


## 2. Related Work

The concept of V2X communication which helps to support variety of traffic-efficient applications has drawn great attention in both industrial and academic fields recently [10, 13, 14]. In [10], Ashraf et al. developed a novel QoS-aware resource allocation scheme for V2V communication. A joint resource block (RB) allocation and power control algorithm was proposed in [13] for radio resource management of device-to-device (D2D) based V2V communications. The authors in [14] proposed an energy sensing-based spectrum sharing mechanism which can reduce the transmission collisions between cellular V2X and vehicular ad hoc network (VANET) users by allowing cellular V2X users to use unlicensed channels fairly. These works mainly regard vehicles as terminal users but have not taken into account the network capacity expansion by adopting vehicles as mobile relays.Several works have focused on the service queue stability to improve users’ QoE [15–18]. In [15], a cluster-based heterogeneous vehicular networks (C-HetVNETs) framework with dynamic data arrival was developed, and the performance metrics including delay, throughput, and queue length are analyzed based on a Markov queuing model. Two queue-aware power allocation schemes in V2V networks were proposed in [16], which characterized the statistics of extreme events according to the maximal queue length by extreme value theory. The authors in [17] presented a joint power allocation and subcarrier scheme in the downlink of an OFDMA system, in which the rate constraints were defined in order to guarantee queue stability. In [18], queue theory was used to analyze the performance of arrival and the service curve to guarantee queue stability, and the proposed traffic flow model was verified by a M/M/c model. The control of queue stability in these works generally assumed that the complete state information is known, while it is optimistic to get perfect information in advance. On the other hand, the traditional methods of processing queues own a higher computational complexity in practical implementations.Resource allocation problems in V2X communication have been studied in [19–22]. A joint optimization of the radio resource and power allocation algorithm was proposed in [19] to maximize the service rate of cellular user equipment (UE). In [20, 21], a two-stage resource allocation algorithm based on auction matching and nonlinear fractional programming was presented in vehicular heterogeneous networks. An uplink radio resource allocation scheme for V2V communication in freeway scenario was proposed in [22], which aimed to maximize the sum rate of V2V links, while the transmission requirements of vehicular UEs were neglected. These resource allocation schemes for V2X communications mainly focus on short-term designs, i.e., implementing optimization in a single time slot while ignoring the practical long-term constraints.


## 3. System Model

Figure1(a) shows the proposed V2X communication systems. We consider a downlink data transmission in a dense network with one BS and K users. Moreover, we assume the users are heterogeneous, so that users’ traffic could be classified as K types. There also are N vehicles. For users, these vehicles play the roles of mobile relays using the amplify and forward (AF) protocol. To proceed, assume these vehicles running at a constant speed and in the same direction. Further, the users’ set is presented by K=1,2,⋯k,⋯,K, and the vehicles’ set is presented by N=1,2,⋯,n,⋯,N.Figure 1
System model. (a) V2X communications system. (b) Queue diagram of the system.
(a) (b)The system operates in a time-slotted manner with timeslot indext∈0,1,2,⋯. At timeslot t, Rkt bits traffic data arrive at BS for user k. So define the Qkt as the amount of data buffered at queue k for user k at timeslot t. The queue model is shown in the Figure 1(b). In this system, the buffer size is enough and packet loss incidents will not happen. To proceed, let Ckt denote the amount of traffic data that could be delivered to user k. In fact, Ckt could be seen as transmission capacity of the V2X system for the k-th user. Then, the dynamics queue corresponding to the k-th queue can be characterized as(1)Qkt+1=maxQkt-Ckt,0+RktIt is worth noting thatRkt and Ckt are indicators that belong to different layers. Rkt is the traffic from Internet, buffered at BS and transmitted to user k. Correspondingly, one of the network layer functions is to control the traffic from the source node to the destination node. So Rkt corresponds to network layer. In addition, Ckt completes the functions of the physical layer, implementing transparent transmission of the bit stream.As we know, the higher data rate brings more enjoyable experience to users. However, marginal utility theory sets forth a viewpoint: When other inputs remain unchanged, increasing a certain input continuously will result in a gradual decrease in the new income. On this basis, we define QoEUkt to describe the satisfaction of user k, which is shown as [23](2)Ukt=χklog21+Rktχk represents the degree of preference of BS to the k-th type service. The larger χk is, the more data user k will receive. The logarithmic function describes that the marginal increment of QoE declines gradually with Rkt, but the QoE is increasing continuously.To improve the transmission capacity of the downlink, AF protocol is applied to vehicles with single antenna, which are called mobile relays in this paper.As illustrated in Figure2, the AF collaboration system is composed of a single source node, i.e., BS, single relay node, i.e., the n-th mobile relay, and a single destination node, i.e., the k-th user. The mobile relay just acts as a helper for BS and does not have any own information to send. In this paper, the frequency band of BS is orthogonally assigned to the K queues.Figure 2
AF collaboration system model.The mobile relay is assumed to be operated in half-duplex mode; i.e., it cannot transmit and receive simultaneously. The transmission from BS and the relay node are done over orthogonal channels in time domain [24]. In the first half of the timeslot, BS broadcasts its signal to the destination and the mobile relay. The received signal-to-noise ratios (SNR) are(3)SNRkAFt=∑n=1Nwk,ntPktN0hk,nt2(4)SNRk,uDLt=PktN0hk,ut2Then, according to AF protocol, the mobile relay node forwards the source signal to user over the remaining time. The received SNR after amplifying is expressed as follows:(5)SNRuAFt=∑n=1Nwk,ntPntN0hn,ut2Here, SNRkAFt is the received SNR of mobile relay for user k. SNRk,uDLt is the received SNR of user k by the direct link from BS. SNRuAFt is the received SNR of user k from the amplified signal by mobile relay.N 0 is the Gaussian white noise, Pkt is the transmit power allocated by BS to transfer data of queue k belonged to user k at the timeslot t, and Pnt is the transmit power of mobile relay n. hk,nt, hk,ut, and hn,ut are the fading coefficients of BS to mobile relay n, BS to users and mobile relay n to users on Rayleigh channel links obeying the complex Gaussian distribution. hk,nt, hk,ut, and hn,ut are i.i.d. over time and remain unchanged at each timeslot but change from slot to slot. wk,nt∈0,1, if queue k accesses the mobile relay n, wk,nt=1; otherwise, wk,nt=0.When users receive signals with maximum ratio combining (MRC) [25, 26], the available maximum average transmission capacity for the k-th user is(6)Ckt=F2log21+SNRk,uDLt+fSNRkAFt,SNRuAFtwhere fx,y=xy/1+x+y and F is the bandwidth allocated to queue k.To be simple, this paper just considers the power allocation of BS to the queues, and the transmission power of relay is fixed. The queues’ transmission power is constrained by two practical limitations. One is inspired with the energy saving of BS, which is to limit the long-term averaged power consumption and it is set as(7)0≤limT→∞1T∑t=1TE∑k=1K∑n=1Nwk,ntPk,nt≤PavePave is the long-term maximum average power consumption. The other one is a regular instantaneous limit, which is set as(8)0≤∑n=1Nwk,ntPk,nt≤Pmax∀k,t


## 4. Problem Formulation

The aim of this paper is to maximize the long-term QoE of this system, which is shown as(9)maxRt,Pt,wtlimT→∞1T∑t=1T∑k=1KUkts.t.C1:limT→∞EQktT=0∀kC2:0≤∑n=1Nwk,ntPk,nt≤Pmax∀k,tC3:limT→∞1T∑t=1TE∑k=1K∑n=1Nwk,ntPk,nt≤PaveC4:θkt≤Dkt∀k,tC5:wk,nt∈0,1∀k,n,tC6:∑n=1Nwk,nt=1∀k,tC7:∑k=1Kwk,nt=1∀n,tC8:0≤∑k=1KRkt≤Rmax∀k,twhere Rt=R1t,R2t,⋯RKt, Pt=P1t,P2t,⋯PKt, and wt is the mobile relay selection matrix. The constraint C1 guarantees that Qkt is mean rate stable, which indicates the queue will be stable at a finite value finally. C2 and C3 are the constraints of power. θk(t) is the queuing delay defined as the time that a packet waits in a queue until it can be transmitted to the users. Moreover, Dk(t) defines the upper bound of the queuing delay. C6 and C7 suggest that each queue only accesses one relay and each relay only services one queue. C8 constrains the data amount of queue k admitted within the system at timeslot t.Due to the queuing model (1) and the long-term average power constraint (6), rate control (RC) and mobile relay selection and power allocation (RSPA) are tangled together across layers. In the sense, (9) is difficult to be solved. To address the challenges, Lyapunov optimization technique is developed [27, 28]. Lyapunov optimization technique deals with such problems without prior information and has low computational complexity.


## 5. Online Algorithm Based on Lyapunov Optimization

Lyapunov optimization is efficient in designing stable control algorithms. It has been extended to treat network stability and performance optimization simultaneously. In this section, the online algorithm based on Lyapunov optimization toward (9) is evolved.


### 5.1. Lyapunov Optimization

The long-term power constraintC3 could be transferred to a virtual queue stability problem. The power-constrained virtual queue is formulated as Et with E0=0, and the update equation is(10)Et+1=maxEt-Pave,0+Ytwhere Yt=∑k=1K∑n=1Nwk,ntPk,nt is the power consumption of BS at timeslot t. If Et tends to mean rate stable, the long-term average power constraint will be satisfied [29].Similarly, the delay-constrained virtual queueZkt is defined as(11)Zkt+1=max⁡Zkt-CktDkt,0+QktPhysically speaking, (11) indicates that if traffic of queue k cannot all be transmitted within the upper bound of the delay, and then the rest of the traffic will be backlogged to be transmitted in the next time slot.Subsequently, letGt=Qt,Et,Zt be a concatenated vector, where Qt=Q1t,Q2t,⋯,Qkt and Zt=Z1t,Z2t,⋯,Zkt. The Lyapunov function is LGt:(12)LGt=12∑k=1KQk2t+12E2t+12∑k=1KZk2tThen the Lyapunov drift is denoted as(13)ΔGt=ELGt+1-LGt∣GtWe can obtain the drift minus utility function as(14)ΔGt-VE∑k=1KUkt∣Gtwhere V is a tuneable weight, which controls the tradeoff between the drift ΔGt and the utility E∑k=1KUkt∣Gt. The drift minus utility function is further bounded in the following way:(15)ΔGt-VE∑k=1KUkt∣Gt≤12∑k=1KECk2t+12∑k=1KERk2t+∑k=1KQktERkt-Ckt∣Gt+12EPave2t+12EY2t+EtEYt-Pave∣Gt+12∑k=1KEQk2t+12∑k=1KECk2tDk2t+∑k=1KZktEQkt-CktDkt∣Gt-VE∑k=1KUkt∣GtLet(16)B≥Bt=12∑k=1KECk2t+12∑k=1KERk2t+12EPave2t+12EY2t+12∑k=1KEQk2t+12∑k=1KECk2tDk2tAnd there is an upper bound B for Bt. It is easy to find that(17)ΔGt-VE∑k=1KUkt∣Gt≤B+∑k=1KQktERkt-Ckt∣Gt+EtEYt-PaveGt+∑k=1KZktEQkt-CktDkt∣Gt-VE∑k=1KUkt∣GtAccording to the design principle of Lyapunov optimization, (9) is rearranged as(18)minRt,Pt,wt∑k=1KQktRkt-Ckt+Et∑k=1KPkt-Pave+∑k=1KZktQkt-CktDkt-V∑k=1KUkts.t.C2,C5,C6,C7,C8QueueQkt,Zkt,∀k,andEtaremeanratestable.


### 5.2. Online Algorithm Design

Shown as (18), the long-term optimization (9) is transferred to a series of single slot optimization problems. Further, (18) could be decomposed into two subproblems, due to none coupling constraints at single slot. One is the RC subproblem in the network layer. The other one is the RSPA subproblem in the physical layer.The RC subproblem is illustrated as(19)RCminRt∑k=1KQktRkt-VUkts.t.C8Because Ukt is a concave function of Rkt. The RC subproblem is a convex optimization problem. This problem is easy to be solved using the Lagrangian multiplier method. Observing the objective of RC subproblem, it is found that RC results are affected by factors such as Qkt, V, and χk.In addition, the RSPA subproblem is shown as(20)minPt,wt∑k=1KZktQkt-CktDkt-∑k=1KQktCkt+Et∑k=1KPkt-Paves.t.C2,C5,C6,C7Consider that the definition of Zkt indicates the demand to transmit traffic data in time; otherwise, the traffic data will be backlogged, note that Qk(t)-CktDkt should be limited by maxQk(t)-CktDkt,0. So (20) can be regulated as(21)RSPAminJ=∑k=1KZktmaxQkt-CktDkt,0-∑k=1KQktCkt+Et∑k=1KPkt-Paves.t.C2,C5,C6,C7Lemma 1.
∂ J / ∂ P k t is a function that is only limited by Pkt. The second-order partial derivative ∂2J/∂Pkt∂Pit is 0 (when k≠i) or positive real value (when k=i).Lemma 2.
The Hessian matrix ofJ for Pt=P1t,P2t,⋯PKt is a diagonal matrix and its eigenvalues are all positive.Lemmas1 and 2 are proved in Appendix A.Theorem 3.
Given the relay selection results, the Hessian matrix ofJ for Pt=P1t,P2t,⋯PKt is a positive definite matrix, and RSPA is a convex function for Pt=P1t,P2t,⋯PKt.Proof.
Theorem3 is proved with Lemmas 1 and 2. Further, it is inferred that RSPA is a convex optimization problem, when the mobile relay selection results are given.


### 5.3. Matching-Based Mobile Relay Selection

RSPA is a mixed integer nonlinear programming problem. And its constraintsC6 and C7 guarantee that there is one-to-one correspondence among queues and mobile relays. Theorem 3 proves that, given the mobile relay selection results, the power allocation problem is a convex problem. Thus the price-based matching algorithm is proposed to get the mobile relay selection results [30].The matching problem can be described as a tripleK,N,Ft. Queue K for different users is one of the matching participants. The other one participant is mobile relays N. Ft is the matching preference matrix.Matching at timeslott is defined by the following: For the mobile relay selection problem K,N,Ft based on matching, the matching Ψ is a one-to-one correspondence from set K∪N onto itself under preference matrix Ft; i.e., ΨK∈N,∀k∈K. Ψk=n represents that queue k is matched with the mobile relay n, that equals wk,nt=1.In order to minimize the RSPA problem, we can define that the preference as(22)Fk,nΨk=n=QktCkt-EtPkt-ZktmaxQkt-CktDkt,0-Θntwhere Θnt is the price for selecting the mobile relay n, which is used to resolve the conflict of the matching process.Obtaining the preference matrixFt: First, queue of user k is paired with every channel. Second, obtain Fkt by selecting the maximum value using (22). Third, Ft is obtained by repeating the first and second steps.Then the price-based matching algorithm is introduced as Algorithm1.Algorithm 1:Price-Based Matching Algorithm.
(1) Initialization: CalculateFkt for each queue. InitializeΨ as an empty set. The set of mobile relays which receive more than one matching proposal from queues is defined asΩt, Ωt=⌀ at the beginning. For any mobile relayn∈N, setting Θnt=0 (2) Repeating: If∃Ψk=⌀, preform the rule of matching k with the mobile relay who has the maximum preference according to Equation (22). Each queuek∈K proposes to its most preferred vehicle in its preference list Fkt. If any mobile relayn∈N receives only one proposal from a queue, then n will be directly matched with the mobile relay which sends the initial proposal. Otherwise, addn in to set Ωt. IfΩt≠⌀, perform the price rising rule for mobile relays which received more than one matching proposal. Each mobile relayn∈Ωt increase its price by adding ΔΘn. Every queue which has proposed ton updates its preference towards n and remews its proposal. Remove the vehicles which receive only proposal fromΩt. End  Every queue has been matched with a mobile relay.The comprehensive theoretical analyses of matching on convergence, stability, optimality, and complexity have been proved in [31]. According to the three facts: (1) RC being a convex problem; (2) matching which could complete the mobile relay selection problem; (3) Theorem 3, (9) could be solved by Algorithm 2.Algorithm 2:Online Algorithm Based on Lyapunov Optimization.
(1) Input:  K, N, T, V, Pave (2) Output:  R∗t, P∗t, w∗t (3) Initialization:  t=0, Qk0=1, Zk0=0, E0=0, T=200 (4) While  t<T do (5) RC: (6)Obtain the optimal solution R∗t by solving RC (7) RSPA: (8)Update the channel state due to the mobility of vehicles (9)Use  matching  to generate the result of mobile relay selection w∗t (10)Given w∗t, obtain the optimal solutions set P∗t (11) Update the queue by Q k t + 1 = m a x Q k t - C k t , 0 + R k ∗ t, E t + 1 = m a x E t - P a v e , 0 + Y ∗ t, Z k t + 1 = m a x Z k t - C k t D k t , 0 + Q k ( t ) (12) t=t+1 (13) end whileIn Algorithm2, R∗t and P∗t are the optimal RC and power allocation solutions at timeslot t. Y∗t is the sum of the energy consumption of BS.


### 5.4. Performance Analysis

The aim of this work is to solve the long-term optimization (9). With the assist of Lyapunov optimization approach, this problem is converted into the online single timeslot optimization problem. If the single timeslot optimization is solved optimally at each timeslot, the optimal solution to the original problem can then be achieved asymptotically, following an OV,O1/V tradeoff between the queue backlogs and the achieved utility, which is given in Theorem 4.Theorem 4.
Bounds of the optimal utility and the average congestion satisfy(23)limT→∞1T∑t=1TE∑k=1KUkt≥U∗-BVlimT→∞1T∑t=1TE∑k=1KQkt≤B+VUmax-U∗εTheorem 4 has been proved in Appendix B. OV shows the size of queue backlog. O1/V shows the gap between the acquired utility and the possible maximum value. When V is large enough, the utility could be considered as the maximum utility, with the worst queue backlog.Actually, Algorithm2 based on the V2X communication system is easy to be operated in practice, with low complexity. We can assume that a large number of users walking in the commercial street produce massive traffic demands. However, the restricted power could not support all users’ requirements, reducing the QoE. Then the vehicles with communication modules on the roadside can give the help.Algorithm2 will be started for the service request from K users to BS. At the first step, there are downlink traffic arrivals, and then the BS network layer starts the traffic control function. The RC subproblem will be solved by standard convex optimization effectively.At the second step, BS will select the optimal mobile relay according to the current channel information which could be obtained through the help of mobile relays. In the process of price-based matching, the complexity for each queue to acquire the preferences of all the vehicles and the complexity for sorting the obtained preferences areON and ONlog⁡N. Assume that the conflicting elements are matched within ξ iterations. The mobile relay selection is solved with matching whose complexity is OξNlog⁡N.At the third step, under the mobile relay selection results, BS will allocate the limited power to users according to RSPA. Theorem3 tells that the power allocation is a convex optimization, so the power allocation is also able to be solved with standard convex optimization. Last, BS will update the current information via (1), (10), and (11) for the next timeslot. And the traffic will be transmitted to users by the multihop links.Moreover, we can find the system will be stabilized after several timeslots, which will be illustrated in the simulation results. And the V2X communication system could support higher performance to users.


## 5.1. Lyapunov Optimization

The long-term power constraintC3 could be transferred to a virtual queue stability problem. The power-constrained virtual queue is formulated as Et with E0=0, and the update equation is(10)Et+1=maxEt-Pave,0+Ytwhere Yt=∑k=1K∑n=1Nwk,ntPk,nt is the power consumption of BS at timeslot t. If Et tends to mean rate stable, the long-term average power constraint will be satisfied [29].Similarly, the delay-constrained virtual queueZkt is defined as(11)Zkt+1=max⁡Zkt-CktDkt,0+QktPhysically speaking, (11) indicates that if traffic of queue k cannot all be transmitted within the upper bound of the delay, and then the rest of the traffic will be backlogged to be transmitted in the next time slot.Subsequently, letGt=Qt,Et,Zt be a concatenated vector, where Qt=Q1t,Q2t,⋯,Qkt and Zt=Z1t,Z2t,⋯,Zkt. The Lyapunov function is LGt:(12)LGt=12∑k=1KQk2t+12E2t+12∑k=1KZk2tThen the Lyapunov drift is denoted as(13)ΔGt=ELGt+1-LGt∣GtWe can obtain the drift minus utility function as(14)ΔGt-VE∑k=1KUkt∣Gtwhere V is a tuneable weight, which controls the tradeoff between the drift ΔGt and the utility E∑k=1KUkt∣Gt. The drift minus utility function is further bounded in the following way:(15)ΔGt-VE∑k=1KUkt∣Gt≤12∑k=1KECk2t+12∑k=1KERk2t+∑k=1KQktERkt-Ckt∣Gt+12EPave2t+12EY2t+EtEYt-Pave∣Gt+12∑k=1KEQk2t+12∑k=1KECk2tDk2t+∑k=1KZktEQkt-CktDkt∣Gt-VE∑k=1KUkt∣GtLet(16)B≥Bt=12∑k=1KECk2t+12∑k=1KERk2t+12EPave2t+12EY2t+12∑k=1KEQk2t+12∑k=1KECk2tDk2tAnd there is an upper bound B for Bt. It is easy to find that(17)ΔGt-VE∑k=1KUkt∣Gt≤B+∑k=1KQktERkt-Ckt∣Gt+EtEYt-PaveGt+∑k=1KZktEQkt-CktDkt∣Gt-VE∑k=1KUkt∣GtAccording to the design principle of Lyapunov optimization, (9) is rearranged as(18)minRt,Pt,wt∑k=1KQktRkt-Ckt+Et∑k=1KPkt-Pave+∑k=1KZktQkt-CktDkt-V∑k=1KUkts.t.C2,C5,C6,C7,C8QueueQkt,Zkt,∀k,andEtaremeanratestable.


## 5.2. Online Algorithm Design

Shown as (18), the long-term optimization (9) is transferred to a series of single slot optimization problems. Further, (18) could be decomposed into two subproblems, due to none coupling constraints at single slot. One is the RC subproblem in the network layer. The other one is the RSPA subproblem in the physical layer.The RC subproblem is illustrated as(19)RCminRt∑k=1KQktRkt-VUkts.t.C8Because Ukt is a concave function of Rkt. The RC subproblem is a convex optimization problem. This problem is easy to be solved using the Lagrangian multiplier method. Observing the objective of RC subproblem, it is found that RC results are affected by factors such as Qkt, V, and χk.In addition, the RSPA subproblem is shown as(20)minPt,wt∑k=1KZktQkt-CktDkt-∑k=1KQktCkt+Et∑k=1KPkt-Paves.t.C2,C5,C6,C7Consider that the definition of Zkt indicates the demand to transmit traffic data in time; otherwise, the traffic data will be backlogged, note that Qk(t)-CktDkt should be limited by maxQk(t)-CktDkt,0. So (20) can be regulated as(21)RSPAminJ=∑k=1KZktmaxQkt-CktDkt,0-∑k=1KQktCkt+Et∑k=1KPkt-Paves.t.C2,C5,C6,C7Lemma 1.
∂ J / ∂ P k t is a function that is only limited by Pkt. The second-order partial derivative ∂2J/∂Pkt∂Pit is 0 (when k≠i) or positive real value (when k=i).Lemma 2.
The Hessian matrix ofJ for Pt=P1t,P2t,⋯PKt is a diagonal matrix and its eigenvalues are all positive.Lemmas1 and 2 are proved in Appendix A.Theorem 3.
Given the relay selection results, the Hessian matrix ofJ for Pt=P1t,P2t,⋯PKt is a positive definite matrix, and RSPA is a convex function for Pt=P1t,P2t,⋯PKt.Proof.
Theorem3 is proved with Lemmas 1 and 2. Further, it is inferred that RSPA is a convex optimization problem, when the mobile relay selection results are given.


## 5.3. Matching-Based Mobile Relay Selection

RSPA is a mixed integer nonlinear programming problem. And its constraintsC6 and C7 guarantee that there is one-to-one correspondence among queues and mobile relays. Theorem 3 proves that, given the mobile relay selection results, the power allocation problem is a convex problem. Thus the price-based matching algorithm is proposed to get the mobile relay selection results [30].The matching problem can be described as a tripleK,N,Ft. Queue K for different users is one of the matching participants. The other one participant is mobile relays N. Ft is the matching preference matrix.Matching at timeslott is defined by the following: For the mobile relay selection problem K,N,Ft based on matching, the matching Ψ is a one-to-one correspondence from set K∪N onto itself under preference matrix Ft; i.e., ΨK∈N,∀k∈K. Ψk=n represents that queue k is matched with the mobile relay n, that equals wk,nt=1.In order to minimize the RSPA problem, we can define that the preference as(22)Fk,nΨk=n=QktCkt-EtPkt-ZktmaxQkt-CktDkt,0-Θntwhere Θnt is the price for selecting the mobile relay n, which is used to resolve the conflict of the matching process.Obtaining the preference matrixFt: First, queue of user k is paired with every channel. Second, obtain Fkt by selecting the maximum value using (22). Third, Ft is obtained by repeating the first and second steps.Then the price-based matching algorithm is introduced as Algorithm1.Algorithm 1:Price-Based Matching Algorithm.
(1) Initialization: CalculateFkt for each queue. InitializeΨ as an empty set. The set of mobile relays which receive more than one matching proposal from queues is defined asΩt, Ωt=⌀ at the beginning. For any mobile relayn∈N, setting Θnt=0 (2) Repeating: If∃Ψk=⌀, preform the rule of matching k with the mobile relay who has the maximum preference according to Equation (22). Each queuek∈K proposes to its most preferred vehicle in its preference list Fkt. If any mobile relayn∈N receives only one proposal from a queue, then n will be directly matched with the mobile relay which sends the initial proposal. Otherwise, addn in to set Ωt. IfΩt≠⌀, perform the price rising rule for mobile relays which received more than one matching proposal. Each mobile relayn∈Ωt increase its price by adding ΔΘn. Every queue which has proposed ton updates its preference towards n and remews its proposal. Remove the vehicles which receive only proposal fromΩt. End  Every queue has been matched with a mobile relay.The comprehensive theoretical analyses of matching on convergence, stability, optimality, and complexity have been proved in [31]. According to the three facts: (1) RC being a convex problem; (2) matching which could complete the mobile relay selection problem; (3) Theorem 3, (9) could be solved by Algorithm 2.Algorithm 2:Online Algorithm Based on Lyapunov Optimization.
(1) Input:  K, N, T, V, Pave (2) Output:  R∗t, P∗t, w∗t (3) Initialization:  t=0, Qk0=1, Zk0=0, E0=0, T=200 (4) While  t<T do (5) RC: (6)Obtain the optimal solution R∗t by solving RC (7) RSPA: (8)Update the channel state due to the mobility of vehicles (9)Use  matching  to generate the result of mobile relay selection w∗t (10)Given w∗t, obtain the optimal solutions set P∗t (11) Update the queue by Q k t + 1 = m a x Q k t - C k t , 0 + R k ∗ t, E t + 1 = m a x E t - P a v e , 0 + Y ∗ t, Z k t + 1 = m a x Z k t - C k t D k t , 0 + Q k ( t ) (12) t=t+1 (13) end whileIn Algorithm2, R∗t and P∗t are the optimal RC and power allocation solutions at timeslot t. Y∗t is the sum of the energy consumption of BS.


## 5.4. Performance Analysis

The aim of this work is to solve the long-term optimization (9). With the assist of Lyapunov optimization approach, this problem is converted into the online single timeslot optimization problem. If the single timeslot optimization is solved optimally at each timeslot, the optimal solution to the original problem can then be achieved asymptotically, following an OV,O1/V tradeoff between the queue backlogs and the achieved utility, which is given in Theorem 4.Theorem 4.
Bounds of the optimal utility and the average congestion satisfy(23)limT→∞1T∑t=1TE∑k=1KUkt≥U∗-BVlimT→∞1T∑t=1TE∑k=1KQkt≤B+VUmax-U∗εTheorem 4 has been proved in Appendix B. OV shows the size of queue backlog. O1/V shows the gap between the acquired utility and the possible maximum value. When V is large enough, the utility could be considered as the maximum utility, with the worst queue backlog.Actually, Algorithm2 based on the V2X communication system is easy to be operated in practice, with low complexity. We can assume that a large number of users walking in the commercial street produce massive traffic demands. However, the restricted power could not support all users’ requirements, reducing the QoE. Then the vehicles with communication modules on the roadside can give the help.Algorithm2 will be started for the service request from K users to BS. At the first step, there are downlink traffic arrivals, and then the BS network layer starts the traffic control function. The RC subproblem will be solved by standard convex optimization effectively.At the second step, BS will select the optimal mobile relay according to the current channel information which could be obtained through the help of mobile relays. In the process of price-based matching, the complexity for each queue to acquire the preferences of all the vehicles and the complexity for sorting the obtained preferences areON and ONlog⁡N. Assume that the conflicting elements are matched within ξ iterations. The mobile relay selection is solved with matching whose complexity is OξNlog⁡N.At the third step, under the mobile relay selection results, BS will allocate the limited power to users according to RSPA. Theorem3 tells that the power allocation is a convex optimization, so the power allocation is also able to be solved with standard convex optimization. Last, BS will update the current information via (1), (10), and (11) for the next timeslot. And the traffic will be transmitted to users by the multihop links.Moreover, we can find the system will be stabilized after several timeslots, which will be illustrated in the simulation results. And the V2X communication system could support higher performance to users.


## 6. Simulation Results and Discussions

In this section, simulation results are presented. The stability and tradeoff between utility and queue backlog are analyzed. What is more, we compare long-term performance of two communication system, including the V2X multihop communication system in this paper and the traditional direct link communication system. For convenience, the work of long-term optimization with AF (LTAF) under V2X multihop communication system is called LTAF, and similarly the work of long-term optimization with direct link (LTDL) is called LTDL. The simulation parameters have been illustrated in Table1.Table 1
Simulation parameters.
Parameters Value Q 0 1,1 , 1,1 Mbits D ( t ) 250,500,800,1000ms Z 0 0,0 , 0,0 E 0 0 watts P m a x 2.5 watts P a v e 8 watts R m a x 50 Mbps K = N 4 Δ Θ n 0.1


### 6.1. Stability

As expected, the queuesQkt, Zkt, and Et tend to stabilize over time, which are shown in Figures 3, 4, and 5. As a result, the system’s utility finally remains stable so as the arrival rate and transmission capacity do, which are shown in Figures 6, 7, and 8. Moreover, Figure 9(a) reflects changes of actual delay. Figure 9(b) tells the fact that the average actual delay is lower than the demand, and its variance is small in the allowable range.Figure 3
Queue backlogs versus time.Figure 4
Delay-constrained virtual queues versus time.Figure 5
Power-constrained virtual queue versus time and the box plot ofE.Figure 6
Utility versus time.Figure 7
Arrival rate versus time.Figure 8
Transmission capacities versus time.Figure 9
Actual delay. (a) Actual delay versus time. (b) The bound and average actual delay of different queues. The error bars represent the variance of measurements for 200 timeslots.
(a) (b)At the same time, the stability of queues reveals three issues:(i)
The robustness of queue congestion is guaranteed. In other words, the queue backlog is limited in a controllable range. So the system will not crash due to heavy traffic owing to the rate control of BS.(ii)
The latency requirements of users are satisfied. Moreover, the actual delay is always lower than the upper bound of delay, shown as Figure9.(iii)
The limited power resource is used effectively, and the long-term power constraint is accomplished. If we assumePave as the energy income at each timeslot, Yt as an expenditure at timeslot t, the fluctuations could be explained by the following: if the income exceeds the expenditure, it will be stored for the next timeslot; otherwise, it will borrow energy from other timeslots with the result of generating debt accumulation. Actually, Et represents the debt accumulation of power consumption. After long-term observation, it can be found that Et fluctuates around a fixed value Pave, and the mean power consumption almost equals Pave which can be proved by the box plot of Figure 5.We can find thatQkt and Zkt will equal Rkt finally, as time goes. According to Lyapunov optimization, when Qkt is stable, Ckt≥Rkt is established. That means traffic will be entirely delivered to users at each timeslot. So, Rkt is recorded as the queue backlog for Qkt+1, according to (1). Similarly, for Zkt, when the system stabilizes, Qkt is recorded as the queue backlog for Zkt+1.In addition, we can findCkt is far higher than Rkt, for Queue 1, Queue 2, and Queue 3. That could be deduced by the stability conditions of delay-constrained virtual queue. The stability of Zkt requires CktDkt≥Qkt, where Dkt is a constant less than 1 second.


### 6.2. Tradeoff

Firstly, we will explain the baseline. Baseline is the results of individually optimizing the utility and transmission capacity, respectively. LTAF is the result of our algorithm. Figure10 is the plots of utility versus Vand queue backlog versus V.Figure 10
The tradeoff between utility and queue backlog versusV.For LTAF, we can observe that the utility is in inverse proportion toV, and the queue backlog is proportional to V. These results respond to Theorem 4. More importantly, the utility gap between LTAF and baseline decreases, as V becomes larger. In fact, baseline stands for the optimal value of utility and queue backlog. Further, Figure 10 shows that the results acquired by LTAF is infinitely close to the optimal utility, with the increase of V. However, the queue backlog is almost equal to 50 Mbps, the worst queue backlog. These phenomena highlight tradeoff relationship between utility and queue backlog.


### 6.3. Comparison

In this part, the main work is to compare the performance of queue backlogQ, delay-constrained virtual queue Z, and power-constrained virtual queue E of LTAF and LTDL.Figure11 illustrates the queue backlog Q of LTDL and error bar comparisons of LTAF and LTDL on Q. Comparing Figure 11 with Figure 3, though Q of LTDL finally becomes stable, bad points often occur. These bad points bring the larger fluctuation to LTDL, so its variance is larger than LTAF, which is shown in Figure 11.Figure 11
Queue backlog of LTDL versus time and error bar for comparison. The error bars represent the variance of measurements for 200 timeslots.In Figure12, there are the plot of delay-constrained virtual queue Z versus time for LTDL and error bar comparisons of LTAF and LTDL on Z. In Figure 12, the delay-constrained virtual queue backlog of Queue 1 is unstable. That means the delay constraint for user 1 could not be met. The delay requirements of the other three queues are satisfied, but there are also many bad points. As a result, variance on Z of LTDL is larger than LTAF.Figure 12
Delay-constrained virtual queue backlog of LTDL versus time and error bar for comparison. The error bars represent the variance of measurements for 200 timeslots.In Figures11 and 12, these bad points and exceeded allowable fluctuations present the possibility that users’ instant constraints are not guaranteed. That means LTDL communication system possesses worse instantaneous performance.Figure13 is the plot of power-constrained virtual queue E versus time for LTDL and error bar comparisons of LTAF and LTDL on E. Comparing with Figure 5, the queue E of LTDL climbs quickly firstly and then began to increase gently. That indicates that BS always consumes the available maximum power at each timeslot. Conversely, the power consumption of BS under LTAF is enough due to the assist of vehicles. From the perspective of power consumption, LTDL brings more pressure on the operators to maintain BSs. Because BSs are more susceptible to damage for working at the maximum power.Figure 13
Power-constrained virtual queue backlog of LTDL versus time and error bar for comparison. The error bars represent the variance of measurements for 200 timeslots.


## 6.1. Stability

As expected, the queuesQkt, Zkt, and Et tend to stabilize over time, which are shown in Figures 3, 4, and 5. As a result, the system’s utility finally remains stable so as the arrival rate and transmission capacity do, which are shown in Figures 6, 7, and 8. Moreover, Figure 9(a) reflects changes of actual delay. Figure 9(b) tells the fact that the average actual delay is lower than the demand, and its variance is small in the allowable range.Figure 3
Queue backlogs versus time.Figure 4
Delay-constrained virtual queues versus time.Figure 5
Power-constrained virtual queue versus time and the box plot ofE.Figure 6
Utility versus time.Figure 7
Arrival rate versus time.Figure 8
Transmission capacities versus time.Figure 9
Actual delay. (a) Actual delay versus time. (b) The bound and average actual delay of different queues. The error bars represent the variance of measurements for 200 timeslots.
(a) (b)At the same time, the stability of queues reveals three issues:(i)
The robustness of queue congestion is guaranteed. In other words, the queue backlog is limited in a controllable range. So the system will not crash due to heavy traffic owing to the rate control of BS.(ii)
The latency requirements of users are satisfied. Moreover, the actual delay is always lower than the upper bound of delay, shown as Figure9.(iii)
The limited power resource is used effectively, and the long-term power constraint is accomplished. If we assumePave as the energy income at each timeslot, Yt as an expenditure at timeslot t, the fluctuations could be explained by the following: if the income exceeds the expenditure, it will be stored for the next timeslot; otherwise, it will borrow energy from other timeslots with the result of generating debt accumulation. Actually, Et represents the debt accumulation of power consumption. After long-term observation, it can be found that Et fluctuates around a fixed value Pave, and the mean power consumption almost equals Pave which can be proved by the box plot of Figure 5.We can find thatQkt and Zkt will equal Rkt finally, as time goes. According to Lyapunov optimization, when Qkt is stable, Ckt≥Rkt is established. That means traffic will be entirely delivered to users at each timeslot. So, Rkt is recorded as the queue backlog for Qkt+1, according to (1). Similarly, for Zkt, when the system stabilizes, Qkt is recorded as the queue backlog for Zkt+1.In addition, we can findCkt is far higher than Rkt, for Queue 1, Queue 2, and Queue 3. That could be deduced by the stability conditions of delay-constrained virtual queue. The stability of Zkt requires CktDkt≥Qkt, where Dkt is a constant less than 1 second.


## 6.2. Tradeoff

Firstly, we will explain the baseline. Baseline is the results of individually optimizing the utility and transmission capacity, respectively. LTAF is the result of our algorithm. Figure10 is the plots of utility versus Vand queue backlog versus V.Figure 10
The tradeoff between utility and queue backlog versusV.For LTAF, we can observe that the utility is in inverse proportion toV, and the queue backlog is proportional to V. These results respond to Theorem 4. More importantly, the utility gap between LTAF and baseline decreases, as V becomes larger. In fact, baseline stands for the optimal value of utility and queue backlog. Further, Figure 10 shows that the results acquired by LTAF is infinitely close to the optimal utility, with the increase of V. However, the queue backlog is almost equal to 50 Mbps, the worst queue backlog. These phenomena highlight tradeoff relationship between utility and queue backlog.


## 6.3. Comparison

In this part, the main work is to compare the performance of queue backlogQ, delay-constrained virtual queue Z, and power-constrained virtual queue E of LTAF and LTDL.Figure11 illustrates the queue backlog Q of LTDL and error bar comparisons of LTAF and LTDL on Q. Comparing Figure 11 with Figure 3, though Q of LTDL finally becomes stable, bad points often occur. These bad points bring the larger fluctuation to LTDL, so its variance is larger than LTAF, which is shown in Figure 11.Figure 11
Queue backlog of LTDL versus time and error bar for comparison. The error bars represent the variance of measurements for 200 timeslots.In Figure12, there are the plot of delay-constrained virtual queue Z versus time for LTDL and error bar comparisons of LTAF and LTDL on Z. In Figure 12, the delay-constrained virtual queue backlog of Queue 1 is unstable. That means the delay constraint for user 1 could not be met. The delay requirements of the other three queues are satisfied, but there are also many bad points. As a result, variance on Z of LTDL is larger than LTAF.Figure 12
Delay-constrained virtual queue backlog of LTDL versus time and error bar for comparison. The error bars represent the variance of measurements for 200 timeslots.In Figures11 and 12, these bad points and exceeded allowable fluctuations present the possibility that users’ instant constraints are not guaranteed. That means LTDL communication system possesses worse instantaneous performance.Figure13 is the plot of power-constrained virtual queue E versus time for LTDL and error bar comparisons of LTAF and LTDL on E. Comparing with Figure 5, the queue E of LTDL climbs quickly firstly and then began to increase gently. That indicates that BS always consumes the available maximum power at each timeslot. Conversely, the power consumption of BS under LTAF is enough due to the assist of vehicles. From the perspective of power consumption, LTDL brings more pressure on the operators to maintain BSs. Because BSs are more susceptible to damage for working at the maximum power.Figure 13
Power-constrained virtual queue backlog of LTDL versus time and error bar for comparison. The error bars represent the variance of measurements for 200 timeslots.


## 7. Conclusions

In this paper, a cross-layer resource allocation schemes for V2X communication system was investigated. First, the downlink transmission for BS with the help of vehicles as mobile relays was proposed. These mobile relays play roles in extending the coverage distance of the BS and increasing the capacity. Second, to establish the cross-layer resource allocation problem, the queue model was applied to couple the arrival rate in the network layer with the transmission capacity in the physical layer. Third, Lyapunov optimization was proposed to transfer the long-term optimization problem to series of rate control and mobile relay selection-power allocation problems at each timeslot. And the tradeoff between queue backlog and utility was evaluated. Fourth, expecting low computational complexity, the mobile relay selection was optimized with matching. Then simulation results verified that LTAF could reach the stability as expected; LTAF could obtain the optimal utility with the worst queue backlog; and LTAF not only could reduce the burden on BSs but also could satisfy the diversity requirements of user business; i.e., LTAF could accomplish the latency demands of different queues at each time slot but the LTDL could not.In future work, we will focus on rental-based relay selection problem for V2X communication system. In this paper, the vehicle is a free boost for BS. In fact, the vehicle, as a private property, is difficult to open for users freely.



---

*Source: 5864657-2019-02-12.xml*