## 4 Energy Balanced Strategies for Sparsely Deployed UWA-SNs
### Overview of EBH
Let \(E_{a}(s_{i},t)\) be the total energy dissipation of node \(S_{i}\) during time period of \(t\) rounds. **Lemma 1:** If \(E_{d}<E/m\), then \(RG(s_{i})-RG(s_{i-1})\leq 1\). **Proof :** Because \(E_{d}<E/m\), then any node transmitting one packet will dissipate less than one unit of energy. (1) We first consider the initial deployment. Each node is working in \(MODE0\), and forms a multi-hop network. We consider \(\forall S_{i}\in S(i=2,......,n)\), \(S_{i-1}\) and \(S_{i}\) are adjacent nodes in the linear network where \(S_{i-1}\) is closer to the sink, just as Figure 3 shows. \(S_{i-1}\) not only transmits its own sensed data but also relays \(S_{i}\)'s packets. So \(S_{i-1}\) has more packets to transmit than \(S_{i}\) during the same period of rounds. We denote \(E_{SEN}(k)\) as the energy consumption of sensing \(k\) bits message and \(E_{RX}(k)\) as the energy dissipation of receiving a \(k\) bits packet. Then, we have  
\[E_{a}(s_{i},t) = t\times E_{SEN}(k)+u\times\] \[(E_{RX}(k)+E_{TX}(k,r))+t\times E_{TX}(k,r)\] \[E_{a}(s_{i-1},t) = t\times E_{SEN}(k)+(u+1)\times\] \[(E_{RX}(k)+E_{TX}(k,r))+t\times E_{TX}(k,r)\]  
where \(u\) is the number of packets relayed by \(S_{i}\) during \(t\) rounds. Thus \(S_{i-1}\) dissipates energy more quickly than \(S_{i}\). As a result, \(S_{i-1}\) will first consume one gradation of energy and drop into the next energy grade. Then, it sends out a control message to \(S_{i}\). At that time, \(RG(s_{i1})-RG(s_{i-1})\leq 1\). (2) When \(S_{i}\) receives the control message sent by \(S_{i-1}\), it changes working mode to \(MODE1\) because \(S_{i}\) has higher grade number than \(S_{i-1}\), thus it sends data directly to the sink just as Figure 4 shows. We denote the time duration as \(v\) rounds before \(S_{i}\) dropping into the next energy grade. We obtain  
\[E_{a}(s_{i},v) = v\times E_{SEN}(k)+w\times E_{RX}(k)\] Figure 4:0 Figure 4:1  
where \(w\) is the number of packets relayed by \(S_{i}\) during the time period of \(v\) rounds. Because \(E_{a}(s_{i},v)\gg E_{a}(s_{i-1},v)\), before \(S_{i}\) dropping into the next energy grade and having the same grade with \(S_{i-1}\), the energy difference between them is diminishing, i.e., \(RG(s_{i-1})-RG(s_{i})<1\). (3) When \(S_{i}\) dropping into the next energy grade, it has the same grade with \(S_{i-1}\). We have \(RG(s_{i})-RG(s_{i-1})=0\). The result was proved. Next, using the **Lemma 1**, we have **Theorem 1**. **Theorem 1:** If \(E_{d}<E/m\), the optimum grades for linear network is given by \(m=min(\sqrt{\frac{nE}{2E_{C}}},\frac{E}{E_{d}})\). **Proof:** Let \(E_{C}\) be the energy spent on transmitting one control message to inform upstream node about its residual energy. We have  
Figure 4:2  
where \(c\) is the bits of one control message. Let \(E_{waste}(m)\) be the wasted energy which includes both the residual energy when the network collapses and the energy spent on sending control messages. Depending on different applications and the network lifetime definitions, when the network collapses, there are at most \(n-1\) nodes still alive. From **Lemma 1**, we know two adjacent nodes' residual energy at most differ one gradation of energy. Thus, we obtain  
Figure 4:3  
The derivative of \(E_{waste}(m)\) is  
Figure 4:4Let \(E^{\prime}_{waste}(m)=0\) then we have \(m=\sqrt{\frac{nE}{2E_{C}}},\quad(E_{d}<E/m)\). Thus, the optimum grade for linear network is  
Figure 4:5  
To make EBH practical, we should take other things into consideration before we present the algorithm in detail. First, how to set up the linear network in the initialization phase? It is easy to find node's neighbors and at the same time to set up the linear network. For example, at the initialization of the network, the sink can broadcast a neighbor-finding control message to its one hop neighbor. When the node nearest to the sink receives the control message, it answers the sink with ACK message. Then it relays the control message to its one hop neighbor.