Topology aware manet for mobile networks

• US 20090059816A1
• Filed: 08/30/2007
• Published: 03/05/2009
• Est. Priority Date: 08/30/2007
• 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 C., Sadosuk, Gregory S., Hsu, Jessica Y., Gu, John A., Reza, Ghanadan
• Granted Patent: US 7,936,697 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/082 the condition being updates or upgrades of network functionality
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/16 Threshold monitoring
• 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: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2483 involving identification of individual flows
• CPC Class Codes: H04W 24/08 Testing, supervising or monitoring using real traffic
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/14 based on stability
• 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 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

Systems and methods provide adaptability in a mobile ad hoc network (MANET), based on an existing protocol, such as adaptive hybrid domain routing (AHDR). The systems and methods are especially suited for fast changing topologies that may change after a reactive route discovery has been completed.

Claims

1. A method for adaptively selecting a domain lead node from among a set of nodes in a mobile ad hoc network, the method comprising:

(a) establishing a link change threshold percentage;

(b) establishing a threshold delta link state level (LSL) increment value;

(c) calculating for each node in the network what percentage of links have changed by more than the threshold delta link state level (LSL) increment value;

(d) determining, at each node in the network, if the calculated percentage of changed links for the given node exceeds the link change percentage threshold;

(e) adaptively computing, at each node in the network, a node coverage value (NC) for each node from among the set of nodes in the network by adaptively adjusting a state value, so, for each node, downward, in response to satisfying said determining step (d); and

(f) selecting said domain lead node from among said set of nodes in said network based on a highest computed node coverage value (NC).

2. A method according to claim 1, wherein said determining step (d) is performed at successive update increments.

3. A method according to claim 1, wherein the link change threshold percentage is adjusted in accordance with a type of network.

5. A method for adaptively selecting a domain lead node from among a set of nodes in a mobile ad hoc network, the method comprising:

for a given node from among said set of nodes, computing a node coverage (NC) value by;

(a) adaptively adjusting a plurality of weight values for neighbor nodes seen by said given node, wherein said adaptive adjustment is based upon at least one of a current state of said neighbor nodes and a current link state level (LSL) of said neighbor nodes; and

(b) selecting said domain lead node from among said set of nodes based on a given node having a highest computed node coverage value (NC).

6. A method according to claim 5, wherein said node coverage value is adaptively computed as:

NC(A)=s₀*[w₀*n+(w₁*s₁, +w₂*s₂+w₃*s₃+* . . . +W_n*s_n)].

7. A method according to claim 6, wherein said weight values w₁-w_n are computed as:

w_n=(LSL*min(1, max(0,LSL-a)))+(z*max(0(LSL-(15-b))))

where

a=sets how many of the bottom LSLs get zeroed.

b=sets how many of the top LSLs get scaled up

z=weight of higher LSL and

s₁ . . . s_n=state of each neighbor node.

8. A method for adaptively selecting a domain lead node from among a set of nodes in a mobile ad hoc network, the method comprising:

for a given node from among said set of nodes, computing a node coverage (NC) value by;

(a) adaptively adjusting an adaptive weight w0 parameter in accordance with the number of neighbor nodes N seen by said given node; and

(b) selecting said domain lead node from among said set of nodes based on a given node having a highest computed node coverage value (NC).

4. A method according to claim 8, wherein the link change threshold percentage is adjusted in accordance with a type of network.

9. A method according to claim 8, wherein said node coverage value is adaptively computed as:

NC(A)=s₀*[w₀*n+(w₁*s₁+w₂*s₂+w₃*s₃+ . . . +w_n,*s_n)].

10. A method for computing the stability of a given link in a mobile ad hoc network (MANET), comprising:

computing a links stability indicator (LSI) metric as a function of the weighted moving average over time of a delta difference of the link congestion indicator (LCI), a delta difference of the link quality indicator (LQI) and a mobility state.

11. A method according to claim 10, wherein the link stability indicator (LSI) metric is computed as a function of the weighted moving average over time of (i) a delta difference of the link congestion indicator (Δ

LCI_WMA), (ii) a delta difference of the link quality indicator (Δ

LQI_WMA) and (iii) a mobility state m_i and (iv) one or more previous states of the link stability indicator (LSI).

12. A method according to claim 11, wherein the link stability indicator (LSI) metric is computed as:

LSI_ij(t)=(w₁Δ

LCI_WMA(t), w₂Δ

LQI_WMA(t), w₃m_i, w₄m_j)

where;

Δ

LCI_WMA(t)—

Weighted moving average of Δ

LCI

Δ

LQI_WMA(t)—

Weighted moving average of Δ

LQI

