Location based routing for mobile ad-hoc networks

• US 6,816,460 B1
• Filed: 03/14/2000
• Issued: 11/09/2004
• Est. Priority Date: 03/14/2000
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Ahmed, Walid, Jiang, Hong, Kodialam, Muralidharan Sampath, Monogioudis, Pantelis, Rege, Kiran M
• Primary Examiner(s): Yao, Kwang Bin
• Application Number:
  US09/525,735
• Time in Patent Office: 1,701 Days
• Field of Search: 370/254, 370/255, 370/236, 370/400, 370/410, 370/480, 370/491, 370/498, 370/500, 370/546, 370/461, 370/462, 370/331, 370/344, 370/338, 370/238, 370/238.1, 370/248, 455/403, 455/422, 455/432, 455/443, 455/899, 455/445, 455/411, 455/69, 709/238, 709/222
• US Class Current: 370/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In an ad-hoc mobile network, a geometry-based routing algorithm (GRA) is used to route traffic from a source node to a destination node. In the GRA, a source node maintains location information and routing information for all nodes in a local area and approximate location information for at least some nodes outside the local area. If the source node has to send a packet to a destination node outside their local area, then the source node uses the approximate location information of the destination node to identify which node in its local area is closer to the destination node than the source node. The source node then sends the packet to the identified local node for further routing.

Claims

1. A routing method for use in a packet network, the routing method comprising the steps of:

receiving a packet for transmission to a destination node; and

using a geometry-based routing protocol to route the packet to the destination node, the geometry-based routing protocol comprising;

calculating distances between a source node and a plurality of local area nodes;

calculating distances between the destination node and each of the plurality of local area nodes;

determining if the destination node is in a local area of nodes;

identifying a local area node closer to the destination node than the source node based on the calculated distances between the destination node and each of the plurality of local area nodes when the destination node is not in the local area of nodes; and

routing the packet on a path to the identified local area node without including at least one of the plurality of local area nodes.

2. The routing method of claim 1 wherein the routing step further includes sending the packet to a next hop node of the plurality of local area nodes on the path to the identified local area node.

3. The routing method of claim 1 wherein the using step further comprises the steps of:

storing a local topology table comprising a list of nodes that are in a local area of a source node;

storing a location table comprising location information about nodes of the packet network;

wherein the determining if the destination node is in a local area of nodes is based on a determining if the destination node is listed in the local topology table; and

wherein the identifying step is further based on the location table to identify one of the list of nodes in the local area that is closer to the destination node than the source node.

4. The routing method of claim 1 wherein the using step further comprises the steps of:

storing a local topology table comprising a list of nodes that are in a local area of a source node;

storing a location table comprising location information about nodes of the packet network;

for a node of the packet network outside of the local area, the identifying step is further based on the location table to identify one of the list of nodes in the local area that is closer to the node outside of the local area;

storing a routing table, wherein the routing table comprises at least an association between the node outside of the local area and a next hop node from the local area, where the next hop node is on a path to the identified local area node; and

wherein the routing step uses the routing table to route the packet.

5. A routing method for use in a packet network, the routing method comprising the steps of:

receiving a packet for transmission to a destination node; and

when the destination node is outside of a local node topology, routing the packet to the destination node as a function of distance to the destination node, by;

calculating distances between a source node and a plurality of local area nodes;

calculating distances between the destination node and the plurality of local area nodes;

determining if a node in the local node topology is closer to the destination node than the source node based on the calculated distances between the destination node and each of the plurality of local area nodes when the destination node is not in the local area of nodes; and

routing the packet on a path to the determined node without including at least one of the plurality of local area nodes.

6. The method of claim 5 wherein the routing step further includes sending the packet to a next hop node of the plurality of local area nodes on the path to the determined node.

7. A routing method for use in a packet network, the routing method comprising the steps of:

receiving, in a source node, a packet for transmission to a destination node;

selecting a node as a function of distance to the destination node such that the selected node is closer to the destination node than the source node, the function including;

calculating distances between a source node and a plurality of local area nodes; and

calculating distances between the destination node and each of the plurality of local area nodes, and

routing the packet on a path to the selected node without including at least one of the plurality of local area nodes.

