Method and Communication Device for Routing Unicast and Multicast Messages in an Ad-Hoc Wireless Network

Abstract

A method and communication device for routing unicast and multicast messages. The method for routing a unicast message includes receiving a first control packet including routing parameters from a group header node, updating a routing table based upon the routing parameters, receiving a second control packet including additional routing parameters from a group node, updating the routing table based upon the additional routing parameters and generating a forwarding table from the routing table when both of the updated steps are completed. The unicast message is routed based upon the forwarding table. A method for routing a multicast message comprises receiving the multicast message, determining if a multicast group destination for the multicast message is in a multicast forwarding table (MFT), determining if the multicast message has been previously forwarded and forwarding the multicast message if the message was not previously forwarded and the multicast group destination is in the MFT.

1 . A method for routing packets of information between nodes within a local peer group in a wireless ad-hoc network comprising the steps of:
 (a) receiving a first control packet including at least one routing parameter from a group header node;   (b) updating a routing table based upon said at least one routing parameter;   (c) receiving a second control packet including at least one additional routing parameter from a group node within said local peer group;   (d) updating said routing table based upon said at least one additional routing parameter;   (e) generating a forwarding table from said routing table when both of said updated steps are completed.   
     
     
         2 . The method for routing packets of information according to  claim 1 , wherein step (b) further comprises the sub-step of determining if said first control packet is in sequence using a sequence number. 
     
     
         3 . The method for routing packets of information according to  claim 2 , wherein step (b) is only performed if said first control packet is determined to be in sequence. 
     
     
         4 . The method for routing packets of information according to  claim 1 , wherein said at least one routing parameter includes a group list, hop count and next hop to said group header. 
     
     
         5 . The method for routing packets of information according to  claim 4 , wherein said step (b) further includes the steps of:
 (i) modifying a destination list based upon said group list;   (ii) initializing a next hop to destination for all destinations except the immediate relay node that directly related said first control packet in said destination list as said group header; and   (iii) modifying said next hop to said group header as said immediate relay node.   
     
     
         6 . The method for routing packets of information according to  claim 1 , wherein step (b) farther comprises the sub-step of determining if said first control packet is new using a sequence number, wherein said first control packet is not new, said updating step includes the sub-steps of:
 updating only a next hop for a destination node that corresponds to said immediate relay node.   
     
     
         7 . The method for routing packets of information according to  claim 1 , wherein step (d) further comprises the step of:
 (i) determining a source for said second control packet;   (ii) determining a direct sender of said second control packet;   (iii) modifying a next hop for said source via said direct sender based upon said at least one additional routing parameter in said second control packet; and   (iv) modifying said next hop for said direct sender based upon said at least one additional routing parameter in said second control packet.   
     
     
         8 . The method for routing packets of information according to  claim 1 , where said forwarding table is used for routing said packets of information. 
     
     
         9 . The method for routing packets of information according to  claim 1 , wherein after reception of said first control packet, a node increments a hop count value field in said first control packet and inserts said node's identification into a next hop to said group header field in said first control packet. 
     
     
         10 . The method for routing packets of information according to  claim 9 , wherein said node forwards said first control packet after performing said incrementing and insertion. 
     
     
         11 . The method for routing packets of information according to  claim 10 , wherein after reception of said second control packet, a node forwards said second control packet towards said group header. 
     
     
         12 . The method for routing packets of information according to  claim 1 , wherein steps (a)-(e) are performed by all group nodes in the local peer group. 
     
     
         13 . A routing method for routing packets of information between nodes within a local peer group in a wireless ad-hoc network comprising:
 determining a type of control packet that is received by a node;   determining if said control packet is received by said node in sequence; and   updating a routing table based upon information contained in said control packet if said control packet is in sequence   
       wherein said determining if said control packet is received by said node in sequence is based upon a comparison of a sequence number value contained in said control packet with a sequence number stored in a memory, a control packet is received in sequence if said received sequence number value is greater than said sequence number stored in the memory. 
     
     
         14 . The routing method according to  claim 13 , wherein said type of control packet is a heartbeat control packet or a membership report. 
     
     
         15 . The routing method according to  claim 14 , wherein said method further includes deciding whether said node is a group header or a group node. 
     
     
         16 . The routing method according to  claim 15 , wherein if said node is said group node and the type of control packet is said heartbeat control packet, said updating step including modifying said routing table to include all members of a group membership list which is contained in said heartbeat control packet. 
     
     
         17 . (canceled) 
     
     
         18 . A method of processing an incoming packet by a node in an ad-hoc network comprising the steps of:
 receiving the incoming packet at the node;   determining if the incoming packet is destined for the node;   determining a next hop to destinations based upon reading an entry in a routing table, if the incoming packet is not destined for said node;   selecting a relay node from a plurality of nodes based on the willingness of said plurality of nodes, the willingness being determined based upon a reception of a periodically broadcast status message; and   relaying the incoming packet to said next hop to destination through said relay node.   
     
     
         19 . The method of processing an incoming packet according to  claim 18 , wherein if the incoming packet is destined for said node, the node processes and consumes the incoming packet. 
     
     
         20 . A method for routing a multicast message in an ad-hoc wireless network comprising the steps of:
 receiving the multicast message for forwarding;   determining if a multicast group destination for the multicast message is in a multicast forwarding table;   determining if the multicast message has been previously forwarded;   forwarding the multicast message if it is determined that the multicast message was not previously forwarded and if it is determined that the multicast group destination is in the multicast forwarding table; and   adding the multicast message to a sent list after the multicast message is sent.   
     
     
         21 . The method for routing a multicast message according to  claim 20 , further comprising the step of: determining if the multicast message is in a transmission queue, wherein if the multicast message is not in the transmission queue, the multicast message is added to the transmission queue for forwarding, and if the multicast message is in the transmission queue, the multicast message is discarded. 
     
     
         22 . The method for routing a multicast message according to  claim 20 , further comprising the steps of:
 selecting a transmission channel for each node having the multicast group destination listed in the multicast forwarding table; and   selecting a reception channel, for each node having the multicast group destination listed in the multicast forwarding table.   
     
     
         23 . The method for routing a multicast message according to  claim 20 , wherein the multicast forwarding table is generated based upon a method comprising:
 assigning a classification for each node within a local peer group;   determining a hop count from a group header for each node, the group header is a node selected from all nodes within the local peer group;   collecting multicast membership information; and   selecting forwarding nodes in a mesh for a multicast group based upon the collected multicast membership information and hop count from group header.   
     
     
         24 . The method for routing a multicast message according to  claim 23 , wherein each selected forwarding node stores a multicast group identification in the multicast forwarding table. 
     
     
         25 . The method for routing a multicast message according to  claim 23 , wherein the classification hop count from group header and multicast membership information is broadcast from the group header to other nodes within the local peer group. 
     
     
         26 . The method for routing a multicast message according to  claim 20 , wherein the multicast routing table is generated based upon a membership report including multicast membership information relayed to a group header, all nodes relaying the membership report to the group header from a multicast member becomes forwarding nodes for a multicast group that includes the multicast member, each forwarding node records the multicast group destination in the multicast forwarding table. 
     
     
         27 . The method for routing a multicast message according to  claim 26 , wherein a number of forwarding nodes for a multicast group is adjusted by the group header based upon the hop count from the group header for each multicast member. 
     
     
         28 . The method for routing a multicast message according to  claim 27 , wherein said adjustment prunes all forwarding nodes between the group header and a multicast member determined to be the closest multicast member of a specific multicast group to the group header, and prunes itself. 
     
     
         29 . The method for routing a multicast message according to  claim 28 , wherein when a forwarding node is pruned, the forwarding node deletes the multicast group destination corresponding to the pruned multicast group, from the multicast forwarding table. 
     
     
         30 . The method for routing a multicast message according to  claim 23 , wherein the forwarding node becomes a non-forwarding node for a multicast group when a preset timer expires without receiving a membership report including the multicast membership information corresponding to the multicast group. 
     
     
         31 . The method for routing a multicast message according to  claim 20 , further comprising the steps of:
 storing the sent multicast message in memory for a predetermined time;   detecting if the sent multicast message is received from a neighboring forwarding node within the predetermined time; and   repeating the forwarding step if the sent multicast message is not detected within the predetermined time, wherein the multicast message is discarded from memory if the sent multicast message is detected within the predetermined time/   
     
     
         32 . The method for routing a multicast message according to  claim 31 , further comprising the steps of:
 counting a number of times that the forwarding step is repeated;   comparing the counted number of times with a preset threshold value; and   discarding the multicast message if the counted number of times is greater than the preset threshold.   
     
     
         33 . The method for routing a multicast message according to  claim 22 , wherein the transmission and reception channels are selected to alternate. 
     
     
         34 . The method for routing a multicast message according to  claim 33 , wherein the transmission and reception channels are selected to alternate in a single alternate pattern. 
     
     
         35 . The method for routing a multicast message according to  claim 33 , wherein each node that is selected to be a forwarding node, sets its transmission and reception channels to said single alternate pattern based upon a reference transmission and reception channel included in a heartbeat control packet from a group header and a hop count from group header also included in said heartbeat control packet. 
     
     
         36 .- 38 . (canceled) 
     
     
         39 . A wireless communication device comprising:
 means for receiving the multicast message for forwarding;   means for determining if a multicast group destination for the multicast message is in a multicast forwarding table;   means for determining if the multicast message has been previously forwarded;   means for forwarding the multicast message if it is determined that the multicast message was not previously forwarded and if it is determined that the multicast group destination is in the multicast forwarding table; and   means for adding the multicast message to a sent list after the multicast message is sent.   
     
     
         40 . The wireless communication device of  claim 39 , further comprising:
 means for storing said multicast forwarding table and said sent list.   
     
     
         41 . The wireless communication device of  claim 39 , further comprising:
 means for determining if a new multicast message has been previously sent; means for discarding said new multicast message if a new multicast message has been previously sent;   means for determining if said new multicast message is in a transmission queue; and   means for removing a multicast message from the transmission queue if a new multicast message has been previously sent and is in the transmission queue.   
     
     
         42 . A wireless communication device of  claim 39 , wherein said wireless communication device is installed into a moving vehicle. 
     
     
         43 . A wireless communication device for processing an incoming packet in an ad-hoc network, comprising:
 means for receiving the incoming packet;   means for determining if the incoming packet is destined for the wireless communication device;   means for determining a next hop to destinations based upon reading an entry in a routing table, if the incoming packet is not destined for said wireless communication device;   means for selecting a relay node from a plurality of nodes based on the willingness of the plurality of nodes, the willingness being determined based upon a reception of a periodically broadcast status message; and   means for relaying the incoming packet to said next hop to destinations through said relay node.   
     
     
         44 . A wireless communication device of  claim 43 , wherein said wireless communication device is installed into a moving vehicle. 
     
     
         45 . A computer readable medium comprising a set of computer readable instructions capable of being executed by at least one processor in a wireless communication device of a moving vehicle for controlling said at least one processor to route messages, the routing comprising the steps of:
 receiving a multicast message for forwarding;   determining if a multicast group destination for the multicast message is in a multicast forwarding table;   determining if the multicast message has been previously forwarded;   forwarding the multicast message if it is determined that the multicast message was not previously forwarded and if it is determined that the multicast group destination is in the multicast forwarding table; and   adding the multicast message to a sent list after the multicast message is sent.   
     
     
         46 . The computer readable medium comprising a set of computer readable instructions capable of being executed by at least one processor in a wireless communication device of a moving vehicle for controlling said at least one processor to route messages of  claim 45 , further comprising instructions for executing the steps of:
 receiving an incoming packet;   determining if the incoming packet is destined for said node;   determining a next hop to destinations based upon reading an entry in a routing table, if the incoming packet is not destined for said node; and   relaying the incoming packet to said next hop to destination.   
     
     
         47 . The method of processing an incoming packet according to  claim 18 , wherein the periodically broadcast status message indicates willingness for only a specific type of message. 
     
     
         48 . The method of processing an incoming packet according to  claim 18 , further comprising receiving the periodically broadcast status message from a predetermined sub-set of the plurality of nodes.