create new tag
, view all tags
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_LANDMARK State Node ID Hop Counter K Hop Neighbour List End of packet
Table: Landmark Packet Structure (TYPE_HYPER, APP_HYPER)

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 landmark 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.

Once the triangulation is obtained, any degeneracies which may arise in the form of two holes adjacent at a vertex or a common chain of shared nodes must be removed by adding 'virtual nodes' to the network. For a simply-connected triangulation, [...]

-- XiaohongWu - 2012-01-24

Topic revision: r2 - 2012-01-25 - XiaohongWu
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