Positioning

FIELD OF THE INVENTION

Embodiments of the present invention relate to positioning. In particular, they relate to the use of geometric algebraic solutions.

BACKGROUND TO THE INVENTION

When there is antenna diversity and each antenna is controlled to receive the same signal from a distant source, the relative phase differences between the received signals may be processed to determine the direction from which signal was transmitted.

BRIEF DESCRIPTION OF VARIOUS EMBODIMENTS OF THE INVENTION

According to various, but not necessarily all, embodiments of the invention there is provided a positioning method comprising: solving a geometric algebraic expression that relates: position vectors for a plurality of receivers relative to a shared origin, a putative position vector for the shared origin and phase information of waves measured at each of the plurality of receivers, to determine a position vector between the shared origin and a source of the waves; and positioning an apparatus using the determined position vector.

According to various, but not necessarily all, embodiments of the invention there is provided an apparatus comprising: processing circuitry configured to solve a geometric algebraic expression that relates: position vectors for a plurality of receivers relative to a shared origin, a putative position vector for the shared origin and received wave phase information for each of the plurality of receivers, to determine a position vector for the shared origin and configured to relatively positioning a source of the received waves and the shared origin.

According to various, but not necessarily all, embodiments of the invention there is provided a positioning method comprising: solving a geometric algebraic expression that relates: position vectors for a plurality of antennas relative to a shared origin, a putative position vector for the shared origin and phase information measured at each of the plurality of antennas, to determine a position vector for the shared origin; and positioning an apparatus using the determined position vector for the shared origin.

According to various, but not necessarily all, embodiments of the invention there is provided an apparatus comprising: processing circuitry configured to solve a geometric algebraic expression that relates: position vectors for a plurality of antennas relative to a shared origin, a putative position vector for the shared origin and phase information for each of the plurality of antennas, to determine a position vector for the shared origin and configured to positioning the apparatus using the determined position vector for the shared origin; and an interface configured to provide phase measurements.

It is expected that the positioning method will be robust to the presence of noise.

BRIEF DESCRIPTION OF THE DRAWINGS

For a better understanding of various examples of embodiments of the present invention reference will now be made by way of example only to the accompanying drawings in which:

Fig 1 schematically illustrates an arrangement of a plurality of antennas that receive radio signals broadcast by the source; Fig 2 schematically illustrates a method for determining the position vector for the shared origin;

Fig 3 schematically illustrates an example of an apparatus suitable for performing positioning;

Fig 4 schematically illustrates an example of a method for determining the position vector of the shared origin;

Fig 5 schematically illustrates an apparatus comprising the plurality of antennas;

Fig 6 schematically illustrates an apparatus comprising a subset of the plurality of antennas.

DETAILED DESCRIPTION OF VARIOUS EMBODIMENTS OF THE INVENTION The following description presents a new methodology that is applicable for positioning. The new methodology relies upon minimizing a cost function expressed using geometric algebra (see Equation 1 below).

The cost function is dependent upon position vectors for a plurality of antennas relative to a shared origin, a position vector for the shared origin and real phase information for each of the plurality of antennas. The position vector of an antenna and the position vector for the shared origin define theoretical phase information for the antenna in the cost function. The cost function expresses summation, over all antennas and all measurements, of the square of a difference value.

The difference value is the difference between real (e.g. measured) phase information for an antenna and expected (e.g. calculated) phase information for the antenna. When performing positioning, the expected phase information for an antenna is dependent upon a putative position of a shared origin used to position the antennas and the position of the antenna from that origin. The minimum of the cost function finds the position of the shared origin that reduces the difference, on the average across the antennas, between the real phase information and the theoretically determined phase information.

The minimum of the cost function is found using geometric, as opposed to linear, algebra.

Geometric algebra and the associated calculus provides one with a method of setting up equations using both known and unknown vectors and then solving the equations for the unknown vectors in terms of the known vectors. A similar process can be achieved using linear algebra, but in this case one does have to select a coordinate system and then operate with the components of the vectors using matrices. However, the complete vector space needs to be specified, when matrices are used, while when one uses the geometric algebraic approach, only the sub space spanned by the vectors need to be specified. This enables the geometric algebraic solutions to be more generic. With matrices, one needs to be careful finding inverses. In geometric algebra, we do not get this problem.

Fig 1 schematically illustrates an arrangement of a plurality of antennas 8 that receive radio signals broadcast by the source 4.

Each antenna 8 _n is positioned at a displacement r _n from a common or shared origin 6. This displacement is defined as the position vector r _n for the antenna n. It should be understood that the position of an antenna 8 _n for the purpose of receiving radio waves may be different to the physical position of the antenna 8 _n . The source of the radio signals is positioned at a displacement r _s from the shared origin 6.

The shared origin 6 is positioned at a displacement R _s from the source 4 of the radio signals. This displacement is defined as the position vector R _s for the shared origin.

In the following description the terms vector and displacement may be used interchangeably. A vector may be represented using either bold font r _n or over-scoring r _n depending on context.

The cost function may be expressed as: ( F„ .* ., ^. - /? ,, ,* )' ⁵ < ¹ >

where

the outer summation limit Γ is the number of antenna n, the inner summation limit P(n) is the number of phase measurements made at the antenna n, and β , is phase information relating to a phase measurement at instant k at antenna n and is expressed in the dimensions of distance

' n,k ^~ ^n,k

O where

OC , is the phase measurement at instant k at antenna n, Θ is a n,k n predetermined antenna dependent phase offset, c is the speed of light and ω is the frequency of the transmitted radio signal. Fig 2 schematically illustrates a method 10 for determining the position vector R _s for the shared origin. At block 12 a geometric algebraic expression is solved to determine the position vector R _s for the shared origin. The geometric algebraic expression that is solved is:

The geometric algebraic expression relates: position vectors r _n for a plurality of antennas 8 relative to a shared origin 6, a putative position vector R _s for the shared origin and scalar phase information β _{η k} measured at each of the plurality of antennas.

The difference value is the difference between real measured phase information β for an antenna and theoretical phase information for the antenna. The dot product of the position vector r _n of an antenna and the position vector R _s for the shared origin 6 define theoretical phase information, expressed in the dimensions of distance, for the antenna n. The solution to Equation (3) finds the position of a shared origin R _s that reduces the difference, on the average across the antennas, between the real phase information and the theoretically determined phase information.

By defining the mean-squared phase dependent vector

& the mean origin dependent vector

It is possible to re-express equation (3) as

1 0

Solving the geometric algebraic expression given by Equation (6) comprises determining a putative position vector R _s for the shared origin 6 that is parallel to a difference vector defined as the difference between the mean origin dependent vector and the mean-squared phase dependent vector.

Equation 6 may be re-expressed as

This equation may be solved iteratively as discussed in detail below.

Next at block 14, an apparatus is positioned using the determined position vector R _s for the shared origin.

Fig 4 schematically illustrates an example of the method 10 in more detail.

At block 31 , a phase C _{n ]i} of a received signal transmitted by the source 4 is measured, at each antenna n at each instance k. At block 32 the measured phase Oi _{n k} of a received signal is compensated by subtracting an antenna dependent phase offset Θ to create phase information. The phase information may be expressed in the dimensions of

2c

distance by multiplication by the scalar— (see Equation (2) ).

ω

Equation (7) may be used to create a number of distinct update multivector expressions for iterative processing.

Expressing the fourth term of Equation (7) as an iterative term provides:

Expressing the third term of Equation (7) as an iterative term provides:

K,m ₊ 1 = ^L QlRs m - A + m f ⁾ (8B)

Expressing the second term of Equation (7) as an iterative term provides:

^, _m+1 = ⁽ ¾^, _m „, -f Hh + _* rfthJ ^{1 <8C)}

Expressing the first term of Equation (7) as an iterative term provides:

Thus the iterative solution may be defined as where f is a multivector function which may be any one of Equations 8A, 8B, 8C or 8D or any weighted summation of Equations 8A, 8B, 8C or 8D. Next at block 33, the initial putative position vector R _s , 1 for the shared origin is set. The value of the mean-squared phase dependent vector If is determined and stored for use as a constant vector during the iteration Next at block 34, the mean origin dependent vector

^5 is determined and the next putative iterative solution is defined as f[d[R _s ,l f, R _s , ) (10)

Next at block 35, the putative iterative solution is tested for convergence. One example of a suitable convergence criterion is

0 < ^R s , m + l - ^R s , m < £ (1 1 )

If convergence is achieved, the method moves to block 36.

If convergence is not achieved, the method returns to block 34 where a new iterative solution is determined according to:

At block 36, after convergence has been achieved, the putative iterative solution is used as the position vector R _s for the shared origin. The value of the initial putative position vector R _{Si Λ} may be updated to the value of R _s .

Fig 3 schematically illustrates an example of an apparatus 20 suitable for performing positioning as described in the preceding paragraphs. The apparatus 20 comprises: phase measurement circuitry 22; storage circuitry 24; and processing apparatus 26.

The phase measurement circuitry 22 is configured to measure, for at least one and in some embodiments all of the antennas, the phase of a received signal at each antenna.

The storage circuitry 24 is configured to store data for use by the processing apparatus 26. The data includes a look-up table comprising the set {Θ } of predetermined antenna dependent phase offsets, the set of position vectors {r _n } relative to a shared origin 6 for the plurality of antennas 8 and the initial putative position vector R _s , -i .

The offsets are valid while the set of position vectors {r _n } remains unchanged. If it changes, the set {Θ } of predetermined antenna dependent phase offsets and the set of position vectors {r _n } need to be recalculated.

The processing apparatus 26 comprises: an interface 25 and processing circuitry 27. The interface 25 is configured to provide the set of phase measurements { C , } from the phase measurement circuitry 22 (and/or the storage 24) to the processing circuitry 27. The interface 25 is also configured to provide the set { Θ } of predetermined antenna dependent phase offsets, the set of position vectors {r _n } and the initial putative position vector R _s , -i from the storage circuitry 24 to the processing circuitry 27.

The processing circuitry 27 configured to solve the geometric algebraic expression and determine the position vector R _s for the shared origin. The processor is configured to perform block 12 and block 14 of Figs 2 and 4. Implementation of the processing circuitry 27 can be in hardware alone ( a circuit, a processor...), have certain aspects in software including firmware alone or can be a combination of hardware and software (including firmware). The processing circuitry 27 may be implemented using instructions that enable hardware functionality, for example, by using executable computer program instructions in a general-purpose or special-purpose processor that may be stored on a computer readable storage medium (disk, memory etc) to be executed by such a processor.

The processing circuitry 27 is configured to read from and write to the storage 24.

The storage 24 may be a memory that stores a computer program 29 comprising computer program instructions that control the operation of the apparatus when loaded into the processing circuitry 27. The computer program instructions provide the logic and routines that enables the apparatus to perform the methods illustrated in Figs 2 and 4. The processing circuitry 27 by reading the memory 24 is able to load and execute the computer program 29.

The computer program may arrive at the apparatus 20 via any suitable delivery mechanism 21 . The delivery mechanism 21 may be, for example, a computer-readable storage 24 medium, a computer program product, a memory device, a record medium, an article of manufacture that tangibly embodies the computer program 29. The delivery mechanism may be a signal configured to reliably transfer the computer program 29.

Although the storage 24 is illustrated as a single component it may be implemented as one or more separate components some or all of which may be integrated/removable and/or may provide permanent/semi-permanent/ dynamic/cached storage 24. References to 'computer-readable storage 24 medium', 'computer program product', 'tangibly embodied computer program' etc. or a 'controller',

'computer', 'processor' etc. should be understood to encompass not only computers having different architectures such as single /multi- processor architectures and sequential (Von Neumann)/parallel architectures but also specialized circuits such as field-programmable gate arrays (FPGA), application specific circuits (ASIC), signal processing devices and other devices. References to computer program, instructions, code etc. should be understood to encompass software for a programmable processor or firmware such as, for example, the programmable content of a hardware device whether instructions for a processor, or configuration settings for a fixed- function device, gate array or programmable logic device etc. The processing apparatus 26 may be a module. As used here 'module' refers to a unit or apparatus that excludes certain parts/components that would be added by an end manufacturer or a user.

The set {Θ } of predetermined antenna dependent phase offsets may be determined by measuring the antenna response in a anechoic chamber or by using the specification given by the antenna manufacturer. The antenna dependent phase offset gives a measure of the impact of the antenna characteristic on the phase of a signal recorded by the antenna itself. The set of position vectors {r _n } may be determined by solving the equation

when r _s ,q is a known current position of the shared origin, and there are a set { r _s,q } of known positions of the shared origin at different instances. where.

2c

β ( OS , - Θ ) (1 3) n. ,k,q n,k,q n,q

ω and (X , is the phase measurement at instant k at antenna n, Θ is n,k,q n,q predetermined antenna dependent phase offset when the shared origin is r _s , c is the speed of light and ω is the frequency of the transmitted radio signal.

This can be solved iteratively using

P[n]

q,n,k 7 s, q 7 n,m 7 s,q /))

. k=\

