{'fraction_non_alphanumeric': 0.03963402291405206, 'fraction_numerical': 0.009797174203473544, 'mean_word_length': 4.3088330109606705, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stability Analysis of Device-to-Device Relay-Assisted Cellular Networks

Motivated by increasing popularity of delay sensitive applications, we investigate the queue stability in device-to-device (D2D) relay-assisted cellular networks. In contrast to prior works on D2D relay-assisted cellular networks, we incorporate practical properties of these networks such as bursty packet arrivals, user mobility and relays generating their own traffic. Assuming network topology evolving in IID fashion, we first evaluate the system stability region to quantify its delay performance. Subsequently, we formulate a policy for joint resource allocation and power control under a more realistic mobility scenario of generalized reflected random walk. Also, the throughput optimality of this policy is investigated. Simulation results are provided to give better understanding of queue stability in the network.


I. INTRODUCTION
Device-to-device (D2D) communications is a promising technique for complementing and enhancing the conventional cellular systems through spatial diversity [1]. With D2D communications, a user can act as a virtual infrastructure to relay the data being transmitted from other users in the network for combating fading and improving coverage [2]. Compared to traditional relays in relay-assisted cellular networks, such D2D relay nodes can be deployed without incurring any additional infrastructure cost.
With the rising prospects for deployment of D2D relayassisted cellular networks [3], extensive research is being undertaken on it. In [4], the authors formulated analytical models for the uplink coverage probability and spectral efficiency of D2D relay-assisted cellular networks. In [5], the authors considered D2D relaying in multi-cell downlink networks. They analyzed the inter-cell interference using fluid network model and captured the interaction between relaying decisions and inter-cell interference. In [6], the authors investigated joint D2D relay node placement and power allocation with the objective of maximizing energy efficiency. In [7], the authors studied the problem of incentivizing users to cooperate in relaying. Despite this recent progress, prior works in D2D relay-assisted cellular networks have only considered physical layer dynamics. Since most applications are delaysensitive, it is very important to consider delay performance in addition to physical layer throughput. Addressing resource allocation and power control for delay-sensitive applications is non-trivial as it involves both queueing theory (to model the queue dynamics) and information theory (to model the physical layer dynamics).
The defining feature of D2D relay-assisted cellular networks that makes it so attractive is that users act as D2D relay nodes. This implicitly infers that relays can generate their own exogenous arrivals to the network which complicates the design of policies for resource allocation and power control. Additionally, mobility of users is a paramount feature in wireless networks which significantly affects the achievable performances [8]. An example of mobility is the usage of smartphones as relays [9]. To the authors' best knowledge, no previous work has investigated the delay performance in the D2D relay-assisted cellular networks while including the above practical features.
In this paper, each user is assumed to be mobile with bursty arrivals and has queues of infinite length for storing the arriving packets. Each user acts as both source and relay for other users with the base station (BS) being the final destination for all the packets in the network. The goal of this work is to formulate a policy for resource allocation and power control for an underlay D2D relay-assisted cellular network that guarantees queue stability for each user while satisfying average power constraints. For brevity, hereinafter, each user will be referred to as Mobile Station (MS). In summary, our contributions are as follows: • In contrast to prior works on D2D relay-assisted cellular networks, our network includes practical features such as bursty nature of packet arrivals, D2D relays generating their own traffic to the network and mobility of all MSs. • We evaluated the system stability region to quantify the delay performance under the assumption that the network topology evolves in an IID fashion. • We formulated an online policy for joint resource allocation and power control for network topology evolving as a generalized random walk that is proved to be −throughput optimal in terms of queue stability. The remainder of the paper is organised as follows. We describe the proposed system model in Section II. The system stability region is quantified in Section III. In Section IV, we present the proposed online scheduling policy for joint resource allocation and power control and investigate its optimality in terms of queue stability. In Section V, we present numerical simulation results on the performance of the policy. Finally, we draw the main conclusions in Section VI. {1, . . . , N } where nodes 1, ..., N represent MSs in the network and node 0 represents the BS. The direct transmission between an MS and the BS is a cellular link and that between any two MSs is a D2D link. In this paper, only uplink is considered and, thus, an MS transmits its data either directly to BS or relay via another MS. For tractability, the number of hops is limited to two. With focus on underlay D2D communication, the spectrum is shared between cellular links and D2D links. Time is slotted and each slot has equal length. The coverage area of the BS is divided into a uniform square grid. Each MS i is on a grid point in every slot. Fig. 1 illustrates the system model described here. To model mobility, we assume that each MS performs generalised reflected random walk on the grid points, i.e. each MS stays at the current position or moves to one of the adjacent grid points. The probability with which a MS moves may vary from MS to MS and may also depend on the current position of the MS. However, we assume that the movements of various MSs are independent, and mobility process for each MS is an irreducible and aperiodic Markov chain. Let s(n) denote the network topology in slot n. Let S denote the set of all possible network topologies, i.e. s(n) ∈ S with probability 1 for every n. Also, let [π s ] s∈S denote the steady state distribution of the Markov chain modelling the evolution of network topology.
At each node i ∈ [N ], exogenous packets arrive as per arrival process {A i (n)} ∞ n=1 , where A i (n) is the number of packets arriving at MS i in slot n. We assume that the arrivals are independent and identically distributed (IID) across slots for every MS i. Moreover, arrivals are independent across MSs. Let A i (n) ≤ A max for every MS i ∈ [N ]. Also, let λ i = E[A i (n)] and λ = [λ 1 · · · λ N ] denote the arrival rate vector. At each MS, we allow for transmit power selection and thereby rate adaptation. Specifically, we assume that each MS can pick one of the finitely many possible power levels available to it. A transmit power vector [ 10 , 12 , ..., ij , ...] is an N 2 -dimensional vector in which (i, j) th element, ij , for i, j ∈ [N ], denotes the power expended by MS i to transmit packets to MS j over the link (i, j) and i0 is the power expended by MS i for transmitting directly to BS. Let L denote the set of all possible power vectors satisfying the assumption that in each slot, an MS can transmit to only one receiver. Denote by µ ij (s, ) the transmission rate (in packets per slot) on the link (i, j) in network topology s ∈ S with power vector ∈ L. Consider µ max be the maximum possible transmission rate across any link in the network at any topology. Additionally, suppose that each MS i complies with average power constraint. That is, Our proposed network entails each MS to maintain two queues, own queue for storing packets arriving exogenously to the MS and relay queue to store the packets arriving from other MSs for relaying to BS. With number of hops limited to two, packets from the relay queue are transmitted directly to the BS. Let X i (n) and Y i (n) represent the backlog in the own queue and relay queue of MS i in slot n, respectively. The queues' dynamics are described as follows: For every i ∈ N and n ∈ Z + {0}, Additionally, on the lines of [10], we establish a virtual power queue for each MS i with queue length U i (n) equal to the maximum excess power expended beyond the average power constraint over any interval ending in slot n. Defining U i (0) = 0, its dynamics evolve as follows: The U i (n) process acts as a single-server queue with constant departure in each slot given by the average power allocation P i , with 'arrivals' given by the total power allocated for outgoing transmissions of MS i in the current time slot. The intuition behind this construction is that if a scheduling policy ∆ with power vector ∆ ∈ L stabilises queues X i (n), Y i (n) and the virtual queue U i (n) for every i ∈ [N ], then that policy also satisfies the average power constraint for each MS (1). Consider P max be the maximum transmit power for any MS in the network.
Due to mobility, an MS can have good channel to the BS in one slot and can has poor channel to the BS in another slot. The MS can conveniently transmit its data to another MS that have good channel with the BS. The second MS can store the received packets in its relay queue. The second MS can later transmit the packets buffered in relay queue depending on availability of appropriate channel state and queue length. Hence, a scheduling policy must be formulated for allocating spectrum to appropriate MS for establishing wireless communication links with appropriate receivers at appropriate transmit power.

Definition 1 (Policy for Resource Allocation and Power Control).
A policy ∆ is an algorithm that chooses a power vector ∆ (n) ∈ L in every slot n.
Note that the decisions made by a policy can be based on the entire past and future information.
Next, we will provide the details on the notion of rate stable by relating the scheduling policies to the queue level dynamics and the average power expended. We will first define the average power consumed by MS i under ∆: where ∆ ij (n) is the transmit power on link (i, j) under policy ∆ in slot n. Define the average transmission rate on link (i, j): where µ ∆ ij (n) is compact notation for µ ij (s(n), ∆ (n)). Recall that when an MS sends data to the BS, i.e. on link (i, 0), it can either transmit packets backlogged in the own queue or in the relay queue. Let I ∆ i (n) denote the indicator function such that I ∆ i (n) = 1 if MS i transmits its own traffic to the BS in slot n under ∆, and 0 otherwise. Now, we have: µ ∆ iO and µ ∆ iR are the service rates for the own queue and the relay queue of MS i, respectively, under resource allocation policy ∆. A precise definition of rate stability associated with a policy ∆ for a given arrival rate vector λ is: states that the sum of average service rate for the packets in the own queue of each MS to the BS and to every other MS is greater than the average exogenous arrival rate. Condition (c) implies that the average service rate for relay queue at an MS is greater than the sum of average arrival rates for the traffic coming from the own queue of other MSs. We quantify the performance of a policy by its stability region.
Definition 3 (Rate region). Stability region C ∆ of policy ∆ is the set of arrival rate vectors λ for which ∆ is rate stable. System stability region C is ∪ ∆ C ∆ .
The set C contains all arrival rate vectors for which there exist a rate stable policy ∆. Clearly, larger the stability region, better the policy is. In this regard, we define the following.
Definition 4 (Throughput optimal policy). Policy ∆ is throughput optimal if C ∆ = C.
Next, we will quantify the system stability region.

III. QUANTIFICATION OF SYSTEM STABILITY REGION
The generalized random walk of each MS collectively implies that network topology also evolves as generalized random walk. Our target is to provide a policy for the network evolving under generalized random walk. Towards this end, we first characterize the stability region under the assumption that network topology instead evolves in an IID fashion. This assumption helps us in appropriating strong law of large numbers. Let C IID be the system stability region under the assumption that network topology evolves in an IID fashion. Assume that in each slot, topology s ∈ S is selected at random according to the probability distribution π s which is also the stationary distribution for our original network with topology evolving as generalized random walk. Let Λ IID denote the set of arrival rate vectors λ such that there exists some randomized policy identified by constants w sk and q isk for i ∈ [N ], s ∈ S and k = 1, ..., M satisfying Intuitively, w sk is the probability that power vector k ∈ L is selected given that the network topology is s ∈ S, q isk is the probability that MS i opts to transmit the packets in the own queue to BS given that power vector k ∈ L is selected and the network topology is s ∈ S. ijk is the power level of the link (i, j), if it is active under the power vector k . Equation (11) and (12) says that under the randomised policy identified by w sk and q isk for i ∈ [N ], s ∈ S and k = 1, ..., M , average departure rate from the own queue and relay queue of MS i, respectively, should be greater than their respective average arrival rate. Meanwhile, (13) guarantees that average power expended by the randomised policy satisfies the average power constraint. Then, we have the following. Theorem 1. The system stability region C IID = Λ IID .
The proof involves showing C IID ⊆ Λ IID and Λ IID ⊆ C IID . For the former, we take a λ ∈ C IID satisfying Definition 2 and then show that there exists w sk and q isk for i ∈ [N ], s ∈ S and k = 1, ..., M which are fulfilling constraints (9) and (10), for which λ satisfies constraints (11), (11) and (13). The latter involves defining a Lyapunov function and then using it to show that for each λ ∈ Λ IID , there exists a randomized policy which is rate stable for that λ, which by Definition 3 implies that λ ∈ C IID . A rigorous analysis is given in [12,Appendix B]. Note that the above characterization of system stability region provides a recipe for a throughput optimal randomized policy ∆ IID .
Taking into consideration of the sizes of current or future wireless networks, we would like to remark that it is not feasible to implement the randomized policy ∆ IID . They are computationally expensive as we would need to determine appropriate probability distributions. The search for probability distribution requires one to know all system parameters in advance, which is impossible to determine unless we seek to know up to a bounded time in future. So, we desire an online scheduling policy. Nevertheless, we would utilize the randomized policy to investigate the throughput optimality of the online policy.

IV. ONLINE POLICY FOR ACHIEVING SYSTEM STABILITY
In this section, we will formulate an online policy for resource allocation and policy control for network topology evolving as a generalized random walk. Afterwards, we will investigate its throughput optimality. Our process for formulating such a policy follows in three stages: 1) Construct an online throughput optimal policy for network topology evolving in IID fashion. 2) Construct an online T −step policy for similar topology evolution that uses stale information on queue lengths. 3) Construct an online T −step policy for network topology evolving as generalized random walk that uses stale information on queue lengths. As a first step towards our goal, assume that network topology evolves in IID fashion. Consider a policy ∆ o IID that solves the following optimization to obtain the power vector ∆ o IID (n) in slot n ≥ 0.
where s IID (n) is the network topology in slot n. The objective function can be interpreted as follows: inside the summation over i, the first term is summation of products of back-pressure involving own queue at MS i w.r.t the relay queue at an MS j and the transmission rate of link (i, j). The second term is the product of the maximum of the back-pressure of own queue and relay queue with respect to BS and the link connecting MS with the BS. The third term is the product of instantaneous virtual queue length with arrivals in that queue. The foloowing lemma states that C ∆ o IID IID = C IID = Λ IID . Lemma 1. Let λ be any stabilizable arrival rate vector with network topology changing in IID fashion in each slot. Then, ∆ o IID stabilizes the system. Proof: We provide a brief outline of the proof. For detailed proof, refer to [12,Appendix C]. We use the general framework of Lyapunov optimization introduced in [11] to prove stability. Towards that end, we define the following Lyapunov function Our goal is to determine the set A of vectors {X(n), Y(n), U(n)} such that the expected Lyapunov drift in any slot n ≥ 0 outside A is negative. That is, Using the fact that for every randomized policy ∆ IID and n ≥ 0, we show that A is finite for every λ ∈ C IID . Then, the Foster's Theorem [13,Theorem 2.2.3] guarantees that {X(n), Y(n), U(n)} n≥0 is positive recurrent, and for each queue the expected queue length under its stationary distribution is finite. Thus, the system is stable under ∆ o IID ∀λ ∈ Λ.
Next, consider that the time axis is divided in the intervals of length T , i.e., in intervals of the form [KT, (K +1)T −1]. Under the assumption that network topology evolves in IID fashion, we develop a policy ∆ T IID that solves the following optimization to obtain the power vector ∆ T IID (n) in each slot n ∈ [KT, (K + 1)T − 1].

