# Online Self-Organizing Network Control with Time Averaged Weighted Throughput Objective

Authors: Zhicong Zhang; Shuai Li; Xiaohui Yan
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

We study an online multisource multisink queueing network control problem characterized with self-organizing network structure and self-organizing job routing. We decompose the self-organizing queueing network control problem into a series of interrelated Markov Decision Processes and construct a control decision model for them based on the coupled reinforcement learning (RL) architecture. To maximize the mean time averaged weighted throughput of the jobs through the network, we propose a reinforcement learning algorithm with time averaged reward to deal with the control decision model and obtain a control policy integrating the jobs routing selection strategy and the jobs sequencing strategy. Computational experiments verify the learning ability and the effectiveness of the proposed reinforcement learning algorithm applied in the investigated self-organizing network control problem.


---

## Body

## 1. Introduction

Queueing network optimization problems widely exist in the fields of manufacturing, transportation, logistics, computer science, communication, healthcare [1], and so on. With the rapid development of the Internet of Things, large-scale logistics distribution network, wireless sensor network [2–4], new generation wireless communication network, and other network technologies, more and more new network structures and new network optimization problems emerge. Optimization of network control is an important factor to affect the efficiency of network operation.Self-organizing networks are a kind of new queueing network system. In self-organizing networks, each station or node can establish a link with its adjacent stations or nodes, receive jobs from other stations or nodes, and transfer them to other stations or nodes. Due to the complex link relationship of stations or nodes, the paths and the sequence of the jobs to go through the network are very complicated. Consequently, the control problem of this kind of networks is very complicated. In literature, researchers concentrate on the control of multihop network, which is a kind of network with self-organizing characteristic. The research methods of multihop network control mainly include two categories. The first one is to decompose it into a series of single-station queueing problems or tandem queueing network problems [5]. The second kind of methods is to simplify the multihop network control problem into link scheduling problem [6] or queue management problem [7]. The main task of link scheduling is to establish a link between the stations and select the appropriate paths for job transferring. He et al. [8] proposed a load-based scheduling algorithm to optimize the link scheduling between stations so as to achieve the load balance of each station and reduce the degree of paths congestion. Pinheiro et al. [9] studied link scheduling and path selection by fuzzy control. Augusto et al. [10] simultaneously optimized link scheduling and routing planning. Nandiraju et al. [11] studied the problem of restricting the length of transmission path and improved the efficiency of long-path transmission. In order to enlarge the network capacity, Gupta and Shroff [12] optimized link scheduling and path selection by solving the maximum weighted matching problem subject to the K-hop interference constraints. The main task of queue management is to classify the jobs to the job groups and to determine the transmission order of the job groups. Fu and Agrawal [7] focused on the problem of jobs classification in queue management and improved the efficiency by batch processing of the jobs. Nieminen et al. [13] and Wang et al. [14] studied optimization of energy management and queue management in multihop networks. Liu et al. [15] reduced the transmission delay and shortened the queue length by modeling and analysis based on Markov chain. Kim et al. [16] considered the fairness of customer services and improved the efficiency of the network while reducing the difference of customers’ waiting time. Vučević et al. [17] and Zhou et al. [18] used a reinforcement learning (RL) algorithm to optimize queue management that allocates the data packets to the queues.In this paper, we study an online multisource multisink queueing network control problem limited by the queue length. We consider the inherent self-organization characteristic of the queueing network problem, transform the problem into Markov Decision Processes (MDP), and then construct an RL system to deal with them. An optimized control strategy and a global optimized solution are obtained by the proposed RL system. The rest of this paper is organized as follows: we introduce the self-organizing queueing network control problem in Section2, formulate the problem into an RL model in Section 3, present the detailed RL algorithm in Section 4, conduct computational experiments in Section 5, and draw conclusions in Section 6.


## 2. Problem Statement

