Method and apparatus for broadcast in an ad hoc network using elected broadcast relay nodes

• US 7,593,376 B2
• Filed: 12/07/2005
• Issued: 09/22/2009
• Est. Priority Date: 12/07/2005
• Status: Active Grant

• Current Assignee: Bison Patent Licensing, LLC
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Matson, Peggy K., Lee, Whay Chiou, Kumar, Surender, Kotzin, Michael D., Joshi, Avinash, Ekl, Randy L., Bonta, Jeffrey D., D'Amico, Thomas V.
• Primary Examiner(s): Feild, Joseph H
• Assistant Examiner(s): Nguyen, Huy D
• Application Number:
  US11/295,909
• Publication Number:
  US 20070127421A1
• Time in Patent Office: 1,385 Days
• Field of Search: 370/338, 455/445, 455/412.2, 455/420, 455/425
• US Class Current: 370/338
• CPC Class Codes: H04W 72/30 Resource management for broadcast services
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method and apparatus for electing broadcast relay nodes (520B, H, M) in an ad hoc network (500). Each node (520A-520O) generates an attribute message including associated parameters. Each node (520A-520O) generates a weighted value (WV) based on the parameters. The WV can be included in the attribute message for that node, can provide a metric for ranking that node to be nominated to be a broadcast relay node, can alternatively provide a probability measure for that node to probabilistically elect itself as a broadcast relay node. The broadcast manager node (520C) receives the attribute messages and elects at least one nominated node as a broadcast relay node (520B, H, M) based on the attribute messages. Each node (520A-520O) can also initiate election of an intermediate broadcast relay node if that node fails to receive a test message within a predetermined time.

Claims

1. An ad hoc network, comprising:

a plurality of nodes,

wherein each node is configured to generate an attribute message comprising parameters associated with that node, and to transmit the attribute message; and

a broadcast manager node configured to receive the attribute messages from each node and to elect at least one of said nodes as a broadcast relay node based on the attribute messages,

wherein each node is configured to generate a weighted value based on the parameters associated with that node, the weighted value provides a metric for ranking that node as a candidate for election as a broadcast relay node, and the attribute message transmitted from each node further comprises the weighted value associated with each particular node, and

wherein at least one of;

a) each node is configured to nominate at least one nominee node for election as a broadcast relay node, and the broadcast manager node is configured to rank each nominee node based on the weighted values associated with the nominee nodes to determine candidate nodes, and to elect at least one of the candidate nodes as the broadcast relay node, or

b) the weighted value is a probability measure, and each node is configured to probabilistically elect itself as a broadcast relay node based on its probability measure by sending an announcement message to its neighbor nodes.

2. The ad hoc network of claim 1, wherein each of said nodes has at least one neighbor node, and wherein the parameters associated with each particular node comprise at least one of:

a number of neighbor nodes of the particular node,

a received signal strength from each of the neighbor nodes to the particular node,

a battery state of the particular node,

an activity level of the particular node,

a mobility of the particular node,

an indicator as to whether the particular node is in communication with an infrastructure entity,

location of the particular node, and

service types associated with the particular node.

3. The ad hoc network of claim 1, wherein the broadcast manager node is configured to rank each node based on the weighted values to determine candidate nodes, and to elect at least one of the candidate nodes as the broadcast relay node.

4. The ad hoc network of claim 1, wherein the broadcast manager node is configured to periodically broadcast a test message to ensure that a broadcast message is transmitted within a predetermined time, and

wherein each node is configured to determine if the test message is received within a predetermined time and, when the node is a broadcast relay node, relay the test message to neighbor nodes of that node.

5. The ad hoc network of claim 4, wherein each node which fails to receive the test message within a predetermined period of time, transmits a message to its neighbor nodes to request election of a broadcast relay node, electing at least one neighbor node that has received the test message within the predetermined period of time as a broadcast relay node, and the elected node sending a broadcast relay status announcement message to its neighbor nodes.

6. The ad hoc network of claim 5, wherein each broadcast relay node probabilistically renounces its broadcast relay status by sending a renouncement message to its neighbor nodes if at least a predetermined number of its neighbor nodes announce themselves to be broadcast relay nodes.

7. An ad hoc network, comprising:

a plurality of nodes, each node configured to generate an attribute message comprising parameters associated with that node and to transmit the attribute message; and

a broadcast manager node configured to receive the attribute messages from each node and to elect at least one of said nodes as a broadcast relay node based on the attribute messages,

wherein the broadcast manager node is configured to periodically broadcast a test message to ensure that a broadcast message is transmitted within a predetermined time, and

wherein each node is configured to determine if the test message is received within a predetermined time and, when the node is a broadcast relay node, relay the test message to neighbor nodes of that node.

8. The ad hoc network of claim 7, wherein each node is configured to initiate election of at least one of the nodes as an intermediate broadcast relay node when that node fails to receive the message within the predetermined time.

9. The ad hoc network of claim 8, wherein each node is configured to initiate route discovery to attempt to discover a route from that node to at least one of the broadcast manager node or one of the elected broadcast relay nodes when the message is not received at that node.

10. The ad hoc network of claim 9, wherein the broadcast manager node is configured to elect at least one of the nodes as an intermediate broadcast relay node when a route is discovered from the node, that failed to receive the message within the predetermined time, to at least one of the broadcast manager node or one of the elected broadcast relay nodes,

wherein the intermediate broadcast relay node completes a communication link from the node, that failed to receive the message within the predetermined time, to at least one of the broadcast manager node or one of the elected broadcast relay nodes.

11. The ad hoc network of claim 7, wherein each of said nodes has at least one neighbor node, and wherein the parameters associated with each particular node comprise at least one of:

a number of neighbor nodes of the particular node,

a received signal strength from each of the neighbor nodes to the particular node,

a battery state of the particular node,

an activity level of the particular node,

a mobility of the particular node,

an indicator as to whether the particular node is in communication with an infrastructure entity,

location of the particular node, and

service types associated with the particular node.

12. In an ad hoc network comprising a plurality of nodes, a method comprising:

generating an attribute message at each node, wherein each attribute message comprises parameters associated with each particular node;

transmitting the attribute message from each node to neighbor nodes;

electing at least one of said nodes as a broadcast relay node based on the attribute messages; and

generating a weighted value for each node based on the parameters associated with each node,

wherein the weighted value provides a metric for ranking the node as a candidate for election as a broadcast relay node and the attribute message transmitted from each node further comprises the weighted value associated that node,

and at least one of;

a) the weighted value is a probability measure, and each node is configured to probabilistically elect itself as a broadcast relay node based on its probability measure by sending an announcement message to its neighbor nodes,

b) electing at least one of said nodes as a broadcast relay node comprises;

nominating, at each node, at least one nominee node for election as a broadcast relay node;

ranking each nominee node based on the weighted values associated with the nominee nodes to determine candidate nodes; and

electing at least one of the candidate nodes as the broadcast relay node, or

c) the plurality of nodes are divided into first and second multicast groups, and electing at least one of said nodes as a broadcast relay node comprises;

nominating, at each node in the first multicast group, nominee nodes for election as a broadcast relay node for the first multicast group;

ranking each nominee node based on the weighted values associated with the nominee nodes to determine candidate nodes for the first multicast group; and

electing at least one of the candidate nodes as the broadcast relay node for the first multicast group.

13. The method of claim 12, wherein each of said nodes has at least one neighbor node, and wherein the parameters associated with each node comprise at least one of:

a number of neighbor nodes of the node,

a received signal strength from each of the neighbor nodes to the node,

a battery state of the node, an activity level of the node,

a mobility of the node and an indicator as to whether the node is in communication with a wired infrastructure entity,

location of the particular node, and

service types associated with the particular node.

14. The method of claim 12, wherein electing at least one of said nodes as a broadcast relay node, comprises:

ranking each node based on the weighted values to determine candidate nodes; and

electing at least one of the candidate nodes as the broadcast relay node.

15. The method of claim 12, wherein the plurality of nodes are divided into a first multicast group and a second multicast group, and wherein electing at least one of said nodes as a broadcast relay node, comprises:

ranking each node based on the weighted values to determine candidate nodes for the first multicast group; and

electing at least one of the candidate nodes as the broadcast relay node for the first multicast group.

16. The method of claim 12, wherein the ad hoc network further comprises a broadcast manager node, and further comprising:

periodically broadcasting a test message from the broadcast manager node to ensure that a broadcast message is transmitted within a predetermined time;

determining, at each node if the test message is received within a predetermined time; and

relaying the test message to neighbor nodes, when the node is a broadcast relay node; and

transmitting a message to its neighbor nodes to request election of a broadcast relay node from each node which fails to receive the test message within a predetermined period of time, electing at least one neighbor node that has received the test message within the predetermined period of time as a broadcast relay node, and the elected node sending a broadcast relay status announcement message to its neighbor nodes.

17. The method of claim 16, wherein each broadcast relay node probabilistically renounces its broadcast relay status by sending a renouncement message to its neighbor nodes if at least a predetermined number of its neighbor nodes announce themselves to be broadcast relay nodes.

18. In an ad hoc network comprising a plurality of nodes including a first node, a method comprising:

generating an attribute message at each node, wherein each attribute message comprises parameters associated with each particular node;

transmitting the attribute message from each node to neighbor nodes;

electing at least one of said nodes as a broadcast relay node based on the attribute messages; and

at least one of;

(a) periodically broadcasting a test message from a broadcast manager node to ensure that a broadcast message is transmitted within a predetermined time;

determining if the first node received the test message; and

electing at least one of the nodes as an intermediate broadcast relay node to restore network connectivity to the first node when the first node did not receive the test message, or

b) wherein the plurality of nodes each have at least one service type associated therewith, and wherein electing at least one of said nodes as a broadcast relay node, comprises;

grouping the nodes into groups based on service types;

determining candidate nodes belonging to a group associated with a first service; and

electing at least one of the candidate nodes as the broadcast relay node for the group associated with a first service.

19. The method of claim 18, wherein electing at least one of the nodes as an intermediate broadcast relay node, comprises:

attempting to discover a route from the first node to at least one of the broadcast manager node or one of the elected broadcast relay nodes when the test message is not received at the first node; and

when a route is discovered from the first node to at least one of the broadcast manager node or one of the elected broadcast relay nodes, electing at least one of the nodes as an intermediate broadcast relay node which completes a communication link from the first node to at least one of the broadcast manager node or one of the elected broadcast relay nodes.

20. The method of claim 18, further comprising:

determining if the first node is a broadcast relay node upon receipt to the test message; and

relaying the test message to neighbor nodes of the first node when the first node is determined to be a broadcast relay node.

21. The method of claim 18, wherein each of said nodes has at least one neighbor node, and wherein the parameters associated with each particular node comprise at least one of:

a number of neighbor nodes of the particular node,

a received signal strength from each of the neighbor nodes to the particular node,

a battery state of the particular node,

an activity level of the particular node,

a mobility of the particular node,

an indicator as to whether the particular node is in communication with an infrastructure entity,

location of the particular node, and

service types associated with the particular node.