Keywords

1 Introduction

Wireless sensor network (WSN) applications are spread over a wide range of domains such as environmental monitoring, health monitoring, military, inventory tracking, and disaster detection systems. These networks containing thousand to millions of nodes provide distributed monitoring by their properties such as collaboration, adaptation, and self organization. However, the distributed nodes may not have knowledge on their coordinates, relative distance from the neighbors, whole structure of the network, and physical voids in the network. This knowledge is significant for developing network awareness among the nodes for efficient data transfer.

A large sensor network with nodes having knowledge about their location is not a realistic solution due to the huge cost involved in integrating GPS, inaccessibility of GPS signal in environment, such as indoor or under dense foliage, and the complexity and errors of other localization techniques. In this scenario, one of the major requirements is to develop virtual coordinates (VCs) for each node. This has been achieved through a VCS [1]. VCS is capable of preserving the node’s connectivity in the network. However, this VCS method lacks in generating distinctive virtual coordinates for all nodes in the network. Hence, network awareness cannot be completely achieved through a hop-based VCS alone.

Topology preserving maps (TPM) [1] preserve the neighborhood information of a network that does not have exact physical coordinates but provides a distorted map of the original topology. TPM gives the ability to visualize the structural characteristics of such networks. It maintains the internal and external outlines of the network and provides an alternative for physical maps for many applications such as tracking [2], routing, mapping, and boundary detection. TPM will also make network design and network management processes easy for large sensor networks.

The paper [1] introduces a technique for obtaining a topology preserving map of the network through a virtual coordinate system (VCS) which uses hop count to generate VC. We propose a distance-based VCS to improve the accuracy of the map obtained using hop-based VCS. This will provide more accurate TPM of the network by providing distinctive VC for every node. This will be helpful for better and efficient WSN routing, boundary detection, backbone identification of the network, and network management.

Section 2 discusses the related work. Section 3 details the distance-based VCS generation technique. Section 4 discusses the simulation and the performance evaluation of the proposed methodology. The conclusion and the future work are described in Sect. 5.

2 Related Work

Large-scale application includes a high density of nodes deployed in areas. This brings its own challenges which include scalability, fault tolerance, density, operating environment, transmission media, and sensor network topology [3]. On the other hand, it also brings real-time challenges due to the varying dynamic environment or physical damages of devices. Network awareness means achieving knowledge about the entire network, density of the network, physical layout, and physical voids. Network awareness among nodes helps maintain sensor network services without any delay due to node failures. Also, knowledge of structural characteristics is vital for the management of large topology complex networks.

The self awareness among nodes will improve network quality of services and resources utilization. In [4], the authors introduced a self-management solution to detect fires in an area using a Voronoi diagram to identify nodes and angstrom index to prioritize the messages. When the risk of fire was high, data was disseminated at a high data rate or else reduced. This method was for a specific application. Thus, there is a need to bring a self awareness technique that can be applied to all scenarios.

In the research papers [1, 5], the authors proposed a scheme to generate virtual coordinates which represent minimum hop count from anchor nodes. Through singular value decomposition transformation, they generated the topology preserving map. The authors observed that the performance of address-based routing improved as the network awareness develops in the node. However, in these studies, the authors have not considered reducing the probability of having the same virtual coordinate for some nodes in scenarios where density of nodes is high or nodes have a high range.

Geographic routing [6] which scales well is best for resource constraint large sensor networks. For this, nodes should know the location of all the other nodes. Node localization cost, deployment, use of GPS, and failing due to physical voids are the limitations of geographic routing. In order to overcome these limitations, virtual coordinate systems are introduced to generate virtual coordinates which can be used as an alternative to geographic coordinates. In [7], the authors performed a conformal mapping to prevent failure of greedy forwarding at intermediate nodes.

Mal et al. [8] come up with a VCS where they used connectivity information in the setup phase to generate virtual region. In order to route packets in regions that have the same virtual coordinates, the authors used neighbor table for route which needed regular updating. Therefore, there is need to develop a VCS that accounts for nodes that have distinctive virtual coordinates.

Virtual coordinates are obtained with reference to anchors nodes selected in VCS. Thus, anchor placement in the network plays a major role. Extreme node search (ENS) [9] uses a directional transformation to identify how many anchors should be placed and its position in the network. A solitary anchor node is placed at the center in the spanning path virtual coordinate system (SPVCS) [10] which showed better performance for small networks. In the Virtual Coordinate assignment protocol (VCap) [11], the farthest three nodes in the network were chosen as anchor nodes to generate virtual topology.

