Signal propagation delay routing

• US 8,072,906 B2
• Filed: 08/11/2003
• Issued: 12/06/2011
• 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
• Primary Examiner(s): TRAN, PABLO N
• Application Number:
  US10/526,565
• Publication Number:
  US 20060007863A1
• Time in Patent Office: 3,039 Days
• Field of Search: 370229-230, 370/235, 370/238, 370252-256, 3703101-313, 370/328, 370/338, 370386-393, 370/432, 455/403, 455418-425, 455427-430, 455432-445, 455450-457
• US Class Current: 370/255
• 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 in a network comprising a plurality of nodes, the method comprising:

transmitting a first message from a source node to a destination node along a plurality of paths, wherein each of the plurality of paths includes a first intermediate node and a second intermediate node;

receiving, at the source node, a plurality of second messages from the destination node, wherein each of the plurality of paths is traversed by one of the plurality of the second messages, and wherein each of the plurality of the second messages comprises;

a first time stamp corresponding to receipt of the second message at the first intermediate node;

a second time stamp corresponding to transmission of the second message from the first intermediate node to the second intermediate node;

a third time stamp corresponding to receipt of the second message at the second intermediate node; and

a fourth time stamp corresponding to transmission of the second message by the second intermediate node;

calculating a propagation delay between the first intermediate node and the second intermediate node for each of the plurality of paths, wherein the propagation delay comprises a difference between the second time stamp and the third time stamp; and

selecting a first path from the plurality of paths for communication between the source node and the destination node based at least in part on the propagation delays.

2. The method of claim 1, wherein each of the plurality of the second messages further comprises a fifth time stamp corresponding to receipt of the second message at a third intermediate node in communication with the second intermediate node.

3. The method of claim 2, further comprising calculating a second propagation delay for each of the plurality of paths, wherein the second propagation delay comprises a difference between the fourth time stamp and the fifth time stamp.

4. The method of claim 3, further comprising calculating an overall propagation delay for each of the plurality of paths based at least in part on a sum of the propagation delay and the second propagation delay of each of the plurality of paths, wherein the first path is selected based on the overall propagation delays.

5. The method of claim 4, further comprising calculating a processing delay of the first intermediate node for each of the plurality of paths, wherein the processing delay comprises a difference between the first time stamp and the second time stamp, and further wherein the first path is selected based at least in part on the processing delays.

6. The method of claim 1, further comprising:

selecting the first path for communication between the source node and the destination node based at least in part on signal qualities of the plurality of paths, wherein each of the plurality of the second messages further comprises a signal quality at the first intermediate node.

7. The method of claim 1, further comprising:

calculating a distance between the first intermediate node and the second intermediate node of each of the plurality of paths; and

selecting the first path for communication between the source node and the destination node based at least in part on the calculated distances.

8. The method of claim 1, further comprising:

calculating a velocity of the first intermediate node of each of the plurality of paths; and

selecting the first path for communication between the source node and the destination node based at least in part on the calculated velocities.

9. The method of claim 1, further comprising:

selecting the first path for communication between the source node and the destination node based at least in part on power attributes of the plurality of paths, wherein each of the plurality of the second messages further comprises a power attribute of the first intermediate node.

10. The method of claim 1, further comprising:

assessing a link stability for each of the plurality of paths; and

selecting the first path for communication between the source node and the destination node based at least in part on the assessed link stabilities.

11. The method of claim 1, further comprising:

identifying a quality of service for a third message; and

selecting the first path for communication between the source node and the destination node based at least in part on the identified quality of service.

12. The method of claim 8, wherein each of the plurality of the second messages further comprises:

a first position of the first intermediate node at a first time; and

a second position of the first intermediate node at a second time, and wherein calculating the velocity comprises using the first position and the second position.

13. The method of claim 1, further comprising using a routing algorithm to weight a parameter based on a priority value, wherein selecting the path for communication between the source node to the destination node is based at least in part on the weighted parameter.

