Description Title of Invention: NETWORK OF NODES, BATTERY-POWERED NODE AND METHOD FOR MANAGING BATTERY-POWERED NODE
Technical Field
[0001] This invention relates generally lo management of wireless networks, and par¬ticularly to management of heterogeneous multi-hop wireless networks including battery-powered nodes and mains-powered nodes. Background Art
[0002] Energy efficient management, such as routing of data packets, is a critical issue for networks including nodes with constrained power source. According to the power source of the node, the nodes can be classified into two categories, i.e., nodes with con¬strained power source such as battery-powered nodes (BPNs) and nodes with un-constrained power source such as mains-powered nodes (MPNs). In some applications, battery replacement is impractical or impossible. Therefore, in wireless networks including the BPNs, prolonging network lifetime becomes critical. The network lifetime is generally defined by the operation time of the battery powered node that first runs out of battery power.
[0003] Based on resource and capability of the node, the wireless networks can be classified into homogeneous and heterogeneous. In a homogeneous wireless network, all nodes have identical resources and capabilities. All nodes arc cither battery powered, or mains powered. A wireless sensor network is an example of homogeneous wireless network in which all nodes are typically battery powered. Electric smart meter network is another example of homogeneous wireless network in which all nodes are mains powered. On the other hand, in a heterogeneous wireless network, nodes have different resources and capabilities, e.g., some nodes can be battery powered and have small memory and limited computational capabilities, and other nodes can be mains powered and have greater memory and computational capabilities.
[0004] In a wireless network with battery powered nodes, a key objective of network
management, such as routing, is to maximize the network lifetime. A node consumes its energy for data transmission, data receiving, control message transmission and control message receiving. This category of energy consumption is considered as necessary energy use. A node also consumes its energy on idle listening, overhearing, collision and retransmission. This category of energy consumption is considered as energy waste. One of the main goals for the energy saving management is to minimize the energy waste.

