Method and system for automatically determining lines of sight between nodes

• US 6,771,932 B2
• Filed: 05/24/2002
• Issued: 08/03/2004
• Est. Priority Date: 05/24/2002
• Status: Expired due to Fees

• Current Assignee: Clearmesh Networks Incorporated
• Original Assignee: Omnilux, Inc.
• Inventors: Caminiti, Lorenzo, Goncalves, Luis, Di Bernardo, Enrico, Moursund, Carter
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US10/153,878
• Publication Number:
  US 20030218994A1
• Time in Patent Office: 802 Days
• Field of Search: 382/154, 382/100, 382/106, 398/130, 398/154, 345/419-427, 356/12.T, 370/316, 370/328, 455/421, 455/423, 455/513, 455/514, 455/517, 455/151.2, 702/5, 702/36
• US Class Current: 455/41.1
• CPC Class Codes: H04W 16/18 Network planning tools

Abstract

The present invention uses data from several sources to determine lines-of-sight between nodes in a FSO network. The present invention provides a three-dimensional neighborhood modeling system that uses aerial image data, Digital Elevation Models, U.S. street map data and address data to automatically map the placement of nodes within a neighborhood or other geographical area.

Method for creating the 3-Dimensional, House and Tree Maps used in the line-of-sight processing are also disclosed. A House Map in the present invention identifies houses in an area of consideration, and a Tree Map in the present invention identifies trees in an area of consideration. A 3-Dimensional Map in the present invention provides an elevation for every pixel for the area under consideration, whereby the elevation is adjusted for the height of trees, houses and other objects.

Claims

1. A method of determining line-of-sight configurations between a plurality of points in three-dimensional space, comprising the steps of:

(a) selecting a first point and a second point for processing;

(b) determining whether a valid, unobstructed line-of-sight exists between the first point and the second point by performing the steps of

i) determining a straight line between the first point and the second point;

(ii) determining whether the length of the straight line is less than a maximum link length;

(iii) determining whether the angle between the straight line and the vertical is less than a maximum vertical angle; and

iv) if the length of the straight line is less than the maximum link length, and the vertical angle of the straight line is less than the maximum vertical angle, determining whether the straight line intersects with an obstruction in the three-dimensional space;

(c) if a valid, unobstructed line-of-sight exists between the first point and the second point, recording information about the line-of-sight in a first database; and

(d) if a valid, unobstructed line-of-sight does not exist between the first point and the second point, determining whether an alternative placement of at least one point results in a valid, alternative unobstructed line-of-sight between the first point and the second point, and if a valid, alternative unobstructed line-of-sight does exist between the first point and the second point, recording information about the alternative line-of-sight in a second database;

repeating steps (a)-(d) for other combinations of points.

2. The method of claim 1, wherein the points are nodes in an infrared wireless system.

3. The method of claim 1, wherein step (b)(i) additionally comprises adding a margin to the straight line.

4. The method of claim 3, wherein said margin comprises a vertical margin and a horizontal margin.

5. The method of claim 3, wherein step (b)(iv) determines whether the straight line with the margin added intersects with an obstruction in the three-dimensional space.

6. The method of claim 1, wherein said maximum link length is a configurable parameter.

7. The method of claim 1, wherein said maximum vertical angle is a configurable parameter.

8. The method of claim 1, wherein step (b)(iv) comprises:

dividing the straight line into equally sized pixels in a 3-Dimensional Map;

determining each pixel'"'"'s elevation;

for each pixel, reading an adjusted terrain elevation from the 3-Dimensional Map for that pixel'"'"'s ground location and determining whether the pixel'"'"'s elevation is lower than the adjusted terrain elevation; and

if the elevation of any segment is lower than the adjusted terrain elevation at that pixel'"'"'s location, determining that the straight line intersects with an obstruction.

9. The method of claim 8, wherein the adjusted elevation of a location in the 3-Dimensional Map is the elevation of the terrain at that location adjusted by the height of an object at that location.

10. The method of claim 9, wherein the object is a building.

11. The method of claim 9, wherein the object is a tree.

12. The method of claim 1, wherein step (c) additionally comprises recording information about the straight line between the first point and the second point in the first database, if a valid, unobstructed line-of-sight does not exist between the first point and the second point.

13. The method of claim 1, wherein step (c) records information about the line-of-sight including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the first point and the second point.

14. The method of claim 13, wherein the first point and second points are nodes in a communications system, and wherein information about a structure on which the first node resides and information about a structure on which the second node resides is also recorded.

15. The method of claim 13, wherein information about the length of the link between the first point and the second point is also recorded.

