Methods and apparatus for routing in a mobile ad hoc network

• US 6,980,524 B1
• Filed: 05/22/2000
• Issued: 12/27/2005
• Est. Priority Date: 05/20/1999
• Status: Expired due to Fees

• Current Assignee: Polytechnic University (New York University)
• Original Assignee: Polytechnic University (New York University)
• Inventors: Lu, I-Tai, Joa-Ng, Mario
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/575,884
• Time in Patent Office: 2,045 Days
• Field of Search: 370248-255, 370389-3956, 370/465, 370/535, 370/428, 370466-473, 370/284, 370/331, 370/221, 709/223, 709/22, 709/315, 709/328, 342/354, 342/357, 455/12.1, 455 131- 134, 455/429, 455/428, 455/456.1, 455/503, 455/408, 455/458, 455/456, 455/456.2
• US Class Current: 370/254
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building

Abstract

A “peer-to-peer” hierarchical routing protocol—also referred to as Zone-based Hierarchical Link State Routing protocol (or “ZHLS”)—which incorporates location information into a novel “peer-to-peer” hierarchical routing approach. The network may be divided into non-overlapping zones. Aggregating nodes into zones conceals the detail of the network topology. Initially, each node knows its own position and therefore zone ID through a position determination unit, such as a Global Positioning System (GPS). After the network is established, each node knows the low level (node level) topology about node connectivity within its zone and the high level (zone level) topology about zone connectivity of the whole network. A packet may be forwarded by specifying the hierarchical address—zone ID and node ID—of a destination node in the packet header.

Claims

1. In a network having a plurality of nodes arranged in at least two zones, a method for a particular node to determine a current partial topological state of the network, the method comprising:

a) determining a zone of the network in which the particular node resides;

b) for each node in the zone, determining nodes having a physical communication link with the node in the zone; and

c) for each zone in the network, determining zones having a virtual connection with the zone in the network,

wherein the act of determining nodes having a physical communication link with the node in the zone includes;

i) broadcasting a link request from the node;

ii) if a response to the link request is received by the node,

A) if the response was from a node within the same zone as the node, storing an identifier of the responding node, and

B) if the response was from a node that is not within the same zone as the node, storing an identifier of the zone to which the responding node belongs; and

iii) broadcasting, from the particular node, a link state message including the identifier of the responding node if the response was from a node within the same zone and the identifier of the zone to which the responding node belongs if the response was from a node not within the same zone as the node.

2. The method of claim 1, wherein the act of determining nodes having a physical communication link with the node in the zone further includes:

iv) if a link state message is received, by the node, from another node, then storing the link state message if the other node is within the same zone as the particular node.

3. In a network having a plurality of nodes arranged in at least two zones, a method for a particular node to determine a current partial topological state of the network, the method comprising:

a) determining a zone of the network in which the particular node resides;

b) for each node in the zone, determining nodes having a physical communication link with the node in the zone; and

c) for each zone in the network, determining zones having a virtual connection with the zone in the network,

wherein the act, for each zone in the network, of determining zones having a virtual connection with the zone in the network includes;

i) determining whether another zone has a node with a physical communications link with a node in the zone, and

ii) if it is determined that the other zone has a node with a physical communications link with the zone in the zone, then storing a data structure including an identification of the other zone.

4. The method of claim 3, wherein the act, for each zone in the network, of determining zones having a virtual connection with the zone in the network further includes:

iii) sending the stored data structure, including the identification of the other zone, throughout the network.

5. The method of claim 4 wherein the stored data structure, including the identification of the other zone, is only broadcast by gateway nodes.

6. In a network having a plurality of nodes arranged in at least two zones, a method for a particular node to determine a current partial topological state of the network, the method comprising:

a) for each node in a zone in which the particular node resides, determining nodes having a physical communication link with the node in the zone; and

b) for each zone in the network, determining zones having a virtual connection with the zone in the network,

wherein the act of determining nodes having a physical communication link with the node in the zone includes;

i) broadcasting a link request from the node;

ii) if a response to the link request is received by the node,

A) if the response was from a node within the same zone as the node, storing an identifier of the responding node, and

B) if the response was from a node that is not within the same zone as the node, storing an identifier of the zone to which the responding node belongs; and

iii) broadcasting, from the particular node, a link state message including the identifier of the responding node if the response was from a node within the same zone as the node and the identifier of the zone to which the responding node belongs if the response was from a node that is not within the same zone as the node.

7. In a network having a plurality of nodes arranged in at least two zones, a method for a particular node to determine a current partial topological state of the network, the method comprising:

a) for each node in a zone in which the particular node resides, determining nodes having a physical communication link with the node in the zone; and

b) for each zone in the network, determining zones having a virtual connection with the zone in the network,

wherein the act, for each zone in the network, of determining zones having a virtual connection with the zone in the network includes;

i) determining whether another zone has a node with a physical communications link with a node in the zone, and

ii) if it is determined that the other zone has a node with a physical communications link with the zone in the zone, then storing a data structure including an identification of the other zone.

8. In a network having a plurality of nodes arranged in at least two zones, a method for transmitting data from a first node in the network to a second node in the network, the method comprising:

a) determining whether or not the second node is in the same zone as the first node;

b1) if it is determined that the second node is in the same zone as the first node, then routing the data towards the second node based on an intra-zone routing table; and

b2) if it is determined that the second node is not in the same zone as the first node, then

i) transmitting a location request,

ii) if a response to the location request is received, then ensuring that the data is provided with a zone identifier and node identifier for the second node, and

iii) routing the data based on an inter-zone routing table.

9. In a network having a plurality of nodes arranged in at least two zones, a method for a particular node to respond to a request for the location of a destination node, the method comprising:

a) determining whether or not the destination node is in the zone of the particular node; and

b) if the zone of the destination node is in the zone of the particular node, transmitting a reply message which includes an identifier of the zone of the particular node,

wherein the step of determining whether or not the destination node is in the zone of a particular node is done based on the contents of a intra-zone routing table of the particular node.

10. In a network having a plurality of nodes arranged in at least two zones, a method for a particular node to forward data towards a destination node in a destination zone, the method comprising:

a) determining whether or not the destination zone of the data is the same as the zone of the particular node;

b1) if it is determined that the destination zone of the data is not the same as the zone of the particular node, then advancing the data towards the destination zone based on an inter-zone routing table; and

b2) if it is determined that the destination zone of the data is the same as the zone of the particular node, but that the particular node is not the destination node, then advancing the data towards the destination node based on an intra-zone routing table.

11. The method of claim 10 further comprising:

b3) if it is determined that the destination zone of the data is the same as the zone of the particular node, and that the particular node is the destination node, then reading the data.

12. A network having a plurality of nodes arranged in at least two zones, each node comprising:

a) a storage device, the storage device storing

i) a value identifying one of the at least two zones in which the current node resides,

ii) a list of nodes with which the current node has a physical communications link, and

iii) a list of zones with which the one of the at least two zones has a virtual connection; and

b) a processor which can access information stored on the storage device.

13. The network of claim 12, wherein the storage device further stores

iv) an intra-zone routing table, and

v) an inter-zone routing table.

14. The network of claim 12, wherein the storage device further stores

iv) a list of zones which include a node with which the current node has a physical communications link.

15. In a network having a plurality of nodes arranged in at least two zones, a node comprising:

a) a storage device, the storage device storing

i) a value identifying one of the at least two zones in which the current node resides,

ii) a list of nodes with which the current node has a physical communications link, and

iii) a list of zones with which the one of the at least two zones has a virtual connection; and

b) a processor which can access information stored on the storage device.

16. The node of claim 15, wherein the storage device further stores

iv) an intra-zone routing table, and

v) an inter-zone routing table.

17. The node of claim 15, wherein the storage device further stores

iv) a list of zones which include a node with which the current node has a physical communications link.

18. In a network having a plurality of nodes arranged in at least two zones, a method for a particular node to generate intra-zone and inter-zone routing tables based on a partial topological current state of the network, the method comprising:

a) determining a zone of the network in which the particular node resides;

b) for each node in the zone, determining nodes having a physical communication link with the node in the zone;

c) determining an intra-zone routing table from the nodes determined to have a physical communication link with the node in the zone;

d) for each zone in the network, determining zones having a virtual connection with the zone in the network; and

e) determining an inter-zone routing table from the zones determined to have a virtual connection with the zone in the network.

19. In a network having a plurality of nodes arranged in at least two zones, a method for a particular node to generate intra-zone and inter-zone routing tables based on a partial topological current state of the network, the method comprising:

a) for each node in the zone, determining nodes having a physical communication link with the node in a zone in which the particular node resides;

b) determining an intra-zone routing table from the nodes determined to have a physical communication link with the node in the zone;

c) for each zone in the network, determining zones having a virtual connection with the zone in the network; and

d) determining an inter-zone routing table from the zones determined to have a virtual connection with the zone in the network.