Location based routing for mobile ad-hoc networks

• US 7,006,453 B1
• Filed: 03/14/2000
• Issued: 02/28/2006
• Est. Priority Date: 03/14/2000
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Jiang, Hong, Monogioudis, Pantelis, Kodialam, Muralidharan Sampath, Ahmed, Walid, Rege, Kiran M
• Primary Examiner(s): PHAM, BRENDA H
• Application Number:
  US09/525,090
• Time in Patent Office: 2,177 Days
• Field of Search: 370/248, 370/310, 370/349, 370/351, 370/363, 370/368, 370/374, 370/378, 370/379, 370/381, 370/382, 370/384, 370/386, 370/389, 370/390, 370/392, 370/393, 370/400, 370/254, 370/255, 370/328, 370/371
• US Class Current: 370/255
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/248 Connectivity information update
• 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 8/22 Processing or transfer of terminal data, e.g. status or physical capabilities
• CPC Class Codes: H04W 8/24 Transfer of terminal data
• 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 protocol (GRP) is used to route traffic from a source node to a destination node. In the GRP, each node maintains a location list, which comprises location information for a number of nodes of the ad-hoc mobile network. Periodically, each node transmits to its direct neighbors (i.e., those nodes with which it has a point-to-point link) (a) its location, and (b) its location list. Each node that receives a location list from an adjacent node merges the received location list into its own location list such that location information for existing nodes, and/or newly identified nodes, is current.

Claims

1. A method for use in a node of a network comprising the steps of:

storing location information of other nodes of the network, wherein said location information comprises a global position represented by at least two coordinates,

exchanging the stored location information with adjacent nodes of the network, and

wherein said node stores a local topology having at least one other node with a continually changing position, said local topology having the location information of said at least one other node and connections between said node and said at least one other node, and said node stores said location information of other nodes outside of said local topology.

2. The method of claim 1, wherein said node uses a geometry-based routing protocol to transmit said location information to nodes outside of said local topology.

3. The method of claim 2, wherein said node determines a distance from a destination node outside of said local topology to nodes in said local topology using said geometry-based routing protocol and said location information to identify the closest node in said local topology for routing to said destination node.

4. The method of claim 1, wherein said node determines said coordinates from information received from a global positioning system.

5. The method of claim 1, said local topology of said node being nodes located within a predetermined number of hops from said node.

6. The method of claim 5, wherein said local topology of said node comprises a first set of nodes having a point-to-point link to said node and a second set of nodes having a point-to-point link to a node in said first set of nodes.

7. A method of creating a local topology of a node in a network, said local topology being stored by said node and having i) a list of direct neighbors of said node, ii) a location of said direct neighbors, and iii) connections between said node and said direct neighbors, comprising the steps of:

identifying said direct neighbors of said node, said direct neighbors being a subset of nodes within hearing distance of said node;

constructing point-to-point links from said node to at least some of said direct neighbors;

transmitting information about said location of said direct neighbors to other nodes of the network, wherein said location information includes a global position represented by at least two coordinates.

8. The method of claim 7, wherein the step of identifying said direct neighbors further comprises the step of collecting global position information of nodes.

9. The method of claim 8, wherein the step of collecting global position information further comprises the step of selecting nodes for said point-to-point links as a function of said global position information.

10. The method of claim 7, wherein said information about said location of said direct neighbors further includes associated time-stamp information indicating an age of the location information of at least some of the nodes of the network.

11. The method of claim 7, wherein said transmitting step is repeated periodically.

12. A method of updating a local topology of a node in a network, said local topology being stored by said node and having i) a list of direct neighbors of said node, ii) a location of said direct neighbors, and iii) connections between said node and said direct neighbors, comprising the steps of:

identifying said direct neighbors of said node, said direct neighbors being a subset of nodes within hearing distance of said node;

constructing point-to-point links from said node to at least some of said direct neighbors;

transmitting, at different times, information about said location of said direct neighbors to other nodes of the network, wherein said location information includes a global position represented by at least two coordinates.

13. The method of claim 12, wherein the step of identifying said direct neighbors further comprises the step of collecting global position information of nodes.

14. The method of claim 13, wherein the step of collecting global position information further comprises the step of selecting nodes for said point-to-point links as a function of said global positioning information.

15. The method of claim 12, wherein said information about said location of said direct neighbors further includes associated time-stamp information indicating an age of the location information of at least some of the nodes of the network.