FIELD OF THE INVENTION

The present invention relates to a method for transmitting a message to a destination network node in a fault tolerant communication system, said destination network node being reachable over a number of communication paths comprising a number of network nodes, between which the message is forwarded until it has reached said destination network node. The present invention further relates to a network node to be used in a fault tolerant communication system when transmitting a message to a destination network node, said destination network node being reachable over a number of communication paths comprising a number of said network nodes, between which the message is forwarded until it has reached said destination network node.

BACKGROUND

Communication network in its nature, either wireless or wired, is subject to frequent packet or connection losses due to interference, broken wire lines, traffic congestion and other impairments. Nevertheless, such networks are to be used in medical, automotive and other safety critical applications for reasons like convenience, ruggedness (wireless networks do not need cumbersome connectors), mobility and others, and thus require fault- tolerance and guaranteed message delivery.

In WO 03/005629 a system and a method are disclosed for reducing data loss in wireless networks resulting from corruption of one or more wireless links or resulting from failure of an intermediate connection node. The wireless network, which includes at least one intermediate node having an internal buffer for continually buffering data passing from source node to destination node, establishes an alternating path bypassing the failed node. Lost data packets are locally retransmitted in response to receipt of an error message indicating node failure, or in response to a retransmit request resulting from data corruption over a wireless link. The drawback here is that the time delay, from when the failure occurred until a new path has been established and the message is sent over the new path, can be too long. Especially in situations where the message is an alert signal, e.g. from a device attached to a patient, such a time delay can have unforeseen consequences.

OBJECT AND SUMMARY OF THE INVENTION

It is the object of the present invention to prevent the before mentioned drawback by reducing said time delay. According to a first aspect, the present invention relates to a method for transmitting a message to a destination network node in a fault tolerant communication system, said destination network node being reachable over a number of communication paths comprising a number of network nodes, between which the message is forwarded until it has reached said destination network node, said method comprising: - selecting a primary communication path from said number of communication paths, transmitting said message to another network node in said primary communication path, storing said message, where said method further comprises selecting a secondary communication path from said number of communication paths, if said message does not reach the destination network node over said primary communication path and transmitting said message to another network node in said secondary communication path.

Thereby, it is ensured that said message does not get lost in case the first transmission over said primary communication path fails, and that said stored messages are used for further transmission until the message reaches its destination network node. Furthermore, since the copies of said messages are stored along a communication path, the latency for retransmission after loss of a message is reduced significantly. Also, in cases where interference occurs geographically (i.e. a certain network node in the network is affected) by transmitting copies of the message over different communication paths using geographically different paths, the chances of message loss are significantly reduced. In an embodiment said network nodes are adapted to receive a positive acknowledgement message issued by said destination network node by receipt of said message. In this way the network nodes having stored said message are notified whether or not the transmission of said message was successful.

In an embodiment said network node is provided with a timer with pre-defined time out value for determining the latest allowed arrival time of said positive acknowledgement message. Thereby, the time out value can be used as an indicator of when to retransmit said message over said secondary communication path, e.g. at the expiration of

said timer (i.e. when the time out value has been reached) the stored message is transmitted over said secondary communication path towards said destination network node.

In an embodiment, said pre-defined time out value is defined based on the relative position between said network node and said destination network node. It is thereby ensured that the network node closest to the destination has the shortest time out value and will be the first one to re-transmit the message towards the destination network node. In this way, the latency for retransmission after loss of a message is minimized. The pre-defined time out value can be based on other parameters, such as measured in geographical distance, number of hops or another suitable parameter. In an embodiment, selection of said primary communication path is based on criteria from the group consisting of at least: end-to-end bandwidth of said network nodes and the links in between the nodes, the hop count between the network nodes, the measured end-to-end delay during last path assessment, traffic load of forwarding terminals involved, buffer occupancy of forwarding terminals involved and available system power of forwarding nodes involved. Therefore, as soon as one or more of these parameters change, the presumption for the evaluation of which communication path to be used as a primary communication path and which one to be used as a secondary communication path can be changed, and thereby the primary communication path can be updated. In an embodiment, said primary communication path is frequently revalued.

