Method and apparatus for detecting and locating intrusion in a wireless network

• US 7,570,213 B2
• Filed: 06/06/2006
• Issued: 08/04/2009
• Est. Priority Date: 06/14/2005
• Status: Active Grant

• Current Assignee: United States Of America As Represented By The Secretary Of The Air Force
• Original Assignee: United States Of America As Represented By The Secretary Of The Air Force
• Inventors: Cole, Frank R., Debany, Warren H., Ratazzi, E. Paul
• Primary Examiner(s): Tarcza; Thomas H
• Assistant Examiner(s): LIU, HARRY K
• Application Number:
  US11/449,184
• Publication Number:
  US 20060281473A1
• Time in Patent Office: 1,155 Days
• Field of Search: 342/458, 455/456.1, 455/456.5
• US Class Current: 342/458
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

Method and apparatus for locating an intruding radio frequency signal in a wireless network. Relative distance measurements are computed between pairs of receivers from a plurality of receivers to the source of the intruding signal based on received signal strength. Loci of possible locations are plotted, points of intersection are determined, and a clustering algorithm is applied, yielding the location of the source of the intruding signal. The invention is distinguished in that its operation does not require knowledge of either the transmitted power or antenna gain of the intruding signal source.

Claims

1. Method for detecting and locating intrusion in a wireless network, comprising the steps of:

receiving an intruding radio frequency signal by a plurality of receivers;

measuring the received signal strength R_i on each of said plurality of receivers;

for each paired combination of said plurality of receivers, computing one relative distance measurement d to the location of said transmitting source,

said one relative distance measurement d being a function of said received signal strength R_i of each said receiver in each said paired combination;

for each paired combination of said plurality of receivers, computing the possible locations of said transmitting source lying on the locus of points satisfying

d=[R₁/R₂]^1/2;

further comprising;

computing the displacement c of the center of said locus from the first receiver in each said paired combination;

computing the radius r of said locus;

and,

computing the point about which said locus is centered;

computing the intermediate points of intersection of all said loci corresponding to all said paired combinations; and

computing the actual points of intersection from said intermediate points of intersection of all said loci of points so as to determine an unambiguous location of said transmitting source.

2. The step of computing intermediate points of intersection of all said loci of points of claim 1, further comprising

computing the j^th intermediate point of intersection by

computing the Euclidian distance L between the center points of each of said loci of points according to

L=√

{square root over ((x_c2−

x_c1)²+(y_c2−

y_c1)²)}{square root over ((x_c2−

x_c1)²+(y_c2−

y_c1)²)}

wherein (x_c1, y_c1) and (x_c2, y_c2) are the coordinates of the centers of an i^th said locus of points having a radius r₁ and an i^th+1 said locus of points having a radius r₂, respectively;

mapping said i^th locus center point onto the origin of x-y coordinate system and mapping said i^th+1 locus center point onto the x-axis of said coordinate system at a displacement L units along said x-axis from said i^th locus center point;

locating a third point within the first quadrant of said coordinate system, said third point being

displaced r₁ units from said first locus center point and r₂ units from said second locus center point so as to form the apex of a right triangle having base length L₁ and height h; and

displaced θ

units from said x-axis, counterclockwise about the origin;

so as to cause said third point to coincide with the coordinate (L₁, h).

3. Method of claim 2, further comprising the step of computing said base length L₁ according to

L₁=r₁ cos θ

−

.

4. Method of claim 2, further comprising the step of computing said height of said apex according to

h=r₁ sin θ

.

5. Method of claim 2, further comprising computing the j^th+1 intermediate point of intersection by

reflecting said j^th intermediate point of intersection across the x-axis such that the coordinates of said j^th+1 intermediate point of intersection coincide with (L₁, −

h).

6. Method of claim 2, further comprising computing the k^th actual point of intersection by

computing the counter clockwise angular displacement α

of the center point of the i^th+1 said locus from the x-axis about the origin according to

$\sin <br><br><br><br>\mathrm{\alpha <br><br>}=\frac{y_{c<br><br><br><br>2}-y_{c<br><br><br><br>1}}{L}$

$\cos <br><br><br><br>\mathrm{\alpha <br><br>}=\frac{x_{c<br><br><br><br>2}-x_{c<br><br><br><br>1}}{L}$

rotating said j^th intermediate point of intersection by a units with respect to said i^th locus center point;

translating said rotated j^th intermediate point of intersection by a number of units equivalent to the displacement of said mapped i^th locus center point from said i^th locus center point; and

computing the coordinates (x₃, y₃) of said translated and rotated j^th intermediate point of intersection according to

x₃=L₁ cos α

−

h sin α

+x_c1

y₃=h cos α

+L₁ sin α

+y_c1

said coordinates (x₃, y₃) being the location of said k^th actual point of intersection.

7. Method of claim 2, further comprising computing the k^th+1 actual point of intersection by

computing the counter clockwise angular displacement α

of the center point of the i^th+1 said locus from the x-axis about the origin according to

$\sin <br><br><br><br>\mathrm{\alpha <br><br>}=\frac{y_{c<br><br><br><br>2}-y_{c<br><br><br><br>1}}{L}$

$\cos <br><br><br><br>\mathrm{\alpha <br><br>}=\frac{x_{c<br><br><br><br>2}-x_{c<br><br><br><br>1}}{L}$

rotating said j^th+1 intermediate point of intersection by a units with respect to said i^th locus center point;

translating said rotated j^th+1 intermediate point of intersection by a number of units equivalent to the displacement of said mapped i^th locus center point from said i^th locus center point; and

computing the coordinates (x₄, y₄) of said translated and rotated j^th+1 intermediate point of intersection according to

x₄=L₁ cos α

−

h sin α

+x_c1

y₄=h cos α

+L₁ sin α

+y_c1

said coordinates (x₄, y₄) being the location of said k^th+1 actual point of intersection.

8. Method of claim 1, further comprising computing the number of said loci M according to

$M=\left(\begin{array}{c}N\\ 2\end{array}\right)=\frac{N^2-N}{2}$

wherein N represents the number of said receivers.

9. Method of claim 8, further comprising computing the number of intersections I between said loci according to

$I=2$

( M 2 ) = M 2 - M = N 4 4 - N 3 2 - N 2 4 + N 2 .

10. Method of claim 1 further comprising the step of computing a linear regression of received signal strength R_i versus distance.

11. Method of claim 1 wherein said step of determining an unambiguous location of said transmitting source further comprising computing a clustering algorithm, said step of computing further comprising

computing the mean of the remaining actual points of intersection;

selecting said computed mean as the cluster center;

eliminating from the said cluster that actual point of intersection being furthest from said cluster center;

determining whether one-half of the original points of intersection have been eliminated;

IF one-half of the original points of intersection have NOT been eliminated,

THEN, returning to said step of computing the mean of the remaining actual points of intersection;

OTHERWISE, locating said transmitting source coincident with current said cluster center.

12. Method of claim 1, where, in said step of computing said radius r, r is computed according to

$r=$

D 2 ⁡

[ 1 1 + d - 1 1 - d ] 

.

13. Method of claim 1, where, in said step of computing the displacement c, c is computed according to

$c=\frac{D}{2}$

[ 1 1 + d + 1 1 - d ]

wherein D is the distance between said receivers in each said paired combination.

14. Method of claim 1, where, in said step of computing the point about which said locus is centered, the coordinates (x_c, y_c) represent said point and further satisfy

$x_c=x_1+\frac{c}{D}$

( x 2 - x 1 )

$y_c=y_1+\frac{c}{D}<br><br><br><br>\left(y_2-y_1\right)$

wherein (x₁,y₁) and (x₂,y₂) are the coordinates of the first and the second said receivers in each said paired combination, respectively.

15. An apparatus for detecting and locating intrusion in a wireless network, comprising:

a computer processor;

a plurality of radio frequency receivers;

a means for each of said plurality of said radio frequency receivers to communicate a received signal strength indication (RSSI) with said computer processor; and

a software program residing in said computer processor;

wherein said software program comprises computer-executable instructions, stored on computer-readable media, and wherein said instructions, when executed by said computer processor, provide means for;

receiving an intruding radio frequency signal by a plurality of receivers;

measuring the received signal strength R_i on each of said plurality of receivers;

for each paired combination of said plurality of receivers, computing one relative distance measurement d to the location of said transmitting source, said one relative distance measurement d being a function of said received signal strength R_i of each said receiver in each said paired combination;

for each paired combination of said plurality of receivers, computing the possible locations of said transmitting source lying on the locus of points satisfying

d=[R₁/R₂]^1/2;

further comprising;

computing the displacement c of the center of said locus from the first receiver in each said paired combination;

computing the radius r of said locus;

and,

computing the point about which said locus is centered;

computing the intermediate points of intersection of all said loci corresponding to all said paired combinations; and

computing the actual points of intersection from said intermediate points of intersection of all said loci of points so as to determine an unambiguous location of said transmitting source.

