WSAN simultaneous failures recovery method

• US 9,146,820 B2
• Filed: 04/29/2013
• Issued: 09/29/2015
• Est. Priority Date: 04/29/2013
• Status: Active Grant

• Current Assignee: King Fahd University Of Petroleum And Minerals
• Original Assignee: King Fahd University Of Petroleum And Minerals
• Inventors: Baroudi, Uthman, Alfadhly, Abdullah, Younis, Mohamed Farag
• Primary Examiner(s): BRYAN, JASON B
• Application Number:
  US13/873,101
• Publication Number:
  US 20140325257A1
• Time in Patent Office: 883 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2002 where interconnections or communication control functionality are redundant flexible arrangements for bus networks involving redundancy H04L12/40176
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04W 24/04 Arrangements for maintaining operational condition

Abstract

The WSAN simultaneous failures recovery method ranks each node based on the number of hops to a pre-designated root node in the network. The method identifies some nodes as cluster heads based on the number of their children in the recovery tree. The method assigns a recovery weight and a nearby cluster node to each node. Nearby cluster nodes serve as gateways to other nodes that belong to that cluster. The recovery weight is used to decide which node is better to move in order to achieve lower recovery cost. The recovery method uses the same on-going set of actors to restore connectivity. Simulation results have demonstrated that the recovery method can achieve low recovery cost per failed node in small and large networks. The results have also shown that clustering leads to lower recovery cost if the sub-network needs to re-establish links with the rest of the network.

Claims

1. In a wireless sensor-actor network (WSAN) having a topology defined by a plurality of connected sensor nodes and actor nodes, a computer- implemented WSAN simultaneous failures recovery method, comprising the steps of:

searching the plurality of connected sensor nodes and actor nodes in a breadth first search (BFS) manner, starting at a root node;

assigning a rank to the plurality of connected sensor nodes and actor nodes during the BFS of the plurality of connected sensor nodes and actor nodes, wherein the rank of each of the plurality of connected sensor nodes and actor nodes is determined by a number of shortest hops to the root node of the wireless sensor-actor network;

creating a recovery tree based on the rank assigned to the plurality of connected sensor nodes and actor nodes, the recovery tree having parent nodes;

defining roles of the plurality of connected sensor nodes and actor nodes based on levels of the plurality of connected sensor nodes and actor nodes in the recovery tree;

assigning a clustering weight and a recovery weight to each of the plurality of connected sensor nodes and actor nodes, the recovery weight being based on a number of hops to a particular one of the plurality of connected sensor nodes and actor node'"'"'s closest leaf node in the recovery tree, the recovery weight being used to determine how the plurality of connected sensor nodes and actor nodes are to move to restore connectivity, the clustering weight being based on the number of children nodes down in the recovery tree until a cluster is encountered, the clustering weight being used to determine which of the plurality of connected sensor nodes and actor nodes will form a new cluster head;

each of the plurality of connected sensor nodes and actor nodes checking its clustering weight against a predefined cluster size and when its clustering weight exceeds the predefined cluster size establishing itself as a cluster head and sending cluster identification to the cluster head'"'"'s neighbor nodes;

monitoring the network for the occurrence of a node failure;

upon determination of a failed node, each of the plurality of connected sensor nodes and actor nodes in a set of children nodes of the failed node in the recovery tree recursively transmitting its assigned recovery weight and an ID of its parent to other ones of the plurality of connected sensor nodes and actor nodes in the set of children nodes of the failed node and saving received assigned recovery weights and IDs from the other ones of the plurality of connected sensor nodes and actor nodes in the set of children nodes of the failed node, each of the plurality of connected sensor nodes and actor nodes in the set of children nodes of the failed node ceasing transmission of its assigned recovery weight and saving of received assigned recovery weights when a received assigned recovery weight is lower than its own assigned recovery weight, thereby leaving the other children nodes of the failed node with lower weight to recover;

moving each of the plurality of connected sensor nodes and actor nodes to positions having ranks that are at most half of the rank of the failed nodes away from the failed node, one of the plurality of connected sensor nodes and actor nodes becoming a recovering node taking the place of the failed node in the recovery tree.

2. The WSAN simultaneous failures recovery method according to claim 1, further comprising the steps of:

said recovering node broadcasting a recovered message to its neighbor nodes;

any of the neighbor nodes moving towards said failed node'"'"'s location ceasing movement towards said failed node'"'"'s location upon receiving the recovered message;

transmitting a response from said neighbor nodes to said recovering node;

said recovering node updating its list of children nodes upon receiving the neighbor nodes'"'"' responses;

said recovering node allowing a responding one of said neighbor nodes to rank said recovering node if said responding one of said neighbor nodes has the highest rank among said neighbor nodes having a higher rank than the rank of said recovering node;

said recovering node assuming the role of lost node if said recovering node does not receive a response to said recovered message broadcast, wherein said lost node sends a replacement request message to a selected one of said nodes whose weight is the lowest among the children of said lost node, said lost node then initiating movement towards a position of its cluster head, said lost node then resuming as the recovering node until the replacement request reaches a node without any children in the recovery tree.

3. The WSAN simultaneous failures recovery method according to claim 1, further comprising the steps of:

said recovering node broadcasting a recovered message to its neighbor nodes;

any of said neighbor nodes moving towards said failed node'"'"'s location ceasing movement towards said failed node'"'"'s location upon receiving the recovered message;

transmitting a response from said neighbor nodes to said recovering node;

said recovering node updating its list of children nodes upon receiving the neighbor nodes'"'"' responses;

said recovering node allowing a responding one of said neighbor nodes to rank said recovering node if said responding one of said neighbor nodes has the highest rank among said neighbor nodes having a higher rank than the rank of said recovering node;

said recovering node assuming the role of lost node if said recovering node does not receive a response to said recovered message broadcast, said lost node searching for a node with a higher rank;

if said lost node finds a node with a higher rank, then said lost node establishing connectivity with said node having the higher rank;

said lost node attempting connectivity with said cluster head if said lost node search did not find a node with a higher rank;

said lost node moving towards said root node of said network if said lost node fails to connect with said cluster head;

said lost node reattempting said search and connectivity with a node having a higher rank than said lost node;

said lost node stopping its movement and sending a stop request to a selected one of said nodes whose weight is the lowest among the children of said lost node, said lost node then resuming as the recovering node until the children nodes of said lost node have stopped moving.