# Cross-Layer QoS Scheme Based on Priority Differentiation in Multihop Wireless Networks

Authors: Mingjiu Wang; Shu Fan
Journal: Journal of Electrical and Computer Engineering
 (2017)

---

## Abstract

To support different QoS requirements of diverse types of services, a cross-layer QoS scheme providing different QoS guarantees is designed. This scheme sets values of service priorities according to services’ data arrival rates and required end-to-end delay to endow different services with diverse scheduling priorities. To support QoS requirements better and maintain fairness, this scheme introduces delay and throughput weight coefficients. The methods of calculating the coefficients are also proposed. Through decomposing the optimization problem that uses weighted network utility as its optimization objective using Lyapunov optimization technique, this scheme can simultaneously support different QoS requirements of various services. The throughput utility optimality of the scheme is also proved. To reduce the computational complexity of the scheme, a distributed media access control scheme is proposed. A power control algorithm for this cross-layer scheme is also designed, and this algorithm transforms the power control into the solution of a multivariate equation. The simulation results evaluated with Matlab show that, compared with the existing works, the algorithm presented in this paper can simultaneously satisfy the delay demands of different services with maintaining high throughput.


---

## Body

## 1. Introduction

With various multimedia applications that have diverse QoS requirements appearing in multihop wireless networks [1], how to satisfy different QoS demands of diverse services has become a hotspot research issue. Considering the sharing of wireless channels among nodes and the diversity of QoS requirements of different services, the way of assigning transmission priorities to applications according to their QoS demands is an effective method to utilize wireless resources and provide QoS guarantees. Some algorithms following this line of thinking have been proposed. EDCA of IEEE 802.11e [2] standard defines four access categories corresponding to voice, video, best effort, and background to endow different applications with diverse priorities in media access control. Reference [3] adopts the 802.11e Access Control (AC) queue structure. Control packets used to route are prioritized according to the type of traffic associated with them to ensure that high priority packets are not penalized by the control packets. In [4], delay time of transmitting data is chosen as QoS metric. Packets in queues of flows with higher QoS level are delivered with higher priority. To support efficient video transmission, the scheduling algorithm in [5] assigns priority depending on the types of video frame. This video-based scheduling algorithm is combined with 802.11e protocol. Designed for video transport, the policy of [6] calculates the values of the counters depending on the delay estimation and the importance of packets. Under this policy, the packets with the lowest value of the counters gain the transmission opportunity. However, as there is no corresponding routing and flow control scheme combined with the above priority-based scheduling algorithms, congestion of high priority data packets may occur. Service-differentiation routing algorithms [7, 8] that select routes with different approaches depending on the type of traffic to ensure that packets with higher priority will be transmitted on higher quality links are also proposed. However, these algorithms may cause unbalanced distribution of packets in the network.Different from the above layered QoS schemes, the Backpressure policy [9] is designed by applying Lyapunov optimization technique joint routes and schedules. The policy can also be combined with flow control [10] to ensure that the admitted rate injected into the network layer lies within the network capacity region, as well as combined with MAC [11], TCP [12], and application layers [13]. Due to its throughput-optimal characteristic for different network structures, the backpressure cross-layer control scheme has been a promising scheme to provide QoS guarantees. There are still few researches of Backpressure policies designed to support different QoS requirements of different types of traffic [14, 15]. In [14], services are divided into different classes according to their QoS demands. QoS requirements are supported through solving the optimization problem with the objective of maximizing weighted utility of different classes and constraints of QoS demands of each class. However, under the condition of high traffic loads, the fairness of the policy will decline. Reference [15] proposes a Backpressure cross-layer algorithm which ensures that the delays of flows are proportional to the priorities of services with keeping optimal throughput utility. However, the work of [15] did not consider the situation that services have different arrival data rates.In this paper, we consider both arrival data rate and QoS demands when setting priorities. The effect of priorities of services on services’ QoS performance is also studied. We propose a cross-layer QoS scheme which can provide QoS guarantees for different types of services simultaneously. The key contributions of this paper can be summarized as follows.(i)
The paper proposes a Lyapunov optimization technique-based cross-layer scheme which can satisfy different QoS requirements of various applications with priority differentiation. The method of how to calculate services’ priorities is also designed.(ii)
The paper introduces throughput weight coefficient and delay weight coefficient that are updated according to QoS performance to meet QoS demands better and maintain fairness.(iii)
To reduce the computational complexity, a distributed media access control scheme is proposed. A power control algorithm to keep the data transmission rates of all wireless links being equal is also designed. This power control algorithm treats the power control as the solution of a multivariate equation.(iv)
The performance in terms of utility optimality is demonstrated with rigorous theoretical analyses. The policy is shown that it can achieve a time average throughput utility which can be arbitrarily close to the optimal value.The structure of the rest of the paper is as follows. Section2 introduces the system model and problem formulation. In Section 3, the algorithm is designed using Lyapunov optimization. The performance analyses of the proposed algorithm are present in Section 4. Simulation results are given in Section 5. Conclusions are provided in Section 6.


## 2. Model and Problem Formulation

### 2.1. Network Model

Consider a multihop wireless network consisting of several nodes. Let the network be modeled by a directed connectivity graphG(N,L), where N is the set of nodes and (i,j)∈L represents a unidirectional wireless link between node i and nodej.M denotes the set of unicast sessions m between source-destination pairs in the network.K denotes the set of services k in each session. Ns is the set of source nodes sm(k) of service k in sessionm. Nd is the set of destination nodes dm(k) of service k in session m. Packets generated in the source nodes traverse multiple wireless hops before arriving at the destination nodes. The system is assumed to run in a time-slotted fashion. There are two channels including common control channel and data channel which use different communication frequencies in the network. Each node can broadcast control packets consisting of channel access negotiation information, lengths of queues, and weight values of nodes on the common control channel. Each node can gain control information by monitoring the control channel. The data channel is used for data communication. In this model scheduling will be subjected to the following constraints [16]:(1)∑j:n,j∈Lαnjt+∑i:i,n∈Lαint≤1.αnj(t)∈{0,1} is used to indicate whether link (n,j) is used to transmit packets in time slott.αnj(t)=1 if Pnj(t)>0, and αnj(t)=0 if Pnj(t)<0. Pnj(t) denotes the transmit power from node n to node j in time slot t. Constraint (1) means that each node can either transmit or receive data on data channel at the same time. The SINR (Signal to Interference plus Noise Ratio) of link (x,y) at node y in time slot t is calculated as follows:(2)SINRxyt=GxyPxyt∑z≠x,z≠yGzyPzht+ny.Node x is the sending node, and node y is the destination node of packets from node x. Node z denotes the neighbor nodes of node x. When node z sends packets, node h is the destination node of packets from nodez. Gxy denotes the transmit loss from node x to nodey. ny is the receiver noise at node y. The achievable capacity of link (x,y) in time slot t is calculated as follows: (3)Cxyt=B·log21+SINRxyt.B represents the bandwidth of the data channel. There are two necessary constraints for the successful data transmission on link (x,y) to be satisfied. The first constraint can be expressed as(4)SINRxyt=GxyPxyt∑z≠x,z≠yGzyPzht+ny≥SINRth.This constraint states that the SINR of link (x,y) at node y must be above the predefined SINR threshold SINRth.However, if the new link(x,y) is built, the transmission power from node x to y may result in additional interference at the receiving node q of existing link (p,q), and the SINR of link (p,q) at node q will decrease. To make sure that the new transmission will not impair the existing transmissions and the SINR of each existing link keeps being above the predefined SINR threshold SINRth, the second constraint is expressed as(5)SINRpqt=GpqPpqt∑z≠p,z≠qGzqPzht+nq+ΔIxqt=GpqPpqt∑z≠p,z≠qGzqPzht+nq+GxqPxyt≥SINRth.ΔIxq(t) denotes the additional interference at node q caused by the data transmission from node x to y in time slot t. According to constraints (4) and (5), the maximum and minimum transmit power of node x to node y in time slot t can be written as(6)Pxymint=∑z≠x,z≠yGzyPzht+ny·SINRthGxy,Pxymaxt=GpqPpqt/SINRth-∑z≠p,z≠qGzqPzht-nqGxq.


