Optimization of over-the-air file distribution for connected cars based upon a heuristic scheduling algorithm

• US 10,332,006 B2
• Filed: 12/15/2016
• Issued: 06/25/2019
• Est. Priority Date: 12/15/2016
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Chen, Jie, Guan, Sichong, Zhao, Wenjie, Bigler, Laurie
• Primary Examiner(s): Bates, Kevin T
• Assistant Examiner(s): Kennedy, Lesa M
• Application Number:
  US15/379,880
• Publication Number:
  US 20180176329A1
• Time in Patent Office: 922 Days
• Field of Search: None
• CPC Class Codes: G06F 8/61 Installation
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04W 4/40 for vehicles, e.g. vehicle-to-pedestrians [V2P]
• CPC Class Codes: H04W 4/50 Service provisioning or reconfiguring
• CPC Class Codes: H04W 8/245 from a network towards a terminal

Abstract

Concepts and technologies disclosed herein are directed to the optimization of over-the-air (“OTA”) file distribution for connected cars based upon a heuristic scheduling algorithm. A schedule provided by the heuristic scheduling algorithm is designed to distribute OTA data flow to connected cars over the network (geographically) and over a scheduling time horizon (timely), and is capable of reducing the negative impact of OTA file updates on overall wireless network performance. This schedule is created based upon historical statistics associated with connected car driving patterns and simulations of connected car-specific OTA traffic over the network. By leveraging connected cars that connect to different cells at different times based upon driving patterns, the heuristic scheduling algorithm is effective in reducing OTA impact on the network.

Claims

1. A method comprising:

initiating, by a processor of a system, execution of a heuristic scheduling algorithm to schedule distribution over-the-air of a file to each connected car of a plurality of connected cars operating in communication with a radio access network;

setting, by the processor of the system via execution of the heuristic scheduling algorithm, a day value equal to zero;

determining, by the processor of the system via execution of the heuristic scheduling algorithm, if a number of unscheduled connected cars of the plurality of connected cars is equal to zero;

when the processor of the system determines via execution of the heuristic scheduling algorithm that the number of unscheduled connected cars of the plurality of connected cars is not equal to zero,

setting, by the processor of the system via execution of the heuristic scheduling algorithm, the day value equal to the day value incremented by one,

setting, by the processor of the system via execution of the heuristic scheduling algorithm, a schedule time value equal to zero, and

setting, by the processor of the system via execution of the heuristic scheduling algorithm, a list of connected car candidates equal to a list of unscheduled connected cars;

sorting, by the processor of the system via execution of the heuristic scheduling algorithm, for the schedule time value, in ascending order, a plurality of cells of the radio access network by a sum of a first set of connected cars connected to a cell of the plurality of cells and a second set of connected cars connected to all neighbor cells of the cell, thereby creating a sorted list of cells comprising a number of sorted cells of the plurality of cells;

selecting, by the processor of the system via execution of the heuristic scheduling algorithm, a first cell from the sorted list of cells;

selecting, by the processor of the system via execution of the heuristic scheduling algorithm, a connected car of the plurality of connected cars that is connected to a fewest number of cells of the plurality of cells during a time between the schedule time value to a sum of the schedule time value and a schedule unit value, and that has a longest connection duration with the first cell;

deleting, by the processor of the system via execution of the heuristic scheduling algorithm, from the sorted list of cells, all cells connected to the connected car and any neighbor cells during the time between the schedule time value to the sum of the schedule time value and the schedule unit value, thereby creating a set of deleted cells;

removing, by the processor of the system via execution of the heuristic scheduling algorithm, all connected cars that are connected to the set of deleted cells during the time between the schedule time value to the sum of the schedule time value and the schedule unit value from the list of connected car candidates;

determining, by the processor of the system via execution of the heuristic scheduling algorithm, if the number of sorted cells in the sorted list of cells is equal to zero;

when the processor of the system determines via execution of the heuristic scheduling algorithm that the number of sorted cells in the sorted list of cells is equal zero, updating, by the processor of the system via execution of the heuristic scheduling algorithm, the schedule time value to be equal to the sum of the schedule time value and the schedule unit value;

determining, by the processor of the system via execution of the heuristic scheduling algorithm, if the schedule time value is equal to an end of the day value; and

when the processor of the system determines via execution of the heuristic scheduling algorithm that the schedule time value is equal to the end of the day value, returning to determining, by the processor of the system via execution of the heuristic scheduling algorithm, if the number of unscheduled connected cars of the plurality of connected cars is equal to zero, and if so, ending execution of the heuristic scheduling algorithm.

2. The method of claim 1, further comprising, when the processor of the system determines via execution of the heuristic scheduling algorithm, that the number of unscheduled connected cars of the plurality of connected cars is equal to zero, ending execution of the heuristic scheduling algorithm.

3. The method of claim 1, further comprising when the processor of the system determines via execution of the heuristic scheduling algorithm, that the number of sorted cells is not equal to zero, selecting, by the processor of the system via execution of the heuristic scheduling algorithm, a next cell from the sorted list of cells.

4. The method of claim 1, wherein the file comprises an update file to a software application or a firmware.

5. The method of claim 1, wherein the file comprises a document file, an image file, an audio file, a video file, or a data file.

6. The method of claim 1, wherein the file comprises an initial release of a software application or a firmware.

7. A computer-readable storage medium comprising computer-executable instructions that, when executed by a processor, causes the processor to perform operations comprising:

initiating execution of a heuristic scheduling algorithm to schedule distribution over-the-air of a file to each connected car of a plurality of connected cars operating in communication with a radio access network;

setting, via execution of the heuristic scheduling algorithm, a day value equal to zero;

determining, via execution of the heuristic scheduling algorithm, if a number of unscheduled connected cars of the plurality of connected cars is equal to zero;

when the processor determines via execution of the heuristic scheduling algorithm that the number of unscheduled connected cars of the plurality of connected cars is not equal to zero,

setting, via execution of the heuristic scheduling algorithm, the day value equal to the day value incremented by one,

setting, via execution of the heuristic scheduling algorithm, a schedule time value equal to zero, and

setting, via execution of the heuristic scheduling algorithm, a list of connected car candidates equal to a list of unscheduled connected cars;

sorting, via execution of the heuristic scheduling algorithm, for the schedule time value, in ascending order, a plurality of cells of the radio access network by a sum of a first set of connected cars connected to a cell of the plurality of cells and a second set of connected cars connected to all neighbor cells of the cell, thereby creating a sorted list of cells comprising a number of sorted cells of the plurality of cells;

selecting, via execution of the heuristic scheduling algorithm, a first cell from the sorted list of cells;

selecting, via execution of the heuristic scheduling algorithm, a connected car of the plurality of connected cars that is connected to a fewest number of cells of the plurality of cells during a time between the schedule time value to a sum of the schedule time value and a schedule unit value, and that has a longest connection duration with the first cell;

deleting, via execution of the heuristic scheduling algorithm, from the sorted list of cells, all cells connected to the connected car and any neighbor cells during the time between the schedule time value to the sum of the schedule time value and the schedule unit value, thereby creating a set of deleted cells;

removing, via execution of the heuristic scheduling algorithm, all connected cars that are connected to the set of deleted cells during the time between the schedule time value to the sum of the schedule time value and the schedule unit value from the list of connected car candidates;

determining, via execution of the heuristic scheduling algorithm, if the number of sorted cells in the sorted list of cells is equal to zero;

when the processor of the system determines via execution of the heuristic scheduling algorithm that the number of sorted cells in the sorted list of cells is equal zero, updating, via execution of the heuristic scheduling algorithm, the schedule time value to be equal to the sum of the schedule time value and the schedule unit value;

determining, via execution of the heuristic scheduling algorithm, if the schedule time value is equal to an end of the day value; and

when the processor of the system determines via execution of the heuristic scheduling algorithm that the schedule time value is equal to the end of the day value, returning to determining, via execution of the heuristic scheduling algorithm, if the number of unscheduled connected cars of the plurality of connected cars is equal to zero, and if so, ending execution of the heuristic scheduling algorithm.

8. The computer-readable storage medium of claim 7, wherein the operations further comprise, when the processor of the system determines via execution of the heuristic scheduling algorithm, that the number of unscheduled connected cars of the plurality of connected cars is equal to zero, ending execution of the heuristic scheduling algorithm.

9. The computer-readable storage medium of claim 7, wherein the operations further comprise, when the processor of the system determines via execution of the heuristic scheduling algorithm, that the number of sorted cells is not equal to zero, selecting, via execution of the heuristic scheduling algorithm, a next cell from the sorted list of cells.

10. The computer-readable storage medium of claim 7, wherein the heuristic scheduling algorithm is based, at least in part, upon a driving pattern for each connected car of the plurality of connected cars.

