Reliable broadcast protocol and apparatus for sensor networks
First Claim
1. A method for broadcasting messages in an ad hoc wireless network having a tree-based architecture, comprising:
- a. receiving a message at a node in the network;
b. determining whether the message is a broadcast message;
c. when the message is a broadcast message, determining a source node of the broadcast message based on stored data at the node that represents an existing tree-based topology of the network;
d. determining from the broadcast message a number of node hops to a root node for said source node and deriving therefrom a number of nodes from said root node to said node;
e. comparing the number of node hops from said root node to said node with data stored at said node that represents the number of node hops between said root node and said node for said existing tree-based topology of the network;
f. based on said (e) comparing, building a list of identifiers of other nodes in the network from which said node requires reception of a broadcast message as an implicit acknowledgment that said other nodes in the network have received said broadcast message; and
g. re-broadcasting said broadcast message.
11 Assignments
0 Petitions
Accused Products
Abstract
A method for broadcasting messages in an ad hoc wireless network having a tree-based architecture is provided. When a node receives a broadcast message for re-broadcasting to other nodes in the network, it builds a list of identifiers of other nodes in the network from which the node requires reception of a broadcast message as an implicit acknowledgment that said other nodes in the network have received said broadcast message. The node builds this implicit acknowledgment list based on stored data pertaining to an existing tree-based topology of the network. After this list is built, the node re-broadcasts the broadcast message. Each node in the network executes this broadcasting protocol and in so doing a broadcast message quickly and efficiently propagates through the network with minimal redundancy and impact on the topology of the network.
42 Citations
43 Claims
-
1. A method for broadcasting messages in an ad hoc wireless network having a tree-based architecture, comprising:
-
a. receiving a message at a node in the network; b. determining whether the message is a broadcast message; c. when the message is a broadcast message, determining a source node of the broadcast message based on stored data at the node that represents an existing tree-based topology of the network; d. determining from the broadcast message a number of node hops to a root node for said source node and deriving therefrom a number of nodes from said root node to said node; e. comparing the number of node hops from said root node to said node with data stored at said node that represents the number of node hops between said root node and said node for said existing tree-based topology of the network; f. based on said (e) comparing, building a list of identifiers of other nodes in the network from which said node requires reception of a broadcast message as an implicit acknowledgment that said other nodes in the network have received said broadcast message; and g. re-broadcasting said broadcast message. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A method for re-broadcasting messages from a node in an ad hoc wireless network having a tree-based architecture, comprising:
-
a. receiving a broadcast message at the node for re-broadcasting from the node to other nodes in the network; b. determining from the broadcast message a number of node hops between said node and a root node in the network, and comparing the number of node hops with data stored at said node that represents the number of node hops between said root node and said node for an existing tree-based topology of the network; c. based on said comparing, building a list of identifiers of other nodes in the network from which said node requires reception of the broadcast message as an implicit acknowledgment that said other nodes in the network have received said broadcast message; and d. re-broadcasting said broadcast message. - View Dependent Claims (29, 30)
-
-
31. A wireless communication device that operates as a node in an ad hoc wireless network having a tree-based architecture, the device comprising:
-
a. a radio transceiver that transmits and receive signals; b. a modem that modulates baseband transmit signals and demodulates baseband receive signals; c. a memory that stores network topology data for an existing network; and d. a controller coupled to said modem and said memory, wherein the controller controls operation of said device as a node in the network, wherein when the device receives a broadcast message for re-broadcasting to other nodes in the network, said controller determines from the broadcast message a number of node hops to a root node for a source node, compares the number of node hops from said root node to said node with data stored at said node that represents the number of node hops between said root node and said node for said network topology, and, based on said network topology data, generates a list of identifiers of other nodes in the network from which reception of a broadcast message is required as an implicit acknowledgment that said other nodes in the network have received said broadcast message. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43)
-
Specification