The online self-organizing network control problem concerned in this paper is described as follows. There arem stations in the network and n types of jobs arrive at the network. Let E={ei∣1≤i≤m} denote the set of stations in the network and let Jj,h(1≤j≤n) denote the hth job of type j. Take the network in Figure 1 as an example. As shown in Figure 1, the self-organizing queueing network is composed of three types of stations. The first type of stations is arrival stations. Each type of jobs has a specific arrival station. The specified arrival station for type j jobs is bj∈Ea(Ea⊂E), where Ea denotes the set of arrival stations. The second type of stations is transfer stations, which receive jobs and send them to other transfer stations or destination stations. The set of transfer stations is denoted by Et={Ni∣1≤i≤mt}, where Ni denotes the ith transfer station, mt denotes the number of transfer stations, and Et⊂E. The third type of stations is destination stations. Each type of jobs has a specific destination station and the jobs of the same type aim to arrive at the same destination station. The specified destination station for type j jobs is dj∈Ed, where Ed(Ed⊂E) denotes the set of destination stations. Once a job is processed by its specified destination station, it passes through the entire network.Figure 1
An example of self-organizing network with multitype stations.Jobs of typej arrive at their arrival station bj following Poisson process with rate parameter λj. The arriving jobs wait in the queue of station bj for transferring. Let Ω(ei)(Ω(ei)⊂E) denote the set of stations visible to station ei. Specifically, each arrival station corresponds to a set of visible transfer stations. Ω(bj)(Ω(bj)⊂Et) denotes the set of transfer stations visible for the arrival station bj of type j jobs. Each transfer station also corresponds to a set of visible stations. Ω(Ni)(Ω(Ni)⊂Et∪Ed) denotes the set of stations visible for transfer station Ni. Ω(Ni) contains one or more transfer stations or destination stations. Transfer station Ni is qualified to transfer the jobs of the types in set J(Ni)(J(Ni)⊆{1,2,…,n}). One station transfers only one job at a time. From the arrival station to the destination station, each job needs to pass through at least one transfer station. Under certain conditions, the arrival station bj(1≤j≤n) can establish a link with transfer station Ni if Ni∈Ω(bj) and then send a type j job to station Ni. The job waits in the queue to be transferred to another station. The arrival station bj(1≤j≤n) cannot send a job to transfer station Ni if Ni∉Ω(bj). Similarly, transfer station Ni can establish a link with station ei if ei∈Ω(Ni), select a job from its queue, and send this job to station ei. If station ei∈Ed, then transfer station Ni sends a type j job to station ei only if ei is the destination station for type j jobs, that is, station dj.There exist a lot of feasible paths for a job from its arrival station to its destination station. Take the network in Figure1 as an example. Assume that the arrival station for type j jobs is station e1 and the destination station for type j jobs is station e6. The sets of visible stations of stations e1~e5 are {e2,e3,e7}, {e4,e5}, {e4,e5,e7}, {e6,e8,e9,e10}, and {e6,e9,e10}, respectively. Thus, many paths are feasible for type j jobs from the arrival station to the destination station, such as e1→e2→e4→e6,e1→e2→e5→e6,e1→e3→e4→e6,and e1→e3→e5→e6.The queue capacity of each transfer station is limited, which is denoted byCq. The maximum number of simultaneous transferring jobs for each station is also limited; that is, the number of jobs being transferred to this station cannot exceed a predetermined quantity CL. Though a station can be linked by more than one upstream station, it is allowed to link to at most one downstream station. In order to establish a link between two stations to send jobs, the following conditions must be met: (1) the downstream station is visible for the upstream station; (2) the number of stations transferring jobs to the downstream station is less than the predetermined maximum number; (3) the queue length of the downstream station has not reached the upper limit.A station is not allowed to send a job to another station if a link is not established between the two stations. An upstream station is allowed to send one or more jobs after establishing a link with a downstream station until it establishes a new link with another downstream station. Assume that a station can only send a job to another station at a time. The time required for establishing a link between two stations is a random variable. Letη(ei,ek) denote the time required for establishing a link between stations ei and ek(1≤i,k≤m), which follows exponential distributed random variable exp⁡(λη(ei,ek)) with parameter λη(ei,ek). The time consumed in transferring a job depends on the station and the job type. The transferring time of a type j job by stations ei is denoted by ti,j, which follows exponential distributed random variable exp⁡(λt(ei,j)) with parameter λt(ei,j).The task of network control is to control the routes and the transferring sequence of the jobs. Based on the dynamic status of the queueing network, each station selects an appropriate job from its queue and sends it to an appropriate transfer station or its destination station. The control objective function is to maximize the time averaged weighted throughput (i.e., the weighted throughput rate) of the jobs across the network, which is defined as(1)max⁡1T∑p=1nTwp,where T is the running time, nT is the total number of jobs of all types passing across the network by time T, and wp(1≤p≤nT) is the weight of the pth job passing through the network.The problem addressed above is of a new queueing network problem with the following characteristics. (1) The first one is that the problem is an online dynamic control problem for multisource multisink networks with limited queue length. (2) The second one is self-organization characteristics of the jobs’ transferring paths. There are multiple kinds of jobs with different destination stations. For arbitrary job, many alternative paths exist from the arrival station to its destination station. The most suitable path is not necessarily the shortest one or the one with the fewest transfer stations. Moreover, the more complex the network structure is, the more flexible the path selection is. Network control needs to be conducted considering the factors such as the global situation, the transferring time of each job on each station, the efficiency of each station, and the length of each station’s queue. (3) The third one is the self-organization characteristics of network structure. The topological structure of the network is complex and may be dynamic; that is, the location and the number of stations and the relationship among the stations may vary over time. The control approach for the queueing network should be able to adapt to the changes of network topology structure.In the following sections, an RL model is constructed to depict the above network control problem and an RL algorithm is proposed to deal with it.


## 3. The Reinforcement Learning Model

To depict the size of the feasible solution space and the difficulty of the self-organizing network control problem, we use a tandem queueing network control problem as an extremely simple example. This tandem queueing network is composed ofm tandem stations (e1,e2,…,em) and n jobs of different types that need to be processed on each station in the order of e1,e2,…,em. Suppose that each station processes only one job at a time and the processing sequences of the jobs on different stations are independent. For each station, there are n! possible permutations of the jobs. Thus the number of feasible solutions to this m-station network control problem is (n!)m. If m=7 and n=4, then (n!)m is an enormous figure much larger than 109. Moreover, the general online self-organizing network control problem is much more complicated than the above tandem queueing network control problem with the same number of stations and job types. Due to the large scale of the self-organizing network, it is difficult to formulate the whole system as a unified model and solve it. We formulate the RL model of the self-organizing queueing network problem described in the previous section. According to the characteristics of the self-organizing queueing network control problem and following the decomposition-association strategy, the whole queueing network is decomposed into a number of closely connected small-scale subnetworks and a Markov Decision Process (MDP) model is constructed for each subnetwork. That is, the whole queueing network control problem is converted into a plurality of interconnected MDP problems. The subnetworks are connected by the coupling mechanism. By using this method, we can enhance the adaptability and robustness of the model and make it more adaptive to the changes of the topology structure of self-organizing networks so as to reduce the size of the problem and keep the essential structure of the original problem.Construct a subnetwork for each station in the self-organizing queueing network. For each station, its corresponding subnetwork is centered on this station and contains its adjacent stations linked with this station. Each subnetwork corresponds to an RL subsystem which is used to solve the MDP model formulating the control problem for this subnetwork. The state transition of an RL subsystem directly causes the state variation of its adjacent RL subsystems, thus the adjacent RL subsystems are coupled in state transition.Reinforcement learning (RL) is a machine learning method proposed to solve large-scale multistage decision problems or Markov Decision Processes with incomplete probability information. In the following we convert the self-organizing queueing network control problems of the subnetworks into RL problems, mainly including representation of states, construction of actions, and definition of the reward function. In this section we also introduce the coupling mechanism of the RL subsystems.


### 3.1. States Representation

State variables describe the primary characteristics of the RL subsystem. Theuth(u=0,1,2,…) state of the kth(1≤k≤m) RL subsystem is represented by vector sk,u, which is composed of state variables and defined as(2)sk,u=jk,u;qj,k,u1≤j≤n;eD,k,u;nE,k,u,where jk,u denotes the type of the job being transferred from the central station of the kth RL subsystem at the uth state (jk,u equals zero if the central station is idle), qj,k,u(1≤j≤n) denotes the number of type j jobs waiting in the queue of the central station of the kth RL subsystem at the uth state, eD,k,u denotes the downstream station to which the central station of the kth RL subsystem is linking at the uth state, and nE,k,u denotes the number of upstream stations linking the central station of the kth RL subsystem at the uth state. The trigger events for state transition are arrival of a job and completion of transferring a job on a station.