16. The method of claim 1, wherein steps (a)-(d) are repeated for every combination of points in a system and wherein the first database has a record for every possible combination of points.

17. The method of claim 1, wherein step (d) additionally comprises recording information about a straight line between an alternative placement of the first point and an alternative placement of the second point in the second database.

18. The method of claim 17, wherein step (d) records information about the straight line including first point identification, second point identification, location of to first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the points when at least one point is placed in an alternative location in the second database.

19. The method of claim 18, wherein the first point and second point are nodes in a communications system, and step (d) additionally records information about a structure on which the first node resides and information about a structure on which the second resides in the second database.

20. The method of claim 19, wherein step (d) additionally records information about the length of the link between points when at least one point is placed at an alternative location in the second database.

21. A computer-readable medium containing instructions for determining line-of-sight configurations between a plurality of points in three-dimensional space, wherein said instructions cause a computer to:

(a) select a first point and a second point for processing;

(b) determine whether a valid, unobstructed line-of-sight exists between the first point and the second point by performing the steps of

i) determine a straight line between the first point and the second point;

ii) determine whether the length of the straight line is less than a maximum link length;

iii) determine whether the angle between the straight line and the vertical is less than a maximum vertical angle; and

iv) if the length of the straight line is less than a maximum link length and the angle between the straight line and the vertical is less than the maximum vertical angle, determine whether the straight line intersects with an obstruction in the three-dimensional space;

(c) if a valid, unobstructed line-of-sight exists between the first point and the second point, record information about the line-of-sight in a first database; and

(d) if a valid, unobstructed line-of-sight does not exist between the fist point and the second point, determine whether an alternative placement at least one point results in a valid, alternative unobstructed line-of-sight between the first point and the second point, and if a valid, alternative unobstructed line-of-sight does exist between the first point and the second point, record information about the alternative line-of-sight in a second database;

repeat steps (a)-(d) for other combination of points.

22. The computer-readable medium of claim 21, wherein the points are nodes in an infrared wireless system.

23. The computer-readable medium of claim 21, wherein said instructions to determine whether the length of the straight line is less than a maximum link additionally comprises instructions to add a margin to the straight line.

24. The computer-readable medium of claim 23, wherein said margin comprises a vertical margin and a horizontal margin.

25. The computer-readable medium of claim 23, wherein said instructions to determine whether the straight line intersects with an obstruction cause a computer to determine whether the straight line with the margin added intersects with an obstruction in the three-dimensional space.

26. The computer-readable medium of claim 21, wherein said maximum link length is a configurable parameter.

27. The computer-readable medium of claim 21, wherein said maximum vertical angle is a configurable parameter.

28. The computer-readable medium of claim 21, wherein said instructions to determine whether the straight line intersects with an obstruction cause a computer to:

divide the straight line into equally sized pixels in a 3-Dimensional Map;

determine each pixel'"'"'s elevation;

for each pixel, read an adjusted terrain elevation from the 3-Dimensional Map for that pixel'"'"'s ground location and determining whether the pixel'"'"'s elevation is lower than the adjusted terrain elevation; and

if the elevation of any segment is lower than the adjusted terrain elevation at that pixel'"'"'s location, determine that the straight line intersects with an obstruction.

29. The computer-readable medium of claim 28, wherein the adjusted elevation of a location in the 3-Dimensional Map is the elevation of the terrain at that location adjusted by die height of an object at that location.

30. The computer-readable medium of claim 29, wherein the object is a building.

31. The computer-readable medium of claim 29, wherein the object is a tree.

32. The computer-readable medium of claim 21, wherein said instructions to record information about the line-of-sight in a first database additionally instructions to record information about the straight line between the first point and the second point in the first database if a valid, unobstructed line-of-sight does not exist between the first point and the second point.

33. The computer-readable medium of claim 21, wherein said instructions to record information about the line-of-sight in a first database cause the computer to record information about the line-of-sight including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the first point and the second point.

34. The computer-readable medium of claim 33, wherein the first point and second points are nodes in a communications system, and said instructions to record information additionally comprise instructions to record information about a structure on which the first node resides and information about a structure on which the second node resides.

35. The computer-readable medium of claim 33, wherein said instructions to record information additionally comprises instructions to record information about the length of the link between the first point and the second point.

36. The computer-readable medium of claim 21, wherein said instructions are repeated for every combination of points in a system and wherein the first database has a record for every possible combination of points.

37. The computer-readable medium of claim 36, wherein said instructions to record information in a second database additionally comprises instructions to record information about a straight line between an alternative placement of the first point and an alternative placement of the second point in the second database.

38. The computer-readable medium of claim 36, wherein said instructions to record information in a second database additionally comprises instructions to record information about the straight line including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the points when at least one point is placed in an alternative location in the second database.

39. The computer-readable medium of claim 38, wherein the first point and second point are nodes in a communications system, and additionally comprising instructions to record information in the second database about a structure on which the first node resides and information about a structure on which the second resides.

40. The computer-readable medium of claim 38, additionally comprising instructions to record information in the second database about the length of the link between points when at least one point is placed at an alternative location.

41. A method operable on a computer for determining line-of-sight configurations between a plurality of points in three-dimensional space, comprising the steps of:

(a) selecting a first point and a second point for processing;

(b) determining on the computer whether a valid, unobstructed line-of-sight exists between the first point and the second point by performing the steps of

i) determining a straight line between the first point and the second point;

(ii) determining whether the length of the straight line is less than a maximum link length;

(iii) determining whether the angle between the straight line and the vertical is less than a maximum vertical angle; and

iv) if the length of the straight line is less than the maximum link length, and the vertical angle of the straight line is less than the maximum vertical angle, determining whether the straight line intersects with an obstruction in the three-dimensional space;

(c) if a valid, unobstructed line-of-sight exists between the first point and the second point, recording information about the line-of-sight in a first database; and

(d) if a valid, unobstructed line-of-sight does not exist between the first point and the second point, determining on the computer whether an alternative placement of at least one point results in a valid, alternative unobstructed line-of-sight between the first point and the second point, and if a valid, alternative unobstructed line-of-sight does exist between the first point and the second point, recording information about the alternative line-of-sight in a second database;

repeating steps (a)-(d) for other combinations of points.

42. A system for determining line-of-sight configurations between a plurality of points in three-dimensional space, comprising:

(a) means for selecting a first point and a second point for processing;

(b) means for determining whether a valid, unobstructed line-of-sight exists between the first point and the second point by performing the steps of

i) determining a straight line between the first point and the second point;

(ii) determining whether the length of the straight line is less than a maximum link length;

(iii) determining whether the angle between the straight line and the vertical is less than a maximum vertical angle;

end

iv) if the length of the straight line is less than the maximum link length, and the vertical angle of the straight line is less than the maximum vertical angle, determining whether the straight line intersects with an obstruction in the three-dimensional space;

(c) means for, if a valid, unobstructed line-of-sight exists between the first point and the second point, recording information about the line-of-sight in a first database; and

(d) means for, if a valid, unobstructed line-of-sight does not exist between the first point and the second point, determining whether an alternative placement of at least one point results in a valid, alternative unobstructed line-of-sight between the first point and the second point, and if a valid, alternative unobstructed line-of-sight does exist between the first point and the second point, recording information about the alternative line-of-sight in a second database;

repeating the functions performed by means (a)-(d) for other combinations of points.

43. The system of claim 42, wherein the points are nodes in an infrared wireless system.

44. The system of claim 42, wherein means (b)(i) additionally comprises means for adding a margin to the straight line.

45. The system of claim 44, wherein said margin comprises a vertical margin and a horizontal margin.

46. The system of claim 44, wherein means (b)(iv) determines whether the straight line with the margin added intersects with an obstruction in the three-dimensional space.

47. The system of claim 42, wherein said maximum link length is a configurable parameter.

48. The system of claim 42, wherein said maximum vertical angle is a configurable parameter.

49. The system of claim 42, wherein means (b)(iv) comprises:

means for dividing the straight line into equally sized pixels in a 3-Dimensional Map;

means for determining each pixel'"'"'s elevation;

means, for each pixel, for reading an adjusted terrain elevation from the 3-Dimensional Map for that pixel'"'"'s ground location and determining whether the pixel'"'"'s elevation is lower than the adjusted terrain elevation; and

means, if the elevation of any segment is lower than the adjusted terrain elevation at that pixel'"'"'s location, for determining that the straight line intersects with an obstruction.

50. The system of claim 49, wherein the adjusted elevation of a location in the 3-Dimensional Map is the elevation of the terrain at that location adjusted by the height of an object at that location.

51. The system of claim 50, wherein the object is a building.

52. The system of claim 50, wherein the object is a tree.

53. The system of claim 42, wherein means (c) additionally comprises recording information about the straight line between the first point and the second point in the first database, if a valid, unobstructed line-of-sight does not exist between the first point and the second point.

54. The system of claim 42, wherein means (c) records information about the line-of-sight including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the first point and the second point.

55. The system of claim 54, wherein the first point and second points are nodes in a communications system, and wherein information about a structure on which the first node resides and information about a structure on which the second node resides is also recorded.

