Method and apparatus for facilitating resource pairing using a deep Q-network

A method of determining a sequence of actions includes training a first deep Q-network (DQN); providing a plurality of entries of a first multi-dimensional matrix as input to the DQN, the first matrix representing a first state, each entry of the first matrix representing an action that can be taken in the first state; determining, using the first DQN, a plurality of Q-values for the plurality of entries of the first matrix, respectively; executing a first action, the first action being the action represented by the entry, from among the plurality of entries, for which the first DQN determined the highest Q-value among the plurality of determined Q-values; accumulating a reward based on executing the first action; and transitioning from the first state to a next state in accordance with a first set of rules and the executed first action.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a national phase under 35 U.S.C. § 371 of PCT International Application No. PCT/US2018/24538 which has an International filing date of Mar. 27, 2018, the entire contents of each of which are hereby incorporated by reference.

BACKGROUND

Example embodiments relate generally to methods and apparatuses for determining a sequence of actions, and particularly to using deep Q-network technology to facilitate resource pairing in communications network resource allocation.

2. Related Art

In 5G multi-user MIMO (MU-MIMO), each cell has multiple sub-cells, each with its own antenna array. The scheduler in the cell needs to assign beams to active UEs on a per transmission time interval (TTI) basis. One objective of the scheduler is to assign UEs to beams in such a manner that a desirable or, alternatively, maximum total system throughput is achieved.

SUMMARY

According to at least some example embodiments, a method of determining a sequence of actions includes training a first deep Q-network (DQN); providing a plurality of entries of a first multi-dimensional matrix as input to the DQN, the first matrix representing a first state, each entry of the first matrix representing an action that can be taken in the first state; determining, using the first DQN, a plurality of Q-values for the plurality of entries of the first matrix, respectively; executing a first action, the first action being the action represented by the entry, from among the plurality of entries, for which the first DQN determined the highest Q-value among the plurality of determined Q-values; accumulating a reward based on executing the first action; and transitioning from the first state to a next state in accordance with a first set of rules and the executed first action.

The training of the first DQN may include initializing first weights; randomly selecting a mini-batch of sample states from among a plurality of stored states, each stored state including a plurality of entries corresponding to a plurality of actions; and for each sample state Sjamong the randomly selected mini-batch of sample states determining one or more valid actions of the sample state Sjbased on the first set of rules, generating, using the first DQN having the first weights, one or more first Q-values corresponding, respectively, to the one or more valid actions of the sample state Sj, generating, using a second DQN having second weights, one or more target values corresponding, respectively, to the one or more valid actions of the sample state Sj, and updating the first weights based on the one or more first Q-values and the one or more target values.

Each valid action of the sample state Sjmay be an action that is permitted to be executed in the sample state Sj, in accordance with the first set of rules.

Initializing the first weights may include randomly selecting the first weights.

The method of determining a sequence of actions may further include initializing the second weights by setting the second weights equal to the first weights.

The generating one or more target values may include determining, for each valid action a among A,

yj⁡(a)=[R⁡(a)+γ*maxa′⁢Q⁡(Sj,next⁡(a),a′;θ-)],
where A represents the one or more valid actions of the sample state Sj, yj(a) represents the target value, from among the one or more target values, that corresponds to the valid action a, R(a) represents a reward value corresponding to the valid action a, y represents a discount parameter having a value not less than 0 and not more than 1, Sj,next(a) represents a next state which would result, in accordance with the first set of rules, from executing valid action a with respect to the sample state Sj, θ−represents the second weights of the second DQN, the expression

maxa′Q⁡(Sj,next(a),a′;θ-)
represents a maximum Q-value from among one or more next Q-values generated by the second DQN, and the generating of the one or more next Q-values includes the second DQN generating, for each valid action a′ among one or more valid actions of the next state Sj,next(a), one of the one or more next Q-values. Further, the updating the first weights may performing a batch gradient descent step in the first DQN using the randomly selected mini-batch of samples such that, for each sample Sjof the randomly selected mini-batch of samples, a loss value to minimize=[yj(A)−Q(Sj, A; θ)]2, where yj(A) represents a concatenation of the one or more target values yj(a) generated for each valid action a among the one or more valid actions A, the expression Q(Sj, A; θ) represents the first Q-values, and θ represents the first weights.

The method of determining a sequence of actions may further include iteratively performing each of the providing, determining, executing, accumulating and transitioning steps for each consecutive state until reaching a terminal state, the terminal state being a state for which no valid action exist.

A valid action of a current state may be an action that is permitted to be executed in the current state, in accordance with the first set of rules.

Executing the first action may include assigning resources in a wireless communications network.

For each entry among the plurality of entries of the first matrix, a numerical value of the entry may correspond to a reward associated with executing the action represented by the entry.

According to at least some example embodiments, a method of operating a scheduler in a wireless communications network includes obtaining, at the scheduler, a plurality of metric values, each metric value corresponding to a UE-beam pair, from among a plurality of UE-beam pairs, each UE-beam pair including a UE from among a plurality of UEs and a beam from among a plurality of beams; performing a UE-beam pair selecting operation including, determining, by a deep Q-network (DQN) of the scheduler, based on the plurality of metric values, a plurality of Q-values, the plurality of Q-values corresponding, respectively, to the plurality of UE-beam pairs, and selecting a UE-beam pair from among the plurality of UE-beam pairs based on the plurality of Q-values; and assigning the UE included in the selected UE-beam pair to the beam included in the selected UE-beam pair.

The selecting may include selecting a highest Q-value, from among the plurality of Q-values, as the selected Q-value.

The plurality of metric values may be a plurality of proportional fair (PF) metric values, respectively.

For each PF metric value, from among the plurality of PF metric values, the PF metric value may be a ratio of an instantaneous spectral efficiency of a first UE with respect to a first beam to a throughput of the first UE, the first UE being the UE included in the UE-beam pair to which the PF metric value corresponds, the first beam being the beam included in the UE-beam pair to which the PR metric value corresponds.