### 3.2. Actions

When the central station of an RL subsystem is idle and a trigger event occurs, the RL subsystem selects an action. Since the task of the queueing network control is to control the routes and the transferring sequence of the jobs, an action of an RL subsystem contains two decisions: one decision is to determine which station this central station is going to connect to and the other decision is to select a job from the jobs waiting in its queue to transfer. For thekth subsystem, the number of available actions is ∑ei∈Ω(ek)Ψek,ei, where Ω(ek) denotes the set of stations visible to station ek, Ψ(ek,ei) denotes the set of qualified job types that station ek may select and transfer to station ei, and Ψek,ei denotes the cardinality of set Ψ(ek,ei). For an RL subsystem (e.g., the kth subsystem), where a trigger event occurs, a feasible action for this subsystem is to select station ei to link with and send a type j job if all the following conditions are satisfied: (1) ei∈Ω(ek); that is, station ei is a visible station for station ek; (2) the number of upstream stations currently transferring jobs station ei is less than the predetermined number CL; (3) the queue length of station ei is less than Cq-CL; (4) job type j is a qualified job type for station ek to select and transfer to station ei. Trivially, a null action (i.e., selecting no job) is selected if no job is waiting in the queue of station ek or one of the above conditions is not satisfied.


### 3.3. The Reward Function

The reward function indicates the instant and long-term impact of an action; that is, the immediate reward indicates the instant impact of an action and the average reward indicates the optimization of the objective function value. Thus, the whole RL system receives larger time averaged reward for larger time averaged weighted throughput. Letτk,u denote the time at the uth decision-making epoch of the kth RL subsystem, that is, the time when the state of the kth RL subsystem transfers from sk,u-1 into sk,u. Let r(sk,u,ak,u) denote the reward that the kth RL subsystem selects action ak,u at state sk,u and receives reward at time τk,u+1. Without loss of generality, assume that the central station ek of the kth RL subsystem transfers a type j job during time interval (τk,u,τk,u+1] and completes transferring the job at time τk,u+1; then r(sk,u,ak,u) is defined as(3)rsk,u,ak,u=wjLjek-Lj,2Dj,where wj is the weight of the jth job type, Lj(ek) is the label of the central station ek for the jth job type, Lj,2 is the label of the downstream station to which the type j job just transferred from station ek, and Dj is the length of the shortest path from the arriving station to the destination station of a type j job (i.e., the least amount of flow time for a type j job across the whole network from its arrival station to its destination station). The label of a station for the jth job type is defined as the length of the shortest path from the kth station to the destination station of the jth job type, that is, the least amount of flow time for a type j job from the current station to the destination station. The immediate reward r(sk,u,ak,u) represents the progress of a job’s passing through the network during the time between two state transitions. In the following we show the property of the reward function.Lemma 1.
For a typej job (1≤j≤n), assume that this job attains a transfer station Ni with label Lj(Ni). Whichever path this job attains transfer station Ni through, the accumulated reward R(Ni) of all RL subsystems caused by this job is (4)wjDj-LjNiDj,where wj is the weight of the jth job type and Dj is the length of the shortest path from the arriving station to the destination station of the jth job type.Proof.
Without loss of generality, assume that the job starts from its arrival stationbj and before it attains station Ni, it is transferred successively by transfer stations Ni,1,Ni,2,…,Ni,h. Let Lj(Ni,k)(1≤k≤h) denote the label of station Ni,k for the jth job type. Then the reward caused by the type j job during the process of being transferred from station bj to station Ni,1 is(5)wjLjbj-LjNi,1Dj=wjDj-LjNi,1Dj.
Similarly, the reward caused by the job during the process of being transferred from stationNi,k(1≤k≤h-1) to station Ni,k+1 is(6)wjLjNi,k-LjNi,k+1Dj.
Consequently, the accumulated reward caused by the job during the process of being transferred from stationbj to station Ni is(7)RNi=wjDj-LjNi,1Dj+wjLjNi,1-LjNi,2Dj+wjLjNi,2-LjNi,3Dj+⋯+wjLjNi,h-1-LjNi,hDj+wjLjNi,h-LjDj=wjDj-LjNiDj.
By Lemma1 we obtain the following lemma.Lemma 2.
For a typej job (1≤j≤n), assume that this job attains its destination station dj. Whichever path this job passes through the network from its arrival station to its destination station, the accumulated reward of all RL subsystems caused by this job during the whole process is wj.Proof.
By Lemma1, the accumulated reward caused by this job during the whole process of passing through the network is (8)Rdj=wjDj-LjdjDj,where Lj(dj) denotes the label of station dj. Since dj is the destination station of type j jobs, by the definition of a station’s label we get Lj(dj)=0. Hence,(9)Rdj=wjDj-0Dj=wj.
A state transition takes place when a new job arrives at the network or a job is completely transferred by any station. Without loss of generality, we assume that the sojourn time of any arriving job in the network is finite. Hence, the total number of jobs staying in the network at any time is finite. According to Lemmas1 and 2 we prove the following theorem.Theorem 3.
If there exists a positive integerU such that the total number of jobs staying in the network is less than or equal to U, then maximizing the time averaged weighted throughput of the network (i.e., the control objective function (1)) is equivalent to maximizing the time averaged reward of all RL subsystems over infinite time.Proof.
Assume that the jobs arriving at the network are divided into two setsφ1 and φ2. φ1 is the set of jobs having passed through the network by time T and φ2 is the set of jobs still staying in the network at time T. Let Jp denote the pth arriving job. Thus, according to Lemmas 1 and 2, the accumulated reward of all RL subsystems by time T is(10)RT=∑Jp∈φ1wp+∑Jp∈φ2wpDp-LpDp,where wp is the weight of job Jp, Dp is the length of the shortest path from the arrival station of job Jp to the destination station of job Jp, and Lp denotes the label of the station at which job Jp is at time T. By definition, the time averaged weighted throughput by time T is(11)PT¯=1T∑Jp∈φ1wp.
It follows from (10) and (11) that(12)PT¯=1TRT-∑Jp∈φ2wpDp-LpDp.
Because the total number of jobs staying in the network is less than or equal toU, that is, |φ2|≤U, we have(13)∑Jp∈φ2wpDp-LpDp≤∑Jp∈φ2wp≤Umaxj∈1,2,…,n⁡wj.
It follows from (12) and (13) that(14)1TRT-Umaxj∈1,2,…,n⁡wj≤PT¯≤RTT.
SinceUmaxj∈{1,2,…,n}⁡{wj} is a constant, we have(15)limT→+∞⁡1TRT-Umaxj∈1,2,…,n⁡wj=limT→+∞⁡RTT.
It follows from (14) and (15) that(16)limT→+∞⁡PT¯=limT→+∞⁡RTT.
Consequently, maximizing the time averaged weighted throughput is equivalent to maximizing the time averaged reward over infinite time. This links the long-term average reward of the RL system and the optimization of the objective function value for the network control problem.


