WIFI MULTI-BAND FINGERPRINT-BASED INDOOR POSITIONING

Abstract

A method for determining the position of a mobile or asset in an indoor location in a radio frequency system, the method comprising: a) generating a Wi-Fi multi-band fingerprint database using at least one multi-band Wi-Fi access point configured to simultaneously transmit multiple frequency band wireless signals; b) selecting a most probable frequency band having the highest probability function for a target location of the mobile or asset given one or more measured signals; c) selecting one or more fingerprints from the Wi-Fi multi-band fingerprint database in dependence on the selected frequency band and selecting a measured signal that is needed to determine the location in dependence on the said most probable frequency band for each Wi-Fi access point; and d) comparing the selected measured signal and the selected one or more fingerprints to determine the location of the measured signal in dependence on a location estimation algorithm.

Claims

1. A method for determining the position of a mobile or asset in an indoor location in a radio frequency transmission and receive system, the method comprising: a) generating a Wi-Fi multi-band fingerprint database using at least one multi-band Wi-Fi access point configured to simultaneously transmit multiple frequency band wireless signals; b) selecting, from the multiple frequency band wireless signals transmitted by each Wi-Fi access point, a most probable frequency band having the highest probability function for a target location of the mobile or asset given one or more measured signals; c) selecting one or more fingerprints from the Wi-Fi multi-band fingerprint database in dependence on the selected most probable frequency band and selecting a measured signal that is needed to determine the location in dependence on the said most probable frequency band for each Wi-Fi access point; and d) comparing the selected measured signal and the selected one or more fingerprints to determine the location of the measured signal in dependence on a location estimation algorithm.

2. The method as claimed in claim 1, wherein generating the Wi-Fi multi-band fingerprint database comprises: a) defining a plurality of reference points having known locations in an indoor area; b) getting a plurality of received signal strengths for a plurality of detected Wi-Fi signals from a plurality of access points at the respective defined reference points; and c) storing the plurality of received signal strengths and corresponding location information of the respective access points at the respective reference points as the Wi-Fi multi-band fingerprint database.

3. The method as claimed in claim 2, wherein getting the plurality of received signal strengths comprises: measuring the plurality of received signal strengths for the plurality of detected Wi-Fi signals from the plurality of access points at the respective defined reference points.

4. The method as claimed in claim 2 or 3, wherein getting the plurality of received signal strengths comprises: modelling an indoor scenario and network; and simulating the plurality of received signal strengths from the plurality of access points at the respective defined reference points.

5. The method as claimed in any preceding claim, wherein the Wi-Fi multi-band fingerprint database further comprises location information, average received signal strength and variance of received signal strength, a fingerprint at /th reference point being represented by ${\left(x,y,z,o\right)}_l,{\left[\begin{array}{cccc}{\stackrel{\_}{\mathrm{RSS}}}_{1,1},& {\stackrel{\_}{\mathrm{RSS}}}_{1,2},& \mathrm{.Math.}.Math.,& {\stackrel{\_}{\mathrm{RSS}}.Math.}_{1,B}\\ {\stackrel{\_}{\mathrm{RSS}}}_{2,1},& {\stackrel{\_}{\mathrm{RSS}}}_{2,2},& \mathrm{.Math.}.Math.,& {\stackrel{\_}{\mathrm{RSS}}.Math.}_{2,B}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ {\stackrel{\_}{\mathrm{RSS}}}_{K,1},& {\stackrel{\_}{\mathrm{RSS}}}_{K,2},& \mathrm{.Math.}.Math.,& {\stackrel{\_}{\mathrm{RSS}}.Math.}_{K,B}\end{array}\right]}_l,.Math.{\left[\begin{array}{cccc}{}_{1,1},& {}_{1,2},& \mathrm{.Math.}.Math.,& {.Math.}_{1,B}\\ {}_{2,1},& {}_{2,2},& \mathrm{.Math.}.Math.,& {.Math.}_{2,B}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ {}_{K,1},& {}_{K,2},& \mathrm{.Math.}.Math.,& {.Math.}_{K,B}\end{array}\right]}_l$ where x, y, and z are three-dimension location coordinates at an /th reference point, and o is an orientation with East, South, West, and North at the /th reference point, RSS.sub.i,b is an average received signal strength from an ith access point and a bth band at the /th reference point, and .sub.i,b is a variance of received signal strength from the ith access point and a bth band at the /th reference point.

6. The method as claimed in claim 5, wherein the said average received signal strength is the mean value of the plurality of received signal strengths per access point per band at one reference point during a sampling period, and the variance is the variance value of all received signal strengths per access point per band at one reference point during a sampling period.

