create new tag
, view all tags
The virtual localization algorithm uses a spring energy function to determine a node's coordinates from its one-hop and two-hop neighbour information. Beacon messages are periodically broadcasted which include each node's own information (node ID, physical location (for comparison purposes) and virtual location) and those of its one-hop neighbours (same as above). Physical locations are read in during initialization from a manually updated table and are included purely for testing and comparison purposes (in a network running purely on virtual localization, they would not need to be included).

Self Information     One-Hop Neighbour Information            
Node ID Physical location Virtual location Node ID Physical location Virtual location Node ID Physical location Virtual location ...

Table 1.2 Beacon Frame (TYPE_VIRTLOC, APP_BEACON)

Virtual locations are stored as floats and are determined by minimizing the total energy of a node where energy is calculated as the sum of forces; one-hop neighbours have an attraction force and two-hop neighbours have a repulsive force. Each node perturbs its location by an iterative descent method with stochastic hill-climbing for 50 iterations.

One node must be chosen as the root node to act as both the sink for the network and a reference for the rest of the nodes. The root node maintains its virtual location at (0, 0, 0) and does not recalculate it. To improve convergence, only the root node sends beacons at the start of the program. Only after a node has received a set number of beacons from its neighbours, allowing it to estimate its own virtual location, then it will broadcast its beacons.

The algorithm maintains lists of its one-hop and two-hop neighbours in self.onehop_list and self.twohop_list respectively which update whenever a beacon packet is received (in ExtractBeacon()). Both lists have the same structure, and contain information on the neighbour's node ID, the hop distance (which will be either 1 or 2 hops), physical location (3D integer coordinates), virtual location (3D floating point coordinates) and time-to-live (TTL, set so that stale entries will delete themselves after three beacon periods with no new packets from that node).

Source Distance Physical Location Virtual Location TTL

Table 1.3 Neighbour List Structure

Upon termination of the thread, both neighbour lists (excluding the physical location information) are written to files in the folder 'results_VL' called VL_onehop_XX.csv and VL_twohop_XX.csv (where XX is the node ID). Additionally, a log file is written to in real-time called VL_log_XX.csv which shows each node's one-hop and two-hop neighbours every beacon period so that connectivity history can be traced.

-- XiaohongWu - 2012-01-24

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