Internet-oriented ad-hoc network

• US 7,668,146 B2
• Filed: 12/20/2004
• Issued: 02/23/2010
• Est. Priority Date: 12/20/2004
• Status: Active Grant

• Current Assignee: Connectivities, LLC
• Original Assignee: Connectivities, LLC
• Inventors: Metz, Reinhard, Hara, Jacques, Levendel, Isaac
• Primary Examiner(s): Corsaro; Nick
• Assistant Examiner(s): Ajayi; Joel
• Application Number:
  US11/014,700
• Publication Number:
  US 20060133328A1
• Time in Patent Office: 1,891 Days
• Field of Search: None
• US Class Current: 370/338
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user
• CPC Class Codes: H04W 88/16 Gateway arrangements
• CPC Class Codes: H04W 88/18 Service support devices; Network management devices

Abstract

A hierarchical directional internet-oriented ad-hoc network, defined by a software infrastructure, is composed of fixed gateway nodes and a plurality of wireless nodes, which may be fixed or mobile, and which may act as subscribers, routers, or both. The infrastructure hierarchy is defined by the hop count of each node (distance of that node to a fixed gateway node). The software infrastructure includes two tables associated with each node in the network: the upstream routing table which provides shortest routes to fixed gateway nodes through upstream neighbors, and the downstream routing table which provides shortest routes to subscribers through downstream neighbors. These two tables are used by routing algorithms. A peer table can also be used for alternate routes. The maintenance of the aforementioned tables is performed by autonomous algorithms operating locally on each node by receiving and processing signals from their neighbors.

Claims

1. An Internet-oriented mobile ad-hoc network comprising:

at least one fixed gateway node, the at least one fixed gateway node being in communication with the Internet; and

a plurality of wireless nodes communicatively accessible downstream from the at least one fixed gateway node through any number of intermediate nodes and being able to communicate upstream with the at least one fixed gateway node through any number of intermediate nodes, each of the wireless nodes including wireless transceivers, each of the wireless nodes further including, for each of the at least one fixed gateway node, an upstream routing table (URT), a peer table (PT), a downstream neighborhood table (DNT) and a downstream routing table (DRT), each of the wireless nodes being configured to use the associated tables to make routing decisions, some of the wireless nodes being mobile wireless nodes, some of the mobile wireless nodes being configured to act as a relay for other wireless nodes that cannot directly access the at least one fixed gateway node;

wherein the URT of a wireless node Ni is updated independently by the wireless node Ni and lists each upstream neighboring node that is closer by one hop, to a particular fixed gateway node than is the node Ni, together with the hop count from the upstream neighboring node to the particular fixed gateway;

wherein the PT of the wireless node Ni is updated independently by the wireless node Ni and lists each peer node, defined as a neighboring node that has equal distance, as measured by hop count, to a particular fixed gateway node as the wireless node Ni, together with an associated hop count to the particular fixed gateway;

wherein the DNT of the wireless node Ni is undated independently by the wireless node Ni and lists each neighboring downstream node that is one hope count further away from a particular fixed gateway node than the node Ni, together with the hop count of the downstream neighboring node to the particular fixed gateway node;

wherein the DRT of the wireless node Ni is undated independently by the wireless node Ni and lists each downstream node Nk, as defined by a node that can communicate with the node Ni and is further away from the node Ni, as measured by hop counts of the nodes Ni and Nk to a particular fixed gateway node, together with the hop count of the downstream node Nk to the node Ni;

wherein each node periodically broadcasts a trigger message that comprises a node identification and hop count corresponding to a particular node to inform neighboring nodes that the particular node is present;

wherein each node independently and periodically receives and processes control signals from neighboring nodes; and

wherein each node updates the tables within itself and each node communicates changes to neighboring nodes.

2. The network of claim 1, wherein the at least one fixed gateway node is directly connected to the Internet.

3. The network of claim 1, wherein the at least one fixed gateway node includes a plurality of fixed gateway nodes, for every fixed gateway Gj, the wireless node Ni can communicate with, wireless node Ni has a different set of tables, URTij, PTij, DNTij and DRTij;

