Deploying line-of-sight communication networks

Patent metadata

Field	Value
Publication number	US-10637573-B2
Application number	US-201715713496-A
Country	US
Kind code	B2
Filing date	Sep 22, 2017
Priority date	Nov 6, 2014
Publication date	Apr 28, 2020
Grant date	Apr 28, 2020

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 one or more constraints for a target region;
selecting at least one network position on at least one network backbone;
determining multiple priority directions based on real-world information, the at least one network position, and a Line-Of-Sight (LOS) range based on the one or more constraints;
generating iteratively a set of node positions based on the multiple priority directions such that a subsequent node placement is generated based upon an accessible range of a preceding contemplated node position; and
after determining that the multiple priority directions have achieved a threshold limit, determining a set of paths comprising the set of node positions, the set of paths indicating network node placements.

2. The computer-implemented method of claim 1 , wherein the at least one network position includes a plurality of positions on the network backbone.

3. The computer-implemented method of claim 2 , wherein each network position in the plurality of positions are spaced apart at regular intervals.

4. The computer-implemented method of claim 1 , wherein the threshold limit is based on the one or more constraints or other network positions on the at least one network backbone.

5. The computer-implemented method of claim 1 , wherein the one or more constraints for the target region include at least one of: a maximum number of nodes available, a desired coverage of the target region, uncovered areas of the target region, a prioritization of certain communities or areas, cost, difficulty in node installation, or population information.

6. The computer-implemented method of claim 1 , wherein each path in the set of paths is associated with a metric value, further comprising:
selecting, in the set of paths, a path with a preferred metric value.

7. The computer-implemented method of claim 6 , wherein the preferred metric value is the highest metric value.

8. The computer-implemented method of claim 6 , wherein the preferred metric value is the lowest metric value.

9. A non-transitory computer-readable storage medium storing instructions configured to cause a computer system to perform a method comprising:
receiving one or more constraints for a target region;
selecting at least one network position on at least one network backbone;
determining multiple priority directions based upon real-world information, the at least one network position, and a Line-Of-Sight (LOS) range based on the one or more constraints;
generating iteratively a set of node positions based on the multiple priority directions such that a subsequent node placement is generated based upon an accessible range of a preceding contemplated node position; and
after determining that the multiple priority directions have achieved a threshold limit, determining a set of paths comprising the set of node positions, the set of paths indicating network node placements.

10. The computer-readable storage medium of claim 9 , wherein the at least one network position includes a plurality of positions on the network backbone.

11. The computer-readable storage medium of claim 10 , wherein each network position in the plurality of positions are spaced apart at regular intervals.

12. The computer-readable storage medium of claim 9 , wherein the threshold limit is based on the one or more constraints or other positions on the at least one network backbone.

13. The computer-readable storage medium of claim 9 , wherein the one or more constraints for the target region include at least one of: a maximum number of nodes available, a desired coverage of the target region, uncovered areas of the target region, a prioritization of certain communities or areas, cost, difficulty in node installation, or population information.

14. The computer-readable storage medium of claim 9 , wherein each path in the set of paths is associated with a metric value, further comprising:
selecting, in the set of paths, a path with a preferred metric value.

15. The computer-readable storage medium of claim 14 , wherein the preferred metric value is the highest metric value.

16. The computer-readable storage medium of claim 14 , wherein the preferred metric value is the lowest metric value.

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 one or more constraints for a target region;
selecting at least one network position on at least one network backbone;
determining multiple priority directions based on real-world information, the at least one network position, and a Line-Of-Sight (LOS) range based on the one or more constraints;
generating iteratively a set of node positions based on the multiple priority directions such that a subsequent node placement is generated based upon an accessible range of a preceding contemplated node position; and
after determining that multiple priority directions have achieved a threshold limit, determining a set of paths comprising the set of node positions, the set of paths indicating network node placements.

18. The system of claim 17 , wherein the one or more constraints for the target region include at least one of: a maximum number of nodes available, a desired coverage of the target region, uncovered areas of the target region, a prioritization of certain communities or areas, cost, difficulty in node installation, or population information.

19. The system of claim 17 , wherein each path in the set of paths is associated with a metric value, further comprising:
selecting, in the set of paths, a path with a preferred metric value.

20. The system of claim 19 , wherein the preferred metric value is the highest metric value.

Assignees

• Facebook Inc

Inventors

• Gros Andreas
• Maguire Yael
• Yogeeswaran Karthik

Classifications

• 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

• H04W64/003

  locating network equipment · CPC title

• H04L29/08657

  Electricity · mapped topic

• H04L67/18

  Electricity · mapped topic