7. The method as claimed in any preceding claim, wherein the said most probable frequency band is selected by a multi-band diversity combining method which com prises: a) getting a probability function, P(s.sub.i,b|l), that a signal s.sub.i,b is received at a given location / in dependence on the said multi-band fingerprint database, wherein s.sub.i,b is the measured received signal strengths from an ith Wi-Fi access point and a bth frequency band at the given location l; b) calculating the probability function P(l|s.sub.i,b) at the target location / based on the given signals s.sub.i,b; and c) finding the frequency band with the highest probability function, $\arg .Math..Math.\underset{b}{\max }.Math.P\left(l{s}_{i,b}\right),$ for each access point.

8. The method as claimed in claim 7, wherein the probability function P(s.sub.i,b|l) is calculated by: a) surveying received signal strength multiple times at each of at least one survey location, and getting a statistically significant number of occurrences of each possible signal; and b) approximating the probability function P(s.sub.i,b|l) by maximum likelihood methods.

9. The method as claimed in claim 8, wherein the said maximum likelihood is modelled by parametric distributions.

10. The method as claimed in any preceding claim, wherein selecting the measured signal further comprises: a) measuring multi-band received signal strengths at the target location from each access point; and b) reporting the multi-band measured received signal strengths of each access point to a server.

11. The method as claimed in claim 10, wherein the reported multi-band measured received signal strengths for each access point are represented by $\left(x^{},y^{},z^{},o\right),\left[\begin{array}{cccc}{s}_{1,1},& s_{1,2},& \mathrm{.Math.}.Math.,& {s.Math.}_{1,B}\\ s_{2,1},& s_{2,2},& \mathrm{.Math.}.Math.,& {s.Math.}_{2,B}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ s_{K,1},& s_{K,2},& \mathrm{.Math.}.Math.,& {s.Math.}_{K,B}\end{array}\right]$ where x, y, and z are the coordinate variables of the target location, o is an orientation with East, South, West, and North at the target location, s.sub.i,b is a measured received signal strength from an ith access point and a bth band at the target location.

12. The method as claimed in claim 11, wherein the orientation o is obtained from one or more orientation sensors in the mobile or asset.

13. The method as claimed in any preceding claim, wherein selecting the one or more fingerprints from the Wi-Fi multi-band fingerprint database in dependence on the selected most probable frequency band and selecting the measured signal further com prises: a) generating a best frequency band set b=(b.sub.1,b.sub.2, . . . , b.sub.K).sup.T for each of K access points, wherein b.sub.i is the most probable frequency band of an ith Wi-Fi access point; and b) selecting a fingerprint set (x, y, z, o).sub.l, (RSS.sub.1,b.sub.1, RSS.sub.2,b.sub.2, . . . , RSS.sub.K,b.sub.K).sub.l.sup.T in dependence on the best frequency band set, where x, y, and z are three-dimension location coordinates, and o is an orientation with East, South, West, and North at an lth defined reference point, and RSS.sub.1,b.sub.i is an average received signal strength from an ith access point at the selected most probable frequency band; and c) selecting the measured signal set (x, y, z, o), (s.sub.1,b.sub.1, s.sub.2,b.sub.2, . . . , s.sub.K,b.sub.K).sup.T based on the frequency band set, where x , y , and z are the coordinates of target location, o is the orientation with East, South, West, and North at the target location, and s.sub.1,b.sub.i is the measured received signal strength from the ith Wi-Fi access point and a bth most probable frequency band at the target location.

14. The method as claimed in any preceding claim, wherein the said location estimation algorithm is a nearest neighbour with closest distance between the selected fingerprint set and the selected given signal set.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0035] The present invention will now be described by way of example with reference to the accompanying drawings. In the drawings:

[0036] FIG. 1 shows the traditional fingerprint-based indoor localization method

[0037] FIG. 2 shows a block diagram of a method for positioning indoor location based on multi-band diversity fingerprint.

[0038] FIG. 3 shows a block diagram of an example of the inventive method.

[0039] FIG. 4 shows a flow chart of a selection diversity combining algorithm.

DETAILED DESCRIPTION OF THE INVENTION

[0040] The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art.

[0041] The general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

[0042] Hereinafter, the present invention will be further described in detail with reference to the accompanying drawings. The invention is described in connection with wireless communications and more particularly relates to indoor positioning method based on fingerprint WiFi system with multi-band diversity combining, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents.

[0043] Traditional Wi-Fi fingerprinting is usually conducted in two phases: an offline phase followed by an online phase, as shown in Fig.1. In the offline phase, a site survey 101 is conducted to collect the vectors of received signal strength indicator (RSSI) of all the detected Wi-Fi signals from different access points (APs) at many reference points (RPs) of known locations. Hence, all the RSSI vectors form the fingerprints of the site and are stored at a database 102. In the online phase, a user (or target) 103 samples or measures an RSSI vector at the position and reports it to the server 104, the server compares the received target vector with the stored fingerprints. The target position is estimated based on the most similar neighbours, the set of RPs whose fingerprints closely match the target's RSSI.

[0044] A major challenge facing WiFi fingerprint location determination is that signal strength of received radio signals is a dynamic parameter and varies widely with changes in the environment due to fading, shadowing, barrier in the building etc. Such variation puts a limit on the resolution achievable by the location determination system.

[0045] Diversity has been a well-researched topic in the field of communications with the view of combating fading. It involves combing multiple uncorrelated signal envelopes in order to effectively reduce the variation in received signal strength values and as a result, improve accuracy is achieved in location determination.

[0046] Motivation for use of diversity techniques stems from the fact that the probability of simultaneous deep fading occurring on two or multiple uncorrelated fading channels is much lower than the probability of a deep fading occurring on a single branch system. Thus, employing a new selection combining approach on top of any diversity technique which assures sufficiently uncorrelated frequency channels will reduce the variance in signal strength. The rational for considering this variable is two-fold: (i) as received signal strength is inherently time varying, the signals that vary less would more likely result in better accuracy of localization; (ii) RSS variance is the most influential factor determining the accuracy of a WiFi fingerprinting system.

[0047] Current in a typical environment today with APs transmitter is dual band of WLAN (Wireless Local Area Network), i.e. 2.4 GHz and 5 GHz are simultaneously transmitted, and receivers can support both 2.4 GHz and 5 GHz bands to collect multiple samples for each measurement location. Therefore, from a WiFi fingerprinting system perspective, a measurement sample (WiFi scan) obtained either during the radio map construction phase or subsequent runtime positioning phase will likely include a mix signals of 2.4 GHz and 5 GHz channels. From the propagation characteristic, 2.4 GHz channel has low propagation loss, and result in high received signal strength, but the strong interference will result in the RSS fluctuation, and then high variance of RSS. 5 GHz channel has high propagation effect, but is less crowded and low interference due to more available spectrum. This in turn could impact the accuracy of the WiFi fingerprinting system as signals from these two bands behave differently.

[0048] This invention uses the selection diversity combining over the multiple uncorrelated frequency channels results in reduced variance in signal strength, and then the location accuracy based on fingerprint can be improved. The fingerprint consisted of two phases, which are training and positioning phases, as shown in FIG. 2. In training phases, the multi-band RSS at each position from measurement or simulation 201 are used to create a multi-band fingerprint database 202, and the created database is used as reference for the localization 203 by positioning algorithm 205 in positioning phase based on the selection combining of multi-band RSS 204. The detail description is shown in FIG. 3.

[0049] The invention discloses an indoor positioning method based on fingerprint Wi-Fi system with multi-band diversity combining. The indoor positioning method includes the step of creating a position fingerprint database with multi-band RSS, a selection combining method based on probability density function of WiFi multi-band RSS is used for selecting the minimum variance signal of fingerprints and measured RSS. The closest distance among the position fingerprints and given RSS is comprehensively considered on the basis of the level of similarity to finish position estimation.

[0050] A. Training phase 301

[0051] Initially, without loss the generation, assuming all APs 303 transmit the multi-band signals, and the RSS of each band is pre-measured or simulated 304 to create the fingerprint database 305 based on pre-defined reference points (RPs). First, rasterize a known area into many RPs, a number of RSSs are measured or simulated during a period of time for each RP. At the same time, these values are stored as a signal strength distribution with probability density function (PDF).

[0052] Assuming there are B frequency bands for each AP, and the RSS from ith AP at a RP can be described

m.sub.i=[RSS.sub.i,1,RSS.sub.i,2, . . . , RSS.sub.i,B]

where RSS.sub.i,b is the average RSS in a measured period on bth band from ith AP. The fingerprint and their location information 1 are usually denoted as a tuple of (l,m). If orientation of mobile or asset is considered at the RP, then the location information is denoted as

l={(x,y,z,o)|x,y,z R, o {E,S,W,N}}

where x, y, and z are the three-dimension location coordinate, and o is the orientation with East (E), South (S), West (W), and North (N). For each frequency band of each AP, there have T RSS values based on a specific sample time, i.e.

RSS.sub.i,b=[RSS.sub.i,b(1),RSS.sub.i,b(2), . . . , RSS.sub.i,b(T)]

