Distributed traffic control in flooding mesh networks

Abstract

A method and apparatus for relaying messages in a mesh network.

Claims

1. A method, being performed by a relaying device (RD), for relaying user data messages originated in a source device (SD) intended for a destination device (DD), where the source device (SD), the relaying device (RD) and the destination device (DD) participates in a mesh network, the method comprising: receiving a first ping message, originating in the source device (SD) intended for the destination device (DD), where the first ping message comprises a first hop counter; relaying the first ping message by stepping the first hop counter and transmitting the first ping message; receiving a user data message originating in the source device (SD) intended for the destination device (DD); determining whether the relaying device (RD) is on a possible path, indicating that the relaying device (RD) is on a path from the source device (SD) to the destination device (DD); determining whether the relaying device (RD) is on a short enough path, indicating that the relaying device (RD) is on a path from the source device (SD) to the destination device (DD) that is deemed short enough to justify relaying; and relaying the user data message only if the relaying device (RD) is on the possible path and on the short enough path, wherein the determining whether the relaying device (RD) is on the short enough path comprises: acquiring a shortest distance via the relaying device, indicating the number of hops on a shortest path from the source device (SD) via the relaying device (RD) to the destination device (DD); and determining that the relaying device (RD) is on the short enough path based on at least the shortest distance via the relaying device and the path length of shortest possible path.

2. The method according to claim 1, wherein the determining whether the relaying device (RD) is on the possible path, comprises: determining that the relaying device (RD) is on the possible path only if the relaying device (RD) has received a first ping response message, originating in the destination device (DD), intended for the source device (SD), where the first ping response message is related to the first ping message and comprises a first path length of shortest possible path.

3. The method according to claim 1, wherein the determining whether the relaying device (RD) is on the short enough path, further comprises: basing the determination on an allowed additional hops value.

4. The method according to claim 1, wherein the acquiring the shortest distance via the relaying device comprises: obtaining the shortest distance via the relaying device from a database in the relaying device.

5. The method according to claim 1, wherein the acquiring the shortest distance via the relaying device comprises: obtaining the shortest distance via the relaying device from another device.

6. The method according to claim 1, wherein the acquiring the shortest distance via the relaying device comprises: transmitting a second ping message intended for the source device (SD); receiving a second ping response message originating in the source device (SD), intended for the relaying device (RD), where the second ping response message is related to the second ping message and comprises a second path length of shortest possible path; transmitting a third ping message intended for the destination device (DD); receiving a third ping response message originating in the destination device (DD), intended for the relaying device (RD), where the third ping response message is related to the third ping message and comprises a third path length of shortest possible path; and determining the shortest distance via the relaying device based on the second and third path length of shortest possible path.

7. The method according to claim 1, wherein the first ping response message further comprises a remaining distance to source indicating the remaining number of hops from the relaying device (RD) to the source device (SD), and wherein the determining whether the relaying device (RD) is on the short enough path comprises: determining that the relaying device (RD) is on the short enough path based on at least the first hop counter and the remaining distance to source.

8. The method according to claim 7, wherein the determining whether the relaying device (RD) is on the short enough path, further comprises: basing the determination on an allowed additional hops value.

9. The method according to claim 7, further comprising: relaying the first ping response message, by stepping the remaining distance to source and transmitting the first ping response message.

10. The method according to claim 7, further comprising: relaying the first ping response message, by stepping the remaining distance to source and transmitting the first ping response message, only if the relaying device (RD) is on the short enough path.

11. A method, being performed by a relaying device (RD), for omitting relaying user data messages originated in a source device (SD) intended for a destination device (DD), where the source device (SD), the relaying device (RD) and the destination device (DD) participates in a mesh network, the method comprising: receiving a first ping message, originating in the source device (SD) intended for the destination device (DD), where the first ping message comprises a first hop counter; relaying the first ping message by stepping the first hop counter and transmitting the first ping message; receiving a user data message originating in the source device (SD) intended for the destination device (DD); determining whether the relaying device (RD) is not on a short enough path, indicating that the relaying device (RD) is not on a path from the source device (SD) to the destination device (DD) that is deemed short enough to justify relaying; and determining whether the relaying device (RD) is not on a possible path, indicating that the relaying device (RD) is not on a path from the source device (SD) to the destination device (DD); and not relaying the user data message if the relaying device (RD) is not on the short enough path or is not on the possible path, wherein the determining whether the relaying device (RD) is not on the short enough path comprises: acquiring a shortest distance via the relaying device, indicating the number of hops on a shortest path from the source device (SD) via the relaying device (RD) to the destination device (DD); and determining that the relaying device (RD) is not on the short enough path based on at least the shortest distance via the relaying device and the path length of shortest possible path.

12. The method according to claim 11, wherein the determining whether the relaying device (RD) is not on the possible path, comprises: determining that the relaying device (RD) is not on the possible path only if the relaying device (RD) has not received a first ping response message, originating in the destination device (DD), intended for the source device (SD), where the first ping response message is related to the first ping message.

13. A relaying device (RD), for relaying user data messages originated in a source device (SD) intended for a destination device (DD), where the source device (SD), the relaying device (RD) and the destination device (DD) participates in a mesh network, comprising: a transceiver unit being configured to receive a first ping message, originating in the source device (SD) intended for the destination device (DD), where the first ping message comprises a first hop counter; a controller unit being configured to relay the first ping message by stepping the first hop counter and transmitting the first ping message via the transceiver unit which has been configured to transmit the first ping message; the transceiver unit being further configured to receive a user data message originating in the source device (SD) intended for the destination device (DD); the controller unit being further configured to determine whether the relaying device (RD) is on a possible path, indicating that the relaying device (RD) is on a path from the source device (SD) to the destination device (DD); the controller unit being further configured to determine whether the relaying device (RD) is on a short enough path, indicating that the relaying device (RD) is on a path from the source device (SD) to the destination device (DD) that is deemed short enough to justify relaying; and the controller unit being further configured to relay the user data message only if the relaying device (RD) is on the possible path and on the short enough path, wherein the determining whether the relaying device (RD) is on the short enough path comprises: acquiring a shortest distance via the relaying device, indicating the number of hops on a shortest path from the source device (SD) via the relaying device (RD) to the destination device (DD); and determining that the relaying device (RD) is on the short enough path based on at least the shortest distance via the relaying device and the path length of shortest possible path.

14. The relaying device (RD) according to claim 13, wherein the controller unit being configured to determine whether the relaying device (RD) is on the possible path, is further configured to: determine that the relaying device (RD) is on the possible path only if the relaying device (RD) has received a first ping response message, originating in the destination device (DD), intended for the source device (SD), where the first ping response message is related to the first ping message and comprises a first path length of shortest possible path.

15. The relaying device (RD) according to claim 13, wherein the controller unit being configured to determine whether the relaying device (RD) is on the short enough path, is further configured to: base the determination on an allowed additional hops value.

16. The relaying device (RD) according to claim 13, wherein the controlling unit being configured to acquire the shortest distance via the relaying device is further configured to: obtain the shortest distance via the relaying device from a database in the relaying device.

17. The relaying device (RD) according to claim 13, wherein the controller unit being configured to acquire the shortest distance via the relaying device is further configured to: obtain the shortest distance via the relaying device from another device via the transceiver unit which has been configured to send and receive the messages to the other device.

18. The relaying device (RD) according to claim 13, wherein the controller unit being configured to acquire the shortest distance via the relaying device is further configured to: via the transceiver unit transmit a second ping message intended for the source device (SD); via the transceiver unit receive a second ping response message originating in the source device (SD), intended for the relaying device (RD), where the second ping response message is related to the second ping message and comprises a second path length of shortest possible path; via the transceiver unit transmit a third ping message intended for the destination device (DD); via the transceiver unit receive a third ping response message originating in the destination device (DD), intended for the relaying device (RD), where the third ping response message is related to the third ping message and comprises a third path length of shortest possible path; and determine the shortest distance via the relaying device based on the second and third path length of shortest possible path.