### 2.2. Virtual Queue at the Transport Layer

A
m
(
k
)
(
t
)
∈
[
0
,
A
m
a
x
(
m
)
(
k
)
] denotes the arrival rate of service k in session m injected into the transport layer from the application layer at source node. Amax(m)(k) is the maximum arrival rate of sessionm. rm(k)(t)∈[0,Am(k)(t)] is the admitted rate of session m injected into the network layer. ηm(k)(t)∈[0,Amax(m)(k)] is an auxiliary variable called the virtual input rate. There is a virtual queue for every service k in session m at the service’s source node. The virtual queue at the transport layer of source node sm(k) is denoted by Ym(k) that is updated as follows:(7)Ymkt+1=max⁡Ymkt-rmkt,0+ηmkt.If each virtual queue Ym(k) is guaranteed to be stable, according to the necessity and sufficiency for queue stability [17], it is apparent that ηm(k)¯≤rm(k)¯, where the time average value of time-varying variable x(t) is denoted by x¯=limt→∞⁡1/t∑τ=0t-1E(x(τ)). Therefore, the lower bound of rm(k)¯ can be derived from ηm(k)¯ which is calculable.


### 2.3. Data Queue at the Network Layer

The data backlog queue for servicek in session m at the network layer of node n is denoted by Qn(m)(k)(t). In each slot t, the queue is updated as(8)Qnmkt+1=max⁡Qnmkt-∑i∈Onμnimkt,0+∑j∈Inμjnmkt+1n=smkrmkt,where O(n) represents the set of nodes with (n,i)∈L. I(n) represents the set of nodes with (j,n)∈L. μij(m)(k)(t) is the amount of data of service k in session m to be forwarded from nodes i to j in time slot t. 1{n=sm(k)} is an indicator function that denotes 1 if n=sm(k) and denotes 0 otherwise. In addition, ∑m∈M∑k∈Kμij(m)(k)(t) must not be greater than the transmission capacity of link (i,j) in time slot t.


### 2.4. Design of Priorities of Services

β
k represents the priority of service k, which is used to denote the importance degree of service k in scheduling. βk is calculated using the method as follows:(9)βk=Ak/DkthAbasic/Dbasicth.Ak is the average data arrival rate of service k. Dkth represents the maximum allowable end-to-end delay bound of servicek. Abasic denotes the basic average data arrival rate. Dbasicth is the basic allowable end-to-end delay. Abasic and Dbasicth can be calculated as(10)Abasic=mink∈KAk,Dbasicth=maxk∈KDkth.


### 2.5. Design of Throughput and Delay Weight Coefficients

σ
k
D represents delay weight coefficient of service k. In every T0 interval, the destination nodes of the same service calculate the average end-to-end delay of their corresponding service and the delay weight coefficient. As an example of servicek, in destination nodes of servicek, σkD is calculated as(11)σkD=expDk-DkthifDk>Dkth1ifDk≤Dkth.Here, Dk is the average end-to-end delay of service k in interval T0. Similarly, the throughput weight coefficient of servicek, σkT is calculated as follows:(12)σkT=expThk-ThkthifThk<Thkth1ifThk≥Thkth.Thk represents the average throughput of service k in interval T0. Thkth denotes the required average throughput of servicek.Through introducing throughput and delay weight coefficients into the optimization objective, the QoS performances of services are considered in the optimization. According to the calculation methods above, we can find that if the QoS performances of a service including average end-to-end delay and average throughput in the interval do not reach the threshold values, the delay and throughput weight coefficients will increase sharply. Meanwhile, the transmitted probability of the packets of this service will increase, which helps to support QoS requirements better.


### 2.6. Throughput Utility Optimization Problem

Similar to the design of utility function in [18], let the utility function of service k in sessionm, Um(k)(·), be a concave, differentiable, and nondecreasing utility function with Um(k)(0)=0. The throughput utility maximization problemP1 can be defined as follows:(13)maximize∑m∈M∑k∈KσkDσkTUmkηmk¯subject  tor¯∈Λ,0≤r¯≤λ,η¯≤r¯,∑j:n,j∈Lαnjt+∑i:i,n∈Lαint≤1,Pxymint≤Pxyt≤Pxymaxt,∀x,y∈N.Similar to the definition in Section 2.2, x¯ is the time average value of time-varying variable x(t), and x¯ is calculated according to x¯=limt→∞⁡1/t∑τ=0t-1E(x(τ)). Here, r¯=(rm(k)¯), η¯=(ηm(k)¯), λm(k)=E{Am(k)(t)}, and λ=(λm(k)). Λ is the capacity region of the network. The constraint r¯∈Λ is used to guarantee the stability of the network.


## 2.1. Network Model

