Multicasting in a network using neighbor information

• US 8,175,101 B2
• Filed: 07/24/2009
• Issued: 05/08/2012
• Est. Priority Date: 08/15/2008
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Park, Sung I., Johnnie, Darryn A.
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): NGUYEN, PHUONGCHAU BA
• Application Number:
  US12/508,747
• Publication Number:
  US 20100040079A1
• Time in Patent Office: 1,019 Days
• Field of Search: 370/252, 370/389, 370/395.4, 370407-408, 370/442, 370/444, 370/458
• US Class Current: 370/395.4
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• 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: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

In one aspect, a method to multicast in a network includes determining using a processor a least amount of relay nodes for use in multicasting a message to nodes in the network by using a neighbor matrix of a source node used in Node Activation Multiple Access (NAMA) scheduling. The method may include designating a one-hop neighbor that exclusively accesses the two-hop neighbor of the source node as a relay node. The method may also include designating a one-hop neighbor of the source node with accessibility to a maximum number of two-hop neighbors of the source node as a relay node.

Claims

1. A method to multicast in a network comprising:

determining using a processor a least amount of relay nodes to multicast a message from a source node to all other nodes in the network by using a neighbor matrix of the source node stored in the data link layer of the source node and used in Node Activation Multiple Access (NAMA) scheduling by;

designating a one-hop neighbor of the source node that exclusively accesses a two-hop neighbor of the source node as a relay node;

designating a one-hop neighbor of the source node with accessibility to a maximum number of two-hop neighbors of the source node as a relay node;

indicating in a field of the neighbor matrix associated with the exclusive one-hop neighbor that the exclusive one-hop neighbor is covered;

indicating in a field of the neighbor matrix associated with the two-hop neighbor of the source node that is accessed exclusively by the exclusive one-hop neighbor of the source node that the two-hop neighbor is covered; and

notifying one-hop neighbors of the source node that are selected as relay nodes of their selection as relay nodes.

2. The method of claim 1 wherein designating a one-hop neighbor of the source node with accessibility to a maximum number of two-hop neighbors of the source node as a relay node comprises designating a one-hop neighbor of the source node with accessibility to a maximum number of two-hop neighbors of the source node as a relay node that do not have a field in the neighbor matrix of the source node indicating that the two-hop neighbors are already covered.

3. The method of claim 1, further comprising:

at a second node being a one-hop neighbor of the source node, determining a least amount of relay nodes for use in multicasting a message nodes in the network by using a neighbor matrix of the second node by;

designating a one-hop neighbor that exclusively accesses a two-hop neighbor of the second node as a relay node;

designating a one-hop neighbor of the second node with accessibility to a maximum number of two-hop neighbors of the second node as a relay node; and

notifying one-hop neighbors of the second node that are selected as relay nodes of their selection as relay nodes.

4. The method of claim 1, further comprising connecting the nodes in the network by links wherein at least one of the links is a wireless link.

5. The method of claim 1, further comprising providing each node with a neighbor matrix which is maintained by each node for NAMA scheduling.

6. The method of claim 5 wherein providing each node with a neighbor matrix comprises providing each node with a neighbor matrix which identifies one-hop neighbors and two-hop neighbors.

7. The method of claim 6 wherein providing each node with a neighbor matrix comprises providing each node with a neighbor matrix in a table format that indicates a neighbor relationship between two nodes by having a nonzero value in an entry of the table corresponding to a row and a column associated with the two nodes.

8. An article comprising:

a non-transitory machine-readable medium that stores executable instructions to multicast in a network, the instructions causing a machine to determine a least amount of relay nodes to multicast a message from a source node to all other nodes in the network by using a neighbor matrix of the source node stored in the data link layer of the source node and used in Node Activation Multiple Access (NAMA) scheduling by;

designating a one-hop neighbor that exclusively accesses a two-hop neighbor of the source node as a relay node;

designating a one-hop neighbor of the source node with accessibility to a maximum number of two-hop neighbors of the source node as a relay node;

indicating in a field of the neighbor matrix associated with the one-hop neighbor that exclusively accesses a two-hop neighbor of the source node that the one-hop neighbor that exclusively accesses a two-hop neighbor of the source node is covered;

indicating in a field of the neighbor matrix associated with the two-hop neighbor of the source node that is accessed exclusively by the one-hop neighbor of the source node that the two-hop neighbor is covered; and

notifying one-hop neighbors of the source node that are selected as relay nodes of their selection as relay nodes.

9. The article of claim 8, further comprising at a second node being a one-hop neighbor of the source node instructions causing a machine to:

designate a one-hop neighbor that exclusively accesses a two-hop neighbor of the second node as a relay node;

designate a one-hop neighbor of the second node with accessibility to a maximum number of two-hop neighbors of the second node as a relay node; and

notify one-hop neighbors of the second node that are selected as relay nodes of their selection as relay nodes.

10. An apparatus to multicast in a network, comprising:

circuitry to determine a least amount of relay nodes to multicast a a message from a source node to all other nodes in the network by using a neighbor matrix of the source node stored in the data link layer of the source node and used in Node Activation Multiple Access (NAMA) scheduling by;

designating a one-hop neighbor that exclusively accesses a two-hop neighbor of the source node as a relay node;

designating a one-hop neighbor of the source node with accessibility to a maximum number of two-hop neighbors of the source node as a relay node;

indicating in a field of the neighbor matrix associated with the one-hop neighbor that exclusively accesses a two-hop neighbor of the source node that the one-hop neighbor that exclusively accesses a two-hop neighbor of the source node is covered;

indicating in a field of the neighbor matrix associated with the two-hop neighbor of the source node that is accessed exclusively by the one-hop neighbor of the source node that the two-hop neighbor is covered; and

notifying one-hop neighbors of the source node that are selected as relay nodes of their selection as relay nodes.

11. The apparatus of claim 10 wherein the circuitry comprises at least one of a processor, a memory, programmable logic and logic gates.

12. The apparatus of claim 10, further comprising at a second node being a one-hop neighbor of the source node circuitry configured to:

designate a one-hop neighbor that exclusively accesses a two-hop neighbor of the second node as a relay node;

designate a one-hop neighbor of the second node with accessibility to a maximum number of two-hop neighbors of the second node as a relay node; and

notify one-hop neighbors of the second node that are selected as relay nodes of their selection as relay nodes.