Routing and mobility management protocols for ad-hoc networks

• US 6,304,556 B1
• Filed: 08/24/1998
• Issued: 10/16/2001
• Est. Priority Date: 08/24/1998
• Status: Expired due to Term

• Current Assignee: Cornell Research Foundation Incorporated (Cornell University)
• Original Assignee: Cornell Research Foundation Incorporated (Cornell University)
• Inventors: Haas, Zygmunt J.
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US09/138,566
• Time in Patent Office: 1,149 Days
• Field of Search: 370/254, 370/255, 370/256, 370/257, 370/258, 370/328, 370/338, 370/349, 370/351-359, 370/238, 370/216, 370/227, 370/228, 370/237, 370/229, 709/220, 709/221, 709/222, 709/241, 455/422, 455/432, 455/433, 455/435, 455/456
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Two network communication protocols, one for routing and one for mobility management, are presented that are particularly suited for use with ad-hoc networks. The routing protocol is a proactive-reactive hybrid routing protocol that limits the scope of the proactive procedure to the node'"'"'s local neighborhood. Routing zones are defined for each node that include nodes whose distance from the subject node in hops is at most some predefined number, referred to as the zone radius. Each node is required to know the topology of the network within its routing zone only. The reactive procedure is limited during route discovery to queries of only those nodes located on the periphery of routing zones. In this manner, the queries hop across nodes in distances of zone radius, thus limiting the scope of the reactive procedure. The zone radius is preferably adjustable to accommodate different and differing network topologies and network operational conditions in the most efficient manner. The mobility management protocol relies on some network nodes assuming the mobility management function. In this scheme, each network node is “associated” with one or more mobility management nodes. The mobility management nodes form a virtual network which is embedded within the actual ad-hoc network. Each mobility management node knows the location of all nodes within its zone, and communicates this information to any other mobility management node that requests it.

Claims

1. A method for locating a route in a communications network comprising the steps of:

a) providing a network comprised of a plurality of communications nodes;

b) defining a routing zone for each node, each said routing zone including all nodes in said network that are within a predefined maximum distance from a corresponding node;

c) providing each node in said network with routing information for all nodes win said network that are within each node'"'"'s corresponding routing zone;

d) determining from said routing information whether a destination node is located within a same routing zone as a source node in said network, and if so, determining a route from said source node to said destination node from said information;

e) if said destination node is not located within the same routing zone as said source node, then sending a route location query from said source node to at least one peripheral node on a periphery of said source node'"'"'s routing zone;

f) in response to said route location query, determining whether said destination node is located within a routing zone corresponding to said at least one peripheral node, and if so,

g) determining at least one route from said source node through said at least one peripheral node to said destination node;

h) if said destination node is not located within said at least one peripheral node'"'"'s routing zone, then sending a route location query from said at least one peripheral node to at least one node on a periphery of said at least one peripheral node'"'"'s routing zone; and

i) repeating steps f-h as necessary to locate at least one route from said source node to said destination node.

2. The method of claim 1, further comprising the steps of monitoring the communication activity level for each node in at least one of said routing zones of said network, and adjusting the size of said at least one of said routing zones in response to changes in the monitored activity level.

3. The method of claim 2, wherein said network is a wireless network, said activity comprises the number of connections initiated by each node in a routing zone, and the size of said routing zone is increased or decreased in response to increase or decreases, respectively, in said number of initiated connections.

4. The method of claim 1, further comprising the steps of storing routing information for a route between said source node and said destination node in each node along said route, and deleting said routing information if said route is not requested again within a predetermined amount of time.

5. The method of claim 1, further comprising the steps of detecting whether a link between two nodes in a route has been broken due to a topology change in said network, and initiating a local repair procedure to locate a replacement path between said two nodes.

6. The method of claim 5, further comprising the steps of monitoring the number of local repairs initiated for a route, and initiating a new route location procedure after a predetermined number of repairs have been initiated to locate a new replacement route for said route.

7. The method of claim 1, wherein multiple routes are located between said source node and said destination node by sending route location queries to multiple peripheral nodes on the periphery of said source node'"'"'s routing zone.

8. The method of claim 7, wherein said route location queries are sent to said multiple peripheral nodes sequentially.

9. A method for locating a route in a communications network comprising the steps of:

a) providing a network comprised of a plurality of communications nodes;

b) designating a subset of said nodes as a plurality of mobility management nodes;

c) defining a management zone for each said mobility management node, each said management zone including all nodes in said network that are within a first predefined maximal distance from a corresponding mobility management node;

d) providing each mobility management node in said network with location information for all nodes that are within each mobility management node'"'"'s corresponding management zone;

e) defining a routing zone for each node in said network, each said routing zone including all nodes in said network that are within a second predefined maximal distance from a corresponding node;