16. Means for computing intermediate points of intersection of all said loci of points of claim 15, further comprising means for computing the j^th intermediate point of intersection by computing the Euclidian distance L between the center points of each of said loci of points according to

L=√

{square root over ((x_c2−

x_c1)²+(y_c2−

y_c1)²)}{square root over ((x_c2−

x_c1)²+(y_c2−

y_c1)²)}

wherein (x_c1, y_c1) and (x_c2, y_c2) are the coordinates of the centers of an i^th said locus of points having a radius r_i and an i^th+1 said locus of points having a radius r₂, respectively;

mapping said i^th locus center point onto the origin of x-y coordinate system and mapping said i^th+1 locus center point onto the x-axis of said coordinate system at a displacement L units along said x-axis from said i^th locus center point;

locating a third point within the first quadrant of said coordinate system, said third point being

displaced r₁ units from said first locus center point and r₂ units from said second locus center point so as to form the apex of a right triangle having base length L₁ and height h; and

displaced θ

units from said x-axis, counterclockwise about the origin;

so as to cause said third point to coincide with the coordinate (L₁, h).

17. Apparatus of claim 16, further comprising means for computing said base length L₁ according to

L₁=r₁ cos θ

.

18. Apparatus of claim 16, further comprising means for computing said height of said apex according to

h=r₁ sin θ

.

19. Apparatus of claim 16, further comprising means for computing the j^th+1 intermediate point of intersection by further

reflecting said j^th intermediate point of intersection across the x-axis such that the coordinates of said j^th+1 intermediate point of intersection coincide with (L₁, −

h).

20. Apparatus of claim 16, further comprising means for computing the k^th actual point of intersection by further

computing the counter clockwise angular displacement α

of the center point of the i^th+1 said locus from the x-axis about the origin according to

$\sin <br><br><br><br>\mathrm{\alpha <br><br>}=\frac{y_{c<br><br><br><br>2}-y_{c<br><br><br><br>1}}{L}$

$\cos <br><br><br><br>\mathrm{\alpha <br><br>}=\frac{x_{c<br><br><br><br>2}-x_{c<br><br><br><br>1}}{L}$

rotating said j^th intermediate point of intersection by a units with respect to said i^th locus center point;

translating said rotated j^th intermediate point of intersection by a number of units equivalent to the displacement of said mapped i^th locus center point from said i^th locus center point; and

computing the coordinates (x₃, y₃) of said translated and rotated j^th intermediate point of intersection according to

x₃=L₁ cos α

−

h sin α

+x_c1

y₃=h cos α

+L₁ sin α

+y_c1

said coordinates (x₃, y₃) being the location of said k^th actual point of intersection.

21. Apparatus of claim 16, further comprising means for computing the k^th+1 actual point of intersection by further

computing the counter clockwise angular displacement α

of the center point of the i^th+1 said locus from the x-axis about the origin according to

$\sin <br><br><br><br>\mathrm{\alpha <br><br>}=\frac{y_{c<br><br><br><br>2}-y_{c<br><br><br><br>1}}{L}$

$\cos <br><br><br><br>\mathrm{\alpha <br><br>}=\frac{x_{c<br><br><br><br>2}-x_{c<br><br><br><br>1}}{L}$

rotating said j^th+1 intermediate point of intersection by α

units with respect to said i^th locus center point;

translating said rotated j^th+1 intermediate point of intersection by a number of units equivalent to the displacement of said mapped i^th locus center point from said i^th locus center point; and

computing the coordinates (x₄, y₄) of said translated and rotated j^th+1 intermediate point of intersection according to

x₄=L₁ cos α

−

h sin α

+x_c1

y₄=h cos α

+L₁ sin α

+y_c1

said coordinates (x₄, y₄) being the location of said k^th+1 actual point of intersection.

22. Apparatus of claim 15, further comprising means for computing the number of said loci M according to

$M=\left(\begin{array}{c}N\\ 2\end{array}\right)=\frac{N^2-N}{2}$

wherein N represents the number of said receivers.

23. Method of claim 22, further comprising means for computing the number of intersections I between said loci according to

$I=2$

⁢

( M 2 ) = M 2 - M = N 4 4 - N 3 2 - N 2 4 + N 2 .

24. Apparatus of claim 15 further comprising means for computing a linear regression of received signal strength R_i versus distance.

25. Apparatus of claim 15 wherein said means for determining an unambiguous location of said transmitting source further comprising means for computing a clustering algorithm, said means for computing further comprising means for

computing the mean of the remaining actual points of intersection;

selecting said computed mean as the cluster center;

eliminating from the said cluster that actual point of intersection being furthest from said cluster center;

determining whether one-half of the original points of intersection have been eliminated;

IF one-half of the original points of intersection have NOT been eliminated,

THEN, returning to said step of computing the mean of the remaining actual points of intersection;

OTHERWISE, locating said transmitting source coincident with current said cluster center.

26. Apparatus of claim 15, where said means for computing said radius r, further comprises computing r according to

$r=$

D 2 ⁡

[ 1 1 + d - 1 1 - d ] 

.

27. Apparatus of claim 15, where said means for computing the displacement c, further comprises means for computing c according to

$c=\frac{D}{2}$

[ 1 1 + d - 1 1 - d ]

wherein D is the distance between said receivers in each said paired combination.

28. Apparatus of claim 15, where, in said means for computing the point about which said locus is centered, the coordinates (x_c, y_c) represent said point, and said means for computing further comprises computed (x_c, y_c) according to

$x_c=x_1+\frac{c}{D}$

⁢

( x 2 - x 1 )

$y_c=y_1+\frac{c}{D}<br><br><br><br>\left(y_2-y_1\right)$

wherein (x₁,y₁) and (x₂, y₂) are the coordinates of the first and the second said receivers in each said paired combination, respectively.

29. Apparatus for locating transmitting sources of a radio frequency (RF) signal intrusion into a wireless network, comprising:

a computer network;

a plurality of wireless intrusion detection processors;

said wireless intrusion detection processor being in communication with said computer network and all elements connected thereto;

said wireless intrusion detection processor further comprising at least one wireless intrusion detection sensor for measuring received signal strength of said transmitting sources;

said at least one wireless intrusion detection sensor further comprising a first software program comprising computer-executable instructions, stored on computer-readable media, and wherein said instructions, when executed, provide means for;

receiving intruding radio frequency signals;

measuring the received signal strength R_i of each of said intruding radio frequency signals;

communicating said measured signal strength R_i of each of said intruding radio frequency signals to said wireless intrusion detection processor within which it resides;

a wireless intrusion detection concentrator processor;

said wireless intrusion detection concentrator processor being in communication with said computer network and all elements connected thereto;

said wireless intrusion detection concentrator processor further comprising a second software program comprising computer-executable instructions, stored on computer-readable media, and wherein said instructions, when executed, provide means for;

for each paired combination of wireless intrusion detection sensors, computing one relative distance measurement d to the location of said transmitting sources;

said one relative distance measurement d being a function of said received signal strength R_i of each said wireless intrusion detection sensor in each said paired combination;

for each paired combination of said wireless intrusion detection sensors, computing the possible locations of said transmitting sources lying on the locus of points satisfying

d=[R₁/R₂]^1/2

further comprising;

computing the displacement c of the center of said locus from the first receiver in each said paired combination;

computing the radius r of said locus;

and,

computing the point about which said locus is centered;

computing the intermediate points of intersection of all said loci corresponding to all said paired combinations; and

computing the actual points of intersection from said intermediate points of intersection of all said loci of points so as to determine an unambiguous location of said transmitting source; and

an enterprise security management processor;

said enterprise security management processor being in communication with said computer network and all elements connected thereto;

said enterprise security management processor further comprising a third software program comprising computer-executable instructions, stored on computer-readable media, and wherein said instructions, when executed, provide means for;

displaying the geospace within which said wireless intrusion detection processors are located;

receiving and logging intrusion alerts; and

displaying intrusion time, location, signal strength and location of each said transmitting source of radio frequency (RF) signal intrusion.

30. Apparatus of claim 29 wherein said third software program comprises Hewlett Packard OpenView®

.

31. Apparatus of claim 29, where said means for computing said radius r, further comprises computing r according to

$r=$

D 2 ⁡

[ 1 1 + d - 1 1 - d ] 

.

32. Apparatus of claim 29, where said means for computing the displacement c, further comprises means for computing c according to

$c=\frac{D}{2}$

[ 1 1 + d - 1 1 - d ]

wherein D is the distance between said receivers in each said paired combination.

33. Apparatus of claim 29, where, in said means for computing the point about which said locus is centered, the coordinates (x_c, y_c) represent said point, and said means for computing further comprises computed (x_c, y_c) according to

$x_c=x_1+\frac{c}{D}$

⁢

( x 2 - x 1 )

$y_c=y_1+\frac{c}{D}<br><br><br><br>\left(y_2-y_1\right)$

wherein (x₁,y₁) and (x₂, y₂) are the coordinates of the first and the second said receivers in each said paired combination, respectively.