Deploying line-of-sight communication networks

Patent metadata

Field	Value
Publication number	US-2016134373-A1
Application number	US-201414534690-A
Country	US
Kind code	A1
Filing date	Nov 6, 2014
Priority date	Nov 6, 2014
Publication date	May 12, 2016
Grant date	—

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

Assignees

• Facebook Inc

Inventors

• Gros Andreas
• Maguire Yael
• Yogeeswaran Karthik

Classifications

• H04B10/1129 Primary

  Arrangements for outdoor wireless networking of information · CPC title

• H04W64/003

  locating network equipment · CPC title

• H04W64/00

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

• H04L67/52

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