Swarm autonomous routing algorithm for mobile ad hoc network communications

• US 7,957,355 B1
• Filed: 05/30/2006
• Issued: 06/07/2011
• Est. Priority Date: 05/27/2005
• Status: Active Grant

• Current Assignee: Bluetronix Incorporated
• Original Assignee: Bluetronix Incorporated
• Inventors: Heiferling, Mark J., Kelm, Jonathon C.
• Primary Examiner(s): CAI, WAYNE HUU
• Application Number:
  US11/421,067
• Time in Patent Office: 1,834 Days
• Field of Search: 370/338, 370/328, 370/351, 370/392, 370/395.31
• US Class Current: 370/338
• CPC Class Codes: H04B 7/2606 Arrangements for base station coverage control, e.g. by using relays in tunnels
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

A Swarm Autonomous Routing Algorithm (SARA) is performed by simple communication node devices for node to node communications in a network, especially a Mobile Ad hoc NETwork (MANET). Each node maintains a table of pheromone values for known neighbor nodes. Pheromone values are dynamic for adapting to a dynamic arrangement of nodes, and are updated either passively or actively. Routing tables are not used. When a node receives a packet, it uses the pheromone table to simply determine whether or not to forward (rebroadcast) the packet to a neighbor node, and if possible, determines and indicates the best neighbor node for next forwarding the packet. Destination Zone Routing (DZR) and Swarm Location Service (SLS) are alternative enhancements of SARA that can be used for more efficient routing when nodes are location aware/knowledgeable. SLS may also be used to improve routing algorithms other than SARA.

Claims

1. A method for relaying communications among a plurality of communication nodes in a mobile ad hoc network (MANET), wherein each node is a device that has computing and wireless communication broadcasting and receiving capabilities plus a broadcastable identifier, wherein wireless communication comprises broadcasting a packet containing a message portion, and wherein the method is implemented in each node such that each node considers itself to be a current node in the context of the method steps it carries out;

the method in the current node comprising the steps of;

identifying a set of neighbor nodes for the current node by determining whether a node qualifies by being within wireless communication range;

without knowledge of a route to a packet'"'"'s ultimate destination, broadcasting any packet originated at the current node, or re-broadcasting any received packet to relay it, by randomly selecting no more than one of the neighbor nodes to have its identifier set in the packet as a designated receiver node that should re-broadcast the packet;

and

examining received packets to learn the designated receiver node identifier if one is contained therein, then using the following steps to guide re-broadcasting actions;

if the current node is the designated receiver node, then re-broadcasting the packet;

and

if the current node is not the designated receiver node, then only re-broadcasting the packet according to a predetermined non-designated receiver re-broadcast probability.

2. The method of claim 1, further comprising the step of:

additionally limiting identification of neighbor nodes to determining whether nodes also have the current node within their radio range, thereby assuring that a neighbor node has a bi-directional communication link with the current node.

3. A routing table independent mobile ad hoc network (MANET) communication method for relaying communications among a plurality of communication nodes, wherein each node is a device that has computing and wireless communication broadcasting and receiving capabilities plus a broadcastable identifier, wherein wireless communication comprises broadcasting a packet containing a message portion, a message source node S identifier, and a message destination node D identifier;

and wherein the method is implemented in each node such that each node considers itself to be a current node in the context of the method steps it carries out;

the method in the current node comprising the steps of;

for every broadcast packet received by the current node, processing the received packet for passively learning about other nodes;

thereby minimizing broadcasting by avoiding pro-active learning through exchange of node information protocol packets;

wherein packets can contain a sending node identifier and a designated receiver node identifier;

including the current node'"'"'s identifier as the sending node in every packet that is broadcast;

establishing a receiving (RX) pheromone and a transmission (TX) pheromone for each other node from which the current node receives a packet, and associating the other node'"'"'s identifier with its respective RX and TX pheromones, wherein receiving from an other node means that the receiving node directly received, in a single hop, a packet transmitted by the other node;

defining a neighbor node as being an other node that is associated with RX and TX pheromones that both have values above predetermined minimum values;

maintaining a table of neighbor node identifiers with respective RX and TX pheromone values, and continuously updating the table by;

defining the RX pheromone as an indicator of whether the associated node can receive packets from the current node;

defining the TX pheromone as an indicator of whether the associated node can transmit packets to the current node;

increasing the value of an other node'"'"'s TX pheromone whenever a packet is received from the respective other node;

decreasing the value of each established TX pheromone whenever a predetermined amount of time elapses from the most recent value modification of the subject TX pheromone;

increasing the value of an other node'"'"'s RX pheromone whenever a packet is received from the respective other node and the received packet is a re-broadcast of a packet just previously broadcast by the current node;

decreasing the value of each established RX pheromone whenever a predetermined amount of time elapses from the most recent value modification of the subject RX pheromone; and

broadcasting any packet originated at the current node or re-broadcasting any received packet to relay it, by selecting no more than one node to be identified in the packet as the designated receiver node, selected from among the nodes currently defined as neighbor nodes;

