# US 10,873,412 B2 · System and method for real-time optimized scheduling for network data transmission

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,873,412 B2
- Document ID: US10873412B2
- Status: Granted
- Kind: B2
- Application number: 16/039,486
- Filed: 2018-07-19
- Published: 2019-01-31
- Granted: 2020-12-22
- Earliest claimed: 2017-07-27
- Assignees: Virginia Polytechnic Institute and State University
- Applicants: Virginia Tech Intellectual Properties, Inc.
- Inventors: Yan Huang; Y. Thomas Hou; Yongce Chen
- Web page: https://patentgrep.com/patent/US10873412B2

## CPC

- H04L 1/0003: {by switching between different modulation schemes}
- H04W 72/535: {based on resource usage policies}
- H04L 1/0009: {by adapting the channel coding (H04L1/1812 takes precedence)}
- H04L 1/0015: {characterised by the adaptation strategy}
- H04L 1/0026: {Transmission of channel quality indication}
- H04L 5/003: {Arrangements for allocating sub-channels of the transmission path}
- H04L 5/0053: {Allocation of signalling, i.e. of overhead other than pilot signals}
- H04L 2001/0093: {Point-to-multipoint}
- H04W 72/0453: Resources in frequency domain, e.g. a carrier in FDMA
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

System and method for using a network with base stations to optimally or near-optimally schedule radio resources among the users are disclosed. In certain embodiments the system and method are designed to operate in real-time (such as but not limited to 100 μs) to schedule radio resources in a 5G NR network by solving for an optimal or near-optimal solution to scheduling problem by decomposing it into a number of small and independent sub-problems, selecting a subset of sub-problems and fitting them into a number of parallel processing cores from one or multiple many-core computing devices, and solving for an optimal or near-optimal solution through parallel processing within approximately 100 μs. In other embodiments, the sub-problems are constructed to have a similar mathematical structure. In yet other embodiments, the sub-problems are constructed to each be solved within approximately 10 s of μs.

## Claims

### Claim 1

A system for scheduling resources comprising:
a network, one or more cellular base stations, one or more networked many-core computing devices located at each base station, a plurality of parallel processing cores at the one or more computing devices, wherein each of the one or more cellular base stations finds an optimal or near-optimal solution within approximately 100 μs to a scheduling of resources for a plurality of users in the network by:
decomposing an original problem into a plurality of small and mutually independent sub-problems, wherein the sub-problems are solvable in less than approximately 100 μs;
choosing and generating a subset from the plurality of sub-problems at the one or more computing devices independently and in parallel, wherein the number of generated sub-problems fits the available number of parallel processing cores at the one or more computing devices;
solving each of the generated subset of sub-problems using the parallel processing cores at the one or more computing devices independently and in parallel;
calculating an objective value of each of the solved sub-problems using the parallel processing cores at the one or more computing devices independently and in parallel; and
determining an extreme objective value among all solved sub-problems at the one or more computing devices, wherein the solution to the sub-problem with the extreme objective value is set as the optimal or near-optimal solution, and wherein the said optimal or near-optimal solution is obtained prior to being used for resource scheduling,
wherein the system further comprises consecutive transmission time intervals (TTIs), wherein at each TTI:
a scheduling solution for the next TTI is determined;
operations related to the determination of the scheduling solution for the next TTI are completed, said operations comprising:
transferring input data to the one or more computing devices; computing the optimal or near-optimal solution at the one or more computing devices through parallel processing; and
transferring the optimal or near-optimal solution to its application at the base station;
wherein the base station applies the optimal or near-optimal solution determined in the previous TTI to schedule the transmissions to/from the plurality of users within the TTI;
wherein the input data to the one or more computing devices includes a number of users in the network, an amount of available resources, information from the users' channel quality indication (CQI) reports, and the users' past average data throughput.

### Claim 2 (depends on 1)

The system of claim 1, wherein the resources are radio resources such as resource blocks (RB) comprised of transmissions in time and/or frequency domains and modulation and coding scheme (MCS) used for transmission to/from each user.

### Claim 3 (depends on 1)

The system of claim 1, where the network is a cellular network such as 5G NR, 4G LTE, or 4G LTE-Advanced.

### Claim 4 (depends on 1)

The system of claim 1, where the one or more computing devices are at least one of: a Graphics Processing Unit (GPU), Field-Programmable Gate Array (FPGA), and Application-Specific Integrated Circuit (ASIC).

### Claim 5 (depends on 1)

The system of claim 1, wherein parallel processing cores are from one or more many-core computing devices such as one or more GPUs.

### Claim 6 (depends on 1)

The system of claim 1, wherein the scheduling solution comprises an assignment of values to all variables, such as MCS and RB assignments for the plurality of users.

### Claim 7 (depends on 1)

The system of claim 1, wherein a total processing time for finding the optimal or near-optimal solution meets a real-time requirement of the network.

### Claim 8 (depends on 1)

The system of claim 1, where the optimal or near-optimal) scheduling solution is tied to the outcome of solving a mathematical program such as a mixed-integer linear program (MILP).

### Claim 9 (depends on 1)

The system of claim 1, wherein for the problem decomposition:
each sub-problem is of much smaller size than the original problem;
each sub-problem is generated by fixing a subset of variables in the original problem such as fixing a choice of modulation and coding scheme (MCS) for each user;
the sub-problems are purposefully made to be mutually independent;
the solution to each sub-problem requires the same small number of calculations; and
the solution to each sub-problem meets all the constraints in the original problem.

### Claim 10 (depends on 1)

The system of claim 1, wherein the number of sub-problems to be generated is to be fitted into the total number of parallel processing cores at the one or more computing devices.

### Claim 11 (depends on 10)

The system of claim 10, wherein a sub-set of the number of sub-problems to be generated are chosen from the most promising search space of the original problem.

### Claim 12 (depends on 11)

The system of claim 11, wherein the system employs techniques including intensification to identify the most promising search space and random sampling to generate the sub-problems, wherein:
the intensification technique refers to restricting the selection of values for certain variables in the original problem to a subset of all possible values for the said variables, such as restricting the selection of MCS for each user to a subset of all possible MCSs;
the random sampling technique refers to randomly choosing values for certain variables in the original problem from the subset of values for the said variables after intensification, such as randomly choosing an MCS for each user from the subset of MCSs after intensification subject to a probability distribution such as but not limited to uniform distribution; and
each sub-problem is generated by fixing certain variables in the original problem through random sampling after applying intensification to the original problem.

### Claim 13 (depends on 12)

The system of claim 12, wherein the generation of sub-problems at the one or more computing devices is done independently and in parallel.

### Claim 14 (depends on 1)

The system of claim 1, wherein solving each sub-problem refers to determining the optimal or near-optimal values of the remaining variables in each sub-problem, such as allocating RBs for transmissions to/from the plurality of users.

### Claim 15 (depends on 14)

The system of claim 14, wherein the sub-problems are solved independently and in parallel using the parallel processing cores at the one or more computing devices.

### Claim 16 (depends on 9)

The method of claim 9, wherein K/P sub-problems are generated for each thread block, wherein K represents a total number of sub-problems generated at the one or more computing devices, and P represents the total number of thread blocks at the one or more computing devices.