[0053] Assuming the probability density function (PDF) on bth band from ith AP at /th RP is f.sub.i,b,l, which can follow a Rayleigh distribution, and the mean and variance on the specific sample time are RSS.sub.i,b and .sub.i,b, the PDF can be denoted as

[00007]$f_{i,b,l}\left(s\right)=\frac{s}{{}_{i,b,l}^2}.Math.e^{\frac{-s^2}{2.Math.{}_{i,b,l}^2}}$

[0054] Simply, there are a total of T RSS values based on a specific sample time at the RP, RSS.sub.i,b=[RSS.sub.i,b(1),RSS.sub.i,b(2), . . . , RSS.sub.i,b(T)], the probability P(RSS.sub.i,b|l) that signal RSS.sub.i,b appear the given location RP can be calculated as

[00008]$P\left({\mathrm{RSS}}_{i,b}l\right)=\frac{\mathrm{count}\left({\mathrm{AP}}_{i,l,b}={\mathrm{RSS}}_{i,b}\right)}{T}$

where AP.sub.i,l,b denotes the received signal on bth frequency band from ith AP at /th RP. If K APs are selected to create the fingerprint at the RP, the fingerprint database 305 at RP / is described as

[00009]${\left(x,y,z,o\right)}_l,{\left[\begin{array}{cccc}{\stackrel{\_}{\mathrm{RSS}}}_{1,1},& {\stackrel{\_}{\mathrm{RSS}}}_{1,2},& \mathrm{.Math.}.Math.,& {\stackrel{\_}{\mathrm{RSS}}.Math.}_{1,B}\\ {\stackrel{\_}{\mathrm{RSS}}}_{2,1},& {\stackrel{\_}{\mathrm{RSS}}}_{2,2},& \mathrm{.Math.}.Math.,& {\stackrel{\_}{\mathrm{RSS}}.Math.}_{2,B}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ {\stackrel{\_}{\mathrm{RSS}}}_{K,1},& {\stackrel{\_}{\mathrm{RSS}}}_{K,2},& \mathrm{.Math.}.Math.,& {\stackrel{\_}{\mathrm{RSS}}.Math.}_{K,B}\end{array}\right]}_l,.Math.{\left[\begin{array}{cccc}{}_{1,1},& {}_{1,2},& \mathrm{.Math.}.Math.,& {.Math.}_{1,B}\\ {}_{2,1},& {}_{2,2},& \mathrm{.Math.}.Math.,& {.Math.}_{2,B}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ {}_{K,1},& {}_{K,2},& \mathrm{.Math.}.Math.,& {.Math.}_{K,B}\end{array}\right]}_l$

[0055] B. Positioning phase 302

[0056] In the positioning phase 302, the measured RSS at the receiver at a target location is matched with fingerprint database which was built in the previous phase. Because the multi-band RSSs are received at each target location, the selection combining algorithm can be used to select the best frequency band RSS based on the PDF to match the fingerprint, so the diversity gain can improve the positioning accuracy.

[0057] Assuming the mobile or asset is at the target location l, the measured RSS at the l is s.sub.i,b on the bth frequency band from the ith AP, so the measured signal 306 at the target location l can be written as

[00010]$\left(x^{},y^{},z^{},o\right),\left[\begin{array}{cccc}{s}_{1,1},& s_{1,2},& \mathrm{.Math.}.Math.,& {s.Math.}_{1,B}\\ s_{2,1},& s_{2,2},& \mathrm{.Math.}.Math.,& {s.Math.}_{2,B}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ s_{K,1},& s_{K,2},& \mathrm{.Math.}.Math.,& {s.Math.}_{K,B}\end{array}\right]$

where x, y, and z are the coordinate of target location l, which need to be estimated based on the positioning algorithm. By selection diversity algorithm 401, as shown in FIG. 4, the most proper frequency band is selected to estimate the target location l(x, y, z). Define P(l|s.sub.i,b) as the probability of the target location l(x, y, z) given measured signals s.sub.i,b. Apply Bayes' theorem.

[00011]$P\left(l^{}{s}_{i,b}\right)=\frac{P\left(s_{i,b}{l}^{}\right).Math.P\left(l^{}\right)}{P\left(s_{i,b}\right)}$

where P(l) is the probability that the mobile or asset is at the location l, P(s.sub.i,b) is the RSS probability, and P(s.sub.i,b|l) is the probability 402 that signal s.sub.i,b appear the given location l, which can be calculated by the PDF f.sub.i,b,l(s), i.e.

[00012]$P\left(s_{i,b}{l}^{}\right)={}_{{\mathrm{AP}}_{i,l^{},b=s_{i,b}}}^{}.Math.f_{i,b,l}\left(s\right).Math.\mathrm{ds}$

where AP.sub.i,l,b denotes the received signal on bth frequency band from ith AP at the target location. Or calculating the probability based on the above probability P(RSS.sub.i,b|l), i.e.

[00013]$P.Math.\left(s_{i,b}{l}^{}\right)=\frac{\mathrm{count}\left({\mathrm{AP}}_{i,l^{},b}=s_{i,b}\right)}{T}$

[0058] Because the system only cares about the most probable frequency band 403, that location factor is just a constant that can ignore, the most probable frequency band 404 can be found

[00014]$\arg .Math..Math.\underset{b}{\max }.Math.P\left(l^{}{s}_{i,b}\right)=\arg .Math..Math.\underset{b}{\max }.Math.P\left(s_{i,b}{l}^{}\right)/P\left(s_{i,b}\right)$

[0059] The Wi-Fi multi-band fingerprint database includes multiple frequency band fingerprints at each location. Once the most probable frequency band is selected, the fingerprints of the corresponding frequency band from multiple band fingerprint database may be selected, forming a single frequency band fingerprint database.

[0060] By application of the selection combining approach 307 where the measured RSS of frequency band with maximum probability of above expression is selected, i.e.

b=(b.sub.1,b.sub.2, . . . , b.sub.K).sup.T

where (.).sup.T denotes the transposition of vector, and b.sub.i is the selected frequency band of ith AP. So the measured RSS 309 from K APs can be described as

s=(s.sub.1,b.sub.1,s.sub.2,b.sub.2, . . . , s.sub.K,b.sub.K).sup.T

[0061] The corresponding selected fingerprint 308 in the database at location / can be expressed as

m.sub.l=(RSS.sub.1,b.sub.1,RSS.sub.2,b.sub.2, . . . , RSS.sub.K,b.sub.K).sub.l.sup.T

where RSS.sub.1,b, is average RSS from ith AP at the selected most probable frequency band. In the positioning calculation 310, deterministic type of algorithm based on nearest neighbour (NN) classifiers can be used to position the location. The basic algorithm concept of NN is closest distance algorithm, that the selected measured RSS is matched to the closest selected fingerprint value to estimate the position.

[0062] The closest distance of signal space is denoted as Dist(.) function, which can be the Euclidean distance, or Manhattan distance, etc. Therefore, calculate the closest distance between the target point location and fingerprint reference point location 311 as follows:

[00015]$\left(\hat{x},\hat{y},\hat{z}\right)=\arg .Math..Math.\underset{l}{\min }.Math.\mathrm{Dist}\left(m_l,s\right)$

where {circumflex over (x)},, and z are the estimated coordinate of location l(x, y, z).

[0063] For the Euclidean distance method, the expression is

[00016]$\left(\hat{x},\hat{y},\hat{z}\right)=\arg .Math..Math.\underset{l}{\min }.Math.\sqrt{\underset{i=1}{\overset{K}{.Math.}}.Math.{\left(m_{l,i}-s_i\right)}^2}$

[0064] For the Manhattan distance method, the expression is

[00017]$\left(\hat{x},\hat{y},\hat{z}\right)=\arg .Math..Math.\underset{l}{\min }.Math.\underset{i=1}{\overset{K}{.Math.}}.Math..Math.m_{l,i}-s_i.Math.$

[0065] Indoor location based Wi-Fi location fingerprinting of the present invention not only considers the closest distance between the position of fingerprints, but also considers the frequency diversity between multi-bands, and improve the accuracy of positioning accuracy. When building location fingerprint database only stores the received signal strength average value data, also stores the received signal strength standard variance of the data to calculate the signal distribution.

[0066] A detailed description of the preferred embodiment of the present invention specific or more. It should be understood that one of ordinary skill in the art without creative work to many modifications and variations may be made according to the teachings of the present invention. Therefore, all those skilled in the art under this inventive concept on the basis of prior art technical solutions through logical analysis, reasoning or limited experiments could be obtained, are to be made within the scope of the claims determined.

[0067] The applicant hereby discloses in isolation each individual feature described herein and any combination of two or more such features, to the extent that such features or combinations are capable of being carried out based on the present specification as a whole in the light of the common general knowledge of a person skilled in the art, irrespective of whether such features or combinations of features solve any problems disclosed herein, and without limitation to the scope of the claims. The applicant indicates that aspects of the present invention may consist of any such individual feature or combination of features. In view of the foregoing description it will be evident to a person skilled in the art that various modifications may be made within the scope of the invention.