Swarm location service for mobile ad hoc network communications

• US 7,813,326 B1
• Filed: 11/20/2006
• Issued: 10/12/2010
• Est. Priority Date: 05/27/2005
• Status: Active Grant

• Current Assignee: Bluetronix Incorporated
• Original Assignee: Bluetronix Incorporated
• Inventors: Kelm, Jonathon C., Heiferling, Mark J.
• Primary Examiner(s): Edouard, Patrick N
• Assistant Examiner(s): Amirmokri, Jalaleddin
• Application Number:
  US11/561,634
• Time in Patent Office: 1,422 Days
• Field of Search: 370/338
• US Class Current: 370/338
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: Y02D 30/70 in wireless communication networks

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 providing geographic node location information to nodes among a plurality of communication nodes in a mobile ad hoc network (MANET);

wherein each node is a device that has computing and communication broadcasting and receiving capabilities plus a broadcastable identifier, a broadcast can be “

sent to”

a particular node by including a designated receiver node'"'"'s identifier in a broadcast packet, and many of the nodes are able to determine a node'"'"'s geographic location;

the method being implemented in each node, if able, each node being a “

current node”

in the context of the method steps it carries out;

the method in the current node comprising the method steps of;

maintaining a first table being a node location table wherein each line in the node location table corresponds to a node known to the current node, and the line contains the node'"'"'s identifier and geographic location information;

maintaining a second table being a “

scorecard”

of potential location server nodes for the current node, wherein each line of the scorecard corresponds to a particular node that has disclosed node location information to the current node, and the line contains the particular node'"'"'s identifier and a dynamically changing score that is determined for the particular node by the current node, such that the score'"'"'s value is a pheromone strength that indicates how relatively good the particular node is as a location server node that provides node location information to the current node;

upon receiving any broadcast packet containing node location information, updating the node location table with node identifier and corresponding node location information that is new or changed according to the received packet, and also updating the scorecard by increasing the score of the node that provided the node location information;

whenever a predetermined amount of time elapses from the most recent value modification of the score for a node in the scorecard, implementing time based decay of pheromone strength by decreasing the score of the node in the scorecard, thereby independently determining the current node'"'"'s best location server node based on recent experience as indicated by the highest valued pheromone strength;

when location information is desired for a node with a known identifier, broadcasting a location request (LREQ) packet that a includes the identifier of a “

requested node”

; and

upon receiving any LREQ packet, if location information for the requested node is in the node location table, broadcasting a location reply (LRPL) packet that includes;

the requested node'"'"'s identifier and location information, and

the current node'"'"'s identifier and location information;

thereby increasing the current node'"'"'s score (pheromone strength) in all nodes that receive the LRPL broadcast packet.

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

when broadcasting an LREQ packet, sending it to the highest-scoring node in the current node'"'"'s scorecard, if any;

thereby addressing its location request to the node it deems to be its best location server node.

3. The method of claim 1, further comprising the method steps of:

upon receiving an LREQ packet that requests location information about a node that isn'"'"'t in its node location table, sending the LREQ packet to the highest-scoring node in the its scorecard, if any; and

if there aren'"'"'t any location server nodes in the scorecard that have a non-zero score, then rebroadcasting the LREQ packet without a designated receiver node.

4. The method of claim 1, further comprising the method steps of:

the current node initializing itself by;

determining its location information, if possible; and

broadcasting a location packet (LOCN) containing its location information, if known, and its identifier.

5. The method of claim 4, further comprising the method steps of:

upon receiving an LOCN packet, updating the sending node'"'"'s location information in the node location table, and broadcasting a location acknowledgement (LACK) packet that includes;

the identifier and location information, if known, for the current node, and the identifier and location information for the highest-scoring node in the scorecard, if any;

and if there aren'"'"'t any location server nodes in the scorecard, then randomly determining whether or not to include the identifier and location information for the current node for use as a location server node.

6. The method of claim 1, further comprising the method steps of:

including maximum broadcasting range information, if known, for each node in the node location table and in the scorecard; and

when broadcasting, including maximum broadcasting range information, if known, for each node listed in any message packet being broadcast.

7. The method of claim 1, further comprising the method steps of:

wherein mobility of a node can be noted as stationary or mobile, including mobility information, if known, for each node in the node location table; and

when broadcasting, including mobility information, if known, for each node listed in any message packet being broadcast.

8. The method of claim 7, further comprising the method step of:

only updating location information for nodes that are not noted as stationary.

9. The method of claim 7, further comprising the method step of:

further noting mobility of a mobile node as mobility of two or more different amounts of mobility.

10. The method of claim 9, further comprising the method steps of:

only updating location information for nodes that are not noted as stationary; and

updating a node'"'"'s location information at a frequency that increases with the amount of mobility of the node.

11. The method of claim 7, further comprising the method steps of:

updating an associated timestamp when updating location information in the node location table, and including the associated timestamp with location information being included in a location reply packet to indicate the age of location information;

timing a speed of reply to a location request broadcast;

in a network containing mostly stationary nodes, increasing a location server node'"'"'s score mainly according to the location server node'"'"'s speed of reply;

in a network containing mostly mobile nodes, increasing a location server node'"'"'s score mainly according to the location server node'"'"'s ability to provide low age location information; and

when a uniform mobility for a majority of the nodes in the network may not be known, increasing a location server node'"'"'s score according to a weighted average of the location server node'"'"'s speed of reply and ability to provide low age location information.

12. The method of claim 1, further comprising the method steps of:

learning whether the current node is a good location server node itself by maintaining its own identifier and score in its scorecard; and

increasing its score whenever it successfully replies to an LREQ packet with an LRPL packet.

13. The method of claim 12, further comprising the method steps of:

adjusting both the maximum number of nodes to be stored in the node location table, and the current node'"'"'s probability of responding to location requests, in proportion to the value of its own location server score in the scorecard;

thereby reducing the likelihood of expending energy storing unneeded information.