19. The relaying device according to claim 13, wherein the first ping response message further comprises a remaining distance to source indicating the remaining number of hops from the relaying device (RD) to the source device (SD); and wherein the controller unit being configured to determine whether the relaying device (RD) is on the short enough path is further configured to determine that the relaying device (RD) is on the short enough path based on at least the first hop counter and the remaining distance to source.

20. The relaying device (RD) according to claim 19, wherein the controller unit being configured to determine whether the relaying device (RD) is on the short enough path, further being configured to: base the determination on an allowed additional hops value.

21. The relaying device (RD) according to claim 19 wherein the controller unit being further configured to: relay the first ping response message, by stepping the remaining distance to source and transmitting the first ping response message via the transceiver unit, the transceiver unit being further configured to transmit the first ping response message.

22. The relaying device (RD) according to claim 19, wherein the controller unit being configured to relay the first ping response message, by stepping the remaining distance to source and transmitting the first ping response message via the transceiver unit, the transceiver unit being further configured to transmit the first ping response message, only if the relaying device (RD) is on the short enough path.

23. A relaying device (RD), for omitting relaying user data messages originated in a source device (SD) intended for a destination device (DD), where the source device (SD), the relaying device (RD) and the destination device (DD) participates in a mesh network, comprising: a transceiver unit being configured to receive a first ping message, originating in the source device (SD) intended for the destination device (DD), where the first ping message comprises a first hop counter; a controller unit being configured to relay the first ping message by stepping the first hop counter and transmitting the first ping message via the transceiver unit which is being configured to transmit the first ping message; the transceiver unit being further configured to receive a user data message originating in the source device (SD) intended for the destination device (DD); the controller unit being further configured to determine whether the relaying device (RD) is not on a short enough path, indicating that the relaying device (RD) is not on a path from the source device (SD) to the destination device (DD) that is deemed short enough to justify relaying; the controller unit being further configured to determine whether the relaying device (RD) is not on a possible path, indicating that the relaying device (RD) is not on a path from the source device (SD) to the destination device (DD); and the controller unit being configured to not relay the user data message if the relaying device (RD) is not on the short enough path or is not on the possible path, wherein the determining whether the relaying device (RD) is not on the short enough path comprises: acquiring a shortest distance via the relaying device, indicating the number of hops on a shortest path from the source device (SD) via the relaying device (RD) to the destination device (DD); and determining that the relaying device (RD) is not on the short enough path based on at least the shortest distance via the relaying device and the path length of shortest possible path.

24. The relaying device (RD) according to claim 23, wherein the controller unit being configured to determine whether the relaying device (RD) is not on the possible path, is further configured to: determine that the relaying device (RD) is not on the possible path only if the relaying device (RD) has not received a first ping response message, originating in the destination device (DD), intended for the source device (SD), where the first ping response message is related to the first ping message.

25. A computer program product comprising a non-transitory computer readable storage medium storing a computer program comprising instructions which, when executed on a relaying device (RD), cause the relaying device (RD) to carry out the method according to claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The inventive concept will be described, by way of example, with reference to the accompanying drawings, in which:

(2) FIG. 1 shows an example of an overview of a mesh network. FIG. 1 is the basis for FIGS. 2 to 9.

(3) FIG. 2 shows the possible paths from D1 to D5 in the mesh network.

(4) FIG. 3 shows D19 as relaying device (RD) in an impossible path from D1 to D5 in the mesh network.

(5) FIG. 4 shows D2 as relaying device (RD) in a possible path from D1 to D5 in the mesh network.

(6) FIG. 5 shows the distances from devices to the source device in some different possible paths from D1 to D5 in the mesh network.

(7) FIG. 6 shows the path lengths for the possible paths from D1 to D5 in the mesh network.

(8) FIG. 7 shows D6 as relaying device (RD) when relaying based on path length.

(9) FIG. 8 shows the allowed remaining distance to source, ARDTS, for various possible paths from D1 to D5 in the mesh network.

(10) FIG. 9 shows D6 as relaying device (RD) when relaying based on allowed remaining distance to source, ARDTS.

(11) FIG. 10 shows different message formats.

(12) FIG. 11 is a flowchart depicting embodiments of a method in a relaying device. FIG. 11 is the basis for FIGS. 12 to 14.

(13) FIG. 12 is a flow flowchart depicting embodiments of a method in a relaying device when taking decisions on whether to relay or not based on the shortest distance via the relaying device.

(14) FIG. 13 is a flow flowchart depicting embodiments of a method in a relaying device for acquiring the shortest distance via the relaying path using pinging.

(15) FIG. 14 is a flow flowchart depicting embodiments of a method in a relaying device when taking decisions on whether to relay or not based on the allowed remaining distance to source, ARDTS.

(16) FIG. 15 is a schematic block diagram illustrating embodiments of a relaying device.

(17) FIG. 16 shows one example of a computer program product comprising a computer readable storage medium and a computer program according to an embodiment.

DETAILED DESCRIPTION

(18) As part of developing embodiments herein, some problems of the state of the art will first be identified and discussed.

(19) Using a traditional flooding technique in a mesh network causes serious medium contention, especially for higher traffic intensities and large networks. Specifically, a message transmitted from a source device to a destination device may often cause a significant amount of traffic activity in the network, even in parts of the network that are not at all contributing to the delivery of a message to its destination. Such unnecessary activities consume network resources and often degrade performance with respect to, e.g., message delay, network capacity, and power consumption.

(20) Although setting a proper TTL (often referred to as TTL tuning) limits the problem in some situations, such a solution does still not limit the message forwarding to branches that do not contribute to the message delivery, and in branches that do contribute it only limits the traffic in the end of the branches. It should also be acknowledged, that when there is a large number of hops between the source device and the destination device, the effect of TTL tuning is limited.

(21) The inventive concept will now be described more fully hereinafter with reference to the before mentioned figures, in which certain embodiments of the inventive concept are shown. This inventive concept may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided by way of example so that this disclosure will be thorough and complete, and will fully convey the scope of the inventive concept to those skilled in the art.

(22) Like numbers and reference symbols refer to like elements throughout the description. Any step or feature illustrated by dashed lines in the flow diagrams should be regarded as optional.

(23) FIG. 1 provides an example of an overview of a mesh network. The circles symbolise the devices in the network, D1 to D25, where D1 denotes device 1, etc. The dashed lines symbolise possible communication links between the devices. A possible communication link denotes a communication link where a message that is sent by the device in one end of the communication link can be successfully received by the device in the other end of the communication link. It is also assumed that transmission will also be successful in the reverse direction. In the remainder of this document the shorter term link denotes a possible communication link.

(24) The person skilled in the art would realise that much more complex overview mesh networks could occur. Not only including additional devices, but also including additional links. One such simple but illustrating example could be that D1 could also have a link to D3, which in such a scenario would be illustrated with an additional dashed line between D1 and D3. The person skilled in the art would also realise that in a scenario where the devices are mobile and connected wirelessly, the overview picture provided in FIG. 1 could change over time. An example could be that D17 move from its position and after a while is closer to D21, and in the process D17 would lose the link to D16 but it would gain a new link to D21, this example would then be represented by an accordingly updated figure. The person skilled in the art would also realise that these issues don't affect the methods and apparatuses described in the embodiments herein. Thus the overview of the mesh network is kept complex enough to illustrate the problem and the solution in a generic way, but simple enough to facilitate the understanding. Also to facilitate the understanding, FIG. 1 is the basis for FIGS. 2 till 9.

(25) FIG. 2 shows the possible paths from D1 to D5 in the mesh network. The solid lines symbolise links that are on the various possible paths from D1 to D5. The dashed lines symbolise links that are not on any possible path from D1 to D5. Please note that the links drawn with dash lines are still useful for communication between various devices, but it would not be beneficial to use those links for communication between D1 and D5.

(26) Assume that, D1 would like to send a message to D5. In this scenario D1 would be regarded as the source device (SD) and D5 would be regarded as the destination device (DD). One possible way, or path, could be: D1 sends the message intended for D5 D2 will receive it and relay/forward it D3 will receive it and relay/forward it D4 will receive it and relay/forward it D5 will receive it.

