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

Notation	Description
N	Total number of nodes
ni	Node i
M	Total number of anchors
Ai, i=1:M	Set of all anchors
hninj	Hop distance from nito nj
Vi=[hniAj,…,hniAM]	Node i’sVC
rniAj	Reliability variable of node iw.r.t. jthVC
Ri=rniAj,…,rniAM; rniAj∈{0,1}	Set of ni’sreliability vector
Ki	Set of nodes in ni’s1-hop neighborhood

When node failure affects the shortest path from an anchor to a node, the corresponding virtual ordinate of the node becomes invalid. For algorithms that work purely using anchor based VCs, invalid VCs can result in dramatic failures. The Virtual Coordinate Recovery Algorithm (VCRA), which have developed, detects node failures, and responds by recovering the VCs using a distributed adaptive approach in 3D sensor networks. The algorithm adapts naturally to recover VCs irrespective of the number of faults, as long as the network remains connected.

IV.   3D VIRTUAL COORDINATE RECOVERY ALGORITHM

We have modified our 2D anchor selection mechanism for the 3D networks. We establish the network using ENS anchors in 2D which starts with 2 random anchors – however, in 3D network we are using two pairs of initial random anchors and perform ENS to cover the added dimensionality of the network. The added ENS anchors help to allot unique VCs to the nodes in 3D network.

As discussed in a previous section, the 3D network differs in its connectivity. The 2D networks with 4 connected neighbors form a grid shape; however, its 3D extension has 8 connectivity making the connectivity and neighborhood information more complex to handle for network establishment, for flooding during execution of the algorithm and for routing during performance check.

Definitions

Following definitions explain the terminologies used in this text:

1.     Reliability of a Virtual Ordinate: Each node keeps a vector of flags

   Ricorresponding to the reliability of the individual virtual ordinate

   hniAj. The flag

   rniAjis 1 only if node

   iis reliable w.r.t. its ordinate for

   Aj. This is the case for the (j^th) ordinate

   hniAjif there is at least one node

   p∈ Kis.t. the following three conditions are satisfied at

   p:

hnpAj=hniAj-1;rnpAj=1;and hniAj≠0

(1)

If these three conditions are satisfied, then

(hniAj)is considered reliable and thus,

rniAj=1; otherwise,

rniAj=0.

2.     Affected nodes: Nodes that cannot satisfy the reliability condition in Eq. (1), after a node failure event, are referred as ‘affected nodes’ or ‘unreliable nodes’.

3.     Non-affected nodes: Nodes that continue to satisfy the reliability condition in Eq. (1), after the failure event, are referred as ‘non-affected nodes’.

Note that the status of a node corresponding to a given ordinate may change as the status of its neighbors change. This status change propagates over the region whose coordinates are affected by the node failure.

Assumptions

We make the following assumptions regarding the network:

1. The sensor nodes are stationary.
2. Each node is aware of its neighbors’ VCs. This can be easily achieved by each node exchanging the information with its neighbors; this is a part of normal VC based algorithms.
3. Failure of nodes does not partition the network.

Node failure causes neighbor change for its surrounding nodes. This triggers the VC repair algorithm. Thus, the system starts repairing itself as soon as the failure event occurs. This is irrespective of the location of the failure event in the network.

Algorithm Steps

The 3D Virtual Coordinate Recovery Algorithm (VCRA) can be summarized as follows:

1. Each node exchanges its VC information with its neighbors.
2. Any node

   nithat senses a change in its neighbors’ VCs initiates a reliability check for each of its ordinates. If the j^th coordinate is found to be unreliable, the node is affected and sets

   rniAj=0.

3. All the neighbors of nodes that have sensed neighbor VC or reliability change compulsorily conduct the reliability check;
4. Neighbors of affected nodes check for reliability;
5. Repeat steps 3 and 4 until a set of reliable node(s) is found
6. Affected node updates its unreliable ordinates

   Viand updates its reliability. Set

   rniAj=1

7. The recovered nodes act as reliable nodes and step 6 is repeated until there are no unreliable nodes in the network

V.    TESTING

To gauge the performance of the algorithm accurately we will be testing the networks at three instances: before failure, after failure, after repair. This will give us a better insight into the contribution made by this repair algorithm. For the testing phase, we would be using the definitions and performance metrics:

Nodes affected: total number of nodes with

rniAj=0after node failure

Nodes repaired: total number of nodes with

rniAj=0after node failure which were repaired to have

rniAj=1

Cost of repair: total messages exchanged in order to repair the entire network after node failure event

Routing performance:

Percentage Routability=total number of successful routing attemptstotal routing attempts

For the 2D algorithm, we had tested the algorithm on following two networks [14]:

1. Odd shaped: it has 700 nodes and includes concave as well as convex boundaries
2. Circle with voids: It has 421 nodes and has circular voids.

The XY-coordinates of these networks can be found [15].

We will be testing the algorithm on 3D networks of different shapes and sizes. Following will be the networks under test

1. Cube: a 15 x 15 cube with no voids
2. Spherical void Cube: the original cube with spherical voids

Figure 2. Types of networks used for testing in 3D domain.

Test Conditions

The listed networks will be tested for all practical node failure situations possible. We try to cover these in the following three cases:

1. Random node failure: It will be simulated by deleting the given percentage of nodes in random fashion.
2. Clustered node failure: It will be simulated by deleting the given percentage of nodes in clustered fashion.
3. Mixed node failure: It will be simulated by deleting half of the given percentage of nodes in random fashion and half in cluster.

We test the failure and repair for failure percentages from 0% to 20% in steps: 0, 2, 4, 8, 16 and 20. We stop at 20% because as per our observation, the node deletion after 20% causes network cuts leading to disconnected parts in the network. Although there are few algorithms which provide solutions to repair cuts in WSNs [16], a cut is caused when a large number of nodes fail or a network is not repaired after successive node failure events indicating an aggravated failure situation. This algorithm focuses on connected networks to provide solutions for initial node failure situations to promptly repair the network. Thus, we would not be testing the performance of the algorithm for disconnected networks. However, we would still observe how the algorithm performs for disconnected 3D networks, to study the behavior.

There is a slight performance degradation when we extend the 2D algorithm to 3D spaces, though it provides correct results. The performance depends on the structure of the 3D network. Surface 3D networks or thinner work very much like 2D networks; whereas, volume 3D networks tend to a have higher node degree and thus a different node connectivity. The wider the 3D network, the more the chances of nodes having duplicate VCs with exiting anchor selection scheme. It might also create multiple local minimas in the network, which would in turn reduce the routing success within the network. Thus, it is important to customize the algorithm for 3D to have a better performance.

VI.   EXTENSION TO OTHER NETWORKS

For the exploratory component of the project, we have explored the possibility of modifying the virtual coordinate algorithm to adapt it to other application domains. We have particularly looked at the routing protocols used for routing traffic on the Internet. The present routing algorithms focus on the global-knowledge scheme. This means that each router maintains an index of the location of every piece of information on the Internet. Though the algorithms work perfectly in the present, however they are not scalable and such an approach would not be feasible in near future, as the amount of information grows. Further, it would be very difficult to introduce fault tolerance and repair mechanisms if any links in the network fails. The mean-time-to-repair would be enormous, keeping in view the sheer volume of network-index data stored on a failed node. Keeping in view all these aspects, we have considered the possibility of using virtual coordinate based algorithms for traffic routing on the Internet. As we know, the virtual coordinates scheme does not depend on the global-knowledge but on the local information of the neighboring nodes.  So even if the network scales, the amount of index data on each node would not be as high. And automatic repair of nodes could be used, as we have used in our algorithm for the sensor networks. We still need to figure out an efficient and fail-safe way of mapping from IP addresses to VCs. This possibility could make an excellent future work on fault tolerant and automatic repair Internet routing algorithms.

VII. CONCLUSION

In the present report, we have presented our work on the development of an algorithm for fault detection and recovery in 3D wireless sensor networks. We have modified our existing 2D algorithm for 3D networks. The pseudo-code for the algorithm is ready, and we have started the coding and implementation phase. The test networks for 3D domain have been identified and performance metrics have been set up. We can say that we have completed approximately seventy percent of the proposed work. The final report would contain:

