Patent ID: 12235375

DETAILED DESCRIPTION

FIG.1shows a flow diagram of an example implementation of a method100for determining a position of a mobile device. The mobile device can be a tag that transmits or receives a radio frequency, RF, signal, like a Bluetooth direction finding signal, which includes a constant tone extension packet, CTE. Other RF signals like Wi-Fi signals, Ultra-wideband, UWB, or cellular signals could be used as an alternative, for example. Such signals are transmitted between the mobile device and a plurality of anchor points.

Referring now toFIG.2, an example of a positioning system is shown comprising a positioning engine LPE that includes a processing unit PROC and a receiver RX. Furthermore, the positioning system includes a plurality of anchor points1,2,3,4,5.FIG.2further shows a mobile device TG that further may be comprised by the positioning system. It should be noted that in some implementations the positioning engine LPE can be placed inside one of the anchor points1-5or inside the mobile device TG, or even in a network cloud. By transmitting respective signals between the mobile device TG and each of the anchor points1-5as described above, relative position information for each of the anchor points1-5can be determined by the respective anchor point and/or the mobile device TG. Such relative position information includes one of i) a direction between the respective anchor point and the mobile device, ii) a distance between the respective anchor point and the mobile device TG, and iii) a direction and distance between the respective anchor point and the mobile device TG. Respective measures for determining such relative position information are known to the skilled person and therefore not described in more detail here.

Referring back toFIG.1, in step101, for each of the plurality of anchor points1-5the respective relative position information between the respective anchor point and the mobile device TG is received, for example by the receiver RX of the positioning engine LPE, such that the received relative position information for the plurality of anchor points1-5forms a set of position information.

Further method steps102to106may be carried out by the processing unit PROC of the positioning engine LPE.

It should be noted that the number of five anchor points chosen in the example ofFIG.2should not be limiting and a smaller or greater number of anchor points could be used without loss of generality. The lower limit of anchor points is e.g. two if direction is included in the relative position information, and e.g. four if only a distance is included in the relative position information received for an anchor point. Generally, the lower limit depends on the type of relative position information provided by the anchor points to be used, which in detail will be apparent to the skilled reader from the above description.

A direction may be defined as a directional vector or as a 3D angle of arrival, AoA, or 3D angle of departure, AoD.

Referring now toFIG.3, an example 3D view of the anchor points1-5and a mobile device TG is shown, in particular in a 3D coordinate system. In this example, anchor point1and anchor point2are each able to provide relative position information including a distance between the anchor points1,2and the mobile device TG. The mobile device TG is shown at its ground truth position. For anchor point3, the relative position information includes both a direction and a distance between the anchor point3and the mobile device TG. For anchor points4and5, the relative position information includes only a direction between the respective anchor points4,5and the mobile device TG, e.g. derived from respective AoA measurements.

In this example the case is assumed where the mobile device TG is moving around a room and the anchor points1-5are responsible for measuring the distance and/or the AoA/AoD among them and the mobile device TG. A position of the anchor points1-5is assumed to be known. Furthermore, each measurement of distance and/or AoA/AoD is being conducted or transformed in such a way with respect to a global coordinate frame that characterizes the room under examination.

Referring now toFIG.4, an example 3D view of an anchor point and a mobile device is shown. This anchor point2, for example, measures only a distance. An anchor point that measures distance can be, for example, an UWB anchor point or a Bluetooth access point or a Wi-Fi router or any other device capable of estimating a distance between itself and the presumably moving target. However, it has to be assumed that due to AWGN, multipath, obstacles in the line of sight and other factors, the measured distance is erroneous. As shown inFIG.4, by measuring a distance, an anchor defines a sphere, also called a distance sphere, where the center of the sphere is the anchor point2itself and the radius equals the measured distance.

Let us suppose that the Anchor Aiis located at the point xi,yi,ziand measures a distance di. Then, the equation of the distance sphere is given by equation (1), where every quantity is expressed with respect to the room-global coordinate system that is depicted inFIG.3.

Anchor⁢point:Ai(xi,yi,zi)⁢(x-xi)2+(y-yi)2+(z-zi)2=di2(1)