This is important in the case that the network system is a "dynamical network" where some parameters as e.g. the position of the network nodes are changing, e.g. the network node can be carried by a patient taking a walk. Such a frequent evaluation can result in that the initial primary communication path is no longer the most favorable communication path and is as a result updated, although the message has e.g. not reached the destination network node. A network node on the primary communication path might therefore select a new primary communication path over the initial primary communication path and transmit the message to a new primary network node.

The invention further relates to a computer-readable medium having stored therein instructions for causing a processing unit to execute said method.

According to another aspect, the present invention relates to a network node to be used in a fault tolerant communication system when transmitting a message to a destination network node, said destination network node being reachable over a number of communication paths comprising a number of said network nodes, between which the

message is forwarded until it has reached said destination network node, said network node comprising: a processor for selecting a primary communication path from said number of communication paths, - a transmitter for transmitting said message to a another network node in said primary communication path, storage means for storing said message, where said processor is further adapted to select a secondary communication path from said number of communication paths, if said message does not reach the destination network node over said primary communication path and said transmitter is further adapted for transmitting said message to a another network node in said secondary communication path.

This network node preferably comprises a message generator for issuing said message and/or for issuing a tag indicating which one of the neighboring network nodes is a primary network node, a receiver for receiving a positive acknowledgement message from said destination network node indicating the receipt of said message and/or for receiving said message from a previous neighboring network node and a time-out mechanism for determining a pre-defined time out value for determining the latest allowed arrival time of the acknowledgement message. According to a further aspect, the present invention relates to a method of performing a fault tolerant communication of a message to a destination network node, wherein said destination network node can be reached over a number of communication paths, wherein a communication path comprises a number of network nodes including said destination network node, said method comprising the steps of: - selecting a primary communication path from said number of communication paths, transmitting said message to said destination network node by forwarding said message between the network nodes in said primary communication path, selecting a secondary communication path from said number of communication paths during said transmitting storing said message in at least one network node in either said primary communication path or said secondary communication path, wherein the secondary communication path is selected in which a network node storing said message is a first network node to reach said destination network node, and

this secondary communication path is used to transmit said message, if said message does not reach the destination over said primary communication path.

In an embodiment, the selection of said primary communication path and said at least one secondary communication path is initially determined by a message-originating network node. Typically, this network node is the one which issued said message. This network node can therefore select, at that instant of time where the issued message is to be transmitted, which communication path is the most favorable communication path.

BRIEF DESCRIPTION OF THE DRAWINGS In the following, the present invention, and in particular preferred embodiments thereof, will be described in more detail in connection with accompanying drawings in which

Fig. 1 illustrates an embodiment of the present invention showing a network comprising network nodes, Figs. 2-5 illustrate the steps of transmitting a message from a message- originating network node to a destination network node,

Fig. 6 depicts the situation where the message has reached the destination node Nl 6 105, which after receipt issues a positive acknowledgement message and sends it over the same primary communication path in the opposite order, Fig. 7 shows an example of where the transmission of the message has failed,

Fig. 8 shows another embodiment where the network nodes on the primary communication path further store the message and

Fig. 9 shows an example of basic technical features in a network node.

DESCRIPTION OF PREFERRED EMBODIMENTS

Fig 1 illustrates an embodiment of the present invention showing a network 100 comprising network nodes, 101-118, wherein the network 100 can be completely wireless, partly wireless and partly wired, or only wired. In the present invention the term network node can at least comprise an access point, a terminal, router, etc. The main object of the present invention is to provide a reliable transmission of a message 119 (see Fig. 2) from an originating network node, Nl 101 (see Fig. 2), where said message is issued towards a destination network node, Nl 6 105 (see Fig. 2), where the message is to be received. The main object of the present invention is to transmit the message, not only via a single

communication path towards the destination network node, but by using multiple "store-and- forward" steps until a first copy of the message has reached the destination network node. In this embodiment, only the network nodes marked as circles (N1-N4, N6- N8, N13-N16, N18-N19), 101-113, are used in the steps of transmitting/forwarding and/or storing the message 119 due to e.g. their position, whereas the network nodes marked as squares, (N5, NlO-11, N17, N20), 114-118, do not participate in this process at all. It is assumed here that each of the network nodes has stored data comprising a local communication path table, which in itself comprises information about to which network nodes in the network 100 a received message is to be sent in order to reach its destination. This will be discussed in more details later. The data comprised in this local communication path table are determined e.g. using state-of-the-art (ad-hoc) routing protocols, such as the AODV ("Ad hoc On-Demand Distance Vector", documented as IETF draft "draft-ietf-manet- aodv-13.txt"dated 17 February 2003). For the purpose of this invention, we assume the distributed routing algorithm is to be executed independently of the claimed reliable transmission. The reliable transmission only makes use of the latest routing information, whenever this is needed.