f) providing each node in said network with routing information for all nodes within said network that are within each node'"'"'s corresponding routing zone;

g) sending a route determination request from a source node in said network to a first of said mobility management nodes having a management zone in which said source node is located;

h) sending said request from said first mobility management node to a plurality of the remaining mobility management nodes in said network, including at least a second mobility management node having a management zone that covers a destination node identified in said route determination request;

i) sending location information for said destination node from said second mobility management node to said first mobility management node;

j) determining a general direction from said source node to said destination node through use of said location information sent by said second mobility management node;

k) sending a route location query from said source node to at least one peripheral node on a periphery of said source node'"'"'s routing zone that is in said general direction of said destination node;

l) determining whether said destination node is located within a routing zone corresponding to any of said peripheral nodes, and if so, determining at least one route from said source node through said at least one peripheral node to said destination node;

m) if said destination node is not located within said at least one peripheral node'"'"'s routing zones, then sending a route location query from said at least one peripheral node to at least one node that is on a periphery of said at least one peripheral node'"'"'s routing zone, and is in said general direction of said destination node; and

n) repeating steps l and m as necessary to locate at least one route from said source node to said destination node.

10. The method of claim 9, wherein said first predefined maximal distance is greater than said second predefined maximal distance.

11. A multiple node communications network comprising:

a) a plurality of communications nodes for transmitting and receiving information;

b) means in a first node for storing routing information for all of said nodes that are within a routing zone of said first node, said routing zone being defined by a radius of a first predefined maximal distance from said first node;

c) means in said first node for receiving a query from a source node outside said first node'"'"'s routing zone for a route determination to a destination node; and

d) means responsive to said query for sending route information to said source node if said destination node is in said first node'"'"'s routing zone, and sending a route location query to at least one node on a periphery of said first node'"'"'s routing zone, if said destination node is not in said first node'"'"'s routing zone.

14. The communications network of claim 11, wherein said means for storing further includes means for storing route information for previously requested routes that have been received by said first node.

16. The communications network of claim 11, further comprising means for detecting whether a link between two nodes in a route has been broken due to a topology change in said network, and initiating a local repair procedure to locate a replacement path between said two nodes.

17. The communications network of claim 16, further comprising means for monitoring the number of local repairs initiated for a route, and initiating a new route location procedure after a predetermined number of repairs have been initiated to locate a new replacement route for said route.

18. The communications network of claim 11, wherein a plurality of said nodes are designated as mobility management nodes, and each of said mobility management nodes includes:

1) a management zone that includes all nodes in said network that are within a second predefined maximal distance from said mobility management node;

2) means for storing location information for all nodes that are within said mobility management node'"'"'s corresponding management routing zone;

3) means for receiving node location requests from nodes located in said mobility management zone, and from other of said mobility management nodes;

4) means for sending route determination requests to other mobility management nodes in said network in response to route determination requests received from nodes located within said management zone; and

5) means for sending node location information for a destination node located in said management zone to other of said mobility management nodes requesting the location of said destination node.

19. The communications network of claim 18, wherein said second predefined maximal distance is greater than said first predefined maximal distance, whereby said management zones are larger than said first node'"'"'s routing zone.

20. The communications network of claim 19, wherein a plurality of said mobility management nodes have management zones which overlap one another.

21. The communications network of claim 11, wherein each of a plurality of said nodes includes:

1) means for storing location information for all of said nodes that are within a routing zone of said node, said routing zone being defined by a radius of said first predefined maximal distance from said node;

2) means for receiving a query from a source node outside said node'"'"'s routing zone for a route determination to a destination node; and

3) means responsive to said query for sending route information to said source node if said destination node is m said node'"'"'s routing zone, and sending a route location query to at least one node on a periphery of said node'"'"'s routing zone, if said destination node is not in said node'"'"'s routing zone.

22. The communications network of claim 21, wherein said means for sending a route location query to at least one node on a periphery of said node'"'"'s routing zone further comprises means for sending route location queries to a plurality of nodes on said periphery of said node'"'"'s routing zone to locate multiple routes between said source node and said destination node.

12. The communications network of clam 11, wherein said first node further comprises means for monitoring the communication activity level for said first node'"'"'s routing zone, and adjusting the size of said routing zone in response to changes in the monitored activity level.

13. The communications network of claim 12, wherein said network is a wireless network, said activity comprises the number of connections initiated by each node in said first node'"'"'s routing zone, and the size of said routing zone is increased or decreased in response to increase or decreases, respectively, in said number of initiated connections.

15. The communications network of claim 13, further including means for deleting route information from said storing means if said first node does not receive a request for said route information within a predetermined amount of time.

23. The communications network of clam 22, wherein said means for sending route location queries to a plurality of nodes further comprises means for sequentially sending said queries to said plurality of peripheral nodes.