Reliable Broadcast Protocol and Apparatus for Sensor Networks

• US 20080247408A1
• Filed: 04/03/2007
• Published: 10/09/2008
• Est. Priority Date: 04/03/2007
• Status: Active Grant

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: ITT Manufacturing Enterprises, Inc. (ITT, Inc.)
• Inventors: Wentworth, Alexander D., Yoon, Chang-June C.J.
• Granted Patent: US 7,916,666 B2
• Time in Patent Office: Days
• US Class Current: 370/408
• CPC Class Codes: H04L 1/1657 Implicit acknowledgement of correct or incorrect reception, e.g. with a moving window
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

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

2. The method of claim 1, wherein when (c) comparing determines that the number of node hops from said root node to said node equals the number of node hops between said root node and said node for said existing tree-based topology of the network, said (f) building comprises adding an identifier of one or more downstream nodes with respect to said node from the existing tree-based topology of the network.

3. The method of claim 2, when (e) comparing determines that the number of node hops from said root node to said node does not equal the number of node hops between said root node and said node for said existing tree-based topology of the network, then further comprising determining whether an identifier of the source node of the received broadcast message is a node that is part of a sub-tree of said node in said existing tree-based topology, and if so, said (f) building comprises adding an identifier of one or more upstream nodes with respect to said node from the existing tree-based topology of the network.

4. The method of claim 3, when it is determined that the identifier of the source node of the received broadcast message is not part of a sub-tree of said node in said existing tree-based topology, then said (f) building comprises adding identifiers of all upstream nodes and downstream nodes with respect to said node from said existing tree-based topology of the network.

5. The method of claim 3, when said (e) comparing determines that the source node of the received broadcast message is a node that is not part of the existing tree-based topology of the network, said (d) building comprises building a list of identifiers of other nodes in the network that are neighbors of said node in the existing-tree based topology but excluding the source node.

6. The method of claim 1, and further comprising determining whether said message originates from a host device and indicates that the root node is leaving the network, and if so, when said node is the root node generating and broadcasting a network deactivation message.

7. The method of claim 1, wherein (g) re-broadcasting comprises re-broadcasting said broadcast message after a re-broadcast delay time interval that is based on a first value and a second random value.

8. The method of claim 7, and further comprising setting said first value to minimize collisions between re-broadcasted messages from other nodes.

9. The method of claim 7, wherein after said node re-broadcasts the broadcast message, further comprising waiting a time interval to allow for reception of the broadcast message from another node as an implicit acknowledgement that said other node received said broadcast message, and deleting from said list an identifier of said other node from which said node receives the broadcast message.

10. The method of claim 9, wherein said re-broadcasting is performed up to a predetermined number of iterations until said list maintained by said node is empty.

11. The method of claim 1, and further comprising determining when the received broadcast message is a deactivate message indicating that the root node is leaving the network, and wherein said (d) determining, (e) comparing, (f) building and (g) re-broadcasting are performed in order to re-broadcast said deactivate message to other nodes in order to notify other nodes in the network that the root node is leaving the network.

12. The method of claim 11, and further comprising said node deleting the stored data representing the existing tree-based topology of the network and waiting a reset time interval after which said node initiates a network formation procedure.

13. The method of claim 12, wherein said waiting comprises waiting a reset time interval that is derived from a rebroadcast delay time interval, a maximum number of node hops to the root node in said existing tree-based topology and the number of node hops between said node and said root node, wherein said reset time interval allows time for other nodes in the network to delete stored data representing said existing tree-based topology.

14. The method of claim 13, and further comprising ignoring any network activation messages received at said node from other nodes during said reset time interval.

15. The method of claim 13, wherein after initiating said network formation procedure, further comprising said node disabling a node affiliation procedure with respect to neighboring nodes for an affiliate delay time interval that is based on said re-broadcast delay time interval and the maximum number of hops to the root node.

16. The method of claim 1, and further comprising determining when the received broadcast message at said node is a network activation message, and if so, said node determining whether it is the first time receiving said activation message.

17. The method of claim 16, when it is the first time receiving said network activation message, said node executes a network formation process to build a new tree-based topology for the network, and wherein said (d) determining, (e) comparing, (f) building and (g) re-broadcasting are performed to re-broadcast the network formation message to other nodes to notify other nodes of the new tree-based topology for the network.

18. The method of claim 16, when it is not the first time receiving said network formation message, said node executes a re-routing procedure in order to prevent downstream nodes from executing local repair procedures.

19. The method of claim 18, and further comprising extracting from said network activation message a root node identifier, a source node identifier that identifies that node that transmitted the network activation message to said node and the number of node hops between the root node and said node, and waiting a reset delay time interval during which said node may receive neighbor discovery packets from other nodes.

20. The method of claim 19, wherein when during said reset delay time interval said node receives a neighbor discovery packet that contains a root node identifier that matches the root node identifier contained in said network activation message that said node received, then waiting a neighbor discovery time interval.

21. The method of claim 20, wherein upon expiration of the neighbor discovery time interval said node selects an upstream node and determines whether the selected upstream node is the same as an existing upstream node for said node, and if so storing data for a new tree-based topology of the network and if the selected upstream node is different than the existing upstream node, then said node performs an affiliation procedure with said selected upstream node.

22. The method of claim 19, wherein when said node determines that no neighboring nodes are discovered during said reset delay time interval, then deleting any network topology data stored at said node and said node entering an out-of-network state.

23. The method of claim 1, and further comprising said node determining whether the message is a network activation message received from a host device, and if so, said node becomes the root node for a new tree-based topology.

24. The method of claim 23, and further comprising said node attempting to discover neighboring nodes by attempting to exchange packets with other nodes during a neighbor discovery time interval, and upon expiration of the neighbor discovery time interval, said node determining whether any neighbors are discovered.

25. The method of claim 24, when said node determines that no neighbors are discovered, said node sends a message back to the host device indicating that said node is isolated, and when said node determines that at least one neighboring node is discovered, then said node setting said number of hops to said root node to zero, and wherein said (d) determining, (e) comparing, (f) building and (g) re-broadcasting are performed in order to broadcast said network activation message to other nodes.

26. 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. based on stored data in the node for an existing tree-based topology of the network, 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

c. re-broadcasting said broadcast message.

27. The method of claim 26, and further comprising determining from the received broadcast message a number of node hops between said node and a root node in the network, and comparing the number of node hops between said root node and said node 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, wherein building is based on said comparing.

28. 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, 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.