As shown in Fig. 2, the originating network node, where the message is issued, is Nl 101 (first network node on the primary communication path). This network node evaluates, according to the routing information available to it, which of the surrounding nodes is to be used as the next hop in the primary communication path, and which ones are to be used as starting points of secondary (fallback) communication paths. This evaluation can be based on several parameters. Examples of parameters, which can influence this evaluation, are: the end-to-end bandwidth, the hop count between the network nodes, the measured delay during last communication path assessment, traffic load of forwarding terminals involved, buffer occupancy of forwarding terminals involved and available system power of forwarding involved. All this information can be retrieved from the distributed routing algorithm. At any given time, the distributed routing algorithm provides the node with its best guess of the optimum path towards the message's destination node; this path can be considered as this node's best guess of a (partial) preliminary primary path. This information may be updated by the distributed routing algorithm periodically or on demand, when the network reaches the node and needs to be transmitted to the next node. As illustrated here, the evaluation of the aforementioned information has resulted in that the second network node on the primary communication path is N3 102, and that the starting points on the

secondary communication paths are the network nodes N2 106 and N4 107. These two secondary network nodes store the issued message (119a, 119b).

The message 119 is further accompanied by a tag issued by Nl 101 indicating which network node is the primary network node, and which are the secondary network nodes. This assignment is also stored in the second network node of the primary communication path, i.e. N3 102.

The process of selecting the most appropriate next hop in the primary path and the suitable network nodes as starting points for new secondary communication paths (according to the aforementioned routing information available to it) is now repeated, this time by N3 102. As illustrated in Fig. 3, this evaluation has resulted in that the third network node on the primary communication path is N8 103 and the two secondary network nodes, which store the message (119c and 119d), are N6 108 and N7 109. The transmitted message 119 is, as mentioned previously, accompanied by a tag. This time the tag is issued by N3 102 indicating which next network node is the third primary network node, i.e. N8 103, and which are the secondary network nodes, i.e. N6 108 and N7 109, and is stored by the network nodes N6-N8.

Figs. 4-5 illustrate the same steps as discussed under Figs. 2-3. In Fig. 4 the third network node, N8 103, on the primary communication path has selected the network node Nl 3 104 to be the fourth network node on the primary communication path and the network nodes, N14 110 and Nl 5 119 (according to the routing information available to N8 103), as secondary network nodes, which further store the received message (119e and 119f) from N8 103 along with the associated tag issued by N8 103.

In Fig. 5 the fourth network node Nl 3 104 on the primary communication path has received the forwarded message from N8 103 along with the associated tag issued by N8 (stating which network node is to be used as a primary network node, and which ones are to be used as secondary nodes) and forwards the message 119 to the destination network node N16 105 and to the selected secondary network nodes Nl 8 112 and N19 113, where the message is stored (119g, 119h), along with the tag issued by N13.

In this way the process of selecting the most appropriate next hop in the primary communication path and the suitable nodes as starting points for new secondary communication paths (according to the routing information available to it) is repeated with every new node on the primary communication path.

In the embodiment shown here, the iterative path evaluation (see the dotted curves) has resulted in that the most favorable primary communication path was N1-N3-N8-

N13-N16. In this embodiment, none of the network nodes on this primary communication path stored the message but only the tag issued by the previous network node.

Each of the secondary network nodes determines, based on its locally available routing information, to which network nodes in network 100 a received message is to be sent in case the transmission of the message on the primary communication path foiled, thereby pursuing a secondary path starting point. This may happen directly after reception and storage of the message, or immediately before the message is to be transmitted, since the most current routing information can then be used. This would especially be preferred in dynamical networks, where the network nodes can be moving and thereby changing their positions. The transmission of the stored message from these secondary network nodes is, however, suspended until said time out value defined for each of the network nodes, which will be discussed in more details later, has expired.

Depending on the actual network topology, it may happen that no 'n' secondary nodes can be identified; in the extreme case, only a single node is able to do the requested forwarding of the message. In this case, no starting nodes for secondary paths can be selected; this fact is then also reflected in the tag associated with the message when forwarded to this specific next node in the primary path.

Fig. 6 depicts the situation where the message 119 has reached the destination node Nl 6 105, which after receipt issues a positive acknowledgement message 120 and transmits it over the same primary communication path in the opposite order. Each network node on the primary communication path then transmits the positive acknowledgement message to the secondary network nodes (according to the information from the tag attached to the received message available to the network nodes on the primary communication path) and to the previous (next) network nodes on the primary communication path. As shown here, the destination network node 16 105 transmits the positive acknowledgement message back to the previous network node Nl 3 104 on the primary communication path, which then forwards the positive acknowledgement message 120a and 120b to Nl 9 and Nl 8, respectively, in order to trigger deletion of the original message 119g, 119h in these nodes. This is then repeated until the acknowledgement message has reached Nl 101 and has also been forwarded to all the secondary network nodes having stored said message 119.

For each of the network nodes having stored the message, a time out value is defined in order to determine the latest allowed arrival time of the acknowledgement message. The definition of the time out value can be based on the position of the network node in relation to the destination network node Nl 6 105. The information of a node's

position in the network can be derived by an analysis of information available from the distributed routing algorithm. Since every node stores its own best guess of the primary communication path, it can also determine its own location within this path, and set the time out value accordingly. As an example, if the destination node is part of a wired network, consequently the network nodes closest to the wired network should have the shortest time out values, whereas network nodes closest to the first network node on the primary communication path, Nl 101, should have the largest time out value. If this time period expires, the network nodes having stored the message 119 start sending the stored message based on their local routing information as described previously, using the same mechanisms as described in the explanation of figures 2 to 5, i.e. that each starting point of a secondary path then starts to establish a new primary communication path. This new primary communication path consists of that section of the original primary communication path that guided the message to the current node and of the new path taken by the message according to the mechanisms of this invention. It may happen that some acknowledgement messages get lost in the network, whereas the original message 119 has already reached its destination, and the message originator has also already received a proper acknowledgement message. This is a quite undesirable situation, since it may lead to flooding the network with copies of the original message 119. This, however, can be avoided if every message is tagged with an identification number, which is then in some form referenced in subsequent messages 119. These references may be either direct, i.e. a subsequent messages bears the ID number of a previous message, thereby indicating that this message has been successfully acknowledged, or it may be indirect, e.g. by bearing an ID number such that all messages with an ID number smaller than the current one are indicated to be properly transmitted and acknowledged. This finally leads to the removal of all stored copies of a successfully transmitted message, performing a kind of "garbage collection".

In another case, it may also happen that (due to changed network topology and according routing information) a node receives another copy of a message, which it has already stored. In this case, it considers itself as being part of the primary part, deletes the stored copy of the message and forwards the message to the node, thereby becoming the next hop in the primary communication path, and to the nodes to be used as starting points of potential secondary communication paths (the same procedure as described before).

Fig. 7 shows an example of where the transmission of the message 119 has failed, since the network node Nl 3 104 was not reachable. In this case, no local

acknowledgement from Nl 3 104 has been sent to N8 103. Assuming that the network node N14 110 has the shortest time out value (e.g. closest to the destination node Nl 6) this node is the first node in the network 100 to respond to this message failure. As the time out value has elapsed, Nl 4 105 becomes a network node in the new primary communication path, N1-N3- N8-N14-N16, as shown. In order to inform all other network nodes on the primary and secondary communication paths of this node's intention to transmit the message it sends a control message indicating that it will start to transmit message 119 to the previous hop in the primary communication path (i.e. the node from which it received the message). This network node then forwards this control message forwards and backwards on the primary communication path, and each node on the primary communication path forwards this information to the secondary nodes based on the local routing table and the tag attached to the received message. Upon receiving this information, all nodes restart their timers. Then, based on current local routing information, the message is forwarded to the destination network node Nl 6 105, and is simultaneously sent to the secondary network node Nl 7 118, where the message is stored 119. If the message now reaches Nl 6 105, a positive acknowledgement will be sent, thereby deleting all the stored messages. However, if again the transmission of the message 119 would fail (not shown here) the same procedure is continued, the network node having the shortest time out value initiates the transmission of the stored message based on the data stored in said path table. Fig. 8 shows another embodiment, where the network nodes on the primary communication path, 101-105, further store the message instead of forwarding it to the next secondary network nodes as illustrated in Figs. 2-6. Note that all the transmission steps as set forth in Figs. 2-6 are here shown simultaneously. Of course, the processing steps occur as depicted in Figs. 2-6, i.e. first transmission from N 1 101 to N3 102, from N3 to N8 103 etc. In this embodiment the forwarding procedure to the next network nodes on the secondary communication paths (e.g. N2 106 and N4 107 from the primary node N3 102) will not take effect until after said time out value has lapsed.

In yet another embodiment, the message originator (Nl 101) re-transmits the message using another alternative communication path, or the same. However, in case the message carries an identifier, which shows its relation to the previous, unsuccessful transmission attempt, if a node that earlier stored a copy of the first message receives this second message, it deletes the first message from its memory.

In an embodiment, all the network nodes are supported with a "master timeout", which allows them to delete messages from their memory, once this period has elapsed.

Of course, this time out value has to be chosen larger than all the other time out values described so far. Once this happens, at the moment of deletion the node also issues a negative acknowledgement message back to the message originator, indicating that it will no longer attempt to transmit the message. Fig. 9 shows an example of basic technical features in a network node, e.g.

101, 105, 109 from Figs. 1-7. Assuming that this node is the first network node in the primary communication path, Nl 101, it comprises in a preferred embodiment a processor 303, a storage means 301, a receiver 304, a transmitter 302 and a message generator 305. The message generator can e.g. comprise a sensor for providing output data, wherein, if the data exceed a pre-defined upper/lower limit, the message generator generates an alert signal. The sensor can e.g. be comprised in a device attached to a patient subject to monitoring of medical parameters, or e.g. comprise a sensor in a car indicating slippery road conditions, or e.g. a radio activity sensor comprised in a nuclear reactor. The processor is adapted to determine, which communication path to be a primary communication path and to select the n secondary nodes based on local routing information, which is the outcome of a routing protocol executed by the processor as well. The transmitter 302 is adapted to transmit the message 119 to the neighboring network nodes, based on the local routing plan, which is stored in the storage means 301. The storage means can be a random access memory (ram), read-only memory (rom) or equivalent memories designed to store information. The receiver is adapted to e.g. receive message 119 and receive said acknowledgement message from the final destination node Nl 6 105.

As previously mentioned, the network node shown here might just as well be a secondary node, e.g. N7 109, which has a receiver for receiving said message and storing it in the storage means 301, a processor for e.g. initiating a transmission of the stored message when said time out limit has elapsed, a time-out mechanism for keeping track on the timer value (not shown) and a transmitter for transmitting the stored message to the neighboring network nodes (according to the path table) when the time-out value has been reached. N7 109 also has the capability to generate the control message, indicating that it starts to transmit the message 119 into a new primary communication path, and to interpret such message, and consequently re-start its timer.

The network 100 can both comprise stationary network, a dynamic network and a combination thereof.

An example of implementation of the present invention is where a patient has some sensor equipment attached to the body. In regular time intervals, sensor data need to be

checked in a monitoring computer of the hospital. Now, the patient is e.g. allowed to walk around in the hospital park, but still regularly the sensor data needs to reach the fixed network. This can be achieved e.g. by the "monitoring terminal" of another patient, who is closer to an access point, in that this terminal forwards the messages from the first patient's monitoring terminal. The same could happen if a patient's monitoring terminal connects to so-called bed-side monitors located in rooms close by. In this case, the patient's monitoring terminal sends messages to several bed-side monitors (also terminals) inside these rooms, which then forward this further into the hospital infrastructure.

It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word 'comprising' does not exclude the presence of other elements or steps than those listed in a claim. The invention can be implemented by means of hardware comprising several distinct elements and by means of a suitably programmed computer. In a device claim enumerating several means, several of these means can be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different, dependent claims does not indicate that a combination of these measures cannot be used to advantage.