A method for obtaining topology-preserving maps (TPMs) from virtual coordinates (VCs) of wireless sensor networks is presented. In a virtual coordinate system (VCS), a node is identified by a vector containing its distances, in hops, to a small subset of nodes called anchors. Layout information such as physical voids, shape, and even relative physical positions of sensor nodes with respect to x- y directions are absent in a VCS description. The proposed technique uses Singular Value Decomposition to isolate dominant radial information and to extract topological information from the VCS for networks deployed on 2-D/3-D surfaces and in 3-D volumes. The transformation required for TPM extraction can be generated using the coordinates of a subset of nodes, resulting in sensor-network-friendly implementation alternatives. TPMs of networks representing a variety of topologies are extracted. Topology preservation error ( ETP), a metric that accounts for both the number and degree of node flips, is defined and used to evaluate 2-D TPMs. The techniques extract TPMs with ( ETP) less than 2%. Topology coordinates provide an economical alternative to physical coordinates for many sensor networking algorithms.

A Compressive Sensing (CS) based solution is proposed for centralized and distributed discovery of physical phenomena in large scale Wireless Sensor Networks (WSNs). WSNs monitoring environmental phenomena over large geographic areas collect measurements from a large number of distributed sensors. Compressive Sensing provides an effective means of discovery and reconstruction of functions with only a subset of samples. Traditional CS relies on uniformly distributed samples which limits practicality of CS based recovery. To enhance the flexibility of sampling and implementation, the proposed approach uses random walk based samples. Unlike uniform sampling, random walk based sampling enables individual nodes achieve phenomenon awareness, i.e., the physical distribution of the phenomenon. We also derive a theoretical upper bound for the reconstruction failure probability. Simulation results on the number of samples required and error show that random walk based sampling is comparable to uniform sampling but with superior energy efficiency. More importantly, the proposed scheme provides a practical solution for a range of applications where uniform sampling is less economical or even infeasible.

Existing methods for detection and tracking of mobile nodes and objects via sensor networks depend on physical localization of sensor nodes. Consequently, they suffer from disadvantages associated with localization, which is often costly, error prone, and in some cases even infeasible. Tracking mobile nodes in a topological coordinate domain is proposed as an alternative to that in geographic coordinate domain. Topological coordinates (TCs), the basis of recent developments in Topology Preserving Maps (TPMs), are derived from hop distances from each node to a small subset of nodes. A technique is presented to reduce the distortion closer to the edges of principal component based TPMs, thereby enhancing its accuracy, which in turn facilitates accurate mobility tracking. Topological Coordinate based Tracking and Prediction (TCTP) algorithm is proposed for tracking and predicting the position of mobile nodes in the TC domain. Simulation results presented show that tracking and detecting performance of TCTP is competitive with geographic coordinate based algorithms despite the fact that it relies only on hop distances to a subset of nodes.

A novel scheme is presented that allows individual nodes in sensor networks to achieve network/topology-awareness by listening to regular packets associated with applications. Nodes, initially oblivious to network topology and their position within the network, gradually infer information required to evaluate their own Virtual Coordinates (VCs). A Singular Value Decomposition based transformation allows each node to convert the VCs of nodes, gleaned from the source or destination address field of packets, to corresponding Topological Coordinates (TCs). Eventually each node generates a topology map of the network, thus becoming aware of its own location and those of other nodes. Effectiveness of self-learning scheme, in terms of convergence of different stages, and gradual development of network awareness at nodes are illustrated. While many applications of network awareness within nodes can be foreseen, we illustrate how performance of routing can improve dramatically over time as network awareness develops within a node.

A novel method of identifying boundaries of wireless sensor networks deployed on 2D and 3D surfaces is presented. It does not require costly, error prone localization algorithms or physical locations of nodes. Instead, a Virtual Coordinate System (VCS) is used in which each node is characterized by the hop- distances to a set of randomly selected nodes known as anchors. To use geometric relationships for boundary detection, it transforms the VCS to a Topology Preserving Map (TPM). A TPM generation scheme for networks deployed on 3D surfaces is derived as well. The boundary detection scheme proposed is simple, not computationally intensive, energy efficient, and can be used with physical coordinates as well. Five representative example networks show the proposed scheme to be effective, with 100% of boundary nodes identified correctly with no erroneous identification of non-boundary nodes as boundary nodes. Use of TPM based boundary detection scheme for detecting dynamic event boundaries, such as those of plumes, in a distributed manner is also illustrated.

A Directional Virtual Coordinate System (DVCS) is proposed based on a novel transformation that restores the lost directionality information in a Virtual Coordinate System (VCS). VCS is an attractive option to characterize the node locations in Wireless Sensor Networks (WSNs), instead of using geographical coordinates, which is expensive or difficult to obtain. A VCS characterizes each node in a network with the minimum hop distances to a set of anchor nodes as its coordinates. The proposed transformation supplements the virtual coordinates, thus preserving all the inheriting properties such as embedded information of geodesic distances in the coordinates. The virtual directionality introduced, alleviates the local minima issue present in original VCS. Properties of this virtual directional domain are discussed. With these directional properties, it is possible, for the first time, to consider deterministic algorithms in the virtual domain, as illustrated with a constrained tree network example. A novel routing scheme called Directional Virtual Coordinate Routing (DVCR), which illustrates the effectiveness of the Directional Virtual Coordinate domain is proposed. DVCR significantly outperforms existing VCS routing schemes Convex Subspace Routing (CSR) and Logical Coordinate Routing (LCR), while achieving a performance similar to the geographical routing scheme - Greedy Perimeter Stateless Routing (GPSR), but without the need for node location information.

