Cellular backhaul coverage algorithms

Patent metadata

Field	Value
Publication number	US-9986441-B2
Application number	US-201715719262-A
Country	US
Kind code	B2
Filing date	Sep 28, 2017
Priority date	Oct 12, 2015
Publication date	May 29, 2018
Grant date	May 29, 2018

Abstract

Systems and methods for designing cellular backhaul networks are disclosed. The system can include an Adaptive Graph Minimum Spanning Tree (AG-MST) algorithm to identify and connect stranded cellular sites at minimum cost. The system can compare pending bids for new connections such as, for example, new microwave or fiber optic links at stranded sites to provide new connectivity. The system can design a network that connects the maximum number of stranded sites at the minimum average cost per site.

First claim

The invention claimed is:

1. One or more non-transitory computer-readable media storing computer-executable instructions that, when executed on one or more processors, cause the one or more processors to perform acts comprising:
identifying stranded sites in a cellular communication system;
creating a stranded site cluster comprising a mesh network graph between stranded sites and relay sites for a portion of a network;
updating weights for each vertex and edge of the mesh network graph for which there is an associated bid cost;
selecting a first potential starting point in the stranded site cluster;
updating the mesh network graph based on the selection of the first potential starting point;
identifying a first, minimum weight spanning tree, solution for the first potential starting point, the first solution representing a first average cost per stranded site;
selecting a second potential starting point in the stranded site cluster;
updating the mesh network graph based on the selection of the second potential starting point;
identifying a second, minimum weight spanning tree, solution for the second potential starting point, the second solution representing a second average cost per stranded site; and
discarding the first solution at least partially in response to determining that the second average cost per stranded site is lower than the first average cost per stranded site.

2. The one or more non-transitory computer-readable media of claim 1 , the acts further comprising:
determining that each microwave link capacity in the first solution is equal to, or larger than, an aggregated site capacity; and
determining that the end-to-end backhaul availability is equal to or larger than the minimum backhaul availability threshold.

3. The one or more non-transitory computer-readable media of claim 1 ,
wherein updating the mesh network graph based on the selection of the first potential starting point comprises setting weights of the potential starting points different than the first potential starting point to zero and removing stranded sites and relay sites that do not have bids to connect them to the first potential starting point.

4. The one or more non-transitory computer-readable media of claim 1 , wherein a particular stranded site being associated with a bid to connect it via fiber to an alternative access vendor (AAV) or that is an AAV site already connected to other stranded sites with a relay link qualifies the particular stranded site to be the first potential starting point or the second potential starting point.

5. The one or more non-transitory computer-readable media of claim 1 , the acts further comprising:
determining that the first solution cost is below a predetermined threshold cost.

6. The one or more non-transitory computer-readable media of claim 1 , wherein the associated bid cost comprises adding a fiber optic connection to the first potential starting point.

7. The one or more non-transitory computer-readable media of claim 1 , wherein the associated bid cost comprises adding a microwave link connection to the first potential starting point.

8. The one or more non-transitory computer-readable media of claim 1 , wherein the weights for each vertex and edge comprise at least one of bandwidth, cost, and availability.

9. The one or more non-transitory computer-readable media of claim 1 , wherein the mesh network graph between stranded sites and relay sites comprises a plurality of line-of-site (LoS), near-line-of-site (nLoS), and non-line-of-site (NLoS) point-to-point (P2P) connections.

10. The one or more non-transitory computer-readable media of claim 1 , wherein the mesh network graph between stranded sites and relay sites comprises at least one item of physical information for at least one of the stranded sites or at least one of the relay sites.

11. A method comprising:
identifying stranded sites in a cellular communication system;
creating a stranded site cluster comprising a mesh network graph between at least one stranded site and at least one relay site for a portion of a network;
updating weights for each vertex and edge of the mesh network graph for which there is an associated bid cost;
selecting two or more potential starting points in the stranded site cluster;
updating the mesh network graph based on the selection of the two or more potential starting points;
identifying a minimum weight spanning tree solution for each of the two or more potential starting points, each of the minimum weight spanning tree solutions representing an average cost per stranded site; and
selecting the minimum weight spanning tree that represents the lowest average cost per stranded site.

12. The method of claim 11 , further comprising:
determining that each microwave link capacity in the minimum weight spanning tree solutions is equal to, or larger than, an aggregated site capacity; and
determining that the end-to-end backhaul availability is equal to or larger than the minimum backhaul availability threshold.

13. The method of claim 11 ,
wherein updating the mesh network graph based on the selection of the two or more potential starting points comprises, in separate instances of the mesh network graph for each of the two or more potential starting points, setting weights of the potential starting points different than the potential starting point associated with the instance to zero and removing stranded sites and relay sites that do not have bids to connect them to the potential starting point associated with the instance.

14. The method of claim 11 , wherein the associated bid cost comprises a contractor bid to add a fiber optic connection to at least one of the stranded sites.

15. The method of claim 11 , wherein the associated bid cost comprises a contractor bid to add a microwave connection to at least one of the stranded sites.

16. The method of claim 11 , wherein the at least one relay site comprises a site with an existing microwave link.

17. The method of claim 11 , wherein the at least one relay site comprises a site with an existing alternative access vendor (AAV) connection.

18. A backhaul optimization engine comprising:
a processor;
system memory; and
an adaptive graph minimum spanning tree (AG-MST) algorithm to:
identify stranded sites in a cellular communication system;
create a stranded site cluster comprising a mesh network graph between at least one stranded site and at least one relay site for a portion of a network;
update weights for each vertex and edge of the mesh network graph for which there is an associated bid cost;
selecting one or more potential starting points in the stranded site cluster;
update the mesh network graph based on the selection of the two or more potential starting points;
identify a minimum weight spanning tree solution for each of the two or more potential starting points, each of the minimum weight spanning tree solutions representing an average cost per stranded site; and
selecting the minimum weight spanning tree that represents the lowest average cost per stranded site.

19. The backhaul optimization engine of claim 18 ,
wherein updating the mesh network graph based on the selection of the two or more potential starting points comprises, in separate instances of the mesh network graph for each of the two or more potential starting points, setting weights of the potential starting points different than the potential starting point associated with the instance to zero and removing stranded sites and relay sites that do not have bids

Assignees

• T Mobile Usa Inc

Inventors

• Liu Chunming
• Taylor Michael D
• Fleming Bryan
• Mayo David Arthur

Classifications

• H04L45/18

  Loop-free operations · CPC title

• H04W84/18

  Self-organising networks, e.g. ad-hoc networks or sensor networks · CPC title

• H04W16/18

  Network planning tools · CPC title

• H04W16/24 Primary

  Cell structures · CPC title

• H04W24/02 Primary

  Arrangements for optimising operational condition · CPC title