Routing in wireless ad-hoc networks

• US 8,135,021 B2
• Filed: 09/28/2006
• Issued: 03/13/2012
• Est. Priority Date: 09/28/2006
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Westphal, Cedric
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): REDDIVALAM, SRINIVASA R
• Application Number:
  US11/529,801
• Publication Number:
  US 20080080520A1
• Time in Patent Office: 1,993 Days
• Field of Search: None
• US Class Current: 370/400
• CPC Class Codes: H04L 12/2838 Distribution of signals within a home automation network, e.g. involving splitting/multiplexing signals to/from different paths adaptations of television systems for transmission by electric cable for domestic distribution H04N7/106; hybrid transport H04L12/6418; home network arrangements specially adapted for distribution of digital video signals H04N7/24
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

A method of transmitting data in a communication system from a first node to destination node comprising transmitting the data from the first node to an intermediate node; determining if the intermediate node communicated with the destination node more recently than the first node that transmitted the data to the intermediate node communicated with the destination node; forwarding the data from the intermediate node to a further node if the intermediate node communicated with the destination node more recently than the first node that transmitted the data to the intermediate node communicated with the destination node.

Claims

1. A method of transmitting data in a communication system from a first node to destination node comprising:

transmitting the data from the first node to an intermediate node;

determining if the intermediate node communicated with the destination node more recently than the first node that transmitted the data to the intermediate node communicated with the destination node;

forwarding the data from the intermediate node to a further node if the intermediate node communicated with the destination node more recently than the first node that transmitted the data to the intermediate node communicated with the destination node,

wherein time information relating to when at least one of the first node and the intermediate node communicated with the destination node is transmitted with the data, and

wherein the first node transmits a request to find the intermediate node that has been in communication with the destination node when the first node has not previously directly communicated with the destination node.

3. A method as claimed in claim 1 wherein at least one of the first node and the intermediate node transmits the data by broadcasting the data.

13. A method as claimed in claim 1 wherein the data comprises an alert.

14. A method as claimed in claim 13 wherein the alert is generated by the first node when parameters sensed by the first node exceed a predefined threshold.

15. A method as claimed in claim 1 wherein the at least one of the first node, intermediate node and further node is static.

16. A method as claimed in claim 1 further comprising the step of storing time information for at least one of the first node, intermediate node and further node when at least one of the first node, intermediate node and further node was in contact with the destination node.

17. A method as claimed in claim 1 wherein there is more than one destination node.

18. A method as claimed in claim 16 wherein there at least one of the first node, intermediate node and further node stores time information relating to more than one destination node.

19. A method as claimed in claim 1 wherein the first node is the source node.

20. A method as claimed in claim 1 wherein the destination node is a sink node.

21. A method as claimed in claim 1 wherein at least one of the first node, the intermediate node and the further node are sensor nodes.

22. A method as claimed in claim 1 wherein the further node is the destination node.

23. A method as claimed in claim 1 wherein the communication system is an ad hoc network.

24. A method as claimed in claim 1 wherein the communication system is a sensor network.

25. A method as claimed in claim 1 wherein the communication system is metropolitan wireless mesh network.

26. A method as claimed in claim 1 where in the intermediate node is arranged to transmit a response to the request to the first node, containing an indication of the time when it communicated with the destination node.

27. A method as claimed in claim 26 wherein the first node is arranged to update the time information relating to when it was last in communication with the destination node based on the response.

2. A method of transmitting the data in a communication system from a first node to a destination node comprising;

receiving at the first node time information relating to when an intermediate node communicated with the destination node;

determining at the first node if the intermediate node communicated with the destination node more recently than the first node communicated with the destination node;

transmitting the data to the intermediate node if the intermediate node communicated with the destination node more recently than the first node communicated with the destination node,

wherein time information relating to when at least one of the first node and the intermediate node communicated with the destination node is transmitted with the data, and

wherein the first node transmits a request to find the intermediate node that has been in communication with the destination node when the first node has not previously directly communicated with the destination node.

4. A method as claimed in claim 2 wherein the first node receives time information via a handshake with the intermediate node.

5. A method as claimed in claim 2 wherein the time information is transmitted separately from the data.

6. A method as claimed in claim 2 wherein the time information is the time lapsed since either the first node or the intermediate node communicated with the destination node.

7. A method as claimed in claim 6 wherein the time lapsed is determined by timing the time lapsed from when the destination node stops communicating directly with either the first node or the intermediate node.

8. A method as claimed in claim 6 wherein the time lapsed is determined by timing the time lapsed from when the destination node starts communicating directly with either the first node or the intermediate node.

9. A method as claimed in claim 6 wherein the time lapsed is determined by subtracting the time when the destination node stopped communication directly with either the first node or the intermediate node from the current time.

10. A method as claimed in claim 6 wherein the time lapsed is determined by subtracting the time when the destination node started communication directly with either the first node or the intermediate node from the current time.

11. A method as claimed in claim 6 wherein the time lapsed is an estimated value calculated by adding a predetermined amount to the time lapsed from when the destination node stopped communicating directly with a neighbour node.

12. A method as claimed in claim 6 wherein the time lapsed is an estimated value calculated by adding a predetermined amount to the time lapsed from when the destination node started communicating directly with a neighbour node.

28. A communication system comprising a first node, an intermediate node, a further node and a destination node wherein the first node comprises:

a transmitter configured to transmit data to the intermediate node;

and wherein the intermediate node comprises;

a processor configured to determine if the intermediate node communicated with the destination node more recently than the first node that transmitted the data to the intermediate node communicated with the destination node; and

a transmitter configured to forward the data from the intermediate node to a further node if the intermediate node communicated with the destination node more recently than the first node that transmitted the data to the intermediate node communicated with the destination node,

wherein time information relating to when at least one of the first node and the intermediate node communicated with the destination node is transmitted with the data, and

wherein the first node transmits a request to find the intermediate node that has been in communication with the destination node when the first node has not previously directly communicated with the destination node.

30. A communication system as claimed in claim 28 wherein at least one of the first node, intermediate node and further node further comprise a timer for recording time information relating to when it communicated with the destination node.

31. A communication system as claimed in claim 30 wherein the timer records the time lapsed since the destination node stopped communicating with the first node, intermediate node or further node.

32. A communication system as claimed in claim 30 wherein the timer records the time lapsed since the destination node started communicating with the first node, intermediate node or further node.

33. A communication system as claimed in claim 30 wherein the timer records a time stamp of when the destination node stopped communicating with the first node, intermediate node or further node.

34. A communication system as claimed in claim 30 wherein the timer records a time stamp of when the destination node started communicating with the first node, intermediate node or further node.

35. A communication system as claimed in claim 28 wherein the data comprises an alert.

36. A communication system as claimed in claim 28 wherein the communication system is an ad hoc network.

37. A communication system as claimed in claim 28 wherein the communication system is a sensor network.

38. A communication system as claimed in claim 28 wherein the communication system is a wireless mesh network.

39. A communication system as claimed in claim 28 wherein at least one of the first node, the intermediate node and the further node comprise means for determining if it is in communication with the destination node.

40. A destination node for use in a communication system as claimed in claim 28.

41. A destination node as claimed in claim 40 further comprising means for indicating time information.

42. A destination node as claimed in claim 41 wherein the value of the time information indicated by the destination node relating to when the intermediate node communicated with the destination node is less than the value of the time information relating to when any other node communicated with the destination node.

29. A communication system comprising a first node, an intermediate node and a destination node wherein the first node comprises:

a receiver for receiving time information relating to when the intermediate node communicated with the destination node;

a processor for determining if the intermediate node communicated with the destination node more recently than the first node communicated with the destination node; and

a transmitter for transmitting the data to the intermediate node if the intermediate node communicated with the destination node more recently than the first node communicated with the destination node,

wherein at least one of the time information relating to when the intermediate node communicated with the destination node and time information relating to when the first node communicated with the destination mode is transmitted with the data, and

wherein the first node transmits a request to find the intermediate node that has been in communication with the destination node when the first node has not previously directly communicated with the destination node.

43. A destination node for use in a communication system comprising:

a transmitter configured to establish connection with an intermediate node; and

a receiver configured to receive data from the intermediate node,

wherein the receiver is arranged to receive data broadcast from a further node,

wherein time information relating to when at least one of a first node and the intermediate node communicated with the destination node is transmitted with the data to the intermediate node, and

wherein the first node transmits a request to find the intermediate node that has been in communication with the destination node when the first node has not previously directly communicated with the destination node.

44. A destination node as claimed in claim 43 wherein the transmitter is arranged to transmit time information indicating that the time lapsed since the destination node communicated with the intermediate node is zero.

45. A first node comprising:

a detector configured to detect if it is in communication with a destination node;

a timer configured to time the time lapsed since communicating with the destination node;

a processor configured to determine if an intermediate node communicated with a destination node more recently than the first node communicated with the destination node; and

a transmitter configured to forward data to the intermediate node if the intermediate node communicated with the destination node more recently than the first node communicated with the destination node,

wherein time information relating to at least one of the lapsed time and when the intermediate node communicated with the destination node is transmitted with the data, and wherein the first node transmits a request to find the intermediate node that has been in communication with the destination node when the first node has not previously directly communicated with the destination node.

46. A computer program product, embodied on a non-transitory computer-readable medium, comprising program code configured to perform, when the program code is run on a computer or on a processor:

transmitting the data from a first node to an intermediate node;

determining if the intermediate node communicated with a destination node more recently than the first node that transmitted the data to the intermediate node communicated with the destination node; and

forwarding the data from the intermediate node to a further node if the intermediate node communicated with the destination node more recently than the first node that transmitted the data to the intermediate node communicated with the destination node,

wherein time information relating to when at least one of the first node and the intermediate node communicated with the destination node is transmitted with the data, and

wherein the first node transmits a request to find the intermediate node that has been in communication with the destination node when the first node has not previously directly communicated with the destination node.

47. A computer program product, embodied on a non-transitory computer-readable medium, comprising program code configured to perform, when the program code is run on a computer or on a processor:

receiving at a first node time information relating to when an intermediate node communicated with a destination node;

determining at the first node if the intermediate node communicated with the destination node more recently than the first node communicated with the destination node; and

transmitting the data to the intermediate node if the intermediate node communicated with the destination node more recently than the first node communicated with the destination node,

wherein time information relating to when at least one of the first node and the intermediate node communicated with the destination node is transmitted with the data, and

wherein the first node transmits a request to find the intermediate node that has been in communication with the destination node when the first node has not previously directly communicated with the destination node.