Archived from groups: alt.cellular.bluetooth (

More info?)

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

proximity (using RSSI).

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:

Adam Nagy