• The pseudo-code for the algorithm
• Explanation of notations, definitions and formulae used
• Description of the test networks
• Simulation results
• Explanation of the results
• Conclusions and inferences
• Directions for future work

References:

[1] J. Zhou, Y. Chen, B. Leong, and P. S. Sundaramoorthy, “Practical 3D Geographic Routing for Wireless Sensor Networks,” Proc. 8th ACM Conf. Embed. Networked Sens. Syst., pp. 337–350, 2010.

[2] D. V. K. Viswanath, K. M. Krishna, H. Hexmoor, and S. Singh, “Robot navigation in a 3D world mediated by sensor networks,” 2007 Int. Conf. Integr. Knowl. Intensive Multi-Agent Syst. KIMAS 2007, pp. 272–276, 2007.

[3] J. Heidemann, W. Y. W. Ye, J. Wills, A. Syed, and Y. L. Y. Li, “Research challenges and applications for underwater sensor networking,” IEEE Wirel. Commun. Netw. Conf., vol. 0, no. c, pp. 228–235, 2006.

[4] A. Davis and H. Chang, “Underwater wireless sensor networks,” 2012 Ocean., vol. 4, no. Vii, pp. 1–5, 2012.

[5] A. P. Jayasumana, Q. Han, and T. H. Illangasekare, “Virtual sensor networks-A resource efficient approach for concurrent applications,” Inf. Technol. 2007. ITNG’07. Fourth Int. Conf., pp. 111–115, 2007.

[6] J. Allred et al., “SensorFlock: An Airborne Wireless Sensor Network of Micro-air Vehicles,” … Networked Sens. …, pp. 117–129, 2007.

[7] M. Younis, I. F. Senturk, K. Akkaya, S. Lee, and F. Senel, “Topology management techniques for tolerating node failures in wireless sensor networks: A survey,” Comput. Networks, vol. 58, no. 1, pp. 254–283, 2014.

[8] A. A. Abbasi, M. F. Younis, and U. A. Baroudi, “Recovering from a node failure in wireless sensor-actor networks with minimal topology changes,” IEEE Trans. Veh. Technol., vol. 62, no. 1, pp. 256–271, 2013.

[9] Z. A. Bhuiyan, J. Cao, and G. Wang, “Deploying Wireless Sensor Networks with Fault Tolerance for Structural Health Monitoring,” IEEE Trans. Comput., vol. 64, no. 2, pp. 382–395, 2012.

[10] G. Han, L. Liu, J. Jiang, L. Shu, and G. Hancke, “Analysis of energy-efficient connected target coverage algorithms for industrial wireless sensor networks,” IEEE Trans. Ind. Informatics, vol. PP, no. 99, pp. 135–143, 2015.

[11] P. K. Sahoo and W. C. Liao, “HORA: A Distributed Coverage Hole Repair Algorithm for Wireless Sensor Networks,” IEEE Trans. Mob. Comput., vol. 14, no. 7, pp. 1397–1410, 2015.

[12] M. M. Baboli, S. R. Bajgan, and H. Alinejad-rokny, “The Enhancement of Network Lifetime by Mobile Node in OPP Routing of Wireless Sensor Network,” vol. 6, no. 1, pp. 1–6, 2015.

[13] D. C. Dhanapala and A. P. Jayasumana, “Anchor selection and topology preserving maps in WSNs – A Directional virtual coordinate based approach,” Proc. – Conf. Local Comput. Networks, LCN, pp. 571–579, 2011.

[14] G. S. Mahindre and A. P. Jayasumana, “Post failure recovery of virtual coordinates in wireless sensor networks,” 2014 7th Int. Conf. Inf. Autom. Sustain. “Sharpening Futur. with Sustain. Technol. ICIAfS 2014, 2014.

[15] C. N. R. L. CNRL, “Coordinates for simulating Wireless Sensor Networks.” .

[16] W. Lalouani, M. Younis, and N. Badache, “Optimized repair of a partitioned network topology,” Comput. Networks, vol. 0, pp. 1–15, 2017.