### 3.4. The State Transition Mechanism and the Coupling Mechanism

The trigger events for state transition in an RL subsystem are completion of transferring a job to the central station of this subsystem and completion of transferring a job from the central station of this subsystem. Take thekth RL subsystem as an example to illustrate the state transition mechanism. Currently the kth RL subsystem is at the uth decision-making state sk,u. This subsystem takes an action ak,u and it transfers to an interim state sk,u∗ immediately. When a trigger event for the kth RL subsystem takes place, the system transfers to a new decision-making state sk,u+1 and receives a reward ru+1, which is computed due to sk,u and ak,u. The above procedure is repeated until a terminal state is attained; that is, all the jobs reach their destination stations. An episode is a trajectory from the initial state to a terminal state of a schedule horizon. With the states representation defined as (2), the decision process is a Markov Decision Process.An RL subsystem is coupled with another RL subsystem if a link is established between the central stations of these two subsystems. For example, for any two stationsei and ek, if there is a link from ei to ek or from ek to ei, then the two RL subsystems with central stations ei and ek are coupled with each other. The coupling mechanism of the RL subsystems (as shown in Figure 2) mainly contains the following two aspects. (1) The first one being the coupled correlation of the state transitions of coupling RL subsystems. One action in a subsystem can change the state of its corresponding coupling subsystem; that is, the state transition of a subsystem directly causes the variation of state variables of its corresponding coupling subsystem. (2) The second one being broadcast mechanism of reward signals in the coupling RL subsystems and the coupled iteration of state values of RL subsystems.Figure 2
The constitution of the RL architecture.To describe the coupling mechanism more precisely and explain the overlap among subsystems, we give an illustrative example. Suppose thatei is a visible station to station ek and they are the central stations of the kth RL subsystem and the ith RL subsystem. Currently the kth RL subsystem is at the uth decision epoch and station ek is idle. The kth RL subsystem is at the uth decision-making state sk,u and the ith RL subsystem is at the vth state si,v, where sk,u=0;qj,k,u(1≤j≤n);eD,k,u;nE,k,u and si,v=ji,v;qj,i,v(1≤j≤n);eD,i,v;nE,i,v. At this decision epoch, the kth subsystem takes an action ak,u which selects a job of type j∗ waiting in its queue, establishes a link with station ei, and transfers the job to station ei. The kth subsystem transfers to an interim state sk,u∗=j∗;qj,k,u(1≤j<j∗),qj∗,k,u-1,qj,k,u(j∗<j≤n);ei;nE,k,u immediately. The difference of states sk,u∗ and sk,u is that the job type being transferred on station ek is j∗, the number of type j∗ jobs waiting the queue of station ek decreases by one, and the downstream station to which station ek is linked is station ei. The ith subsystem transfers to an interim state si,v∗=ji,v;qj,i,v(1≤j≤n);eD,i,v;nE,i,v+1 immediately. The difference of states si,v∗ and si,v is that the number of upstream stations linking station ei increases by one. When station ek completes transferring the type j∗ job, the kth subsystem receives a reward r(sk,u,ak,u) and it transfers to the next decision-making state sk,u+1=0;qj,k,u(1≤j<j∗),qj∗,k,u-1,qj,k,u(j∗<j≤n);ei;nE,k,u. The ith subsystem transfers to the next decision-making state si,v+1=ji,v;qj,i,v(1≤j<j∗),qj∗,k,u+1,qj,i,v(j∗<j≤n);eD,i,v;nE,i,v+1 simultaneously. For each RL subsystem, the state transition process continues as above until all the jobs reach their destination stations.For thekth RL subsystem, when its central station completes transferring a type j job at the (u+1)th decision epoch, the state value of the kth RL subsystem is updated with its immediate reward r(sk,u,ak,u) following the proposed RL algorithm. The state values of all the subsystems coupled with the kth subsystem are also updated. Assume that the ith subsystem is coupled with the kth subsystem; then the virtual reward, denoted by r(sk,u,ak,u,i), for updating the state value of the ith subsystem is defined as(17)rsk,u,ak,u,i=Dj-tk,jDjrsk,u,ak,u,where Dj is the shortest path from the arrival station to the destination station of the jth job type and tk,j is the transfer time of a type j job from station ek. The detailed computation procedure of the RL algorithm is shown in Section 4.


## 3.1. States Representation

State variables describe the primary characteristics of the RL subsystem. Theuth(u=0,1,2,…) state of the kth(1≤k≤m) RL subsystem is represented by vector sk,u, which is composed of state variables and defined as(2)sk,u=jk,u;qj,k,u1≤j≤n;eD,k,u;nE,k,u,where jk,u denotes the type of the job being transferred from the central station of the kth RL subsystem at the uth state (jk,u equals zero if the central station is idle), qj,k,u(1≤j≤n) denotes the number of type j jobs waiting in the queue of the central station of the kth RL subsystem at the uth state, eD,k,u denotes the downstream station to which the central station of the kth RL subsystem is linking at the uth state, and nE,k,u denotes the number of upstream stations linking the central station of the kth RL subsystem at the uth state. The trigger events for state transition are arrival of a job and completion of transferring a job on a station.


## 3.2. Actions

