Method to support multicast routing in multi-hop wireless networks

• US 7,403,492 B2
• Filed: 05/05/2005
• Issued: 07/22/2008
• Est. Priority Date: 05/05/2005
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: MeshNetworks, Inc. (Motorola Solutions, Inc.)
• Inventors: Zheng, Heyun, Zeng, Surong
• Primary Examiner(s): Kizou, Hasssan
• Assistant Examiner(s): RENNER, BRANDON M
• Application Number:
  US11/122,545
• Publication Number:
  US 20060250999A1
• Time in Patent Office: 1,174 Days
• Field of Search: 370/389, 370/390, 709/238
• US Class Current: 370/254
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A system and method for supporting multicast in highly dynamic wireless multi-hop networks, such as ad-hoc networks, with good scalability. The system and method provide a multicast routing algorithm to work in wireless ad-hoc networks without any fixed infrastructure nodes present. In doing so, the system and method provide a technique to build a multicast source specific tree on demand, while using a core source node to limit routing overhead. The system and method further provide a repair process to reduce the latency of discovery of topology change, employ a node sequence number mechanism to differentiate between upstream nodes and downstream nodes on the multicast tree in the repair process, and provide an active joining process to reduce the latency of discovery of membership change.

Claims

1. A method for supporting multicast in a multihop wireless network, the method comprising:

establishing certain nodes in the network as core source nodes, wherein the establishing step comprises;

determining whether a node should be a core source node for a multicast group, based on criteria comprising a number of activated core sources in the network, a multicast core source number threshold, a distance to a closest activated core source, a number of hop counts from the node to one of the activated core sources, an address of the node, and an address of the closest activated core source;

engaging in a multicast tree discovery or refreshing process by operating at least one of the core source nodes to broadcast a route request (RREQ) message; and

building the multicast tree or refreshing the multicast tree based on the RREQ message, and at least one route reply (RREP) message received by the at least one core source node from another node in response to the RREQ message.

2. The method of claim 1, wherein the RREQ message carries information including at least one of source address, source node sequence number, desired multicast group address, hop count to the source node, routing metrics to the source node, and time-to-live (TTL).

3. The method of claim 1, wherein the step of engaging in a multicast tree discovery process further comprises:

receiving, at the core source node, the RREP message that is unicast along a reverse route to the core source node by the another node that is a multicast group member node that received the RREQ message and created the reverse route in response to the RREQ message.

4. The method of claim 3, wherein the reverse route includes at least one node, each of which becoming a forwarding node of a multicast group, such that a forwarding node is adapted to broadcast a hello message to inform its neighborhood that the multicast group is active, and the hello message carries information including a current node address and a multicast group address.

5. The method of claim 1, further comprising:

refreshing the multicast tree by periodically broadcasting a RREQ message from the core source node.

6. The method of claim 1, further comprising:

monitoring link quality of each link between a node and its neighboring nodes of the multicast tree; and

detecting a link breakage between the nodes based on the monitored link quality.

7. The method of claim 6, further comprising:

pruning a multicast branch connected by a broken link when a link breakage is detected; and

repairing a broken link, wherein the repair comprises a node connected to the broken link broadcasting a repair RREQ message, a lost core source node or a node with a fresh unicast route to the lost core source receiving the repair RREQ message, and a receiving node transmitting a repair RREP message to the node initiating the repair.

8. The method of claim 1, further comprising enabling another node to join the multicast tree by performing the steps of:

detecting a hello message including a multicast group address, at the node attempting to joint the multicast tree;

broadcasting a joining RREQ message from the joining node in order to join the multicast tree; and

transmitting a joining RREP message from any node on the multicast tree to shorten a new member joining latency.

9. The method of claim 1, wherein:

the multicast tree includes a plurality of nodes, such that packets transmitted by the nodes in the multicast tree each carry a sequence number in a header to eliminate duplicate packets.

10. A multihop wireless communications network, comprising:

a plurality of nodes, some of which being multicast source nodes; and

a number of core source nodes that is less than a total number of multicast source nodes in the network, the core source nodes engaging in a multicast tree discovery or refreshing process by broadcasting route request (RREQ) messages and receiving route reply (RREP) messages in response to the RREQ messages, and then building or refreshing a multicast tree based on an exchange of the RREQ message and RREP messages, wherein;

one of the nodes in the network is a core source node based on criteria comprising a number of activated core sources in the network, a multicast core source number threshold, a distance to a closest activated core source, a number of hop counts from the node to one of the activated core sources, an address of the node, and an address of the closest activated core source, such that;

the number of active core source nodes is less than a core source threshold number;

the number of hop counts from the node to closest activated core source node is larger than a hop count threshold number;

or

the number of hop counts from the node to an activated core source node is less than a hop count threshold number and the address of the node is larger than the address of the core source node.

11. The network of claim 10, wherein the RREQ message carries information including source address, source node sequence number, desired multicast group address, hop count to the source node, routing metrics to the source node, and (time-to-live) TTL.

12. The network of claim 10, wherein when a multicast group member node receives the RREQ message, the member node unicasts a RREP message to the core source node along a reverse route created by the RREQ message.

13. The network of claim 10, wherein each node

monitors a link quality of each link between a node and its neighboring nodes;

and

detects a link breakage.

14. The network of claim 10 wherein each of the nodes

performs the following operations:

detecting a link breakage between itself and another node;

pruning a multicast branch connected by a broken link when a link breakage is detected; and

repairing a broken link by broadcasting a repair RREQ message that is received by a lost core source node or a node with a fresh unicast route to the lost core source and the receiving node transmitting a repair RREP message to the node initiating the repair.

15. The network of claim 10, wherein any of the nodes joins a multicast tree by detecting a hello message, broadcasting a joining RREQ message, and receiving a joining RREP message that is transmitted by any node on the multicast tree that receives the joining RREQ message.

16. The network of claim 10, wherein packets transmitted by nodes in a multicast tree each carry a sequence number in a header to eliminate duplicate packets.

17. The network of claim 10, wherein a limited number of core source nodes broadcasting the RREQ message limits routing overhead.