LOCATION ESTIMATION SYSTEM, METHOD AND PROGRAM

• US 20090109095A1
• Filed: 10/24/2008
• Published: 04/30/2009
• Est. Priority Date: 10/25/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Takahashi, Toshihiro, Tsuboi, Yuta, Kashima, Hisashi, Suzuki, Shoko, Hido, Shohei, Takahashi, Rikiya, Tajima, Akira, Ide, Tsuyoshi
• Granted Patent: US 8,138,974 B2
• Time in Patent Office: Days
• US Class Current: 342/417
• CPC Class Codes: G01S 5/02521 using a radio-map

Abstract

A location estimation method using label propagation. The achieved location estimation method is robust to variations in radio signal strengths and is highly accurate by using the q-norm (0<q<1), especially, for calculating the similarities among radio signal strength vectors. The accuracy in location estimation is further improved by putting more importance on the time-series similarities. Specifically, the time-series similarity is calculated by using time-series values indicating the temporal order of radio signal strengths during the measurement. If the time-series similarity is larger than the similarity between the radio signal strength vectors, the time-series similarity is preferentially used. The exponential attenuation function can also be used for calculating the similarities, instead of the q norm (0<q<1).

Claims

1. A system for estimating a location label of a vector dataset without any location label from a plurality of vector datasets respectively with location labels using a computer, the system comprising:

storage means provided in the computer;

means for storing the vector datasets in the storage means of the computer;

means for calculating the similarity between the vector dataset without any location label and each neighboring vector dataset with a location label, by using any one of a q-norm wherein 0<

q<

1 and an exponential attenuation function; and

means for estimating the location label of the vector data without any location label from the calculated similarities.

2. The system according to claim 1, wherein the similarities are calculated by means of the following expression using the q-norm,

W_X^(i,j)=exp(−

||X⁽ⁱ⁾−

X^(j)||_q^q),  

 

[Expression 1]

where X⁽ⁱ⁾ and X^(j) denote i-th and j-th vectors, respectively, and

$\begin{array}{cc}{<br><br>X<br><br>}_q={\left(\underset{d=1}{\overset{n}{\sum <br><br>}}<br><br>\frac{{<br><br>X_d<br><br>}^q}{{\mathrm{\sigma <br><br>}}_d}\right)}^{\frac{1}{q}}& \left[\mathrm{Expression}<br><br><br><br>2\right]\end{array}$

where n denotes the number of dimensions of the vector and 0<

σ

_d<

∞

.

3. The system according to claim 1, wherein the similarities are calculated by means of the following expression with an exponential attenuation function,

$\begin{array}{c}{W}_X^{\left(i,j\right)}=\prod _{}^{}\end{array}$

d = 1 n 

[ 1 + 1 v 

( X d ( i ) - X d ( j ) σ

d ) 2 ] - ( v + 1 ) 2 [ Expression 



3 ]

where n denotes the number of dimensions of the vector, 0<

σ

_d<

∞

, and ν

is a number larger than 1.

4. The system according to claim 1, wherein the similarities are calculated by means of the following expression with an exponential attenuation function,

$\begin{array}{c}{W}_X^{\left(i,j\right)}=\prod _{}^{}\end{array}$

d = 1 n 

[ 1 + 1 β





X d ( i ) - X d ( j ) σ

d 

] - β

[ Expression 



4 ]

where n denotes the number of dimensions of the vector, 0<

σ

_d<

∞

, and β

is a number larger than 1.

5. A location estimation method for estimating a location from radio signal strength datasets by means of a computer, the method comprising the steps of:

preparing a plurality of radio signal strength vector datasets with location labels and a plurality of radio signal strength vector datasets without location labels, respectively, and then storing the prepared datasets in storage means of the computer;

setting, by means of the computer, an initial value of the plausibility score f⁽ⁱ⁾(c) wherein i=1 . . . N and wherein N denotes the number of all the prepared radio signal strength vector datasets such that each of the radio signal strength vector datasets with location labels and the radio signal strength vector datasets without location labels has a location label c;

calculating, using the computer, the similarity W^(i,j) for each combination of i and j wherein i,j=1 . . . N, by using any one of a q-norm wherein 0<

q<

1, of the radio signal strength vector and an exponential attenuation function;

calculating, by means of the computer, f⁽ⁱ⁾(c) for each of the radio signal strength vector datasets without location labels, by using the following expression