Maximize:
The policy ∆ T IID computes ∆ T IID (n) based on stale information on queue lengths from the beginning of the interval, i.e., in the slots KT for K ≥ 0. The information on the queue lengths in the optimization are updated at the beginning of each interval. The following lemma shows that even with stale updates in queue lengths, one can obtain C Maximize: Consider J is a 1 × N -dimensional vector with all entries equal to 1. We have the following theorem to comment upon its throughput optimality.
Proof: We provide the proof outline. Consider the same Lyapunov function as defined in (15). We consider two similar networks but one network having topology evolving in IID fashion and the other network having topology evolving as generalized random walk. Assume that the stationary distribution of the network with topology evolving as generalized random walk is same as IID distribution of the first network. Let s IID (n) and s RW (n) be the state of the grid under IID and Markov mobility process at time n, respectively. Suppose that s IID (n) = s RW (n) for some n ∈ Also, we can show that for s IID (n) = s RW (n) in some slot n ∈ [KT, (K + 1)T − 1], we have For tractability, suppose there are two possible states, s 1 and s 2 , that network topology can assume. Let τ = | number of states s 1 in IID process − number of states s 1 in Markov process | . Then,using (18) and (19), we can show that the Lyapunov drift is negative outside a finite set C of vectors {X(KT ), Y(KT ), U(KT )} ∀λ ∈ Λ . Then, we apply Foster's Theorem to conclude that system is stable under ∆ T IID ∀λ ∈ Λ . It is important to note that due to exponentially fast convergence of empirical distribution to the unique stationary distribution for ergodic Markov chains [14], we have E[τ ] → 0 as T → ∞ and, thus, Λ \ Λ → Ø. For the detailed proof, see [12,Appendix E].
We term such policies that stabilize the system for arrival rate vectors λ ∈ Λ as −throughput optimal.

V. NUMERICAL RESULTS
In this section, we evaluate the performance of the proposed throughput optimal policy ∆ T RW for resource allocation and power control in a D2D relay-assisted cellular network. Towards this end, we simulated a 2-D grid with vertices of the form (a, b) such that a ∈ {0, 10, 20, ..., 2000},b ∈ {0, 10, 20, ..., 2000} in meters. Thus, two adjacent grid points are 10 meters away from each other. The MSs are restricted to move along the grid. Assume that the BS is located at (1000, 1000). In this simulation, 60 MSs are present in the grid. These MSs move in a reflected random walk fashion with each MS in each slot equally likely to go to any of its neighbouring grid point or stay at the same grid point. For convenience, assume that when any two MSs in the same grid point, they are separated by a distance of 1 meter. Each MS can assume power level from the set P = {20, 23.01, 24.77, 26.02, 26.99, 27.78, 28.45, 29.03, 29.54, 30} (in dBm) in each slot. The average power constraint at each MS is 28 dBm. The carrier frequency is taken to be 3.5 GHz. Applying OFDMA, there are 50 physical resource blocks (PRBs) to be assigned to various links amounting to total bandwidth of 10 MHz. For simplicity in simulation, it is assumed that each PRB can be assigned to only one MS in each slot, thereby, effectively removing interference. Thus, the transmission rate of a link is dependent only on the power level of the transmitting MS of that link. Thus, for any link (i, j), µ ij (s RW (n), ∆ T IID (n)) = µ ij (s RW (n), ∆ T IID ij (n)) However, we emphasize that that the theory developed in this work applies for any general interference scenario. We evaluate the performance of our policy described in (17) in two scenarios: (a) D2D relay-assisted cellular network as proposed in Section II and (b) cellular network with no relays. Note that in scenario (b), each MS just maintains own queue that backlogs the packets to be sent directly to the BS. Thus, for scenario (b), (17) modifies to Maximize: For evaluation of transmission rate µ T x,Rx (s RW (n), ∆ T RW ), we use alpha-beta-gamma (ABG) path loss model for 5G urban micro and macro-cellular scenarios [15]. For scaling purpose, assume that 1 packet = 25000 bits. For brevity, we assume that all MSs have symmetrical arrival rate. Note that we have used delay and queue length interchangeably. Fig. 2 illustrates the average delay per node for symmetric arrival rates of 18, 20, 25, 28 packets/slot. Each of these simulations were run for 50000 slots. It is important to note that for the scenario where relays are present, we have to calculate the sum of queue lengths in own queue and relay queue whereas in the scenario where relays are absent, we have to calculate queue length in own queue only. Clearly, from Fig.2, in both scenarios (a) and (b), the average queue length increases with arrival rate. Furthermore, it can be inferred that for the scenario (b), where relays are absent, the maximum stabilizable symmetric arrival rate lies between 18 packets/slot and 20 packets/slot while for scenario (a), where relays are present, the maximum stabilizable symmetric arrival rate lies between 25 packets/slot and 28 packets/slot. Thus, using relay increases the maximum symmetric stabilizable arrival rate by at least 25%. This implies that using mobile relays can be beneficial in alleviating the detrimental impact of mobility on delay [16].
To implement proposed −throughput optimal policy, we refer to Algorithm 1. We construct a weighted bipartite graph where the end-points of an edge represent a particular MS and a particular PRB. The edge symbolises assignment of the PRB to the MS. For finding the weight of an edge between a MS, say i, and a PRB, say prb, first evaluate the value of Then, determine the link from MS i that gives highest weight. The corresponding weight is the weight of the edge between MS i and PRB prb. One can apply suitable algorithm to find the maximum weighted bipartite matching of the above constructed bipartite graph to obtain an assignment of PRBs to the MSs such that objective in (17) is satisfied. The Python implementation for Algorithm 1 is provided in [17].

VI. CONCLUSIONS
In this paper, we investigated resource allocation and power control for delay-sensitive applications in D2D relayassisted cellular communication. We evaluated the system stability region when the network topology evolves in IID fashion. Thereafter, we formulated an online T −step policy for network topology evolving in a generalized random walk that is shown to be −throughput optimal with respect to above system stability region. We have also provided numerical results to illustrate the benefits of having relays. The future work will involve formulating a distributed policy for resource allocation and power control which is necessary from the point of scalability and robustness.