14. The method of claim 1, further comprising using a mapping value to determine a degree to which a measured parameter value meets a predefined parameter value.

15. The method of claim 1, wherein the network is an ad hoc wireless network.

16. The method of claim 1, wherein the first intermediate node is a mobile station.

17. An ad hoc wireless network, comprising:

a plurality of nodes that form a plurality of paths between a source node and a destination node, wherein the source node is configured to transmit a first message to the destination node along the plurality of paths, and wherein the destination node is configured to send plurality of second messages to the source node in response to the first message, wherein each of the plurality of paths is traversed by one of the plurality of second messages;

a first intermediate node along the first path, wherein the first intermediate node is configured to generate a first time stamp corresponding to receipt of the second message at the first intermediate node and a second time stamp corresponding to transmission of the second message from the first intermediate node to a second intermediate node along the first path;

the second intermediate node configured to generate a third time stamp corresponding to receipt of the second message at the second intermediate node; and

selecting means configured to select the first path from the plurality of paths for communication between the source node and the destination node based at least in part on propagation delays between the first intermediate node and the second intermediate node of each of the plurality of paths, wherein the propagation delay comprises a difference between the second time stamp and the third time stamp.

18. The ad hoc network of claim 17, wherein the propagation delay is stored in the second message.

19. The ad hoc network of claim 17, further comprising:

means for measuring a signal quality of the second message for each of the plurality of paths;

wherein the selecting means is further configured to select the first path for communication between the source node and the destination node based at least in part on the measured signal qualities.

20. The ad hoc network of claim 17, further comprising:

processing means for calculating a distance between the first intermediate node and the second intermediate node for each of the plurality of paths;

wherein the selecting means is further configured to select the first path for communication between the source node and the destination node based at least in part on the calculated distances.

21. The ad hoc network of claim 17, further comprising:

processing means for calculating a velocity of the first intermediate node for each of the plurality of paths;

wherein the selecting means is further configured to select the first path for communication between the source node and the destination node based at least in part on the calculated velocities.

22. The ad hoc network of claim 17, further comprising:

means for measuring a power attribute of the first intermediate node for each of the plurality of paths;

wherein the selecting means is configured to select the first path for communication between the source node and the destination node based at least in part on the measured power attributes.

23. The ad hoc network of claim 17, further comprising:

means for determining a link stability for each of the plurality of paths;

wherein the selecting means is further configured to select the first path for communication between the source node and the destination node based at least in part on the link stabilities.

24. The ad hoc network of claim 17, further comprising:

means for identifying a quality of service of a third message;

wherein the selecting means is further configured to select the first path for communication between the source node and the destination node based at least in part on the quality of service.

25. The ad hoc network of claim 17, wherein:

the selecting means is configured to select a plurality of candidate routes;

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

wherein the selecting means is further configured to select the first path from the plurality of candidate routes based at least in part on a quality of service of third message.

26. A node in an ad hoc wireless network, the node comprising:

means for transmitting a first message to a destination node along a plurality of paths, wherein each of the plurality of paths includes a first intermediate node and a second intermediate node;

means for receiving a plurality of second messages transmitted from the destination node along the plurality of paths, wherein each of the plurality of paths is traversed by one of the plurality of second messages, and wherein each of the second messages comprises;

a first time stamp corresponding to the time that the second message is received at the first intermediate node;

a second time stamp corresponding to the time that the second message is transmitted from the first intermediate node to the second intermediate node; and

a third time stamp corresponding to the time that the second message is received at the second intermediate node, wherein the first time, the second time, and the third time are stored in a metrics field of the message;

means for determining a propagation delay between the first intermediate node and the second intermediate node of each of the plurality of paths, wherein the propagation delay comprises a difference between the second time and the third time; and

means for selecting a first communication path for communication with the source node based at least in part on the propagation delays.

27. The node of claim 26, further comprising means for calculating a distance between the first intermediate node and the second intermediate node for each of the plurality of paths based at least in part on the propagation delay.