Method and system for location estimation in wireless networks

• US 7,406,320 B1
• Filed: 10/18/2004
• Issued: 07/29/2008
• Est. Priority Date: 12/08/2003
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Airtight Networks Incorporated (Arista Networks, Inc.)
• Inventors: Kumar, Manikant, Bhagwat, Pravin
• Primary Examiner(s): Eng; George
• Assistant Examiner(s): KIM, WESLEY LEO
• Application Number:
  US10/968,461
• Time in Patent Office: 1,380 Days
• Field of Search: 455/456.1, 342/463, 342/465, 342/453, 340/572.4, 726/25, 702/150
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0244 Accuracy or reliability of position solution or of measurements contributing thereto
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

A system and method for locating a wireless device in one or more wireless networks within a selected geographic region. The method includes generating a computer model of a selected geographic region including a layout and inputting information associated with one or more components of a wireless network into the computer model. The one or more components includes at least one or more sniffer devices. Additionally, the method includes determining signal intensity characteristics of the one or more components of the wireless network over at least a portion of the selected geographic region and receiving one or more wireless signals from one or more wireless devices. Moreover, the method includes determining a plurality of probabilities associated with a plurality of locations for at least one of the one or more wireless devices.

Claims

1. A method for locating a wireless device in one or more wireless networks within a selected geographic region, the method comprising:

generating a computer model of a selected geographic region, the computer model at least encoding a radio signal attenuation characteristic and a radio signal attenuation variability characteristic for each of a plurality of components of a layout of the selected geographic region, the each of the plurality of components being positioned within free space within the selected geographic region, the radio signal attenuation variability characteristic for the each component being indicative of projected variation for the radio signal attenuation characteristic for the each component due to at least one factor selected from the group consisting of movement of objects about the each component, operating state of the each component, and incomplete specification of physical structure of the each component;

inputting at least a spatial location information associated with one or more components of a wireless network into the computer model, the one or more components including at least one or more sniffer devices;

determining receive radio signal strength characteristics for the one or more components of the wireless network over at least a portion of the selected geographic region using the computer model, the receive radio signal strength characteristics including at least one indicator of predicted receive radio signal strength and at least one indicator of predicted variability in the receive radio signal strength at least one of the one or more components of the wireless network for each of a plurality of radio signals originating from a plurality of locations respectively within the portion of the selected geographic region, the determining including;

determining using the computer model at least a portion of a path of the each of the plurality of the originating radio signals, the portion of the path at least passing through or at least reflecting off at least one component of the layout from the plurality of components before receiving by the at least one of the one or more components of the wireless network;

computing contribution to the predicted receive radio signal strength from the at least the portion of the path based at least upon the radio signal attenuation characteristic of the at least one component of the layout; and

computing contribution to the predicted variability in the receive radio signal strength from the at least the portion of the path based at least upon the radio signal attenuation variability characteristic of the at least one component of the layout;

receiving one or more radio signals at the one or more components of the wireless network from a wireless device placed at a physical location;

measuring receive radio signal strengths of the one or more radio signals received at the one or more components of the wireless network respectively;

computing probabilities of the wireless device being located at the plurality of locations within the portion of the selected geographic region using the receive radio signal strength characteristics for the one or more components of the wireless network and the measured receive radio signal strengths of the one or more radio signals received at the one or more components of the wireless network;

displaying a first estimated physical location view for the wireless device on a display in relation to the layout of the selected geographic region; and

displaying a likelihood indicator associated with a first likelihood level on the display;

wherein the first estimated physical location view for the wireless device indicates one or more first estimated locations for the wireless device within the layout of the selected geographic region related to the first likelihood level, the one or more first estimated locations being from the plurality of locations.

2. The method of claim 1, and further comprising:

selecting a second likelihood level, the second likelihood level being different from the first likelihood level; and

displaying a second estimated physical location view for the wireless device on the display in relation to the layout of the selected geographic region;

wherein the second estimated physical location view for the wireless device indicates one or more second estimated locations for the wireless device within the layout of the selected geographic region related to the second likelihood level, the one or more second estimated locations being from the plurality of locations.

3. The method of claim 1 wherein at least one component of the layout from the plurality of components is a portion of a free space within the selected geographic region, the portion of the free space being characterized by a level movement of persons within the portion of the free space and the radio signal attenuation variability characteristic for the at least one component being related to the level of movement of persons within the portion of the free space.

4. The method of claim 1 wherein at least one component of the layout from the plurality of components is selected from the group consisting of wall, door, elevator shaft, and column.