56. The system of claim 54, wherein information about the length of the link between the first point and the second point is also recorded.

57. The system of claim 42, wherein means (a)-(d) are operated for every combination of points in a system and wherein the first database has a record for every possible combination of points.

58. The system of claim 42, wherein means (d) additionally comprises means for recording information about a straight line between an alternative placement of the first point and an alternative placement of the second point in the second database.

59. The system of claim 58, wherein means (d) records information about the straight line including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the points when at least one point is placed in an alternative location in the second database.

60. The system of claim 59, wherein the first point and second point are nodes in a communications system, and means (d) additionally records information about a structure on which the first node resides and information about a structure on which the second resides in the second database.

61. The system of claim 60, wherein means (d) additionally records information about the length of the link between points when at least one point is placed at an altern.

62. A system for determining line-of-sight configurations between a plurality of points in three-dimensional space, comprising:

a processor;

a memory connected to the processor and storing instructions to control the operation of the processor to perform the steps of

(a) selecting a first point and a second point for processing;

(b) determining whether a valid, unobstructed line-of-sight exists between the first point and the second point by performing the steps of

i) determining a straight line between the first point and the second point;

(ii) determining whether the length of the straight line is less than a maximum link length;

(iii) determining whether the angle between the straight line and the vertical is less than a maximum vertical angle; and

iv) if the length of the straight line is less than the maximum link length, and the vertical angle of the straight line is less than the maximum vertical angle, determining whether the straight line intersects with an obstruction in the three-dimensional space;

(c) if a valid, unobstructed line-of-sight exists between the first point and the second point, recording information about the line-of sight in a first database; and

(d) if a valid, unobstructed line-of-sight does not exist between the first point and the second point, determining whether an alternative placement of at least one point results in a valid, alternative unobstructed line-of-sight between the first point and the second point, and if a valid, alternative unobstructed line-of-sight does exist between the first point and the second point, recording information about the alternative line-of-sight in a second database;

repeating steps (a)-(d) for other combinations of points.

63. The system of claim 62, wherein the points are nodes in an infrared wireless system.

64. The system of claim 62, wherein step (b)(i) additionally comprises adding a margin to the straight line.

65. The system of claim 64, wherein said margin comprises a vertical margin and a horizontal margin.

66. The system of claim 64, wherein step (b)(iv) determines whether the straight line with the margin added intersects with an obstruction in the three-dimensional space.

67. The system of claim 62, wherein said maximum link length is a configurable parameter.

68. The system of claim 62, wherein said maximum vertical angle is a configurable parameter.

69. The system of claim 62, wherein step (b)(iv) comprises:

dividing the straight line into equally sized pixels in a 3-Dimensional Map;

determining each pixel'"'"'s elevation;

for each pixel, reading an adjusted terrain elevation from the 3-Dimensional Map for that pixel'"'"'s ground location and determining whether the pixel'"'"'s elevation is lower than the adjusted terrain elevation; and

if the elevation of any segment is lower than the adjusted terrain elevation at that pixel'"'"'s location, determining that the straight line intersects with an obstruction.

70. The system of claim 69, wherein the adjusted elevation of a location in the 3-Dimensional Map is the elevation of the terrain at that location adjusted by the height of an object at that location.

71. The system of claim 70, wherein the object is a building.

72. The system of claim 70, wherein the object is a tree.

73. The system of claim 62, wherein step (c) additionally comprises recording information about the straight line between the first point and the second point in the first database, if a valid, unobstructed line-of-sight does not exist between the first point and the second point.

74. The system of claim 62, wherein step (c) records information about the line-of-sight including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of sight between the first point and the second point.

75. The system of claim 74, wherein the first point and second points are nodes in a communications system, and wherein information about a structure on which the first node resides and information about a structure on which the second node resides is also recorded.

76. The system of claim 74, wherein information about the length of the link between the first point and the second point is also recorded.

77. The system of claim 62, wherein steps (a)-(d) are repeated for every combination of points in a system and wherein the first database has a record for every possible combination of points.

78. The system of claim 62, wherein step (d) additionally comprises recording information about a straight line between an alternative placement of the first point and an alternative placement of the second point in the second database.

79. The system of claim 78, wherein step (d) records information about the straight line including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the points when at least one point is placed in an alternative location in the second database.

80. The system of claim 79, wherein the first point and second point are nodes in a communications system, and step (d) additionally records information about a structure on which the first node resides and information about a structure on which the second resides in the second database.

81. The system of claim 80, wherein step (d) additionally records information about the length of the link between points when at least one point is placed at an alternative location in the second database.