Deploying line-of-sight communication networks

Patent metadata

Field	Value
Publication number	US-9806809-B2
Application number	US-201414534690-A
Country	US
Kind code	B2
Filing date	Nov 6, 2014
Priority date	Nov 6, 2014
Publication date	Oct 31, 2017
Grant date	Oct 31, 2017

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.

First claim

What is claimed is:

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 base

Assignees

• Facebook Inc

Inventors

• Gros Andreas
• Maguire Yael
• Yogeeswaran Karthik

Classifications

• H04W64/003

  locating network equipment · CPC title

• H04B10/1129 Primary

  Arrangements for outdoor wireless networking of information · CPC title

• H04W64/00

  Locating users or terminals {or network equipment} for network management purposes, e.g. mobility management · CPC title

• H04L29/08657

  Electricity · mapped topic

• H04L67/52

  specially adapted for the location of the user terminal · CPC title