The assigning may include the scheduler assigning the UE included in the selected UE-beam pair to the beam included in the selected UE-beam pair for a current transmission time interval (TTI).

The selected UE-beam pair may be one of a plurality of selected UE-beam pairs. The method of a operating scheduler in a wireless communications network may further include generating, by the scheduler, the plurality of the plurality of selected UE-beam pairs by performing the UE-beam pair selecting operation a plurality of times. The assigning may include assigning the UEs included in the plurality of selected UE-beam pairs to the beams included in the plurality of selected UE-beam pairs, respectively, for the current TTI.

According to at least some example embodiments, a method of training a scheduler to perform scheduling in a wireless communications network with respect to a plurality of user equipment (UEs) and a plurality of beams includes randomly selecting a mini-batch of sample UE-beam states from among a plurality of stored UE-beam states, where each stored UE-beam state includes a plurality of UE-beam pairs, and a plurality of metric values corresponding to the plurality of UE-beam pairs, respectively. According to at least some example embodiments, each UE-beam pair includes a UE from among the plurality of UEs and a beam from among the plurality of beams. According to at least some example embodiments, the method of training a scheduler to perform scheduling further includes, for each sample UE-beam state Sjamong the randomly selected mini-batch of sample UE-beam states, determining one or more valid actions of the sample UE-beam state Sjcorresponding, respectively, to one or more valid UE-beam pairs of the UE-beam state Sj, based on first scheduling rules, generating, using a first deep Q-network (DQN) having first weights, one or more first Q-values corresponding, respectively, to the one or more valid actions of the sample UE-beam state Sj, generating, using a second DQN having second weights, one or more target values corresponding, respectively, to the one or more valid actions of the sample UE-beam state Sj, and updating the first weights based on the one or more first Q-values and the one or more target values.

The method of a method of training a scheduler to perform scheduling may further include initializing the first weights by randomly selecting the first weights; and initializing the second weights by setting the second weights equal to the first weights.

For each valid UE-beam pair among the one or more valid UE-beam pairs of the sample UE-beam state Sj, the scheduler may be permitted, in accordance with the first scheduling rules, to assign the UE included in the valid UE-beam pair to the beam included in the valid UE-beam pair for a current transmission time interval (TTI), and for each action among the one or more valid actions of the sample UE-beam state Sj, the action may include the scheduler assigning the UE included in the valid UE-beam to which the action corresponds to the beam included in the valid UE-beam pair to which the action corresponds.

The generating one or more target values may include determining, for each valid action a among A,

yj(a)=[R⁡(a)+γ*maxa′Q⁡(Sj,next,(a),a′;θ-)],
where A represents the one or more valid actions of the sample UE-beam state Sj, yj(a) represents the target value, from among the one or more target values, that corresponds to the valid action a, R(a) represents the metric value corresponding to the valid UE-beam pair to which the valid action a corresponds, y represents a discount parameter having a value not less than 0 and not more than 1, Sj,next(a) represents a next UE-beam state which would result, in accordance with the first scheduling rules, from the scheduler performing valid action a with respect to the sample UE-beam state Sj, θ−represents the second weights of the second DQN, and the expression

maxa′Q⁡(Sj,next(a),a′;θ-)
represents a maximum Q-value from among one or more next Q-values generated by the second DQN. The generating of the one or more next Q-values may include the second DQN generating, for each valid action a′ among one or more valid actions of the next UE-beam state Sj,next(a), one of the one or more next Q-values. The updating the first weights may include performing a batch gradient descent step in the first DQN using the randomly selected mini-batch of UE-beam states such that, for each UE-beam state Sjof the randomly selected mini-batch of UE-beam states, a loss value to minimize=[yj(A)−Q(Sj, A; θ)]2, where yj(A) represents a concatenation of the one or more target values yj(a) generated for each valid action a among the one or more valid actions A, the expression Q(Sj, A; θ) represents the first Q-values, and θ represents the first weights.

According to at least some example embodiments, a scheduler includes memory storing computer-executable instructions; and a processor configured to execute the computer-executable instructions such that the processor is configured to, obtain a plurality of metric values, each metric value corresponding to a UE-beam pair, from among a plurality of UE-beam pairs, each UE-beam pair including a UE from among a plurality of UEs and a beam from among a plurality of beams. According to at least some example embodiments, the processor is further configured to execute the computer-executable instructions such that the processor is configured to perform a UE-beam pair selecting operation including determining, using a deep Q-network (DQN), based on the plurality of metric values, a plurality of Q-values, and selecting a UE-beam pair from among the plurality of UE-beam pairs based on the plurality of Q-values. According to at least some example embodiments, the plurality of Q-values correspond, respectively, to the plurality of UE-beam pairs. According to at least some example embodiments, the processor is further configured to execute the computer-executable instructions such that the processor is configured to assign the UE included in the selected UE-beam pair to the beam included in the selected UE-beam pair.

The processor may be configured to execute the computer-executable instructions such that the selecting includes selecting a highest Q-value, from among the plurality of Q-values, as the selected Q-value.

The processor may be configured to execute the computer-executable instructions such that the plurality of metric values are a plurality of proportional fair (PF) metric values, respectively.

The processor may be configured to execute the computer-executable instructions such that for each PF metric value, from among the plurality of PF metric values, the PF metric value is a ratio of an instantaneous spectral efficiency of a first UE with respect to a first beam to a throughput of the first UE, the first UE being the UE included in the UE-beam pair to which the PF metric value corresponds, the first beam being the beam included in the UE-beam pair to which the PF metric value corresponds.

The processor may be configured to execute the computer-executable instructions such that the assigning includes assigning the UE included in the selected UE-beam pair to the beam included in the selected UE-beam pair for a current transmission time interval (TTI).

