HYBRID MULTICAST ROUTING PROTOCOL FOR WIRELESS MESH NETWORKS

• US 20090161594A1
• Filed: 12/17/2008
• Published: 06/25/2009
• Est. Priority Date: 12/21/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Ngo, Chiu, Zhu, Chunhui
• Granted Patent: US 8,289,883 B2
• Time in Patent Office: Days
• US Class Current: 370/312
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

A method of multicast routing in a wireless mesh network is provided. One implementation involves maintaining a multicast logical tree having a structure establishing parent-child connectivity relationships between wireless station nodes, wherein each node has access to local connectivity information for its local nodes; and a wireless station node joining a multicast group in the network and becoming the group coordinator. Each multicast group member may join and leave the group at any time utilizing both tree structure and local link state information.

Claims

1. A method of multicast routing in a wireless mesh network, comprising:

maintaining a multicast logical tree having a structure establishing parent-child connectivity relationships between wireless station nodes, wherein each node has access to local connectivity information for its local nodes; and

a wireless station node joining a multicast group in the network, and each group member or router propagating group membership information and local connectivity information via message transmission among its local nodes in the logical tree.

2. The method of claim 1 further comprising:

one or more other wireless station nodes joining the multicast group and becoming members; and

performing multicast packet forwarding communications among the multicast group members based on the tree structure and local link state information.

3. The method of claim 2, wherein the logical tree spans all nodes in the network providing forwarding of multicast control packets including Group Join REQuest (G-JREQ) and Group Join REPly (G-JREP (G-JREP), wherein each control packet is forwarded to appropriate nodes by checking the control packet destination address.

4. The method of claim 3 further including maintaining a neighbor list for each node, the list containing multicast related information for member nodes of each multicast group said node participates in.

5. The method of claim 4, wherein forwarding each G-JREQ packet includes:

unicast forwarding the G-JREQ packet without requiring recording backward forwarding for a G-JREP packet.

6. The method of claim 4, wherein a forwarded G-JREP packet is not required to follow the route of a G-JREQ packet, for utilizing a mesh link for short routes.

7. The method of claim 4, further including:

providing multicast membership information in the neighbor list of each node, such that a G-JREQ packet can be transmitted by a node directly to one of the member neighbor nodes in the neighbor list of that node.

8. The method of claim 4, wherein forwarding a G-JREQ packet includes:

when no members are found in the neighbor list of a node, forwarding the G-JREQ packet to a unicast address of a group coordinator if the group coordinator address is known.

9. The method of claim 4 further including:

when a joining node is set to be the group coordinator of a group, forwarding the G-JREQ packet directly to a mesh coordinator.

10. The method of claim 4 further including:

when neither a member nor a group coordinator is found in the neighbor list, forwarding a G-JREQ packet to a parent of the node.

11. The method of claim 4 further including:

when a member or group coordinator is in the neighbor list of an intermediate node in relation to a joining node, then forwarding a G-JREP packet back to the joining node without waiting for the G-JREQ pack to reach the member node or the group coordinator.

12. The method of claim 4 further including providing multicast group membership updates using the neighbor list by exchanging messages among the member nodes of each multicast group.

13. The method of claim 4 further including:

a member node leaving a multicast group by broadcasting a message to its local nodes; and

each local node in the multicast group receiving the message, updating its neighbor list to reflect that the local node can no longer reach remaining nodes in said multicast group through the leaving member node.

14. The method of claim 13 further including ending a multicast group when no members remain in the multicast group.

15. The method of claim 13, wherein the local connectivity information for a node comprises local communication link state information for a number of hops in relation to the node in the network.

16. The method of claim 13, wherein no control messages are broadcast.

17. The method of claim 13, wherein said messages are exchanged when the network is in operation after initialization, each node broadcasting a message locally when the node becomes a member, or router, of a multicast group, as well as when leaving a multicast group.

18. A system for multicast routing in a wireless mesh network, comprising:

a multicast logical tree module maintaining a multicast tree having a structure establishing parent-child connectivity relationships between wireless station nodes, wherein each node has access to local connectivity information for its local nodes; and

a wireless station node configured for joining a multicast group in the network, and each group member or router wireless station node configured for r propagating group membership information and local connectivity information via message transmission among its local nodes in the logical tree.

19. The system of claim 18 further comprising:

one or more other wireless station nodes configured for joining the multicast group, becoming members, and performing multicast packet forwarding communications among the multicast group members based on the tree structure and local link state information.

20. The system of claim 19, wherein the logical tree spans all nodes in the network providing forwarding of multicast control packets including Group Join REQuest (G-JREQ) and Group Join REPly (G-JREP (G-JREP), wherein each control packet is routed to appropriate nodes by checking the control packet destination address.

21. The system of claim 20, wherein each node is further configured for maintaining a neighbor list for each node, the list containing multicast related information for member nodes of each multicast groups said node participates in.

22. The system of claim 21, wherein each node is further configured for forwarding each G-JREQ packet by unicast forwarding the G-JREQ packet without requiring recording backward forwarding for a G-JREP packet.

23. The system of claim 21, wherein a forwarded G-JREP packet is not required to follow the route of a G-JREQ packet, for utilizing a mesh link for short routes.

24. The system of claim 21, wherein the neighbor list of each node further includes multicast membership information, such that a G-JREQ packet may be transmitted by a node directly to one of the member neighbor nodes in the neighbor list of that node.

25. The system of claim 21, wherein each node is further configured for forwarding a G-JREQ packet such that when no members are found in the neighbor list of a node, the G-JREQ packet is forwarded to a unicast address of a group coordinator if the group coordinator address is known.

26. The system of claim 21, wherein a joining node is further configured such that when the joining node is set to be the group coordinator of a group, the joining node forwards the G-JREQ packet directly to a mesh coordinator.

27. The system of claim 21, wherein each node is further configured such that when neither a member nor a group coordinator is found in the neighbor list of the node, the node forwards G-JREQ packet to a parent of the node.

28. The system of claim 21, wherein a joining node is further configured such that when a member or group coordinator is in the neighbor list of an intermediate node in relation to the joining node, then a G-JREP packet is forwarded back to the joining node without waiting for the G-JREQ pack to reach the member node or the group coordinator.

29. The system of claim 21, wherein each node is further configured for providing multicast group membership updates using the neighbor list by exchanging messages with the member nodes of each multicast group said node participates in.

30. The system of claim 21, wherein each node is further configured for leaving a multicast group by broadcasting a message to its local nodes, such that each local node in the multicast group receiving the message updates its neighbor list to reflect that the local node can no longer reach remaining nodes in said multicast group through the leaving member node.

31. The system of claim 30, wherein said messages are exchanged when the network is in operation after initialization, each node broadcasting a message locally when the node becomes a member, or router, of a multicast group, as well as when leaving a multicast group.

32. A computer program product for multicast routing in a wireless mesh network, comprising a computer usable medium including a computer readable program comprising program instructions, wherein the computer readable program when executed on a computer causes the computer to:

maintain a multicast logical tree having a structure establishing parent-child connectivity relationships between wireless station nodes, wherein each node has access to local connectivity information for its local nodes; and

enable a wireless station to join a multicast group in the network, and each group member or router propagating group membership information and local connectivity information via message transmission among its local nodes in the logical tree.

33. The computer program product of claim 32 further including program instructions for:

one or more other wireless station nodes joining the multicast group and becoming members; and

performing multicast packet forwarding communications among the multicast group members based on the tree structure.

34. The computer program product of claim 33, wherein the logical tree spans all nodes in the network providing basic forwarding of multicast control packets including Group Join REQuest (G-JREQ) and Group Join REPly (G-JREP), wherein each control packet is routed to appropriate nodes by checking the control packet destination address.

35. The computer program product of claim 34 further including program instructions for maintaining a neighbor list for each node, the list containing multicast related information for member nodes of each multicast groups said node participates in.

36. The computer program product of claim 35 further including program instructions for providing multicast group membership updates using the neighbor list by exchanging messages among the member nodes of each multicast group.

37. The computer program product of claim 35 further including program instructions for:

a member node leaving a multicast group by broadcasting a message to its local nodes; and

each local node in the multicast group receiving the message updating its neighbor list to reflect that the local node can no longer reach remaining nodes in said multicast group through the leaving member node.

38. The computer program product of claim 37 further including program instructions for exchanging said messages when the network is in operation after initialization, each node broadcasting a message locally when the node becomes a member, or router, of a multicast group, as well as when leaving a multicast group.