Tags:
create new tag
, view all tags

Self-Organizing Virtual Coordinates for Location-based Routing

Annabelle Ng January 2012

3. Landmark-based Triangulation Localization Algorithm

A number of nodes in a network are elected as landmark nodes which form 'cells' with their closest non-landmark nodes, effectively transforming the network into a Voronoi diagram. From this, a landmark-based triangulation can be obtained which easily allows the combinatorial Delaunay complex to be calculated. Embedding the Delaunay complex provides an idea of the network topology from connectivity alone, and may hold less ambiguity than other methods due to a global rigidity principle.

TYPE_LANDMARK

2

APP_LANDMARK

1

CTRL_ELECTION

0

CTRL_BORDER

1

CTRL_REQUEST

2

CTRL_RESPONSE

3

CTRL_EMBED

4

CTRL_RELAX

5

CTRL_FLOOD

6

CTRL_STAYALIVE

7

Packet Type and Applications

As mentioned earlier, the Landmark module will share the same type bits as Virtual Localization (TYPE_VIRTLOC and TYPE_LANDMARK are equivalent) and as such, it has only one application, APP_LANDMARK. The Landmark module implements its own control byte to all applications which are decoded within the module only.

3.1 Phase 1: Obtaining a Triangulation

First, a triangulation of the network must be obtained from the network connectivity information. As nodes do not have physical location information, triangulation is acquired through use of landmarks. A subset of nodes in the network are selected as uniformly distributed landmarks so that landmarks are k hops apart. Any nodes which are within k hops of a landmark become part of that landmark's cell and cannot become a landmark themselves.

Each node maintains information about whether it is 'active' (still in the process of defining its state), its current state (IN = node is a landmark, OUT = node is not a landmark and hence part of a landmark cell, NULL = initial unknown state) and its closest landmark (if any).

CTRL_

ELECTION

Hop Counter

Node ID

State

K Hop

Neighbour List

Election Packet Structure (TYPE_LANDMARK, APP_LANDMARK)

This is implemented by first choosing one root node, which acts as the first landmark and floods its k-hop neighbours with landmark packets. At the beginning, all nodes are 'active' and have a null state, meaning that they are not landmarks but are not part of a landmark cell either. The first landmark broadcasts that it is a landmark and it has a hop count of 0.

As neighbouring nodes receive the packets, if the hop count is less than k hops and they are 'active', they become part of that landmark's cell and deactivate themselves with state = OUT. Finally, they will increment the hop count, add their own node ID to the list and forward it to their neighbours.

Nodes keep information on the state of all their k-hop neighbours so that they can check if they are eligible to become a new landmark node. Each time period, all 'deactive' nodes flood election packets to their k-hop neighbourhood. If a node's k-hop neighbours with lower IDs all have definitive states and that node is 'active', not part of a landmark cell and its neighbours have not updated their states for a set period: the node will set itself as a landmark node and broadcast its new state.

CTRL_

BORDER

Hop Counter

Node ID

Distance

Simplex

Landmark IDs

Border Packet Structure (TYPE_LANDMARK, APP_LANDMARK)

Following this, non-landmark nodes which have multiple closest landmarks identify themselves as border nodes and send border packets to their landmarks, broadcasting their hop distances to each landmark. Upon receiving a border packet, landmarks are able to estimate their distances to all their neighbouring landmarks and learn which landmarks they share a simplex with, hence the triangulation is complete.

3.2 Phase 2: Embedding the Combinatorial Delaunay Complex

Once the triangulation is obtained, one simplex must be arbitrarily embedded first, hence a simplex involving the root node is chosen. At this point, the root node only knows of its smallest hop distances to the other two nodes in the simplex, but it does not know the distance between them. A special once-off request packet is sent from the root node to the simplex member with the smallest ID, to learn the distance to the remaining simplex member. When the request packet is received by the simplex member, it will send the required distance in a response packet for the root node.

CTRL_

REQUEST

Hop Counter

Root ID

Request ID

Request Pair ID

Request Packet Structure (TYPE_LANDMARK, APP_LANDMARK)

CTRL_

RESPONSE

Hop Counter

Root ID

Request ID

Request Pair ID

Distance

Response Packet Structure (TYPE_LANDMARK, APP_LANDMARK)

The root landmark now has enough information to embed its simplex using simple triangle mathematics and will broadcast these coordinates in embedding packets, containing each node's own ID and location, plus the IDs and locations of its neighbouring landmarks.

From this, each landmark can keep a table of its neighbouring landmarks, their distances and their locations. Landmarks can also determine if they have received coordinates from two landmarks in a simplex and a third reference landmark, which can used to calculate its own location via trilateration. If a node has extra information than necessary, it will take its location at the centroid of the multiple calculated values.

Self-Information

Neighbour Landmark-Information

CTRL_

EMBED

Hop Counter

Node ID

X-Coord

Y-Coord

Node ID

X-Coord

Y-Coord

...

Embedding Packet Structure (TYPE_LANDMARK, APP_LANDMARK)

3.3 Phase 3: Mass-Spring Relaxation

Landmark nodes run a mass-spring relaxation algorithm, similar to the one used in the PSVC module, to improve the topology after they have all converged to a stable location. Relaxation packets are exchanged during this stage to allow landmarks to know of their neighbours' neighbours which are used in the algorithm.

CTRL_

RELAX

Hop Counter

Stable

Node ID

X-Coord

Y-Coord

Neighbour List

Relaxation Packet Structure (TYPE_LANDMARK, APP_LANDMARK)

3.4 Phase 4: Non-Landmark Trilateration

Non-landmark nodes are now able to determine locations from the coordinates of their three closest stable landmarks using trilateration. The landmarks flood lasting twice the designated k-hop to reach outside their Voronoi cell using flood packets. Once a node has stabilized, it will periodically broadcast stayalive beacon packets.

CTRL_

FLOOD

Hop Counter

Node ID

X-Coord

Y-Coord

Flood Packet Structure (TYPE_LANDMARK, APP_LANDMARK)

CTRL_

STAYALIVE

Node ID

X-Coord

Y-Coord

Stayalive Beacon Structure (TYPE_LANDMARK, APP_LANDMARK)

3.5 Operation

This command calls Wisenet with the Landmark-based Triangulation program with Geographic Routing (--hop and -r are optional):

python wisenet.py -a XX --pro --sym --landmark (--hop) (-r)

This command calls the Landmark-based Triangulation program with Geographic Routing and Packet Generator:

python wisenet.py -a XX --pro --sym --landmark (--hop) -d YY -g -i AA --alrate=BB -n CC

Command/Option

Notes

--landmark

Opens Wisenet with Landmark-based Triangulation enabled

-r

Sets current node as root landmark

-d YY

Specify root landmark ID

Landmark-based Triangulation Options

The 2D visualization function is called as follows:

python draw_links.py --landmark

Each node keeps a log file detailing when it progresses to each phase and its location at each period. A neighbour table is output at the end of the program containing that nodes one-hop neighbours during time of termination. Hop count information is produced the same as for the previous modules.

Data packets are always forwarded to the root landmark, which acts as the sink node, as it has a known virtual location at (0, 0). When calling the packet generator, the destination node field must be set to the root landmark ID.

Relevant file(s): landmark_module.py, draw_links.py

Output file(s): LM_log_XX.csv, LM_onehop_XX.csv, LM_hop_count.csv (in results_LM)

-- AnnabelleNg - 2012-02-06

Topic revision: r1 - 2012-02-06 - AnnabelleNg
 
This site is powered by the TWiki collaboration platformCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback