Method and communication device for routing unicast and multicast messages in an ad-hoc wireless network

• US 20080095163A1
• Filed: 10/23/2006
• Published: 04/24/2008
• Est. Priority Date: 10/23/2006
• Status: Active Grant

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson), Toyota Infotechnology Center USA, Inc.
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Kwon, Taek-Jin, Lee, John, Chen, Wai, Hikita, Toshiro, Onishi, Ryokichi
• Granted Patent: US 8,520,673 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 84/005 Moving wireless networks
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

Claims

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; and

(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) further 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.

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. The routing method according to claim 13, 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 memory, a control packet is received in sequence if said received sequence number value is greater than said sequence number stored in memory.

18. A method of processing an incoming packet by a node in an ad-hoc network comprising the steps of:

receiving the 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.

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 22, wherein the transmission and reception channels are selected to alternate.

24. The method for routing a multicast message according to claim 23, wherein the transmission and reception channels are selected to alternate in a single alternate pattern.

25. The method for routing a multicast message according to claim 23, 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.

26. 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.

27. The method for routing a multicast message according to claim 26, wherein each selected forwarding node stores a multicast group identification in the multicast forwarding table.

28. The method for routing a multicast message according to claim 26, 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.

29. The method for routing a multicast message according to claim 26, 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.

30. 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.

31. The method for routing a multicast message according to claim 30, 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.

32. The method for routing a multicast message according to claim 31, 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.

33. The method for routing a multicast message according to claim 32, 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.

34. 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.

35. The method for routing a multicast message according to claim 34, 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.

36. The method for routing a multicast message according to claim 35, wherein the transmission and reception channels are selected to alternate in a double alternate pattern.

37. The method for routing a multicast message according to claim 36, wherein the method for setting the double alternate pattern including the steps of:

(a) specifying a reference transmission channel;

(b) selecting a reference classification side;

(c) broadcasting a heartbeat control packet including the reference transmission channel and the reference classification side; and

(d) assigning transmission channels based upon said reference classification side and reference transmission channel.

38. The method for routing a multicast message according to claim 37, wherein step (d) includes the sub-steps of:

determining a classification side for a forwarding node;

determining its hop distance from the group header; and

assigning the transmission channels based upon a comparison of the classification side with the reference classification side and the hop distance from the group header.

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 comprising:

means for receiving the incoming packet;

means for determining if the incoming packet is destined for said node;

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 node; and

means for relaying the incoming packet to said next hop to destination.

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.