Consider a multihop wireless network consisting of several nodes. Let the network be modeled by a directed connectivity graphG(N,L), where N is the set of nodes and (i,j)∈L represents a unidirectional wireless link between node i and nodej.M denotes the set of unicast sessions m between source-destination pairs in the network.K denotes the set of services k in each session. Ns is the set of source nodes sm(k) of service k in sessionm. Nd is the set of destination nodes dm(k) of service k in session m. Packets generated in the source nodes traverse multiple wireless hops before arriving at the destination nodes. The system is assumed to run in a time-slotted fashion. There are two channels including common control channel and data channel which use different communication frequencies in the network. Each node can broadcast control packets consisting of channel access negotiation information, lengths of queues, and weight values of nodes on the common control channel. Each node can gain control information by monitoring the control channel. The data channel is used for data communication. In this model scheduling will be subjected to the following constraints [16]:(1)∑j:n,j∈Lαnjt+∑i:i,n∈Lαint≤1.αnj(t)∈{0,1} is used to indicate whether link (n,j) is used to transmit packets in time slott.αnj(t)=1 if Pnj(t)>0, and αnj(t)=0 if Pnj(t)<0. Pnj(t) denotes the transmit power from node n to node j in time slot t. Constraint (1) means that each node can either transmit or receive data on data channel at the same time. The SINR (Signal to Interference plus Noise Ratio) of link (x,y) at node y in time slot t is calculated as follows:(2)SINRxyt=GxyPxyt∑z≠x,z≠yGzyPzht+ny.Node x is the sending node, and node y is the destination node of packets from node x. Node z denotes the neighbor nodes of node x. When node z sends packets, node h is the destination node of packets from nodez. Gxy denotes the transmit loss from node x to nodey. ny is the receiver noise at node y. The achievable capacity of link (x,y) in time slot t is calculated as follows: (3)Cxyt=B·log21+SINRxyt.B represents the bandwidth of the data channel. There are two necessary constraints for the successful data transmission on link (x,y) to be satisfied. The first constraint can be expressed as(4)SINRxyt=GxyPxyt∑z≠x,z≠yGzyPzht+ny≥SINRth.This constraint states that the SINR of link (x,y) at node y must be above the predefined SINR threshold SINRth.However, if the new link(x,y) is built, the transmission power from node x to y may result in additional interference at the receiving node q of existing link (p,q), and the SINR of link (p,q) at node q will decrease. To make sure that the new transmission will not impair the existing transmissions and the SINR of each existing link keeps being above the predefined SINR threshold SINRth, the second constraint is expressed as(5)SINRpqt=GpqPpqt∑z≠p,z≠qGzqPzht+nq+ΔIxqt=GpqPpqt∑z≠p,z≠qGzqPzht+nq+GxqPxyt≥SINRth.ΔIxq(t) denotes the additional interference at node q caused by the data transmission from node x to y in time slot t. According to constraints (4) and (5), the maximum and minimum transmit power of node x to node y in time slot t can be written as(6)Pxymint=∑z≠x,z≠yGzyPzht+ny·SINRthGxy,Pxymaxt=GpqPpqt/SINRth-∑z≠p,z≠qGzqPzht-nqGxq.


## 2.2. Virtual Queue at the Transport Layer

A
m
(
k
)
(
t
)
∈
[
0
,
A
m
a
x
(
m
)
(
k
)
] denotes the arrival rate of service k in session m injected into the transport layer from the application layer at source node. Amax(m)(k) is the maximum arrival rate of sessionm. rm(k)(t)∈[0,Am(k)(t)] is the admitted rate of session m injected into the network layer. ηm(k)(t)∈[0,Amax(m)(k)] is an auxiliary variable called the virtual input rate. There is a virtual queue for every service k in session m at the service’s source node. The virtual queue at the transport layer of source node sm(k) is denoted by Ym(k) that is updated as follows:(7)Ymkt+1=max⁡Ymkt-rmkt,0+ηmkt.If each virtual queue Ym(k) is guaranteed to be stable, according to the necessity and sufficiency for queue stability [17], it is apparent that ηm(k)¯≤rm(k)¯, where the time average value of time-varying variable x(t) is denoted by x¯=limt→∞⁡1/t∑τ=0t-1E(x(τ)). Therefore, the lower bound of rm(k)¯ can be derived from ηm(k)¯ which is calculable.


## 2.3. Data Queue at the Network Layer

The data backlog queue for servicek in session m at the network layer of node n is denoted by Qn(m)(k)(t). In each slot t, the queue is updated as(8)Qnmkt+1=max⁡Qnmkt-∑i∈Onμnimkt,0+∑j∈Inμjnmkt+1n=smkrmkt,where O(n) represents the set of nodes with (n,i)∈L. I(n) represents the set of nodes with (j,n)∈L. μij(m)(k)(t) is the amount of data of service k in session m to be forwarded from nodes i to j in time slot t. 1{n=sm(k)} is an indicator function that denotes 1 if n=sm(k) and denotes 0 otherwise. In addition, ∑m∈M∑k∈Kμij(m)(k)(t) must not be greater than the transmission capacity of link (i,j) in time slot t.


## 2.4. Design of Priorities of Services

β
k represents the priority of service k, which is used to denote the importance degree of service k in scheduling. βk is calculated using the method as follows:(9)βk=Ak/DkthAbasic/Dbasicth.Ak is the average data arrival rate of service k. Dkth represents the maximum allowable end-to-end delay bound of servicek. Abasic denotes the basic average data arrival rate. Dbasicth is the basic allowable end-to-end delay. Abasic and Dbasicth can be calculated as(10)Abasic=mink∈KAk,Dbasicth=maxk∈KDkth.


## 2.5. Design of Throughput and Delay Weight Coefficients

σ
k
D represents delay weight coefficient of service k. In every T0 interval, the destination nodes of the same service calculate the average end-to-end delay of their corresponding service and the delay weight coefficient. As an example of servicek, in destination nodes of servicek, σkD is calculated as(11)σkD=expDk-DkthifDk>Dkth1ifDk≤Dkth.Here, Dk is the average end-to-end delay of service k in interval T0. Similarly, the throughput weight coefficient of servicek, σkT is calculated as follows:(12)σkT=expThk-ThkthifThk<Thkth1ifThk≥Thkth.Thk represents the average throughput of service k in interval T0. Thkth denotes the required average throughput of servicek.Through introducing throughput and delay weight coefficients into the optimization objective, the QoS performances of services are considered in the optimization. According to the calculation methods above, we can find that if the QoS performances of a service including average end-to-end delay and average throughput in the interval do not reach the threshold values, the delay and throughput weight coefficients will increase sharply. Meanwhile, the transmitted probability of the packets of this service will increase, which helps to support QoS requirements better.


## 2.6. Throughput Utility Optimization Problem

Similar to the design of utility function in [18], let the utility function of service k in sessionm, Um(k)(·), be a concave, differentiable, and nondecreasing utility function with Um(k)(0)=0. The throughput utility maximization problemP1 can be defined as follows:(13)maximize∑m∈M∑k∈KσkDσkTUmkηmk¯subject  tor¯∈Λ,0≤r¯≤λ,η¯≤r¯,∑j:n,j∈Lαnjt+∑i:i,n∈Lαint≤1,Pxymint≤Pxyt≤Pxymaxt,∀x,y∈N.Similar to the definition in Section 2.2, x¯ is the time average value of time-varying variable x(t), and x¯ is calculated according to x¯=limt→∞⁡1/t∑τ=0t-1E(x(τ)). Here, r¯=(rm(k)¯), η¯=(ηm(k)¯), λm(k)=E{Am(k)(t)}, and λ=(λm(k)). Λ is the capacity region of the network. The constraint r¯∈Λ is used to guarantee the stability of the network.


## 3. Dynamic Algorithm via Lyapunov Optimization

Lyapunov optimization technique is applied to solveP1. Qn(m)(k)(t)(∀n≠dm,m∈M,k∈K) and Ym(k)(t)(m∈M,k∈K) are used in the dynamic algorithm. Let Θ(t)=[Q(t),Y(t)] be the network state vector in time slot t. Define the Lyapunov function as (14)LΘt=12∑m∈M∑k∈KYmkt2+∑n≠dmk∑m∈M∑k∈KβkQnmkt2.The conditional Lyapunov drift in time slot t is(15)ΔΘt=ELΘt+1-LΘt∣Θt.To maximize a lower bound for ∑m∈M∑k∈KσkDσkTUm(k)(ηm(k)¯), the drift-plus -penalty function can be defined as (16)ΔVΘt=ΔΘt-V·E∑m∈M∑k∈KσkDσkTUmkηmkt∣Θt,where V is the weight of utility defined by user. The following inequality can be derived:(17)EΔVΘt≤B-Ψ1t-Ψ2t-Ψ3t;here, Ψ1(t), Ψ2(t), and Ψ3(t) can be evaluated as follows: (18)Ψ1t=∑m∈M∑k∈KV·σkDσkTUmkηmkt-Ymkt·ηmkt,Ψ2t=∑m∈M∑k∈KrmktYmkt-βk·Qnmkt·1n=smk,Ψ3t=∑n≠dmk∑m∈M∑k∈K∑i∈Onμnimkt·βk·Qnmkt-Qimkt.B is a constant and satisfies(19)B≥∑n≠dmk∑m∈M∑k∈Kβk∑i∈Onμnimkt2+∑j∈Inμjnmkt+rmkt2+∑m∈M∑k∈Krmkt2+ηmkt2.Assume that in this paper the transmit capacity of each link is a constant value Cmax by using a power control algorithm. According to rm(k)(t)∈[0,Am(k)(t)], ηm(k)(t)∈[0,Amax(m)(k)], and Cmax, constant B must exist.The algorithm CADSP (Cross-Layer Algorithm with Differentiated Service Prioritization) scheme is based on the drift-plus-penalty framework [17]. The main design principle of the algorithm is to minimize the right-hand side of (17). This scheme consists of three parts which are joint flow control, routing, and scheduling scheme, medium access control scheme, and power control algorithm.


### 3.1. Joint Flow Control, Routing, and Scheduling Scheme

This scheme includes four parts as follows.Source Rate Control. For sessions m∈M and k∈K at source node sm(k), the admitted rate rm(k)(t) is chosen to solve(20)maximizermktYmkt-βk·Qsmkmktsubject  to0≤rmkt≤Amkt.Problem (20) is a linear optimization problem, and if Ym(k)(t)>βk·Qsm(k)(m)(k)(t), rm(k)(t) is set to be Am(k)(t); otherwise it is set to be zero.Virtual Input Rate Control. For sessions m∈M and k∈K at source node sm(k), the virtual input rate ηm(k)(t) is chosen to solve(21)maximizeV·σkDσkTUmkηmkt-Ymkt·ηmktsubject  to0≤ηmkt≤Amaxmk.If Um(k)(·) is strictly concave and twice differentiable, (21) is a concave maximization problem with linear constraint. ηmk(·) can be chosen by(22)ηmkt=max⁡min⁡Um′-1kYmktVσkDσkT,Amaxmk,0,where Um′-1(k)(·) is the inverse function of Um′(k)(·) that is the first-order derivative of Um(k)(·). Since the utility function Um(k)(·) is strictly concave and twice differentiable, Um′(k)(·) must be a monotonic function, and therefore, Um′-1(k)(·) must exist. If Um(k)(·) is a linear function, let us suppose Um(k)(x)=bx. ηm(k)(·) can be calculated as (23)ηmkt=AmaxmkifVbσkDσkT>Ymkt0ifVbσkDσkT≤Ymkt.Joint Routing and Scheduling. At the node n≠dm(k), routing and scheduling decisions for each service k in session m can be made by solving the following: (24)maximize∑n≠dmk∑m∈M∑k∈K∑i∈Onμnimkt·βk·Qnmkt-Qimktsubject  to0≤μabmkt≤Cabt,∀a,b∈N,∑j:n,j∈Lαnjt+∑i:i,n∈Lαint≤1,Pxymint≤Pxyt≤Pxymaxt,∀x,y∈N.Cab(t) denotes the capacity of link (a,b) in time slott, and Cab(t) is calculated according to (3). The first constraint of (24) indicates that the amount of data to be forwarded from one node to another node in a time slot should not be greater than the capacity of the link between these two nodes in time slot t. The second constraint of (24) is built according to constraint (1) given in Section 2.1. The third constraint of (24) is built according to constraint (6) given in Section 2.1.First, the best servicek∗ and the best session m∗ whose data should be transmitted on link (n,i) can be chosen as(25)m∗,k∗=argmaxm∈M,k∈Kβk·Qnmkt-Qimkt.The weight value of link (n,i) is calculated using the following method as(26)wni=βk∗·Qnm∗k∗t-Qim∗k∗t.So the joint routing and scheduling problem can be reduced to the following problem:(27)maximize∑n≠dm∗k∗∑i∈Onμnim∗k∗t·wnisubject  to0≤μabmkt≤Cabt,∀a,b∈N,∑j:n,j∈Lαnjt+∑i:i,n∈Lαint≤1,Pxymint≤Pxyt≤Pxymaxt,∀x,y∈N.Transmission rates μni(m∗)(k∗)(t) are chosen based on (27) which is a hard problem for solving as it requires global knowledge and centralized algorithm. We define Pc as the set of transmit powers on each link and define Ic as the set of links which can be used for data transmission simultaneously when using Pc as the set of transmit powers. I is defined as the set of (Pc,Ic). In each slot, (Pc∗,Ic∗)∈I that maximizes ∑n≠dm∗(k∗)∑i∈O(n)μni(m∗)(k∗)(t)·wni is chosen as the set of scheduled links and the set of transmit powers.Update of Queues. Y(t) and Q(t) are updated using (7) and (8) in each time slot.


### 3.2. Distributed Medium Access Control Scheme