When the central station of an RL subsystem is idle and a trigger event occurs, the RL subsystem selects an action. Since the task of the queueing network control is to control the routes and the transferring sequence of the jobs, an action of an RL subsystem contains two decisions: one decision is to determine which station this central station is going to connect to and the other decision is to select a job from the jobs waiting in its queue to transfer. For thekth subsystem, the number of available actions is ∑ei∈Ω(ek)Ψek,ei, where Ω(ek) denotes the set of stations visible to station ek, Ψ(ek,ei) denotes the set of qualified job types that station ek may select and transfer to station ei, and Ψek,ei denotes the cardinality of set Ψ(ek,ei). For an RL subsystem (e.g., the kth subsystem), where a trigger event occurs, a feasible action for this subsystem is to select station ei to link with and send a type j job if all the following conditions are satisfied: (1) ei∈Ω(ek); that is, station ei is a visible station for station ek; (2) the number of upstream stations currently transferring jobs station ei is less than the predetermined number CL; (3) the queue length of station ei is less than Cq-CL; (4) job type j is a qualified job type for station ek to select and transfer to station ei. Trivially, a null action (i.e., selecting no job) is selected if no job is waiting in the queue of station ek or one of the above conditions is not satisfied.


## 3.3. The Reward Function

The reward function indicates the instant and long-term impact of an action; that is, the immediate reward indicates the instant impact of an action and the average reward indicates the optimization of the objective function value. Thus, the whole RL system receives larger time averaged reward for larger time averaged weighted throughput. Letτk,u denote the time at the uth decision-making epoch of the kth RL subsystem, that is, the time when the state of the kth RL subsystem transfers from sk,u-1 into sk,u. Let r(sk,u,ak,u) denote the reward that the kth RL subsystem selects action ak,u at state sk,u and receives reward at time τk,u+1. Without loss of generality, assume that the central station ek of the kth RL subsystem transfers a type j job during time interval (τk,u,τk,u+1] and completes transferring the job at time τk,u+1; then r(sk,u,ak,u) is defined as(3)rsk,u,ak,u=wjLjek-Lj,2Dj,where wj is the weight of the jth job type, Lj(ek) is the label of the central station ek for the jth job type, Lj,2 is the label of the downstream station to which the type j job just transferred from station ek, and Dj is the length of the shortest path from the arriving station to the destination station of a type j job (i.e., the least amount of flow time for a type j job across the whole network from its arrival station to its destination station). The label of a station for the jth job type is defined as the length of the shortest path from the kth station to the destination station of the jth job type, that is, the least amount of flow time for a type j job from the current station to the destination station. The immediate reward r(sk,u,ak,u) represents the progress of a job’s passing through the network during the time between two state transitions. In the following we show the property of the reward function.Lemma 1.
For a typej job (1≤j≤n), assume that this job attains a transfer station Ni with label Lj(Ni). Whichever path this job attains transfer station Ni through, the accumulated reward R(Ni) of all RL subsystems caused by this job is (4)wjDj-LjNiDj,where wj is the weight of the jth job type and Dj is the length of the shortest path from the arriving station to the destination station of the jth job type.Proof.
Without loss of generality, assume that the job starts from its arrival stationbj and before it attains station Ni, it is transferred successively by transfer stations Ni,1,Ni,2,…,Ni,h. Let Lj(Ni,k)(1≤k≤h) denote the label of station Ni,k for the jth job type. Then the reward caused by the type j job during the process of being transferred from station bj to station Ni,1 is(5)wjLjbj-LjNi,1Dj=wjDj-LjNi,1Dj.
Similarly, the reward caused by the job during the process of being transferred from stationNi,k(1≤k≤h-1) to station Ni,k+1 is(6)wjLjNi,k-LjNi,k+1Dj.
Consequently, the accumulated reward caused by the job during the process of being transferred from stationbj to station Ni is(7)RNi=wjDj-LjNi,1Dj+wjLjNi,1-LjNi,2Dj+wjLjNi,2-LjNi,3Dj+⋯+wjLjNi,h-1-LjNi,hDj+wjLjNi,h-LjDj=wjDj-LjNiDj.
By Lemma1 we obtain the following lemma.Lemma 2.
For a typej job (1≤j≤n), assume that this job attains its destination station dj. Whichever path this job passes through the network from its arrival station to its destination station, the accumulated reward of all RL subsystems caused by this job during the whole process is wj.Proof.
By Lemma1, the accumulated reward caused by this job during the whole process of passing through the network is (8)Rdj=wjDj-LjdjDj,where Lj(dj) denotes the label of station dj. Since dj is the destination station of type j jobs, by the definition of a station’s label we get Lj(dj)=0. Hence,(9)Rdj=wjDj-0Dj=wj.
A state transition takes place when a new job arrives at the network or a job is completely transferred by any station. Without loss of generality, we assume that the sojourn time of any arriving job in the network is finite. Hence, the total number of jobs staying in the network at any time is finite. According to Lemmas1 and 2 we prove the following theorem.Theorem 3.
If there exists a positive integerU such that the total number of jobs staying in the network is less than or equal to U, then maximizing the time averaged weighted throughput of the network (i.e., the control objective function (1)) is equivalent to maximizing the time averaged reward of all RL subsystems over infinite time.Proof.
Assume that the jobs arriving at the network are divided into two setsφ1 and φ2. φ1 is the set of jobs having passed through the network by time T and φ2 is the set of jobs still staying in the network at time T. Let Jp denote the pth arriving job. Thus, according to Lemmas 1 and 2, the accumulated reward of all RL subsystems by time T is(10)RT=∑Jp∈φ1wp+∑Jp∈φ2wpDp-LpDp,where wp is the weight of job Jp, Dp is the length of the shortest path from the arrival station of job Jp to the destination station of job Jp, and Lp denotes the label of the station at which job Jp is at time T. By definition, the time averaged weighted throughput by time T is(11)PT¯=1T∑Jp∈φ1wp.
It follows from (10) and (11) that(12)PT¯=1TRT-∑Jp∈φ2wpDp-LpDp.
Because the total number of jobs staying in the network is less than or equal toU, that is, |φ2|≤U, we have(13)∑Jp∈φ2wpDp-LpDp≤∑Jp∈φ2wp≤Umaxj∈1,2,…,n⁡wj.
It follows from (12) and (13) that(14)1TRT-Umaxj∈1,2,…,n⁡wj≤PT¯≤RTT.
SinceUmaxj∈{1,2,…,n}⁡{wj} is a constant, we have(15)limT→+∞⁡1TRT-Umaxj∈1,2,…,n⁡wj=limT→+∞⁡RTT.
It follows from (14) and (15) that(16)limT→+∞⁡PT¯=limT→+∞⁡RTT.
Consequently, maximizing the time averaged weighted throughput is equivalent to maximizing the time averaged reward over infinite time. This links the long-term average reward of the RL system and the optimization of the objective function value for the network control problem.