The processor may be configured to execute the computer-executable instructions such that the selected UE-beam pair is one of a plurality of selected UE-beam pairs. The processor may be configured to execute the computer-executable instructions such that the processor is further configured to generate, by the scheduler, the plurality of selected UE-beam pairs by performing the UE-beam pair selecting operation a plurality of times. Further, the processor may be configured to execute the computer-executable instructions such that the assigning includes assigning the UEs included in the plurality of selected UE-beam pairs to the beams included in the plurality of selected UE-beam pairs, respectively, for the current TTI.

According to at least some example embodiments, a scheduler includes memory storing computer-executable instructions; and a processor configured to execute the computer-executable instructions such that the processor is configured to randomly select a mini-batch of sample UE-beam states from among a plurality of stored UE-beam states. According to at least some example embodiments, each stored UE-beam state includes a plurality of UE-beam pairs, and a plurality of metric values corresponding to the plurality of UE-beam pairs, respectively, and each UE-beam pair includes a UE from among the plurality of UEs and a beam from among the plurality of beams. According to at least some example embodiments, the processor is further configured to execute the computer-executable instructions such that the processor is configured to, for each sample UE-beam state Sjamong the randomly selected mini-batch of sample UE-beam states, determine one or more valid actions of the sample UE-beam state Sjcorresponding, respectively, to one or more valid UE-beam pairs of the UE-beam state Sj, based on first scheduling rules, generate, using a first deep Q-network (DQN) having first weights, one or more first Q-values corresponding, respectively, to the one or more valid actions of the sample UE-beam state Sj, generate, using a second DQN having second weights, one or more target values corresponding, respectively, to the one or more valid actions of the sample UE-beam state Sj, and update the first weights based on the one or more first Q-values and the one or more target values.

The processor may configured to execute the computer-executable instructions such that the processor is further configured to initialize the first weights by randomly selecting the first weights; and initialize the second weights by setting the second weights equal to the first weights.

The processor is configured to execute the computer-executable instructions such that, for each valid UE-beam pair among the one or more valid UE-beam pairs of the sample UE-beam state Sj, the processor is permitted, in accordance with the first scheduling rules, to assign the UE included in the valid UE-beam pair to the beam included in the valid UE-beam pair for a current transmission time interval (TTI), and for each action among the one or more valid actions of the sample UE-beam state Sj, the action includes the processor assigning the UE included in the valid UE-beam to which the action corresponds to the beam included in the valid UE-beam pair to which the action corresponds.

The processor may be configured to execute the computer-executable instructions such that the generating one or more target values includes determining, for each valid action a among A,

yj(a)=[R⁡(a)+γ*maxa′Q⁡(Sj,next,(a),a′;θ-)],
where A represents the one or more valid actions of the sample UE-beam state Sj, yj(a) represents the target value, from among the one or more target values, that corresponds to the valid action a, R(a) represents the metric value corresponding to the valid UE-beam pair to which the valid action a corresponds, y represents a discount parameter having a value not less than 0 and not more than 1, Sj,next(a) represents a next UE-beam state which would result, in accordance with the first scheduling rules, from the scheduler performing valid action a with respect to the sample UE-beam state Sj, θ−represents the second weights of the second DQN, and the expression

maxa′Q⁡(Sj,next(a),a′;θ-)
represents a maximum Q-value from among one or more next Q-values generated by the second DQN. According to at least some example embodiments, the processor is configured to execute the computer-executable instructions such that the generating of the one or more next Q-values includes the processor using the second DQN to generate, for each valid action a′ among one or more valid actions of the next UE-beam state Sj,next(a), one of the one or more next Q-values. According to at least some example embodiments, the processor is configured to execute the computer-executable instructions such that the updating the first weights includes performing a batch gradient descent step in the first DQN using the randomly selected mini-batch of UE-beam states such that, for each UE-beam state Sjof the randomly selected mini-batch of UE-beam states, a loss value to minimize=[yj(A)−Q(Sj, A; θ)]2, where yj(A) represents a concatenation of the one or more target values yj(a) generated for each valid action a among the one or more valid actions A, the expression Q(Sj, A; θ) represents the first Q-values, and θ represents the first weights.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS

Accordingly, while example embodiments are capable of various modifications and alternative forms, embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit example embodiments to the particular forms disclosed, but on the contrary, example embodiments are to cover all modifications, equivalents, and alternatives falling within the scope of example embodiments. Like numbers refer to like elements throughout the description of the figures. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items.

As used herein, the term mobile terminal may be considered synonymous to, and may hereafter be occasionally referred to, as a user equipment (UE), terminal, mobile terminal, mobile unit, mobile device, mobile station, mobile user, access terminal (AT), subscriber, user, remote station, access terminal, receiver, etc., and may describe a remote user of wireless resources in a wireless communication network. The term base station (BS) may be considered synonymous to and/or referred to as a Node B, evolved Node B (eNB), base transceiver station (BTS), Home eNB (HeNB), access point (AP), etc. and may describe equipment that provides the radio baseband functions for data and/or voice connectivity between a network and one or more users.

Exemplary embodiments are discussed herein as being implemented in a suitable computing environment. Although not required, exemplary embodiments will be described in the general context of computer-executable instructions, such as program modules or functional processes, being executed by one or more computer processors or CPUs. Generally, program modules or functional processes include routines, programs, objects, components, data structures, etc. that performs particular tasks or implement particular abstract data types.

The program modules and functional processes discussed herein may be implemented using existing hardware in existing communication networks. For example, program modules and functional processes discussed herein may be implemented using existing hardware at existing network elements or control nodes (e.g., an e node B (enB) or a radio network controller (RNC)). Such existing hardware may include one or more digital signal processors (DSPs), application-specific-integrated-circuits (ASICs), field programmable gate arrays (FPGAs) computers or the like.