wherein the URTij of the wireless node Ni with respect to the fixed gateway Gj lists each upstream neighboring node that is closer by one hop to the fixed gateway Gj than the node Ni, together with the hop count of the upstream node to the fixed gateway Gj;

the PTij of the wireless node Ni with respect to the fixed gateway Gj lists each peer node, as defined as a neighboring node that has equal distance, as measured by a hop count, to the fixed gateway Gj as Ni, together with an associated hop count to the fixed gateway Gj;

the DNTij of the wireless node Ni with respect to the fixed gateway Gj lists each downstream neighboring node that is further away from the fixed gateway Gj than Ni, together with the hop count of the downstream node to the fixed gateway Gj; and

the DRTij of the wireless node Ni with respect to the fixed gateway Gj lists each downstream node, as defined by a node that is reachable from Ni and is further away, as measured by a hop count, from the fixed gateway Gj than Ni, together with the hop count of the downstream node to the fixed gateway Gj;

wherein the wireless node Ni independently receives and processes control signals from neighboring nodes; and

wherein the wireless node Ni updates the tables within itself and each node communicates changes to neighboring nodes.

4. The network of claim 1, wherein the at least one fixed gateway node is connected to the Internet via a central node.

5. The network of claim 4, wherein the central node is connected to at least one other fixed gateway node.

6. The network of claim 1, wherein each of the wireless nodes is configured to act as a relay for other wireless nodes that cannot directly access the at least one fixed gateway node.

7. The network of claim 1, wherein all of the wireless nodes are mobile nodes.

8. The network of claim 1, wherein some of the wireless nodes are mobile nodes and other wireless nodes are fixed nodes.

9. The network of claim 1, wherein the DRTs are indexed by destination node.

10. The network of claim 1, wherein the DRTs are indexed by downstream neighbor.

11. The network of claim 1, wherein the DRTs are indexed by both destination node and downstream neighbor.

12. A method for Internet-oriented mobile ad-hoc network upon a failure, the Internet-oriented mobile ad-hoc network including a multiplicity of mobile wireless nodes and at least one fixed node acting as a gateway to other networks outside the Internet-oriented mobile ad-hoc network, the method comprising the steps of:

receiving a packet by a mobile wireless node Ni, wherein the network has a plurality of wireless nodes, Ni, wherein each mobile wireless node Ni in the network, for each of the at least one fixed gateway node Gk, includes an upstream routing table (URT), a peer table (PT), a downstream neighboring table (DNT) and a downstream routing table (DRT), wherein the URT is updated independently by the wireless node Ni and lists each upstream neighboring node that is closer by one hop to a particular fixed gateway node than the node Ni, together with the hop count of the upstream node to the particular fixed gateway, wherein the PT is updated independently by the wireless node Ni and lists each peer node, as defined as a neighboring node that has equal distance, as measured by hop count, to a particular fixed gateway node as the node Ni, together with an associated hop count to the particular fixed gateway, wherein the DNT is updated independently by the wireless node Ni and lists each neighboring downstream node that is further away from a particular fixed gateway node than the node Ni, together with the hop count of the downstream node to the particular fixed gateway; and

wherein the DRT is updated independently by the wireless node Ni and lists each downstream node, as defined by a node that is reachable from the node Ni and is further away, as measured by a hop count, from a particular fixed gateway node than the node Ni, together with the hop count of the downstream node;

receiving a trigger message by the receiving mobile wireless node, wherein the trigger message is generated by a neighboring node; and

updating the tables of the receiving mobile wireless node by the receiving mobile wireless node and thus reorganizing the network.

13. The method of claim 12, further comprising:

generating a trigger message D1 when the packet cannot be sent successfully from the wireless node Ni to a downstream neighbor Nk in the DNT of the wireless node Ni;

processing the generated trigger message D1 by removing the downstream neighbor Nk to which the packet could not be sent from the DNT of the wireless node Ni;

