Multi-hop wireless network planning

• US 10,536,860 B2
• Filed: 05/10/2017
• Issued: 01/14/2020
• Est. Priority Date: 05/10/2017
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Pang, Guan, Huang, Jing, Paluri, Balmanohar, Karrer, Brian, Filiz, Ismail Onur, Tezel, Birce, Moses, Nicolas Emilio Stier, Ponnampalam, Vishakan, Danford, Timothy Eric
• Primary Examiner(s): Nguyen, Phu K
• Application Number:
  US15/592,100
• Publication Number:
  US 20180332480A1
• Time in Patent Office: 979 Days
• Field of Search: 345419
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 40/20 based on geographic position or location

Abstract

In one embodiment, a method includes accessing a point cloud comprising several points, wherein each point corresponds to a location on a surface of an object located in three-dimensional space; determining whether each point in the point cloud is part of a linear structure, a planar structure, or a volumetric structure; identifying a plurality of point clusters, wherein each point cluster comprises one or more points that are located within a grid segment on a two-dimensional grid derived from the three-dimensional space; determining, for each point cluster, whether the point cluster represents a vertical-linear structure or a portion of a vertical-linear structure; identifying one or more point-cluster pairs, wherein each point-cluster pair includes two point clusters corresponding to one or more vertical-linear structures within a threshold distance in the three-dimensional space; and determining, for each point-cluster pair, whether a line-of-sight exists between each point-cluster in the point-cluster pair.

Claims

1. A method comprising, by one or more computing devices:

identifying, from a point cloud comprising a plurality of point-cloud points, a first set of point clusters, wherein the point cloud is generated by measuring the distance from an initial measuring point to each point-cloud point, wherein each point-cloud point corresponds to a location on a surface of an object located in a region in a three-dimensional space,

and wherein each point cluster comprises one or more point-cloud points that are located within a grid segment on a two-dimensional grid derived from the three-dimensional space;

determining, for at least a plurality of point clusters from the first set of point clusters, that each point cluster represents a vertical-linear structure or a portion of a vertical-linear structure; and

identifying one or more point-cluster pairs from the plurality of point clusters, wherein each point-cluster pair is identified based on the two point clusters having (1) a separation distance within a threshold distance in the three-dimensional space and

(2) a line-of-sight connection in the three-dimensional space.

2. The method of claim 1, wherein determining that each point cluster of the plurality of point clusters represents a vertical-linear structure or a portion of a vertical-structure is done using Principle Component Analysis (PCA).

3. The method of claim 2, wherein the PCA results in three eigenvalues λ

₁, λ

₂, λ

₃,wherein;

a linear structure is characterized by λ

₁>

>

λ

₂≅

λ

₃;

a planar structure is characterized by λ

₁≅

λ

₂>

>

λ

₃; and

a volumetric structure is characterized by λ

₁≅

λ

₂≅

λ

₃.

4. The method of claim 1, wherein a line-of-sight connection exists between two point clusters in a point-cluster pair if a number of point-cloud points between the two point clusters is below a threshold number.

5. The method of claim 1, wherein the point cloud is obtained using light detection and ranging (LiDAR).

6. The method of claim 1, further comprising:

for each point cluster determined to represent a vertical-linear structure or portion of the vertical-linear structure, applying one or more filter constraints to determine that the vertical-linear structure or portion of the vertical-linear structure is a utility pole or portion of a utility pole, respectively.

7. The method of claim 6, further comprising:

retrieving one or more point-cloud points that are within a threshold distance of the vertical-linear structure or portion of the vertical-linear structure, wherein the one or more retrieved point-cloud points correspond to a location on a non-vertical component of the utility pole.

8. The method of claim 1, further comprising:

selecting a plurality of point clusters for antenna sites for a multi-hop wireless network, the selection based at least in part on;

whether a line-of-sight connection exists between a respective point cluster and at least one other point cluster; and

one or more demand measures associated with the region in the three-dimensional space.

9. The method of claim 8, wherein the one or more demand measures comprise a set of point clusters that have been determined to require a network antenna.

10. The method of claim 8, wherein the one or more demand measures comprise an amount of traffic at one or more locations within the region in the three-dimensional space.

13. The method of claim 2, wherein the PCA results in three eigenvalues λ

₁, λ

₂, λ

₃,wherein;

a linear structure is characterized by λ

₁>

>

λ

₂≅

λ

₃;

a planar structure is characterized by λ

₁≅

λ

₂>

>

λ

₃; and

a volumetric structure is characterized by λ

₁≅

λ

₂≅

λ

₃.

11. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

identify, from a point cloud comprising a plurality of point-cloud points, a first set of point clusters, wherein the point cloud is generated by measuring the distance from an initial measuring point to each point-cloud point, wherein each point-cloud point corresponds to a location on a surface of an object located in a region in a three-dimensional space,

and wherein each point cluster comprises one or more point-cloud points that are located within a grid segment on a two-dimensional grid derived from the three-dimensional space;

determine, for at least a plurality of point clusters from the first set of point clusters, that each point cluster represents a vertical-linear structure or a portion of a vertical-linear structure; and

identify one or more point-cluster pairs from the plurality of point clusters, wherein each point-cluster pair is identified based on the two point clusters having (1) a separation distance within a threshold distance in the three-dimensional space and (2) a line-of-sight connection in the three-dimensional space.

12. The media of claim 11, wherein determining that each point cluster of the plurality of point clusters represents a vertical-linear structure or a portion of a vertical-structure is done using Principle Component Analysis (PCA).

14. The media of claim 11, wherein a line-of-sight connection exists between two point clusters in a point-cluster pair if a number of point-cloud points between the two point clusters is below a threshold number.

15. The media of claim 11, wherein the point cloud is obtained using light detection and ranging (LiDAR).

16. The media of claim 11, wherein the software is further operable when executed to:

for each point cluster determined to represent a vertical-linear structure or portion of the vertical-linear structure, apply one or more filter constraints to determine that the vertical-linear structure or portion of the vertical-linear structure is a utility pole or portion of a utility pole, respectively.

17. The media of claim 16, wherein the software is further operable when executed to:

retrieve one or more point-cloud points that are within a threshold distance of the vertical-linear structure or portion of the vertical-linear structure, wherein the one or more retrieved point-cloud points correspond to a location on a non-vertical component of the utility pole.

18. The media of claim 11, wherein the software is further operable when executing the instructions to:

select a plurality of point clusters for antenna sites for a multi-hop wireless network, the selection based at least in part on;

whether a line-of-sight connection exists between a respective point cluster and at least one other point cluster; and

one or more demand measures associated with the region in the three-dimensional space.

19. The media of claim 18, wherein the one or more demand measures comprise a set of point clusters that have been determined to require a network antenna.

20. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors being operable when executing the instructions to;

identify, from a point cloud comprising a plurality of point-cloud points, a first set of point clusters, wherein the point cloud is generated by measuring the distance from an initial measuring point to each point-cloud point, wherein each point-cloud point corresponds to a location on a surface of an object located in a region in a three-dimensional space,

and wherein each point cluster comprises one or more point-cloud points that are located within a grid segment on a two-dimensional grid derived from the three-dimensional space;

determine, for at least a plurality of point clusters from the first set of point clusters, that each point cluster represents a vertical-linear structure or a portion of a vertical-linear structure; and

identify one or more point-cluster pairs from the plurality of point clusters, wherein each point-cluster pair is identified based on the two point clusters having (1) a separation distance within a threshold distance in the three-dimensional space and

(2) a line-of-sight connection in the three-dimensional space.