## 3.4. The State Transition Mechanism and the Coupling Mechanism

The trigger events for state transition in an RL subsystem are completion of transferring a job to the central station of this subsystem and completion of transferring a job from the central station of this subsystem. Take thekth RL subsystem as an example to illustrate the state transition mechanism. Currently the kth RL subsystem is at the uth decision-making state sk,u. This subsystem takes an action ak,u and it transfers to an interim state sk,u∗ immediately. When a trigger event for the kth RL subsystem takes place, the system transfers to a new decision-making state sk,u+1 and receives a reward ru+1, which is computed due to sk,u and ak,u. The above procedure is repeated until a terminal state is attained; that is, all the jobs reach their destination stations. An episode is a trajectory from the initial state to a terminal state of a schedule horizon. With the states representation defined as (2), the decision process is a Markov Decision Process.An RL subsystem is coupled with another RL subsystem if a link is established between the central stations of these two subsystems. For example, for any two stationsei and ek, if there is a link from ei to ek or from ek to ei, then the two RL subsystems with central stations ei and ek are coupled with each other. The coupling mechanism of the RL subsystems (as shown in Figure 2) mainly contains the following two aspects. (1) The first one being the coupled correlation of the state transitions of coupling RL subsystems. One action in a subsystem can change the state of its corresponding coupling subsystem; that is, the state transition of a subsystem directly causes the variation of state variables of its corresponding coupling subsystem. (2) The second one being broadcast mechanism of reward signals in the coupling RL subsystems and the coupled iteration of state values of RL subsystems.Figure 2
The constitution of the RL architecture.To describe the coupling mechanism more precisely and explain the overlap among subsystems, we give an illustrative example. Suppose thatei is a visible station to station ek and they are the central stations of the kth RL subsystem and the ith RL subsystem. Currently the kth RL subsystem is at the uth decision epoch and station ek is idle. The kth RL subsystem is at the uth decision-making state sk,u and the ith RL subsystem is at the vth state si,v, where sk,u=0;qj,k,u(1≤j≤n);eD,k,u;nE,k,u and si,v=ji,v;qj,i,v(1≤j≤n);eD,i,v;nE,i,v. At this decision epoch, the kth subsystem takes an action ak,u which selects a job of type j∗ waiting in its queue, establishes a link with station ei, and transfers the job to station ei. The kth subsystem transfers to an interim state sk,u∗=j∗;qj,k,u(1≤j<j∗),qj∗,k,u-1,qj,k,u(j∗<j≤n);ei;nE,k,u immediately. The difference of states sk,u∗ and sk,u is that the job type being transferred on station ek is j∗, the number of type j∗ jobs waiting the queue of station ek decreases by one, and the downstream station to which station ek is linked is station ei. The ith subsystem transfers to an interim state si,v∗=ji,v;qj,i,v(1≤j≤n);eD,i,v;nE,i,v+1 immediately. The difference of states si,v∗ and si,v is that the number of upstream stations linking station ei increases by one. When station ek completes transferring the type j∗ job, the kth subsystem receives a reward r(sk,u,ak,u) and it transfers to the next decision-making state sk,u+1=0;qj,k,u(1≤j<j∗),qj∗,k,u-1,qj,k,u(j∗<j≤n);ei;nE,k,u. The ith subsystem transfers to the next decision-making state si,v+1=ji,v;qj,i,v(1≤j<j∗),qj∗,k,u+1,qj,i,v(j∗<j≤n);eD,i,v;nE,i,v+1 simultaneously. For each RL subsystem, the state transition process continues as above until all the jobs reach their destination stations.For thekth RL subsystem, when its central station completes transferring a type j job at the (u+1)th decision epoch, the state value of the kth RL subsystem is updated with its immediate reward r(sk,u,ak,u) following the proposed RL algorithm. The state values of all the subsystems coupled with the kth subsystem are also updated. Assume that the ith subsystem is coupled with the kth subsystem; then the virtual reward, denoted by r(sk,u,ak,u,i), for updating the state value of the ith subsystem is defined as(17)rsk,u,ak,u,i=Dj-tk,jDjrsk,u,ak,u,where Dj is the shortest path from the arrival station to the destination station of the jth job type and tk,j is the transfer time of a type j job from station ek. The detailed computation procedure of the RL algorithm is shown in Section 4.


## 4. A Reinforcement Learning Algorithm with Time Averaged Reward