Virtual Coordinate Systems (VCS) characterize each node in a network by its hop distances to a subset of nodes called anchors. Performance of VCS based algorithms is highly sensitive to number of anchors and their placement. Extreme Node Search (ENS), a novel and efficient anchor placement scheme, is proposed that demonstrates significantly improved performance over state-of-the-art. ENS starts with two randomly placed anchors and then uses a Directional Virtual Coordinate (DVC) transformation, which restores the lost directionality in traditional VCS, to identify anchor candidates in a completely distributed manner. A vector-based representation is proposed for the DVC domain, which is then used to introduce the concept of angles between virtual directions in the transformed domain. Ability to specify cardinal directions and use angles is a radical change from the traditional VC system approaches. By selecting two anchor pairs with near orthogonal directional coordinates under the DVC transformation, a novel Topology Preserving Map (TPM) generation scheme is developed. This new TPM generation scheme requires significantly less computations than the existing PCA based method. Use of ENS significantly enhances the PCA based TPM generation as well. Simulation results for representative WSNs indicate that the ENS based anchor sets significantly improve performance of all prominent VC based routing schemes. For instance, Directional Virtual Coordinate Routing, when combined with ENS anchor placement strategy, outperforms even the geographic Greedy Perimeter Stateless Routing scheme that relies on exact physical node coordinates.

Geo-Logical Routing (GLR) is a novel technique that brings the advantages of geographic routing to logical domain, without inheriting the disadvantages of physical domain, to achieve higher routability at a lower cost. It uses topology domain coordinates, derived solely from virtual coordinates (VCs), a better alternative for location information. In logical domain, a node is characterized by a VC vector, consisting of minimum number of hops to a set of anchor nodes. VCs contain information derived from connectivity of the network, but lack physical layout information such as directionality and geographic voids. Disadvantages of geographic routing, which relies on physical location information, include cost of node localization or/and use of GPS, as well as misrouting due to physical voids. With the ability to generate topological maps from virtual coordinates via a Singular Value Decomposition based technique, it is now possible to characterize a network with topological coordinates, which are shown to be more effective than physical coordinates for making routing decisions. By switching between a geographic routing scheme operating on topological coordinates and a logical routing scheme, GLR overcomes local minima in the respective domains. Performance results presented indicate that GLR significantly outperforms existing logical routing schemes - Convex Subspace Routing (CSR) and Logical Coordinate Routing (LCR) - as well as geographic scheme, Greedy Perimeter Stateless Routing (GPSR).

Virtual Coordinate System (VCS) based routing schemes for sensor networks characterize each node by a coordinate vector of size M, consisting of distances to each of a set of M anchors. Higher the number of anchors, the higher the coordinate generation cost as well as the communication cost. Identifying an effective set of anchors and encapsulating original VCS's information in a lower dimensional VCS will enhance the energy efficiency. Two main contributions toward this goal are presented. First is a method for evaluating the amount of novel information contained in an ordinate, i.e., in an anchor, on the coordinate space created by the rest of the anchors. This method can be used to identify unnecessary or inefficient anchors as well as good anchor locations, and thus help lower overhead and power consumption in routing. Second, a method for reducing the VCS dimensionality is presented. This Singular Value Decomposition (SVD) based method preserves the routability achieved in original coordinate space but with lower dimensions. Centralized and online realizations of the proposed algorithm are explained. Examples of different topologies with 40 anchors used in performance analysis show that coordinate length can be reduced on average by a factor of 8 without degrading the routability. Use of novelty filtering to select effective anchors prior to SVD based compression results in further improvement in routability.

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 (ETP) 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 ETPless than 2%

Random routing protocols in sensor networks forward packets to randomly selected neighbors. These packets are agents carrying information about events, or queries seeking such information. We derive the probability of a packet visiting a given node in a given step as well as the rendezvous probability of agents and queries within a specific number of hops at a given node(s) in a 2-D grid-based sensor network. The utility of the model is demonstrated by determining the protocol parameters to optimize performance of rumor routing protocol under different constraints, e.g., to evaluate the number of queries and agents to maximize the probability of rendezvous for a given amount of energy. Monte Carlo simulations are used to validate the model. The closed form exact solution presented, unlike existing models relying on asymptotic behavior, is applicable to small and medium-scale networks as well. An upper bound is provided for the case where the packet is not sent back to its immediate forwarding node. Simulation results indicate that the model is a good approximation even for sparse arrays with 75 % of the nodes. The model can be used to set parameters and optimize performance of several classes of random routing protocols.

Virtual coordinate based routing (VCR) is a class of simple scalable routing schemes for sensor networks. VCR relies on coordinates based on the number of hops to a set of anchors, rather than on geographical coordinates. Multiple nodes with identical coordinates and local minima encountered during routing degrade the performance of VCR. Properties of virtual coordinate systems are analyzed to provide insight into the nature of virtual coordinate space, and bounds are derived for path lengths. A new routing scheme, Convex Subspace Routing (CSR), is proposed. In contrast to existing VCR schemes that use backtracking or hill climbing techniques to overcome local minima, CSR avoids using anchors that cause local minima. CSR selects subsets of anchors dynamically to provide a convex distance function from source to destination. Consequently, it is less sensitive to anchor placement and over anchoring, and does not require tracking of route history for backtracking. Performance of CSR is evaluated for different network configurations. Results for varying node densities and different numbers of anchors indicate that CSR significantly outperforms Logical Coordinate Routing (LCR), in terms of routability, number of hops used for routing, memory usage as well as energy consumption.