Delay-Aware Link Scheduling in IAB Networks with Dynamic User Demands

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 73, NO. 10, OCTOBER 2024 15125 Delay-Aware Link Scheduling in IAB Networks With Dynamic User Demands Yekaterina Sadovaya , Graduate Student Member, IEEE, Olga Vikhrova , Member, IEEE,WeiMao , Shu-ping Yeh ,OmidSemiari, Member, IEEE, Hosein Nikopour , Shilpa Talwar , Senior Member, IEEE, and Sergey Andreev , Senior Member, IEEE Abstract—Integrated Access and Backhaul (IAB) is a costefficient network densification technology for improving the coverage and capacity of the millimeter-wave (mmWave) cellular networks. In IAB systems, user traffic is forwarded to/from the wired base station by one or more relay stations, known as IAB nodes. Due to the multi-hop relaying, these systems may be subject to large packet delays and poor performance when the load is unevenly distributed among nodes. Addressing this limitation via delay-aware access and backhaul link scheduling in IAB networks is challenging due to potentially large network scale, complex topology, half-duplex, and interference constraints. In this paper, the topical link scheduling problem is formulated as a Markov decision problem (MDP) for a single-donor IAB system with a general topology that allows for users with different delay requirements and traffic dynamics. The proposed link scheduling strategy jointly optimizes (i) user traffic routing and (ii) multiplexing of access and backhaul links under half-duplex constraints and non-negligible interference that may arise in dense IAB systems even with high beam directionality. To address the complexity of our formulated MDP, we consider several approximation methods, namely, Qlearning, Monte Carlo Tree Search (MCTS), and genetic algorithms (GAs). Then, we propose a customized version of the GA, which provides the preferred optimality–complexity trade-off and offers a 15% packet delay reduction as compared to the state-of-the-art backpressure algorithm. Index Terms—IAB, millimeter-wave, link scheduling, routing, half-duplex constraint, interference, user dynamics. I. INTRODUCTION A. Research Motivation INTEGRATED Access and Backhaul (IAB) technology proposed by the Third Generation Partnership Project (3GPP) Manuscript received 27 February 2023; revised 10 January 2024 and 21 March 2024; accepted 4 May 2024. Date of publication 21 June 2024; date of current version 17 October 2024. This work was supported in part by Intel Corporation, and in part by the Research Council of Finland (Projects RADIANT, ECONEWS, SOLID, and ALL-ON) . The review of this article was coordinated by Dr. Xiaohu Ge. (Corresponding author: Yekaterina Sadovaya.) Yekaterina Sadovaya and Olga Vikhrova are with Tampere University, 33720 Tampere, Finland (e-mail: yekaterina.sadov[email protected]; olga.vikhrov[email protected]). Wei Mao, Shu-ping Yeh, Omid Semiari, Hosein Nikopour, and Shilpa Talwar are with Intel Corporation, Santa Clara, CA 95054 USA (e-mail: [email protected]; [email protected]; [email protected]; ho- [email protected]; shilpa.talw[email protected]). Sergey Andreev is with Tampere University, 33720 Tampere, Finland, and also with Brno University of Technology, 601 90 Brno, Czech Republic (e-mail: sergey.andree[email protected]). Digital Object Identifier 10.1109/TVT.2024.3409179 in [1] has received substantial attention from both academia and industry as a cost-efficient solution for extending the coverage and improving the performance of future cellular networks operating at mmWave frequencies [2]. Due to offering larger bandwidths than sub-6 GHz systems, mmWave radio is crucial for the fifth generation and beyond (5G/B5G) systems to meet the anticipated traffic growth and more stringent requirements of emerging interactive and immersive applications [3]. However, mmWave links are known to have significantly higher path and penetration losses and are more prone to atmospheric absorption as compared to, e.g., microwave links [4]. Even though the impact of losses can be effectively reduced by using advanced signal processing and multiple-input multiple-output (MIMO) communications to form highly directional links, the resulting coverage is inferior to that of sub-6GHz deployment. Hence, mmWave systems require ultra-dense base station deployments to alleviate coverage gaps caused by blockage and directional transmissions. The straightforward densification by increasing the number of 5G New Radio (NR) nodeBs (gNBs) per square meter is costly and challenging in some locations. Instead, IAB offers rapid and low-cost on-demand network densification by deploying multiple IAB nodes where additional coverage or capacity is needed. IAB nodes are wireless relays interconnected with each other and with a donor gNB (DgNB) over wireless backhaul links. Therefore, any new IAB node can be quickly added to the existing deployment, while the already deployed nodes can be moved to a new location. According to the IAB architecture, which is defined in 3GPP TS 38.401 [5], an IAB node accommodates both distributed unit (DU) and mobile termination (MT) functions as shown in Fig. 1. MT function determines IAB node as a child node that is controlled by the other IAB nodes or donor, while DU function makes IAB node behave as a parent for the other IAB nodes and user equipment (UE). IAB nodes and DgNBs can form directed acyclic graph (DAG) and spanning tree topologies according to 3GPP TR 38.874 [1]. Following the principles of the open radio access network (O-RAN), central unit (CU) and DU can utilize various intelligent microservices (rApps or xApps) implemented at the non-real-time and near-real-time radio access network (RAN) intelligent controllers (RICs) [6] to, e.g., predict traffic demands, optimize topology, manage routes, and allocate resources [7],[8] in IAB networks. While 3GPP specifications consider the possibility of implementing backhauling in out-of-band mode, multiplexing access © 2024 The Authors. This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ 15126 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 73, NO. 10, OCTOBER 2024 Fig. 1. Example IAB network with multi-hop topology [1]. and backhaul links at the same frequency provides attractive cost benefits due to hardware and frequency reuse. This also makes IAB nodes lower in price than conventional relays due to the reuse of most of the 5G access interfaces at the backhaul links [9]. Moreover, IAB systems can significantly improve network capacity and delay performance due to dynamic timedivision duplexing (TDD) configuration, which is enabled by the flexible 5G NR frame pattern structure. The performance of IAB networks is reliant on the frame pattern established by the CU and announced by the donor at the beginning of every frame. This pattern indicates the sequence of uplink (UL) and downlink (DL) slots for the donor in a frame and cannot be changed until the end of this frame. Frame pattern along with user scheduling and routing algorithms provide more detailed instructions for IAB nodes on how time slots can be used to prevent half-duplex mismatch and interference [10]. Despite the promising benefits of the IAB technology, IAB networks are subject to fundamental constraints of wireless multi-hop networks. First, in-band operation introduces several challenges for optimizing resource allocation and link scheduling due to the half-duplex constraint. The latter does not allow IAB nodes to transmit and receive signals simultaneously due to significant self-interference at the node, the cancellation of which is challenging and costly. Second, user throughput and packet delay performance rapidly deteriorates as the number of hops between the donor and users grows [11],[12]. Moreover, UE mobility and traffic demand changes lead to unbalanced traffic across UL and DL transmissions. Therefore, it is essential to provide efficient delay-aware traffic routing and user scheduling solutions for mmWave IAB networks to improve the user-centric performance and balance the load in the network subject to the half-duplex and interference constraints and dynamic UL and DL traffic. Specifically, our work focuses on a joint optimization of the frame pattern, routing, and user allocation in the form of efficient link scheduling that considers delay-sensitive and delay-tolerant user applications. Since the pattern is announced in advance, we operate with a centralized frame-based link scheduling solution in IAB networks under predicted traffic demands. B. Related Works Wireless multi-hop networks have been an active area of research for a few decades [13],[11]. However, due to specific technology limitations and application use cases, not all approaches can be applied to the IAB systems. For example, the complexity of the link scheduling problem in wireless multi-hop networks largely depends on the underlying topology and is NP-hard in general due to a large number of possible link combinations for scheduling. It is worth noting that routing and link scheduling problems are typically addressed separately in past works. For instance, state-of-the-art near-optimal delayed column generation method [14] for solving the link scheduling problem in flow-based wireless multi-hop networks has inspired several data-driven approaches [15],[16] to reduce the size of the link search space for faster and more stable learning of the optimal link scheduling strategy. The work in [17] offers an elegant semi-centralized framework for traffic routing in IAB systems that aims at minimizing end-to-end communication latency. However, it does not optimize user scheduling at IAB nodes and cannot provide delay guarantees. To address the scheduling and routing problems jointly, backpressure routing [18] and the maximum weighted matching (MWM) iterative algorithm for instantaneous link scheduling [19] are widely employed. Even though MWM algorithms are highly attractive as approximate solutions to the NP-hard weighted link scheduling problem due to their simple concept, they require continuous buffer and channel state information updates in every slot, which produces enormous overhead if implemented in real-world systems. Moreover, these algorithms only optimize the throughput performance of the system without considering delay-aware metrics. In addition, their complexity is either polynomial in the number of nodes or, in the best case, linear in the product of the number of nodes and links, which rapidly grows with the increasing network size or the number of communication links. The complexity issues associated with the backpressure and MWM algorithms in IAB systems are tackled by the adoption of data-driven methods [17],[20],[21]. Specifically, reinforcement learning (RL) attracts growing attention due to its ability to learn efficient policies via interaction with the environment when the traffic or channel statistics is unknown [22].The work in [21] utilizes RL to learn the optimal scheduling policy in IAB networks. It integrates a frame-based traffic prediction module to minimize the feedback overhead for online learning. However, the learned policy is sub-optimal and outperforms the backpressure alternative only under some traffic regimes. Several recent works on IAB propose scalable semi-centralized and distributed link scheduling solutions [23],[24],[25], which naturally stem from the backpressure concept and, therefore, focus on the network throughput optimization rather than on the satisfaction of user demands. SADOVAYA et al.: DELAY-AWARE LINK SCHEDULING IN IAB NETWORKS WITH DYNAMIC USER DEMANDS 15127 Fig. 2. Illustration of optimal scheduling and routing solution and a frame pattern allocation that can be derived from it. C. Our Contribution Our work addresses important gaps in the existing research on scheduling and routing in IAB systems. Specifically, the majority of past studies consider routing and user scheduling separately and/or disregard practical system considerations, e.g., half-duplex constraints. On the other hand, the works where these constraints are accounted for focus on the network utility rather than on delay-aware or user-centric metrics. On top of this, past known solutions such as widely-employed backpressure and MWM algorithms encounter implementation challenges because a global control action needs to be computed at every time step [18]. Therefore, our contributions in this paper can be summarized as follows. rWe develop a novel 3GPP-compliant optimization framework that accounts for the specific features of IAB networks with the goal to satisfy diverse user demands without any particular assumption on the traffic model. Specifically, we formulate a new delay-aware link scheduling problem as MDP that accounts for realistic half-duplex constraint, non-negligible interference, and UL and DL directions of communication. rWe propose a practical customized genetic algorithm (GA) that delivers desirable system performance in terms of service satisfaction and packet delay of delay-sensitive flows. It converges to the preferred performance region three times faster than the reference Monte Carlo Tree Search (MCTS) algorithm. Moreover, it improves the packet delay by 15% on average as compared to the baseline backpressure algorithm. rWe assess the performance of IAB systems under a wide range of traffic load, deployment, and topology configurations. Based on these observations, we formulate practical recommendations for link scheduling in IAB networks subject to a given system setup. The rest of this paper is organized as follows. Section II describes the system model, while Section III introduces the problem formulation. Section IV provides details on the RL framework used to overcome the complexity of a given MDP, while Section Voutlines the employed approximate solutions. Essential simulation assumptions and numerical results are discussed in Section VI. Finally, Section VII summarizes this work and mentions its potential extensions. II. SYSTEM MODEL This section outlines the assumptions adopted for modeling a mmWave IAB network. We start by describing network deployment and user traffic dynamics. This is followed by a summary of the channel and antenna modeling procedure. Finally, the interference calculations are explained. A. Topology, Routing, and User Demand Assumptions We consider an IAB network with a single donor, VIAB nodes, and UUEs. The topology is assumed to be given by a graph T={V,E}, where V={0,...,V}represents the set of IAB nodes including the donor and E={(eij)i,j∈V}denotes the backhaul links. We consider two types of topologies, namely, DAG and spanning tree, which can be obtained as explained, e.g., in [26]. In spanning tree topology, each IAB node except the donor can have only one parent, while in DAG topology, IAB nodes can have up to Vpparents. Each UE can generate data flows in UL and DL directions. To address delay requirements of different applications, we assume that UL and DL flows can be categorized into distinct classes of flows based on their sensitivity to packet delay. Without loss of generality, we consider two classes of flows, namely, delaysensitive and delay-tolerant flows. Let Fbe the total number of flows. F1denotes the set of flows with frame-based delay requirements, while F0denotes the set of flows without any specific delay constraints. We let parameter δcontrol the ratio of delay-sensitive and delay-tolerant flows in the system. The classes are assigned randomly, such that |F1|=δF, while1 |F0|=(1−δ)F. Each flow is associated with its source and destination nodes sfand dffrom the joint set of UEs U={1,...,U}and donor node with index 0. Given the network topology T, the number of paths between the source and the destination nodes can be more than one. We let Kndenote the set of flows, which have node n∈Nin their paths. When the number of paths from sf to dfis higher than one, the routing decision for flow fis made dynamically by the nodes depending on the queue backlogs. Demand r∗ fof flow f∈Fis given as the number of packets to be delivered in a particular frame to satisfy the timely throughput requirements. We assume that flow demands (r∗ 1,...,r∗ F)and packet arrivals are known to the controller at the beginning of a frame and can be computed based on the predicted traffic load and perceived packet flow rates. The goal is to find a scheduling and routing strategy that fulfills the flow demands and reduces the delay of delay-sensitive 1.and .represent flooring and ceiling operators, respectively. 15128 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 73, NO. 10, OCTOBER 2024 flows. As explained in Fig. 2, this strategy produces a scheduling pattern, which sets the order of link activations in space and time. B. User Deployment and Communication Model 1) Propagation: We consider the urban macrocell (UMa) channel model as suggested for IAB networks in [1]. Accordingly, UEs are uniformly deployed over the area of interest, while the UE heights are uniformly distributed within interval [1.5,20]m. Let xand ybe the 2D and 3D distances between a UE and an IAB node. A UE may fall into either line-of-sight (LoS) or non-LoS (NLoS) region, thereby experiencing different pathloss conditions [27]. Specifically, the LoS probability in (1) shown at the bottom of this page, depends on the 2D distance xand UE height h, where C(h)=0,h≤13 m, (h−13)1.5 10 ,13 m <h. (3) The path loss LdB(y)for the links in the LoS and NLoS conditions is provided by (2), shown at the bottom of this page, where ωcis the carrier frequency in GHz, hBS denotes the height of an IAB node, and the break-point distance dBP is given by dBP =4(h−1)(hBS −1)ωc,Hz c,(4) where cdenotes the speed of light and the carrier frequency ωc,Hz is given in Hz. For user association, we assume that each UE selects a node from Vwith the maximum reference signal received power (RSRP). Further, large-scale link fading is assumed to be known to the controller at the beginning of a frame and does not change during the frame duration. 2) Antenna and Interference: In our reference IAB deployment, the DgNB and IAB nodes comprise of three sectorized antennas with sufficient spatial separation to limit self-interference [28]. We assume that the beams in the transmit and receive directions of the intended communicating pair are perfectly aligned. Beyond that, we explicitly model antenna radiation patterns as recommended by [27] to evaluate interference, since the beams of interfering transmitters and intended receiver may overlap. An example of interference under a particular scheduling pattern is shown in Fig. 3. For each link in the scheduling pattern, all other links are treated as interfering. According to our antenna model, the antenna radiation pattern is represented as a superposition of element radiation patterns. Fig. 3. Example interfering transmissions and simultaneously activated links at time slot t. Therefore, the values of the half-power beamwidth (HPBW) and antenna gain depend on the number of antenna elements. The radiation pattern A(φij,θ ij)of antenna at node iseen at node jis expressed by A(φij,θ ij)=AE(φij ,θ ij) +10 log10 1+ρNH  m=1 NV  n=1|wmnvmn|2−1, (5) where AE(φij,θ ij)stands for a single antenna element pattern, φij and θij are the horizontal and vertical angular shifts, respectively, wis the weighting factor responsible for the strength of side lobes, vis the phase shift, NHand NVare the numbers of antenna elements in horizontal and vertical planes, and ρis the degree of correlation between the elements. The single antenna element pattern AE(φij,θ ij)is computed as AE(φij,θ ij)=GE−min[−(AEH(φij ) +AEV(θij)),A max],(6) where GEis the gain of a single antenna element, Amax is the front to back ratio, while AEH(φij)and AEV(θij )are the attenuation values in horizontal and vertical planes, correspondingly [27],[29]. The gain in the main transmit direction of the intended communicating pair is G0 ij =A(0,0).(7) PLoS(x)=1,x≤18 m, 18 x+exp(−x 63 )(1−18 x)1+C(h)5 4(x 100 )3exp (−x 150 ),18 m <x. (1) LdB(x)=⎧ ⎪ ⎨ ⎪ ⎩ 28 +22 log10(x)+20 log10(ωc),LoS,10 m ≤x≤dBP , 28 +40 log10(x)+20 log10(ωc)−9log10(dBP )2−(hBS −h)2,LoS,d BP ≤x≤5km, 32.4+30log10(x)+20 log10(ωc),NLoS. (2) SADOVAYA et al.: DELAY-AWARE LINK SCHEDULING IN IAB NETWORKS WITH DYNAMIC USER DEMANDS 15129 We note that the antennas of the main transmitting–receiving pair are directed toward each other. Therefore, the beam misalignment angle equals zero, and the resultant gain in this direction is the best achievable, which is computed via (7). For instance, Fig. 3shows an example link schedule, where UE 1 and UE 3 transmit toward the donor and IAB node 2, and IAB node 1 transmits toward UE 2 and the donor. For instance, let us consider the link between UE 2 and IAB node 1. However, the horizontal and vertical beam misalignments φkj and θkj between the target receiver jand the interfering transmitter kare typically non-zero. For the example deployment in Fig. 3, the link from UE 3 to UE 2 is considered to be an interfering one. Having the coordinates of the transmitter (xk,y k,z k)and the receiver (xj,y j,z j), the direction of arrival can be computed as (xkj,y kj,z kj)=⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ (xj−xk)2 √(xj−xk)2+(yj−yk)2+(zj−zk)2) (yj−yk)2 √(xj−xk)2+(yj−yk)2+(zj−zk)2) (zj−zk)2 √(xj−xk)2+(yj−yk)2+(zj−zk)2). (8) The corresponding angular shifts φkj and θkj can be expressed by converting the Cartesian coordinates in (8) into the spherical ones. Further, these values are utilized for weighting the incoming signals according to their directions of arrival and departure. Therefore, the antenna gain in the interfering direction for a receiving antenna is given by Gkj =A(φkj,θ kj).(9) A similar procedure is performed for the computation of the gain for a transmitted signal. III. PROBLEM FORMULATION We assume that the IAB network operates in slotted time and formulate a scheduling and routing problem for the duration of a frame T.LetQf n(t)be the number of packets of flow fqueued at node n∈N fat time t. The network of interest has n∈N |Kn| of total queue length of different flows across all nodes. Let af ij(t)∈{0,1}be a scheduling decision representing whether the packets of flow fare transmitted over the link from node ito node jat time t. The joint scheduling decision produces a scheduling pattern a(t)=(af ij(t))i,j∈N,f∈F.Dueto the half-duplex constraint, a node cannot transmit and receive packets at the same time, whereas it can receive from or transmit to several nodes. Therefore, the pattern a(t)should comply with the following half-duplex constraint:  f∈F  i∈P(n) af in(t)· f∈F  j∈P(n) af nj(t)=0,n∈V,(10) where P(n)is a set of immediate neighbors to node n. Owing to the multi-beam transmission and reception capabilities at IAB nodes [19], the maximum numbers of simultaneously active outgoing and incoming transmissions are limited by Nbas follows:  f∈F  i∈P(n) af in(t)≤Nb,n∈V,(11)  f∈F  j∈P(n) af nj(t)≤Nb,n∈V.(12) Scheduling pattern a(t)is feasible if constraints (10),(11), and (12) are met. We, thus, denote by Athe set of all feasible scheduling patterns for a given network deployment. Let PTij (a(t)) be the transmit power of node ito node junder the pattern a(t). If node i∈Ntransmits to node jthe packets of only one flow, then it sends them with the maximum transmit power Pi. Otherwise, the power Piis equally distributed across the flows yielding PTij (a(t)) = Pi/j∈N f∈F af ij(t). Let L(y)denote the pathloss (in the liner scale) between the nodes separated by distance y. As we demonstrate in subsection VI-B, for many scheduling patterns a∈A, the crosslink interference is non-negligible [30]. Therefore, the signal-tointerference-plus-noise ratio (SINR) over link (i, j)denoted by Γ(yij,a(t)) is given as follows: Γ(yij,a(t)) = PTij (a(t))G0 ijG0 ji (NW +Ij(a(t)))L(yij),(13) where Nis the thermal noise power spectral density, Wis the system bandwidth, Gij and Gji are the corresponding linear antenna gains at nodes iand jfor the perfectly aligned beams, and Ij(a(t)) stands for the interference power at the receiver j for a given pattern a(t). The latter can be obtained by Ij(a(t)) =  k∈Kj(a(t)) m∈N akm(t)PTkm GkjGjk L(ykj),(14) where Kj(a(t)) is the set of interfering nodes to node jgiven the link scheduling pattern a(t),Gis the antenna gain in the linear scale considering the corresponding horizontal and vertical angular shifts φkj and θkj for the current locations of the nodes. The interference can be computed independently for each node once the pattern a(t)is known. The capacity of link (i, j)in slot texpressed as the number of packets is then Cij(a(t)) = Fl(Wlog2(1+Γ(yij,a(t)))) ,(15) where Flis a function that determines the number of transmitted packets for a chosen modulation and coding scheme [31]. We let bf ij(a(t)) be the amount of data in flow ftransmitted from node ito node jin slot t. The number of transmitted packets is determined by the capacity Cij(a(t)) and the number of packets in the backlog queue Qf i(t), so that only the packets that are in the backlog queue can be transmitted subject to the capacity: bf ij(a(t)) = af ij(t)minQf i(t),C ij(a(t)).(16) The numbers of packets in the queues as a result of the scheduling decision a(t)are given for all f∈F and t∈ {0,...,T −1}by the following: Qf n(t+1)=Qf n(t)+Λ f n(t) + i∈P(n) bf in(a(t)) − j∈P(n) bf nj(a(t)),(17) 15130 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 73, NO. 10, OCTOBER 2024 where Λf n(t)denotes the number of exogenously arrived packets and, therefore, Λf n(t)=0 for all IAB nodes n∈V\{0}except for the donor. The initial system backlog Qf n(0)for n∈N\ {d1,...,d F}follows from the distribution Q0, while Qf df(0)= 0forf∈F. Let rf=Qf df(T)be the sizes of the destination queues for flows f∈F after Tslots, which represent the numbers of delivered packets during a scheduling interval. The difference r∗ f−rfindicates whether a flow demand is satisfied. Consider a case where the initial flow backlog is greater than or equal to r∗ f. The demand of flow fis satisfied if r∗ f−rf≤0 and is assumed to be unfulfilled if r∗ f−rf>0forf∈F. It is also possible that r∗ f−rf<0 if all the packets in the backlog queues of flow fare delivered to the destination within Tslots. We, therefore, require that r∗ f−rfis always greater than 0. If the initial flow backlog is less than r∗ f, the difference r∗ f−rfalways exceeds 0. By minimizing r∗ f−rfover all flows, we aim at satisfying the flow demands, but cannot improve the delay of delay-sensitive flows f∈F 1. To reduce the latter, we introduce binary penalty uf(a(t)), f∈F 1, to prioritize the scheduling of packets of delay-sensitive flows. It serves to impose a penalty if the size of the destination queue Qf df(t)is not equal to the flow demand r∗ fof delay-sensitive flows f∈F 1. The penalty in slot tequals 1 if Qf df(t+1)≤r∗ fand equals 0 otherwise: uf(a(t)) = 0,Q f df(t+1)≥r∗ f, 1,Q f df(t+1)<r ∗ f.(18) We let π=(a(0),...,a(T−1)) be a centralized scheduling and routing strategy formulated as a sequence of scheduling decisions from the set Πof all feasible strategies. Our goal is to find a strategy π∗∈Πthat minimizes the expected demand dissatisfaction max[r∗ f−rf,0]over all flows and improves the delay of delay-sensitive flows. This can be achieved by solving the following optimization problem: Min: π∈Π EπT−1  t=0 f∈F0 uf(a(t)) +  f∈F max[r∗ f−rf,0]2, which is subject to: (10),(11),(12),(16),(17),and (18). (19) IV. REINFORCEMENT LEARNING The problem in (19) represents a finite horizon MDP. The size of Πin the worst case is |A|T. However, the number of practical scheduling patterns in every slot t, which avoid scheduling from empty queues, is usually significantly less than |A|,butremains exponentially high. Therefore, we utilize a single-agent RL approach to find a close approximation for the solution of (19). In this section, we define RL-specific formulations that include states, actions, transition probabilities, and costs. a) States: Let st(Qf i(t))i∈N,f∈F be the state of the MDP at time t. All queues Qf nare finite and bounded by the demand r∗ fin a given frame. The state space Sand its cardinality |S| can be given by S=∪F f=1Sf,Sf=(Qf n)n∈Nf:Qf n=0,...,r∗ f, (20) |S| =(r∗ f+1)K.(21) b) Actions: At the beginning of t∈{0,...,T −1},the MDP agent chooses a feasible action ata(t),at∈A. c) Transition probabilities: Since the arrivals Λf n(t)and large-scale fading are known to the MDP agent and do not change within a frame duration, any transition from state st to state s tafter taking action atis deterministic. Hence, the transition probabilities P(s t|st,a t)=1 if state s tis produced via (16) and (17) from stby taking action at; otherwise, P(s t|st,a t)=0. d) Costs: Let gt(st,a t)and gT(sT)be the cost of taking action atin state stand the cost of being in state sTat the end of the problem horizon, respectively. The cost gt(st,a t)= f∈F0uf(at), while uf(at)is given by (18). The cost of being in state sTafter Tslots gT(sT)=f∈F(max[r∗ f−rf,0])2 represents demand dissatisfaction. The return Rπ(s0)represents the total cost obtained by following the strategy π∈Πfrom state s0and is given by Rπ(s0)=EπT−1  t=0 gt(st,a t)+gT(sT).(22) Minimization of Rπ(s0)is equivalent to the problem in (19) subject to st∈S and at∈A. It is known as shortest path problem [32] and can be solved iteratively through the Bellman equation if the state and action spaces are small enough. It is worth noting that for a given initial state s0there might be several paths with the same cost, i.e., the optimal strategy πis not unique. For deterministic problems, in contrast to stochastic ones, minimizing the cost over admissible actions atin every decision epoch results in the same optimal cost as minimizing over sequences of actions π=(a(0),...,a(T−1)), since the future states and control are determined via dynamic equations. V. APPROXIMATE SOLUTIONS In this section, we describe the algorithms, which can be adopted for solving the formulated MDP for a realistic network size and frame duration. We consider different algorithms to identify their advantages in relation to the addressed problem. A. Q-Learning First, we consider the Q-learning method, which uses a lookup table to find the best action in a given state. The so-called Qtable [33] specifies the value of an action taken in a particular state. The Q-table is initialized with zeros; then, the elements q(st,a t)of the table are iteratively updated as q(st+1,a t+1)=q(st,a t) +α(−g(st,a t)+max aq(st+1,a)−q(st,a t)), (23) SADOVAYA et al.: DELAY-AWARE LINK SCHEDULING IN IAB NETWORKS WITH DYNAMIC USER DEMANDS 15131 Algorithm 1: Q-Learning. Initialize Q-table, α,Ne,T for n=1,...,N edo Reset the environment s0∼S 0 for t=0,...,T −1do Sample action atusing ε-greedy policy Take action atand observe g(st,a t),st+1 if st/∈Q-table then Add q(st,a t)to Q-table end if Update Q-table via (23) end for end for where αis the learning rate. Note that we use negative reward −gt(st,a t), which is defined in Section IV, since the original problem aims at minimizing the expected return. The solution is summarized in Algorithm 1, where Nerefers to the number of training episodes. The learning of a Q-table is executed via the following steps. After the initialization of the table, the learning rate, and the number of training episodes, the initial state s0is drawn from a known distribution S0∈S. At every iteration, the actions are chosen randomly from Aaccording to the ε-greedy policy. Specifically, action at=argmax aq(st,a)is selected with probability 1 −ε, while a random action from Ais selected with probability ε. Then, after the corresponding cost is derived, the Q-table is updated by following (23). The algorithm runs for a fixed number of episodes, each of which is terminated after T steps. In our case, the terminal state corresponds to the queue states Q(T). The time complexity of this method depends on the cardinalities of action and state spaces as O(T|A||S|). Moreover, buffer utilization under this algorithm increases over time as new actions and states are discovered. The use of deep Q-learning (DQL) helps tackle the problem of a growing Q-table. However, the process remains memory-heavy as it requires storing the states and actions in the replay buffer. As the learning agent may not encounter the majority of the states during the learning process, we further consider a Q-learning algorithm with prioritized sweeping that can significantly improve the performance of Q-learning in deterministic environments. B. Q-Learning With Prioritized Sweeping In conventional Q-learning, Q-values are updated in the order of agent experience, i.e., as they are encountered. In contrast, prioritized sweeping updates are based on the importance of the state–action pairs [34]. The respective steps are summarized in Algorithm 2. We introduce Ppriorities for the encountered states and a priority queue PQ to store the most promising states. The priorities are computed via a temporal difference error between the discounted estimated value of the current state–action pair and the value of the next state–action pair added to the reward received. However, even though the priorities are updated for Algorithm 2: Q-Learning with Prioritized Sweeping. Initialize q(s, a),Model(s, a),PQ,θ,∀s∈S, ∀a∈A(s) for n=1,...,N edo st←current non-terminal state Sample action atusing ε-greedy policy Take action at, observe reward g(st,a t)and state st+1 Model(st,a t)←g(st,a t),s t+1 P←|g(st,a t)+γmaxaq(st+1,a)−q(st,a t)| if P>θthen insert st,a tinto PQwith priority P while PQis not empty do st,a t←first(PQueue) g(st,a t),s t+1←Model(st,a t) Update elements of Q-table via (23) for ∀¯s, ¯apredicted to yield st:do ¯g(st,a t)←predicted reward for ¯s, ¯a, st P←|¯g(st,a t)+γmaxaq(st,a)−q(¯s, ¯a)| if P>θthen insert ¯ainto PQwith priority P end for end while end for every state–action pair, only those that are above the threshold θare stored in the priority queue PQ. The next state and reward of each state–action pair above the priority threshold are stored in the Model array. During the Q-table update process, the last state–action pair from the priority queue is used for an update. Prioritized sweeping allows for a more directed search over the problem search space as it calculates the impact of a new state–action pair on all its predecessors and keeps track of only the important ones. The theoretical complexity of the prioritized sweeping scheme is as high as that of the conventional Q-learning method. However, several studies, such as the one in [35], demonstrated empirically that the enhanced algorithm converges faster as compared to the conventional option due to its prioritized search. C. Monte Carlo Tree Search The MCTS [36] scheme seeks the best strategy by combining the tree search method and the sampling technique [37] to build a decision tree from the initial state. In this algorithm, the problem is represented via a graph where states are graph nodes. The initial state S0is named the root node, while a node extending from the root or another node is named a child node. This method has become a state-of-the-art technique for deterministic combinatorial games and problems [38]. The fundamental challenge of balancing exploration and exploitation in MCTS is addressed in the same way as in multi-armed bandit (MAB) problems. The algorithm treats each state of the search tree as a MAB and selects an action that maximizes the upper confidence bound (UCB) heuristics. In particular, the algorithm consists of four main steps: rSelection: At the initial step, all graph weights ˆvare initialized as infinite. Therefore, a child node in a graph is selected randomly. Then, the child node is chosen based 15132 IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 73, NO. 10, OCTOBER 2024 on the maximization of the UCB score, which is given by max aNv(st,a) k=1(−Rπ) Nv(st,a)+CUCBlog(Nv(s0)) Nv(st,a), (24) where Nv(st,a)is the number of times action ahas been selected in state st, while Nv(s0)is the total number of visits, Nv k=1(−Rπ)is the reward accumulated over Nv(st,a) when action ahas been selected in state st, and cUCB is a parameter responsible for the exploration–exploitation trade-off. rExpansion: The search tree is expanded via all possible actions by adding child nodes to the leaf nodes. rRoll-out: From a selected child node, the sequence of actions is chosen randomly at each depth of the tree until the terminal state is reached. Then, for this sequence of actions, an intermediate return is conducted to estimate the performance of the selected child node. rBackpropagation: The reward returned from the previous step is backpropagated all the way up to every node by updating the accumulated rewards, the numbers of visits, and the corresponding UCB values. These steps are repeated as many times as time or computational resources allow. A strategy is formed either after a fixed number of iterations or when a computational limit is reached. The complexity behind a single update of the MCTS algorithm is O(T|A|). On the other hand, the overall complexity of the method depends on the total number of iterations. In turn, the number of iterations is a function of multiple factors, such as, e.g., the initial state and deployment parameters. D. Genetic Algorithm GA represents a policy-based approach inspired by the biological evolution process [39]. It starts with an initial population, where an individual represents a scheduling policy π=(a(0),...,a(T−1)) for all a(t)∈A, while the gene of an individual represents a single pattern a(t)for the time slot t.The fitness score of an individual, thus, corresponds to the expected return Rπ(s0)starting from state s0and following policy π. The size of the population Npop is chosen at the initialization step and does not change. Therefore, the algorithm complexity depends on this parameter as O(TNpop). Further, the memory utilization of GA is more efficient as compared to Q-learning because it depends only on the population size Npop, which remains unchanged throughout the simulation time. The initial population is generated randomly, and the fitness score for every individual is then evaluated. The fitness score of the entire population is equivalent to the best fitness score among its individuals. A new population is obtained from the current one via the following steps: rSelection: At the selection step, Npindividuals with the best fitness score are tagged within the population. These individuals are named parents, while others are named children. Further, two parents with the best fitness score Algorithm 3: Customized Genetic Algorithm. Initialize population of size Npop randomly Evaluate initial population for n=1,...,N edo for i=1,...,N pop/2do Pick two parents with the best fitness score Reproduce Mutate end for for j=Npop/2,...,N pop do Pick an individual Pbwith the best return Rπ Identify flows with satisfied demands Fsin Pb Exclude a∈F sfrom action space A for action a(t)in Pbdo if a(t)∈Aor satisfied flow queue is empty then Compare queues of unsatisfied flows Change a(t) end if end for end for Evaluate population end for are selected from the current population to reproduce at the next step. rReproduction: At the reproduction step, crossover is performed for all pairs of parents to produce offspring. The crossover procedure is executed by selecting a crossover point within the parent sequences and by exchanging their genes beyond that point. The crossover point tof a parent is selected randomly from [0,...,T −1]. rMutation: Offspring individuals can be subject to a mutation, when pattern atat a randomly selected position of policy πis to be changed. Note that the newly produced individuals always account for the half-duplex constraint, because a(t)is selected from the set of actions A. Both crossover and mutation procedures are performed with certain probabilities Pcand Pm, which are set at the initial step of the algorithm execution. The above steps are repeated until the time/computational limit or a given number of iterations is reached. E. Customized Genetic Algorithm Even though GA demonstrates adequate operation in combinatorial search problems, its performance may drop due to the randomized population initialization, selection, crossover, and mutation steps [40],[41]. To overcome this shortcoming, we develop a customized version of the GA for our problem. The pseudo-code of our customized GA is summarized in Algorithm 3. In the modified GA, the population is generated via two different methods. Specifically, the first half of the population follows the rules of the classical GA method, while the other half is produced via a customized approach. At the same time, the best SADOVAYA et al.: DELAY-AWARE LINK SCHEDULING IN IAB NETWORKS WITH DYNAMIC USER DEMANDS 15133 individual is determined at each step. The second half represents a modification of the best individual (scheduling policy) being obtained by executing lines 10-19 in Algorithm 3.Itisworth noting that such a population split offers more diversity and decreases the probability of falling into a local minimum. The complexity of the modified GA version is similar to that of the classical implementation in the worst-case scenario. However, the customized algorithm may converge faster than the basic GA for the problem of interest. This is because the number of iterations that the GA needs to converge is subject to random mutations and crossovers, which may not guarantee reasonable convergence. On the contrary, our customized GA has more control over how the scheduling patterns are updated, because it aims to improve the current schedule as much as possible rather than update the links in a pattern randomly. The links within the scheduling pattern atthat can be changed are selected based on the buffer states. Specifically, for the current best policy, the number of transmitted packets is compared to the target requirements r∗ f. Those links, which contain flows where the requirements were satisfied are considered to be fixed, while all other links can be changed. Note that it is also necessary to compare not only the requirements but also the buffer states of these flows to avoid scheduling a packet transmission from an empty buffer. After identifying the links that can be modified, we reduce the action space by excluding those actions, which involve only ‘satisfied’ flows. Moreover, before an action change, we track the queues of ’unsatisfied’ flows to determine the number of potential changes in policy π needed to satisfy the requirements as well as which flows should be prioritized for the change. In the following section, we present a comparative assessment of the discussed algorithms. VI. NUMERICAL RESULTS A. Simulation Assumptions We consider a large number of IAB network deployments, which results in many different realizations of spanning tree and DAG topologies. In particular, the DgNB is placed at the center or at the edge of the cell, while UEs are uniformly distributed within the cell, and IAB nodes are positioned within the cell by ensuring sufficient distance between each other and the DgNB as recommended in [1]. Examples of the IAB deployments with realistic tree and DAG topologies are given in Fig. 4(a) and (b), respectively. We utilize our custom simulation software written in Python programming language to assess the performance of the considered strategies [42]. The modeling parameters are 3GPPcompliant and can be found in Table II. The parameters of the approximation algorithms are selected empirically, i.e., after evaluation of different values, the preferred ones are chosen. We assume that for the selected numerology, the time slot Δtis 1 ms and it is represented by 14 OFDM symbols. This is a reasonable assumption due to the practical limitations of beamforming. However, one can assume that Δtis equal to the duration of an OFDM symbol or a sequence of OFDM symbols to conduct scheduling with a desired granularity. Fig. 4. Examples of IAB network deployments. (a) Spanning tree topology. (b) DAG topology. Without loss of generality, we assume that Λf n(0)=r∗ fand Λf n(t)=0fort∈[1,...,T −1]and f∈F. The flow demand r∗ fcan either be obtained from real data or sampled as follows. In order to understand the impact of heterogeneous demands on the system performance, we introduce parameter σ∈{0.1,...,0.9,1}that captures how far the flow demands are from the capacity region [19] for a given topology and number of users. Here, σ=0 means that all the demands are within the network capacity region and σ=1 means that each demand exceeds the capacity. For every value of σ, we generate different combinations of flow demands and then average the results of simulation runs collected for each combination. With respect to unseen topologies, the scheduling strategy is updated every frame as the initial state of the MDP S0changes. The latter means that the initial queue backlogs and channel states might be updated. However, all the considered algorithms utilize previously learned statistics and strategy, which facilitates finding a new strategy. Whenever the network deployment changes, one needs to update state space Sand action space A with respect to the new number of IAB nodes, UEs, and network topology before solving the target problem again.