The online self-organizing queueing network control problem is converted into an RL problem in the previous section. We apply reinforcement learning to solve the RL problem and useε-greedy policy to balance exploration and exploitation. ε-greedy policy means that the algorithm selects the greedy action with probability 1-ε and selects an available action randomly with probability ε, where ε(0⩽ε⩽1) is usually a small positive number.We propose the following reinforcement learning algorithm (Algorithm4), where K is the number of RL subsystems, Sk denotes the state space of the kth RL subsystem, Vk(sk,u) denotes the value of state sk,u, α is the learning rate for state values, ρk denotes the estimated reward rate of the kth RL subsystem, β is the learning rate for the estimated reward rates, N is the total number of jobs required to pass through the network, and c is the number of jobs currently having passed the network.Algorithm 4 (a reinforcement learning algorithm with time averaged reward for online self-organizing queueing network control problem).
Step  1. For each job type j(1≤j≤n), create a network Gj composed of the stations qualified to transfer type j jobs. For each station ei(1≤i≤m) in network Gj, compute its label Lj(ei).
Step  2. Set parameters α, β, ε, and N to the predetermined values and initialize c to be zero. For each k(1≤k≤K), set u=0 and current time τk,u=0 and initialize ρk to be one. For each k(1≤k≤K), set current state sk,u as the initial state sk,0 and initialize Vk(sk)=1 for all sk(sk∈Sk); that is, initialize the state value function for all states of all RL subsystems.
Step  3. Determine the station where the trigger event occurs (e.g., station ek). Determine the current state sk,u for station ek and the set of available actions for the kth RL subsystem at state sk,u.
Step  4. Select action ak,u based on the current state value Vk(sk,u) of the kth RL subsystem following the ε-greedy control policy.
Step  5. Implement action ak,u and determine the next time τk,u+1, the time at the (u+1)th decision-making epoch of the kth RL subsystem, following the state transition mechanism. Determine the state sk,u+1 at time τk,u+1 and calculate reward r(sk,u,ak,u) by (3).
Step  6. Update the state value Vk(sk,u) as(18)Vksk,u=Vksk,u+αrsk,u,ak,u-ρkτk,u+1-τk,u+maxa′rsk,u+1,a′-ρkτ′-τk,u+1+Vks′-Vksk,u.Update ρk as(19)ρk=ρk+βτk,u+1-τk,ursk,u,ak,u-ρkτk,u+1-τk,u+maxa′⁡rsk,u+1,a′-ρkτ′-τk,u+1+Vks′-maxa⁡rsk,u,a-ρkτ-τk,u+Vks,where a′ denotes an available action which may be taken at state sk,u+1, s′ denotes the state to which if action a′ is taken at state sk,u+1, then the kth subsystem is transferred, τ′ denotes the time when the next state transition takes place if action a′ is taken at state sk,u+1, a denotes an available action which may be taken at state sk,u, s denotes the state to which if action a is takenat state sk,u, then the kth subsystem is transferred, and τ denotes the time when the next state transition takes place if action a is taken at state sk,u.
Step  7. Update the RL subsystems coupled with the kth RL subsystem as follows. For each RL subsystem coupled with the kth RL subsystem (e.g., the ith subsystem at state si,v), compute r(sk,u,ak,u,i) by (17) and then update Vi(si,v) and ρi as(20)Visi,v=Visi,v+α1-ρiτk,u+1-τk,ursk,u,ak,ursk,u,ak,u,i,ρi=ρi+βτk,u+1-τk,u1-ρiτk,u+1-τk,ursk,u,ak,ursk,u,ak,u,i.
Step  8. Set u=u+1 and adjust the current time by τk,u+1 for the kth subsystem. Update the current states of all subsystems following the state transition mechanism.
Step  9. If the trigger event is that a job finishes passing through the network, then c=c+1. If the number of jobs across the network is N, then the algorithm terminates; otherwise go to Step  3.


## 5. Computational Experiments