In the following description, illustrative embodiments will be described with reference to acts and symbolic representations of operations (e.g., in the form of flowcharts) that are performed by one or more processors, unless indicated otherwise. As such, it will be understood that such acts and operations, which are at times referred to as being computer-executed, include the manipulation by the processor of electrical signals representing data in a structured form. This manipulation transforms the data or maintains it at locations in the memory system of the computer, which reconfigures or otherwise alters the operation of the computer in a manner well understood by those skilled in the art.

Some real world tasks may be represented in terms of states S and actions A, where each state is associated with one or more available actions, each available action is associated with (i) a corresponding reward value R and (ii) a corresponding transition to a next state (e.g., St→St+1), and attributes of the next state are updated in accordance with a particular set of rules.FIG.1Ais a diagram for explaining an example method of a sequence of actions that will produce a desirable or maximum cumulative reward.

FIG.1Aillustrates an example state Strepresented as a matrix105with entries organized into M columns and N rows. Each entry of the matrix105corresponds to a different action Atthat may be taken in state St. Each entry of the matrix105may have a depth dimension. For example, in the example illustrated inFIG.1A, each entry of the matrix105has a depth value (e.g., d in general) of at least 3, as is illustrated by the three layers of matrix105inFIG.1A. Consequently, in the example illustrated inFIG.1A, an entry of the matrix105corresponds to at least 3 numerical values (i.e., the 3 numerical values associated with the depth dimension at the location of the entry in the matrix105). According to at least some example embodiments, the numerical values associated with each entry in the matrix105may indicate attributes of a particular task state Strepresents. According to at least some example embodiments, the numerical values associated with each entry in the matrix105may be used in accordance with a particular set of rules to calculate a reward value associated with choosing, in state St, to take the action Atto which the entry corresponds. When a task is represented in the manner illustrated inFIG.1A, a general method, according to at least some example embodiments, of determining a sequence of actions that will produce a desirable or maximum cumulative reward may include the steps of Algorithm 1, below. Algorithm 1 is expressed in pseudo code.

O1: Train a Deep Q-network (DQN) (e.g., by performing operations outlined in Algorithm 2, which is discussed in greater detail below).

O2: Pass a current state (e.g., state Stwhich the matrix105represents) as input to the trained DQN to determine a Q-value for each available action Atof the current state.

O3: Select the entry (e.g., an entry of the matrix105representing state St) out of N*M entries from a matrix (e.g., the matrix105) that corresponds to an action Athaving a highest Q-value output by the trained DQN for the current state. Each entry in the matrix has a depth dimension of size d. According to at least some example embodiments, the d numerical values can be viewed as image pixel values.
O4: Based on (St, At), accumulate a reward Rt+1≥0, and form the next state (e.g., state St+1) by following a set of rules. The rules are such that they enable a Markov Decision Process (MDP) based evolution (i.e., {St+1, Rt+1} completely determined by {St, At}).
O5: Find a sequence of actions that corresponds to a desirable or maximum cumulative reward by repeating operations O2-O4 for each consecutive state until reaching a terminal state ST.

Algorithm 1 is explained in greater detail below with reference toFIGS.1B-6and an example scenario in which the task to which Algorithm 1 is applied is a task of a scheduler assigning user equipment (UEs) to beams in a 5G wireless communication network, and each state S may be represented by a matrix that has a depth of 1 and a plurality of entries each of which correspond to an action of assigning UE identified by a row of the entry to a beam identified by the column of the entry. For example, Algorithm 2, which will be discussed in greater detail below, represents an example implementation of step O1 of Algorithm 1; and steps S610, S615 and S625 ofFIG.6, which will be discussed in greater detail below, represent example implementations of steps O2, O3, and O4 of Algorithm 1, respectively.

However, the assignment of UEs to beams is but one example application of the general framework represented by Algorithm 1, and at least some example embodiments are not limited to this one example. According to at least some example embodiments, the general framework represented by Algorithm 1 can be applied for any resource assignment task or other scenario wherein the task or scenario can be framed as one of picking entries from a multi-dimensional matrix (of numerical values) in a sequential manner following a Markovian or semi-Markovian evolution process with the aim of increasing or, alternatively, maximizing cumulative rewards. The idea of viewing the matrix cells as image pixels enables the use of powerful image processing capabilities of neural networks. An example of resource assignment in a wireless communications network will now be discussed with reference toFIGS.1B and2.

FIG.1Bis a diagram for explaining an example of resource assignment in a wireless communications network according to at least some example embodiments.FIG.2is a diagram illustrating an example structure of a scheduler251according to at least some example embodiments. In, for example, a wireless communications network implementing 5G multi-user MIMO (MU-MIMO), each cell has multiple sub-cells, each with its own antenna array. Each cell may include a scheduler. The scheduler251assigns beams to active UEs on a per transmission time interval (TTI) basis. According to at least some example embodiments, each TTI, the scheduler251creates a matrix D, whose (i,j)th entry denotes the proportional fair (PF) metric for UE i on beam j. For example,FIG.1Billustrates first, second and third states110,120, and130of the matrix D. Examples of the scheduler251include any network element or device that performs wireless communications network scheduling functions (e.g., assigning UEs to beams). For example, the scheduler251may be embodied by an e-Node B (eNB) or radio network controller (RNC). The term PF metric may also be referred to, occasionally, in the present disclosure as any of a “metric,” a “metric value,” and a “PF metric value.”

For example, as is illustrated inFIG.1B, the scheduler251may generate the matrix D such that the first state110includes a plurality of entries (1,1)˜(6,4) corresponding, respectively, to a plurality of UE-beam pairs (UE1,beam1)˜(UE6,beam4). As is illustrated inFIG.1B, each entry (i,j) in the first state110includes the PF metric of the corresponding UE-beam pair (UE i,beam j). For example, each entry (i,j) in the first state110includes the PF metric corresponding to UE i being assigned to beam j for a current TTI.

