Signal propagation delay routing

• US 20060007863A1
• Filed: 08/11/2003
• Published: 01/12/2006
• Est. Priority Date: 09/05/2002
• Status: Active Grant

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC), Province of Manitoba
• Original Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Inventors: Naghian, Siamak
• Granted Patent: US 8,072,906 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 1/16 in which the return channel carries supervisory signals, e.g. repetition request signals
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A method of routing a message from a source node to a destination node in an adhoc wireless network comprising a plurality of nodes, comprising the steps of; transmitting a first message from the source node to the destination node, receiving said first message at said destination node, transmitting a second message from said destination node in response to the first message and, wherein at least one of said first message and said second message is sent between the source and destination nodes via a plurality of paths comprising at least one intermediate node, selecting a path for communication between the source node and the destination node using an indication of the time taken for at least one of said second and first messages to propagate between each node on each path.

Claims

1. A method of routing a message from a source node to a destination node in an adhoc wireless network comprising a plurality of nodes, comprising the steps of;

transmitting a first message from the source node to the destination node, receiving said first message at said destination node,

transmitting a second message from said destination node in response to the first message and,

wherein at least one of said first message and said second message is sent between the source and destination nodes via a plurality of paths comprising at least one intermediate node,

selecting a path for communication between the source node and the destination node using an indication of the time taken for at least one of said second and first messages to propagate between each node on each path.

2. A method of routing a message as claimed in claim 1, wherein the indication of the time taken for at least one of the first and second messages to propagate between each node on the path is provided by time stamping the at least one of the first and second message at the time when the at least one of the first and second message is transmitted at each node.

3. A method of routing a message as claimed in claim 1, wherein the indication of the time taken for the at least one of the first and second messages to propagate between each node on the path is provided by time stamping the at least one of the first and second messages at the time when the at last one of the first and second messages is received at each node.

4. A method of routing a message as claimed in claim 1, wherein the indication of the time taken for the at least one of the first and second messages to propagate between each node on the path is given by calculating the actual time taken for the at least one of the first and second messages to propagate between each node and storing the calculated times in the messages.

5. A method of routing a message as claimed in claim 4 wherein the method comprises the step of:

summing the calculated times stored in the messages in order to determine the time taken for the at least one of the first and second messages to propagate between the source node and the destination node.

6. A method as claimed in claim 1, comprising the step of:

calculating the time taken for the at least one of the first and second messages to propagate between the source node and the destination node.

7. A method as claimed in claim 5, comprising the step of comparing the calculated time taken for the at least one of the first and second messages to propagate between the source node and the destination node to the time between transmitting the at least one of the first and second messages from either the source or destination node and receiving the at least one of the first and second messages at either the source the source or destination node.

8. A method of routing a message in accordance with claim 1 further comprising the step of;

measuring the signal quality of the at least one of the first and second messages at each node on the path; and

selecting a path for communication between the source node and the destination node using the measured the signal quality.

9. A method as claimed in claim 8, comprising the step of storing the signal quality measurement in the at least one of the first and second messages.

10. A method of routing a message in accordance with claim 1 further comprising the step of;

calculating the distance between each node; and

selecting a path for communication between the source node and the destination node using the calculated distance.

11. A method as claimed in claim 10, comprising the step of storing the calculated distance in the at least one of said first and second messages.

12. A method of routing a message in accordance with claim 1 further comprising the step of:

calculating the velocity of at least one of said nodes;

selecting a path for communication between the source node and the destination node using the calculated velocity of at least one of said nodes.

13. A method as claimed in claim 1 further comprising the steps of measuring power attributes of at least one of said nodes;

selecting a path for communication between the source node and the destination node using said measured power attribute.

14. A method as claimed in claim 1 further comprising the step of assessing the link stability of the plurality of paths between said plurality of nodes, selecting a path for communication between the source node and the destination node using said assessed link stability.

15. A method as claimed in claim 1, further comprising the step of assessing the required Quality of Service;

and

selecting a path—

for communication between the source node and the destination node based on the required quality of service.

16. A method as clamed in claim 1 comprising the steps of:

measuring the position of the nodes at a first time;

measuring the position of the nodes at a second time;

calculating the velocity of the nodes from the position measurements;

storing the calculated velocities in the at least one of the first and second messages

selecting a path for communication between the source node and the destination node using said stored velocities.

17. The method as claimed in claim 1 wherein a routing algorithm uses an priority value to weight a parameter which is used for selecting a path for communication between the source node to the destination node.

18. A method as claimed in claim 1, wherein a routing algorithm uses a mapping value that indicates the degree to which a measured parameter value meets a predefined parameter value.

19. A method as claimed in claim 1, wherein said network is an ad hoc network.

20. A method as claimed in claim 1, wherein at least one of said nodes is a mobile station.

21. An ad hoc wireless network comprising a plurality of nodes wherein a source node is arranged to transmit a first message to a destination node,

said destination node is arranged to receive the said first message,

said destination node is arranged to transmit a second message in response to said first message and;

at least one intermediate node is arranged to transmit at least one of said first message and said second message via a plurality of paths,

said network further comprising selecting means arranged to select at least one of said plurality of paths for communication between said source node and said destination node using an indication of the time taken for at least one of said second and first messages to propagate between each node on each path.

22. An ad hoc network as claimed in claim 21 wherein means to time stamp the at least one of the first and second messages is provided at each node.

23. An ad hoc network as claimed in claim 21 wherein each node comprises processing means to calculate the actual time taken for the at least one of said first and second messages to propagate between each node and to store the calculated time in the at least one of the first and second messages.

24. An ad hoc network claimed in claim 21 further comprising means to measure the signal quality of the at least one of the first and second messages;

wherein said selecting means is further arranged to select a path for communication between the source node and the destination node using said measured signal quality.

25. An, ad hoc network as claimed in claim 21 comprising processing means to calculate the distance between each node;

and

wherein said selecting means is further arranged for selecting a path for communication between the source node and the destination node using the calculated distance.

26. An ad hoc network as claimed in claim 21 comprising processing means for calculating the velocity of the at least one of said nodes;

and

wherein said selecting means is further arranged for selecting a path for communication between the source node and the destination node using the calculated velocity.

27. An ad hoc network as claimed in claim 21 further comprising means to measure power attributes of at least one of said nodes;

and

wherein said selecting means is further arranged to select a path for communication between the source node and the destination node using said measured power attributes.

28. An ad hoc network as claimed in claim 21 further comprising:

means to assess the link stability of the plurality of paths between said plurality of nodes; and

wherein said selecting means is further arranged to select a path for communication between the source node and the destination node using said assessed link stability.

29. An ad hoc network as claimed in claim 21 comprising:

means to assess the required quality of service; and

wherein said selecting means is further arranged for selecting a path for communication between the source node and the destination node based on the required quality of service.

30. An ad hoc network as claimed in claim 21, wherein:

said selecting means is arranged to select a plurality of candidate routes;

said network further comprising mapping means for mapping said plurality of candidate routes to a plurality of quality of service classes; and

wherein said selecting means is further arranged to select a path from one of said plurality of candidate routes that is mapped to a required quality of service.

31. A node in an ad hoc wireless network, said ad hoc network comprising a plurality of nodes, said node comprising:

means for receiving and transmitting at least one of a plurality of messages sent on a plurality of communication paths;

means for indicating the time said at least one message is received at the node; and

means for indicating the time said message is transmitted from the node.

32. A node as claimed in claim 31, wherein:

the means for indicating the time said message is received and transmitted are provided by time stamping the message.

33. A node as claimed in claim 31 further comprising means for storing the indication of the time said message is received and transmitted in a metrics field of the message.

34. A node as claimed in claim 31 further comprising means for calculating the time for said at least one message to propagate from another of said plurality of nodes to said node using the indication of time said message is received and transmitted.

35. A node as claimed in claim 31 further comprising means for calculating the distance between said plurality of nodes using the indication of time said message is received and transmitted.

36. A node as claimed in claim 31, further comprising selecting means to select a path from said plurality of communication paths on which to transmit and/or receive messages using said calculated time.