create new tag
, view all tags
In the first phase, a small number of nodes within the network are elected as reference nodes for other nodes to calculate their locations from. For 3D networks, 6 reference nodes are sufficient (4 reference nodes are required for 2D networks).

There are 7 stages in Phase 1; one for each reference node plus a special 'node r' which is the node with the smallest ID in the network. Firstly, all participating nodes exchange the number of the stage they are currently on, node ID, hop count (zero in this case), a stable byte to show whether the current stage has converged yet, and special information regarding hop count (explained later) using APP_ELECTION packets.

The stage number shows which reference node position the candidate node is up for election. This prevents nodes which join late from interfering with a partially converged network and lets the network keep track of the election phase. The candidate node ID is the most suitable node in the network which is known to the broadcasting node. For example, if node 16 has a neighbour node 8, it will broadcast candidate node 8 for the position of 'node r' as it has a smaller node ID. The candidate hop count is simply the hop count to the candidate node from the broadcasting node. In the beginning nodes do not know of their neighbours; instead, they will elect themselves as candidates and broadcast their own information until a more suitable node is found.

When a node does not update its candidate node for a set period (ie. there is no better node in the network), the stage is considered converged and the stable byte is set to true. After a node is stable, once it receives a packet from at least one neighbour who is also stable it will prepare to advance to the next stage; it continues broadcasting its stable packet for a short while to allow other neighbours to stabilize before progressing.

Each node uses the received information to maintain a list of 'node r' and the six reference nodes: the reference node ID, hop count from itself to the reference node, stable control byte and the maximum hop count of that reference node.

Stage Number Candidate Node ID Candidate Hop Count Stable Byte Reference Node Distance

Table: Election Packet Structure (TYPE_PSVC, APP_ELECTION)

Node ID Hop Count Stable Byte Reference Node Distance

Table: Reference Node List (7 entries including 'node r')

In the Stage 1, the node with the smallest ID is chosen as 'node r'. However, in Stage 2, the node with the largest hop count to 'node r' is selected as reference node p1 hence nodes must also exchange information about the hop count to 'node r'; this is done in the reference node distance. Subsequent stages calculate reference nodes pi as the nodes with the maximum sum of square roots of hop counts to earlier reference nodes using the reference node distance field also. Any ties are broken by comparing node IDs and choosing the smallest.

-- XiaohongWu - 2012-01-24

Topic revision: r3 - 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