ADAPTIVE MESSAGE ROUTING FOR MOBILE AD HOC NETWORKS

• US 20100014444A1
• Filed: 10/12/2006
• Published: 01/21/2010
• Est. Priority Date: 10/12/2006
• Status: Active Grant

• Current Assignee: BAE Systems Information and Electronic Systems Integration Incorporated (BAE Systems Plc)
• Original Assignee: BAE Systems Information and Electronic Systems Integration Incorporated (BAE Systems Plc)
• Inventors: Khuu, Phong, Sadosuk, Greg, Gu, John, Hsu, Jessica, Ghanadan, Reza
• Granted Patent: US 7,656,851 B1
• Time in Patent Office: Days
• US Class Current: 370/310
• 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 8/24 Transfer of terminal data
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

Domains are formed in a mobile ad hoc network by exchanging topology update messages among neighboring nodes, each message including the node coverage of the originating node. The node having an optimum coverage of its neighbors becomes a domain lead (DL) node, and nodes within hearing distance or range of the DL node form a network domain. Each domain node, including the DL, selects a set of bridge nodes (BNs) that can link the domain node to nodes in corresponding neighboring domains. All domain lead nodes in the network exchange messages to inform one another of the nodes contained in their respective domains. A node in one domain seeking a route for a message destined to a node in another domain, may send a route discovery (RDisc) message to the DL node of the inquiring node'"'"'s domain. A responsive route resolution (RRes) message is returned to the inquiring node.

Claims

1-27. -27. (canceled)

28. A method of exchanging information among nodes in a mobile ad hoc network (MANET), comprising:

forming a number of logical domains in the network by periodically exchanging first topology update (TU1) messages within one or more groups of neighboring nodes, each TU1 message identifying (i) a node sending the TU1 message, and (ii) certain other nodes within a range of one hop from the node sending the TU1 message as a measure of node coverage of the sending node;

determining, within each group of neighboring nodes, a node having an optimum node coverage among the nodes of each group, and designating the determined node as a domain lead (DL) node of the group;

defining a domain as containing all nodes within a one hop range of the DL node;

associating with each node of a given domain including the DL node, a set of one or more bridge nodes (BN) for linking each node with other nodes in neighboring domains by

defining, at each node of the given domain, a first routing table for identifying other nodes that are in a range of one hop (H1 nodes),

periodically updating the H1 nodes identified in the first routing table according to the TU1 messages received at each node, and

selecting, at each node, members of the set of bridge nodes from among H1 nodes currently identified in the first routing table at each node, so that each member of the set of bridge nodes has an optimal node coverage of a different neighboring domain, thereby enabling each node of the given domain to link with other nodes in the neighboring domains through its associated set of bridge nodes the selection of which adapts to changes in network topology; and

periodically originating domain topology update (TUd) messages from each of a number of DL nodes in the network, and forwarding the TUd messages through the set of bridge nodes associated with each DL node originating a TUd message, including identifying in each TUd message those nodes contained in the domain of the originating DL node, thereby disseminating network node topology information via an architecture defined by the DL nodes and the sets of bridge nodes associated with each of the DL nodes in the network.

29. The method of claim 28, including discovering the presence of neighboring network nodes by an outside node desiring to enter the network, by transmitting topology update zero (TU0) messages from the outside node for identifying the outside node.

30. The method of claim 29, including exchanging the TU0 messages among a number of nodes desiring to enter the network, and identifying those nodes from which a TU0 message was received in the first routing table at each of the entering nodes.

36. The method of claim 28, wherein the TUd message forwarding step includes forwarding a given TUd message from the set of bridge nodes associated with the DL node originating the TUd message, to other DL nodes within a one hop or a two hop range of each bridge node.

37. The method of claim 36, including identifying in each TUd message an identification (ID) of the DL node originating the message, and the IDs of the set of bridge nodes selected by the originating DL node.

41. A method according to claim 28, wherein the domain lead node designating step is repeated at determined intervals for adapting to changes in network topology, including, at a given node of a defined domain;

designating the given node as a new DL node of the domain if the coverage of the given node surpasses the coverage of a currently designated DL node by a defined threshold;

broadcasting a domain lead announcement (DLA) message from the given node for announcing the given node as a new DL node; and

broadcasting a domain lead renouncement (DLR) message from the currently designated DL node to renounce its designation as a DL node, and including in the DLR message an acknowledgment of the new DL node.

31. (canceled)

32. A method of exchanging information among nodes in a mobile ad hoc network (MANET), comprising:

forming a number of logical domains in the network by periodically exchanging first topology update (TU1) messages within one or more groups of neighboring nodes, each TU1 message identifying (i) a node sending the TU1 message, and (ii) certain other nodes within a range of one hop from the node sending the TU1 message as a measure of node coverage of the sending node;

determining, within each group of neighboring nodes, a node having an optimum node coverage among the nodes of each group, and designating the determined node as a domain lead (DL) node of the group;

defining a domain as containing all nodes within a one hop range of the DL node;

associating with each node of a given domain including the DL node, a set of one or more bridge nodes (BN) for linking each node with other nodes in neighboring domains by selecting as members of the set of bridge nodes certain nodes of the given domain each of which has an optimal node coverage of a different neighboring domain, thereby enabling each node of the given domain to link with other nodes in the neighboring domains through its associated set of bridge nodes;

periodically originating domain topology update (TUd) messages from each of a number of DL nodes in the network, and forwarding the TUd messages through the set of bridge nodes associated with each DL node originating a TUd message, including identifying in each TUd message those nodes contained in the domain of the originating DL node, thereby disseminating network node topology information via an architecture defined by the DL nodes and the sets of bridge nodes in the network;

defining, at a given node of a defined domain, a first routing table for identifying nodes that are in a range of one hop (H1 nodes) from the given node; and

defining, at said given node, a second routing table for identifying nodes that are in a range of two hops (H2 nodes) from the given node, together with one or more H1 nodes with which the given node can link to acquire a route to each of the H2 nodes.

34. The method of claim 32, including receiving the TUd messages at a given domain lead (DL) node, and defining at the given DL node a third routing table for identifying nodes that are beyond a range of two hops (Hk nodes) from the DL node.

35. The method of claim 34, including entering for each node identified in the third routing table at the given DL node, (i) a destination node ID, (ii) a node in one hop range with which the DL node can link to acquire a path to the destination node, and (iii) a link performance (LP) metric for each of one or more routing paths to the destination node.

43. A method according to claim 32, including;

obtaining, at a given source node in the network, routing path information for a destination node not entered in a routing table at the source node; and

if more than one routing path is available for traffic between the source node and the destination node, acquiring a link performance metric for each path to the destination node, including;

counting a number of hops along the path;

determining a number of links along the path having a certain quality level; and

determining a number of links along the path having a certain congestion level.

44. The method of claim 32, including discovering a route for a message from a given source node in a first domain of the network and destined to a certain destination node in a second domain of the network, by;

transmitting a route discovery (RDisc) message from the source node to a DL node of the first domain, the RDisc message identifying the destination node; and

receiving, at the source node, a responsive route resolution (RRes) message from the DL node of the first domain, the RRes message identifying a link node in the first domain with which the source node can link to route the message to the destination node in the second domain.

45. The method of claim 44, wherein the discovering step includes determining, at the DL node of the first domain, if the destination node is entered in a routing table at the DL node of the first domain.

46. The method of claim 45, including, if the result of the determining step is affirmative, transmitting a responsive route resolution (RRes) message from the DL node of the first domain to the source node, the RRes message identifying a link node in the first domain through which the source node can reach the destination node.

47. The method of claim 45, including, if the result of the determining step is negative, forwarding the RDisc message from the DL node of the first domain to the set of bridge nodes associated with the DL node.

48. The method of claim 47, including determining if the destination node is entered in a routing table of one of the bridge nodes associated with the DL node of the first domain, and, if the result is affirmative, sending the RRes message from the one bridge node to the DL node for forwarding to the source node.

49. The method of claim 47, including, if the destination node is not entered in a routing table of one of the bridge nodes associated with the DL node of the first domain, forwarding the RDisc message from each of the associated bridge nodes to DL nodes within a range of two hops from the bridge nodes other than the DL node or nodes that forwarded the RDisc message.

50. The method of claim 49, including continuing to forward the RDisc message successively to DL nodes, and to sets of bridge nodes associated with the DL nodes to which the RDisc message is forwarded, until a defined maximum propagation count is reached or until all DL nodes in the network receive the message.

51. The method of claim 50, including determining redundant paths and eliminating loops in propagation of the RDisc message through the network, by appending to each RDisc message the identifications of one or more DL nodes in one hop range of each node that forwards the message, thereby defining covered domains and avoiding loops in the propagation path of the RDisc message.

33. (canceled)

38. (canceled)

39. (canceled)

40. A method of exchanging information among nodes in a mobile ad hoc network (MANET), comprising:

forming a number of logical domains in the network by periodically exchanging first topology update (TU1) messages within one or more groups of neighboring nodes each TU1 message identifying (i) a node sending the TU1 message, and (ii) certain other nodes within a range of one hop from the node sending the TU1 message as a measure of node coverage of the sending node;

determining, within each group of neighboring nodes a node having an optimum node coverage among the nodes of each group, and designating the determined node as a domain lead (DL) node of the group;

defining a domain as containing all nodes within a one hop range of the DL node;

associating with each node of a given domain including the DL node, a set of one or more bridge nodes (BN) for linking each node with other nodes in neighboring domains by selecting as members of the set of bridge nodes certain nodes of the given domain each of which has an optimal node coverage of a different neighboring domain, thereby enabling each node of the given domain to link with other nodes in the neighboring domains through its associated set of bridge nodes, and

periodically originating domain topology update (TUd) messages from each of a number of DL nodes in the network, and forwarding the TUd messages through the set of bridge nodes associated with each DL node originating a TUd message, including identifying in each TUd message those nodes contained in the domain of the originating DL node, thereby disseminating network node topology information via an architecture defined by the DL nodes and the sets of bridge nodes in the network.

wherein the TUd message forwarding step includes forwarding a given TUd message from a first bridge node associated with the DL node originating the TUd message to a second bridge node associated with the first bridge node, after appending to the TUd message an identification of one or more DL nodes in one hop range of the first bridge node, thereby defining covered domains and preventing redundant paths and loops in the message forwarding path;

forwarding the TUd message from the second bridge node to a DL node within a one hop or a two hop range of the second bridge node, other than DL nodes in the covered domains; and

continuing to forward the TUd message via successively associated bridge nodes until either a certain maximum propagation count is reached, or all DL nodes in the network are identified as covered in the message.

42. (canceled)

52. A method of exchanging information among nodes in a mobile ad hoc network (MANET) comprising:

forming a number of logical domains in the network by periodically exchanging first topology update (TU1) messages within one or more groups of neighboring nodes each TU1 message identifying (i) a node sending the TU1 message, and (ii) certain other nodes within a range of one hop from the node sending the TU1 message as a measure of node coverage of the sending node;

determining, within each group of neighboring nodes, a node having an optimum node coverage among the nodes of each group, and designating the determined node as a domain lead (DL) node of the group;

defining a domain as containing all nodes within a one hop range of the DL node;

associating with each node of a given domain including the DL node, a set of one or more bridge nodes (BN) for linking each node with other nodes in neighboring domains by selecting as members of the set of bridge nodes certain nodes of the given domain each of which has an optimal node coverage of a different neighboring domain, thereby enabling each node of the given domain to link with other nodes in the neighboring domains through its associated set of bridge nodes;

periodically originating domain topology update (TUd) messages from each of a number of DL nodes in the network, and forwarding the TUd messages through the set of bridge nodes associated with each DL node originating a TUd message, including identifying in each TUd message those nodes contained in the domain of the originating DL node, thereby disseminating network node topology information via an architecture defined by the DL nodes and the sets of bridge nodes in the network;

determining, at a given node of the network, a link state level (LSL) representing a transmission condition of each link from the given node to certain nodes in one hop range of the given node;

deriving, at the given node, a link performance (LP) metric for each of one or more routing paths from the given node to a desired destination node in two or more hop range of the given node, including identifying a target node in one hop range for each path, and deriving the LP metric for each path according to the LSL for each link along the path from the given node to the destination node;

selecting, at the given node, a certain path according to the derived LP for the path; and

originating a message to the destination node from the given node by sending the message from the given node to the target node identified for the selected path.

53. The method of claim 52, including deriving the LP metric for each routing path according to a number of hops over the path from the given node to the desired destination node.

54. The method of claim 52, including deriving the LP metric for each routing path according to a number of a number of links along the path having a certain quality level.

55. The method of claim 52, including deriving the LP metric for each routing path according to a number of links along the path having a certain congestion level.

56. The method of claim 52, including maintaining a first routing table at the given node, and entering in the first routing table identifications of the nodes in one hop range (H1 nodes) of the given node together with a link state level for the link to each H1 node.

57. The method of claim 56, including maintaining a second routing table at the given node, and entering in the second routing table (i) the nodes in two hop range (H2 nodes) of the given node, together with one or more H1 nodes with which the given node can link to acquire a path to each H2 node, and (ii) a link state level for each link of a selected path from the given node to a given H2 node.