updating the DRT of the wireless node Ni;

computing a downstream cluster by calculating a union of columns of the DRT and adding the wireless node Ni and its hop count 0; and

sending a trigger message T4 including the downstream cluster to upstream neighbors of the wireless node Ni.

14. The method of claim 13, further comprising:

generating a trigger message D2 upon the occurrence of the event when the packet cannot be sent successfully from the wireless node Ni to a destination node Nd in the DRT of wireless node Ni;

processing the generated trigger message D2 by computing a downstream cluster, the computing comprising calculating a union of columns of the DRT and adding the wireless node Ni and its hop count 0; and

sending a trigger message T4 including the downstream cluster to upstream neighbors of the wireless node Ni.

15. The method of claim 12, further comprising:

generating a trigger message U1 when the packet cannot be sent successfully from the wireless node Ni to an upstream neighbor Nk in the URT of the wireless node Ni;

processing the generated trigger message U1 by removing the upstream neighbor Nk to which the packet could not be sent from the URT of the wireless node Ni;

if the URT is not empty, ending the process; and

if the URT is empty;

making the PT of wireless node Ni the new URT of the receiving wireless node Ni;

making the DNT of wireless node Ni the new PT of the receiving wireless node Ni;

emptying the DNT and DRT of wireless node Ni;

if the new URT of wireless node Ni is empty, setting a hop count of wireless node Ni to infinity and ending the process; and

if the new URT of wireless node Ni is not empty;

computing a downstream cluster by calculating a union of columns of the DRT and adding wireless node Ni and its hop count 0; and

sending a trigger message T4 including the downstream cluster to upstream neighbors of wireless node Ni.

16. The method of claim 13, further comprising:

in response to wireless node Ni receiving the trigger message T4, modifying the trigger message T4 by increasing all hop counts of nodes in the trigger message T4 by one;

replacing the Nk column of the DRT of wireless node Ni by the modified T4; and

if the hop count of the node Ni is zero, ending the process; and

if the hop count of the node Ni is not zero;

computing a downstream cluster by calculating a union of columns of the DRT and adding wireless node Ni and its hop count 0; and

sending a trigger message T4 including the downstream cluster to upstream neighbors of wireless node Ni.

17. The method of claim 12, further comprising:

periodically broadcasting a trigger message T5 by each node, each trigger message T5 comprising a node ID and hop count corresponding to a particular node to inform neighboring nodes that the particular node is present;

generating a trigger message T5 upon predetermined changes;

receiving at receiving wireless node Ni the trigger message T5 sent by a sending node Nk;

comparing the hop count of the receiving wireless node Ni with the hop count of the sending node Nk;

if a difference between the hop count of the receiving wireless node Ni and the hop count of the sending node Nk is greater than 2;

removing Nk from the neighborhood of Ni if Nk is in the neighborhood;

moving and adding all the nodes of the URT and PT of node Ni into the DNT of node Ni;

moving Nk into the URT of Ni;

resetting the hop count of Ni to the hop count of Nk augmented by 1; and

sending to all the neighbors of Ni a trigger message T5 composed of Ni and its hop count;

if a difference between the hop count of the receiving wireless node Ni and the hop count of the sending node Nk is equal to 2;

removing Nk from the neighborhood of Ni if Nk is in the neighborhood;

moving and adding all the nodes of the PT of node Ni into the DNT of node Ni, then moving all the nodes of the URT of Ni to the PT of Ni;

moving Nk into the URT of Ni;

resetting the hop count of Ni to the hop count of Nk augmented by 1; and

sending to all the neighbors of Ni a trigger message T5 composed of Ni and its hop count

if a difference between the hop count of the receiving wireless node Ni and the hop count of the sending node Nk is equal to 1;

if Nk is in the URT of Ni, ending the process; and

if Nk is not in the URT of Ni;

if Nk is in the neighborhood of Ni, removing Nk from the neighborhood of Ni;