Solving (27) is a NP-hard problem whose computation complexity is O(N2) where N denote the number of nodes in the network. Obviously, the computation complexity will increase shapely with the increase of N. To reduce the computation complexity, a distributed medium access control scheme for routing and link scheduling is proposed in this section. The design principle of this distributed scheme is that nodes with higher weight values will get higher probabilities of accessing the medium and transmitting data. When the runtime is long enough, the distributed media access control scheme plays the same role to the GMS (Greedy Maximal Scheduling) algorithm which is a central algorithm and whose capacity region can reach 1/2 capacity region of MWM (Maximal Weighted Matching) [19] which is the basic of the central cross-layer routing and scheduling scheme proposed in Section 3.1.The medium access control scheme is implemented in a time-slotted fashion on the common control channel. The way that nodes contend to access the control channel is similar to IEEE 802.11 two-way RTS and CTS handshake. The medium access control logic is illustrated in Figure1. The details of the scheme are as follows. (i) There is a central control node which implements the power control algorithm and records state information of existing links, including transmit power, positions of nodes, and noises at the receiving nodes. (ii) At the beginning of each slot, each node trying to send data chooses a random waiting time RB∈[0,Rtime]. The value of Rtime is calculated in the central control node. It relates with number of nodes in the network. (iii) Each node sends IU packet that includes information about weight value, the next hop node chosen, current position, and noise on the control channel after waiting for RB. For the send node n, the receiving node of node n is i∗=argmaxi∈Nwni, and the weight value of node n is wn=wni∗. Each node also monitors the IU packets from other nodes to gain the weight values of other nodes. (iv) Every backlogged node i calculates its contention window CWi and backoff counter BCi [20] as follows:(28)CWi=-φ·wi∑n∈Nwn+γ,φ>0,γ>0.BCi is randomly chosen from the range [0,2CWi-1]. (v) After Rtime from the beginning of the slot, each backlogged node i continues monitoring the control channel. If the node i senses an idle control channel for a period of DIFS+BCi, it can send RTS packet which includes Qi(m∗)(k∗)(t). RTS packet also includes the information about the receiving node in plan. (vi) After receiving RTS packet from nodei, the central control node checks if the receiving node in plan of node i is in transmission. The control node also implements the power control algorithm to decide if the new link is allowed to be established. If the new link is allowed to be established, the control node responds with a CTS packet that includes the new transmit powers and transmission time lengths of all send nodes after a period of SIFS; otherwise, the control node responds with a NCTS that includes decision that the new link is not allowed to be established. (vii) The send nodes update the transmit powers after receiving CTS packet. The receiving node in plan of node i prepares for data reception and responds with a ACK packet after the successful data reception. Without considering the weight value of nodei, idle nodes update their contention windows and backoff counters after receiving CTS packet. (viii) Node i and other idle nodes begin to monitor the control channel for further negotiation after receiving NCTS packet. (ix) The maximum times that each node is allowed to send RTS packets in a time slot is three.Figure 1
Medium access control logic.


### 3.3. Power Control Algorithm

The power control algorithm is implemented in the central control node of the network. The design objective of the algorithm is to ensure that the SINR at every receiving node isSINRth. Assume that there have been n links in the network. The links from send nodes to receiving nodes are represented by (x1,y1),(x2,y2),…,(xn,yn). When node xn+1 tries to transmit data packets to node yn+1, it send RTS packet on the control channel. After receiving RTS packet from xn+1 by monitoring the common control channel, the central control node begins the computation to check the transmit powers (Px1y1,Px2y2,…,Pxn+1yn+1) of all send nodes (x1,x2,…,xn+1) which can guarantee that the following equalities exist:(29)Pxiyi·Gxiyinyi+∑j=1n+1Pxjyj·Gxjyi·1j≠i=SINRth,where i∈[1,n+1]. If we can get (Px1y1,Px2y2,…,Pxn+1yn+1), the new link (xn+1,yn+1) can be established. Equation (29) can be transformed into multivariate equations as follows:(30)GX=S,where (31)G=Gx1y1-Gx2y1·SINRth-Gx3y1·SINRth…-Gxn+1y1·SINRth-Gx1y2·SINRthGx2y2-Gx3y2·SINRth…-Gxn+1y2·SINRth-Gx1y3·SINRth-Gx2y3·SINRthGx3y3…-Gxn+1y3·SINRth…-Gx1yn+1·SINRth…-Gx2yn+1·SINRth……………Gxn+1yn+1,X=Px1y1,Px2y2,…,Pxn+1yn+1T,S=SINRth·ny1,ny2,…,nyn+1T.If 0<Pxiyi≤Pxi,max, the link (xn+1,yn+1) is allowed to be established. Here i∈[1,n+1], and Pxi,max represents the maximum transmit power that node xi can support. On the common control channel, the central control node will broadcast (Px1y1,Px2y2,…,Pxn+1yn+1) which are new transmit powers of the send nodes.


## 3.1. Joint Flow Control, Routing, and Scheduling Scheme

This scheme includes four parts as follows.Source Rate Control. For sessions m∈M and k∈K at source node sm(k), the admitted rate rm(k)(t) is chosen to solve(20)maximizermktYmkt-βk·Qsmkmktsubject  to0≤rmkt≤Amkt.Problem (20) is a linear optimization problem, and if Ym(k)(t)>βk·Qsm(k)(m)(k)(t), rm(k)(t) is set to be Am(k)(t); otherwise it is set to be zero.Virtual Input Rate Control. For sessions m∈M and k∈K at source node sm(k), the virtual input rate ηm(k)(t) is chosen to solve(21)maximizeV·σkDσkTUmkηmkt-Ymkt·ηmktsubject  to0≤ηmkt≤Amaxmk.If Um(k)(·) is strictly concave and twice differentiable, (21) is a concave maximization problem with linear constraint. ηmk(·) can be chosen by(22)ηmkt=max⁡min⁡Um′-1kYmktVσkDσkT,Amaxmk,0,where Um′-1(k)(·) is the inverse function of Um′(k)(·) that is the first-order derivative of Um(k)(·). Since the utility function Um(k)(·) is strictly concave and twice differentiable, Um′(k)(·) must be a monotonic function, and therefore, Um′-1(k)(·) must exist. If Um(k)(·) is a linear function, let us suppose Um(k)(x)=bx. ηm(k)(·) can be calculated as (23)ηmkt=AmaxmkifVbσkDσkT>Ymkt0ifVbσkDσkT≤Ymkt.Joint Routing and Scheduling. At the node n≠dm(k), routing and scheduling decisions for each service k in session m can be made by solving the following: (24)maximize∑n≠dmk∑m∈M∑k∈K∑i∈Onμnimkt·βk·Qnmkt-Qimktsubject  to0≤μabmkt≤Cabt,∀a,b∈N,∑j:n,j∈Lαnjt+∑i:i,n∈Lαint≤1,Pxymint≤Pxyt≤Pxymaxt,∀x,y∈N.Cab(t) denotes the capacity of link (a,b) in time slott, and Cab(t) is calculated according to (3). The first constraint of (24) indicates that the amount of data to be forwarded from one node to another node in a time slot should not be greater than the capacity of the link between these two nodes in time slot t. The second constraint of (24) is built according to constraint (1) given in Section 2.1. The third constraint of (24) is built according to constraint (6) given in Section 2.1.First, the best servicek∗ and the best session m∗ whose data should be transmitted on link (n,i) can be chosen as(25)m∗,k∗=argmaxm∈M,k∈Kβk·Qnmkt-Qimkt.The weight value of link (n,i) is calculated using the following method as(26)wni=βk∗·Qnm∗k∗t-Qim∗k∗t.So the joint routing and scheduling problem can be reduced to the following problem:(27)maximize∑n≠dm∗k∗∑i∈Onμnim∗k∗t·wnisubject  to0≤μabmkt≤Cabt,∀a,b∈N,∑j:n,j∈Lαnjt+∑i:i,n∈Lαint≤1,Pxymint≤Pxyt≤Pxymaxt,∀x,y∈N.Transmission rates μni(m∗)(k∗)(t) are chosen based on (27) which is a hard problem for solving as it requires global knowledge and centralized algorithm. We define Pc as the set of transmit powers on each link and define Ic as the set of links which can be used for data transmission simultaneously when using Pc as the set of transmit powers. I is defined as the set of (Pc,Ic). In each slot, (Pc∗,Ic∗)∈I that maximizes ∑n≠dm∗(k∗)∑i∈O(n)μni(m∗)(k∗)(t)·wni is chosen as the set of scheduled links and the set of transmit powers.Update of Queues. Y(t) and Q(t) are updated using (7) and (8) in each time slot.


