create new tag
, view all tags
A key component in the Virtual Localisation Algorithm is the Neighbour Acceptance Algorithm, which defines the conditions which need to be met in order for nodes to be considered neighbours. In this implementation, we draw heavily upon work done by Tony Grubman.

The neighbour acceptance algorithm implemented here works through the use of beacon packets. To begin, a single node is chosen as the 'root' node, and assigned the virtual co-ordinates [0, 0, 0] and begins broadcasting beacon packets. Any node within range will detect these packets and begin broadcasting their own beacons. To accept a node as a neighbour, eight beacons from that node must be received within 800 seconds, with at least one packet every 100 seconds. For example, if node A receives 8 packets from node B periodically at 100 second intervals, it will be accepted as a neighbour. Similarly, if node A received 8 packets from node B at 10 second intervals, it would also be accepted as a neighbour. However, if node A received 6 packets from node B within 200 seconds, but it took 120 seconds for the next packet to arrive, they would NOT be neighbours.

Symmetry amongst neighbours is determined by having the receiver check the incoming packet for their own address, indicating that the transmitting node sees them as a neighbour. When this condition is met, the receiver sets a flag indicating that the transmitter is a symmetric neighbour.

Once a neighbour is accepted, it is only discarded if no beacon is received within 100 seconds.

It should be noted that nodes transmit beacons every 6-18 seconds, in line with the algorithm proposed by Tony Grubman.

One small deviation from Tony's original algorithm is the use of shift registers, which allows us to observe the neighbour interactions with a moving window. Initiall, Tony's algorithm would discard a candidate if no beacon was received within the timeframe. With the new implementation, a shift register allows us to more easily adjust for different conditions, such as 7 out of 8 or 6 out of 8 rather than the original 8 out of 8 beacon condition.

One operational concern which arose was an unacceptably high bit error rate as the length of the beacon packets increased. Through some rudimentary testing, it was found that packets with size greater than about 100 bytes would regularly fail. To overcome this, the neighbour table was broken down into fragments, and transmitted 5 elements at a time, which was maximum number which could get through fairly reliably. To further mitigate the effects of bit errors, a second type of beacon was transmitted, which contained only node IDs and symmetry flags. This would allow a node to transmit all of its neighbour table elements in a single packet, thus reducing the effect of bit errors. This is possible as the neighbour acceptance algorithm does not require any location information to work, but simply which nodes are one hop away from the transmitting node. The location packets are then sent at a later time, and can be processed individually ie. we do not need for the entire neighbour table to be received to properly process the location information.

-- BenjaminFoo - 2012-02-06

Topic revision: r3 - 2012-02-07 - BenjaminFoo
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