A method for localization of nodes by using partial order of the nodes

(12) Patent Specification do) SE 534 644 C2

<img file="SE534644C2_D0001.tif" />

*

CD

<img file="SE534644C2_D0002.tif" />

Sweden (21) Patent application number: 0800688-4 (45) Patent granted: 2011-11-01 (41) Application generally available: 2009-09-28 (22) Patent application submitted: 2007-03-27 (24) Maturity date: 2008- 03-27 (83) Deposit of microorganism: - (30) Priority information: - (51) International class:

G01S5 / 08 (2006.01)

<td>(73) Patent holders:</td><td>SICS Swedish Institute of Computer Science AB, Box 1263, 164 29 Kista SE</td>

<td>(72) Inventor:</td><td>Martin Nilsson, Sundbyberg SE</td>

<td>(74) Agents:</td><td>Groth &amp; Co. KB, Box 6107, 102 32 Stockholm SE</td>

<td>(54) Name:</td><td>Method and system for localization of nodes</td>

<td>(56) Publications cited:</td><td>US 6266014 Bl · Peralta, Laura M. Rodriguez et al, Collaborative Localization in Wireless Sensor Networks, Sensor Technologies and Applications, 2007. SensorComm 2007. International Conference on, vol., Pp. 94-100,14-20 Oct . 2007</td>

(47) Summary:

The present invention relates to a method of localization ie. find the position and orientation of nodes communicating in a wireless network. The method is based on the use of direction information (angle-of-arrival, AO A), but may also include distance information, in combination with an estimate through recursive filters such as Kalman filters, recursive least-squares filters, Bayesian filters, or particle filters. The method expresses the location problem as a series of linear equations that ensure stability and convergence by partially arranging the nodes.

<img file="SE534644C2_D0003.tif" />

534 644

The present invention relates to a method of localization ie. find the position and orientation of nodes communicating in a wireless network. The method is based on the use of angle information (angle-of-arrival, AOA), but may also include distance information, in combination with an estimate through recursive filters such as Kalman filters, recursive least squares filters, Bayesian filters, or particle filters. The method expresses the location problem as a series of linear equations that ensure stability and convergence by partially arranging the nodes.

534 644

PROCEDURES AND SYSTEMS FOR LOCATION OF Nodes

Technical area

The present invention relates, in a first aspect, to a system operable for locating nodes communicating in a wireless network.

In a second aspect, the present invention relates to a method for locating nodes communicating in a wireless network.

According to a third aspect, the present invention relates to at least one computer program product for locating nodes communicating in a wireless network.

Background of the invention

The document "Sensor Network Localization via Received Signal Strength Measurements with Directional Antennas", by Joshua N. Ash and Lee C. Potter, Dept, of Electrical and Computer Engineering, The Ohio State University, 2015 Neil Avenue, Columbus, OH 43210, refers to the self-localization that can be obtained using received signal strength (RSS) from devices with directional antennas at each sensor node. The Crame'r-Rao lower limit of position error variance is used to predict the function of efficiency estimator and can provide information on design compromises for antennas, communication protocols and estimation algorithms.

The document "Robust System Multiangulation Using Subspace Methods," by Joshua N. Ash and Lee C. Potter, Department of Electrical and Computer Engineering, The Ohio State University, OH 43210, refers to a robust and less complex algorithm for self-locating and orienting sensors in a network based on angle-of-arrival (AOA) information.

The document J. Krumm: "Probalistic Interferencing for Location", Workshop on Location Aware Computing (Part of UlbiComp 2003), 2003-10-12, Seattle, WA, USA, describes and discusses various general techniques that researchers have adopted for processing sensor readings to position values, with emphasis on probable approaches. The general techniques described are deterministic function inversion, maximum likelihood estimation, MAP (maximum a posteriori) estimation and three recursive filtration techniques: Kalman filtration, hidden Markov model and particle filter.

534 644

Kalman filtering assumes that the ratio of the measurement vector z to a position vector x is linear with additive Gaussian zero mean noise. It also assumes that the previous position x_t.i and current position x_t is linear with additive Gaussian zero mean noise.

The patent publication W0-A1-2005 / 119 293 relates to a method for determining the location data for at least one node (K1) in a network, which method comprises a number of nodes (K1 ..... Kn), wherein the location data refers to an internal coordinate system. The method comprises the following steps: a) preparing position data for a subgroup (u) of nodes (K3 ..... K6), b) determining separation data (D1-3, ...,

D1-6) for said at least one node (K1), c) determining, or repeating step c), correction of location data for said at least one node (K1), dependent on location data from step a), separation data determined in step b) and location data for said at least one node, and d) repeating steps a) - c) until an interrupt relationship is met.

