Energy-efficient network protocol and node device for sensor networks

• US 7,729,285 B2
• Filed: 03/22/2005
• Issued: 06/01/2010
• Est. Priority Date: 03/22/2005
• Status: Active Grant

• Current Assignee: Ollnova Technologies Limited (Atlantic IP Services Limited)
• Original Assignee: ITT Manufacturing Enterprises, Inc. (ITT, Inc.)
• Inventors: Yoon, Chang-June C. J.
• Primary Examiner(s): Eng; George
• Assistant Examiner(s): MANOHARAN, MUTHUSWAMY GANAPATHY
• Application Number:
  US11/085,655
• Publication Number:
  US 20060215588A1
• Time in Patent Office: 1,897 Days
• Field of Search: 370254-256, 370/351, 370400-401
• US Class Current: 370/254
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 52/0219 where the power saving management affects multiple terminals
• CPC Class Codes: H04W 56/00 Synchronisation arrangements
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

An “on-demand” approach for a routing protocol for a wireless network that achieves balanced energy consumption among all participating nodes in the network. Synchronization messages transmitted by nodes associated with an upstream node include local node information (LNI) that a node can use to repair or bypass a lost upstream node in a real or virtual (temporary) manner depending upon the local node'"'"'s battery level. Only if a repair process fails will a global re-organization (Re-Org) be initiated. The LNI also allows for nodes having lower power availability (battery level) not to transmit the LNI so that unaffiliated node(s) can select an upstream node having more power availability thereby extending network life.

Claims

1. A method for forming a wireless network comprised of a plurality of nodes including a main node, wherein the plurality of nodes transmit and receive information between each other and ultimately to the main node in a tree-like configuration, the method comprising:

periodically transmitting a local node information message from a first node, the local node information message comprising synchronization information pertaining to a clock of the first node and network tree information with respect to the first node, wherein the network tree information comprises an identifier of the first node, an address of the main node, number of node hops from the first node to the main node, information indicating remaining battery life of the first node, number of downstream nodes with respect to the first node, and maximum number of node hops from any node in the network to the main node;

at the first node, computing the period at which the first node periodically transmits the local node information message as A1*LneHopInterval+A2*BatteryLifeInterval+A3*LneCountInterval+A4*NumMbrInterval+random(LneXmtInterval), where A1 is a factor derived from the number of node hops from the first node to the main node divided by the maximum number of node hops from any node in the network to the main node, A2 is a factor derived from a remaining battery level of the first node divided by a maximum battery level possible at the first node, A3 is a factor representing a local node information message count staffed from 0 and incremented by one each time the first node transmits a local node information message and A4 is a factor representing the number of downstream nodes with respect to the first node, and where LneHopInterval, BatteryLifeInterval, LneCountInterval and NumMbrInterval are time interval values that are weighted by the factors A1, A2, A3 and A4, respectively, and random(LneXmtInterval) is a random function of a time transmit time interval quantity;

receiving at a second node that is not currently joined to the network the local node;

information message transmitted by the first node that is joined to the network;

said second node synchronizing to the clock of the first node based on the synchronization information contained in the local node information message and thereby becoming time-synchronized to the network; and

said second node determining whether to join the network at the first node based on the network tree information contained in the local node information message received from the first node.

2. The method of claim 1, wherein transmitting comprises broadcasting the local node information message from the first node to be received by any node in the network.

3. The method of claim 1, wherein transmitting comprises periodically transmitting the local node information message with a period that is dynamically changed according to the data routing responsibility of the first node.

4. The method of claim 3, wherein transmitting comprises periodically transmitting the local node information message with a period that is longer when the first node has more data routing responsibility.

5. The method of claim 1, wherein transmitting the local node information message comprises transmitting network tree information indicating the number of nodes associated with the first node that are downstream nodes with respect to the first node.

6. The method of claim 1, wherein receiving at the second node comprises receiving the local node information message from the first node and a local node information message from at least one other of the plurality of nodes, and wherein said second node determining comprises said second node determining to join at the first node or the at least one other node based on the network tree information contained in the local node information messages received from the first node and the at least one other node.

7. The method of claim 6, wherein said second node determining comprises said second node selecting one of the first node and the at least one other node that has the least data routing responsibility based on network tree information contained in the local node information messages received from the first node and at least one other node, which network tree information comprises a number of downstream nodes associated with the first node and with the at least one other node.

8. The method of claim 1, wherein upon said second node determining to join the network at the first node, said second node transmitting a join request message to the first node.

9. The method of claim 8, and further comprising transmitting a join acknowledgement message from the first node to the second node in response to receiving the join request message.

10. The method of claim 9, and further comprising receiving the join acknowledgement message at the second node from the first node.

11. The method of claim 10, wherein after receiving a join acknowledgement message from the first node, the second node acts like a candidate upstream node with respect to other nodes and transmits a local node information message comprising synchronization information pertaining to a clock of the second node and network tree information with respect to the second node.

12. The method of claim 10, wherein in response to receiving the join acknowledgement message at the second node, further comprising storing the network tree information contained in the local node information message received at the second node.

13. The method of claim 9, and further comprising at the first node transmitting information to its upstream node to update topology information for a sub-tree of the network associated with the first node due to the joining of the second node to the network at the first node.

14. The method of claim 8, and further comprising deleting the first node as an available upstream node if a join acknowledgement message is not received from the first node at the second node within a period of time after transmission of the join request message.

15. The method of claim 1, wherein the second node joins the network at the first node based on the local node information message and without any subsequent information message from the first node.

16. The method of claim 1, wherein receiving comprises receiving at the second node the local node information message when the second node is transitioning from a low power sleep mode in which the second node is not joined to the network to an awake mode in which the second node is capable of receiving the local node information message from other nodes.

17. A wireless network node device, comprising:

a receiver configured to receive signals from other nodes in a network;

a transmitter configured to transmit signals to other nodes in the network;

a processor coupled to the receiver and to the transmitter, wherein the processor is configured to;

generate a local node information message to be transmitted to other nodes, wherein the local node information message comprises synchronization information pertaining to a clock and network tree information, wherein the network tree information comprises a node identifier, an address of a main node, number of node hops to the main node, information indicating remaining battery life, number of downstream nodes, and maximum number of node hops from any node in the network to the main node;

compute a period at which the local node information message is to be periodically transmitted based on a formula A1*LneHopInterval+A2-BatteryLifeInterval+A3*LneCountInterval+A4*NumMbrInterval+random(LneXmtInterval), where A1 is a factor derived from the number of node hops to the main node divided by the maximum number of node hops from any node in the network to the main node, A2 is a factor derived from a remaining battery level divided by a maximum battery level possible, A3 is a factor representing a local node information message count started from and incremented by one each time the local node information message is transmitted and A4 is a factor representing the number of downstream nodes, and where LneHopInterval, BatteryLifeInterval, LneCountInterval and NumMbrInterval are time interval values that are weighted by the factors A1, A2, A3 and A4, respectively, and random(LneXmtInterval) is a random function of a time transmit time interval quantity; and

supply the local node information message to the transmitter for transmission.

18. A system comprising a first wireless network node device according to claim 17 and a second wireless network node device, the second wireless network node device comprising:

a receiver configured to receive signals from other nodes in the network;

a transmitter configured to transmit signals to other nodes in the network;

a processor coupled to the receiver and to the transmitter, wherein the processor is configured to;

analyze a received local node information message transmitted by the first wireless network node device that is joined to the network;

synchronize to the clock of the first wireless network node device based on the synchronization information contained in the local node information message to become time-synchronized to the network; and

determine whether to join the network at the first wireless network node device based on the network tree information contained in the local node information message received from the first wireless network node device.

19. The system of claim 18, wherein the processor of the second wireless network node device is further configured to transmit a join request message to the first wireless network node device, and to receive a join tree acknowledgment message from the first wireless network node device sent in response to the join request message, wherein in response to receiving the join tree acknowledgment message, the processor configures the second wireless network node device to serve as a candidate upstream node with respect to other nodes and transmits a local node information message comprising synchronization information.

20. The system of claim 19, wherein the processor of the second wireless network node device is further configured to delete the first wireless network node device as an available upstream node if a join acknowledgement message is not received from the first wireless network node device within a period of time after transmission of the join request message.

21. The wireless network node device of claim 17, wherein the processor is further configured to generate a message for transmission to an upstream node, the message containing updated network topology information for a sub-tree of the network associated with respect to the wireless network node device due to the joining of another node in response to receiving the local node information message.