11. The computer-readable storage medium of claim 10, wherein the heuristic scheduling algorithm is further based, at least in part, upon a network connection pattern for each connected car of the plurality of connected cars.

12. The computer-readable storage medium of claim 11, wherein the heuristic scheduling algorithm balances distribution over-the-air of the file to each connected car of the plurality of connected cars operating in communication with the radio access network among the plurality of cells of the radio access network to minimize a negative impact on resources of the radio access network.

13. A system comprising:

a processor; and

memory that stores instructions that, when executed by the processor, cause the processor to perform operations comprising

initiating execution of a heuristic scheduling algorithm to schedule distribution over-the-air of a file to each connected car of a plurality of connected cars operating in communication with a radio access network,

setting, via execution of the heuristic scheduling algorithm, a day value equal to zero,

determining, via execution of the heuristic scheduling algorithm, if a number of unscheduled connected cars of the plurality of connected cars is equal to zero,

when the processor determines via execution of the heuristic scheduling algorithm that the number of unscheduled connected cars of the plurality of connected cars is not equal to zero,

setting, via execution of the heuristic scheduling algorithm, the day value equal to the day value incremented by one,

setting, via execution of the heuristic scheduling algorithm, a schedule time value equal to zero, and

setting, via execution of the heuristic scheduling algorithm, a list of connected car candidates equal to a list of unscheduled connected cars,

sorting, via execution of the heuristic scheduling algorithm, for the schedule time value, in ascending order, a plurality of cells of the radio access network by a sum of a first set of connected cars connected to a cell of the plurality of cells and a second set of connected cars connected to all neighbor cells of the cell, thereby creating a sorted list of cells comprising a number of sorted cells of the plurality of cells,

selecting, via execution of the heuristic scheduling algorithm, a first cell from the sorted list of cells,

selecting, via execution of the heuristic scheduling algorithm, a connected car of the plurality of connected cars that is connected to a fewest number of cells of the plurality of cells during a time between the schedule time value to a sum of the schedule time value and a schedule unit value, and that has a longest connection duration with the first cell,

deleting, via execution of the heuristic scheduling algorithm, from the sorted list of cells, all cells connected to the connected car and any neighbor cells during the time between the schedule time value to the sum of the schedule time value and the schedule unit value, thereby creating a set of deleted cells,

removing, via execution of the heuristic scheduling algorithm, all connected cars that are connected to the set of deleted cells during the time between the schedule time value to the sum of the schedule time value and the schedule unit value from the list of connected car candidates,

determining, via execution of the heuristic scheduling algorithm, if the number of sorted cells in the sorted list of cells is equal to zero,

when the processor of the system determines via execution of the heuristic scheduling algorithm that the number of sorted cells in the sorted list of cells is equal zero, updating, via execution of the heuristic scheduling algorithm, the schedule time value to be equal to the sum of the schedule time value and the schedule unit value,

determining, via execution of the heuristic scheduling algorithm, if the schedule time value is equal to an end of the day value, and

when the processor of the system determines via execution of the heuristic scheduling algorithm that the schedule time value is equal to the end of the day value, returning to determining, via execution of the heuristic scheduling algorithm, if the number of unscheduled connected cars of the plurality of connected cars is equal to zero, and if so, ending execution of the heuristic scheduling algorithm.

14. The system of claim 13, wherein the operations further comprise, when the processor of the system determines via execution of the heuristic scheduling algorithm, that the number of unscheduled connected cars of the plurality of connected cars is equal to zero, ending execution of the heuristic scheduling algorithm.

15. The system of claim 13, wherein the operations further comprise, when the processor of the system determines via execution of the heuristic scheduling algorithm, that the number of sorted cells is not equal to zero, selecting, via execution of the heuristic scheduling algorithm, a next cell from the sorted list of cells.

16. The system of claim 13, wherein the heuristic scheduling algorithm is based, at least in part, upon a driving pattern for each connected car of the plurality of connected cars.

17. The system of claim 16, wherein the heuristic scheduling algorithm is further based, at least in part, upon a network connection pattern for each connected car of the plurality of connected cars.

18. The system of claim 17, wherein the heuristic scheduling algorithm balances distribution over-the-air of the file to each connected car of the plurality of connected cars operating in communication with the radio access network among the plurality of cells of the radio access network.

19. The system of claim 18, wherein the heuristic scheduling algorithm minimizes a negative impact on resources of the radio access network.

20. The system of claim 19, further comprising simulating the negative impact on the resources of the radio access network based upon output of the heuristic scheduling algorithm.