adding Nk to the URT of Ni;

computing a trigger message T4 by performing a union of columns of the DRT of Ni and adding the node Ni with a hop count of zero; and

sending the trigger message T4 to all the nodes in the URT of Ni if Nk was in the DNT of Ni, otherwise sending the trigger message T4 to Nk only;

if a difference between the hop count of the sending wireless node Nk and the hop count of the receiving node Ni is greater than or equal to 1;

if node Nk is in the DNT of node Ni, setting the hop count of node Nk to the hop count of Ni plus 1; and

if node Nk is not in the DNT of node N;

if Nk is in the Neighborhood of Ni, removing Nk from the neighborhood table of node Ni;

entering Nk into the DNT of Ni

setting the hop count of node Nk to the hop count of Ni plus 1;

if the URT of node Ni is empty, then moving the nodes in PT of Ni into URT; and

moving the nodes in DNT of Ni into PT;

if the URT of node Ni is not empty;

computing a trigger message T4 by performing the union of the columns of the DRT of Ni and adding node Ni with hop count zero; and

sending the trigger message T4 to all the nodes in the URT of node Ni;

setting the hop count of Ni to infinity if URT of Ni is empty;

sending a trigger message T5 (Ni and its hop count) to Nk;

if the hop count of the sending wireless node Nk and the hop count of the receiving node Ni are equal;

if Nk is in the PT of Ni, ending the process; and

if Nk is not in the PT of Ni;

if Nk is in the Neighborhood of Ni, removing Nk out of the neighborhood of Ni;

entering node Nk into the PT of Ni;

setting the hop count of Nk to the hop count of Ni;

if the URT of node Ni is empty, then

moving the nodes in PT of Ni into URT, and

moving the nodes in DNT of node Ni into PT;

if URT of node Ni is empty, setting the hop count of Ni to infinity;

and

if the URT of Ni is not empty, then;

Computing a trigger message T4 by performing the unions of the columns of the DRT of Ni and adding Ni with hop count zero;

Sending the trigger message T4 to all the nodes in the URT of Ni;

moving to process next signal.

18. The method of claim 12, wherein receiving a packet by a mobile wireless node Ni comprises receiving a packet by a mobile wireless node Ni that has multiple simultaneous associations with fixed gateway nodes, thereby providing additional communication paths from every node Ni to fixed gateways, eliminating the need for active handover dialogue between node Ni and fixed gateways and Preventing dropped communication lines.

19. The method of claim 12, for comprising:

extracting from the packet a final destination address;

wherein if the final destination address is Ni, then halting further processing of the packet, and otherwise;

if the final destination address of the packet is not inside the Internet-oriented mobile ad-hoc network and Ni is a fixed gateway, then sending the packet to the final destination;

if the final destination address of the packet is not inside the Internet-oriented mobile ad-hoc network and Ni is not a fixed gateway, then sending the packet to a destination in a URTik of Ni towards fixed Gateway Gk, and;

if there is a failure, then generate a trigger message U1k;

if the final destination address of the packet is inside the Internet-oriented mobile ad-hoc network and it is not in any DNTij or a DRTij of Ni, then;

if Ni is the fixed gateway, then halting further processing, and

if Ni is not the fixed gateway, sending the packet to a destination in a URTik of Ni towards fixed Gateway Gk; and

if there is a failure, then generate a trigger message U1k;

if the final destination address of the packet is inside the Internet-oriented mobile ad-hoc network and the final destination address is in a DNTij or in a DRTij of node Ni, then sending the packet to that destination and

if there is a failure, then generating a trigger message D1j, if the destination is in DNTij, or a trigger message D2j, if the destination is in DRTij.

20. The method of claim 18, wherein for each particular fixed Gateway in the potential multiplicity of fixed Gateways, at every node Ni that can communicate with that particular fixed Gateway, the multiplicity of trigger messages generated with respect to any particular fixed Gateway Gj is processed independently of the multiplicity of trigger messages generated with respect to any other fixed Gateway Gk.