(27) Forwarding here means that a device receives a message and realizes that it is not intended for the device itself, thus the device will send the message again with the intention that it will be sent to (or at least towards) the device for which the message is intended. This action is commonly also referred to as relaying. The device could be called either a relaying device or a forwarding device. Throughout this application the term relaying device will be used in a slightly wider sense, also indicating a device that receives a message and realizes that it is not intended for the device itself and then also determines whether it is meaningful, according to one or more criterion, to relay the message, and then relays the message if it is meaningful (and does not relay the message if it is not meaningful). Meaningful would here mean that it would in some way contribute to transmitting the message to or towards the device the message is intended for also taking into account the specific design objectives.

(28) Considering the above, one can identify 4 different possible paths from D1 to D5: P1 (path 1): D1-D2-D3-D4-D5 P2 (path 2): D1-D2-D6-D3-D4-D5 P3 (path 3): D1-D2-D6-D7-D8-D4-D5 P4 (path 4): D1-D10-D11-D12-D13-D14-D5

(29) In the figure one can see that there are 4 links between device D1 and device D5, if going on the shortest path P1 (D1-D2-D3-D4-D5). The message can be said to make 4 hops on the same path. A hop denotes a transmission over a link.

(30) One could also identify the devices, and links between them, that do not contribute when transmitting data from D1 to D5. Let's for the sake of simplicity divide these devices in branches: Branches left of D1: D19-D20-D21 D19-D22-D23 D19-D24-D25 Branches above D1: D15-D16-D17 D15-D16-D18 Branches above D7: D9

(31) The embodiments herein describe a distributed traffic control in a mesh network using a flooding technique. This means that the relaying devices determines whether to relay a message or not. In order for a relaying device to be able to determine whether it should relay a message or not from a source device to a destination device, it has to be able to determine the following things: Whether it is on a possible path (from the source device to the destination device) Whether it is on a short enough path (from the source device to the destination device)

(32) Let's now introduce some different types of messages: Ping Message (510) Ping Response Message (520) User Data Message (530)

(33) The ping message (510) the ping response message (520) and the user data message (530) and their respective contents will be further explained throughout this description.

(34) Other types of messages or mechanisms can of course also be used, e.g. acknowledgments of user data messages, either as separate messages or piggy backed on other user data messages.

(35) The aim of the embodiments herein is to minimise the transmission of user data messages in the mesh network, while still successfully transferring user data messages from source devices to destination devices. The two main ways of minimising the transmission are, to avoid or minimize transmission in branches that do not contribute to the transmission and to avoid or minimise transmission in redundant possible paths that are considered too long. The determination and decisions will be made in the relaying devices.

(36) The relaying devices will analyse the ping messages (from the source device to the destination device) and the ping response messages, or absence thereof (from the destination device to the source device).

(37) A ping message is typically sent from a source device to destination device to find out, primarily, if the destination device is reachable and available. The destination device will answer with a ping response message. Depending on the contents of the ping message and the ping response message, the source device as well as the relaying devices can determine not only if the destination device is reachable and available, but also other things like e.g. the distance in hops between the two devices.

(38) Different approaches on how to use the ping message and the ping response message could be implemented in different types of network layouts, when using different kinds of network technologies and for different degrees of mobility of the devices, for different quality of the links, etc. The chosen approach or combination of approaches could either be fixed or change over time. Non-limiting examples of approaches on how to use the ping message could be: Initial Ping. The source device pings the destination device once. It could either ping the destination device before intending to send a user data message to the destination device, or it could ping the destination device even with no immediate intention to send a user data message it. Ping before each user data message. The source device pings the destination device before intending to send each user data message to the destination device. Periodic Ping. The source device pings the destination device periodically. Ping again at detection of unsuccessful data transfer. The source device pings the destination device upon detection of bad data transfer. This could be detected in various ways, the most obvious would that the source device did not receive an acknowledgement for a user data message that was sent.

(39) With any of the approaches described above, at some point in time, before sending a user data message to a destination device, the source device would send a ping message intended for the destination device and wait for one or more ping response messages from the destination device, before sending the user data message.

(40) Any device that overhears and analyses the ping message and the one, or possibly more, ping response messages can determine that it is on a possible path from the source device to the destination device.

(41) In traditional networking the ping response would typically comprise information on the distance from the source node to the destination node, which would allow the source device to set a suitable time to live value for subsequent user data packages. The use of TTL allows for a very crude and limited control of transmissions in the network as described further above.

(42) In different embodiments described herein the relaying device will use one or more design objective parameters, obtained in different ways and from different devices, to be able to provide a better means for reducing the amount of unnecessary traffic and a better means to control path diversity. How this can be achieved will be further elaborated on below.

(43) FIG. 3 shows D19 being the relaying device (RD), D1, being the source device (SD) and D5 being the destination device (DD).

(44) Let's walk through the case when D1 intends to send a user data message intended for D5, focusing on the behaviour of D19 which is not on a possible path from D1 to D5.

(45) A. D1 sends a ping message intended for D5 (when this is done depends on the selected ping approach, as discussed above)

(46) B. The Ping message is received by the following devices which understand they are not the intended receiver, making them relay the ping message. D2 D10 D15 D19

(47) C. At some point D5 will receive one or more instances of the ping message, being relayed on the possible paths, and will respond with one or more instances of the ping response message

(48) D. The ping response message would be relayed back to D1 on one or more of the possible paths (e.g. including D2, but not including D19)

(49) E. D1 would then send the user data message intended for D5, which would be received by the same devices receiving the ping message.

(50) F. D19 would when receiving the user data message: a. Determine that the user data message is not intended for D19, thus considering relaying the user data message. b. Determine, based on not having received any ping response message associated with the ping message, that it is not on any possible path from D1 to D5

(51) c. Based on the above, not relay the user data message. The user data message would thus never reach D20, D22 or D24.

(52) The person skilled in the art would realise that for example D15 would behave in the same way as D19.

(53) Assuming the situation (not indicated in FIG. 3) where there would be additional links between D2 and D19, meaning that D19 would receive the ping response message relayed by D2. In this case D19 would determine that it was on a possible path from D1 to D5 and relay the user data message. The relaying would however be stopped in D20, D22 and D24. In this situation the embodiments herein would be slightly less efficient, but still provide a good minimising effect on unnecessary or unwanted transmission.

(54) Let's make a short comparison with using TTL (Time to Live). Time to live is typically a field in the user data message that states the number of hops the user data message should be allowed to make. Time to live is typically set to a start value of the maximum number of hops allowed and then decreased in every relaying node. Assume that in the mesh network outlined in FIG. 3 D1 has found out that the shortest distance from D1 to D5 is 4 hops. To make sure the user data message reaches D5, D1 could set TTL to 4. This mechanism would however not prevent the user data message from being relayed by the branches that do not contribute to transmitting the user data message to D5. D19 would for example receive the user data message and check the TTL (which would have the value of four) and since TTL would be larger than 0 it would then decrease the TTL value and relay the user data message. The D20 would then receive it and act in the same way. Then D21 would receive it and even D21 would relay it. The same would apply to other devices that are within the same distance from D1 as D4 (meaning 3 hops). This illustrates that TTL does not prevent relaying in parts of the network that do not contribute to the transmission of the data to D5.

(55) FIG. 4 shows device D2 being the relaying device (RD), device D1, being the source device (SD) and device D5 being the destination device (DD).

(56) Let's walk through the case when D1 intends to send a user data message intended for D5, focusing on the behaviour of D2 which is on a possible path from D1 to D5. (“Identical” below means that the step would be identical to the corresponding step as presented in the discussion of FIG. 3.)

(57) A. Identical

(58) B. Identical

(59) C. Identical

(60) D. Identical

(61) E. Identical

(62) F. D2 would when receiving the user data message: a. Determine that the user data message is not intended for D2, thus considering relaying the user data message. b. Determine, based on having received a ping response message associated with the ping message, that it is on a possible path from D1 to D5 c. Based on the above i. In some embodiments D2 would relay the message when having determined that it is on a possible path, without making further determinations on whether it is on a short enough path from D1 to D5. ii. In other embodiments D2 would also determine whether it is on a short enough path from D1 to D5. If D2 is on a short enough path it will relay the user data message, the user data message would thus reach D3 and D6. If D2 is not on a short enough path, it will not relay the user data message. How to determine whether a relaying device is on a short enough path from the source device to a destination device will be discussed further below in this description.

(63) The person skilled in the art would realise that the other devices (except the destination device) on the possible paths would behave in the same way as D2 in the above situation.

(64) FIG. 5 shows the distances from devices to the source device in different possible paths from D1 to D5 in the mesh network. The distance is counted in number of hops towards the source device.

(65) The figure illustrates some interesting facts: Different devices will be at different distances from the source device. D2 and D10 (both being at the distance of 1 hop) will for example be closer to D1 than the other devices. A device can be on multiple possible paths. D2 and D4 are for example on three possible paths (P1, P2 and P3) A device being on multiple possible paths can have different distances to the source device on each possible path. D2 has the following distances to the source device. 1 on P1, P2 and P3. D4 has the following distances to the source device. 3 on P1, 4 on P2 and 5 on P3. D5 has the following distances to the source device. 4 on P1, 5 on P2, 6 on P3 and 6 on P4).

(66) Please note that to make the table simpler to understand the path P4 has been excluded. The person skilled in the art will be able to draw the corresponding conclusions regarding P4.

(67) FIG. 6 shows the path lengths for various possible paths from D1 to D5 in the mesh network. The path length is the distance in hops from the source device to the destination device (and vice versa).

(68) P1 has the path length of 4

(69) P2 has the path length of 5

(70) P3 has the path length of 6

(71) P4 has the path length of 6

(72) FIG. 7 shows D6 as relaying device (RD) when relaying based on path length. The description below also refers to FIG. 10, outlining the message formats.

(73) Assuming in analogy with the embodiment described when discussing FIG. 4 that D6 has determined that it is on a possible path. In some embodiments, D6 also will determine whether it is on a short enough path before deciding whether to relay a user data message. In this way, it will further participate in and contribute to controlling the amount of transmissions generated for the user data message in the mesh network.

(74) As has been discussed above, there are four possible paths, with 3 different path lengths (4, 5 and 6). The shortest possible path is P1, and the path length of the shortest possible path is 4. As discussed above, there are benefits and drawbacks of relaying user data messages in all possible paths (paths with path lengths of 6 and lower). The reverse benefits and drawbacks apply when relaying user data messages only in the shortest possible path (paths with path lengths of 4). A middle scenario would be achieved if relaying user data messages on paths with path lengths of 5 and lower.

(75) By setting a maximum allowed path length for relaying, the transmission of user data messages through the different possible paths could be controlled and the system could be tuned with respect to desired redundancy. The maximum allowed path length for relaying would have to be set in relation to the shortest possible path. The maximum allowed path length for relaying would be set as the path length of the shortest possible path plus allowed additional hops. Where allowed additional hops would be a value bigger than or equal to zero. By setting allowed additional hops to zero only devices on the shortest possible path would relay user data messages. Increasing the allowed additional hops would cause user data messages to be sent in additional possible paths.

(76) For a relaying device to determine that it is on a short enough path it would need to know two things. The maximum allowed path length, for relaying which is the sum of: the path length of the shortest possible path the allowed additional hops The shortest distance via the relaying device which is the length of the shortest path that the relaying device is part of. D6 is part of two paths: P2 (with a path length of 5) P3 (with a path length of 6)

(77) Here the maximum allowed path length as well as the allowed additional hops (which is part of the maximum allowed path length), are regarded as designed objective parameters.

(78) If the maximum allowed path length for relaying would be equal or greater than the shortest distance via the relaying device, the relaying device would determine it was on a short enough path. If the relaying device is on a short enough path it would relay the user data message, otherwise not.

(79) For a relaying device to find out the maximum allowed path length, for relaying, it would need to obtain either the maximum allowed path length directly, or to obtain the path length of the shortest possible path and the allowed additional hops separately and then add them.

(80) To describe how any device on any possible path could obtain the path length of the shortest possible path, it is appropriate to discuss some details on how to relay the ping message and a few different approaches for the destination device to send ping response messages.

(81) In the scenario described in FIG. 7 the source device D1 will send a ping message intended for the destination device D5. This ping message will be relayed in the different paths. Assuming all transmissions succeed the ping message (or copies or instances thereof) will be received 4 times by the destination device.

(82) To allow for calculation of the path length of the shortest possible path, the source device D1 will set a hop counter, 515, in the ping message, 510, to a start value. The start value could be any value (as long as all devices agree on the start value) but for the sake of simplicity we assume it is set to 0 (zero), indicating that no successful hop been made yet. Each relaying device will then step the hop counter, 515, before relaying the ping message, to indicate that one more successful hop has been made. The stepping could be done either by incrementing or decrementing the hop counter, 515, by any value (as long as all devices agree on the mechanism) but for the sake of simplicity we assume it will be incremented by 1 (one). In this way when the destination device will receive the 4 ping messages, the hop counters in the different ping messages will be 3, 4, and 5 when the destination device receives them.

(83) The hop counter could be implemented by using a dedicated field, 515, in the ping message as described above. The hop counter could in some implementation be calculated from TTL, thus minimising the number of fields in the ping message. In this latter case the involved devices would have to know the start value of TTL. In its simplest form all devices could use the same start value for TTL. TTL will be stepped for each hop made when traversing the network. The relaying units could then calculate the number of hops (corresponding to the hop counter) from the start value of TTL and the value TTL has when arriving at the relaying device.

(84) In one embodiment, the destination device will determine the path length of the shortest possible path by waiting, by for example using one or more timers, to be able to receive all ping messages. The destination node can in this way calculate that the path lengths of the possible paths are 4, 5, and 6. It can then also calculate that path length of the shortest possible path is 4. The path length of the shortest possible path will then be communicated back to all the relaying nodes as well as the source node. This will be done in the path length of the shortest possible path field, 526, in the ping response message, 520.

(85) In another embodiment, the destination device could make the determination based on the assumption that the first ping message to arrive was transmitted via the shortest path thus representing the shortest distance. The path length of the shortest possible path will then be communicated back to all the relaying nodes as well as the source node. This will be done in the path length of the shortest possible path field, 526, in the ping response message, 520. Please note that in some networks and situations, due to the radio conditions, the delay caused internally in devices and other delays this approach might not cause reliable results. Maybe in some situation the ping message arriving on the second shortest possible path, or any other path, could arrive first in time. The person skilled in the art will realise that using, for example, the path length of the second shortest possible path instead of the path length of the shortest possible path would be less ideal. It would however maybe not happen too often. How this would be implemented depends on the desired behaviour of the system.

(86) In yet another embodiment, the destination device could send one ping response message for each received ping message. Here the determination of the shortest possible path would be left to the source device, or possibly all devices on all the possible paths. The path lengths of each of the paths will then be communicated back to all the relaying nodes as well as the source node. This will be done in the path length of the shortest possible path field, 526, in the ping response message, 520.

(87) Based on the above the maximum allowed path length can be determined, and the information can be distributed, in a few different ways.

(88) In some embodiments, the destination device (DD) determines the path length of the shortest possible path based on one or more of the received ping messages, either by waiting for all ping messages or by assuming that the first ping message received represents the shortest path as described above. The destination device (DD) can then communicate any of the following alternatives in the ping response message (520), in the fields as indicated: The path length of the shortest possible path (526) This would lead to that all devices in all possible paths would obtain this information. The maximum allowed path length could then be obtained by the relaying devices in either of the following ways: The source device (SD) transmitting either or both, of the following in a user data message (530): the maximum allowed path length (537) the allowed additional hops (538)  This would lead to that all devices in all the possible paths would be able to calculate the maximum allowed path length. The relaying device could obtain the allowed additional hops in any of the following ways (allowing it to calculate the maximum allowed path length): The allowed additional hops could be preconfigured in the relaying device. The allowed additional hops could have been received already in the in the allowed additional hops (518) field in the original ping message (510). The allowed additional hops could be, or already have been, obtained from another device in another message. The maximum allowed path length (527) This would lead to that all devices in all the possible paths would obtain the necessary information. The path length of the shortest possible path (526) and the allowed additional hops (528) This would lead to that all devices in all the possible paths would be able to calculate the maximum allowed path length.