The scheduler may determine each PF metric in the first state110of the matrix D in accordance with known methods. For example, the scheduler251may determine the PF metric for each entry (i,j) of the first state110as the ratio of the instantaneous spectral efficiency of UE i for beam j to the long-term throughput achieved by UE i. The scheduler251uses the determined PF metrics to determine the manner in which UEs (e.g., UE1-UE6) get assigned resources (e.g., beam1-beam4) for the current TTI. For example, in accordance with one example scheduling scheme, the scheduler251attempts to give resources to the set of UEs that have the highest PF metrics.

Further, the scheduler251may follow a set of scheduling rules when assigning resources using matrix D. In the example illustrated inFIG.1B, the scheduler251follows a first scheduling rule requiring that any two scheduled beams be separated by a minimum distance of δ and a second scheduling rule requiring that there is an upper bound on the number of UEs that can be scheduled.

In the example illustrated inFIG.1B, the first UE-beam pair selected by the scheduler251from the first state110for scheduling in the current TTI is (UE3,beam3). The entry in the first state110corresponding to the UE-beam pair (UE3,beam3) is entry (3,3). As is illustrated inFIG.3, the PF metric included in entry (3,3) of the first state110is 35. After selecting a UE-beam pair from the first state110, the scheduler251calculates a cumulative reward based on all the UE-beam pairs the scheduler has selected for the current TTI thus far. Since, at this point, the scheduler251has only selected the UE-beam pair (UE3,beam3), the scheduler calculates the cumulative reward as 35 (i.e., the PF value of the entry (3,3) corresponding to the UE-beam pair (UE3,beam3)).

According to the first and second scheduling rules discussed above, the selection of the UE-beam pair (UE3,beam3) results in the matrix D transitioning from the first state110to the second state120. As is illustrated inFIG.1B, in the second state120, some of the UE-beam pairs (UE1,beam1)˜(UE6,beam4) are barred from being selected due to the requirements of the first and second scheduling rules followed by the scheduler251. InFIG.1B, a UE-beam pair being barred from selection by the scheduler251for a current TTI is indicated by the value of the entry in matrix D corresponding to the barred UE-beam pair being set to 0. As is noted above, in the example shown inFIG.1B, the scheduler251follows first scheduling rule requiring that any two scheduled beams be separated by at least a minimum distance δ. In the example illustrated inFIG.1B, the minimum distance δ=2. Thus, as is illustrated inFIG.1B, in the second state120, UE-beam pairs corresponding to beams2-4become barred from being selected for scheduling during the current TTI because beam3was already selected in the first state101, and the distance between beam3and each of beam2and beam4is 1, which is less than the minimum distance δ=2.

In the example illustrated inFIG.1B, the second UE-beam pair selected by the scheduler251from the second state120for scheduling in the current TTI is (UE5,beam1). The entry in the first state110corresponding to the UE-beam pair (UE5,beam1) is entry (5,1). As is illustrated inFIG.3, the PF metric included in entry (5,1) of the second state120is 40. Thus, after selecting the second UE-beam pair from the second state120, the scheduler251calculates a cumulative reward based on all the UE-beam pairs the scheduler has selected for the current TTI thus far as 75 (i.e., the sum of the PF value of the entry (3,3) corresponding to the UE-beam pair (UE3,beam3) and he PF value of the entry (5,1) corresponding to the UE-beam pair (UE5,beam1)).

According to the first and second scheduling rules discussed above, the selection of the UE-beam pair (UE3,beam3) results in the matrix D transitioning from the second state120to the third state130. As is illustrated inFIG.1B, in the third state130, all of the UE-beam pairs (UE1,beam1)˜(UE6,beam4) are barred from being selected due to the requirements of the first and second scheduling rules followed by the scheduler251. Because no UE-beam pairs are selectable by the scheduler in the third state130, the third state130is determined by the scheduler251to be a terminal state, and the selection of UE-beam pairs for scheduling during the current TTI ends.

Thus, in the example illustrated inFIG.1B, for the current TTI, the scheduler251schedules the two selected beam pairs (UE3,beam3) and (UE5,beam1). In the present disclosure, the act of assigning a UE i to a beam j may be referred to, simply, as scheduling the UE-beam pair (UE i,beam j) or assigning the UE-beam pair (UE i,beam j). Though the example inFIG.1Bshows one possible sequence of actions (i.e., selecting the UE-beam pair (UE3,beam3) first, and then selecting the UE-beam pair (UE5,beam1)), there are several other possible sequences of actions that could have been chosen by the scheduler251and may have led to more desirable results. Thus, it may be advantageous to determine methods for improving or, alternatively, optimizing the process of the scheduler251assigning resources (e.g., assigning UEs to beams) such that a traffic throughput of the cell of the scheduler251is increased or, alternatively, maximized.

An example structure of the scheduler251will be discussed in greater detail below with reference toFIG.2. Example methods for improving the process of assigning resources in a wireless communications network using the scheduler251will be discussed in in greater detail below with reference toFIGS.3-6.

As is noted above,FIG.2is a diagram illustrating an example structure of a scheduler251.

Referring toFIG.2, the scheduler251may include, for example, a data bus259, a transmitting unit252, a receiving unit254, a memory unit256, and a processing unit258.

The transmitting unit252, receiving unit254, memory unit256, and processing unit258may send data to and/or receive data from one another using the data bus259.

The transmitting unit252is a device that includes hardware and any necessary software for transmitting signals including, for example, control signals or data signals via one or more wired and/or wireless connections to one or more other network elements in a wireless communications network.

The receiving unit254is a device that includes hardware and any necessary software for receiving wireless signals including, for example, control signals or data signals via one or more wired and/or wireless connections to one or more other network elements in a wireless communications network.

The memory unit256may be any device capable of storing data including magnetic storage, flash storage, etc.

The processing unit258may be any device capable of processing data including, for example, a processor.

