Topology Preserving Maps From Virtual Coordinates for Wireless Sensor Networks

A method of obtaining a topology preserving map from virtual coordinates of a sensor network is presented. In a Virtual Coordinate System (VCS), a node is identified by a vector containing its distances, in hops, to a set of nodes called anchors. VCS is a higher dimensional abstraction of the connectivity map of nodes, with dimensionality defined by the number of anchors. Physical layout information such as physical voids and even relative physical positions of sensor nodes with respect to X-Y directions are absent in a VCS description, and obtaining the physical topology has not been possible up to now. A novel technique, based on Singular Value Decomposition, is presented to extract a topology preserving map from VCS. Three options with different computation and communication complexities, as a result of using different subsets of coordinates as the input, are presented and analyzed; the input for the three cases consist of a) the entire virtual coordinate set, b) only the virtual coordinates of anchors, and c) virtual coordinates of a random set of nodes. Evaluation results indicate that last two approaches achieve comparable accuracy to the first, but with significantly less complexity. Topology preserving maps for networks representing a variety of topologies and shapes are extracted. A new metric termed Topology Preservation Error (E-TP) is defined to evaluate the topology preservation; it accounts for both the number of node flips and degree of the flips. The techniques extract topology preserving maps with E-TP less than 2%.