Deploying line-of-sight communication networks

• US 9,806,809 B2
• Filed: 11/06/2014
• Issued: 10/31/2017
• Est. Priority Date: 11/06/2014
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Gros, Andreas, Maguire, Yael, Yogeeswaran, Karthik
• Primary Examiner(s): Sedighian, M. R.
• Application Number:
  US14/534,690
• Publication Number:
  US 20160134373A1
• Time in Patent Office: 1,090 Days
• Field of Search: 398156, 398122, 398129, 398131, 4554561, 4554562, 4554563
• CPC Class Codes: H04B 10/1129 Arrangements for outdoor wireless networking of information
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 64/003 locating network equipment

Abstract

Various of the disclosed embodiments relate to line-of-sight (LOS), e.g., optical, based networks. Systems and methods for determining where to place and how to configure nodes in an optically connected network across a geographic region are provided. Various factors concerning the region may be collected, including, e.g.,: building locations and height, building types, population densities, backbone connection locations, recurring weather factors, geographic elevation, etc. The algorithm may iteratively place nodes based upon the accessible range of a preceding contemplated node position.

Claims

1. A computer-implemented method for generating network node placements, comprising:

receiving real-world information for a target region;

determining a first plurality of priority directions based upon the real-world information;

generating a first set of node positions based upon the first plurality of priority directions and a position on the network backbone;

determining a second plurality of priority directions based upon the real-world information, the first set of node positions, and a Line-of-Sight (LOS) range associated with the first set of node positions;

generating a second set of node positions based upon the second plurality of priority directions;

pruning the first set of node positions and the second set of node positions to generate a subset of the first set of node positions and the second set of node positions;

determining a path comprising the subset of the first set of node positions and the second set of node positions, the path indicating network node placements; and

placing candidate nodes at locations corresponding to the network node placements included in the subset of the first set of node positions and the second set of node positions.

2. The computer-implemented method of claim 1, wherein the real-world information for the target region comprises population information.

3. The computer-implemented method of claim 1, wherein the first set of node positions comprises a single node'"'"'s position, and the second set of node positions comprises candidate child node positions placed along a span associated with the single node, a width of the span determined based on a location of a centroid calculated using the real-world information.

4. The computer-implemented method of claim 1, wherein the path is one of a plurality of paths determined based on pruning the first set of node positions and the second set of node positions.

5. The computer-implemented method of claim 4, wherein the plurality of paths are associated with metric values and form subpaths, wherein the metric values are based on one or more constraints associated with the real-world information.

6. The computer-implemented method of claim 1, further comprising generating topology information associated with the path, the topology information indicating communication devices to be included in nodes of the path.

7. The computer-implemented method of claim 6, wherein the topology information comprises caching capabilities associated with nodes in the path.

8. The computer-implemented method of claim 6, wherein the topology information comprises rerouting information associated with nodes in the path.

9. A non-transitory computer-readable storage medium storing instructions configured to cause a computer system to perform a method comprising:

receiving real-world information for a target region;

determining a first plurality of priority directions based upon the real-world information;

generating a first set of node positions based upon the first plurality of priority directions and a position on the network backbone;

determining a second plurality of priority directions based upon the real-world information, the first set of node positions, and a Line-of-Sight (LOS) range associated with the first set of node positions;

generating a second set of node positions based upon the second plurality of priority directions;

pruning the first set of node positions and the second set of node positions to generate a subset of the first set of node positions and the second set of node positions;

determining a path comprising a subset of the first set of node positions and the second set of node positions, the path indicating network node placements; and

placing candidate nodes at locations corresponding to the network node placements included in the subset of the first set of node positions and the second set of node positions.

10. The computer-readable storage medium of claim 9, wherein the real-world information for the target region comprises population information.

11. The computer-readable storage medium of claim 9, wherein the first set of node positions comprises a single node'"'"'s position, and the second set of node positions comprises candidate child node positions placed along a span associated with the single node, a width of the span determined based on a location of a centroid calculated using the real-world information.

12. The computer-readable storage medium of claim 9, wherein the path is one of a plurality of paths determined based on pruning the first set of node positions and the second set of node positions.

13. The computer-readable storage medium of claim 12, wherein the plurality of paths are associated with metric values and form subpaths, wherein the metric values are based on one or more constraints associated with the real-world information.

14. The computer-readable storage medium of claim 9, the instructions further comprising generating topology information associated with the path, the topology information indicating communication devices to be included in nodes of the path.

15. The computer-readable storage medium of claim 14, wherein the topology information comprises caching capabilities associated with nodes in the path.

16. The computer-readable storage medium of claim 14, wherein the topology information comprises rerouting information associated with nodes in the path.

17. A computer system comprising:

at least one processor;

at least one memory comprising instructions configured to cause the at least one processor to perform a method comprising;

receiving real-world information for a target region;

determining a first plurality of priority directions based upon the real-world information;

generating a first set of node positions based upon the first plurality of priority directions and a position on the network backbone;

determining a second plurality of priority directions based upon the real-world information, the first set of node positions, and a Line-of-Sight (LOS) range associated with the first set of node positions;

generating a second set of node positions based upon the second plurality of priority directions;

pruning the first set of node positions and the second set of node positions to generate a subset of the first set of node positions and the second set of node positions;

determining a path comprising the subset of the first set of node positions and the second set of node positions, the path indicating network node placements; and

placing candidate nodes at locations corresponding to the network node placements included in the subset of the first set of node positions and the second set of node positions.

18. The computer system of claim 17, wherein the real-world information for the target region comprises population information.

19. The computer system of claim 17, wherein the first set of node positions comprises a single node'"'"'s position, and the second set of node positions comprises candidate child node positions placed along a span associated with the single node, a width of the span determined based on a location of a centroid calculated using the real-world information.

20. The computer system of claim 17, wherein the path is one of a plurality of paths determined based on pruning the first set of node positions and the second set of node positions.

21. The computer system of claim 20, wherein the plurality of paths are associated with metric values and form subpaths, wherein the metric values are based on one or more constraints associated with the real-world information.

22. The computer system of claim 17, further comprising generating topology information associated with the path, the topology information indicating communication devices to be included in nodes of the path.

23. The computer system of claim 22, wherein the topology information comprises caching capabilities associated with nodes in the path.

24. The computer-readable storage medium of claim 22, wherein the topology information comprises rerouting information associated with nodes in the path.