Referring now toFIG.5, a definition of spherical coordinates is shown that is going to be used in this disclosure.

In mathematics, a spherical coordinate system is a coordinate system for three-dimensional space where the position of a point is specified by three numbers: the radial distance r of that point from a fixed origin, its polar angle θ measured from a fixed zenith direction, and the azimuthal angle φ of its orthogonal projection on a reference plane that passes through the origin and is orthogonal to the zenith, measured from a fixed reference direction on that plane.

The spherical coordinates vary at the following range:

r≥0⁢0≤θ≤π⁢0≤φ<2⁢π⁢or⁢-π<φ≤π(2)

Referring now toFIG.6, anchor point4is shown that measures a direction between itself and the mobile device TG.

For example, such an anchor point, after the appropriate coordinate transformations, provides two angles φ and θ which are the spherical coordinates of the target, except of the “r”. These two angles are measured with respect to the global coordinate axes that have been transferred to the anchor's position without changing its orientation.

The direction on which the target is located, relative to the anchor point's position is given by the directional vector {right arrow over (δ)}iwhich is defined in equation (3):

Measured⁢angles:⁢φi,θi⁢δ→i=[δi⁢xδi⁢yδi⁢z]=[cos⁢φi·sin⁢θisin⁢φi·sin⁢θicos⁢θi](3)

Directional vector {right arrow over (δ, )} defines completely a 3D straight line which contains the anchor and the tag, provided that no error has occurred.

Let us suppose that the tag and the anchor are located at the points T(x,y,x) and respectively. Then we can assert that

Aι⁢T→=[x-xiy-yiz-zi],δ→i=[δi⁢xδi⁢yδi⁢z]⁢Aι⁢T→//δ→i⇒{x-xiy-yi=δixδiyy-yiz-zi=δiyδiz⇒{δi⁢y⁢x-δi⁢x⁢y=δi⁢y⁢xi-δi⁢x⁢yiδi⁢z⁢y-δi⁢y⁢z=δi⁢z⁢yi-δi⁢yZ⁢i(4)

The last equation (4) represents the aforementioned 3D straight line which is depicted inFIG.6.

Referring now toFIG.7, an example 3D view of anchor point3and the mobile device TG with a directional vector is shown. Anchor point3is able to measure both distance and AoA. For example, a Bluetooth access point which is equipped with an antenna array, is capable to measure both types of information.

In this case, the anchor point3is a combination of the previous scenarios and based on equation (3), this anchor point determines a relative positional vector that is pointing to the target, respectively to the mobile device TG.

Indeed, if we suppose that the anchor Aiis located at the point (xi,yi,zi) and measures a distance diand the two angles φiand θi, then we can derive the following equation:

Measured⁢distance:diMeasured⁢angles:φi,θiΔ→︀i=di·δ→︀i=[ΔixΔiyΔiz]=[di·cos⁢φi·sin⁢θidi·sin⁢φi·sin⁢θidi·cos⁢θi](5)

If there is zero impact from multipath effects, AWGN, etc., then the positional vector {right arrow over (Δ)}i, which can also be called a relative positional vector, should point exactly at the location of the target.

Referring back toFIG.1, step102, an estimated position of the mobile device TG is determined, e.g. with processing unit PROC, based on the set of position information. To this end, the information being measured by the anchor points1to5of this example is exploited. A well-known method is to use equations (1), (4), (5) in order to create a system of linear equations and to use an LS approach in order to solve it. This should be demonstrated using the example configuration ofFIG.3, where all types of anchor points are present. The following table summarizes the details of all the anchor points1to5.

NO.TYPECOORDINATESMEASUREMENTS1DistanceA1(x1, y1, z1)d12DistanceA2(x2, y2, z2)d23Distance and directionA3(x3, y3, z3)d3, φ3, θ34directionA4(x4, y4, z4)φ4, θ45directionA5(x5, y5, z5)φ5, θ5

Of particular interest are the anchor points1and2, which measure distance and define spheres given by equation (1). In order to use these anchor points, one must combine a pair of them each time and create a useful linear equation. In the present example there are only two of them, so we have the following algebraic manipulations:

