Cellular backhaul coverage algorithms

Patent metadata

Field	Value
Publication number	US-9826414-B2
Application number	US-201514982581-A
Country	US
Kind code	B2
Filing date	Dec 29, 2015
Priority date	Oct 12, 2015
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

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, 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 for which there is an associated bid cost;
identifying a first potential starting point in the stranded site cluster;
updating the stranded site cluster by removing connected stranded sites;
identifying a first, minimum weight spanning tree solution for the first potential starting point;
determining that each microwave link capacity in the first, minimum weight spanning tree solution is equal to, or larger than, an aggregated site capacity; and
determining that an end-to-end backhaul availability is equal to or larger than a minimum backhaul availability threshold.

2. The one or more non-transitory computer-readable media of claim 1 , the acts further comprising:
determining that the first solution represents a minimum average cost per stranded site.

3. The one or more non-transitory computer-readable media of claim 2 , further comprising:
identifying a second potential starting point in the stranded site cluster;
updating the stranded site cluster by removing connected stranded sites;
identifying a second, minimum weight spanning tree solution for the second potential starting point;
determining that each microwave link capacity in the second, minimum weight spanning tree solution is equal to, or larger than, the aggregated site capacity;
determining that the second solution represents the minimum average cost per stranded site; and
discarding the first solution.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

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 at least one item of physical information for at least one of the stranded sites or at least one of the relay sites.

10. 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 for which there is an associated bid cost;
identifying one or more potential starting points in the stranded site cluster;
updating the stranded site cluster by removing connected stranded sites;
identifying a first, minimum weight spanning tree solution for each of the one or more potential starting points;
determining that each microwave link capacity in the first, minimum weight spanning tree solution is equal to, or larger than, an aggregated site capacity; and
determining that an end-to-end backhaul availability is equal to or larger than a minimum backhaul availability threshold.

11. The method of claim 10 , further comprising:
determining a solution in the first subset that provides a minimum average cost per stranded site.

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

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

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

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

16. 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 for which there is an associated bid cost;
identify one or more potential starting points in the stranded site cluster;
update the stranded site cluster by removing connected stranded sites;
identify a first, minimum weight spanning tree solution for each of the one or more potential starting points;
determine that each microwave link capacity in the first, minimum weight spanning tree solution is equal to, or larger than, an aggregated site capacity; and
determine that an end-to-end backhaul availability is equal to or larger than a minimum backhaul availability threshold.

17. The backhaul optimization engine of claim 16 , wherein the AG-MST algorithm is further to:
determine a solution that provides a minimum average cost per stranded site.

18. The backhaul optimization engine of claim 16 , wherein the associated bid cost comprises a contractor bid to add at least one of a fiber optic connection and a microwave link to at least one of the stranded sites.

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