8. A routing method for use in a packet network, the routing method comprising the steps of:

receiving, in a source node, a packet for transmission to a destination node;

selecting a node as a function of distance to the destination node such that the selected node is closer to the destination node than the source node, the function including;

calculating distances between the source node and a plurality of local area nodes; and

calculating distances between the destination node and each of the plurality of local area nodes; and

sending the packet to a next hop node on a path to the selected node without including at least one of the plurality of local area nodes.

9. Apparatus for use in a node of a packet network, the apparatus comprising:

a global positioning system receiver for determining location information of the node; and

a processor that implements a geometry-based routing protocol for routing packets to distant nodes such that the processor uses location information received from a plurality of local area nodes to select an identified node that is closest to one of the distant nodes, calculates distances between the node and the plurality of local area nodes, and calculate calculates distances between the destination one distant node and each of the plurality of local area nodes, the selecting based on the calculated distances between the one distant node and each of the plurality of local area nodes.

10. The apparatus of claim 9 further comprising:

a global position system receiver configurable to determine location information of the node.

11. The apparatus of claim 9 wherein the processor further routes packets to the selected node for further transmission to the distant node.

12. The apparatus of claim 9 wherein the processor further drops packets to the distant node if the node is also the selected node.

13. Apparatus for use in a node of a packet network, the apparatus comprising:

a processor that implements a geometry-based routing protocol for routing packets to distant nodes such that that processor uses location information received from a plurality of local area nodes to select a selected node that is closer to one of the distant nodes, calculates distances between the node and the plurality of local area nodes, calculates distances between the one distant node and each of the plurality of local area nodes, the selecting based on the calculated distances between the one distant node and each of the plurality of local area nodes, wherein the processor sends the packet to a next hop node on a path to the selected node.

14. The apparatus of claim 13 further comprising:

a global position system receiver configurable to determine location information of the node.

15. Apparatus for use in a first node of a packet network, the apparatus comprising:

a memory for storing (a) a local topology table comprising a list of nodes that are in a local area of the first node, and (b) a location table comprising location information about nodes of the packet network; and

a processor for routing a received packet to a destination node by determining if the destination node is listed in the local topology table, and, if the destination node is not in the local area of nodes, using the location table to;

identify one local area node of the list of nodes in the local area that is closer to the destination node than the first node, calculate distances between the first node and a plurality of local area nodes and calculate distances between the destination node and the plurality of local area nodes, and route the received packet to the identified local area node, the processor identifies the identified local area node based on the calculated distances between the distant node and each of the plurality of local area nodes.

16. Apparatus for use in a first node of a packet network, the apparatus comprising:

a memory for storing (a) a local topology table comprising a list of nodes that are in a local area of the first node, (b) a location table comprising location information about nodes of the packet network, and (c) a routing table; and

a processor for (a) using the location table to identify one of the list of nodes in the local area that is closer to a node of the packet network outside of the local area than the first node, in part by calculating distances between a source node and a plurality of local area nodes, and calculating distances between the destination node and the plurality of local area nodes, (b) creating an entry in the routing table that associates the node outside of the local area with a next hop node from the local area, where the next hop node is on a path to the identified local area node, and (c) routing a received packet to a destination node by using the routing table, wherein at least one of the nodes of the list of nodes is not on a path to the destination node.

17. An improved node for use in routing packets to a destination node of a packet network, the improvement comprising:

a router that routes packets to the destination node by determining if the destination node is in a local area of nodes such that if the destination node is not in the local area of nodes, the router identifies a local area node closer to the destination node than the improved node, in part by calculating distances between the improved node and a plurality of local area nodes and calculating distances between the destination node and the plurality of local area nodes, and routes the packet to the identified local area node without including at least one of the plurality of local area nodes.

18. An improved node for use in routing packets to a destination node of a packet network, the improvement comprising:

a router that routes packets to the destination node by determining if the destination node is in a local area of nodes such that if the destination node is not in the local area of nodes, the router identifies a local area node closer to the destination node than the improved node, in part by calculating distances between the improved node and a plurality of local area nodes and calculating distances between the destination node and the plurality of local area nodes, and sends the packet to a next hop node on a path to the identified local area node without including at least one of the plurality of local area nodes.