$\begin{array}{cc}{f}^{\left(i\right)}<br><br>\left(c\right)=\frac{\underset{j}{\sum <br><br>}<br><br>W^{\left(i,j\right)}<br><br>f^{\left(j\right)}<br><br>\left(c\right)}{\underset{j}{\sum <br><br>}<br><br>W^{\left(i,j\right)}};<br><br><br><br>\mathrm{and}& \left[\mathrm{Expression}<br><br><br><br>5\right]\end{array}$

iteratively executing the step of calculating f⁽ⁱ⁾(c) by means of the computer.

6. The method according to claim 5, wherein the step of calculating the similarity W^(i,j) includes the steps of:

calculating the temporal similarity W_t^(i,j); and

choosing, as the similarity W^(i,j), one having the larger value from the temporal similarity W_t^(i,j) and the spatial similarity calculated by using any one of the q-norm and the exponential attenuation function.

7. The method according to claim 5, wherein the spatial similarities are calculated using the following expression using the q-norm,

W_X^(i,j)=exp(−

||X⁽ⁱ⁾−

X^(j)||_q^q)  

 

[Expression 6]

where X⁽ⁱ⁾ denotes the i-th radio signal strength vector, and

$\begin{array}{cc}{<br><br>X<br><br>}_q={\left(\underset{d=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>\frac{{<br><br>X_d<br><br>}^q}{{\mathrm{\sigma <br><br>}}_d}\right)}^{\frac{1}{q}}& \left[\mathrm{Expression}<br><br><br><br>7\right]\end{array}$

where n denotes the number of dimensions of the radio signal strength vector, and each of 0<

σ

_d<

∞

wherein d=1, . . . , n denotes a constant scale parameter.

8. The method according to claim 7, wherein both q and σ

are set at 0.5.

9. The method according to claim 5, wherein the spatial similarities are calculated by using the following expression with an exponential attenuation function,

$\begin{array}{c}{W}_X^{\left(i,j\right)}=\prod _{}^{}\end{array}$

d = 1 n 



[ 1 + 1 v 

( X d ( i ) - X d ( j ) σ

d ) 2 ] - ( v + 1 ) 2 [ Expression 



8 ]

where X⁽ⁱ⁾ and X^(j) denote i-th and j-th vectors, respectively;

n denotes the number of dimensions of the vector;

0<

σ

_d<

∞

; and

v is a number larger than 1.

10. The method according to claim 5, wherein the spatial similarities are calculated by using the following expression using exponential attenuation function,

$\begin{array}{c}{W}_X^{\left(i,j\right)}=\prod _{}^{}\end{array}$

d = 1 n 



[ 1 + 1 β





X d ( i ) - X d ( j ) σ

d 

] - β

[ Expression 



9 ]

where X⁽ⁱ⁾ and X^(j) denote i-th and j-th vectors, respectively;

n denotes the number of dimensions of the vector;

0<

σ

_d<

∞

; and

β

is a number larger than 1.

11. The method according to claim 6, wherein the temporal similarity W_t^(i,j) is calculated by using the following expression,

W_t^(i,j)=p·

δ

(TID⁽ⁱ⁾=TID^(j))·

δ

(|t⁽ⁱ⁾−

t^(j)|=1)  

 

[Expression 10]

where 0<

p≦

1 is a constant parameter, TID⁽ⁱ⁾ is the trace ID to which the i-th vector belongs, and t⁽ⁱ⁾ is the time of observation of the i-th vector.

12. The method according to claim 6, wherein the temporal similarity W_t^(i,j) is calculated by using the following expression,

$\begin{array}{c}{W}_t^{\left(i,j\right)}=p·\end{array}$

δ



( TID ( i ) = TID ( j ) ) ·

exp 

( - 

t ( i ) - t ( j ) 

r r ) 



where [ Expression 



11 ] 

X 

r = ( 

X 

r σ

) 1 r , [ Expression 



12 ]

and where 0<

p≦

1, 0<

r≦

2, and 0<

σ

<

∞

.

13. A program for estimating a location from radio signal strength datasets by means of a computer, the program causing the computer to execute the steps of:

preparing a plurality of radio signal strength vector datasets respectively with location labels and a plurality of radio signal strength vector datasets without location labels, and then storing the prepared datasets into storage means of the computer;

setting an initial value of the plausibility score f⁽ⁱ⁾(c) wherein i=1 . . . N and wherein N denotes the number of all the prepared radio signal strength vector datasets that each of the radio signal strength vector datasets with location labels and the radio signal strength vector datasets without location labels has a location label c;

calculating the similarity W^(i,j) for each combination of i and j wherein i,j=1 . . . N, by using any one of a q-norm wherein 0<

q<

1, of the radio signal strength vector and an exponential attenuation function;

calculating f⁽ⁱ⁾(c) for each of the radio signal strength vector datasets without location labels, by using the following expression

$\begin{array}{cc}{f}^{\left(i\right)}<br><br>\left(c\right)=\frac{\underset{j}{\sum <br><br>}<br><br>W^{\left(i,j\right)}<br><br>f^{\left(j\right)}<br><br>\left(c\right)}{\underset{j}{\sum <br><br>}<br><br>W^{\left(i,j\right)}};<br><br><br><br>\mathrm{and}& \left[\mathrm{Expression}<br><br><br><br>13\right]\end{array}$

iteratively executing the step of calculating f⁽ⁱ⁾(c).

14. The program according to claim 13, wherein the step of calculating the similarity W^(i,j) includes the steps of:

calculating temporal similarity W_t^(i,j); and

choosing, as the similarity W^(i,j), one having the larger value from the temporal similarity W_t^(i,j) and the spatial similarity calculated by using any one of the q-norm and the exponential attenuation function.

15. The program according to claim 13, wherein the q-norm is calculated by using the following expression,

W_X^(i,j)=exp(−

||X⁽ⁱ⁾−

X^(j)||_q^q)  

 

[Expression 14]

where X⁽ⁱ⁾ denotes the i-th radio signal strength vector and

$\begin{array}{cc}{<br><br>X<br><br>}_q={\left(\underset{d=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>\frac{{<br><br>X_d<br><br>}^q}{{\mathrm{\sigma <br><br>}}_d}\right)}^{\frac{1}{q}}& \left[\mathrm{Expression}<br><br><br><br>15\right]\end{array}$

where n denotes the number of dimensions of the radio signal strength vector, and each of 0<

σ

_d<

∞

wherein d=1, . . . n denotes a constant scale parameter.

16. The program according to claim 15, wherein both q and σ

are set at 0.5.

17. The program according to claim 14, wherein the spatial similarity is calculated by using the following expression using exponential attenuation function

$W_X^{\left(i,j\right)}=\prod _{}^{}$

d = 1 n 



[ 1 + 1 v 

( X d ( i ) - X d ( j ) σ

d ) 2 ] - ( v + 1 ) 2

where X⁽ⁱ⁾ and X^(j) denote i-th and j-th vectors, respectively;

n denotes the number of dimensions of the vector;

0<

σ

_d<

∞

; and

v is a number larger than 1.

18. The program according to claim 14, wherein the spatial similarity is calculated by using the following expression with an exponential attenuation function,

$\begin{array}{c}{W}_X^{\left(i,j\right)}=\prod _{}^{}\end{array}$

d = 1 n 

[ 1 + 1 β





X d ( i ) - X d ( j ) σ

d 

] - β

[ Expression 



17 ]

where X⁽ⁱ⁾ and X^(j) denote i-th and j-th vectors, respectively;

n denotes the number of dimensions of the vector;

0<

σ

_d<

∞

; and

β

is a number larger than 1.

19. The method according to claim 14, wherein the temporal similarity W_t^(i,j) is calculated by using the following expression,

W_t^(i,j)=p·

δ

(TID⁽ⁱ⁾=TID^(j))·

δ

(|t⁽ⁱ⁾−

t^(j)|=1)  

 

[Expression 18]

where 0<

q≦

1 is a constant parameter, TID⁽ⁱ⁾ is the trace ID to which the i-th vector belongs, and t⁽ⁱ⁾ is the time of observation of the i-th vector.

20. The method according to claim 14, wherein the temporal similarity W_t^(i,j) is calculated by using the following expression,

W_t^(i,j)=p·

δ

(TID⁽ⁱ⁾=TID^(j))·

δ

exp(−

||t⁽ⁱ⁾−

t^(j)||_r^r)  

 

[Expression 19]

where

$\begin{array}{cc}{<br><br>X<br><br>}_r={\left(\frac{{<br><br>X<br><br>}^r}{\mathrm{\sigma <br><br>}}\right)}^{\frac{1}{r}},& \left[\mathrm{Expression}<br><br><br><br>20\right]<br><br>\end{array}$

and where 0<

p≦

1, 0<

r≦

2, and 0<

σ

<

∞

.

21. A system for estimating a location from radio signal strength datasets by means of a computer, the system comprising:

storage means;

means for preparing a plurality of radio signal strength vector datasets respectively with location labels and a plurality of radio signal strength vector datasets without location labels, and then storing the prepared datasets into the storage means;

means for setting an initial value of the plausibility score f⁽ⁱ⁾(c) wherein i=1 . . . N and wherein N denotes the number of all the prepared radio signal strength vector datasets that each of the radio signal strength vector datasets with location labels and the radio signal strength vector datasets without location labels has a location label c;

means for calculating the similarity W^(i,j) for each combination of i and j wherein i,j=1 . . . N by using any one of a q-norm wherein 0<

q<

1 of the radio signal strength vector and an exponential attenuation function;

means for calculating f⁽ⁱ⁾(c) for each of the radio signal strength vector datasets without location labels, by using the following expression

$\begin{array}{cc}{f}^{\left(i\right)}<br><br>\left(c\right)=\frac{\underset{j}{\sum <br><br>}<br><br>W^{\left(i,j\right)}<br><br>f^{\left(j\right)}<br><br>\left(c\right)}{\underset{j}{\sum <br><br>}<br><br>W^{\left(i,j\right)}};<br><br><br><br>\mathrm{and}& \left[\mathrm{Expression}<br><br><br><br>21\right]\end{array}$

means for iteratively executing the step of calculating f⁽ⁱ⁾(c).

22. The system according to claim 21, wherein the means of calculating the similarity W^(i,j) includes:

means for calculating the temporal similarity W_t^(i,j); and

means of choosing as the similarity W^(i,j), one having the larger value from the temporal similarity W_t^(i,j) and the spatial similarity calculated by using any one of the q-norm and the exponential attenuation function.

23. The system according to claim 21, wherein the q-norm is calculated by using the following expression,

W_X^(i,j)=exp(−

||X⁽ⁱ⁾−

X^(j)||_q^q)  

 

[Expression 22]

where X⁽ⁱ⁾ denotes the i-th radio signal strength vector and

$\begin{array}{cc}{<br><br>X<br><br>}_q={\left(\underset{d=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>\frac{{<br><br>X_d<br><br>}^q}{{\mathrm{\sigma <br><br>}}_d}\right)}^{\frac{1}{q}}& \left[\mathrm{Expression}<br><br><br><br>23\right]\end{array}$

where n denotes the number of dimensions of the radio signal strength vector, and each of 0<

σ

_d<

∞

wherein d=1, . . . , n denotes a constant scale parameter.

24. The system according to claim 23, wherein both q and σ

are set at 0.5.

25. The system according to claim 22, wherein the spatial similarity is calculated by using the following expression with an exponential attenuation function,

$\begin{array}{c}{W}_X^{\left(i,j\right)}=\prod _{}^{}\end{array}$

d = 1 n 



[ 1 + 1 v 

( X d ( i ) - X d ( j ) σ

d ) 2 ] - ( v + 1 ) 2 [ Expression 



24 ]

where X⁽ⁱ⁾ and X^(j) denote i-th and j-th vectors, respectively;

n denotes the number of dimensions of the vector;

0<

σ

_d<

∞

; and

v is a number larger than 1.

26. The system according to claim 22, wherein the spatial similarity is calculated by using the following expression with an exponential attenuation function,

$\begin{array}{c}{W}_X^{\left(i,j\right)}=\prod _{}^{}\end{array}$

d = 1 n 

[ 1 + 1 β





X d ( i ) - X d ( j ) σ

d 

] - β

[ Expression 



25 ]

where X⁽ⁱ⁾ and X^(j) denote i-th and j-th vectors, respectively;

n denotes the number of dimensions of the vector;

0<

σ

_d<

∞

; and

β

is a number larger than 1.

27. The system according to claim 22, wherein the temporal similarity W_t^(i,j) is calculated by using the following expression,

W_t^(i,j)=p·

δ

(TID⁽ⁱ⁾=TID^(j))·

δ

(|t⁽ⁱ⁾−

t^(j)|=1)  

 

[Expression 26]

where 0<

p≦

1 is a constant parameter, TID⁽ⁱ⁾ is the trace ID to which the i-th vector belongs, and t⁽ⁱ⁾ is the time of observation of the i-th vector.

28. The system according to claim 22, wherein the temporal similarity W_t^(i,j) is calculated by using the following expression,

$\begin{array}{c}{W}_t^{\left(i,j\right)}=p·\end{array}$

δ



( TID ( i ) = TID ( j ) ) ·

exp 

( - 

t ( i ) - t ( j ) 

r r ) 



where [ Expression 



27 ] 

X 

r = ( 

X 

r σ

) 1 r , [ Expression 



28 ]

and where 0<

p≦

1, 0<

r≦

2, and 0<

σ

<

∞

.