Most of the work done in achieving network awareness will be helpful in achieving fault tolerance, efficient resource utilization, and efficient and cost-effective replacements for geographic routing for large-scale sensor networks. Our work focuses on achieving network awareness by enhancing the topology preserving map considering different network topologies, voids, connectivity and reducing the probability for having nodes with the same virtual coordinates.

3 Design of Distance-Based Virtual Coordinate System

Among different virtual coordinate systems, a major study has been done on hop-based VCSs where every node has virtual coordinates which represents the minimum hop distance from anchor nodes in the network. So in this system, nodes within the transmission range of an anchor node will same virtual coordinates. The resulting TPM obtained through this system does not portray the actual physical topology of the network. Hence, it is necessary to introduce a technique which is able to reveal those hidden structural characteristics by reducing the chance to have nodes with the same virtual coordinates. Thus, we introduce a novel distance-based virtual coordinate system (D-VCS) to capture the structural characteristics of a network in a better way compared to hop-based VCS. Here, instead of minimum hop distance from anchor nodes, the physical distance between the nodes along the shortest path to all anchor nodes is used to generate the virtual coordinates.

Consider an anchor node as shown in Fig. 1a, having a transmission range ‘R’ in VCS. All the nodes that lie inside the circle of radius R will have the same minimum hop distance from this particular anchor node, i.e., a hop count of one for all nodes within the range R as depicted in Fig. 1b. However, in the case of the proposed distance-based VCS, instead of hop count, the physical distance between the node and the anchor estimated using any localization method such as RSSI is used to calculate the VC. So every nodes within the transmission range will have a distinctive position based on the distance, i.e., each node inside the range of the anchor will have different coordinates which is shown as multiple levels in Fig. 1c. Even if the density of the network becomes high or if the range of the nodes is high, the probability of having nodes with the same virtual coordinates can reduce through this approach. The proposed D-VCS to generate accurate topology preserving maps also consists of three main phases as in the existing hop-based VCS: virtual coordination (VC) generation, topology coordinate (TC) generation, and topology preserving map (TPM) generation. The main difference of the proposed algorithm with the existing hop-based VCS is in the virtual coordination (VC) generation phase, wherein we determine the actual distance between nodes rather than the hop count.

Fig. 1
figure 1

Limitation of hop-based VCS

Full size image

3.1 Virtual Coordinate Generation

In hop-based VCS, the minimum hop distance from all anchor nodes is represented as the virtual coordinates of every node in the network. However, in the proposed distance-based VCS, the virtual coordinate is characterized by the summation of distance between nodes along the shortest path to all anchor nodes. If a network consists of N nodes in which M nodes are chosen as anchor nodes, ith node is represented by the vector;

$$P\left( i \right) = \left[ {d_{iA1,} d_{iA2, \ldots \ldots } \,d_{iAM} } \right]$$
(1)

where d iA1, d iA2,…… d iAM are the distance from ith node to all M anchor nodes, respectively. In the VC generation phase, all the nodes will generate its VC through the initial setup phase which uses random routing. When a packet is received by an anchor node for the first time, it will attach its ID and a distance value field and forwards it to the random neighbor node. A node will store the node ID when it receives the message from a node for the initial time, and it will calculate the distance from the sender. The node will then add this calculated value with the distance value in the message received. Figure 2 shows an example network showing VC generation. When the packet is sent by the anchor A1, it will append its ID A1 and a distance value field with value zero. When this packet is received by a node, it calculates the distance from the sender and adds it with the distance value from the packet. If the distance between the nodes is 2 units, on receiving the packet from A1, it calculates the distance as 2 and adds this with 0, received as the distance value from the node. So the node will have 2 as the shortest distance from anchor A1. Eventually all the nodes will generate VC when sufficient packets are flowed through the network.

Fig. 2
figure 2

An example showing VC generation

Full size image

3.2 Topology Preserving Map Generation

In the topology coordinate generation phase, a node will generate its topology coordinates using singular value decomposition (SVD) on the VC matrix of the network. The length of VC vector of all nodes in the network will be M if there are M anchor nodes in the network. There is a matrix which contains VCs of all nodes in the network, P of order N × M. In order to procure the significant information about the topology from the dataset P, we apply SVD on P

$$P = U \cdot S \cdot V^{T}$$
(2)

where U, S, and V are N × N, N × M, and M × M matrices, respectively. Then U∙S gives coordinates for P under the new basis V.

$$P_{\text{svd}} = U \cdot S$$
(3)
$$\left[ {x,\,y} \right] = \left[ {P_{{{\text{svd}}2}} ,\,P_{{{\text{svd}}3}} } \right]$$
(4)

where P svd is an N × M matrix which contains the information about the original network. The most significant information lies in the first component and it decreases for higher components. The second and third components contain the two-dimensional x and y coordinates, and thus, they are used to generate topology preserving maps.

4 Simulation and Results

The realization of the proposed D-VCS was done on Matlab 7.8.0, R2009a. In order to qualitatively analyze the accuracy of the maps obtained, we considered different network topologies such as random network with void, rectangular network, and rectangular network with void. In each network, we tried to vary the size of the network, density of the network, number of anchor nodes, anchor placement, and transmission range and analyzed the effect on the topology preserving map obtained. Furthermore, in order to quantitatively analyze the efficiency of the TPM obtained using the proposed distance-based VCS, we introduced a metric known as connectivity error.

4.1 Effect of Transmission Range

It is observed that when the range of the nodes were high in such a way that nodes had one hop connectivity with most of the nodes in the network, the hop-based VCS failed to map the network. When the transmission ranges of the nodes were low, both hop- and distance-based VCS showed similar maps. In Fig. 3, the first map is the original rectangular network with void including 121 nodes, 5 anchor nodes placed on boundaries, and one on the center, with all nodes having a range of 200 units. The second map is the TPM based on hop-based VCS, and the third map shows the TPM based on D-VCS. It can be seen that the hop-based VCS failed to obtain TPM compared to the D-VCS. Since the nodes had a high range, all the nodes were in one hop connectivity with the anchor nodes; thus, every node had the same virtual coordinates. When the transmission range was small of 10 units, both hop-based and distance-based VCS showed similar maps which can be seen in Fig. 4.

Fig. 3
figure 3

Rectangular network with void; 106 nodes, transmission range 200, 5 anchor nodes

Full size image
Fig. 4
figure 4

Rectangular network with void; 106 nodes, transmission range 10, 5 anchor nodes

Full size image

4.2 Effect of Number of Anchor Nodes

When the number of anchor node in the network increases, the probability of having identical virtual coordinates decreases because each node will have distinct distance between all the anchor nodes, and thus, accuracy of the map increases. In case of random network with void of size 500 nodes, the network with 20 anchor nodes had better topology preserving map than the network with 10 anchor nodes. Figure 5 shows the random network with 10 anchor nodes and Fig. 6 with 20 anchor nodes.

Fig. 5
figure 5

Random network with void; 500 nodes, transmission range 50, 10 anchor nodes

Full size image
Fig. 6
figure 6

Random Network with void; 500 nodes, transmission range 50, 20 anchor nodes

Full size image

4.3 Effect of Anchor Placement in the Network

It is observed that proper anchor placement on the network played a major role on the accuracy of the maps. In case of the rectangular network, when the anchors were placed on the boundaries, and one on the center of the network, more accurate TPM was obtained as shown in Fig. 7, than compared to same network with same number of anchors placed randomly as shown in Fig. 8. It can be observed that networks with anchors placed far apart obtained a better map than networks with randomly placed anchors.

Fig. 7
figure 7

Rectangular Network; 441 nodes, transmission range 10, 5 anchors placed on boundaries of the network

Full size image
Fig. 8
figure 8

Rectangular network; 441 nodes, transmission range 10, 5 anchors randomly placed

Full size image

4.4 Connectivity Error

Connectivity error represents the error in total connectivity that each node has in the original network with the total connectivity and each node has in the TPM. It is observed that the TPM obtained from D-VCS shows lesser error compared to hop-based VCS which can be seen in Table 1. Furthermore, there was a mean deviation in connectivity error of approximately 23 % between both systems.

Table 1 Connectivity error for different network topologies for both distance- and hop-based VCS
Full size table

5 Conclusion

We performed an enhancement of the existing hop-based VCS by introducing distance-based VCS where the virtual coordinates of each node were characterized by the summation of the physical distance between nodes along the shortest path to all anchor nodes. It was observed that the distance-based VCS generated better topology preserving maps for different network topologies. In the case of high transmission range, distance-based VCS showed better TPM while hop-based VCS failed as a result of having the same virtual coordinates for nodes. The number of anchors and its placement in the network also affected the TPM generation. The connectivity error metric was less for distance-based TPM than the hop-based TPM. In the future, the improved TPM can be used for better routing and network awareness in WSNs.