## 3.2. Distributed Medium Access Control Scheme

Solving (27) is a NP-hard problem whose computation complexity is O(N2) where N denote the number of nodes in the network. Obviously, the computation complexity will increase shapely with the increase of N. To reduce the computation complexity, a distributed medium access control scheme for routing and link scheduling is proposed in this section. The design principle of this distributed scheme is that nodes with higher weight values will get higher probabilities of accessing the medium and transmitting data. When the runtime is long enough, the distributed media access control scheme plays the same role to the GMS (Greedy Maximal Scheduling) algorithm which is a central algorithm and whose capacity region can reach 1/2 capacity region of MWM (Maximal Weighted Matching) [19] which is the basic of the central cross-layer routing and scheduling scheme proposed in Section 3.1.The medium access control scheme is implemented in a time-slotted fashion on the common control channel. The way that nodes contend to access the control channel is similar to IEEE 802.11 two-way RTS and CTS handshake. The medium access control logic is illustrated in Figure1. The details of the scheme are as follows. (i) There is a central control node which implements the power control algorithm and records state information of existing links, including transmit power, positions of nodes, and noises at the receiving nodes. (ii) At the beginning of each slot, each node trying to send data chooses a random waiting time RB∈[0,Rtime]. The value of Rtime is calculated in the central control node. It relates with number of nodes in the network. (iii) Each node sends IU packet that includes information about weight value, the next hop node chosen, current position, and noise on the control channel after waiting for RB. For the send node n, the receiving node of node n is i∗=argmaxi∈Nwni, and the weight value of node n is wn=wni∗. Each node also monitors the IU packets from other nodes to gain the weight values of other nodes. (iv) Every backlogged node i calculates its contention window CWi and backoff counter BCi [20] as follows:(28)CWi=-φ·wi∑n∈Nwn+γ,φ>0,γ>0.BCi is randomly chosen from the range [0,2CWi-1]. (v) After Rtime from the beginning of the slot, each backlogged node i continues monitoring the control channel. If the node i senses an idle control channel for a period of DIFS+BCi, it can send RTS packet which includes Qi(m∗)(k∗)(t). RTS packet also includes the information about the receiving node in plan. (vi) After receiving RTS packet from nodei, the central control node checks if the receiving node in plan of node i is in transmission. The control node also implements the power control algorithm to decide if the new link is allowed to be established. If the new link is allowed to be established, the control node responds with a CTS packet that includes the new transmit powers and transmission time lengths of all send nodes after a period of SIFS; otherwise, the control node responds with a NCTS that includes decision that the new link is not allowed to be established. (vii) The send nodes update the transmit powers after receiving CTS packet. The receiving node in plan of node i prepares for data reception and responds with a ACK packet after the successful data reception. Without considering the weight value of nodei, idle nodes update their contention windows and backoff counters after receiving CTS packet. (viii) Node i and other idle nodes begin to monitor the control channel for further negotiation after receiving NCTS packet. (ix) The maximum times that each node is allowed to send RTS packets in a time slot is three.Figure 1
Medium access control logic.


## 3.3. Power Control Algorithm

The power control algorithm is implemented in the central control node of the network. The design objective of the algorithm is to ensure that the SINR at every receiving node isSINRth. Assume that there have been n links in the network. The links from send nodes to receiving nodes are represented by (x1,y1),(x2,y2),…,(xn,yn). When node xn+1 tries to transmit data packets to node yn+1, it send RTS packet on the control channel. After receiving RTS packet from xn+1 by monitoring the common control channel, the central control node begins the computation to check the transmit powers (Px1y1,Px2y2,…,Pxn+1yn+1) of all send nodes (x1,x2,…,xn+1) which can guarantee that the following equalities exist:(29)Pxiyi·Gxiyinyi+∑j=1n+1Pxjyj·Gxjyi·1j≠i=SINRth,where i∈[1,n+1]. If we can get (Px1y1,Px2y2,…,Pxn+1yn+1), the new link (xn+1,yn+1) can be established. Equation (29) can be transformed into multivariate equations as follows:(30)GX=S,where (31)G=Gx1y1-Gx2y1·SINRth-Gx3y1·SINRth…-Gxn+1y1·SINRth-Gx1y2·SINRthGx2y2-Gx3y2·SINRth…-Gxn+1y2·SINRth-Gx1y3·SINRth-Gx2y3·SINRthGx3y3…-Gxn+1y3·SINRth…-Gx1yn+1·SINRth…-Gx2yn+1·SINRth……………Gxn+1yn+1,X=Px1y1,Px2y2,…,Pxn+1yn+1T,S=SINRth·ny1,ny2,…,nyn+1T.If 0<Pxiyi≤Pxi,max, the link (xn+1,yn+1) is allowed to be established. Here i∈[1,n+1], and Pxi,max represents the maximum transmit power that node xi can support. On the common control channel, the central control node will broadcast (Px1y1,Px2y2,…,Pxn+1yn+1) which are new transmit powers of the send nodes.


## 4. Performance Analysis

Theorem 1 (algorithm performance).
Defineφ(r)=∑m∈M∑k∈KσkDσkT·Um(k)(rm(k)) and the optimization problemP2 as(32)maximizeφrsubjecttor¯∈Λ,0≤r¯≤λ,∑j:n,j∈Lαnjt+∑i:i,n∈Lαint≤1,Pxymint≤Pxyt≤Pxymaxt,∀x,y∈N.Define φ∗ as the optimal value of φ(r) and rm∗(k) as the solution ofP2. Under the implementation of central CADSP scheme proposed in Section 3.1, the following inequality holds:(33)∑m∈M∑k∈KσkDσkT·Umkrmk¯≥φ∗-BV.Proof.
According to Lemma  4 in [18], similar to Theorem  3 in [16], the following inequality holds when τ=0,1,…,T-1: (34)∑τ=0T-1EΔΘτ-V·∑τ=0T-1∑m∈M∑k∈KσkDσkTUmkηmkτ≤B·T-V·T∑m∈M∑k∈KσkDσkTUmkηm∗k-∑τ=0T-1∑m∈M∑k∈KYmkτrm∗k-ηm∗k-∑τ=0T-1∑n≠dmk∑m∈M∑k∈KQnmkτ∑i∈Onμni∗mkτ-∑j∈Inμjn∗mkτ-1n=smkrm∗k.According to the equalities which can be got, ∑i∈O(n)μni∗(m)(k)(τ)-∑j∈I(n)μjn∗(m)(k)(τ)=1{n=sm(k)}rm∗(k) and rm∗(k)=ηm∗(k), (34) can be transformed into following inequality:(35)∑m∈M∑k∈KσkDσkTUmkηmk¯≥φ∗-BV.As CADSP scheme can guarantee that η¯≤r¯ and function Um(k)(·) is nondecreasing, the following inequality can be got:(36)∑m∈M∑k∈KσkDσkT·Umkrmk¯≥φ∗-BV.Inequality (36) means the overall throughput utility achieved by the algorithm in this paper is within a constant gap from the optimum value.


## 5. Simulation

### 5.1. Simulation Setup

The network for simulations is considered as a network with 20 nodes randomly distributed in a square of 900 m2. There are two unicast sessions with randomly chosen sources and destinations. Each session includes three services. Data are injected at the source nodes following Poisson arrivals. The simulation time lasts 10000 time slots. All the initial queue sizes are set to be 0. The throughput utility function is U(x)=log(x+1). Table 1 summarizes the simulation parameters.Table 1
Simulation parameters.
Parameter
Value
Bandwidth
1 MHz
Slot time
20 ms
SINRth
20 dB
Packet length
1000 bits
DIFS
50μs
SIFS
20μs
Rtime
50μs
Maximum times allowed to send RTS
3
φ
10
γ
10In this paper, the performance of CADSP is compared with Backpressure scheme [21] and PDA-PMF scheme [6]. Backpressure scheme is a classical joint routing and scheduling algorithm that can provide throughput utility optimality. PDA-PMF scheme is a services-differentiated scheduling policy. In this simulation, PDA-PMF scheme is combined with AODV routing algorithm.


### 5.2. Simulation of Services with Different Delay Requirements

In this section, the average data arrival rates of all the services are the same. The maximum allowable end-to-end delay bounds of services are set asD1th=0.8 s, D2th=2 s, and D3th=4 s. The required average throughputs of services are set as Th1th=Th2th=Th3th = 0.5 × 105 bits/s.We compare against the three solutions by varying the average data arrival rate and plot the average throughput of service 1 in Figure2, which shows that CADSP outperforms Backpressure and PDA-PMF. When the average data arrival rate is lower than 5 × 105 bits/s, the three schemes obtain similar throughput performance. However, with higher average data arrival rate, CADSP and PDA-PMF perform much better than Backpressure, since service 1 under CADSP and PDA-PMF is assigned the highest priority in the three services, and it can get more transmission opportunities than service 1 under Backpressure which has the same priority as the other two services. As Backpressure-based algorithm has throughput optimality, CADSP performs better than PDA-PMF in throughput performance.Figure 2
Comparison of average throughput of service 1 in multihop network.Figure3 shows the average end-to-end delay performance of service 1 for the three solutions. When the average data arrival rate is lower than 5.5 × 105 bits/s, PDA-PMF performs best. But when the average data arrival rate is above 6.5 × 105 bits/s, the average end-to-end delay of service 1 under PDA-PMF is higher than the maximum allowable end-to-end delay bound of service 1. The average end-to-end delay of CADSP is always below the maximum allowable end-to-end delay bound of service 1, since CADSP using delay weight coefficient can provide better delay guarantee. When the average data arrival rate is in the range from 0.5 × 105 bits/s to 4 × 105 bits/s, the average end-to-end delay of CADSP and Backpressure decreases. The reason is that the end-to-end delay will be high if the traffic load is too low for the formation of “queue length pressure” from source nodes to destination nodes.Figure 3
Comparison of average end-to-end delay of service 1 in multihop network.The performances of the three solutions in terms of average throughput of service 2 are compared in Figure4, which shows that CADSP outperforms Backpressure and PDA-PMF. When the average data arrival rate is lower than 4 × 105 bits/s, the three schemes obtain similar throughput performance. However, with higher average data arrival rate, CADSP performs better than Backpressure and PDA-PMF. From Figure 2 we can see that when traffic load is high, CADSP can still maintain good performance in terms of average throughput for service 2.Figure 4
Comparison of average throughput of service 2 in multihop network.Figure5 shows the average end-to-end delay performance of service 2 for the three solutions. Since the priority of service 2 in CADSP is not as high as service 1, the average end-to-end delay performance deteriorates. However, the average end-to-end delay of service 2 is still maintained being lower than the maximum allowable end-to-end delay bound of service 2 by using delay weight coefficient. We can also see that, in the condition of low traffic load, the performance of average end-to-end delay of PDA-PMF is the best.Figure 5
Comparison of average end-to-end delay of service 2 in multihop network.In Figure6, the average throughput of service 3 of the three solutions is compared. From the figure we can see that Backpressure with the same priority for each service outperforms CADSP and PDA-PMF. Since service 3 in CADSP and PDA-PMF is scheduled with the lowest priority, their average throughput cannot increase with the increase of average data arrival rate when traffic load is high. However, the average throughput of service 3 of CADSP is always higher than the required average throughput of service 3 through using throughput weight coefficient.Figure 6
Comparison of average throughput of service 3 in multihop network.The average end-to-end delay performance of service 3 for the three solutions can be seen from Figure7. Though CADSP performs worse than Backpressure in most conditions, its average end-to-end delay is maintained being lower than the maximum allowable end-to-end delay bound of service 3.Figure 7
Comparison of average end-to-end delay of service 3 in multihop network.From the simulation results above, we can see that CADSP can support QoS requirements of all services.We plot the throughput of the three solutions in Figure8, which shows that Backpressure outperforms CADSP and PDA-PMF. The reason is that Backpressure can provide the throughput optimality, while the throughput optimality of CADSP is destroyed by introducing throughput and delay weight coefficients into the optimization objective.Figure 8
Comparison of throughput in multihop network.


### 5.3. Simulation of Services with Different Average Data Arrival Rates

The average data arrival rate of service 1 is four times that of service 3. The average data arrival rate of service 2 is two times that of service 3. The maximum allowable end-to-end delay bounds of services are set asD1th=D2th=D3th=2 s. The required average throughputs of services are set as Th1th=Th2th=Th3th = 0.5 × 105 bits/s.In Figure9 the average throughputs of the three services using CADSP are compared. From the figure we can see that the ratio among the average throughputs of the three services is close to the ratio among the average arrival data rates of the three services.Figure 9
Comparison of average throughput in multihop network.The average end-to-end delay performances of the three services using CADSP are compared in Figure10. The performances in terms of average end-to-end delay of service 1 and service 2 are lower than the maximum allowable end-to-end delay bound. When the average data arrival rate is lower than 2 × 105 bits/s, the average end-to-end delay of service 3 is higher than the maximum allowable end-to-end delay bound of service 3. The reason is that the average data arrival rate of service 3 is too low to form the “queue length pressure” to push packets of service 3 from source node to destination node, and this increases the average end-to-end delay of service 3.Figure 10
Comparison of average end-to-end delay in multihop network.