Patent publication WO-A1-2006 / 002 458 relates, inter alia, to a procedure for providing authorized security services in a wireless network. The method comprises the steps of: receiving an access request from a node requesting access to the wireless network; calculating a probability level for a location for the access request node using information provided by the access request node and location information for the access request node obtained from signal values ​​for the access request node received by at least one existing authorized node in the wireless network; and deny access for the wireless network access request node if the probability level does not meet a specified network security threshold ratio. The location information provided by the access request node, the location information of the access request node obtained from the signal value, or both, may include manually specified data for the respective node. The signal value may include received signal strength measurement values ​​(RSS), arrival time values ​​(TOA), arrival time difference (TDOA) or arrival angle values ​​(AOA).

The patent publication US-B1-6407703 relates to a method for determining the geolocation of a transmitter using sensors located on a single or multiple platforms. Generally, the method comprises the steps of receiving a first value group relative to a first transmitter, the first value group comprising the angle of arrival, the arrival time difference and / or the altitude / altitude values,

534 644 receiving a first guess or estimate for the first transmitter and determining at least a second position estimate using at least one of the least square analysis set and Kalman filter analysis.

The patent publication US-A1-2007 / 0 180 918 relates to a self-organizing sensor network, wherein a number of sensor nodes organized themselves and include sensor elements, distance measurement elements and communication elements. The sensor network can locate individual, especially mobile sensor modes. Each sensor node 1 includes, inter alia, a central processing unit 4, a communication means 5 and a distance measuring means 6. The distance measuring means 6, in the form of the radar module, performs measurements in and for determining the distance to adjacent sensor nodes. By exchanging estimated positions via the communication means 5 and using appropriate filtering and / or learning methods, such as for example a Kalman filter, the sensors can determine their position in an internal coordinate system.

The patent publication US-A1-2007 / 0 060 098 relates to a radio frequency (RF) system and method for determining the location of a wireless node in a wireless sensor routing network. The wireless network comprises a plurality of wireless nodes interconnected with a digital computer, such as a server or a location processor, via a communication link. The method further comprises measuring the RF signal strength at the wireless nodes and / or differential arrival times of the received signals at the wireless nodes and / or the angle of arrival of the received signals at the wireless nodes. When the RF signal strength and DTOA measurement values ​​can be utilized, the results of each can be optimally combined using the least-squares estimator (LMS), or Kalman, to minimize any errors for the finally calculated positions.

The patent publication US-A1-2007 / 0 076 638 relates to efforts to determine the location of devices within a wireless network. An exemplary system comprises a wireless device that generates at least one pulse as part of an output signal and said at least one pulse is intercepted by anchor devices and is used, at the time of arrival, to determine the location of the exemplary device. Another exemplary system includes an input mode that generates a directed output signal, wherein the directed output signal includes data indicating its direction, and the directions of output signals from multiple anchor nodes are used when directed to a wireless device to determine the location of the wireless device.

534 644

Combinations of the pulse and directional antenna systems, devices used in each of these systems as well as ideas associated with these systems are also included.

The patent publication US-A1-2006 / 0 215 624 relates to communications between network nodes in connected computer networks. Described is a Neighbor Location Discovery Protocol (NLDP) neighbor protocol that determines the relative locations of the nodes in a grid. NLDP can be implemented for an adhoc wireless network, where the nodes are equipped with directional antennas and cannot use GPS. Because NLDP relies on nodes that have at least two RF transmitters / receivers, it offers significant advantages over previously proposed protocols that only use one RF transmitter / receiver. In NLDP, the antenna hardware is simple, easy to implement and easily accessible. The NLDP utilizes the host node's ability to operate simultaneously across non-overlapping channels to quickly collapse into the neighbor's location. NLDP is limited by the extent of the control channel, which operates in a radiant manner. However, by selecting a low frequency band, high power and low data rate, the extent of the control channel can be extended to match the extent of the data channel.

Patent publication US-B1-6,618,690 relates to any system that estimates some aspect of an object's movement, such as location. More specifically, the publication concerns the application of statistical filters, such as a Kalman filter, in such generalized positioning systems. The generalized positioning system uses a calculated association probability for each metric in a group of position metrics (or other aspect of the movement) at a particular time, which association probabilities are used to calculate a combined metric innovation (residue), which in turn is used in the calculation of the next estimating the position (or other operating position information).

Some disadvantages of the above mentioned solutions are that they require centralized calculation, are not robust to strong noise in the measured values ​​and convergence is not guaranteed.

The invention in brief

The aforementioned problems are solved by a system operable to locate nodes communicating in a wireless network according to claim 1. Each node comprises a partial ordering body operable to initially classify its node as an anchor node (A) for a measure of uncertainty. of the location estimate,

534 644, as a covariance norm for a position estimation error, is below a first threshold value, or classify its nodes as a non-anchor node, giving rise to a partial order of these nodes. Each node also includes a control means connected to the partial ordering means and a recursive filter means connected to the control means. Each time a node (X) receives a message from another node, the controller is operable to check that the second node is ahead of the node (X) in the partial order. The recursive filter means is operable to be applied in the current position and the measured value, giving an updated position. The partial ordering means is operable to update the status of the node (X) in the partial ordering. Each controller is operable to repeat the above, providing location and orientation for each node.

Many advantages of the system of the present invention are set forth later in the specification.

A further advantage in this context is achieved if the control means for each node is operable to find the position and orientation sequentially.

In accordance with another embodiment, it is advantageous if the control means for each node is operable to find the position and orientation partially or completely parallel.

Furthermore, it is an advantage in this context if each recursive filter means is a recursive smallest square filter or weighted recursive smallest square filter.

According to another embodiment, it is an advantage if each recursive filter means is a Kalman filter.

A further advantage in this connection is achieved if said partial ordering means is operable to assign an initially classified anchor node (A) to a fixed minimum ranking, where ranking refers to a unit that obeys a total order, where an anchor node (A) always precedes a non-anchor node. in the partial order.

Furthermore, it is an advantage in this context that said partial arrangement means for the non-anchor node (X), which receives and uses data from a group of nodes, does not assign the anchor node (X) a ranking higher than the highest ranking for said group of nodes.

A further advantage in this context is achieved if said partial ordering means is operable to re-classify a non-anchor node (X) as an anchor node (A) during the update if the measure of location estimation uncertainty is below the first threshold value and its current ranking is frozen.

534 644

Furthermore, it is an advantage in this context if each node also includes a memory means connected to said control means which is operable to store estimated angle of arrival (AOA) of a node (X) from each neighbor node, error (variance) of the AOA estimate, estimated orientation of the node (X), error (variance) for the orientation estimate, estimated position, and error (variance) for the position estimate.

The above-mentioned problems have also been solved by a method for locating nodes communicating in a wireless network according to claim 10. The method comprises the steps of:

- initially classifying a node as an anchor node (A) if a value of the position estimation uncertainty, such as a covariance norm for a position estimation error, is below a first threshold value, or otherwise classifying its node as a non-anchor node, giving rise to a partial order of these nodes;

- each time a node (X) receives a message from another node (Y), the node (X) performs the following steps:

- checking that node (Y) is ahead of node (X) in the partial order;

- applying a recursive filter for the current position and the measured value, which gives an updated position; and

- updating the status of the node (X) in the partial order; and the method also comprises the step:

- to repeat the above steps, giving location and orientation for each node.

Many advantages of the method of the present invention are set forth later in the specification.

A further advantage in this context is achieved if the procedure comprises the step of: sequentially finding the location and orientation.

In accordance with another embodiment, it is advantageous if the method comprises the step of: finding the position and orientation partially or completely parallel.

Furthermore, it is an advantage in this context if the recursive filter is a recursive least square filter or weighted recursive minimum square filter.

In another embodiment, it is an advantage if the recursive filter is a Kalman filter.

A further advantage in this context is achieved if the method also comprises the step of: assigning an initially classified anchor node (A) a fixed minimum rank 534 644, where ranking refers to a unit that obeys a total order, where an anchor node (A) always precedes a non anchor node in the partial order.

Furthermore, it is an advantage in this context if the method also comprises the step: assigning a non-anchor node (X), which receives and uses data from a group of nodes, a ranking that is higher than the highest ranking for said group of nodes.

A further advantage in this context is achieved if the procedure also includes the step: to classify a non-anchor node (X) as an anchor node (A) during the update, if the measure of location estimation uncertainty is below the first threshold value and its current ranking is frozen.

Further, it is an advantage in this context if the method also includes the step of: storing for each node estimated angle of arrival (AOA) of one node (X) from each neighbor node, error (variance) of the AOA estimate, estimated orientation of the node (X), error (variance) for the orientation estimation, estimated position and error (covariance) for the position estimation.

The above mentioned problem has also been solved with at least one computer software product according to claim 19. The at least one computer software product is directly rechargeable in the internal memory of at least one digital computer. The at least one computer program product comprises software code portions for performing the steps of the method according to the present invention, when mint a product is run on at least one computer.

It should be noted that the term "encompassing / comprehensive" as used in this specification is intended to denote the existence of a given characteristic, step or component, without the occurrence of one or more other characteristic properties, integers, steps, components or groups thereof excluded.

Embodiments of the invention will now be described with reference to the accompanying drawings, wherein

Brief description of the drawings

Fig. 1 is a block diagram of a system according to the present invention; Fig. 2 shows a flowchart of a method according to the present invention;

Fig. 3 schematically shows a number of computer software products according to the present invention;

Fig. 4 shows angles relating to two nodes X and Y; and

534 644

Figures 5-25 show a sequence of iterations 0-20.

Detailed description of preferred embodiments

In Figure 1, a block diagram of a system 10 that is operable to locate, i.e. find positions and orientations for nodes X, ..., Y, which communicate in a wireless network 12. For convenience, there are only two nodes X, Y in Fig. 1, with only the node X fully described. The node X comprises a partial ordering means 14X operable to initially classify its node X as an anchor node A if a measure of the uncertainty of the position estimation, such as a covariance norm for position estimation error, is below a first threshold value, or otherwise classify its node as a non- anchor node, giving rise to a partial order of nodes X, Y. The node X also comprises a control means 16X connected to the partial ordering means 14X, and a recursive filter means 18X also connected to the control means 16X. Also described in Figure 1, a memory means 20X is connected to the control means 16X. Each time a node X receives a message from another node Y, the controller is operable to check that node Y is ahead of node X in the partial order. The recursive filter means 18X is operable to be applied to the current position and measured value, which gives an updated position. The partial ordering means 14X is operable to update the position of the node X in the partial ordering. The controller 16X is operable to repeat the above, giving the position and orientation of each node X, Y.

In Figure 2, a flowchart of a method for locating, i.e. find positions and orientations for nodes X, ..., Y, which communicate in a wireless network. The procedure begins with block 50. The procedure proceeds, at block 52, with the step: to initially classify a node X, ..., Y as an anchor node A if a measure of the uncertainty of position estimation, such as a covariance norm for position estimation error, is below a first threshold value, or to otherwise classify its node as a non-anchor node, giving rise to a partial order of nodes X, .... Y. Then, at block 54, the procedure proceeds to ask: Does node X receive a message from another node Y? If the answer to this question becomes negative, this block 54 is executed again. On the other hand, if the answer is yes, then the procedure continues, at block 56, where node X performs the step: to check that node Y is ahead of node X in the partial order. If so, the procedure at block 58 continues with the step: to apply a recursive filter for the current position and the measurement value, which gives an updated position. Then the procedure continues, at

534 644 block 60, with the step: to update the position of node X in the partial order. The procedure continues, at block 62, to ask the question: Is the procedure completed? If the answer is negative, the procedure is completed at block 64. If, on the other hand, the answer is yes, then the step according to block 54 is performed again.

In Fig. 3, a schematic diagram of some computer software products according to the present invention is presented. There are n different digital computers 100i, ..., 100 displayed_n, where n is an integer. There are also n different computer software products 102i, ..., 102_n, here shown in the form of compact discs. The various computer software products 102i, .., 102_n are directly rechargeable in the internal memory of the n different digital computers 100i, ..., 100_n- Every computer program product 102i, .... 102_n comprises software code portions for performing some or all of the steps of Fig. 2, when the product (s) 102i ..... 102_n runs on the computer (s) 100i, .... 100_n. These computer software products 102i, .... 102_n may, for example, be in the form of floppy disks, RAM discs, magnetic tapes, opto / magnetic discs or some other suitable products.

In Fig. 4, the angles referring to the two nodes X and Y. are shown in Fig. 5. A sequence of iterations 0 - 20. is shown. Triangles illustrate estimated orientations. Circles illustrate estimated positions. Current orientations are upwards. Current positions are at the grid points given by the triangles' bases. Initial orientation estimates are uniformly random. Initial position estimates are all at the origin. Black shapes do not indicate anchor position and white shapes indicate anchor status. Figures in circles show current rankings as position anchors. Initially, anchors are located at (0.0), (0.1) and (3.3). The position estimation phase is started with a delay of five iterations after the orientation estimation phase. At each iteration, all nodes each send a broadband message. Each node communicates with neighbors within 1.5 grid steps, ie. inner (not edge) nodes communicate with eight neighbors.

INTRODUCTION

We present a new method for localization, ie. to find positions and directions of nodes communicating in wireless networks. The method is based on the use of direction information (angle-of-arrival, AOA), for received messages and estimation by recursive filters such as Kalman filters or recursive least squares filters. The method guarantees stability and convergence by passing the nodes in partial order. The method expresses the location problem as a number of linear equations and has the following advantages:

• Speed, only small amount of computations needed • Need only a small program in each node • All programs are identical • Need only a small amount of RAM in each node • No centralized computation needed • Requires no synchronization of messages • Direction and position are updated for each received message ( recursive estimation) • Estimates of direction and position can be run as parallel processes without risking instability • Robust and designed for strong noise in measurements • Automatic error estimates for all parameters • Two anchor nodes are sufficient and can be placed centrally • Over time, the nodes automatically become anchor nodes • Allows mobile nodes • Allows dynamic addition and removal of nodes • All nodes are handled uniformly • Simple, inexpensive, and energy efficient antennas are sufficient (e.g. ESPAR) • Can optionally integrate compass readings for calculating orientation • Optionally integrate distance measurements for position calculation • Not dependent on good starting guesses • Guaranteed convergence • System linearity allows use of linear Kalman filters

Examples of applications include:

Wireless sensor networks for monitoring forest fires. Nodes are dropped from aircraft and monitor the spread of forest fires. Directional antennas are used for AO measurements.

534 644

Motion detection in buildings. Security applications in buildings to detect personal movements. Can be used to detect the movements of unauthorized visitors in companies or in security-rated installations.

Reverse monitoring and game tracking. Record of movements of wild animals in the air, on land, or in the water. Wireless communication can be carried out electromagnetically in the atmosphere, and with sound or pressure waves in ground and water.

Traffic monitoring and vehicle tracking. Relative movements between vehicles and between vehicles and ground for collision warning or predictions of other imminent dangers.

Condition monitoring of vehicles and machines. Nodes can be planted into machines and appliances and monitor kinematics to detect wear or other changes in structure. If nodes are cast into the structure, they can first detect their positions automatically, and then continue to detect changes. For example, sensors can be cast into car tires to monitor deformation.

Measurements of buildings and structures. Nodes can be embedded in concrete and other cast materials. After casting, they can measure their position and report the state of the structure, e.g. how heating works, or structural damage after earthquakes.

Optimization of communications. In a mobile system, nodes can use location to optimize their communication, e.g. through location-aware routing algorithms (geographical routing) and communication protocols. Wireless sensor networks can reduce power consumption by eliminating the need to find routes.

State estimate for mobile robots. Robots can be seen as mobile nodes, and their position and configuration can be estimated.

Environmental monitoring. Nodes can be distributed to monitor environmental parameters such as temperature, concentration of substances, or radiation.

534 644

Position-dependent invoicing. Using location information, wireless service providers can offer location-dependent services.

Emergency calls. In emergency situations, a wireless node can automatically contact emergency services and report its position.

Mobile advertising. Businesses can follow the customers' position and display customized messages.

Asset tracking. Seeking lost children, patients, or pets; offer more efficient management of inventory in a factory.

Smart travel and shopping guides. Services that show around customers and visitors based on position in department stores, companies, hospitals, factories, malls, museums, and universities.

Handling of fleets. Tracking and use of vehicle fleets for police, rescue vehicles, shuttle and taxi companies.

Position-based wireless security. By using location information, only people in certain locations can access certain sensitive information.

Military surveillance. Position detection for monitoring military installations or to check if areas have been infiltrated by enemy groups.

Medical applications. Nodes can be injected into the blood or introduced into the digestive system to collect position-based data for diagnosis. Sensors can be used for long-term monitoring of the health status of outpatient or remote patients.

NOTATION x = Node X position (2D vector)

534 644

Λ χ = Estimation of x

V (x) = Covariance matrix for vector x

Φχγ = Angle of arrival (AOA) from Y to X in Z's local coordinate system

yxy ^{= π} + Yyx = a_z⁺ &lt;Pxy&gt; AOA from Y to X in the global coordinate system

Yxy = AOA from Y to X in the global coordinate system, estimated by node Z a_x = Direction of node X

V (x) = Variation of scalar estimation xv = Unit vector parallel to XY m (x) = Measurement of parameter x

V (m (x)) = Measurement variance of parameter x

NODMINNESUTNYTTJANDE

A node X stores the following data representing the state:

φ_Χγ = estimated AOA of X from each neighbor Y

V (&lt;Pxy) = error (variance) in the AOA estimate oh_x = estimated direction of X

V (a_x) = error (variance) in the directional estimate x = estimated position

V (x) = error (covariance) in the position estimate

It is advantageous to use φ to represent the state rather than y, since m (&lt;p) can usually be considered approximately statistically independent.

SENDING MESSAGES

Nodes may send messages at any time, and synchronization is not necessary.

534 644

For directional estimation, a node X sends a message containing the global AOA γ_χγ = ά_χ+ φ_χγ and its variance V (Y $ y) = V (Å_x) + V (q&gt; $ y) to a neighbor Y, assuming approximately independent between_x and &lt;p_xy.

For position estimation, X sends out a general message containing its position estimates x and variance V (x).

These messages can be combined so that X sends a general message containing the entire list of γ_χγ and V (y_Xy) for all its known neighbors, in addition to its estimated position and its variance.