(1)⇒{(x-x1)2+(y-y1)2+(z-z1)2=d12(x-x2)2+(y-y2)2+(z-z2)2=d22⇒{(x2-2⁢x1⁢x+x12)+(y2-2⁢y1⁢y+y12)+(z2-2⁢z1⁢z+z12)=d12(x2-2⁢x2⁢x+x22)+(y2-2⁢y2⁢y+y22)+(z2-2⁢z2⁢z+z22)=d22⇒(-)2⁢(x2-x1)⁢x+2⁢(y2-y1)⁢y+2⁢(z2-z1)⁢z=(x22-x12)+(y22-y12)+(z22-z12)-(d22-d12)(6)

The last equation (6), in general, represents a plane in the 3D space. Referring now toFIG.8, this plane, in the case where the spheres of anchor points1and2are intersected, contains the circle consisting of the common points of the two spheres shown inFIG.8.

Before combining all equations from all kind of anchors, we have to normalize the equations that represent planes in the 3D-space. Namely, we transform equation (6) as follows. First we define the scaling factor SF12for the plane equation (6), defined by anchors1and2, see equation (7), and then we normalize, see equation (8).

SF1⁢2=2⁢(x2-x1)2+(y2-y1)2+(z2-z1)2(7)2⁢(x2-x1)S⁢F1⁢2⁢x+2⁢(y2-y1)S⁢F1⁢2⁢y+2⁢(z2-z1)S⁢F1⁢2⁢z=(x22-x12)+(y22-y12)+(z22-z12)-(d22-d12)S⁢F1⁢2(8)

So, combining all kind of anchors of our example, we get the following matrix equation (9) with the known coordinates of the anchors,

Ai=[xiyizi],1≤i≤5

and the unknown coordinates of the target

X=[xyz].(9)[2⁢(x2-x1)SF122⁢(y2-y1)SF122⁢(z2-z1)SF12100010001δ4⁢y-δ4⁢x00δ4⁢z-δ4⁢yδ5⁢y-δ5⁢x00δ5⁢z-δ5⁢y]︸H⁢[xyz]︸X=[(x22-x12)+(y22-y12)+(z22-z12)-(d22-d12)SF12x3+Δ3⁢xy3+Δ3⁢yz3+Δ3⁢zδ4⁢y⁢x4-δ4⁢x⁢y4δ4⁢z⁢y4-δ4⁢y⁢z4δ5⁢y⁢x5-δ5⁢x⁢y5δ5⁢k⁢y5-δ5⁢y⁢z5]︸B

In the example of equation (9), the first row results from the distance information from anchors1and2, rows2-4result from direction and distance information from anchor3, and rows5-8result from the direction information from anchors4and5, respectively. This also becomes apparent from the indices used.

Referring back toFIG.1, step102, a LS solution using pseudo-inverse can be applied for determining the estimated position {circumflex over (X)} of the mobile device TG:

H⁢X=B⇒Xˆ=[(HT⁢H)-1⁢HT]⁢B(10)

Equation (10) is solved by assuming that all anchor points and all equations in the matrix equation (9) are of equal importance and have the same reliability. In the real world, this is not true. Several sources of errors make the equations that form the matrix equation (9), less or more reliable.

One approach is to use different weights for each equation. For example, in our case we can define a weight matrix and find the solution by using Weighted Least Square, WLS, algorithm.

In general, the idea of WLS, tailored to our example, is being illustrated as described in the following. An 8×8 diagonal weight matrix, such that, in general, each equation (here: 8) of the matrix equation (9) has its own weight.

W=[w1000…00w200…000w30…0000w4…0⋮⋮⋮⋮⋱⋮00000w8]

Usage of the weight matrix W results in

(HX=B)⟹LS⁢solutionweightedXˆw=[(HT⁢WH)-1⁢HT⁢W]⁢B(11)

Of course, there are some critical issues. The most important of them are the following:how to define the weights to correspond to the equation's reliability; andhow to estimate the values of the weights without waste an enormous amount of computational resources.

An indoor environment with many targets to follow inside it is not suitable for statistical models. Furthermore, trying to use memory and/or statistical models is extremely resource consuming when the number of tags increases.

With the improved processing concept it is proposed defining the weights, according to the distance of the estimated position and the locus defined by each anchor point or pair of anchor points, as described at the previous paragraphs.

It has already been described that each kind of anchor (or group of anchors) determines a specific locus for the target. The equations that describe each locus are the rows of the matrices H and B of the matrix equation (9) as mentioned above.

In our example, the correspondence between the type of the anchor(s), the type of the locus that is generated of each anchor type and the number of the equations which describes it in the 3D space, is summarized at the following table

Number ofNumber ofType of AnchoranchorsLocusequationsMeasuring distance2plane1Measuring AoA/AoD1line2Measuring distance + AoA/AoD1point3

Hence referring back toFIG.1, in step103, a set of loci is defined, each locus of the set of loci being based on one or more of the relative position information from the set of position information, e.g. according to the above table.

Furthermore, in step104, for each locus of the set of loci, a distance value between the estimated position of the mobile device (TG) and the respective locus is determined.

This will be described in more detail in the following for the different possible configurations.

Distance between a point and a plane in the 3D space

Let us suppose that we want to determine the distance between the point X0(x0,y0,z0) and the plane described by equation (8). The distance is given from the following with A1(x1,y1,z1) and A2(x2,y2,z2) being the positions of the anchor points1and2that measure distances d1, d2.

Assuming the following notations

Cx=2⁢(x2-x1)S⁢F1⁢2,Cy=2⁢(y2-y1)S⁢F1⁢2,Cz=2⁢(z2-z1)S⁢F1⁢2,C0=(x22-x12)+(y22-y12)+(z22-z12)S⁢F1⁢2⁢Cd=(d22-d12)S⁢F1⁢2

and the plane equation with respect to equation (8),
Cxx+Cyy+Czz=C0−Cd,

a distance Dplanebetween the point X0(x0,y0,z0) and the plane results to

Dplane=❘"\[LeftBracketingBar]"Cx⁢x0+Cy⁢y0+Cz⁢z0-C0+Cd❘"\[RightBracketingBar]"Cx2+Cy2+Cz2(12)

The quantities Cx, Cy, Cz, C0, SF12and √{square root over (Cx2+Cy2+Cz2)} depend on the anchor points only. This observation allows us to predetermine them and simplify the computational effort of such a distance calculation, resulting in the following equation (13):
Dplane=|Cx′x0+C0Cy′y0+Cz′z0−C0′+Cd(d22−d12)|  (13)

Herein the following predefined coefficients are used:

Cx′=cxcx2+cy2+cz2,Cy′=cycx2+cy2+cz2,Cz′=czcx2+cy2+cz2,C0′=c0cx2+cy2+cz2,Cd′=1SF12⁢cx2+cy2+cz2,

Distance Between Two Points in the 3D Space

Let us suppose that we want to determine the distance between the point X0(x0,y0,z0) and the point defined by the vector {right arrow over (Δ)}3for anchor point3as described above. The distance is given from the following equations. With A3(x3,y3,z3) being the position of the anchor point3, and measured distance d3and measured angles φ3, θ3, the vector {right arrow over (Δ)}3for anchor point3is defined as

Δ→3=d3·δ→3=[Δ3⁢xΔ3⁢yΔ3⁢z]=[d3·cos⁢φ3·sin⁢θ3d3·sin⁢φ3·sin⁢θ3d3·cos⁢θ3].

The distance Dpointbetween the two points therefore results in:

Dp⁢o⁢i⁢n⁢t=[x0-(x3+Δ3⁢x)]2+[y0-(y3+Δ3⁢y)]2+[z0-(z3+Δ3⁢z)]2(14)

Distance Between a Point and a Line in the 3D Space

The distance between the point X0(x0,y0,z0) and the line defined by equation (4) is given by equation (15) below, using anchor point4of our example.

With A4(x4,y4,z4) being the position of the anchor point4, and measured angles φ4, θ4, vector {right arrow over (δ)}4and the vector {right arrow over (A4X0)} result to:

δ→4=[δ4⁢xδ4⁢yδ4⁢z]=[cos⁢φ4·sin⁢θ4sin⁢φ4·sin⁢θ4cos⁢θ4]⁢A4⁢X0→=[x0-x4y0-y4z0-z4]

The distance Dlinebetween the point and the line therefore results in:

Dline=A4⁢X0→×δ→4δ→4⟹δ→4=1Dline=A4⁢X0→×δ→4(15)

At the last step, to simplify the calculation of Dline, we have exploited the fact that by definition∥{right arrow over (δ)}4∥=1. In some implementations, the distance values are determined as squared distances, e.g. squared geometrical distances, between the estimated position of the mobile device TG and the respective locus. The use of squared distances may reduce the computational effort of the determination since, for example, square root calculations can be avoided.

Referring now to step105inFIG.1, the estimated position of the mobile device TG and the respective distances between that estimated position and the loci is used to determine whether a locus behaves as an outlier or not, i.e. whether the respective locus is reasonable with respect to estimated position. For example, referring toFIG.9AandFIG.9B, the respective loci for all five anchor points1to5are shown, inFIG.9Ain a 3D view and inFIG.9Bin a 2D view, resembling a top view ofFIG.9A. In particular, the two distance spheres of the anchor points1and2together with the resulting plane locus are shown, as well as the line loci of anchor points4and5and the point locus of anchor point3.

If we look carefully at the room with the five anchor points1to5, we will observe that with respect to the estimated position, called a draft estimation inFIGS.9A and9B, of the mobile device TG, the straight line locus, which is defined by anchor point4, behaves as an outlier. Although anchor point4with the corresponding locus line has its own contribution on the determination of the estimated position, together with the other anchor points, it nevertheless can be seen that the LS solution of all the loci has a large distance from the locus of anchor point4and makes it suspicious for being an outlier.

Hence, referring back to step105, the distances of the estimated LS position from all the four loci are used for producing the weights for each one of the rows of the weight matrix W that has been described above in conjunction with equation (11).

The weights are calculated per locus and not per row of the matrix equation (9).

This means that for our example, weight matrix W should have the following form for the present example:

W=[w1200000000w300000000w300000000w300000000w400000000w400000000w500000000w5]⇒W=diag⁡(w12,w3,w3,w3,w4,w4,w5,w5)(16)

Derivation of Weights Based on the Distances

As already has been mentioned, the improved processing concept makes the weights dependent on the distance of the estimated position from each locus. The bigger the distance is, the less should be the reliability (and the weight) of the specific locus.

Let us assume that we treat a room with N anchors (N=5 in our example) of any type, which produce M different loci (M=4 in our example). For each locus Li, 1≤i≤M we calculate the distance Diaccording to the equations described above. We define a set of M functions fi:M→that maps the M respective values of Dito a set of M values of wI, such that
wi=fi(D1,D2, . . . ,Di, . . . DM),1≤i≤M(17)

There are numerus candidate functions fi, some of which will be described in the following.

Furthermore, we can generalize the concept of the distance Diand use any monotonicaly increasing function of it, for example the squared Dias mentioned above. Let us denote as Eithis generalized distance between the estimated position and each locus. For example, it could be:
Ei=Di,E1=(Di)2,Ei=√{square root over (Di)}etc.

For example, the weight factor wifor each locus of the set of loci as a function of the determined distance values may be defined as

wi=[1-(EiEthreshold+∑j=1MEj)μ]v,(18)

whereini denotes the associated locus;M denotes the number of loci;Ejdenotes the distance value for the locus j, e.g. the locus associated with index j;Ethresholddenotes a distance threshold value; andμ, ν are exponent values with ρ, ν>0.

In an alternative, the weight factor wifor each locus of the set of loci as a function of the determined distance values may be defined as

wi=(Ethreshold+min⁢{E1,E2,…,Ei,…,EM}Et⁢h⁢r⁢eshold+Ei)v,(19)

whereini denotes the associated locus;M denotes the number of loci;Ejdenotes the distance value for the locus j, e.g. the locus associated with index j;Ethresholddenotes a distance threshold value; andv is an exponent value with v>0.

In a further alternative, the weight factor wifor each locus of the set of loci as a function of the determined distance values is defined as

wi={whigh,Ei<Ethresholdwlow,Ei≥Ethreshold,(20)

whereini denotes the associated locus;Eidenotes the distance value for the locus i;Ethresholddenotes a distance a threshold value;whighdenotes a high weight factor; andwlowdenotes a low weight factor that is smaller than the high weight factor whigh.

In an example Whighmay have a value close to 1 or equal to 1, whereas wlowmay have a value close to 0 or equal to 0.

The weights that are being generated from the above formulas are in the range 0≤wi≤1.

The value Ethreshold, where applicable, is a threshold defined from the designer and it expresses the distance limit below which the weight approaches the value “1”.

Also, exponents μ, ν, are choice of the designer and they define the dependence of the weights on the distances and their ranges are, for example ¼≤μ≤1, 1≤ν≤4.

After the weight factors have been determined in step105, in step106a refined position is determined based on the set of position information and the determined weight factors, e.g. by the WLS approach defined in equation (11), using the weight factor of the form described in equation (16).

Optionally, the method may be performed in an iterative fashion. For example, after the refined position has been determined, in a next iteration step it is continued at step104by determining distance values from the loci to the refined position of the mobile device TG. For example, in an initial iteration step the estimated position is determined based on the set of position information, and in each subsequent iteration step the refined position determined in a respective preceding iteration step is used as the estimated position for determining the distance values and the weight factors. The number of iterations may be predetermined and/or the iteration stops when some exit criterion is fulfilled.

Referring now toFIGS.10to13, several examples of cumulative distribution functions, CDF, of localization errors with respect to corresponding ground truth positions according to the improved processing concept are shown. In theseFIGS.10to13, the “draft” line refers to the estimated position of the mobile device, the 1stiteration refers to the refined position with the first application of the weight factors, and the 2nditeration refers to the refined position with the second application of the weight factors.

For example, the CDF shown inFIG.10corresponds to weight factors being determined according to equation (18) with μ=½ and ν=2. It can be seen that the probability for smaller localization errors can be severely improved with a single iteration and further improved with a second iteration, as described above. The CDF ofFIG.10corresponds to a scenario where the mobile device TG is moving around the room, which for example is a typical office environment.

Simulating the same scenario but using the formula of equation (19) with v=2, we get the performance results shown inFIG.11.

For both approaches,
Ethreshold=0.1
has been used. We can observe that the improvement of the confidence level of e.g. 90% is more than 0.5 m.

If we repeat the previous two measurements in the same office environment, but the mobile device follows the path that always one or two of the anchor points are in a non-line-of-sight condition or suffer a strong multipath, then the improvement is even more evident, as can be seen inFIGS.12and13. In particular,FIG.12is based on equation (18) for the weight calculation andFIG.13is based on equation (19) for the weight calculation.

In addition to the weight factors as described above, in some implementations the refined position of the mobile device TG may be determined further based on quality information for at least one of the plurality of anchor points. For example, this quality information can be expressed in one or more further weight matrices that are applied to the WLS algorithm.

For example, the quality information for the at least one anchor point is determined from at least one of the following:a signal strength, e.g. RSSI, associated with the received relative position of the at least one anchor point;a number of antenna elements of the at least one anchor point; a higher number increases accuracy;a confidence factor associated with the received relative position of the at least one anchor point;upper and/or lower bounds for the weight factor associated with the at least one anchor point.

Various embodiments of the improved processing concept can be implemented in the form of logic in software or hardware or a combination of both. The logic may be stored in a computer readable or machine-readable storage medium as a set of instructions adapted to direct a processor of a computer system to perform a set of steps disclosed in embodiments of the improved processing concept. The logic may form part of a computer program product adapted to direct an information-processing device to automatically perform a set of steps disclosed in embodiments of the improved processing concept.

The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. However, it will be evident that various modifications and changes may be made thereunto without departing from the scope of the invention as set forth in the claims.

LIST OF REFERENCE SIGNS

100method for determining a position of a mobile device101-106steps1-5anchor pointsTG mobile deviceRX receiverPROC processing unitLPE positioning engine