K,m+1

P (14)

[n]A using the initial putative solution

where m is the index of the iteration and p _n is the physical geometric position vector of the nth antenna with respect to the shared origin.

The iteration continues until convergence as defined by:

0 < n , m + 1— n , m < £ (16) where ε is a positive (>0) accuracy parameter. The solution at convergences is the position vector r _n of the antenna 8 _n .The iteration is repeated for each value of n to produce the set { r _n } which is stored in storage 24.

The set { r _n } of antenna location may alternatively be estimated by measuring the response of the antennas and by exploiting EADF (effective aperture distribution function).

Fig 5 schematically illustrates an apparatus 40 comprising a housing 42. The housing 42 houses the plurality of antennas 8 _n where n=1 , 2... Γ. In this example, the shared origin is defined within the housing 42, for example, at the centre of the apparatus 40. The position vector R _s for the shared origin in this example is also the position of the apparatus 40 from the radio source 4.

Fig 6 schematically illustrates an apparatus 44 comprising a housing 46. The housing 42 houses a subset of the plurality of antennas 8 _n where n=1 , 2... Γ. In this example, housing houses antenna the 8 ₄ . The shared origin 6 is defined within the housing 46, for example, at the centre of the apparatus 44. The position vector R _s for the shared origin in this example is also the position of the apparatus 44 from the radio source 4. The apparatus 44 may communicate to other apparatus 48, the relative position vector of that apparatus from the apparatus 44 and the position vector R _s of the apparatus 44. For example, the apparatus may send to an apparatus 48 housing the antenna 8 ₁ the position vectors R _s and n. The positioning algorithm may be adapted to make it more effective for tracking a position. The arguments of the function f defining the iterative solution may be weighted towards the most recently used arguments. For example, the mean-squared phase dependent vector γ may be defined as

7 = Λ JoU + (! - >*) 7n new (1 7) i.e.

J n=l k _ne =l ÷ J

For example, the mean origin dependent vector be defined as

where 0< λ<1 .

The blocks illustrated in the Figs 2 and 4 may represent steps in a method and/or sections of code in the computer program 29. The illustration of a particular order to the blocks does not necessarily imply that there is a required or preferred order for the blocks and the order and arrangement of the block may be varied. Furthermore, it may be possible for some steps to be omitted. In the preceding paragraphs, the position vector R _s defines the position of the shared origin 6 from the radio source 4. If the position of the radio source 4 is known then the position of the shared origin is determined by the position vector R _s . If the position of the shared origin is known then the position of the radio source 4 is determined by the position vector R _s . The method may therefore position either the shared origin 6 or position the radio source 4 depending upon applications. The preceding paragraphs have concentrated on positioning using radio waves from a radio source 4. However, the method as described is applicable to audio waves as opposed to radio waves. In the radio implementation, the antennas 8 are replaced by appropriate receivers such as pressure sensing microphones and the radio source 8 is replaced by an appropriate wave source such as an audio source.

The method can therefore be generalized to a positioning method comprising: solving a geometric algebraic expression that relates: position vectors for a plurality of receivers relative to a shared origin, a putative position vector for the shared origin and phase information of waves measured at each of the plurality of receivers, to determine a position vector between the shared origin and a source of the waves; and positioning an apparatus using the determined position vector.

The positioned apparatus may, for example, have a defined spatial relationship to the shared origin. Alternatively, the positioned apparatus may, for example, have a defined spatial relationship to the wave source. The wave source may be a radio wave source.

The wave source may bean acoustic wave source. The acoustic waves may be human audible or human inaudible. The acoustic waves may occupy a sub-band at frequencies below that normally audible to humans e.g. sonar. The acoustic waves may occupy a supra-band at frequencies above that normally audible to humans e.g. ultrasound.

Although embodiments of the present invention have been described in the preceding paragraphs with reference to various examples, it should be appreciated that modifications to the examples given can be made without departing from the scope of the invention as claimed. Features described in the preceding description may be used in combinations other than the combinations explicitly described.

Although functions have been described with reference to certain features, those functions may be performable by other features whether described or not.

Although features have been described with reference to certain

embodiments, those features may also be present in other embodiments whether described or not.

Whilst endeavoring in the foregoing specification to draw attention to those features of the invention believed to be of particular importance it should be understood that the Applicant claims protection in respect of any patentable feature or combination of features hereinbefore referred to and/or shown in the drawings whether or not particular emphasis has been placed thereon.

I/we claim: