# LP algorithm based on virtual forces

Tags:
Last response: in Technologies
Share
Anonymous
December 23, 2004 11:42:46 AM

Hi,

Local Positioning (LP) is a way devices can estimate their positions
communicating with other devices in their proximity.
Local Positioning can be used with bluetooth-enabled mobile phones.

I would like to publish an interesting new LP algorithm here.

This LP calculation is based on virtual forces. Nodes which can see
each other (within range) attract each other, nodes which cannot see
each other (outside of range) repulse each other.
Starting from assigning random positions to the mobile nodes, the
iterative evaluation and application of the "attraction" expression
results in a position estimation on each node. The calculation is done
by the nodes themselves (distributed-iterative calculation).

**********Basics************

We have a mesh of nodes, which communicate over BT.
We have two types of nodes:

A. Nodes with known position (position is not determined by this
algorithm.)
B. Nodes with position, which must be estimated by this algorithm.

I consider the algorithm from the (B) type of node's point of view.

We have two options according to the 'input data' our algorithm is
based on:

A.: A node can have an estimate on the distance of another node in its
B.: A node only has one bit knowledge: whether a node is in its
proximity, or not.

First of all, assume distance=inf (infinitive) when the other node is
not in the proximity.

We can also consider the (B) case as an (A) case:
Let's assume distance=0 when the other node is in our proximity.

**********Propagating position information**************

A critical requirement is to propagate position information to nodes.
A node also need to have information on nodes not in its proximity.

Let's use the following algorithm:

- A node propagates its own position info in every PROP_TIME_INTERVAL
seconds with
[copy counter]=MAX_COPY_COUNTER (3?) to the nodes in its proximity.

- Every node has a 'position info table' with the following fields:
SUBJECT_ID: ID of the node of which the position info we store here.
SENDER_ID: ID of the node from which we received this info.
POS: Position of the node
REC_TIME: time stamp: when we got this info

- After receiving a position message, we add a record to the 'position
info table', we substract one from the [copy counter], and if still
positive, we forward the info to those nodes in its proximity, for
which 'toSend' is true.
toSend is true if we don't have a young enough info message directly
from the given node about the subject node. (This way we eliminate lots
of redundant messages.)

- We also have a simple 'nodes' table, with the following fields:
SUBJECT_ID
POS: the 'newest' known position of that node.
DISTANCE: estimated distance from that node, which can be [0,inf]

- We use some kind of algorithm to estimate the position of our node
using the data in the 'nodes' table.

***********Position info calculation.****************

Until this point we didn't specify how the estimation work, and what
exactly the position data is, so that the things described until this
point can be implemented as a general framework, with concrete
'calculation algorithm, and position format' as a variable 'plugin'.

I assume that we only have an (X,Y) 2 dimensional coordinate vector as
position info.
The estimated position of the node is calculated iteratively, as if
'virtual forces' are acting on the node.

We use the following expression:
POS += [some kind of constant]*Summa(forces acting on this node)

What are the 'forces' like?

If([measured distance]==inf) two nodes are 'tossing' each other. |F| =
[some kind of constant]/[actual distance]

If([measured distance]==0) two nodes are 'attracting' each other |F| =
[some kind of constant]*[actual distance]

If [measured distance] is a positive number, our node is 'N1' the other
node is 'N2':
Draw a line between 'N1' and 'N2'. Lets mark point 'N3', which is on
the line at [measured distance] distance to 'N1' in the direction of
'N2'.
Now, to calculate 'F': We can use the 'attraction expression' as if
'N2' attracts 'N3':

|F| = [some kind of constant]*[distance of 'N2' and 'N3']
Regards: