Fault Detection and Recovery in Virtual Coordinates based Sensor Networks

I.     INTRODUCTION

Sensor networks are a bunch of sensors which monitor physical or environmental conditions, such as temperature, sound, pressure, etc. and send the acquired data through the network to a central location. They are used in many diverse areas such as industrial process monitoring and control, machine health monitoring, and for military and defense applications such as surveillance and intelligence monitoring. Owing to the harsh environmental conditions of deployment and limited battery life of sensor nodes, node failure is inevitable. Even a single node failure in the network can cause huge damages in the application. The sensitive nature of their application domain and the fact that nodes have stringent limitations on physical size and power consumption, makes fault detection and recovery paramount. Also, system recovery should come with minimum computational cost, require no human intervention, and restore the system’s functionality to acceptable performance levels. In the present work, we have developed an  algorithm for 3D sensor networks, which adapts naturally to recover VCs irrespective of the number of faults, size or shape of the network, and avoids flooding the network with updated VCs.

II.    MOTIVATION

Operations in Wireless Sensor Networks (WSNs) rely on the validity of the implemented addressing scheme for efficient system performance. Virtual Coordinates (VCs) are widely used for localization in ad hoc and sensor networks. VCs provide the most popular way to self-localize the nodes in a network. In a VC based addressing scheme, a set of anchor nodes are selected as landmarks and relative shortest hop distances from these set of anchor nodes are used as VCs for that node.

In the past, most of the research in the WSN domain has focused on 2D networks. But recently, owing to the plethora of emerging applications of 3D WSNs in various areas, like building monitoring [1], [2], underwater networks [3], [4], underground networks [5], air-borne networks [6], and so on, there is newly created need for efficient algorithms for 3D WSNs.

Three dimensional networks present a range of challenges to be dealt with for algorithm design while travelling from two-dimensional domain. This generally tends to introduce inefficiencies in the deployed VC systems for 3D environments. The following are some of the factors which require special attention while designing algorithms for 3D networks:

1. Difference in geometric properties – 3D networks present an additional degree for connectivity for sensor nodes which allows them to create different routing planes leading to alternate routes.
2. Increased complexity – The node density for the given volume can be high for 3D sensor networks. This requires refined anchor selection methods for unique VC assignment in the network. This can be solved by increasing the number of anchors used which leads to increased data dimensionality and hence the computation complexity of the algorithm. The alternative can be using a different anchor selection scheme which also would require structural changes in our original 2D algorithm.
3. Difference in connectivity – as we saw above that 3D networks possess an additional degree of connectivity, this implies that the connectivity information for the network has to be extracted in a different way so as to take the three-dimensional connectivity into consideration as opposed to the planar connectivity in 2D networks.
4. Obstacles – We have 3D obstacles in 3D networks causing reflection and absorption of radio signals which render Geographic Positioning System (GPS) and Received Signal Strength Indicator (RSSI) ineffective, increasing the need for virtual coordinates even more

Recently, there have been some efforts to address the need for algorithms for 3D WSNs. Algorithms that increase the tolerance of the network by changing the topology [7], [8], have been proposed; however, it is not always possible to move the network nodes or to deploy new sensors in such events. In fact, most WSNs have stationary sensor nodes. Also, most of these solutions are designed around 2D network infrastructure [9], [10], [11]. A solution has been provided in  [12], for increasing the network life by balancing the energy consumption, however, it is not possible to completely achieve this objective by using homogeneous nodes. And since WSNs generally consist of homogeneous nodes, the proposed solution is not efficient. There has been some work in energy management, deployment of new nodes or system re-establishment, though not much work has been done in repairing the system when intermediate nodes fail without starting over, and moving or introducing new nodes. Thus, we feel that it is paramount to design a solution for node failure in stationary 3D networks with minimum repair cost.

III.   VIRTUAL COORDINATE RECOVERY ALGORITHM

We consider an anchor-based VC system, in which the VCs of a node correspond to the shortest hop distances to a set of anchors. Table 1 table lists all the notations used in this document. We have used the ENS anchor selection [13] that provides unique VCs with a very low number of anchors. The coordinate system is generated by each of the anchors flooding the network with a packet, where the hop count is incremented with each re-transmission of the packet. Flooding is controlled by each node by forwarding only the packet with the least hop count. At the end of this process by anchor A_j, each node n_i is in possession of

hniAjcorresponding to the minimum hop distance to that anchor. The virtual coordinate-set of the node i is given by

Vi=[hniA1,…,hniAM]corresponding to all the M anchors. We use the term virtual ordinate to refer to an individual term in this vector.

1.      NOTATIONS USED IN TEXT