Method for establishing and operating a mobile Ad-Hoc network

• US 7,969,914 B1
• Filed: 07/25/2008
• Issued: 06/28/2011
• Est. Priority Date: 07/25/2008
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Hall, Robert, Gerber, Matthew
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): HAMPTON, TARELL A
• Application Number:
  US12/220,598
• Time in Patent Office: 1,068 Days
• Field of Search: 370/254, 370/255, 370/256, 709/220, 709/221, 709/222
• US Class Current: 370/256
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• 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: Y02D 30/70 in wireless communication networks

Abstract

A method for creating an ad-hoc network that assembles a MANET inductively with no need for any node to request any information, needing only to hear information from an ad-hoc group of at least one node, to select its uplink relay node from the group. The resulting tree-structure network efficiently communicates information upstream to a root node and to all intermediate relay nodes. Downstream communication is enabled by having nodes remember node addresses of information packets arriving from respective downstream nodes.

Claims

1. A method for establishing an ad-hoc network comprising a plurality of nodes, where one of the nodes is pre-designated as a root node that constitutes a relay node and said root node periodically broadcasts a heartbeat message which includes an indirection number that indicates the root node being at a first level, said method comprising each non-root node n_j of the plurality of nodes, wherein n represents a non-root node, and j represent an integer value greater than 1, repetitively executing the steps of:

listening for heartbeat messages, to identify relay nodes of said network that are in neighborhood of said node n_j, wherein said heartbeat message further comprises a number representing how long has it been since node n_j had its connection to the root confirmed, and how far it has moved geographically since it had its connection to the root confirmed,

when node n_j is not yet connected to the network and it hears heartbeat messages,

selecting a relay node corresponding to one of the heard heartbeat messages as an uplink relay node of said node n_j, and

assigning to itself an indirection number that is one greater than the indirection number found in the heartbeat message of the selected uplink relay node;

when node n_j is not a relay node and a first preselected condition is met,

conditioning itself for repetitive broadcasting of a heartbeat message that includes the node'"'"'s own indirection number, thereby becoming a relay node;

when node n_j is a relay node, while a second preselected condition is not met, broadcasting a heartbeat message;

when node n_j is a relay node and said second preselected condition is met,

conditioning itself to stop broadcasting said heartbeat messages, thereby ceasing to be a relay node.

2. The method of claim 1 where node n_j also repetitively executes the following:

when it is a relay node with a selected node as its uplink node,

determining whether another node should be selected as the node'"'"'s uplink relay node, and if so, changing the selection of its uplink node and its corresponding indirection number, if different, based on indirection number of the newly selected node as its uplink relay node.

3. The method of claim 1 where node n_j also repetitively executes the following:

when it is connected to said network but it fails to hear a heartbeat message within a preselected time interval,

setting its own indirection number to a preselected number that is higher than any expected indirection number of a node that is connected to the network.

4. The method of claim 1 where the repetitive execution of said steps is periodic, with period T.

5. The method of claim 4 where the period T is not the same for all of said plurality of nodes.

6. A method for establishing an ad-hoc network comprising a plurality of nodes, where one of the nodes is pre-designated as a root node that constitutes a relay node and said root node periodically broadcasts a heartbeat message which includes an indirection number that indicates the root node being at a first level, said method comprising each non-root node n_j of the plurality of nodes, wherein n represents a non-root node, and j represent an integer value greater than 1, repetitively executing the steps of:

listening for heartbeat messages, to identify relay nodes of said network that are in neighborhood of said node n_j, wherein said heartbeat message comprises a number representing how long has it been since node n_j had its connection to the root confirmed, and how far it has moved geographically since it had its connection to the root confirmed,

when node n_j is not yet connected to the network and it hears heartbeat messages,

selecting a relay node corresponding to one of the heard heartbeat messages as an uplink relay node of said node n_j, and

assigning to itself an indirection number that is one greater than the indirection number found in the heartbeat message of the selected uplink relay node;

when node n_j is not a relay node and a first preselected condition is met,

conditioning itself for repetitive broadcasting of a heartbeat message that includes the node'"'"'s own indirection number, thereby becoming a relay node;

when node n_j is a relay node, while a second preselected condition is not met,

broadcasting a heartbeat message;

when node n_j is a relay node and said second preselected condition is met,

conditioning itself to stop broadcasting said heartbeat messages, thereby ceasing to be a relay node.

7. The method of claim 6 where node n_j also repetitively executes the following:

when it is a relay node with a selected node as its uplink node,

determining whether another node should be selected as the node'"'"'s uplink relay node, and if so, changing the selection of its uplink node and its corresponding indirection number, if different, based on indirection number of the newly selected node as its uplink relay node.

8. The method of claim 6 where node n_j also repetitively executes the following:

when it is connected to said network but it fails to hear a heartbeat message within a preselected time interval,

setting its own indirection number to a preselected number that is higher than any expected indirection number of a node that is connected to the network.

9. The method of claim 6 where the repetitive execution of said steps is periodic, with period T.

10. The method of claim 6 where said heartbeat message of node n_j contains no information about other nodes.

11. The method of claim 6 where said heartbeat message of node n_j comprises an address of node n_j and an indirection number that was assigned to node n_j.

12. The method of claim 6 where said heartbeat message further comprises information about geographical position of said node n_j.

13. The method of claim 12 where said geographical position is obtained by node n_j from a GPS receiver that is included in said node n_j.

14. The method of claim 6 where said heartbeat message further comprises a number representing how long node n_j has had a connection to the root.

15. The method of claim 6 further comprising the steps of:

generating an information packet that includes a source address corresponding to address of node n_j and a destination address of some other node in said network; and

transmitting the generated information packet to the uplink relay node of said node n_j.

16. The method of claim 6 further comprising the steps of:

generating an information packet that includes a source address corresponding to address of node n_j, a destination address of some other node in said network, and a relay target address that is the address of the uplink relay node of node n_j; and

transmitting the information packet.

17. The method of claim 6 further comprising the steps of:

generating an information packet that includes a source address corresponding to address of node n_j, a destination address of some other node in said network, and a relay target address field;

consulting a data array within node n_j which contains information entries, where each information entry comprises a source addresses and a relay address;

when the destination address of the generated information packet is found as a source address in an entry of said data array,

populating the relay target address field of the generated information packet with the relay address that is associated with the found source address, wherein the relay address is other than the uplink relay node of node n_j,

when the destination address of the generated information packet is not found as a source address in an entry of said data array,

populating said relay target address field of the generated information packet with the address of the uplink relay node of node n_j; and

transmitting the information packet.

18. The method of claim 17 further comprising the step of, when the destination address of the generated information packet is not found as a source address in an entry of said data array, creating a tuple comprising the source address and the relay address of the received information packet and storing the tuple in said data array.

19. The method of claim 6 further comprising the steps of:

receiving an information packet that includes a source address, an destination address of a node other than n_j, an relay address and a relay target destination address that is the address of node n_j;

consulting a data array within node which contains information entries, where each information entry comprises a source addresses and a relay address;

replacing the relay address field of the received information packet with the address of node n_j; and

when the destination address of the received information packet is found as a source address in an entry of said data array,

populating the relay target address field of the generated information packet with the relay address that is associated with the found source address, wherein the relay address is other than the uplink relay node of node n_j,

when the destination address of the generated information packet is not found as a source address in an entry of said data array,

populating said relay target address field of the generated information packet with the address of the uplink relay node of node n_j; and

transmitting the information packet.

20. The method of claim 19 further comprising the step of, when the destination address of the generated information packet is not found as a source address in an entry of said data array, creating a tuple comprising the source address and the relay address of the received information packet and storing the tuple in said data array.

21. The method of claim 6 where node n_j is constructed to broadcast at one a number of set power levels, and said heartbeat message further comprises an indication of the broadcast power level of said node n_j.