Efficient storage and fast matching of wireless spatial signatures

• US 6,104,344 A
• Filed: 03/24/1999
• Issued: 08/15/2000
• Est. Priority Date: 03/24/1999
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: US Wireless Corp. (Vontier Corp.)
• Inventors: Radionov, Vladimir, Jayaraman, Sriram, Lebedev, Gennadi, Wax, Mati, Hilsenrath, Oliver
• Primary Examiner(s): Issing, Gregory C.
• Application Number:
  US09/275,655
• Time in Patent Office: 510 Days
• Field of Search: 342/457, 342/378, 342/450, 342/451, 342/453
• US Class Current: 342/378
• CPC Class Codes: G01S 1/026 of associated receivers
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A method for determining a geographical location from a measured wireless signal signature comprises calculating from the measured wireless signal signature a multi-dimensional signature vector, wherein each component of the vector measures a degree of coincidence between the measured wireless signal signature and a calibrated signal signature stored in a calibration table. The method also includes matching the signature vector with vectors in a set of multi-dimensional calibrated vectors. The matching uses a procedure comprising searching a hierarchical tree structure and eliminating nodes that cannot contain the best match vector. Within the remaining nodes, the search eliminates individual vectors that cannot be the best match vector, and selects one or more vectors in the set of multi-dimensional calibrated vectors, where the matched vectors correspond to calibrated geographical locations.

Claims

1. In a wireless location finding system, a computer-implemented method for determining a geographical location from a measured wireless signal signature, the method comprising:

calculating from the measured wireless signal signature a multi-dimensional vector v, wherein each component of v measures a degree of coincidence between the measured wireless signal signature and a calibrated signal signature stored in a calibration table;

matching v with matched vectors in a set of multi-dimensional calibrated vectors v₁, . . . , v_N, using a procedure comprising searching a hierarchical tree structure containing the calibrated vectors v₁, . . . , v_N, and selecting the matched vectors from leaf nodes in the tree, where the matched vectors correspond to calibrated geographical locations.

2. The method of claim 1 wherein the calibrated signal signature stored in the calibration table comprises a calibrated bin covariance matrix R calculated from covariances measured within a geographical bin.

3. The method of claim 2 wherein the bin covariance matrix R is an average of sub-bin covariance matrices calculated from covariance matrices measured in sub-bins of the geographical bin.

4. The method of claim 1 wherein each vector v_k in the set of multi-dimensional calibrated vectors v₁, . . . , v_N is calculated from v_k =[p₁^T r_k, . . . , p_N^T r_k ]^T, where r_k is a p² -dimensional vector derived from a calibrated signal covariance matrix R_k and p_i is a p² -dimensional vector derived from a calibrated signal signature.

5. The method of claim 1 wherein searching the hierarchical tree structure comprises using a branch and bound technique to eliminate from the tree structure nodes not containing a best matched vector.

6. The method of claim 1 wherein searching the hierarchical tree structure comprises using precomputed distances between vectors in a leaf node to eliminate from the leaf node vectors not possibly being a best matched vector.

7. The method of claim 6 wherein searching the hierarchical tree structure further comprises representing v and a vector v_k in the leaf node by lower-dimensional vectors r and r_k, respectively, and calculating a difference between G r_k and G r, where G^T G is the Cholesky factorization of P^T P=[p₁^T . . . p₁^T . . . p_N^T ]^T, and where p₁, . . . , p_N are N-dimensional vectors derived from calibrated subspaces.

8. The method of claim 7 wherein searching the hierarchical tree structure further comprises projecting v and a vector v_k in the leaf node onto a subspace of a calibration table matrix, wherein the subspace is spanned by a set of dominant eigenvectors of the calibration table matrix, and calculating a difference between the projected vectors.