Adaptive multipath routing failure recovery in a wireless network

Abstract

A method for operating a wireless network including a plurality of nodes, the method including: each node generating a set of paths to a head node; initiating an adaptive failure recovery method in the event of a source node sending a message data packet upstream and a discovery node encountering a failed node, wherein the discovery node is a node on a path taken by the message data packet from the source node to a destination node, the adaptive recovery failure method including: collecting, at the discovery node, relevant data, the relevant data comprising: a hop-distance between the failed node and the source node; a count of estimated extra hops required to deliver the data packet using a hop-distance recovery method; a count of estimated extra hops required to deliver the data packet using a multipath recovery method; and a latency time for the hop-distance recovery method.

Claims

1. A method for operating a wireless network (100) comprising a plurality of nodes (102), the method comprising: each node generating a set of paths to a head node (104); initiating an adaptive failure recovery method in the event of a source node (106) sending a message data packet upstream and a discovery node (112) encountering a failed node (108), wherein the discovery node (112) is a node on a path (110) taken by the message data packet from the source node (106) to a destination node, the adaptive recovery failure method comprising the steps of: collecting, at the discovery node (112), relevant data, the relevant data comprising: a hop-distance between the failed node (108) and the source node (106); a count of estimated extra hops required to deliver the data packet using a hop-distance recovery method; a count of estimated extra hops required to deliver the data packet using a multipath recovery method; a latency time for the hop-distance recovery method; and a latency time for the multipath recovery method; comparing, at the discovery node (112), latencies of the hop-distance recovery method and the multipath recovery method calculated from the relevant data; and depending on the comparison, selecting the hop-distance recovery method or the multipath recovery method.

2. The method of claim 1, wherein the set of paths are a set of disjoint paths.

3. The method of claim 1, wherein the destination node is the head node.

4. The method of claim 1, wherein the discovery node retrieves the hop-distance between the failed node and the source node by checking a time-to-live (TTL) of the data packet.

5. The method of claim 1, wherein the relevant data further comprises a hop-distance between a RMS and the source node.

6. The method of claim 5, wherein the discovery node retrieves the hop-distance between the RMS node and the source node by checking a time-to-live (TTL) of the data packet.

7. The method of claim 1, wherein the count of estimated extra hops required to deliver the data packet using the hop-distance recovery method and the count of estimated extra hops required to deliver the data packet using the multipath recovery method are estimated to be within a certain range, depending on multiple factors.

8. The method of claim 1, wherein if the inequality
X>(r+α+2−β)/2 is satisfied, then the hop-distance recovery method is selected, otherwise the multipath recovery method is selected, where: X is the hop-distance between the failed node and the source node; α is the count of estimated extra hops required to deliver the data packet using a hop-distance recovery method; β is the count of estimated extra hops required to deliver the data packet using a multipath recovery method; and r is the latency time for the hop-distance recovery method.

9. The method of claim 1 wherein the set of paths are generated using an optimization algorithm, such as a greedy algorithm.

10. The method of claim 1 wherein the latency time for the hop-distance recovery method is dependent on the density of the network.

11. The method of claim 1, wherein there is more than one failed node in the network.

12. The method of claim 1, wherein the network is for use in a hotel, and wherein the nodes are wireless devices in the hotel and the head node is a Room Management Service (RMS).

13. A wireless network comprising a plurality of nodes, the plurality of nodes comprising: a head node; and a source node, wherein the plurality of nodes are configured to generate a set of paths to the head node; wherein, in the event of the source node sending a message data packet upstream and a discovery node encountering a failed node, wherein the discovery node is a node on a path taken by the message data packet from the source node to a destination node, the discovery node is configured to initiate an adaptive failure recovery method comprising the steps of: collecting, at the discovery node, relevant data, the relevant data comprising: a hop-distance between the failed node and the source node; a count of estimated extra hops required to deliver the data packet using a hop-distance recovery method; a count of estimated extra hops required to deliver the data packet using a multipath recovery method; a latency time for the hop-distance recovery method; and a latency time for the multipath recovery method; comparing, at the discovery node, latencies of the hop-distance recovery method and the multipath recovery method calculated from the relevant data; and depending on the comparison, selecting the hop-distance recovery method or the multipath recovery method.

14. A wireless network comprising: a plurality of nodes, wherein the network is configured to operate in accordance with the method of claim 1.

15. A computer program product embodied on a non-transitory computer readable medium containing instructions that, when executed within a wireless network comprising a plurality of nodes, will configure the network to operate in accordance with the method of claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Certain embodiments of the disclosure will now be described by way of example only and with reference to the accompanying drawings in which:

(2) FIG. 1 is an example network with multiple nodes.

DETAILED DESCRIPTION

(3) FIG. 1 shows an example network 100 comprising a plurality of nodes 102, the plurality of nodes 102 including a head node 104, a source node 106, and a failed node 108. The network is configured to carry out a multi-path creation algorithm to create a plurality of paths between nodes in the network and the head node. Prior to initialization of this algorithm, individual nodes may be configured to collect information about their one-hop neighbouring nodes. This information may include unique node IDs, hop distances, and energy metrics, and may be and are received at each node by receiving advertising data packets or by using previous neighbour data collections.

(4) Upon initialization of the multi-path creation algorithm, route set-up is carried out by each node. Each route set-up is carried out in a hop by hop manner and with a specific purpose in mind. The purpose may be the shortest route to a destination node or the most energy efficient route or any other suitable goal. Multiple paths are derived using optimization methods. For example, the greedy algorithm is a simple and iterative method that is used to solve the routing path search. The code used to implement the greedy search algorithm is as follows:

(5) 1: procedure ORIGINAL SOURCE OPERATIONS

(6) 2: maxTTL=1, nPaths=0, maxPaths=K;

(7) 3: if nPaths<maxPaths then

(8) 4: generate a status message with TTL=maxTTL, goto 14;

(9) 5: else

(10) 6: end path creation;

(11) 7: if there are still neighbours to select with HopDistance>=TTL Or in TempExcluded then

(12) 8: maxTTL++, TTL=maxTTL, goto 14

(13) 9: else

(14) 10: delete status message, end path creation;

(15) 11: if routing ack received then

(16) 12: nPaths++, goto 3;

(17) 13:

(18) 14: procedure SENDING OPERATIONS

(19) 15: select neighbour with min hopDistance<TTL & !(PermExcluded) & !(TempExcluded);

(20) 16: if more than one neighbour then

(21) 17: select node in the same subnet with best RSSI;

(22) 18: if no nodes in the same subnet then

(23) 19: select node in another subnet with best RSSI;

(24) 20: send status packet, goto 27;

(25) 21: else if no neighbours available then

(26) 22: if original source then

(27) 23: goto 7; 24: else

(28) 25: send back a routing nack, goto 40;

(29) 26:

(30) 27: procedure RECEIVING OPERATIONS

(31) 28: if status message received & receiver node is an RMS then

(32) 29: if the RMS is in a previous path & the original source distance is 1-hop then

(33) 30: send link layer nack, goto 38;

(34) 31: else

(35) 32: send link layer ack, delete status message, send back routing ack, goto 11;

(36) 33: else if status message received & receiver is not an RMS then

(37) 34: if the node is in a previous path Or it does not have any neighbour available then

(38) 35: send link layer nack, goto 38;

(39) 36: else

(40) 37: send link layer ack, TTL--, goto 14;

(41) 38: if link layer nack received then

(42) 39: add neighbour in PermExcluded Or TempExcluded, goto 14;

(43) 40: if routing nack received then

(44) 41: add neighbour in TempExcluded, TTL++, goto 14;

(45) The steps for the algorithm are divided into three sections: the first contains the unique operations performed by the source node which is trying to create a path; the second identifies the sending operations performed by a node which currently owns the path creation data packet; and the third section which summarises receiving operations performed by an involved node. The involved node is any node which is a next-hop candidate during path creation.