According to at least one example embodiment, any operations described herein, for example with reference to any ofFIGS.1-6, as being performed by a scheduler may be performed by an electronic device having the structure of the scheduler251illustrated inFIG.2. For example, according to at least one example embodiment, the scheduler251may be programmed, in terms of software and/or hardware, to perform any or all of the functions described herein as being performed by a scheduler. Consequently, the scheduler may be embodied as a special purpose computer through software and/or hardware programming.

Examples of the scheduler251being programmed, in terms of software, to perform any or all of the functions described herein as being performed by any of the schedulers described herein will now be discussed below. For example, the memory unit256may store a program including executable instructions corresponding to any or all of the operations described herein with reference toFIGS.1-4as being performed by a scheduler. According to at least one example embodiment, additionally or alternatively to being stored in the memory unit256, the executable instructions may be stored in a computer-readable medium including, for example, an optical disc, flash drive, SD card, etc., and the scheduler251may include hardware for reading data stored on the computer readable-medium. Further, the processing unit258may be a processor configured to perform any or all of the operations described herein with reference toFIGS.1-4as being performed by a scheduler, for example, by reading and executing the executable instructions stored in at least one of the memory unit256and a computer readable storage medium loaded into hardware included in the scheduler251for reading computer-readable mediums.

Examples of the scheduler251being programmed, in terms of hardware, to perform any or all of the functions described herein as being performed by a scheduler will now be discussed below. Additionally or alternatively to executable instructions corresponding to the functions described with reference toFIGS.1-6as being performed by a scheduler being stored in a memory unit or a computer-readable medium as is discussed above, the processing unit258may include a circuit (e.g., an integrated circuit) that has a structural design dedicated to performing any or all of the operations described herein with reference toFIGS.1-6as being performed by a scheduler. For example, the above-referenced circuit included in the processing unit258may be a FPGA or ASIC physically programmed, through specific circuit design, to perform any or all of the operations described with reference toFIGS.1-6as being performed by a scheduler.

As will be discussed in greater detail below with reference toFIGS.3-6, according to at least some example embodiments, the scheduler251may utilize, or benefit from, reinforcement learning techniques in order to improve resource assignment.

FIGS.3and4are diagrams for explaining an example of reinforcement learning according to at least some example embodiments.

FIG.3illustrates an example of a game in which a game board310includes a matrix of boxes, each of which has a different numerical value indicated by a corresponding grayscale value of the box. The game inFIG.3involves an action Atwhich may be, for example, a player throwing a dart305at the board310. The game has rules that dictate both a reward Rt+1and a transition (e.g., from state Stto state St+1) that result from taking certain actions A while the game board310is in certain states S. Further, after taking one or more actions, the game board310may reach a terminal state ST, from which no further actions can be taken.

One way to increase or, alternatively, maximize the terminal or final score for a game such as that illustrated inFIG.3would be to find a desired or, alternatively, optimal policy (π*) that maps states to actions so as to increase or, alternatively, maximize a cumulative return or reward. For example, the game illustrated inFIG.3may be conceptualized as is a finite Markov decision process (MDP) (where {St+1, Rt+1} is determined by {St, At}), for which reinforcement learning techniques can be used.

For example, the cumulative return at time t, Gt, may be defined in accordance with Equation 1:

Gt=∑k=0Tγk⁢Rt+k+1,(Equation⁢1)
where 0≤y≤1 is a discount parameter, T represents a terminal time point, and k is an integral index value.

The optimum action-value function (Q*) may be defined in accordance with Equation 2:
Q*(s,a)=maxπE[Gt|St=s,At=a,π],  (Equation 2)
where π is a policy mapping states to actions—i.e., Q*(s, a) represents a maximum expected return achievable by following any strategy, after seeing state s and taking action a.

An action-value function Qiconverges to Q* using the known Bellman equation as an iterative update, as is illustrated by Equation 3:
Qi+1(s,a)=E[r+ymaxa′Qi(s′,a′)|s,a],  (Equation 3)
where s′ and r are the state and reward after taking action a in state s.

According to at least some example embodiments, by conceptualizing the process of assigning network resources as a game like that illustrated inFIG.3, reinforcement learning (e.g., Q-learning techniques) like those discussed above with reference to Equations 1-3 may be applied to the task of assigning network resources (e.g., assigning UEs to beams in a cell). For example, as is illustrated inFIG.4, the matrix D discussed above with reference toFIG.1Bmay be represented as the game board310discussed above with reference toFIG.3by setting the grayscale values of the boxes in the game board310in accordance with the numerical values of the PF metrics in spatially corresponding boxes (i.e., entries or elements) of the matrix D.

However, even if the matrix D is reinterpreted as the game board310, and the Q-learning techniques discussed above with respect to Equations 1-3 are applied, trying to learn the Q function for every possible state and action of the game board310(i.e., the matrix D) may be prohibitive in terms of time, processing resources and/or memory requirements. Thus, according to at least some example embodiments, neural networks may be used to facilitate the process of determining the Q-functions associated with the state-action pairs associated with the matrix D.

For example, neural networks may be advantageously applied to find features within structured data such as an array or vector of pixel values of an image. Further, Q-learning techniques can be combined with convolutional neural network (CNN) techniques to create a deep Q-network (DQN), as is discussed in Mnih, Volodymyr, et al, “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pgs. 529-533, 2015, doi:10.1038/nature14236, the contents of which are incorporated herein, by reference.

FIG.5illustrates an example structure of a DQN501included in the scheduler251according to at least some example embodiments. As is illustrated inFIG.5, the DQN501may receive a state505and output Q-values555associated with each valid action corresponding to the state505. For example, each valid action is an action corresponding to an assignment of a UE-beam pair that the scheduler251is allowed to perform during the current TTI given the state505of the matrix D and the scheduling rules being followed by the scheduler251. The state505refers to, for example, a matrix D in a particular state. For example, the first, second and third states110,120and130of the matrix D illustrated inFIG.1Bare each examples of the state505which may be input to the DQN501. A particular state of a matrix D (e.g., the first state310of the matrix D illustrated inFIG.1B) may be referred to in the present disclosure, simply, as a “state” (e.g., “the first state310”).

As is illustrated inFIG.5, the DQN501is may be a convolutional neural network (CNN) that may include, for example, a first convolution layer510, a second convolution layer520, a third convolution layer530, a first fully-connected layer540, and, as an output layer, a second fully-connected layer550. In the example illustrated inFIG.5, the first convolution layer510includes five size 6×6 filters, the second convolution layer520includes ten size 3×3 filters, and the third convolution layer530includes ten size 2×2 filters. According to at least some example embodiments, the activation for all hidden layers of the DQN501is the ReLU function and the second fully-connected layer550(whose outputs are the Q values555) has a linear activation function. The structure of DQN501illustrated inFIG.5is an example. According to at least some example embodiments, parameters (e.g., the number of filters in each layer, sizes of the filters, and a number of fully connected nodes in the 4thhidden layer) of the DQN included in the scheduler251may be different than those illustrated inFIG.5, and may be chosen in accordance with the preferences of a designer or operator of the scheduler251. For example, the above-referenced parameters of the DQN501may be chosen based on empirical analysis. A method of utilizing the DQN501of the scheduler251to facilitate the task of assigning UEs to beams will now be discussed in greater detail below with reference toFIG.6.

FIG.6illustrates an example method of operating the scheduler251to assign resources in a wireless communications network according to at least some example embodiments.

In operation S605, the scheduler251obtains a plurality of PF metric values. For example, in operation S605the scheduler251may obtain the plurality of PF metric values in the form of a state S0of a matrix D. According to at least some example embodiments, the state S0obtained in operation S605may be an N×M matrix including N×M PF metric values for N×M UE-beam pairs corresponding to N UEs and M beams, where N and M are positive integers. For example, the first state110inFIG.1Bis an example of the state S0obtained in operation S605. According to at least some example embodiments, the scheduler251may calculate the N×M PF metric values of the state S0in the same manner discussed above with respect toFIG.1B. For example, the scheduler251may calculate the PF metrics of each of the N×M UE-beam pairs (UE i,beam j) represented in the state S0as the ratio of the instantaneous spectral efficiency of UE i for beam j to the long-term throughput achieved by UE i.

In operation S610, the scheduler251determines a plurality of Q-values corresponding to a plurality of UE-beam pairs represented in the state S0obtained in operation S605. For example, the scheduler251may provide the state S0as input to the DQN501included in the scheduler251, and the DQN501may output Q-values corresponding to each of the UE-beam pairs represented in the state S0. For example, each UE-beam pair represented in the state S0corresponds to a potential action A taken by the scheduler251(i.e., the scheduler251assigning the UE-beam pair for a current TTI). Thus, the scheduler251may calculate N×M Q-values (e.g., Q(S0,A0)−Q(S0,ANM-1)) for the N×M actions corresponding to the N×M UE-beam pairs represented in the state S0.

In operation S615, the scheduler251may determine the action A having the highest Q-value amongst the Q-values calculated in operation S610, and execute the determined action. For example if Q(S0,A1) was the highest Q-value amongst all the Q-values determined in operation S610, then, in operation S615, the scheduler251executes action A1 (i.e., the scheduler251assigns, for the current TTI, the UE-beam pair in the state S0that corresponds to the action A1.)

In operation S620, the scheduler251accumulates a current reward. For example, the scheduler251may determine the PF metric value of the UE-beam pair corresponding to the action A executed in operation S620to be the reward for executing the action A, and add the reward to a cumulative total of rewards corresponding to actions previously executed by the scheduler251for the current TTI (i.e., cumulative total of PF metrics of the UE-beam pairs previously assigned by the scheduler251for the current TTI).

In operation S625, the scheduler251transitions state S0to a next state, state S1. According to at least some example embodiments, in operation S625, the scheduler251may transition the state S0to the state S1in accordance with the action A executed in operation S615and the scheduling rules being followed by the scheduler251, for example, in the same manner discussed above with reference toFIG.1Band the transition between the first state110and the second state120.

In operation S630, the scheduler251determines a plurality of Q-values corresponding to a plurality of UE-beam pairs represented in the state S1obtained in operation S625. For example, the scheduler251may provide the state S1as input to the DQN501included in the scheduler251. In response, the DQN501may output Q-values corresponding to each of the UE-beam pairs represented in the state S1, for example.

After operation S630, the scheduler251may determine the action A having the highest Q-value amongst the Q-values calculated in operation S630for the state S1, execute the determined action, and accumulate a current reward associated with the executed action, for example, in the same manner discussed above with respect to operations S615and S620. For example, according to at least some example embodiments, after each transition from a current state to a new state (i.e., the next state), the scheduler251may repeat operations S610-S625for each new state until reaching a terminal state, at which point, the scheduler251may consider the process of scheduling resources (e.g., assigning UEs to beams) to be completed for the current TTI.

Example methods of training the DQN501will now be discussed below with reference to Algorithm 2. Algorithm 2 is expressed in pseudocode representing operations that may be performed, for example, by the scheduler251in order to train the DQN501. Further, according to at least some example embodiments, the DQN501can be trained by a device (e.g., a trainer, computer or server) other than the scheduler251performing operations included in Algorithm 2, and the trained DQN501may be included in the scheduler251after the training.

P3: Fit DQN with samples using greedy selection approach: Qgreedy(S, a)=cumulative reward obtained by taking action a in state S, followed by greedy selection from next state until terminal state reached.

P3′: If not using greedy selection approach (for training speed-up), fit using only penultimate state samples and associated action-rewards as Q values.

P4: Store above samples and several more randomly generated samples in a replay buffer.

P5: Select a random mini-batch of samples from the replay buffer. For each sample Sjin the mini-batch:

P5-1: Pass Sjthrough current network weights (θ) to obtain Q(Sj, A; θ) for all actions a εA.P5-2: Obtain next state Sj,next(a) for each valid action a εA in Sj(i.e., actions with non-zero rewards, R(a)>0).P5-3: For each valid action a εA in Sj, pass Sj,next(a) through a prior (frozen) version of network weights (θ−) to compute a target, yj(a) as:

For non-terminal state Sj,next(a):

For terminal state Sj,next(a):
yj(a)=R(a);

For actions with zero rewards:
yj(a)=0.P5-4: Obtain the target vector yj(A) by concatenating yj(a) for all a εA.
P6Update θ by performing a batch gradient descent step in the DQN using the mini-batch of samples, where for each sample Sj, the loss value to minimize=[yj(A)-Q(Sj, A; θ)]2(or any other suitably chosen loss function).
P7: After several mini-batches of sampling and training, set θ−=θ, and continue with next set of sampling/training.

Referring to Algorithm 2, in step P1, the scheduler251initializes primary weights θ, which are the weights of the DQN501. According to at least some example embodiments, the scheduler251uses random values as the initial values of the primary weights θ.

In step P2, the scheduler the scheduler251sets frozen weights θ−=to primary weights θ.

In step P3, the scheduler fits the DQN501with samples using a greedy selection approach Qgreedy(S, a) such that Qgreedy(S, a) is equal to a cumulative reward obtained by taking action a in state S, followed by greedy selection from next state until the terminal state reached.

Alternatively, in step P3′, in a case where the greedy selection approach is not being used by the scheduler251, the scheduler251may fit the DQN501using only penultimate state (i.e., one state prior to terminal state) samples and associated action-rewards as Q values. Note that in the penultimate state, Q (S, a)=R(a). Once the Q values for the penultimate states are learnt by the DQN501, the DQN501can learn the Q values for the states prior to the penultimate states and so on.

In step P4, the scheduler stores sample states generated in step P3 or P3′ in a replay buffer. According to at least some example embodiments, the replay buffer may be included in the memory unit256of the scheduler251. For example, for each transition from a state Sjto a next state Sj,nextthat occurs in step P3 or P3′, the scheduler251may store both states Sjand Sj,nextas sample states in the replay buffer. In step P4, in addition to storing the samples generated in step P3 or P3′, the scheduler251may also store additional sample states in the replay buffer. For example, a designer or operator of the scheduler251could use knowledge the intended operating environment of the scheduler251to generate several additional example sample states that correspond to the distribution/pattern that would be encountered in the real application of interest. For example, the additional example sample states could be generated so as to capture any correlation pattern that a UE's PF metric is expected see across beams.

In step P5, the scheduler251selects a random mini-batch of samples from the replay buffer and performs, for each sample Sjincluded in the random min-batch, steps P5-1 through P5-6.

In step P5-1, the scheduler251applies the sample state Sjas an input to the DQN501using the current primary weights θ to obtain, as the output of the DQN501, Q-values for all actions a εA (i.e., to obtain Q(Sj, A; θ)).

In step P5-2, the scheduler251obtains the next state Sj,next(a) for each valid action a εA in state Sj, where a valid action a is an action (i.e., assigning a particular UE-beam pair represented in sample state Sj) the scheduler251is allowed to perform in view of the scheduling rules the scheduler251is currently following (e.g., beams assigned for the same TTI must be separated by at least a minimum distance δ=2). For example, valid actions are actions with non-zero rewards, (i.e., R(a)>0, where R(a) represents a reward obtained as a result of performing action a).

In step P5-3, for each valid action a εA in state Sj, the scheduler applies the next state resulting from taking action a, Sj,next(a), to the DQN501using the frozen weights θ−(instead of the primary weights θ) to compute a target yj(a).

In step P5-3, when the next state Sj,next(a) is a non-terminal state, the scheduler251calculates that target yj(a) in accordance with Equation 4 or Equation 5:

The scheduler251may use Equation 4 in step P5-3 when using a greedy selection approach Qgreedy. Otherwise, the scheduler251may use Equation 5.

In step P5-3, when the next state Sj,next(a) is a terminal state, the scheduler251calculates that target yj(a) in accordance with Equation 6:
yj(a)=R(a).  (Equation 6)

In step P5-3, when an action a is an action with 0 rewards (e.g., an action that is impermissible in view of the scheduling rules being followed by the scheduler251, like assigning a UE-beam pair that is less than the minimum distance δ away from a UE-beam pair previously assigned for the same TTI; or no PF value in that beam), the scheduler251calculates that target yj(a) in accordance with Equation 7:
yj(a)=0.  (Equation 7)

In Equations 4 and 5, R(a) represents a reward obtained as a result of performing action a, y represents a discount parameter having a value not less than 0 and not more than 1, and the expression

maxa′Q⁡(Sj,next(a),a′;θ-)
represents a maximum Q-value from among all valid actions a′ that may be performed with respect to the next state Sj,next(a).

In step P5-4, the scheduler251obtains the target vector yj(A) by concatenating yj(a) for all a εA.

In step P6, the scheduler251updates θ by performing a batch gradient descent step in the DQN501using the mini-batch of samples Sj, with a loss value L to minimize being expressed, for example, by Equation 8 (or any other suitably chosen loss function):
L=[yj(A)−Q(S,A;θ)]2(Equation 8)

After several mini-batches of sampling and training, set θ−=θ, and continue with next set of sampling/training.

In step P7, sets the frozen weights θ−=to the current primary weights θ. Step P5-6 may be performed periodically. For example, scheduler251may iteratively perform several cycles of selecting mini-batches of samples Sjand performing steps P5 through P6. Further, every time a threshold number of cycles has been performed or a threshold number of batches of samples Sjhas been processed in accordance with steps P5 through P6, the scheduler251may perform step P7.

Example embodiments being thus described, it will be obvious that embodiments may be varied in many ways. Such variations are not to be regarded as a departure from example embodiments, and all such modifications are intended to be included within the scope of example embodiments.