10005] However, the energy related management methods designed for homogeneous
wireless network do not work well for heterogeneous wireless networks. For example, the routing methods designed for homogeneous networks do not consider and leverage heterogeneity. In addition, some methods reduce the energy consumption of the ho¬mogeneous network by synchronizing operations of the nodes of ihe network. See, e.g., U.S. patent 7,298,716 and U.S. patent 7,356,561 describing methods that use cen¬tralized sleep control mechanism in which a node can only sleep during a pre-specified time period. However, the synchronization of the network can reduce the collision of the data packets, but also can increase idle time resulting in additional energy waste. In addition, synchronization packet transmission and receiving also result in extra energy waste.
[0006] Accordingly, there is a need to provide a system and a method for energy efficient
management of heterogeneous multi-hop wireless networks including battery-powered nodes and mains-powered nodes. Summary of Invention
[0007] It is an object of various embodiments of the invention to provide a system and a method for energy efficient management of heterogeneous multi-hop wireless networks having at least one sink node and data nodes including battery-powered nodes (BPNs) and mains-powered nodes (MPNs). It is another object of some em-bodiments (o provide an energy efficient routing mechanism for transmitting packets in a multi-hop manner in which at least one data node exchanging the packets with the sink node through at least one intermediate data node relaying the packets between the data node and the sink node. Additionally or alternatively, it is an object of some em¬bodiments of the invention to provide a distributed sleep control model for such a het¬erogeneous wireless network that does not require synchronization of the operations of the nodes.
[0008] Some embodiments of the invention arc based on recognition that centralized
management is more advantageous for a homogeneous network than a heterogeneous network. This is because (he synchronization of (he network results in energy waste. For example, a centralized sleep control method can reduce the collision of data packets transmission, but also can increase idle lime of Ihe nodes, especially in situations when data transmission using mains-powered nodes is preferred.
[0009] Accordingly, some embodiments of the invention provide a distributed sleep
management model to manage sleep schedules of the data nodes of the heterogeneous network. For example, in one embodiment, the MPNs have only active periods, i.e., the nodes do not have sleep periods. In contrast, the BPNs have both (he active and sleep periods, but determine a schedule of the active and sleep periods independently from

ihe active and sleep periods of oiher data nodes in Ihe network or commands Iransmiiled by the sink node. For example, in some embodiments, the processor of the BPN determines the schedule based on information internal to the BPN using activities of the network sensed by the BPN. In combination with always active MPNs and energy efficient routing, this distributed sleep management mode! increases sleep lime ofthcBPNs.
L0010J Additionally or alternatively, some embodiments are based on a realization thai the
battery efficient routing of the data packets from a particular' data node lo the sink node should be via the routing path consuming the least battery energy. For example, some embodiments transmit the data packets along a routing path reducing a number of battery-powered nodes transmitting or receiving transmitted dala packets. Optionally, one embodiment determines an energy saving metric lo locale an energy efficient routing path. The energy saving metric can include one or combination of a power source (PS) metric identifying whether a data node is the BPN or the MPN, a battery-powered node count (BNC) metric storing a number of the BPNs along a routing path, a minimum battery level (MBL) metric storing a minimum level among the BPNs along ihe routing path, and a battery-powered overhearing count (BOC) metric storing a number of times that BPNs of the network receive and/or overhear the data packets transmitted on the routing path.
[0011 ] Accordingly, one embodiment of the invention discloses a network of nodes
including data nodes and at least one sink node, wherein the network is a wireless multi-hope network in which packets are exchanged between the sink node and the data nodes in a multi-hop manner such that there is at least one data node exchanging the packets with the sink node through at least one intermediate data node relaying the packets between the data node and fhc sink node, the data nodes include battery-powered nodes (BPNs) having active and sleep periods and mains-powered nodes (MPNs) having only active periods, wherein each data node transmits the packets only within corresponding active periods.
[0012J A BPN includes a transceiver for transmitting and receiving data packets; a processor for determining a schedule of active and sleep periods of the BPN independently from the active and sleep periods of other data nodes in the network and independently from commands transmitted by the sink node, wherein the processor switches the transceiver ON and OFF according to the schedule; and a battery for providing energy to the transceiver and the processor.
[00 J 31 Another embodiment discloses a battery-powered node (BPN) for forming a het¬erogeneous wireless multi-hope network of nodes including data nodes and at least one sink node, wherein Ihe data nodes include battery-powered nodes (BPNs) and mains-powered nodes (MPNs). The BPN includes a transceiver for transmitting and receiving

data packets; a processor for determining a schedule of active and sleep periods of the BPN independently from the active and sleep periods of other data nodes in the network and independently from commands transmitted by the sink node, wherein the processor switches the transceiver ON and OFF according to the schedule; and a battery for providing energy to the transceiver and the processor.
|0014] Yet another embodiment discloses a method for managing a battery-powered node (BPN) forming a heterogeneous wireless multi-hope network of nodes including data nodes and at least one sink node, wherein the data nodes include battery-powered nodes (BPNs) and mains-powered nodes (MPNs). The method includes determining a schedule of active and sleep periods of the BPN independently from the active and sleep periods of other data nodes in the network and independently from commands transmitted by the sink node; switching a transceiver of the BPN ON and OFF according to the schedule; transmitting a wakeup signal at the beginning of each active period; determining a routing path from the BPN to the sink node reducing a number of the BPNs transmitting or overhearing data packets transmitted on the routing path; and transmitting the data packets to a parent node starting the routing path during the active period. Brief Description of Drawings
[0015] [fig.lAjFigure 1A is schematic of a heterogeneous wireless network according to some embodiments of an invention;
I fig. IB] Figure IB is a block diagram of a structure of a data node in the network of Figure 1A;
[fig.2A]Figure 2A shows schematic of a battery powered node's sleep interval con-figuration according to some embodiments of an invention; [fig.2BJFigure 2B shows schematic of a distributed sleep management model according to some embodiments of an invention;
ffig.3A]Figure 3A depicts an example in which conventional routing algorithms shorten network lifetime by selecting a shorter path;
|fig.3B[Figure 3B depicts an example in which conventional routing algorithms shorten network lifetime by sending data packets to a node with higher battery level; |fig.4A]Figurc 4A illustrates how to count battery powered nodes along a routing path according to some embodiments of an invention;
[fig.4B]Figure 4B illustrates how to measure the minimum battery level along a routing path according to some embodiments of an invention; [fig.4C]Figure 4C shows an example of battery powered neighbors overhear packet transmission along a routing path according to some embodiments of an invention; [fig.5jFigure 5 depicts broadcast message transmission in wireless networks with dis-

Iributed sleep man age men l model according to some embodiments of an invention; [fig.6JFigure 6 shows an example in which selection of the mains powered node as next hop node to the sink actually consumes more battery power; [fig.7]F.igure 7 shows block diagram of routing path discovery according to some em¬bodiments of an invention; and
[fig.8]Figure 8 illustrates that with the distributed sleep management model, multi-hop long delay is possible. Description of Embodiments
3016] Figure 1A shows a schematic of an example of heterogeneous wireless network that uses embodiments of the inventions. The network includes data nodes such as battery powered nodes (BPNs) 100 and mains powered nodes (MPNs) 110. The network also includes sink nodes (S) 120. The nodes form a wireless mesh network using directed wireless links 130, where the general flow of data packets is from the data nodes (battery powered nodes or mains powered nodes) to sink nodes, although control messages can be sent in either direction.
3017] The network is a wireless multi-hop network in which packets are exchanged
between the sink node and the data nodes in a multi-hop manner such that there is at least one data node exchanging the packets with the sink node through at least one in¬termediate data node relaying the packets between the data node and the sink node. For example, some nodes, e.g., 140, can transmit data packets directly to a sink node. Some of nodes, e.g., 100 and 110, cannot directly transmit data packets to any sink node. Instead, the data packets are first transmitted to intermediate or relay nodes, which then relay the packets to sink nodes. In other words, data collection is conducted in a multi-hop manner. Hence, a routing algorithm must be provided to route data packets from nodes that cannot directly communicate with any sink nodes.
)018] Figure IB shows schematically a structure of the data node 101 forming the network of Figure 1. The node includes a transceiver for transmitting and receiving data packets, which includes one or combination of a receiver 150 and a transmitter 160. The node also includes a power source 180 for powering components of the node. According to a type of the power source .180. the nodes can be classified into two categories, i.e., the BPNs have constrained power source such as a battery and MPNs have un-constraincd power source, e.g., powered from a main or a grid. In some em¬bodiments, there is no restriction on power source of the sink nodes, which can cither be mains powered or battery powered.
)019] The data node 101 includes a processor 170 for performing operations of the node and/or for determining a schedule of active and sleep periods of the node. Each data node transmits the packets only during corresponding active periods.