and

examining received packets to learn the designated receiver node identifier if one is contained therein, then using the following steps to guide re-broadcasting actions;

if the current node is the designated receiver node, then re-broadcasting the packet; and

if the current node is not the designated receiver node, then only re-broadcasting the packet according to a predetermined non-designated receiver re-broadcast probability.

4. The MANET communication method of claim 3, further comprising the step of:

no longer saving an other node'"'"'s identifier and associated pheromone values when the other node'"'"'s RX and TX pheromone values both fall below predetermined minimum values.

5. The MANET communication method of claim 3, further comprising the steps of:

maintaining a partial path list in the packets, the path list being at least the most recent portion of a sequential listing of identifiers for the nodes through which the packet has passed in sequence; and

when learning from a packet, increasing the TX pheromone for any node that sequentially immediately precedes the current node anywhere in the path list; and

increasing the RX pheromone for any node that sequentially immediately follows the current node anywhere in the path list.

6. The MANET communication method of claim 3, further comprising the step of:

exclusively upon receiving a communication packet that identifies the current node as the message destination node D,

changing the packet contents to indicate the current node as a new message source node S′

, and the original message source node S as a new message destination node D′

; and

broadcasting the so-changed message packet according to the method as claimed,

thereby discovering a new path back to the message source node S, for acknowledging receipt of the message packet by the original message destination node D.

7. The MANET communication method of claim 3, wherein after broadcasting a particular communications packet, the method further comprises the steps of:

during a predetermined amount of retry time, checking received packets for matches to the particular communications packet;

if no match is received by the end of the retry time, then retrying broadcasting of the particular communications packet without changing the designated receiver node; and

no longer checking received packets for matches to the particular communications packet once a match has been detected, or once a maximum number of retries has been achieved.

8. The MANET communication method of claim 3, further comprising the step of:

selecting a one of the neighbor nodes that has the best quality communication link with the current node as determined by the highest neighbor pheromone values.

9. The MANET communication method of claim 3, further comprising the step of:

randomly selecting the one of the neighbor nodes.

10. The MANET communication method of claim 3, further comprising the step of:

selecting a null value for the designated receiver node identifier when a node cannot be found that meets predetermined selection criteria.

11. The MANET communication method of claim 3, wherein a geographic location and broadcast range of other nodes can be known by the current node, the method further comprising the steps of:

adding a goodness time delay to a random time delay for re-broadcasting; and

calculating the goodness time delay by conditionally selecting one of the method steps of;

if the message destination node D is within the broadcast range of the node that previously broadcasted the packet, then maximizing the goodness time delay;

if the message destination node D is within the broadcast range of the current node, then minimizing the goodness time delay;

or

otherwise making the goodness time delay proportional to the ratio of the current node'"'"'s broadcast range to the distance from the current node to the message destination node D.

12. The MANET communication method of claim 3, wherein the geographic location and broadcast range of other nodes can be known by the current node, and the current node knows the location of the message destination node D plus the location and broadcast range of at least one neighbor node, the method further comprising the steps of:

when broadcasting a packet identifying a message destination node D that is not a neighbor node, conditionally selecting a best neighbor to set as the designated receiver node according to the criteria of;

if the message destination node D is within the broadcast range of a subset of the neighbor nodes, then the best neighbor node is the one of the subset of neighbor nodes that is closest to a line between the current node and the message destination node D;

or else

the best neighbor node is the one of the neighbor nodes that has the least distance from the neighbor node'"'"'s broadcast range to the message destination node D.

13. The MANET communication method of claim 3, wherein the geographic location of other nodes can be known by the current node and the current node knows the location of the message destination node D, the method further comprising the steps of:

establishing a grid of zones around the current node wherein each zone has specified geographic boundaries and a unique zone ID;

upon receiving a packet from a one neighbor node wherein the packet has a message source node S located within a particular zone, increasing the value of a destination zone pheromone that is associated with the one neighbor node and the particular zone; and

when broadcasting a packet for a message destination node D that is known to be located within a specific zone, selecting a best neighbor to set as the designated receiver node according to which of the neighbor nodes has the highest valued destination zone pheromone that is associated with the specific zone.

14. The MANET communication method of claim 13, further comprising the step of:

increasing the value of a destination zone pheromone such that the amount of an increase is inversely related to an average number of node to node hops taken in the path from the message source node S to the neighbor node or if adequate location information is known, inversely related to the geographical distance from the message source node S to the neighbor node.

15. The MANET communication method of claim 3, further comprising the steps of:

upon receiving a packet from a one neighbor node N wherein the packet has a particular message source node D, increasing the value of a destination pheromone PN,D that is associated with the one neighbor N and the particular message source node D; and

when broadcasting a packet for a message destination node D that is the same node as the particular message source node D, selecting a best neighbor to make the designated receiver node according to which of the neighbor nodes N has the highest valued destination pheromone PN,D that is associated with the message destination node D.