# Energy Efficient Data Transmission for Sensors with Wireless Charging
## 4 Transmission in an Unlimited Number of Periods
### Problem with \(C=2e\)  
A \(\frac{3}{2}\)-approximation algorithm can be easily derived by receiving two periods of energy at one time and using Algorithm 4. We show a better algorithm in Algorithm 5.  
```
**Algorithm 4**FirstFitDecreasing (S)

**Theorem 6**: _Algorithm 5 uses no more than \(\frac{4}{3}OPT+1\) periods of energy._

Let OPT be the number of periods of energy used in an optimal solution. When all the packets are shorter than \(E\), transmitting these packets will not waste energy unless it is the last packet that can be transmitted as described in Lemma 3. Therefore, even if the energy charged in the last period is not used, it uses at most \(OPT+1\leq\frac{4}{3}OPT+1\) periods of energy.

We now consider the situation where there are packets longer than \(E\). Because the energy overflow happens only when transmitting a packet whose size is \(s_{i}>E\), the worst case is that energy overflow happens as many times as possible. The previous proof shows that transmitting two larger packets continuously may result in at most \(E\) units of energy overflow. Assume there are \(N\) packets that result in energy overflowing. Letting these packets be a set \(S\), i.e., \(|S|=N\), and the remaining packets be \(S^{\prime}\), then \(OPT\cdot E=\sum_{s\in S}s+\sum_{s\in S^{\prime}}s\).

If \(N\) is even, then at most \(\frac{1}{2}NE\) units of energy overflow, i.e., at most \(\frac{4}{3}\sum_{s\in S}s\) units of energy are used to transmit these \(N\) packets. The packets in \(S^{\prime}\) will not result in energy overflowing, but the last period of energy may not be used completely. Thus, transmitting larger packets first will use at most \(\frac{4}{3}\sum_{s\in S}s+\sum_{s\in S^{\prime}}s+E\leq(\frac{4}{3}OPT+1)E\) units of energy.

If \(N\) is odd, let the first \(N-1\) packets in \(S\) be \(S_{A}\), and let the last packet in \(S\) be \(s_{z}\). Obviously, \(S_{A}=N-1\) is even. Transmitting these packets uses at most \((N-1)\cdot 2E\) units of energy, and at most \(\frac{N-1}{2}E\) units of energy overflow. That is, at most \(\frac{4}{3}\sum_{s\in S_{A}}s\) units of energy are used to transmit the \(N-1\) packets. Note that, because the battery is empty initially, the global first transmitted packet \(s_{first}\) will not result in energy overflow (remember that \(s_{first}\in S^{\prime}\)). Transmitting these two packets \(s_{first}\) and \(s_{z}\) will use at most \(\frac{4}{3}(s_{first}+s_{z})\) units of energy. Then, it derives \(\frac{4}{3}(\sum_{s\in S_{A}}s+s_{z}+s_{first})+(\sum_{s\in S^{\prime}}s-s_{ first})+E\leq(\frac{4}{3}OPT+1)E\).

This completes the proof.

Similar to the previous section, after transmitting a larger packet, the remaining energy can be dedicated to transmitting some shorter packets. Such an improvement is described in Algorithm 6. In many cases, Algorithm 6 can improve energy utilization. However, in the worst case, it has the same energy utilization as Algorithm 5.
```
1:Input:\(S=\{s_{1},s_{2},\ldots,s_{n}\}\), assuming \(\forall s_{i}\leq C\)
2:Output: The assignment of \(S\) and \(k\)
3:Sort \(S\) in non-increasing order, and let the ordered sequence be \(s_{1}\geq s_{2}\geq\ldots\geq s_{n}\);
4:\(k=0\);
5:for\(i=1\) to \(n\)do
6:for\(j=1\) to \(k\)do
7:if\(Bin[j]\geq s_{i}\)then
8:\(assign(i)=j\); // assign item \(i\) to \(j\), corresponding to transmit packet \(i\) in period \(j\).
9:\(Bin[j]=Bin[j]-s_{i}\);
10:endif
11:endfor
12:if\(j>k\)then
13:\(k=k+1\);
14:\(Bin[k]=C\);
15:\(assign(i)=k\)
16:\(Bin[k]=Bin[k]-s_{i}\);
17:endif
18:endfor ```
**Algorithm 5** FirstFitDecreasing (S)