Proactive location based routing in a wireless ad-hoc network

• US 8,630,224 B2
• Filed: 01/31/2005
• Issued: 01/14/2014
• Est. Priority Date: 09/17/2004
• Status: Active Grant

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: TTI Inventions D LLC (Intellectual Ventures LLC)
• Inventors: Ling, Yibei, Chen, Chung-Min, Chen, Wai, Hsing, Russell
• Primary Examiner(s): Ho, Huy C
• Application Number:
  US11/048,410
• Publication Number:
  US 20060062175A1
• Time in Patent Office: 3,270 Days
• Field of Search: 370/328
• US Class Current: 370/328
• 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 28/26 Resource reservation
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/18 based on predicted events
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Disclosed is an improved proactive location based routing protocol for ad-hoc wireless networks. When a source node has a data packet to send to a destination node, the source node calculates an estimated future location of the destination node prior to forwarding a data packet to the destination node. The estimated future location may be based on the last known location, velocity and bearing of the destination node, as well as upon the estimated propagation delay (i.e., the estimated time it will take the data packet to reach the destination node after being transmitted by the source node). The source node routes the data packet by identifying which one of a plurality of its neighbor nodes is closest to the estimated future location of the destination node, and routes the data packet the identified neighbor node as an intermediate node along the route from the source node to the destination node. Further, the frequency of flooding broadcasts is based on the velocity of the network nodes. As the velocity of a network node increases, the rate at which the node broadcasts its location and mobility data also increases. The broadcast frequency of a network node may be dynamically adjusted as its velocity changes.

Claims

1. A method comprising:

receiving, from a destination node in a network, a broadcast that includes a current position and a bearing of the destination node, wherein the broadcast is made at a frequency that is directly proportional to a velocity of the destination node;

calculating an estimated propagation time for a data packet to arrive at the destination node, wherein the estimated propagation time is based at least in part on a prior transmission from the destination node; and

calculating an estimated future location of the destination node based at least in part on the broadcast from the destination node and at least in part on the estimated propagation time; and

routing the data packet to an intermediate node based at least in part on the estimated future location of the destination node.

2. The method of claim 1, further comprising:

identifying, out of a plurality of intermediate nodes, the intermediate node as being closest to the estimated future location.

3. The method of claim 1, wherein the propagation time is synchronized across all nodes via satellite.

4. The method of claim 1, further comprising:

receiving periodic broadcasts from a plurality of nodes, wherein a periodic broadcast includes mobility data of a node that transmitted the periodic broadcast, and wherein the mobility data comprises a node location, a node velocity, and a node bearing; and

compiling a location list of the plurality of nodes, wherein the location list comprises a node identifier (ID) and the mobility data for each of the plurality of nodes.

5. The method of claim 4, further comprising:

updating the location list based on mobility data included in a data packet received from the destination node.

6. The method of claim 5, wherein a destination of the received data packet is another network node, and further comprising

forwarding the received data packet.

7. The method of claim 1, wherein the frequency of broadcasts from the destination node is dynamically adjusted based at least in part on the velocity of the destination node.

8. The method of claim 1, further comprising:

compiling a neighbor list for a plurality of neighbor nodes, wherein the neighbor list comprises an identity for the neighbor nodes and a timestamp for a record corresponding to the neighbor nodes, and wherein the timestamp is synchronized with a satellite.

9. The method of claim 1, wherein the broadcast further includes the velocity of the destination node.

10. A network node comprising:

means for receiving mobility data for a destination node, wherein the mobility data is broadcast from the destination node at a frequency that is directly proportional to a velocity of the destination node;

means for calculating an estimated propagation time for a data packet to arrive at the destination node, wherein the estimated propagation time is based at least in part on a prior transmission from the destination node;

means for calculating an estimated future location of the destination node based at least in part on the mobility data and at least in part on the estimated propagation time; and

means for routing the data packet to an intermediate node based at least in part on the estimated future location of the destination node.

11. The network node of claim 10, wherein the mobility data comprises a location, the velocity, and a bearing of the destination node.

12. The network node of claim 10, further comprising:

means for identifying the intermediate node out of a plurality of neighbor nodes as being closest to the estimated future location.

13. The network node of claim 10, wherein the propagation time is synchronized across all nodes via satellite.

14. The network node of claim 10, wherein the frequency of broadcasts from the destination node are dynamically adjusted based at least in part on the velocity of the destination node.

15. The network node of claim 10, further comprising:

means for generating a location list for a plurality of nodes, wherein the location list comprises a node identifier (ID) and mobility data for the plurality of nodes, and wherein entries in the location list include a timestamp that is synchronized across all nodes via satellite.

16. The network node of claim 15, further comprising:

means for updating the location list based on the mobility data included in a received data packet.

17. The network node of claim 16, wherein a destination of the received data packet is another network node, and further comprising:

means for forwarding the received data packet.

18. A network node comprising:

a memory configured to store a location list comprising location and mobility data for a plurality of network nodes;

a processor operatively coupled to the memory and configured to;

determine a location and mobility information broadcast frequency for the network node based at least in part on a velocity of the network node;

calculate an estimated propagation time for a data packet to arrive at a destination node, wherein the estimated propagation time is based at least in part on a prior transmission from the network node;

calculate an estimated future location of the destination node based at least in part on the stored location and mobility data for the plurality of network nodes and at least in part on the estimated propagation time; and

identify an intermediate node based at least in part on the estimated future location of the destination node; and

a transmitter operatively coupled to the processor and configured to route the data packet to the identified intermediate node.

19. The network node of claim 18, wherein the processor is further configured to dynamically adjust the location and mobility information broadcast frequency such that the location and mobility information broadcast frequency is directly proportional to the velocity of the network node.

20. The network node of claim 18, wherein the memory is further configured to store a neighbor list of nodes that are in range of the network node, and wherein the processor is further configured to identify the intermediate node from the neighbor list.

21. A non-transitory computer-readable medium having instructions stored thereon, the instructions comprising:

instructions to receive a broadcast from a destination node in a network, wherein the broadcast includes a current position and a bearing of the destination node, and wherein the broadcast is made at a frequency that is directly proportional to a velocity of the destination node;

instructions to calculate an estimated propagation time for a data packet to arrive at the destination node, wherein the estimated propagation time is based at least in part on a prior transmission from the destination node;

instructions to calculate an estimated future location of the destination node based at least in part on the broadcast from the destination node and at least in part on the estimated propagation time; and

instructions to route the data packet to an intermediate node based at least in part on the estimated future location of the destination node.

22. The non-transitory computer-readable medium of claim 21, further comprising instructions to update, based on the broadcast, a location list that includes the destination node.

23. The non-transitory computer-readable medium of claim 21, wherein the broadcast further includes the velocity of the destination node.