m_i=mobility_i=(#i'"'"'s good links)/(# I'"'"'s link changes).

13. A method according to claim 12, wherein the link stability indicator (LSI) metric LSI_ij(t) is computed as:

${\mathrm{LSI}}_{\mathrm{ij}}^{\mathrm{\prime <br><br>}}<br><br>\left(t\right)=\mathrm{\Delta <br><br>}<br><br><br><br>{\mathrm{LQI}}_{\mathrm{WMA}}+\mathrm{\Delta <br><br>}<br><br><br><br>{\mathrm{LCI}}_{\mathrm{WMA}}+\mathrm{\alpha <br><br>}<br><br><br><br>{\mathrm{LSI}}_{\mathrm{ij}}<br><br>\left(t-1\right)+\{\begin{array}{cc}\mathrm{\Delta <br><br>}<br><br><br><br>{\mathrm{LQI}}_t><br><br>0& {\mathrm{\beta <br><br>}}_1<br><br>\left(\mathrm{\Delta <br><br>}<br><br><br><br>{\mathrm{LQI}}_t\right)\\ \mathrm{\Delta <br><br>}<br><br><br><br>{\mathrm{LQI}}_t\le <br><br>0& {\mathrm{\beta <br><br>}}_2<br><br>\left(\mathrm{\Delta <br><br>}<br><br><br><br>{\mathrm{LQI}}_t\right)\end{array}$

wherein LSI′

_ij(t) is multiplied by the following mobility terms for respective nodes i and j to derive the link stability indicator metric

LSI_ij(t)=(1−

m_i)(1−

m_i)LSI′

_ij(t), m≦

1.

14. A method for sending updates in a mobile ad hoc network, comprising:

(a) sending a full update every n^th update period from each network node; and

(b) at update periods other than said n^th update period, each of said network nodes;

(i) identifying which nodes in the network have corresponding LSL values that have changed by more than a predetermined threshold amount from an immediately preceding update period; and

(ii) sending, as part of an update message, status information for the identified nodes.

15. A method for adaptively changing an update rate of a node in a mobile ad hoc network, comprising:

determining, in a present update period, by each node in the network, whether at least n nodes in the network have corresponding link state level (LSL) difference values that exceed a first predetermined threshold amount; and

increasing an update rate for each of said nodes who satisfy said determining step.

16. The method according to claim 15, where the LSL difference values is computed as the difference between an LSL value in said present update period and an LSL value in an immediately preceding update period.

17. A method for adaptively changing the route persistence via the timer of a given link based on the link quality and link degradation over a given period of time, the method comprising the steps of:

first determining if the link quality is less than a threshold value;

secondly determining if the link quality is decreasing at least a certain threshold rate;

upon satisfying said first and second determinations, decreasing the route persistence via the timer in the routing tables.

18. A method for discovering a route for a message from a source node in a first domain of the network and destined to a destination node in a second domain of the network, comprising:

(a) upon receiving a route error message at one of said source node or at an intermediate node in a predetermined path between said source node and said destination node, transmitting an alternate route discovery (ARDisc) message from one of the source node or intermediate node receiving said message to one of a corresponding domain lead node of the first domain or a corresponding domain lead node of an intermediate domain, wherein the ARDisc message identifies the destination node in said second domain;

(b) receiving the transmitted ARDisc message at one of the domain lead node of the first domain or the domain lead node of the intermediate domain;

(c) determining, at one of the domain lead node of the first domain or the intermediate domain lead node of the intermediate domain, if an identifier of the destination node is included in either an associated one hop or two hop routing table;

(d) if said determining step is satisfied, transmitting a alternative Route Resolution (ARRes) message from one of the domain lead node of the first domain to the source node or the domain lead node of the intermediate domain to the intermediate node, wherein the ARRes message identifies an alternative node in one of the source domain or intermediate domain to allow the source node or intermediate node to link with, to facilitate an alternative routing of the message to the destination node.

19. The method of claim 18, further comprising:

if said determining step is not satisfied, forwarding the ARDisc message from the DL node of the first domain or intermediate domain to bridge nodes selected by said DL node;

determining if the second node is entered in one of a one hop or two hop routing table of one of said bridge nodes;

if said determining step is satisfied, sending the ARRes message from the bridge node including said second node in one of said one hop or two hop routing table to the source node or intermediate node; and

if said determining step is not satisfied, forwarding the ARDisc message from each of said bridge nodes to DL nodes within a range of two hops from said bridge nodes other than a DL node or a node that forwarded the ARDisc message.

20. The method of claim 19, including forwarding the ARDisc message to the destination node from either a DL node or a bridge node which has the destination node entered in a routing table of the forwarding DL or bridge node.

21. A method for discovering a route for data originating from a first node in a first domain of the network and destined to a second node in a second domain of the network, comprising:

(a) receiving data at a network node situated as an intermediate node in said route discovery between said source and destination nodes;

(b) determining by said intermediate node, that an intended forwarding node in said route discovery is not available to receive said data;

(c) temporarily storing said data at said intermediate node;

(d) identifying an alternative forwarding node in an alternate route discovery for forwarding said data to;

(e) forwarding said data to said alternative forwarding node.

22. A method for selecting and organizing information for a Link Performance metric in support of quality of service (QoS) requirements, the method comprising:

(a) determining a congestion level metric to each hop in an n-hop route based on a link congestion indicator (LCI) metric;

(b) determining a quality level metric to each of said hops in an n-hop route based on a link quality indicator (LQI) metric;

(c) accumulating and incrementing the quality and congestion level metrics assigned to each hop in said an n-hop route; and

(d) constructing a hop k link performance metric for hop k routing decisions from said accumulated and incremented indicators.