## 5.1. Simulation Setup

The network for simulations is considered as a network with 20 nodes randomly distributed in a square of 900 m2. There are two unicast sessions with randomly chosen sources and destinations. Each session includes three services. Data are injected at the source nodes following Poisson arrivals. The simulation time lasts 10000 time slots. All the initial queue sizes are set to be 0. The throughput utility function is U(x)=log(x+1). Table 1 summarizes the simulation parameters.Table 1
Simulation parameters.
Parameter
Value
Bandwidth
1 MHz
Slot time
20 ms
SINRth
20 dB
Packet length
1000 bits
DIFS
50μs
SIFS
20μs
Rtime
50μs
Maximum times allowed to send RTS
3
φ
10
γ
10In this paper, the performance of CADSP is compared with Backpressure scheme [21] and PDA-PMF scheme [6]. Backpressure scheme is a classical joint routing and scheduling algorithm that can provide throughput utility optimality. PDA-PMF scheme is a services-differentiated scheduling policy. In this simulation, PDA-PMF scheme is combined with AODV routing algorithm.


## 5.2. Simulation of Services with Different Delay Requirements

In this section, the average data arrival rates of all the services are the same. The maximum allowable end-to-end delay bounds of services are set asD1th=0.8 s, D2th=2 s, and D3th=4 s. The required average throughputs of services are set as Th1th=Th2th=Th3th = 0.5 × 105 bits/s.We compare against the three solutions by varying the average data arrival rate and plot the average throughput of service 1 in Figure2, which shows that CADSP outperforms Backpressure and PDA-PMF. When the average data arrival rate is lower than 5 × 105 bits/s, the three schemes obtain similar throughput performance. However, with higher average data arrival rate, CADSP and PDA-PMF perform much better than Backpressure, since service 1 under CADSP and PDA-PMF is assigned the highest priority in the three services, and it can get more transmission opportunities than service 1 under Backpressure which has the same priority as the other two services. As Backpressure-based algorithm has throughput optimality, CADSP performs better than PDA-PMF in throughput performance.Figure 2
Comparison of average throughput of service 1 in multihop network.Figure3 shows the average end-to-end delay performance of service 1 for the three solutions. When the average data arrival rate is lower than 5.5 × 105 bits/s, PDA-PMF performs best. But when the average data arrival rate is above 6.5 × 105 bits/s, the average end-to-end delay of service 1 under PDA-PMF is higher than the maximum allowable end-to-end delay bound of service 1. The average end-to-end delay of CADSP is always below the maximum allowable end-to-end delay bound of service 1, since CADSP using delay weight coefficient can provide better delay guarantee. When the average data arrival rate is in the range from 0.5 × 105 bits/s to 4 × 105 bits/s, the average end-to-end delay of CADSP and Backpressure decreases. The reason is that the end-to-end delay will be high if the traffic load is too low for the formation of “queue length pressure” from source nodes to destination nodes.Figure 3
Comparison of average end-to-end delay of service 1 in multihop network.The performances of the three solutions in terms of average throughput of service 2 are compared in Figure4, which shows that CADSP outperforms Backpressure and PDA-PMF. When the average data arrival rate is lower than 4 × 105 bits/s, the three schemes obtain similar throughput performance. However, with higher average data arrival rate, CADSP performs better than Backpressure and PDA-PMF. From Figure 2 we can see that when traffic load is high, CADSP can still maintain good performance in terms of average throughput for service 2.Figure 4
Comparison of average throughput of service 2 in multihop network.Figure5 shows the average end-to-end delay performance of service 2 for the three solutions. Since the priority of service 2 in CADSP is not as high as service 1, the average end-to-end delay performance deteriorates. However, the average end-to-end delay of service 2 is still maintained being lower than the maximum allowable end-to-end delay bound of service 2 by using delay weight coefficient. We can also see that, in the condition of low traffic load, the performance of average end-to-end delay of PDA-PMF is the best.Figure 5
Comparison of average end-to-end delay of service 2 in multihop network.In Figure6, the average throughput of service 3 of the three solutions is compared. From the figure we can see that Backpressure with the same priority for each service outperforms CADSP and PDA-PMF. Since service 3 in CADSP and PDA-PMF is scheduled with the lowest priority, their average throughput cannot increase with the increase of average data arrival rate when traffic load is high. However, the average throughput of service 3 of CADSP is always higher than the required average throughput of service 3 through using throughput weight coefficient.Figure 6
Comparison of average throughput of service 3 in multihop network.The average end-to-end delay performance of service 3 for the three solutions can be seen from Figure7. Though CADSP performs worse than Backpressure in most conditions, its average end-to-end delay is maintained being lower than the maximum allowable end-to-end delay bound of service 3.Figure 7
Comparison of average end-to-end delay of service 3 in multihop network.From the simulation results above, we can see that CADSP can support QoS requirements of all services.We plot the throughput of the three solutions in Figure8, which shows that Backpressure outperforms CADSP and PDA-PMF. The reason is that Backpressure can provide the throughput optimality, while the throughput optimality of CADSP is destroyed by introducing throughput and delay weight coefficients into the optimization objective.Figure 8
Comparison of throughput in multihop network.


## 5.3. Simulation of Services with Different Average Data Arrival Rates

The average data arrival rate of service 1 is four times that of service 3. The average data arrival rate of service 2 is two times that of service 3. The maximum allowable end-to-end delay bounds of services are set asD1th=D2th=D3th=2 s. The required average throughputs of services are set as Th1th=Th2th=Th3th = 0.5 × 105 bits/s.In Figure9 the average throughputs of the three services using CADSP are compared. From the figure we can see that the ratio among the average throughputs of the three services is close to the ratio among the average arrival data rates of the three services.Figure 9
Comparison of average throughput in multihop network.The average end-to-end delay performances of the three services using CADSP are compared in Figure10. The performances in terms of average end-to-end delay of service 1 and service 2 are lower than the maximum allowable end-to-end delay bound. When the average data arrival rate is lower than 2 × 105 bits/s, the average end-to-end delay of service 3 is higher than the maximum allowable end-to-end delay bound of service 3. The reason is that the average data arrival rate of service 3 is too low to form the “queue length pressure” to push packets of service 3 from source node to destination node, and this increases the average end-to-end delay of service 3.Figure 10
Comparison of average end-to-end delay in multihop network.


## 6. Conclusions

This paper proposed a cross-layer QoS scheme which can provide different QoS guarantees for diverse types of services. Through setting priorities of services depending on services’ data arrival rates and end-to-end delay demands, services with higher QoS demands can gain better QoS performance. The delay and throughput weight coefficients in the objective of the optimization problem help to maintain fairness of the policy and make the scheme support QoS requirements better. The throughput utility optimality of the scheme is kept. A distributed medium access control scheme and a power control algorithm are designed to reduce the computational complexity of the scheme. Compared with the existing works, the policy presented in this paper can simultaneously support the delay requirements of different services and maintain higher throughput.



---

*Source: 4892038-2017-12-28.xml*