DEPLOYING LINE-OF-SIGHT COMMUNICATION NETWORKS

• US 20160134373A1
• Filed: 11/06/2014
• Published: 05/12/2016
• 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
• Granted Patent: US 9,806,809 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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; and

determining a path comprising a subset of the generated first and second sets of node positions, the path indicating network node placements.

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 based upon the real-world information.

4. The computer-implemented method of claim 1, wherein the path is one of a plurality of paths determined from subsets of generated nodes.

5. The computer-implemented method of claim 4, wherein the plurality of paths are associated with metric values forming a partial ordering.

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

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

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

9. A 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; and

determining a path comprising a subset of the generated first and second sets of node positions, the path indicating network node placements.

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 based upon the real-world information.

12. The computer-readable storage medium of claim 9, wherein the path is one of a plurality of paths determined from subsets of generated nodes.

13. The computer-readable storage medium of claim 12, wherein the plurality of paths are associated with metric values forming a partial ordering.

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

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

16. The computer-readable storage medium of claim 14, wherein the path metadata 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; and

determining a path comprising a subset of the generated first and second sets of node positions, the path indicating network node placements.

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 based upon the real-world information.

20. The computer system of claim 17, wherein the path is one of a plurality of paths determined from subsets of generated nodes.

21. The computer system of claim 20, wherein the plurality of paths are associated with metric values forming a partial ordering.

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

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

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