Proactive location based routing in a wireless ad-hoc network

• US 20060062175A1
• Filed: 01/31/2005
• Published: 03/23/2006
• 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: Chen, Chung-Min, Chen, Wai, Ling, Yibei, Hsing, Russell
• Granted Patent: US 8,630,224 B2
• Time in Patent Office: Days
• 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 of operation of a mobile node for location based routing in an ad-hoc wireless network comprising the steps of:

calculating an estimated future location of a destination node; and

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

2. The method of claim 1 wherein said step of calculating an estimated future location of a destination node is based at least in part on the velocity and bearing of said destination node.

3. The method of claim 1 further comprising the step of:

identifying which one of a plurality of neighbor nodes is closest to said estimated future location; and

routing said data packet to said identified neighbor node.

4. The method of claim 1 further comprising the steps of:

calculating an estimated propagation time for said data packet to arrive at said destination node; and

calculating said estimated future location based at least in part on said propagation time.

5. The method of claim 1 further comprising the step of:

periodically broadcasting location information, wherein broadcast frequency is based at least in part on the velocity of said mobile node.

6. The method of claim 5 further comprising the step of:

dynamically adjusting said broadcast frequency.

7. The method of claim 1 further comprising the steps of:

maintaining a location table comprising location and mobility data for other nodes in said wireless network; and

updating said location table based on location and mobility data in a received data packet.

8. The method of claim 7 wherein the destination of said received data packet is another network node, said method further comprising the step of:

forwarding said data packet.

9. A network node comprising:

means for calculating an estimated future location of a destination node; and

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

10. The network node of claim 9 wherein said means for calculating an estimated future location of a destination node further comprises means for calculating said estimated future location based at least in part on the velocity and bearing of said destination node.

11. The network node of claim 9 further comprising:

means for identifying which one of a plurality of neighbor nodes is closest to said estimated future location; and

means for routing said data packet to said identified neighbor node.

12. The network node of claim 9 further comprising:

means for calculating an estimated propagation time for said data packet to arrive at said destination node; and

means for calculating said estimated future location based at least in part on said propagation time.

13. The network node of claim 9 further comprising:

means for periodically broadcasting location information, wherein broadcast frequency is based at least in part on the velocity of said mobile node.

14. The network node of claim 13 further comprising:

means for dynamically adjusting said broadcast frequency.

15. The network node of claim 9 further comprising:

means for maintaining a location table comprising location and mobility data for other network nodes; and

means for updating said location table based on location and mobility data in a received data packet.

16. The network node of claim 15 wherein the destination of said received data packet is another network node, said network node further comprising:

means for forwarding said data packet.

17. A network node comprising:

a memory storing;

a neighbor list; and

a location list comprising location and mobility data for a plurality of network nodes;

a processor for executing stored computer program instructions, said computer program instructions defining the steps of;

calculating an estimated future location of a destination node based at least in part on said stored location and mobility data;

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

a transmitter for routing a data packet to said identified intermediate node.

18. The network node of claim 17 wherein said computer program instructions further define the step of:

determining a location information broadcast frequency based at least in part upon the velocity of the network node.

19. The network node of claim 18 wherein said computer program instructions further define the step of:

dynamically adjusting said broadcast frequency.

20. The network node of claim 17 wherein said computer program instructions defining the step of identifying an intermediate node based at least in part on said estimated future location of said destination node further define the step of:

identifying a node in said neighbor list that is closest to said estimated future location.