(89) In some other embodiments, the source device (SD) determines the path length of the shortest possible path based on one or more of the received ping response messages (520), either by waiting for all the ping response messages or by assuming that the ping response message that is received first ping response message represents the shortest possible path. (The skilled person in the art would realise that this will be done in analogy with how the destination device (DD) could determine the path length of the shortest path as described above.) The maximum allowed path length could then be obtained by the relaying devices by either any of the following alternatives: The source device (SD) transmitting any combination of the following in a user data message (530): the maximum allowed path length (537) This would lead to that all devices in all the possible paths would obtain the necessary information. The path length of the shortest possible path (536) Here the relaying device could obtain the allowed additional hops in any of the following ways (allowing it to calculate the maximum allowed path length): The allowed additional hops could be preconfigured in the relaying device. The allowed additional hops could have been received already in the allowed additional hops (518) field in the original ping message (510). The allowed additional hops could be, or already have been, obtained from another device in another message. The path length of the shortest possible path (536) and the allowed additional hops (538) This would lead to that all devices in all the possible paths would be able to calculate the maximum allowed path length.

(90) In yet some other embodiments, the relaying device (RD) determines the path length of the shortest possible path based on one or more of the received ping response messages (520). (The skilled person in the art would realise that this will be done in analogy with how the destination device (DD) could determine the path length of the shortest path as described above.) The maximum allowed path length could then be obtained by the relaying device by any of the following alternatives: The source device (SD) transmitting any combination of the following in a user data message (530): the maximum allowed path length ( ) This would lead to that all devices in all the possible paths would obtain the necessary information. The allowed additional hops (538) This would lead to that all devices in all the possible paths would be able to calculate the maximum allowed path length. The device could obtain the allowed additional hops in any of the following ways (allowing it to calculate the maximum allowed path length): The allowed additional hops could be preconfigured in the relaying device. The allowed additional hops could have been received already in the in the allowed additional hops (518) field in the original ping message (510). The allowed additional hops could be, or already have been, obtained from another device in another message.

(91) The text above describes various ways for a device to find out the maximum allowed path length, the text below describes how a relaying device can find out the shortest distance via the relaying device.

(92) As has been mentioned above, the shortest distance via the relaying device is the path length of the shortest possible path, between the source device and the destination device, that the relaying device is part of.

(93) In this example, as FIG. 7 shows, D6 is part of two possible paths, P2 (with a path length of 5) and P3 (with a path length of 6). Here the shortest distance via the relaying device is 5 (which is the path length of P2).

(94) In different embodiments herein, the relaying device could obtain the shortest distance via the relaying device in different ways. (Here one has to keep in mind that the shortest distance via a relaying device does not necessarily have the same value as the path length of the shortest possible path.)

(95) One way to calculate the shortest distance via the relaying device is to sum the following two distances: The shortest distance from the relaying device to the source device The shortest distance from the relaying device to the destination device

(96) As a generalization of the above formula it can be said that the shortest distance via the relaying device can be calculated from path lengths of different sub paths of the shortest path that the relaying device is part of. P2 in FIG. 7 can for example be divided into two sub paths (D1-D2-D6 and D6-D3-D4-D5), but it could also be divided in many other ways, another example would be to divide it into 5 sub paths (D1-D2, D2-D6, D6-D3, D3-D4, D4-D5).

(97) In one embodiment the shortest distance via the relaying device (or the necessary path lengths of some sub paths to be able to calculate it) are stored in the relaying device.

(98) In another embodiment the above information is stored in another device. The relaying device would in this case have to obtain the information from the other device.

(99) In yet another embodiment the necessary path lengths of some sub paths to be able to calculate the shortest distance via the relaying device is distributed between device. The relaying device would in this case have to obtain some or all of the path lengths from one or more other devices.

(100) Going back to the case of calculating the shortest distance via the relaying device by adding the shortest distance from the relaying device to the source device and the shortest distance from the relaying device to the destination device.

(101) The distances or lengths of each of the sub paths, can be obtained in two different ways. Let's take the shortest distance from the relaying device to the source device as an example. This distance could be obtained if the source device pings the relaying device (either just with the intention to find out the shortest distance between the two devices, or with the intention to see if the relaying device can be reached with the intention to send data to the relaying device). The same distance could be obtained if instead the relaying device pings the source device (with the same possible intentions as discussed in the reverse case above).

(102) The distances of the two sub-paths could be obtained beforehand or on demand (when needed). The relaying device could store information related to when it has pinged other devices and when it has been pinged by other devices. The relaying device could also have a mechanism or logic for deciding if and how long such stored information is valid. In some networks, when for example the positions of all or most of the devices are fixed geographically (for example sensors in a factory) or when the relative distances are fixed (for example sensors on containers on a ship that is moving), the values might be valid for a long time. In other types of networks where the devices have a higher degree of mobility the values might be valid for a significantly shorter amount of time. If the values are still valid they can be used, if they are no longer valid new values would have to be obtained.

(103) Below is outlined in more detail the case when the relaying device obtains the shortest distance via the relaying device by pinging the source device and the destination device. This means that the relaying device would obtain the shortest distance from the relaying device to the source device by pinging the source device, and obtain the shortest distance from the relaying device to the destination device by pinging the destination device, and then add the two distances. This is illustrated in FIG. 13. S1621 shows the relaying device initiating the pinging of the source device by transmitting a ping message (510) to the source device. S1622 shows the relaying device receiving a ping response message from the source device (520), the ping response message (520) being associated with the ping message (510) sent in S1621. The ping response message (520) contains the path length of the shortest possible path (526), representing the distance between the relaying device and the source device. S1623 shows the relaying device initiating the pinging of the destination device by transmitting a ping message (510) to the destination device. S1624 shows the relaying device receiving a ping response message from the destination device (520), the ping response message (520) being associated with the ping message (510) sent in S1623. The ping response message (520) contains the path length of the shortest possible path (526), representing the distance between the relaying device and the destination device. S1625 shows the determining of the shortest distance via the relaying device. This determination would be done by simply adding the two distances that were obtained from the shortest possibly path in the ping response messages.

(104) A few things have to be clarified about the description above and FIG. 13.

(105) The steps in FIG. 13 do not necessarily have to happen in the order as shown in the picture. The person skilled in the art will realize that; which device is pinged first and in which order the ping response messages are received does not affect the logic or the calculations.

(106) The person skilled in the art will also realise that the description, in relation to FIG. 6, describing different ways for different equipment to determine the shortest possible path length also applies to the description above, meaning e.g. that the device responding, with a ping response message, to the ping message could make the determination only sending one ping response message, or that the device initiating the ping sequence could make the determination thus possibly receiving multiple ping response messages. Please refer to the description related to FIG. 6 for more details.

(107) The different distances and other relevant information obtained in this way could be stored in the relaying device for future/later use.

(108) The shortest distance via the relaying device could also be obtained by overhearing and analyzing ping and ping response messages between other nodes in the network and the SD and DD.

(109) According to the logic described above the relaying device can find out the maximum allowed path length and the shortest distance via the relaying device. If the shortest distance via the relaying device is less or equal to the maximum allowed path length it would mean that the relaying device is on a short enough path, otherwise not. If the relaying device is on a short enough path a user data message from the source device to the relaying device will be relayed, otherwise not.

(110) When using the method and apparatus suggested in the embodiments herein, the filtering will be done as soon as possible in the paths, and a high degree of unnecessary relaying will be minimised.