[0020J According to some embodiments, the BPNs have active and sleep periods and MPNs have only active periods. If the data node 101 is a BPN, i.e., the power source 180 is a battery, then the processor determines the schedule of active and sleep periods of the BPN and switches the transceiver ON and OFF according to the schedule.
[0021] Distributed Sleep Management Model
Some embodiments of the invention are based on recognition that the centralized management is more advantageous for homogeneous rather than heterogeneous network. This is because the synchronization of the network results in energy waste. For example, a centralized sleep control method can reduce the collision of data packets transmission, but also can increase idle time of the nodes, especially in situations when data transmission over mains-powered nodes is preferred.
[0022] In various embodiments of the invention, the processor of the BPN determines the schedule independently from the active and sleep periods of other data nodes in the network and independently from any commands transmitted by the sink node. For example, the processor of the BPN determines the schedule based on information internal to the BPN using activities of the network observed by the BPN. For example, the data node 101 includes a memory 190 for buffering the data packets to be transmitted to the sink node. In one embodiment, the processor determines the schedule based on a number of the data packets in the memory, e.g., the active or sleep period is proportional to the number of the data packets in the memory.
[0023] Figure 2A shows a schematic of the distributed sleep management model according to some embodiments of the invention. In these embodiments, a BPN 200 manages its own schedule of active and sleeps intervals. Time is partitioned into sleep intervals with different lengths. An interval 205 includes an active period 210 followed by a sleep period 215. The order of active and sleep periods varies for different em¬bodiments. When BPN 200 goes to sleep, its transceiver is turned OFF. When the BPN 200 wakes up from the sleep, its transceiver is turned ON, and the BPN transmits a wakeup message 220 to inform neighboring data nodes that the BPN 200 is active. If the neighboring nodes have data packets to be sent to the BPN 200, then the neighboring node can initiate that transmission. The node dynamically determines the lengths of active period 210 and sleep period 215, i.e., the schedule of the active and sleep periods does not have to be periodic. For example, a sleep period 218 is shorter than sleep period 215.
[0024] Figure 2B shows schematic of a distributed sleep management model according to some embodiments of an invention. Different nodes can have different active period and sleep period lengths, in which battery powered nodes B| 225, B2 230 and B_; 235 have different length sleep periods 240, 245 and 250, respectively. [0025] With the distributed sleep management model, if a battery powered node has no data

lo transmit, then (he node schedules periodic sleep intervals. For example, nodes B2 230 and B3 235 have no data to transmit, and therefore, (hey perform periodic sleep scheduling. However, if a battery powered node has data to transmit lo another battery powered node, as in one embodiment, then the sender node waits for a wakcup message 220 from the recipient battery powered node. In this case, the sender node prolongs its active period. For example, the node B, has data to send to a battery powered node B2. Node B, extends its active period 255 and waits for a wakcup message from node B2. Upon receiving wakcup message 220 from node B2, node B| sends its data packet 260 to node B2. After transmitting data, node B, performs the sleep scheduling.
[0026] In one embodiment, the BPN uses two timers, a sleep timer and a wakeup timer, to manage its sleep schedule. The sleep timer is used lo schedule how long the node sleeps in a sleep interval and wakeup timer is used to schedule how long the node is awake in a sleep interval. A battery powered node determines its active period length and sleep period length dynamically. When the sleep timer expires, the battery powered node computes the active time value and starts the active timer. When active timer expires, the battery powered node computes the sleep lime value and starts (he sleep timer.
[00271 In some embodiments, the length of the sleep periods for the BPNs is limited and defined for a network. A battery powered node must set its sleep period length less than or equal to a maximal length. Similarly, a minimal active period length also can be defined for a network. A battery powered node must set its active period length greater than or equal to the minimal length.
[0028] With (he distributed sleep management model, mains powered nodes arc always
active. For example, the MPN 265 has an infinite active period 270. A node can send data packet to a mains powered node at any time. In some embodiments, the MPNs do not transmit wakeup message. Therefore, in some embodiments, the routing algorithm determines the lype of the data node.
[0029J Battery Energy Efficient Routing
Some embodiments are based on a realization that the battery efficient routing of (he data packets from a particular data node to the sink node should be via the routing path consuming the least energy. For example, some embodiments transmit the data packets along a routing path reducing a number of battery-powered nodes transmitting or receiving data packets.
[0030] For wireless networks, conventional routing metrics can be classified into two categories, node state metrics, e.g., a hop count and a node energy level, and link metrics, e.g., link quality and expected transmission count (ETX). These conventional routing metrics only consider measurements between two nodes or status of the node

itself. They do not utilize information along a routing path. As a result, those metrics work well for the homogeneous wireless networks without sleep nodes, but for the wireless networks with sleep nodes, (hose metrics can shorten the network lifetime.
[0031] Figure 3A shows an example in which BL - B3 are battery powered nodes and M, - M 4 are mains powered nodes. Sink node S 300 initiates path discovery by broadcasting path discovery message 310. A node N 320 receives path discovery message from two neighbors B3 330 and M4 340. With the conventional routing metric, node N selects path via B3 because path S—»B|->B2-»B3 is shorter than path S-^M,-^M2—^M^M;. However, path S-*B]—>B2—>B3 is composed of all battery powered nodes. On the other hand, path S—»M[ —»M2—»M3—»M4 is composed of all mains powered nodes. As a result, node N should select path via M4. A path with more battery powered nodes consumes more battery energy, and also has higher delay due to sleep of the battery powered node.
[0032] Figure 3B shows an example in which there is one sink node S 300, six battery
powered nodes B4 - By and one node N 310 (battery powered or mains powered). Node N discovered two paths to sink S, one path B»~->Bfi~>B4-»S and other path Bg—>B7—>B5 —>S. Node N has data packets to be sent to sink node S 300. Because node N cannot directly communicate with sink node S, node N must send its packets to either node BK 350 or B9 360. Since B8 has higher energy level 80% 370, conventional routing metric allows N send its packet to BR. However, the path via B* has lower battery powered node B6 380, which has battery level 18% 390. If node N sends its packets to sink S via BK, then node Bfl will run out battery power more quickly since B6 has to relay the packets sent by node N. Instead, node N should send its packets to B,j. The path via B,> has the lowest battery level 40% 395, which is much higher than B6's battery level. However, with conventional routing metrics, node N 320 does not know B(,'s battery level.
[0033] Accordingly, one embodiment determines an energy saving metric to locate an
energy efficient routing path. The energy saving metric can include one or combination of a power source (PS) metric identifying whether a data node is the BPN or the JV1PN, a battery-powered node count (BNC) metric storing a number of the BPNs along a routing path, a minimum battery level (MBL) metric storing a minimum level among the BPNs along the routing path, and a battery-powered overhearing count (BOC) metric storing a number of limes that BPNs of the network overhear the data packets transmitted on the routing path.
[0034] Battery-powered node count (BNC) of a path counts number of battery powered
nodes along a path. During routing path discovery, sink node sets BNC = 0 when the sink is mains powered. Otherwise, sink sets BNC - 1. A battery powered node increases BNC by 1 and a mains powered node does not change the value of BNC.

[0035] Figure 4A shows an example, in which sink S 300 sets BNC = 0, each of ballery
powered nodes B,, B2 and B3 increases BNC by I and mains powered nodes Mi and M2 don'l change BNC value. When routing path discovery message propagates lo node N 310 (ballery powered or mains powered), N knows there are 3 ballery powered nodes along this palh.
[00361 The Minimal Battery Level (MBL) of a path measures the minimal battery level among all battery powered nodes along a path. During routing palh discovery, sink node sets MBL - 100 when sink is mains powered. Otherwise, sink node sets MBL to its battery level. A battery powered node compares MBL contained in path discovery message with its own battery level. If its battery level is lower than MBL received, ihe node replaces MBL with its battery level. Otherwise, the node docs not change the value of MBL. Mains powered nodes do not change the value of MBL.
[0037] Figure 4B shows an example, in which sink S 300 sets MBL = 100, battery powered node Bi changes MBL = 60, ballery powered node B2 changes MBL = 50, battery powered node B3 and mains powered nodes M| and M2 do not change MBL value. When routing path discovery message propagates to node N 310 (ballery powered or mains powered), node N knows that there is at least one battery powered node along this path lhal has 50% of battery level.
[0038] Battery-powered overhearing count (BOC) of a path counts the total number of times ballery powered neighbors overhears packet transmission along the path. If a battery powered node is a neighbor of multiple nodes on the path, then this battery powered node is counted multiple times. In wireless network, when a transmitter sends a packet lo a receiver, all active neighbors of the sender receive the packet even though the packet is not destined to these neighbors. Therefore, routing algorithm must minimize the probability of overhearing. BOC is a metric can be used lo reduce ballery energy consumption on overhearing. During routing path discovery, each node indicates if it is mains powered or battery powered. Sink node sets BOC to its number of battery-powered neighbors (NBN).
[0039] In one embodiment, at each hop, node N (mains powered or battery powered) on the path updates BOC as following:
1) If the node N is ballery powered, it decreases BOC by 1 since previous hop node must count the node N as a ballery powered neighbor.
2) If previous hop node is battery powered, node N decreases its NBN by 1 since previous hop node is node N's battery powered neighbor.
3) Node N adds its updated NBN to the updated BOC and includes BOC in path discovery message.
[0040] Figure 4C shows an example, in which solid line 400 represents packet transmission and dash line 410 indicates packet overhearing by battery powered nodes. Node N 310

transmits packets to sink node S 300 (mains powered in the example) along a path N-*M2->B3->M|-*B2-*B1->S. Even though battery powered nodes B., - B9 are not on the routing path, these nodes receive the packets when the nodes are awake. As a result, their batteries are consumed. [0041] During routing path discovery, sink node S sets BOC = 2 since node S has B, and B4 as its battery powered neighbors. When B, receives path discovery message, it decreases BOC by 1, i.e., sets BOC = 1. B, has three battery powered neighbors B2, B4 and Bs. Hence, B, updates BOC to 4. When B2 receives path discovery message, (he node decreases BOC by 1, i.e., BOC = 3, B2 also decreases its NBN by 1, and finally, B2 sets BOC = BOC +1 = 4. Similarly, Mi, Bj and M2 update BOC. When routing path discovery message propagates to node N 310, node N sets BOC = 10. In this example, the nodes B4, B5> BB and By are counted twice. [0042J In heterogeneous wireless networks with sleep nodes, the routing algorithm needs to
refresh path level routing metrics frequently to reflect recent updates. [0043] New Node State Routing Metric
A conventional node state metric energy level is defined for homogeneous network in which all nodes arc battery powered. For heterogeneous network with both mains powered nodes and battery powered nodes, energy level metric does not indicate whether a node is mains powered or battery powered since at network startup all nodes have 100% of energy level. Therefore, a new node state metric called power source (PS) is used in some embodiments. For a node N, PS(N) = 1 indicates node N is mains powered and PS(N) - 0 indicates node N is battery powered. [0044] RPL Overview
To design a scalable routing protocol for Low-power lossy networks (LLNs), the Internet Engineering Task Force (IETF) Routing Over Low power and Lossy networks (ROLL) working group (WG) has standardized Routing Protocol for Low-power and lossy networks (RPL) as RFC 6550. RPL organizes nodes in LLNs as a Directed Acyclic Graph (DAG) and partitions the DAG into one or more Destination Oriented DAGs (DODAGs). There is one DODAG per data sink. [0045J To construct the topology of the DODAG and upward routes from nodes to a data
sink, the data sink acts as the root of the DODAG and broadcasts DODAG Information Object (DiO) messages to neighboring nodes. DIO messages contain the information to construct the DODAG. For example, three parameters of RPLInstancelD, DODAGID and DODAGVersionNumber arc enclosed to identify a DODAG version. The rank of a node defines the individual position of the node relative to other nodes with respect to the root of the DODAG. Nodes in the proximity of the data sink receive the DIO messages, determine their ranks when the nodes decide to join the DODAG, and transmit updated DIO messages to neighboring nodes. The ranks of the nodes are

contained in the DIO messages. DIO messages are propagated in all directions so (hat the DODAG topology is constructed in a wave front manner, until every node joins a DODAG. RPL uses Destination Advertisement Object (DAO) messages to build downward routes from data sink to other destinations. The DAO messages arc transmitted upwards from nodes to their parents or to the root. The DODAG In-formation Solicitation (DIS) message is used to solicit a DIO from a RPL node, that is, to discover new routes.
[0046] To achieve reliable routing, RPL allows a node to have multiple parents using the DODAG structure for determining the next hop for data packet forwarding. One of parents is selected as the preferred parent and others as backup parents. The preferred parent is used as default next hop for packet forwarding. If the preferred parent is un¬available, then the backup parents can be used. RPL uses Objective Functions (OF) for assisting nodes to determine ranks and select parents.
[0047] A routing algorithm uses control messages to discovery routing paths. For example, AODV uses route request (REQ) message and route reply (REP) message for route discovery. RPL uses DIO message for upward routing path discovery and uses DAO message for downward routing path discovery. Propagating routing path discovery message is challenge in the heterogeneous wireless networks consisting of sleep nodes. In the networks without sleep nodes, a node broadcasts a route discover message, all neighbors receive the broadcasted message. However, in the networks with the dis¬tributed sleep nodes, some neighbors sleep and some neighbor are awake. Sleep neighbor can't receive any message.
[0048] With the centralized sleep control, control node determines when a node sleeps and when it is active. However, with the distributed sleep model, such scheduled sleep and active information is not available. Only information available is that a sleep node transmits a wakeup message when it wakes up. For unicast packet, sender can wail until it receives the wakeup message from the receiver. But broadcast and multicast messages are different. They arc destined to multiple receivers. The most of routing path discovery messages such as DIO in RPL are broadcast messages. For network connectivity, every node must receive such broadcast message. Otherwise, the node is isolated from the network. Therefore, for the important broadcast message, sender must guarantee to deliver the message to all neighbors.
[0049] One method to deliver a broadcast message to a]] neighbors with the distributed sleep management model is to transmit the broadcast message for

limes. These RTX transmissions are uniformly distributed over a lime period called Broadcast interval. The length of broadcast interval is MinActivePeriodLength + MaxSleepPeriodLenglh. During these transmissions, the transmitting node may go to sleep after each retransmission and wakes up for next retransmission. Upon waking up, a transmission node may not send wakcup message. With RTX retransmissions, every neighbor is guaranteed to receive at least one copy of the broadcast message. For du¬plication detection, the transmitting node includes a sequence number in a broadcast message and all RTX retransmissions have same sequence number so that receiving nodes can determine if the broadcast message is duplicated. This broadcast message transmission method is more efficient when MinActivePeriodLength is relatively large so that RTX is relatively small. Figure 5 shows an example, in which node N 500 (mains powered or ballcry powered) is the DIO transmission node and node B i 510 and B2 520 arc two battery powered neighbors of node N. Node B, has a sleep period 540 longer than node B2's sleep period 550. In this example, MaxSleepPcriodLcngth = 2*MinAclivePeriodLength, therefore RTX = 4. Four DIO transmissions 560 are uniformly distributed over a broadcast interval 570. Node Bj receives two copies of the DIO message and node B2 receives one copy of the DIO message.
[00501 Another method to deliver a broadcast message to all neighbors with the distributed sleep management model is that transmission node stays awake for a broadcast interval. At the beginning of the broadcast interval, transmission node transmits the broadcast message once to make sure all mains powered neighbors receive the broadcast message. During the broadcast interval, the transmission node transmits the broadcast message once every time the node receives a wakcup message from a battery powered neighbor. With this method, transmission node transmits the broadcast message for NBN + 1 limes. Similarly, for duplication detection, transmission node includes a sequence number in the broadcast message and all retransmissions have same sequence number. This broadcast message transmission method is more efficient if transmission node has fewer ballery powered neighbors.
10051J Routing algorithm can adaptivcly use cither method for different node by comparing RTX and NBN. RTX is same for all nodes in the network, but NBN is node dependent since different node may have different numbers of battery powered neighbors. A mains powered neighbor receives RTX or NBN+i copies of the same broadcast message.
[0052] Routing Palh Discovery in Heterogeneous Networks with Sleep Nodes
In a heterogeneous wireless network with both mains powered and battery powered, it is not always energy efficient to select mains powered node as next hop node. Figure 6 is an example, in which sink node is S 600. Battery powered node Bs 610 selects mains powered node Mj 620 as next hop node since M,is a mains powered node. The

selected path B5—>M]—>Bf)—>B2—>S actually consumes more battery power since two battery powered nodes B2 630 and B() 640 are on the path. Instead, B5 should select B2 as its next hop node even B2 is a battery powered node. Path B5—>B2—>S is more energy efficient than path B5-^Mi->B6^B2-*S.
[0053] Existing routing algorithms are not designed for heterogeneous networks with both mains powered and battery powered nodes, especially not for distributed sleep management model. New routing functions must be provided.
[0054] Take RPL for example, RPL doesn't support sleep nodes. To support sleep nodes, besides the conventional routing metrics defined by RPL, new metrics BNC, MBL, BOC and PS must be carried in DIO message. With these metrics, many ways can be used to as criteria to select parents and compute rank. The energy efficient methods are provided in following paragraphs. RPL uses DIO message propagation to discover upward routing paths. DIO message is originated by sink node. During DIO propagation, each node selects one default parent and multiple backup parents if these backup parents are available.
[0055] Figure 7 shows RPL with provided routing path discovery method supporting newly introduced battery power efficient routing metrics. When a node receives a DIO message 700, it checks 705 if this DIO is for a new DODAG or existing DODAG. If DIO is for a new DODAG, node decides 710 whether it joins this DODAG or not. If the node does not join new DODAG, the DIO message is discarded 715. If the node joins the DODAG, DIO is processed 720. If BNC is equal to zero 725, the node sets the DIO sender as its default parent 730, computes a rank for itself, schedules 735 a DAO transmission, and starts 740 to transmit DIO by using one of the broadcast message transmission methods provided above. If BNC is not zero, the node selects DIO sender 745 as a parent, but does not compute rank. Instead, the node starts 750 a timer to wait for more preferred DIOs. If the DIO is for an existing DODAG, the node has selected a parent already. So, it checks 755 if a rank is computed. If yes, it checks 758 if its rank is greater than the rank contained in DIO message. If no, DIO is discarded 715. If yes, it checks 760 if enough parents arc selected, if no, the node adds 765 the DIO sender to its parent set, if yes, node updates 770 its parent set by replacing one of the parents if this DIO contains a better routing path. If rank is not computed and this DIO has 775 a BNC = 0, node sets 780 the DIO sender as default parent, cancels 785 DIO waiting timers, compute 790 a rank and update parent set by replacing one of existing parents if enough parents are selected, schedules 735 a DAO transmission and starts 740 to broadcast DIO. If DIO has a BNC > 0, the node adds DIO sender 760 to its parent set if no enough parents arc selected or otherwise updates 770 its parent set if enough are parents selected. When timer expires 795, node selects 798 one parent from parent set as default parent and computes a rank, schedules 735 a

DAO transmission and starts 740 DIO message transmissions.
[0056] To update the parent set, criteria need to be defined to determine one path is better
than another path. There are different ways to define one path is better than other path. A path with smaller BNC is considered better than a path with large BNC if other metrics are similar. A path with greater MBL is considered better than a path with large smaller MBL if other metrics are similar. A path with smaller BOC is considered better than a path with large BOC if other metrics arc similar. A path with the first hop node being mains powered is considered better than a path with the first hop node being battery powered if other metrics are similar.
[0057] Disclosed invention provides a method to determine a better path. For each parent candidate P, node calculates a parent qualification value Q(P) as follows
[0058] A smaller Q(P) value indicates a belter path. A node uses equation (2) to update its parent set. When DTO timer expires, node selects a parent with the least Q(P) value as default parent. In case of lie, node uses PS to break the tie. If PS cannot break the tie, the conventional routing metric defined by RPL is used to break the tic.
[0059] With conventional and new routing metrics, there are many ways to compute a rank
for a node. Following is a rank computation method incorporates four new metrics into
conventional rank computation:
R = RD + R, + CBNC * BNC + CMBL * MBL + CB0C *BOC+Cps*(l-PS(DP)), (3)
where Rn is the rank of default parent (DP), R, is the rank increase computed by using conventional RPL routing metrics and object functions, CBNC, Cum,, CBOC. and C PS are the coefficients to reflect the importance of BNC, MBL, BOC, and PS, re¬spectively. These coefficients should be selected such that a node has a smaller rank if it discovers better default path. Otherwise, the node has a larger rank.
[0060] With (he provided parent selection method, a node selects multiple parents. In other words, the node discovers multiple routing paths towards a sink node. The node ad¬vertises the best routing path discovered in its DIO message. For example, if a node discovered two routing paths to a sink node, one path with BNC = 0 and other path with BNC = 2, the node will advertise path with BNC = 0.
[0061 ] Even (hough RPL is used as example to discover battery power efficient routing paths, the provided methods can be applied to any routing algorithms.
[0062] Idle Listening Time Reduction
Figure 8 shows an example, in which battery powered nodes B0, B,, B2> ..., Bjs. use same active period length and sleep period length. Node B, has data packet to be sent to node B0, but Bs jusl misses the first wakeup message 800 from B(1, Bt waits for next

wakcup message 810 from node B0 and transmits packet 820 lo B„. Similarly, node B2 has dala packet to be sent to node B,, but B2 also just misses the first wakcup message 800 from Bl5 so node B2 wails for next wakcup message 810 from B, and iransmils packet 820 to B,, and so on. In this sequence, wailing time for B! = AclivePeri-odLcngth + SlcepPcriodLcngth, waiting time for B, == ActivePeriodLcngth + 2*SleepPeriodLcngth, ..., wailing time forBN '- ActivePeriodLcngth + N*SlccpPcriodLenglh. If active period length is 10 seconds and sleep period length is 90 seconds, node B5 wails for approximately 460 seconds.
[0063] In some embodiments of the invention, the routing algorithm manages (he schedule of the active and sleep periods of BPNs to also reduce idle listening time resulting in more energy consumption. To reduce idle listening time in distributed sleep model, in some embodiments the transmission node is not required to wait until a wakeup message from the receiver node is received. Different embodiments use one or com¬bination of different methods to reduce idle listening time.
[0064] For example, the number of packets in the buffer is one parameter that can be used to reduce idle listening. If there arc more packets in the buffer to be transmitted, then transmission node can wait for a longer timer. Otherwise, transmission node waits for a shorter time, and if no wakcup is received, the transmission node goes to sleep. Therefore, the idle listening lime can be set to be proportional to the number of packets in the buffer.
[0065] Overhearing is another way to reduce idle listening time. Wireless medium is a shared medium. Any transmission overheard from receiving node indicates thai receiving node is awake, and therefore transmission node can send packets to receiving node. For example, according to RPL protocol, a RPL node transmits DIO based on a trickle timer algorithm. It is pseudo periodic transmission. If transmission node overhears a DIO message from receiving node, then receiving node is awake. Also a node in the network needs to transmit its dala lo the sink.
[0066] The active notification is another method to reduce idle listening time. While a transmission node is waiting for wakeup message from its receiver, there might be other nodes that are waif jng for the wakcup message from this transmission node. Therefore, if a transmission node is waiting for some lime, it can dynamically send an active notification signal to let its neighbors know that it is awake so that neighbors can send their packets to it if they have such packets.
[0067] The battery level also needs lo be considered in idle listening time management.
Define a battery level threshold BLTH. If a battery node's battery level is less than BLnj , this battery node is in critical condition. Therefore, the battery node should set its active period to the minimum active period and sets its sleep period lo the maximum sleep period. However, if a battery powered node has a battery level much higher than

Ihe MBL it collected, this ballery powered node can set idle listening lime longer.
[0068] Battery Energy Efficient Data Packet Transmission
With the sleep nodes, transmission of data packet is different from the case without sleep nodes, where the receiver is always awake, and the transmission node can send packets to the receiver at any timer. With sleep nodes, the transmitter must make sure thai the receiver is awake in order to send packets. With conventional centralized sleep control, transmitter and receiver arc scheduled so that they sleep and wake up simul¬taneously, that is, if the transmitter is awake, the receiver must be awake. Therefore, (he transmitter can send packets to receiver as long as the receiver is awake. However, with the distributed sleep model, transmitter and receiver sleep and wake up inde¬pendently, thai is, when transmitter is awake, Ihe receiver may be asleep. Therefore, routing algorithm must efficiently manage data packet transmission to avoid packet loss and save battery power.
[0069] In conventional RPL, a node always sends data packets to its default parent.
However, with the distributed sleep model, a node cannot always send packets to its default parent since the default parent may be asleep. The node can wait for its default parent to wake up, but waiting consumes energy and also increases data delay. The efficient way is that a node can send data packets to any parent that is awake. If no parent is awake, the node may go to sleep or wait by using sleep management method described above.
[0070] For battery power efficiency, a transmission node must determine to which parent it should send packets if multiple parents arc awake. To determine a preferred parent, the battery energy consumption along a path via each active parent must be estimated. A transmission node then selects a path via an active parent that consumes the least battery energy. The estimation of battery power consumption along a routing path is described in following paragraphs.
[0071] With the distributed sleep management model, the probability of a battery powered
node B awake is
AclivePei'iodLertqth(B)
p (B) - ■■■■■ ■ f41
a^ J Active Per iodlength{B) + SleepPeriodLen,qth{B) ' }
[0072] Assume power consumptions for transmitting and receiving a data packet arc P, and Pr, respectively, power consumptions for transmitting and receiving wakeup message are W, and Wr, respectively. For a battery powered node B, Pi(B) denotes battery power consumption on idle listening to wail for a wakeup message from a ballery powered receiving node before packet transmission.
[0073] There are three steps to estimate battery power consumption along a path for a transmission node to deliver data packets to a sink node.
[0074] Step 1: Compute battery power consumed by transmitting a packet from a node to

another node
a) Battery power consumed by transmitting a packet from a battery powered node B, to
a battery powered node Br is
P(Br_,Br)
.v,.
= (PiW + Wr + K + Pt+ Pr) + ^ Pa(BB*)
k = i
,v,
*Wr+YiPa(BBit)*Pr, (5)
where Nr is total number of battery neighbors of node Br without including node B„ BB rk(k ~ 1 to Nr) are node Br's battery neighbors without including node Bt, Nt is total number of battery neighbors of node B, without including node Br and BB,J (j - I to Nt) arc node B,'s battery neighbors without including node Br.
b) Battery power consumed by transmitting a packet from a mains powered node M, to
a battery powered node Bt is
P(Mt,Br)
■Vr
=(wt+pr)+YJF«(BB'<-)*w>-
k-i ft
+ ^/J„{SJVf/)-Pr, (6)
;=i
where N,. is total number of battery neighbors of node Br, BB,k (k = 1 to Nr) are node Br
's battery neighbors, N, is total number of battery neighbors of node M, without
including node Br and BM,i(j - 1 to N,) arc node M/s battery neighbors without
including node Br.j
c) Battery power consumed by transmitting a packet from a battery powered node B, to
a mains powered node Mr is
j = l
where N, is total number of battery neighbors of node B, and BB,J (j = 1 to NL) arc node B,'s battery neighbors.
dj Battery power consumed by transmitting a packet from a mains powered node M, to a mains powered node M,. is
7 = 1
where Nr is lota] number of battery neighbors of node M, and BM,J (j = 1 to N,) arc node M,'s battery neighbors. [0075J Step 2: Compute battery power consumed by transmitting a packet from a source node to a sink node.

[0076] Along a path from source node N (mains powered or battery powered) to sink node S (mains powered or battery powered), assume there are B2B transmissions from battery powered node to battery powered node, M2B transmissions from mains powered node to battery powered node, B2M transmissions from battery powered node to mains powered node, and M2M transmissions from mains powered node to mains powered node. Using equations (5) - (8), the battery power consumed by transmitting a packet from a source node N to a sink node S is given by
BIB M2B
P(N,S) - y P(B[,B!.) + ^ P(M;,BJ)
1=1 j=-l
BitA M2M
+ YiJ(fif,M*)+ V P{M\,M±). (9)
|0077 j Step 3: Compute the maximum value and the minimum value of P(N,S) along a path.
[0078] For a specific routing path from a source N to a sink node S, even though the number of battery powered nodes and number of mains powered nodes arc fixed, the layout of these nodes affects the battery energy consumption. Including source node N and sink node S, assume there are NB battery powered nodes B,, B2, ..., BNij and NM mains powered nodes M[, M2, ..., MNMon the path. The maximum battery energy con¬sumption occurs when all mains powered nodes arc at the beginning of the path followed by all battery powered nodes, that is, M]-»M2—»...—»MNM—>Bi—»B2—»...—»B NB. Therefore, max{P(A',.S))
NM-- V P{MJ,M.i) + l>{Mt,Br~)
.VR-!
+ ^ P(Dr^r)- (10)
[0079] The minimum battery energy consumption occurs when battery powered nodes and mains powered nodes arc interleaved. If NM >= NB, the minimum battery power con¬sumption layout is Bj->M|—>B2—>M2->...->BNB-*MiNB-*MNB4-i->---~>MNM and if NM < NB, the minimum battery power consumption layout is B,—>M,—>B2—>M2-»...—»BNM
-»MNM-»BNM+|-»...-»BNB. Therefore, if NM >= NB min{P(;V,5))
Nil NB- 1
^YP(S;,M;)+ V p{MJtlBJ.}
VW-ft'K
+ y P{M*,M*) (Ha)
andifNM