Hybrid multicast routing protocol for wireless mesh networks

• US 8,289,883 B2
• Filed: 12/17/2008
• Issued: 10/16/2012
• Est. Priority Date: 12/21/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Zhu, Chunhui, Ngo, Chiu
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Elpenord, Candal
• Application Number:
  US12/337,568
• Publication Number:
  US 20090161594A1
• Time in Patent Office: 1,399 Days
• Field of Search: 370/312, 370/432, 370/254, 370/390, 370/328, 370/338, 370/238, 370/255, 370/401
• US Class Current: 370/255
• 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;

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

performing multicast packet forwarding communications among the multicast group members, wherein multicast packets comprise group request and group reply command frames, wherein a forwarded group reply command frame is not required to follow a route of a group request command frame, wherein a node is configured such that when a multicast group member or group coordinator is in a neighbor list of an intermediate node in relation to the joining node, then receiving a group reply packet without waiting for the group request packet to reach the multicast group member or the group coordinator.

2. The method of claim 1 further comprising:

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

performing multicast packet forwarding communications among the multicast group members is 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, wherein group request command frames comprise Group Join REQuest (G-JREQ) command frames, and group reply command frames comprise Group Join REPly (G-JREP) command frames, 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, wherein each neighbor list comprises 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 command frame includes:

unicast forwarding the G-JREQ command frames without requiring recording backward forwarding for G-JREP command frames.

6. The method of claim 4, wherein a forwarded G-JREP command frame is not required to follow the route of a G-JREQ command frame, 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 command frame is 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 command frame includes:

when no members are found in the neighbor list of a node, forwarding the G-JREQ command frame 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 a G-JREQ command frame 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 command frame to a parent of the node.

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

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

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

14. The method of claim 12, 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.

15. The method of claim 12, wherein no control messages are broadcast.

16. The method of claim 12, 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.

17. The method of claim 1, wherein multicast data forwarding is performed without a routing table.

18. The method of claim 4, further comprising:

determining whether a member or a group coordinator is included in the neighbor list; and

upon determining that the member or the group coordinator is included in the neighbor list, unicast sending a G-JREP command frame from a node to a source without waiting for a final destination of the G-JREQ command frame to send the G-JREP command frame.

19. The method of claim 1, wherein each neighbor list includes a field for indicating multicast groups that member nodes participate in.

20. 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;

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

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, wherein multicast packets comprise group request and group reply command frames, and a forwarded group reply command frame is not required to follow a route of a group request command frame, wherein a node is further configured such that when a group member or group coordinator is in a neighbor list of an intermediate node in relation to the joining node, then receiving a group reply packet without waiting for the group request packet to reach the group member or the group coordinator.

21. The system of claim 20 wherein

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

22. The system of claim 21, wherein the logical tree spans all nodes in the network providing forwarding of multicast control packets, wherein group request command frames comprise Group Join REQuest (G-JREQ) command frames, and group reply command frames comprise Group Join REPly (G-JREP) command frames, wherein each control packet is routed to appropriate nodes by checking the control packet destination address.

23. The system of claim 22, wherein each node maintains a neighbor list for each node, wherein each neighbor list comprises multicast related information for member nodes of each multicast groups said node participates in.

24. The system of claim 23, wherein each node forwards each G-JREQ command frame by unicast forwarding the G-JREQ command frame without requiring recording backward forwarding for a G-JREP command frame.

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

26. The system of claim 23, wherein the neighbor list of each node further includes multicast membership information, such that a G-JREQ command frame is transmitted by a node directly to one of the member neighbor nodes in the neighbor list of that node.

27. The system of claim 23, wherein each node forwards a G-JREQ command frame such that when no members are found in the neighbor list of a node, the G-JREQ command frame is forwarded to a unicast address of a group coordinator if the group coordinator address is known.

28. The system of claim 23, wherein when a joining node is set to be the group coordinator of a group, the joining node forwards the G-JREQ command frame directly to a mesh coordinator.

29. The system of claim 23, wherein for each node, when neither a member nor a group coordinator is found in the neighbor list of the node, the node forwards a G-JREQ command frame to a parent of the node.

30. The system of claim 23, wherein each node provides multicast group membership updates using the neighbor list by exchanging messages with the member nodes of each multicast group said node participates in.

31. The system of claim 23, wherein each node leaves 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.

32. The system of claim 31, 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.

33. A computer program product for multicast routing in a wireless mesh network, comprising a non-transitory 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;

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

enable the multicast group members to perform multicast packet forwarding communications among the multicast group members, wherein multicast packets comprise group request and group reply command frames, wherein a forwarded group reply command frame is not required to follow a route of a group request command frame, wherein when a multicast group member or group coordinator is in a neighbor list of an intermediate node in relation to a node, then receiving a group reply packet without waiting for the group request packet to reach the multicast group member or the group coordinator.

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

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

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

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

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

37. The computer program product of claim 36 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.

38. The computer program product of claim 36 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.

39. The computer program product of claim 38 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.