In this section, we conduct computational experiments to examine the learning ability and the performance of the proposed reinforcement learning algorithm (Algorithm4). We first use a queueing network with four types of jobs as the test bed. A test problem specifies the number of jobs to be scheduled and each problem generates 50 instances. To verify the convergence of the state value function during the learning process, a test problem with 10000 jobs is used for each instance. An instance is the whole process of generating a schedule for the 10000 jobs in an instance from the initial state to the state when all the jobs have passed through the network. The weights of all types of jobs wj(1≤j≤n) are in the range [0.1,1] and the parameters of transferring times λt(ei,j) and link establishing times λη(ei,ek) are in the range [1,10]. The transferring times and link establishing times are exponentially distributed. The parameters of the proposed algorithm are set with α=0.01, β=0.05, ε=0.01, and ρk=1(1≤k≤K). The maximum size of the queues of transfer stations Cq is set to be 5.To investigate the convergence of the state value function, we examine the variation of the state values during the learning process. The experiment results in this section take the average over 50 instances. LetNs,k denote the number of states in the state space of the kth subsystem and Vs denote the mean value of all states. Vs is defined as (21), where Sk denotes the state space of the kth subsystem and Vk(sk) denotes the value of state sk (sk∈Sk). Figure 3 shows the variation of Vs with respect to the number of jobs having crossed the network. When the number of finished jobs is larger than 3000, Vs decreases slowly and gradually converges to −20.53.(21)Vs=1∑k=1KNs,k∑k=1K∑sk∈SkVksk.Figure 3
Variation ofVs with respect to the number of finished jobs.LetVp(sk) denote the value of state sk(sk∈Sk) at the time when the pth job completely passes through the network. Let ADVs denote the average value of the absolution of the difference of values of all states between the two time points when the successive two jobs completely cross the network. For example, at the time when the pth job completely passed through the network, ADVs is defined as(22)ADVs=1∑k=1KNs,k∑k=1K∑sk∈SkVpsk-Vp-1sk.Figure4 shows the variation of ADVs with respect to the number of finished jobs. Although both the curves in Figures 3 and 4 converge asymptotically, the shape of the curve in Figure 4 is not so smooth as Figure 3. When the number of finished jobs is larger than 3000, ADVs is less than 0.2. Figures 3 and 4 show that when the number of finished jobs increases, ADVs asymptotically converges to zero which indicates that the state values are gradually stable.Figure 4
Variation ofADVs with respect to the number of finished jobs.For a given problem, we can draw a “Learning Curve” to examine the learning ability of the proposed reinforcement learning algorithm. In a Learning Curve, the objective function values are averaged over 50 instances. As shown in Figure5, X-coordinate represents the number of finished jobs and y-coordinate represents the time averaged weight throughput from the initial time to the current time. For example, the point (2000,0.196) on the Learning Curve indicates that the weighted throughput rate from the initial time to the time when the 2000th job is finished is 0.196. The Learning Curve increases asymptotically and rapidly in the first 3000 jobs and then fluctuates in the latter jobs. This curve shows that RL system learns quickly through interaction and finds a good policy in the former 3000 jobs. Thereafter, the improvement of the control policy gradually slows down in the latter jobs.Figure 5
The Learning Curve of weighted throughput rate.To validate the adaptability of Algorithm4 for various problems and examine the effectiveness of Algorithm 4, more extensive test problems are also randomly generated and conducted to demonstrate the performance of Algorithm 4. We consider the networks with different topology structures corresponding to the test problems with different numbers of stations (m takes 10, 15, 20, 25, 30, 35, and 40, resp.). For a specific number of stations, the values of the relative arrival intensity index (RAII) is, respectively, 0.50, 0.75, 1.00, 1.50, and 2.00. The RAII index indicates the number of arrival jobs at the arrival stations in these extensive test problems relative to the above test problem. The larger RAII index is, the more jobs arrive at the arrival stations. Each extensive test problem generates 50 instances. We use three approaches, the ε-greedy approach (Algorithm 4), the completely random routing (CRR) approach, and the purely greedy routing (PGR) approach, to solve the test problems. The CRR approach and the PGR approach correspond to ε=1 and ε=0, respectively. Table 1 shows the time averaged weighted throughput (AWT) of the jobs across the network, respectively, obtained by three comparative approaches when 10000 jobs have passed through the network. The experiment results in Table 1 are also averaged over 50 instances. As shown in Table 1, the AWT index increases with respect to the growth of the RAII index. When the RAII index is larger than one, the growth rate of the AWT index is slower than the case that the RAII index is less than one, since high intensity of arrival jobs leads to congestion of the networks. For each test problem, ε-greedy approach obtains larger AWT index than the CRR approach and the PGR approach. Table 2 lists the relative AWT values of the ε-greedy approach and the PGR approach. The relative AWT value of a problem for an approach is defined as the AWT index obtained by this approach divided by the AWT index obtained by the CRR approach.Table 1
The time averaged weighted throughput (AWT) of the extensive test problems.
RAII m 10 15 20 25 30 35 40 0.50 CRR 0.076 0.079 0.091 0.102 0.117 0.131 0.147 PGR 0.089 0.101 0.112 0.127 0.143 0.161 0.175 ε-greedy 0.092 0.104 0.115 0.131 0.147 0.166 0.183  0.75 CRR 0.105 0.117 0.130 0.153 0.174 0.198 0.230 PGR 0.129 0.142 0.165 0.185 0.215 0.242 0.276 ε-greedy 0.134 0.147 0.170 0.192 0.222 0.251 0.286  1.00 CRR 0.171 0.195 0.221 0.258 0.282 0.304 0.338 PGR 0.209 0.248 0.275 0.317 0.348 0.389 0.419 ε-greedy 0.218 0.257 0.284 0.329 0.363 0.403 0.431  1.50 CRR 0.228 0.255 0.285 0.344 0.383 0.428 0.469 PGR 0.285 0.323 0.357 0.424 0.481 0.537 0.597 ε-greedy 0.295 0.335 0.373 0.439 0.502 0.561 0.618  2.00 CRR 0.267 0.296 0.324 0.398 0.446 0.503 0.571 PGR 0.338 0.375 0.415 0.493 0.574 0.642 0.706 ε-greedy 0.352 0.391 0.433 0.511 0.598 0.669 0.735Table 2
The relative AWT value of the three approaches.
RAII m 10 15 20 25 30 35 40 0.50 CRR 1.000 1.000 1.000 1.000 1.000 1.000 1.000 PGR 1.178 1.278 1.226 1.239 1.219 1.229 1.206 ε-greedy 1.212 1.314 1.260 1.280 1.252 1.268 1.241  0.75 CRR 1.000 1.000 1.000 1.000 1.000 1.000 1.000 PGR 1.231 1.215 1.269 1.208 1.234 1.222 1.199 ε-greedy 1.277 1.256 1.310 1.255 1.276 1.268 1.241  1.00 CRR 1.000 1.000 1.000 1.000 1.000 1.000 1.000 PGR 1.218 1.271 1.245 1.230 1.234 1.303 1.266 ε-greedy 1.272 1.318 1.285 1.275 1.287 1.351 1.315  1.50 CRR 1.000 1.000 1.000 1.000 1.000 1.000 1.000 PGR 1.252 1.267 1.256 1.231 1.256 1.255 1.246 ε-greedy 1.296 1.312 1.310 1.275 1.310 1.311 1.292  2.00 CRR 1.000 1.000 1.000 1.000 1.000 1.000 1.000 PGR 1.269 1.268 1.281 1.238 1.286 1.277 1.237 ε-greedy 1.320 1.321 1.336 1.283 1.341 1.330 1.287As shown in Table2, the relative AWT values obtained by the PGR approach range from 1.178 to 1.303 and the relative AWT values obtained by the ε-greedy approach range from 1.212 to 1.351. For the test problems with the RAII index taking 0.50, 0.75, 1.00, 1.50, and 2.00, respectively, the average relative AWT values obtained by the PGR approach are 1.223, 1.226, 1.249, 1.256, and 1.265, respectively, and the average relative AWT values obtained by the ε-greedy approach are 1.262, 1.269, 1.291, 1.305, and 1.316, respectively. Compared with the CRR approach, the PGR approach and the ε-greedy approach improve the weighted throughput rate with an average proportion of 24.4% and 28.8%, respectively. Experiment results show that the ε-greedy approach is superior to both the CRR approach and the PGR approach. Experiment results validate the adaptability and robustness of the proposed algorithm for test problems of various scales and different topology structures. Experiment results also indicate that the reinforcement learning system learns to select an appropriate action on different occasions, links stations and schedules jobs flexibly in online environment, and obtains optimized results.


## 6. Conclusions

We decompose the investigated online self-organizing queueing network control problem with time averaged weighted throughput objective into a series of cross-correlated Markov Decision Processes and convert them into a coupled reinforcement learning model. In the reinforcement learning system, maximizing the time averaged weighted throughput of all jobs across the network is equivalent to maximizing the time averaged reward of all subsystems. Online reinforcement learning algorithm with time averaged reward is adopted to solve the reinforcement learning model and obtains a control policy integrating the jobs routing selection strategy and the jobs sequencing strategy. Computational experiments verify the convergence of the state value function through the learning process and the effectiveness of the proposed algorithm applied in the self-organizing queueing network control problem. In the test problems, the proposed algorithm improves the weighted throughput rate of the networks with a remarkable average proportion through online learning process. The experiment results show that the reinforcement learning system is adaptive to different network topology structures and it learns an optimized policy through interaction with the control process.



---

*Source: 4184805-2018-03-04.xml*