RECEIVING MESSAGES AND CALCULATION OF DIRECTION

When a node X receives a message from Y, it makes a measurement m (q&gt;_Xy) of AOA as well as its variance V (m (g?_Xy)). It receives γ_γχ = π + γ £_γ and V (/ y_X) = V (Y_Xy) in the message, and considers this as a measurement of m (y_Xy) = γ_γχ - π. Given that Y &lt;X (i.e. Y precedes X in the partial direction estimation order described below), the estimates can_x and φ_χγ is calculated with a linear Kal man filter, using the measurement equation (z = Hx in the Kalman filter, compare appendix) 'Κγ_χγΐ

Here, the left-hand line represents a known measurement, and the right-hand line describes how the measurement depends on the current condition to be estimated. The matrix represents the output matrix (measurement matrix) H in the Kalman filter. Thus, for directional estimation, the Kalman filter can be applied with the following parameters:

x =

<img file="SE534644C2_D0004.tif" />

'V' (the_x) 0 ', θ

534 644

Yyx ~ⁿ

Ί f &lt;0 t

- ^ orient -

<img file="SE534644C2_D0005.tif" />

'where q_A and &lt;ty are user-defined parameters

V (rf_x) 0

V (m (cpjy))

If a direct compass reading β_χ = m (a_x) available, it can be included by adding another row to the set of measurement equations, 'η (γ_χγγ m (a_x) k 7

<td>Ί Γ</td><td>(Cl λ ^Ax</td>

<td> 0 1</td><td></td>

<td></td><td>(V XY)</td>

In this case, the Kalman filter also needs the variance. This variance can typically be considered constant, and can be determined by a calibration process. When this is not possible, it can easily be estimated by e.g. another Kalman filter.

For direction estimation that includes compass measurements, the Kal man filter changes as follows:

m (&lt;p £_y) βχ k 7 η ιί h = 0

<td></td><td>A &gt;&gt; '-</td><td> 0</td><td> 0</td>

<td>r =</td><td> 0</td><td></td><td> 0</td>

<td></td><td> 0</td><td> 0</td><td>ν (β_χ)</td>

<td></td><td>k</td><td></td><td> 7</td>

534 644

RECEIVING MESSAGES AND CALCULATION OF POSITION

When X receives a message containing the position estimate y and V (y) from a neighbor Y, X first checks that Y &lt;X (i.e., Y precedes X in the partial position estimation order). Then, the position estimate x and its variance V (x) for X itself can be calculated by a linear Kalman filter via the equation z = m (Hy) = Hy = Hx where v = (cozy_xy siny_xy)

Yxy = oh_x+ &lt;Tfy

H = (~ Vy V,)

V (z) + (VI)²V (Yxy) + H^TV (i) H v (YXy) = v (å_x^ V (we_y) and make a "certainty equivalence" assumption that y_xy = y_xy and

View_Xy) = V (Yxy) The formula for V (z) follows from Gauss' approximation formula for variances applied to z = Hy. Since the estimate y_xy from the directional estimation is used in the position estimation, so directional estimates affect position estimates. However, position estimates do not affect directional estimates, so errors introduced in directional estimation do not risk recirculation and cause stability problems.

Thus, for position estimation, the Kalman filter can be applied with the following parameters:

x = xp = V (x) z = He h = H

534 644

Q - Qpos ~

<img file="SE534644C2_D0006.tif" />

<img file="SE534644C2_D0007.tif" />

where g_x is a user-defined parameter r = V (z)

If a measurement r_xy = m (| yx |) of the distance | XY | is available, e.g. by using the received signal strength (also known as RSSI, “received signal strength indication”), it can be included in the estimate by adding two rows to the equation system 'Hy'

<img file="SE534644C2_D0008.tif" />

In this case, the Kalman filter also needs the variance V (r_xy). This variance can typically be considered constant and can be determined by a calibration process. When not possible, it can easily be estimated with e.g. another Kalman filter.

For position estimation including distance measurements, the Kalman filter parameters are changed as follows:

<td></td><td colspan="2">"-Vy V_X&gt;</td><td></td>

<td>h =</td><td></td><td> 1 0</td><td></td>

<td></td><td></td><td> 0 1</td><td></td>

<td></td><td></td><td></td><td></td>

<td></td><td></td><td>( Skin</td><td>γ</td>

<td>r = V</td><td>f</td><td colspan="2"></td>

[y M

Here, z and r are given as block matrices.

STABILITY AND CONVERGENCE BY PARTIAL ORDER

An essential characteristic of the method is the use of partial arrangements.

APPENDIX: KALMAN FILTERING OF A CONSTANT

534 644

The Kalman filter is an example of a recursive filter that enters a state and a measurement, and returns an updated state. The condition is accompanied by its variance as an error estimate. In the case of constant state, the Kalman filter can be described with the following pseudo-code:

S + -P + Q

HSH + R

Λ Λ ZS x &lt;- x + K (z - / - / x)

P + -S-KHS

Here is

Λ x = Condition estimates (vector) z = Measurement (vector)

P = V (x), error (covariance) ix (matrix)

Q = Convergence rate parameters, can be interpreted as process cartilage variance (matrix). This is a user-defined parameter

R = V (z) covariance of measured value z (matrix)

H - Output die; describes how measurements depend on the condition (matrix)

Implemented as executable program code in a package such as Matlab or Scilab, the filter can be expressed as follows: function [x, p] = kalman (x, p, z, h₁q, r) s = p + q;

k = s * h7 (h * s * h '+ r);

x = x + k * (zh * x);

p = sk * h * s;

end function

Summary: For many applications of wireless sensor networks, it is important to locate the nodes, ie. find their direction and position. If wireless nodes are limited to measuring the amplitude and phase characteristics of radio transmission at location, the measurements will be affected by noise,

534 644 for example caused by scattered reflections and multi-way fading. Therefore, a method of localization based on transmission characteristics needs to be noise-resistant.

In this article, we describe a fast, fully distributed, local method that calculates a node's direction using directional antennas. One advantage of this method is the noise resistance: The method uses only Kalman linear filters. Some other advantages of the method are that it can optionally combine with compass data and continue to be linear; it uses only a small amount of memory and calculations; Antennas need only directional diversity at reception, while broadcasts can be made in general ("broadcast"), so no communication structure needs to be arranged in advance.

Keywords and phrases: Location, direction, wireless sensor network, directional antenna, linear Kalman filter, distributed algorithm, reception angle, self-organization.

In Introduction

For many applications of wireless sensor networks (WSN), it is an important prerequisite to locate the nodes, ie. find their direction and position. These parameters can be calculated from measurements of amplitude and phase for radio transmissions between nodes in the network. For example, distances can be estimated by measuring received signal strength (RSSI) and the angle of arrival (AOA) can be estimated by measuring the phase difference between two antenna elements (time difference of arrival, TDOA, or "time of arrival"). LOO). Unfortunately, such measurements are affected by many different types of noise sources, such as scattered reflections, multi-way fading, or interference with unrelated traffic. Most published algorithms based on transmission properties for WSN location are designed to measure a "snapshot", and then calculate the location parameters from this set of data [LR 2005], [Nic 2004], [EIA 2005], [SHS 2007], I this article we propose a filter method that calculates a new estimate at each node as soon as it receives a new message. The main advantage of this method is its robustness to noise. One disadvantage of some filtering methods is that they require extensive calculations, which may appear to be an obstacle to application in WSN with limited computational power. However, we show that it is possible to perform the necessary calculations only using low-dimensional, linear Kalman filters [WB 2006], [GA 2001], which only

534 644 needs a smaller amount of calculations. This method can optionally combine compass measurements without the filter becoming non-linear. It can also be used for mobile nodes if the movement is slow compared to the message frequency.

Another problem but many published algorithms are that they are limited to distance measurements, which makes it impossible to determine direction. Devices such as compasses can, of course, be used to measure direction locally, but compasses are not precision instruments and are sensitive to magnetic deviations. One reason why distance measurements are popular is that a simple dipole or monopoly antenna is sufficient, while AOA measurements require a directional antenna. Such antennas are often assumed to be large, complicated, and power-consuming, but in recent times new types of simple directional antennas suitable for WSN have received increased attention [Har 1978], [TS 2002],

The class of algorithms we focus on in this article are the fully distributed location algorithms [LR 2005], which do not require any centralized calculation. More specifically, according to the terminology in [Nic 2004], we propose a distributed, localized algorithm for finding direction in an absolute coordinate system, using AOA measurements. A similar method is "DV bearing" [NN 2004], but this method uses triangulation, which makes it more noise sensitive.

Kalman filtration has been used for the related problem of (collective) localization in robotic [RB 2002], [GF 2002]. Published algorithms in this field use nonlinear models, and suffer from problems caused by local minimums, as well as requirements for using computationally heavy extended Kalman filters (EKF). Since we can use linear models and linear Kalman filters, we do not have these problems, and do not have a good initial guess for convergence.

Other features of the proposed method are that the antenna only needs directional diversity at reception, while transmissions can be made generally so that no synchronization and no communication protocol need to be arranged in advance, ie. it is self-organizing according to the terminology of [LR 2005]; a single, arbitrarily placed anchor is enough; no forwarding or flowing of messages is needed; coverage is 100%, ie no nodes are skipped, but each node will automatically receive an estimate; and nodes can be added and removed dynamically.

534 644

II Algorithms

A Network model and notation

A network N of communicating nodes in 2D is given. We consider a 2D scenario for simplicity, but the method can also be generalized to 3D. Each node has computational capacity as well as the ability to send and receive messages from neighbor nodes in a subset of N_x of N. When a node X receives a message from a node Y, X can also estimate the receiving angle (p_Xy in its local coordinate system, for example with a directional antenna, as well as the variance of this estimate. X can optionally include an instrument such as a compass to measure its global direction in 2D. There must be at least one node that has knowledge of its direction, ie. an estimate of its direction with finite variance. We use the following notation (fig. 1): a_x = node X orientation &lt;pfy = receiving angle (AOA) from node Y to node X in node Z's local coordinate system. We assume that this angle is the same as the transmission angle from X to Y.

Y_Xy = π + Yy_X = &lt;p_Xy + σ_ζ, AOA from Y to X in the global coordinate system.

yjy = AOA from Y to X in the global coordinate system, estimated by node Z. x = the estimate of x

V (x) = the variance of the estimate x

C (x, y) = the covariance of x and y ^rxy = distance between X and Y

B Memory requirements

A node X stores the following state information:

on_x = the estimated direction of the node

V (CR_x) = variance in estimated direction

Y_Xy - estimated AOA of X from neighbor Y in X's local coordinate system (one value for each neighbor)

534 644 ν (γχγ) = variance in AOA measurement (one value for each neighbor)

C (&lt;x_x, y_Xy) = direction covariance and AOA (one matrix for each neighbor)

The variances can initially be set to high values, which represent “unknown. The initial estimates are uncritical and can be set to zero.

C Transmission of messages

At arbitrary intervals, node X sends a general message containing the global AOA y_xy = q&gt;_xy + ά_Χ and their variances

V (yxy) = V (q&gt; yy) + V (å_x) for all neighbors Y.

D Receiving messages and calculating orientation

When X receives a message from neighbor Y, X measures the receiving angle &lt;p_Xy in its local coordinate system, together with the variance V (&lt;p_xy). The content of the message is Y's estimate of the global reception angle

Vyx ~^{π +} yxy ^ochdessvar’^ans View_X) = V (Yxy) Since the state vector

<img file="SE534644C2_D0009.tif" />

(1) and the vector of measured quantities ix \ &lt;Pxy

A, (2) is related by the linear equation z = Hx, where

H = (3) lo ij we can now apply a linear Kalman filter. A compass can be included by adding its reading β_Χ to z and add a row (10) at the bottom of H. The date equations for the linear Kalman filter are (4)

S «-P + Q

<img file="SE534644C2_D0010.tif" />

HSH^T + R (5)

534 644 x &lt;- (1-KH) x + / &lt;z

P &lt;- (1-KW) S (7) there _p _f V (d_x(C) a_x, y $ y) | C (&lt;Wxk) V (Y *_y) (6) (8) is the covariance matrix for the estimate x; Q is a user-defined matrix representing the process noise variance, alternatively the rate of convergence, given in advance, and ν (Φχγ) ^ (ΦχγΎχγ)

Ο (φχγ, γζγ) y (y_Xy), (9) is the measurement noise variance. P, Q, R, S are all symmetric 2x2 or 3x3 matrices, so the most computationally demanding operation is the inversion of the matrix HSH + R, which is easy for such small matrices.

III result

We have implemented the algorithm in a simulator and tested it on the following configuration: A single anchor was placed in origin, and 16 non-anchor nodes were placed in points with integer coordinates in a square 4x 4 pattern symmetrically around the origin. A node could hear neighbors within a unit radius. The standard deviation for receiving angle measurements was 5.7. The directions were uniformly randomized from [-77.77], and the initial guesses were all set to zero degrees. The mean error in direction, unit degrees, for ten generations of general messages from each node is shown in Figure 2.

IV Discussion and conclusions

In a situation with very little noise, a method based on snapshots can quickly produce a solution, and may use fewer messages than a filter method. But in a situation of significant noise, a filter method may be preferable, thanks to its built-in averaging. Because wireless transmission has a built-in noise, we believe that filtering methods can be a promising approach.

The greatest difficulty we encountered in the implementation of the proposed method was the determination of in which area (offset with multiples of 2π) an upper measured angle would be applied.

We have proposed a linear model and an associated linear Kalman filter for measuring direction. Here, linearity is a key feature, which brings with it a number of desirable properties, in particular noise resistance. Small linear Kalman filters are easy to implement, inexpensive, and appear as realistic alternatives for calculating direction in the WSN, given that nodes can measure reception angles.

534 644