(111) As an example, if the allowed additional hops equals 1 it would mean that the maximum allowed path length, for relaying will be 5. In path P3 already device D7 would determine it was not on a short enough path and would not relay the user data message. In path P4 already device D10 would determine it was not on a short enough path and would not relay the user data message.

(112) Let's again make a short comparison with using TTL (Time to Live). Assume D1 knows that the shortest distance from D1 to D5 is 4 hops.

(113) As an example, to make sure the user data message reaches D5, D1 could set TTL to 4. This would mean that in path 3 D7 would relay the user data message allowing it to reach D8. In path 4 D10, D11 and D12 would relay the user data message allowing it to reach D13.

(114) As another example D1 could set TTL to 5, with the intention of using TTL to achieve some additional multipath behaviour. This would mean that in path 3 D7 and D8 would relay the user data message allowing it to reach D4. In path 4 D10, D11, D12 and D13 would relay the user data message allowing it to reach D14.

(115) The above examples illustrate that using TTL will achieve some filtering, but one can also see that the filtering will be achieved at the end of the paths. This means that some unnecessary relaying would be done, meaning that user data messages would be relayed even in parts of paths where it would be blocked at the end of the paths. In both examples in path 3 D7 would relay the user data messages when in fact the relaying they do will not contribute to the successful transmission of the user data message to D5. In path 4 it would be even worse, here several devices would relay the user data message to no benefit. Here one can see that the performance according to the method and apparatus suggested in the embodiments herein would here be significantly better than if using TTL.

(116) FIG. 8 introduces ARDTS (allowed remaining distance to source). The introduction of ARDTS allows for an alternative way for a relaying device to determine if it is on a short enough path.

(117) ARDTS states the allowed remaining distance to source, meaning the allowed remaining distance from the relaying device to the source device, when relaying a ping response message (520) from the destination device intended for the source device. Please note that ARDTS is not primarily intended to allow the relaying device to determine whether the ping response message as such should be relayed (even if it in some embodiments could be used to filter such relaying). Instead ARDTS is mainly intended to allow the relaying device to understand if it is on a short enough path or not, allowing the relaying device to determine whether it should relay a user data message from the source device to the destination device.

(118) As a comparison, the solution described further above, with reference to FIG. 7, was based on that, for a relaying device to be able to determine that it is on a short enough path it would need to know two things. The maximum allowed path length a which is the sum of: the path length of the shortest possible path the allowed additional hops The shortest distance via the relaying device

(119) The solution described here, with reference to FIGS. 8 and 9, is based on that, for a relaying device to be able to determine that it is on a short enough path it would need to know two things. The allowed remaining distance to source (ARDTS) a which is the sum of: the remaining distance to source (RDTS) on the shortest possible path the allowed additional hops The shortest distance between the source device and the relaying device

(120) If ARDTS is greater than or equal to the shortest distance between the source device and the relaying device, then the relaying device is on a short enough path, otherwise not

(121) ARDTS (allowed remaining distance to source) has different values in different devices. It has the highest value (the start value) in the destination device, where it corresponds to the maximum allowed path length. ARDTS is decreased by one for each relaying device that is one step closer to the source device.

(122) ARDTS (allowed remaining distance to source) is based on a related value RDTS (remaining distance to source). RDTS is carried in the RDTS (remaining distance to source) field in the ping response message. The relationship between ARDTS and RDTS is elaborated on further below, in relation to FIG. 9.

(123) The shortest distance between the source device and the relaying device also has different values in different nodes. The value can be obtained from the hop counter in the ping message (the hop counter is discussed in detail in the description related to FIG. 7).

(124) As can be seen above the two solutions are based on the same principle; that the maximum allowed path length (the path length of the shortest possible path plus the allowed additional hops) reflects the design objectives. It is purely a matter of two slightly different ways of distributing different parameters between the devices, to allow a relaying device to determine whether it is on a short enough path, meaning that it should relay a user data message, or not.

(125) The table in FIG. 8 shows ARDTS values for three different cases with three different design criteria. To make the table less complex, and thus easier to understand as an introduction, it only shows ARDTS values for devices that are part of path P2 (D1-D2-D6-D3-D4-D5). To further simplify things the table also only shows the ARDTS values that can be derived from ping response messages received via path P2. (Devices that are part of path P2 could also be part of other paths and could also receive ping response messages through these other paths.)

(126) The three lower rows, starting with P2 in the first column, shows the three different cases, one case per row. The different design criteria relate to using different values for the maximum allowed path length. The maximum allowed path length is the start value for ARDTS which applies to the destination device.

(127) The first row shows the example when the maximum allowed path length is set to “the path length of the shortest possible path”, which in this example is 4. This means that only devices that are on a path with the path length of 4 should relay user data messages. As can be seen the values decrease by one for each device that is one step closer to the source device, as an example ARDTS for D6 is 1.

(128) The second row shows the example when the maximum allowed path length is set to “the path length of the shortest possible path” plus 1 allowed additional hop. This means that only devices that are on a path with the path length of 5, or shorter, should relay user data messages. As can be seen the values decrease by one for each device that is one step closer to the source device, as an example ARDTS for D6 is 2.

(129) The third row shows the example when the maximum allowed path length is set to “the path length of the shortest possible path” plus 2 allowed additional hops. This means that only devices that are on a path with the path length of 6, or shorter, should relay user data messages. As can be seen the values decrease by one for each device that is one step closer to the source device, as an example ARDTS for D6 is 3.

(130) FIG. 9 now shows examples on how ARDTS can be used when determining whether a relaying device is on a short enough path.

(131) The description below focuses on D6 being the relaying device (as indicated in the upper part of FIG. 9), but will also cover when D3 and D8 are the relaying device.

(132) The table in the lower part of FIG. 9 shows values for shortest distance between the source device and the relaying device as well as for ARDTS.

(133) Each row in the table shows values for a specific device. As can be seen, in the upper part of FIG. 9, some devices are on multiple paths (for example D6 and D3), while some are not (for example D8). Devices that are on multiple paths will have values in multiple rows, one row per path, thus: D6 has values in two rows (one for P2 and one for P3) D3 has values in two rows (one for P1 and one for P2) D8 has values in one row (for P3).

(134) The left most part, or block, of the table, with the header “Distance to Source Device”, is related to the determination of the shortest distance between the source device and the relaying device.

(135) Each row shows the distance to the source device from the relaying device, for relaying device on a path that the relaying device is part of. In case the relaying device is part of multiple paths, there will be multiple rows, one for each path. The distances to the source device can be different in the same relaying device on different paths. The distance to the source device from the relaying device can be obtained from the hop counter in the ping message. The ping message (or instances thereof) can arrive multiple times, if the path branches towards the source device.

(136) As an example, device D3 is part of the paths P1 and P2. When the ping message arrives via P1 it has passed D1 and D2 before reaching D3, here the distance to the source device will be 2. When the ping message arrives via P2 it has passed D1, D2 and D6 before reaching D3, here the distance to the source device will be 3.

(137) The shortest distance between the source device and the relaying device is the shortest distance of the one or more values for the distance to the source device for the different paths. In the example above the shortest distance between the source device and the relaying device for D3 as relaying device is the lowest value of 2 and 3, which is 2. Meaning that in any of the paths that D3 is part of, the shortest distance to the source device is 2.

(138) The three rightmost parts, or blocks, of the table are related to the determination of ARDTS.

(139) Each of the three parts, or blocks, relates to a specific design criteria (meaning different values for maximum allowed path length), represented by different ARDTS start values (meaning the values in the destination device), the design criteria are the same as the examples used in the table in FIG. 8.

(140) Each row, in each part or block, shows a value for ARDTS for a relaying device related to a path that the relaying device is part of. In case the relaying device is part of multiple paths, there will be multiple rows, one for each path. ARDTS in the same relaying device can be different on different paths. ARDTS can be determined based on the related RDTS, which is carried in the RDTS field in the ping response message, how this can be done will be elaborated on further below. The ping response message (or instances thereof) can arrive multiple times, if the path branches towards the destination device.

(141) As an example (as shown in FIG. 5, FIG. 7 and FIG. 9), device D6 is part of the paths P2 and P3. When the ping response message arrives via P2 it has passed D5, D4 and D3 before reaching D6. If using the mid design criteria (where ARDTS equals 5 in the destination device) ARDTS in D6 will be 2 in path P2. When the ping response message arrives via P3 it has passed D5, D4, D8 and D7 before reaching D3. If using the mid design criteria (where ARDTS equals 5 in the destination device) ARDTS in D6 will be 1 in path P3.

(142) ARDTS is the longest, or maximum, ARDTS for a relaying device related to a path. In the example above ARDTS for D6 is the highest value of 2 and 1, which is 2. The maximum ARDTS (which is the one that is to be selected as the ARDTS) represents the ARDTS which has passed less nodes, meaning the ARDTS in the ping response message that has been traveling the shortest way from the destination device to the relaying devices.

(143) Now let's give a few examples of how the relaying device would determine whether it is on a short enough path.

(144) As stated further above, a device is on a short enough path if ARDTS is greater than or equal to the shortest distance between the source device and the relaying device, otherwise not.

(145) Let's start discussing the case where the start value of ARDTS (the maximum allowed path length) is set to “the path length of the shortest possible path”. The parts of the table that are of interest here is the leftmost part (column 3 with the headers “Distance to Source Device” and “Distance”). And the leftmost of the three parts to the right (column 4 with the header “ARDTS equals 4 in DD”). Let's cover the cases when D6, D3 and D8 are the relaying devices. (The logic is explained in detail for D6, the logic for D3 and D8 is identical) In D6 The shortest distance to the source device Is the minimum value of the distance fields (column 3) for the applicable paths P2 (row 2) and P3 (row 3) Is 2 ARDTS Is the maximum value of the Value in the Dx fields (column 4) for the applicable paths P2 (row 2) and P3 (row 3) Is 1 ARDTS is not greater than or equal to the shortest distance to the source device. Thus D6 is not on a short enough path In D3 The shortest distance to the source device Is the minimum value of the distance fields (column 3) for the applicable paths P1 (row 4) and P2 (row 5) Is 2 ARDTS Is the maximum value of the Value in the Dx fields (column 4) for the applicable paths P1 (row 4) and P2 (row 5) Is 2 ARDTS is greater than or equal to the shortest distance to the source device. Thus D3 is on a short enough path In D8 The shortest distance to the source device Is the minimum value of the distance fields (column 3) for the only applicable path P3 (row 6) Is 4 ARDTS Is the maximum value of the Value in the Dx fields (column 4) for the only applicable path P3 (row 6) Is 2 ARDTS is not greater than or equal to the shortest distance to the source device. Thus D8 is not on a short enough path

(146) Next let's take a look at the case where the start value of ARDTS (the maximum allowed path length) is set to “the path length of the shortest possible path” plus one. Making the same analysis as above, with the exception of using data from column 5 with the header “ARDTS equals 5 in DD” when obtaining ARDTS, one will find that: D6 is on a short enough path D3 is on a short enough path D8 is not on a short enough path

(147) Next let's take a look at the case where the start value of ARDTS (the maximum allowed path length) is set to “the path length of the shortest possible path” plus two. Making the same analysis as above, with the exception of using data from column 6 with the header “ARDTS equals 6 in DD” when obtaining ARDTS, one will find that: D6 is on a short enough path D3 is on a short enough path D8 is on a short enough path

(148) As is mentioned above ARDTS is based on a related value RDTS. RDTS is carried in the remaining distance to source field (529) in the ping response message (520). RDTS can have two different meanings depending on how the system is designed. RDTS could mean either of: The allowed remaining distance to source The remaining distance to source on the shortest possible path

(149) In order for the ARDTS to allow all relaying devices to obtain ARDTS, the corresponding RDTS value has to be distributed through the paths, each relaying device in the paths has to contribute by relaying the ping response message towards the source device. A relaying device that receives a ping response message will obtain the RDTS value, step it, use it store it locally or both, insert it in the ping response message that will be forwarded towards the source device.

(150) The relaying device (RD) will perform some, or all, of the following steps (not necessarily in the exact order listed below) in order to contribute to the distribution of the RDTS value: Receive a ping response message (520) from the destination device (DD, D5) intended for the source device (SD, D1). Determine whether the ping response message is intended for the relaying device (meaning that it would be the response to a ping message originating in the relaying device, rather than in the source device). If the ping response message is not intended for the relaying device: Obtain RDTS from the RDTS field (529) in the ping response message (520) decrease the obtained RDTS, indicating that one more hop towards the source device has been successfully made. Relay the ping response message (520), with the RDTS field now containing the obtained and decreased RDTS.

(151) Please note that in analogy with the discussion on the various ways of initiating the hop counter and stepping the hop counter, the initial value of ARDTS (and/or RDTS) and the stepping of ARDTS (and/or RDTS) could be implemented in various ways. The most straightforward alternative is to set the start value (the value of ARDTS in the destination device) to the maximum allowed path length, and to step by decreasing by one. Another straightforward alternative is to set the start value to maximum allowed path length minus one, and to step by decreasing by one. Which of these ways to choose depends on whether a relaying device use the value before stepping it, or the other way around. Basically, it is about whether the receiving device should regard the RDTS value in the ping response message as valid in the sending device or in the receiving device. A wide variety of other approaches are possible, as long as the involved devices agree on the logic.

(152) The description of the steps in the bulleted list, describes the basic mechanism for how the RDTS value is distributed through devices on a path.

(153) In addition to the above, if the relaying device receives multiple RDTS values in multiple ping response messages that are related to the same ping message, then the relaying device has to determine which RDTS value is largest, and use the largest value when determining ARDTS. The relaying device could also choose to use the larger value when relaying a specific ping response message, or simply use the value obtained when receiving that specific ping response message.

(154) Also depending on the meaning of RDTS, different actions has to be taken to obtain ARDTS.

(155) If RDTS means the allowed remaining distance to source, then ARDTS equals RDTS (and the relaying device does not have to obtain the allowed additional hops separately).

(156) If RDTS means the remaining distance to source on the shortest possible path, then ARDTS can be calculated from the sum of RDTS and the allowed additional hops (which has to be obtained separately). Here, in analogy with the related description of FIG. 7, the allowed additional hops could be obtained in a variety of ways. Depending on the implementation the relaying device could obtain the allowed additional hops from, any of: The ping message (510), sent from the source device In the allowed additional hops field (518) The ping response message (520), sent from the destination device In the allowed additional hops field (528) The allowed additional hops could be pre-configured in the relaying device The user data message (530), sent from the source device In the allowed additional hops field (538) Another message, sent from another device.

(157) In the three first ways above ARDTS will be available in the relaying device upon reception of a ping response message (the only one, or one of many).

(158) In the fourth way, ARDTS will be available upon reception of the user data message.

(159) In the fifth way, ARDTS could be available at different times depending on the implementation.

(160) A comparison with using TTL (Time to Live) will be in analogy with the comparison made when discussing FIG. 7.

(161) FIG. 10 shows the message formats for the different messages types. The exact use of the message types and the fields are described throughout the description. A short overview is given below.

(162) The description focus on three different message types, the Ping Message (510), the Ping Response Message (520) and the User Data Message (530). Some fields are present in all the three message types, and some fields are unique for only one message type. When using an x in the field reference below, it means that the description is generic and covers the field in all message types.

(163) Before describing the address fields, it is important to point out that throughout this description, the following terminology is used for the different devices, unless specifically stated.

(164) The source device—denotes the device that wants to send a user data message to, or intended for, the destination device. The source device will, at some point before sending the user data message (530), send a ping message (510) to, or intended for, the destination device, among other things in order to find out if the destination device is reachable and how far away it is, measured in hops. Another way of expressing this is to say that the source device is the originator of the ping message, and of the user data message, and that the destination device is the intended receiver. The ping message, and also the user data message, might be relayed by other devices on different paths towards the destination device. The source device is still the originator of the ping message, and the user data message, when being relayed. The corresponding relayed messages can be seen as different instances of the original device, the corresponding relayed messages are principally copies of the original message even though the values in some fields might be changed.