5. The method of claim 4 wherein a level of uncertainty of radio propagation characteristics is associated with the each component of the layout.

6. The method of claim 1 wherein the first estimated physical location view for the wireless device is represented by at least one of a plurality of graphic features.

7. The method of claim 6 wherein the at least one of a plurality of graphic features is selected from the group consisting of color, gradation of color, fill pattern, contour, boundary, and region.

8. The method of claim 1 wherein the layout comprises a floor plan including one or more walls and one or more entrances.

9. The method of claim 1 wherein the layout comprises a top view of a selected outdoor region.

10. The method of claim 1, and further comprising inputting at least a radio signal receiving characteristic information associated with the one or more components of the wireless network into the computer model.

11. The method of claim 10 wherein the radio signal receiving characteristic information comprises antenna information associated with the one or more components of the wireless network.

12. The method of claim 11 wherein the antenna information is related to at least one selected from the group consisting of antenna type and antenna orientation.

13. The method of claim 1 wherein the at least one indicator of the predicted variability in the receive radio signal strength is a probability distribution associated with the receive radio signal strength.

14. The method of claim 1, and further comprising inputting to the computer model at least one or more physical dimensions of the each component of the layout or at least one or more material types of the each component of the layout.

15. The method of claim 1 wherein the radio signal attenuation characteristic and the radio signal attenuation variability characteristic for the each component of the layout of the selected geographic region are associated with pass through attenuation.

16. The method of claim 1 wherein the radio signal attenuation characteristic and the radio signal attenuation variability characteristic for the each component of the layout of the selected geographic region are associated with reflection attenuation.

17. The method of claim 1 wherein the determining the receive radio signal strength characteristics for the at least one of the one or more components of the wireless network over the at least the portion of the selected geographic region using the computer model being free from on-site measurements of receive radio signal strengths at the at least one of the one or more components of the wireless network.

18. A computer based system for location estimation in wireless networks, the system comprising:

means for generating a computer model of a selected geographic region, the computer model at least encoding a radio signal attenuation characteristic and a radio signal attenuation variability characteristic for each of a plurality of components of a layout of the selected geographic region, the each of the plurality of components being positioned within free space within the selected geographic region, the radio signal attenuation variability characteristic for the each component being indicative of projected variation for the radio signal attenuation characteristic for the each component due to at least one factor selected from the group consisting of movement of objects about the each component, operating state of the each component, and incomplete specification of physical structure of the each component;

means for inputting at least a spatial location information associated with one or more components of a wireless network into the computer model, the one or more components including at least one or more sniffer devices;

means for determining receive radio signal strength characteristics for the one or more components of the wireless network over at least a portion of the selected geographic region using the computer model, the receive radio signal strength characteristics including at least one indicator of predicted receive radio signal strength and at least one indicator of predicted variability in the receive radio signal strength at least one of the one or more components of the wireless network for each of a plurality of radio signals originating from a plurality of locations respectively within the portion of the selected geographic region, the determining including;

determining using the computer model at least a portion of a path of the each of the plurality of the originating radio signals, the portion of the path at least passing through or at least reflecting off at least one component of the layout from the plurality of components before receiving by the at least one of the one or more components of the wireless network;

computing contribution to the predicted receive radio signal strength from the at least the portion of the path based at least upon the radio signal attenuation characteristic of the at least one component of the layout; and

computing contribution to the at least one indicator of the predicted variability in the receive radio signal strength from the at least the portion of the path based at least upon the radio signal attenuation variability characteristic of the at least one component of the layout;

means for receiving one or more radio signals at the one or more components of the wireless network from a wireless device placed at a physical location;

means for measuring receive radio signal strengths of the one or more radio signals received at the one or more components of the wireless network respectively;

means for computing probabilities of the wireless device being located at the plurality of locations within the portion of the selected geographic region using the receive radio signal strength characteristics for the one or more components of the wireless network and the measured receive radio signal strengths of the one or more radio signals received at the one or more components of the wireless network;

means for displaying a first estimated physical location view for the wireless device on a display in relation to the layout of the selected geographic region; and

means for displaying a likelihood indicator associated with a first likelihood level on the display;

wherein the first estimated physical location view for the wireless device indicates one or more first estimated locations for the wireless device within the layout of the selected geographic region related to the first likelihood level, the one or more first estimated locations being from the plurality of locations.

19. The system of claim 18 wherein the determining the receive radio signal strength characteristics for the at least one of the one or more components of the wireless network over the at least the portion of the selected geographic region using the computer model being free from on-site measurements of receive radio signal strengths at the at least one of the one or more components of the wireless network.