Neural network-based mobility management for healing mobile ad hoc radio networks

• US 7,848,262 B2
• Filed: 06/26/2006
• Issued: 12/07/2010
• Est. Priority Date: 06/26/2006
• Status: Expired due to Fees

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: El-Damhougy, Hesham
• Primary Examiner(s): Pérez-Gutiérrez; Rafael
• Assistant Examiner(s): Batista; Marcos
• Application Number:
  US11/426,428
• Publication Number:
  US 20070299947A1
• Time in Patent Office: 1,625 Days
• Field of Search: 370/310, 701/59, 706/15
• US Class Current: 370/255
• CPC Class Codes: H04B 7/18504 Aircraft used as relay or high altitude atmospheric platform
• CPC Class Codes: H04B 7/2606 Arrangements for base station coverage control, e.g. by using relays in tunnels
• CPC Class Codes: H04W 76/19 Connection re-establishment
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A self healing ad hoc communications network and method of training for and healing the network. The network includes wireless devices or nodes that include a neural network element and the ad hoc network operates as a neural network. Some of the nodes are designated as healing nodes that are identified during network training and are strategically located in the network coverage area. Whenever one group of nodes loses connection with another a healing node may reposition itself to reconnect the two groups. Thus, the network can maintain connectivity without constraining node movement.

Claims

1. A method of managing an ad hoc communications network, said method comprising the steps of:

a) locating a plurality of nodes within a coverage area;

b) selecting at least one of said plurality of nodes within at least one group said plurality of nodes as a healing node, each of said healing node being relocatable within a corresponding said group;

c) locating each said healing node at a location;

d) training said healing nodes to selectively reconnect to at least one other said group whenever a connection to other said nodes of at least one other said group is lost;

wherein the training is unsupervised and recursively constructs a map of healing nodes (Φ

) and ψ

in Euclidean (R³) space for the coverage area and has the form Φ

;

R³→

D⊂

R³ and ψ

;

D→

R³; and

e) relocating each said healing node at said location.

2. A method as in claim 1, wherein each said group is a cluster of said nodes and at least one said healing node is identified for each said cluster.

3. A method as in claim 1, wherein said ad hoc communications network is partitioned, each said group is a partition of said ad hoc communications network and at least one said healing node is identified for each said partition.

4. A method as in claim 1, wherein the step (c) of locating said healing nodes places each identified said healing node at said location selected from a set of identified said healing node said locations.

5. A method as in claim 4, wherein the identified said set is a subset of said node locations.

6. A method as in claim 1, after the step (e) of relocating said healing nodes further comprises the steps of:

f) monitoring connection within each said group to at least one other said group; and

upon loss of connection;

g) identifying a healing node to reconnect a disconnected group, the identified said healing node being selected from a set of previously identified said healing nodes; and

h) relocating the identified said healing node to reconnect said disconnected group.

7. A method as in claim 6, wherein the step (g) of identifying said healing node comprises the steps of:

i) selecting a said node from said nodes in said disconnected group;

ii) identifying a winner said node from said set of previously identified said healing nodes, said winner node being the node from said set closest to the selected said node;

iii) determining whether the selected said node is within a selected maximum distance from said winner node; and

iv) determining whether said disconnected group is reconnected.

8. A method as in claim 7, wherein whenever in step (iii) the winner node is beyond said selected maximum distance, said method further comprises creating a new said node and designating the new said node as said healing node.

9. A method as in claim 7, wherein whenever in step (iv) said disconnected group is reconnected, said method further comprises the steps of:

v) checking said network to determine whether it is partitioned, and whenever said network is partitioned;

vi) updating the position and an age of said winner node and neighbors of said winner node;

vii) determining whether other said nodes of the set of said nodes remain; and

whenever other said nodes remain; and

viii) returning to step (i) and selecting a remaining one of said set of said nodes.

10. A method as in claim 9, wherein whenever in step (vii) all of the set of said nodes have been selected, said method further comprises the steps of:

vi-1) determining whether said network is connected; and

vi-2) pruning said healing nodes from a group of designated said healing nodes.

11. A method as in claim 10, wherein whenever in step (vi-1) said network is partitioned, said method further comprises indicating that healing has failed.

12. A method of training healing nodes in an ad hoc communications network, said method comprising the steps of:

a) selecting a node location from a plurality of node locations in an ad hoc communications network;

b) identifying a winner node as being closest of the remaining ones of said plurality of node locations;

c) determining whether a node at the selected said node location is within a selected maximum distance from said winner node; and

d) determining whether said ad hoc communications network is connected; and

wherein the training is unsupervised and recursively constructs a map of healing nodes (Φ

) and ψ

in Euclidean (R³) space for the coverage area and has the form (Φ

);

R³→

D⊂

R³ and ψ

;

D→

R³.

13. A method as in claim 12, wherein whenever in step (c) the winner node is beyond said selected maximum distance, said method further comprises the steps of:

c1) selecting a potential healing node;

c2) determining whether selected said potential healing node is previously assigned as a healing node; and

c3) designating selected said potential healing node as said healing node.

14. A method as in claim 12, wherein whenever in step (d) said ad hoc communications network is partitioned, said method further comprises the steps of:

e) updating the position of said winner node;

f) determining whether other ones of said plurality of node locations remain for selection as healing nodes; and

g) returning to step (a) and selecting another remaining one of said plurality of node locations.

15. A method as in claim 14, wherein whenever in step (f) all of said plurality of node locations have been selected, said method further comprises the steps of:

f1) determining whether said ad hoc communications network is connected; and

f2) pruning healing nodes from a group of designated said healing nodes.

16. A method as in claim 15, wherein whenever in step (f1) said ad hoc communications network is partitioned, said method further comprises indicating that healing has failed.

17. A method of managing nodes in an ad hoc communications network, said method comprising the steps of:

a) training communications nodes off-line for a selected coverage area, said ad hoc communications network including a plurality of mobile nodes initially located at selected locations in said coverage area and grouped into a plurality of groups, at least one of said plurality of nodes being selected as healing nodes within each group of said plurality of nodes, each of said healing nodes being relocatable within a corresponding said group;

b) deploying the trained said nodes in an ad hoc communications network;

c) monitoring, within each said group, connection to at least one other said group; and

upon loss of connection,

d) relocating a corresponding said healing node to reconnect each said group to the at least one other said group, wherein the healing node is trained unsupervised to reconnect by recursively constructing a map of healing nodes (Φ

) and ψ

in Euclidean (R³) space for the coverage area and has the form Φ

;

R³→

D⊂

R³ and ψ

;

D→

R³.

18. A method as in claim 17, wherein unsupervised training said healing node comprises the steps of:

i) selecting at least one said node from said trained nodes in the disconnected said group;

ii) identifying a winner node from said trained nodes, said winner node being the trained said node closest to the selected said node;

iii) determining whether the selected said node is within a selected maximum distance from said winner node; and

iv) determining whether the disconnected said group is reconnected.

19. A method as in claim 18, wherein whenever in step (iii) the winner node is beyond said selected maximum distance, said method further comprises creating a new node and designating the created said new node as said healing node.

20. A method as in claim 18, wherein whenever in step (iv) said disconnected group is reconnected, said network is checked to determine whether it is partitioned, and whenever said network is partitioned, said method further comprises the steps of:

v) updating the position and the age of said winner node and neighbors of said winner node;

vi) determining whether any of said trained nodes remain; and

whenever said trained nodes remain,

vii) returning to step (i) and selecting at least one said node from the remaining said trained nodes.

21. A method as in claim 20, wherein whenever in step (vi) all of said trained nodes have been selected, said method further comprises the steps of:

vi-1) determining whether said network is connected; and

vi-2) pruning healing nodes from a group of designated said healing nodes.

22. A method as in claim 21, wherein whenever in step (vi-1) said network is partitioned, said method further comprises indicating that healing has failed.

23. A node trainable as a healing node for use in an ad hoc communications network comprising:

off line training means for receiving off-line training for a selected coverage area in an ad hoc communications network of a plurality of mobile nodes grouped into a plurality of groups;

transportation means for locating said healing node to a preselected location, responsive to said training;

means for monitoring connection of a group of ad hoc communications network nodes to at least one other group; and

means for determining a location to reconnect said group to said at least other group, responsive to said training, said transportation means further being for relocating said healing node to the reconnect said location, wherein the means for determining unsupervised and recursively constructs a map of healing nodes (Φ

) and ψ

in Euclidean (R³) space for the coverage area and has the form Φ

;

R³→

D ⊂

R³ and ψ

;

D→

R³.

24. A node as in claim 23, wherein said node is coupled to an unmanned ground vehicle.

25. A node as in claim 23, wherein said node is coupled to an unmanned air vehicle.