(46) At line 7, the TTL value is increased by one whenever the source node does not have any one-hop neighbours which satisfy the main condition of hopDistance<TTL with the current TTL value. By increasing the TTL value, the nodes in the TempExcluded lists may become a potential next-hop node to be selected. In contrast, the nodes in the PermExcluded lists still may never be selected as next-hop nodes once they are stored on the list, at least until the list is updated and they are subsequently removed.

(47) The selection of the next-hop node performed between lines 15 and 19 chooses the one-hop neighbour that has the minimum hop distance which is also lower than the current TTL value and whose unique node ID is not on either of the PermExcluded or TempExcluded lists. If there is more than one node that satisfies these constraints, the next-hop node is prioritised based on whether it is in the same subnetwork as the current node and on its RSSI value. If there are no nodes in the same subnetwork, then the choice falls on a node in another subnetwork with the best RSSI. These constraints regarding the selection of the node may only apply in cases where one than one node satisfies the conditions for selection of the best next-hop node and the constraints may change based on the policy of the system and network. They may also include parameters such as: node energy remaining (i.e. battery life), workload, and traffic congestion. Other parameters characteristic of the node may also serve as basis for selection prioritisation.

(48) When a sink node, which may be the head node, receives the path creation data packet on line 29, the sink node accepts the packet by sending a link layer ack reply if the sink node is not in a previous path or if the sink node is In a previous path but the distance between the current sink node and the source node is not one hop. In other cases, the sink node is configured to send a link layer nack. The second of the two conditions for sending a link layer ack is included because, if true, it means that the sink node already has a direct on-hop path with the source node built in a previous route. This direct path would be chosen over a path being currently built as it predates the path being built and it is unlikely that the source node cannot communicate with this sink node directly while a longer path is available.

(49) When the receiver is not a sink node, as shown on line 33, the receiving node will accept the path creation data packet by replying with a link layer ack or a link layer nack. The greedy algorithm shown is configured to create disjoint paths only. Therefore, the receiving node will reply with a link layer ack if the receiving node is in a previously created path and the receiving node has at least one neighbour to send the data packet on to. If this condition is not met, then the receiving node sends a link layer nack. The nack contains a flag in order to inform the sending node of the reason for refusing the path creation data packet, and the sending node may add the unique ID of the receiving node to one of the PermExcluded or TempExcluded lists, shown at line 39. The unique ID of a receiving node may be added to the PermExcluded list by the sending node if the receiving node is already in a previously created path or if the receiving node's one or more neighbours are all on the PermExcluded list. The sending node may add the unique node ID of the receiving node to the TempExcluded list if the receiving node does not have a neighbour available due to the TTL value of the path creation data packet being too low, in which case the TTL value of the data packet will also be recorded on the list as the receiving node may accept a path creation data packet with a higher TTL value. When a sink node sends a nack, the sink node unique ID is always inerted onto the PermExcluded list as it means that the sink node is already in a previous path with the source node being at a hop distance of one away from the sink node.

(50) In the example network 100, a message data packet has been sent from the source node 106 towards the head node 102 following an original path 110. When attempting to be transmitted from an intermediary node 112, the intermediary node 112 discovers that the next node on the original path 110 is a failed node 108. The intermediary node may now be termed a “discovery node” 112.

(51) The discovery node 112 is then configured to initiate an adaptive failure recovery method. This method involves calculating which of two available failure recovery methods has the smallest latency. The two methods are a hop-distance recovery method and a multipath recovery method. The adaptive failure recovery method is initiated in the event of a source node 106 sending a message data packet upstream and a discovery node 112 encountering a failed node 108.

(52) The adaptive recovery failure method includes collecting, at the discovery node 112, relevant data. The relevant data comprises: a hop-distance between the failed node and the source node; a count of estimated extra hops required to deliver the data packet using a hop-distance recovery method; a count of estimated extra hops required to deliver the data packet using a multipath recovery method; and a latency time for the hop-distance recovery method. Latencies for each of the hop-distance recovery method and the multipath recovery method are calculated at the discovery node 112 from the relevant data and, depending on the comparison, one of the hop-distance recovery method or the multipath recovery method is selected to circumvent the failed node 108.