(165) The destination device—denotes the device that is the intended receiver of the ping message (510) and the user data message (530). The destination device will, upon reception of a ping message, respond by sending back a ping response message (320) intended for the source device. In this case the destination device is the originator of the ping response message and the source device is the intended receiver.

(166) The relaying device—denotes a device that will take the decision on whether to relay a user data message originating in the source device intended for the destination device.

(167) All of the different scenarios described herein have the following overall message flow goal. The source device sends a ping message to the destination device, the destination device responds with a ping response message, the source device will then send a user data message to the destination device. All the different messages might be relayed by other devices.

(168) The Source Address 5×1 and Destination Address 5×2 are two fields that are present in messages of all message types. The Source Address indicates the originator of the message, while the destination address indicates the intended receiver of the message.

(169) The Sequence Number 5×3 is an optional field, in the meaning that whether it is present or not and how the use would be implemented if present is not fundamental for the basics of the embodiments described. If present it could be utilised to separate different messages, for example it could identify different user data messages from the specific source device to a specific destination device.

(170) The TTL (Time to Live) 5×4 is an optional field, in the meaning that whether it is present or not and how the use would be implemented if present is not fundamental for the basics of the embodiments described. TTL is useful for setting limits for how many hops a message should be allowed to make on its way from the destination node to a source node.

(171) The User Data field 540 carries the user data in the user data message (530).

(172) The remaining fields has been explained in detail when discussing different embodiments of the invention.

(173) FIGS. 11-14 are simplified flowcharts depicting different embodiments of a method in a relaying device. FIG. 11, which shows more generic aspects, is also the basis for FIGS. 12 to 14, which shows more specific aspects.

(174) These flow charts aim at describing the top level aspects of the steps in the method. The more intricate details of for example which parameters to obtain from which message in the different embodiments are elaborated on in relation to FIGS. 1-9.

(175) FIG. 11 is a simplified flowchart describing the generic embodiments of a method in a relaying device. This flow chart covers both of the two main embodiments in this description. The two main embodiments describes how a relaying device determines whether to relay a user data message. In both of the main embodiments the determination of whether to relay a user data message is based on the relaying device determining whether the it is on a short enough path, between the source device and the destination device. The main difference between the two main embodiments is how the relaying device determines if it is on a short enough path, this will be elaborated on in relation to FIGS. 12-14.

(176) The relaying device will: S1000—receive a ping message, 510 (originating in the source device, intended for the destination device) and obtain one or more parameters from the ping message. An example of a parameter that is needed in both of the two main embodiments is the Hop Counter, 514. S1100—relay the ping message towards the destination device S1200—receive a user data message, 530 (originating in the source device, intended for the destination device) that is related to the ping message. S1400—determine whether it is on a possible path, based on whether it has received a ping response message, 520, related to the ping message, 510. If it is not on a possible path S1900—Not relay the user data message If it is on a possible path: S1600—determine if it is on a short enough path If it is not on a short enough path  S1900—Not relay the user data message If it is on a short enough path  S1900—Relay the user data message

(177) FIG. 12 is a flow flowchart depicting embodiments of a method in a relaying device when taking decisions on whether to relay or not is based on obtaining the shortest distance via the relaying device.

(178) The difference between this flow chart and the flow chart in FIG. 11 is that: S1600—determine if it is on a short enough path Can be broken down into two steps. S1620—acquiring the shortest distance via relaying device. S1640—determine if it is on a short enough path (based on the shortest distance via relaying device)

(179) FIG. 13 is a flow flowchart depicting embodiments of a method in a relaying device for acquiring the shortest distance via the relaying path using pinging. It outlines in more detail the case when the relaying device obtains the shortest distance via the relaying device by pinging the source device and the destination device. This means that the relaying device would obtain the shortest distance from the relaying device to the source device by pinging the source device, and obtain the shortest distance from the relaying device to the destination device by pinging the destination device, and then add the two distances. This is illustrated in FIG. 13. S1621 shows the relaying device initiating the pinging of the source device by transmitting a ping message (510) to the source device. S1622 shows the relaying device receiving a ping response message from the source device (520), the ping response message (520) being associated with the ping message (510) sent in S1621. The ping response message (520) contains the path length of the shortest possible path (526), representing the distance between the relaying device and the source device. S1623 shows the relaying device initiating the pinging of the destination device by transmitting a ping message (510) to the destination device. S1624 shows the relaying device receiving a ping response message from the destination device (520), the ping response message (520) being associated with the ping message (510) sent in S1623. The ping response message (520) contains the path length of the shortest possible path (526), representing the distance between the relaying device and the destination device. S1625 shows the determining of the shortest distance via the relaying device. This determination would be done by simply adding the two distances that were obtained from the shortest possibly path in the ping response messages.

(180) The steps in FIG. 13 do not necessarily have to happen in the order as shown in the picture. The person skilled in the art will realize that; which device is pinged first and in which order the ping response messages are received does not affect the logic or the calculations.

(181) FIG. 14 is a flow flowchart depicting embodiments of a method in a relaying device when taking decisions on whether to relay or not is based on the allowed remaining distance to source (ARDTS).

(182) The difference between this flow chart and the flow chart in FIG. 11 is that: S1600—determine if it is on a short enough path

(183) Can be broken down into two steps. S16600—acquiring the allowed remaining distance to source. S1640—determine if it is on a short enough path (based on the allowed remaining distance to source)

(184) FIG. 15 is a schematic block diagram illustrating embodiments of a relaying device.

(185) The relaying (RD) device comprises various units.

(186) A controller unit (U100) further comprising, a determining unit (U102), an acquiring unit (U104), an obtaining unit (U106) and a relaying unit (U108), where the controller unit (U100) is (and/or the comprised units are) configured to make determinations, acquiring and obtaining information and relaying messages, according to the various embodiments described in this specification.

(187) A data base (U112) for permanently or temporarily storing different information according to the various embodiments described in this application.

(188) A transceiver unit (U110) that is configured to transmit and receive the various messages according to the various embodiments described in this application.

(189) FIG. 16 shows one example of a computer program product.

(190) The computer program product (710) comprising a computer program (720), and a computer readable storage medium (730) on which the computer program is stored, where the computer program when run on the relaying device causes the relaying device to execute any or all of the various embodiments herein.

(191) The embodiments herein may be implemented through combination of analog and digital circuits, and one or more controller units, together with computer program code for performing the functions and actions of the embodiments herein. The program code mentioned above may also be provided as a computer program product, for instance in the form of a data carrier carrying computer program code for performing the embodiments herein when being loaded into the mobile communications device. One such carrier may be in the form of a CD ROM disc. It is however feasible with other data carriers such as a memory stick. The computer program code may furthermore be provided as pure program code on a server and downloaded to the mobile communications device at production, and/or during software updates.

(192) Those skilled in the art will also appreciate that the blocks in the block diagram, may refer to a combination of analog and digital circuits, and/or one or more controller units, configured with software and/or firmware, e.g. stored in any of the storage units, that when executed by the one or more controller units perform as described above. One or more of these controller units, as well as any other combination of analog and digital circuits, may be included in a single application-specific integrated circuitry (ASIC), or several controller units and various digital hardware may be distributed among several separate components, whether individually packaged or assembled into a system-on-a-chip (SoC). The one or more controller units may be any one of, or a combination of a central processing unit (CPU), graphical processing unit (GPU), programmable logic array (PAL) or any other similar type of circuit or logical arrangement.

(193) When using the word “comprise” or “comprising” it shall be interpreted as non-limiting, i.e. meaning “consist at least of”.

(194) The inventive concept has mainly been described above with reference to a few embodiments. However, as is readily appreciated by a person skilled in the art, other embodiments than the ones disclosed above are equally possible within the scope of the inventive concept, as defined by the appended patent claims.