# Energy Efficient Data Transmission for Sensors with Wireless Charging
## 3 Transmission in Limited \(K\) Periods
### A Simple Problem with \(C=e\)  
When \(C=E\), the energy received in each period is the same as battery capacity. In our assumption, all the data will be transmitted to the base station and no data will be discarded, so we need to transmit as much data as possible in order to completely make use of the received wireless energy without energy waste. Note that, because all the data will be transmitted, it prefers to transmit more data, rather than more packets. In the example illustrated in Figure 3, 20 units of data will be transmitted in two periods if the transmitted order of the packets is as that in Figure 2(a), while 19 units of data will be transmitted in two periods in Figure 2(b), and only 15 units of data can be transmitted in two periods in Figure 2(c). If we want to transmit as much data as possible, we need to charge the battery to as full as possible. It is better to leave no residual space in one period, which may result in energy overflowing in the next period. This problem is NP-Complete that is a class of problems which are hard to solve. One instance of this problem can be represented as the Partition problem, which is NP-Complete. The Partition problem is to partition a set of \(n\) integers \(\{a_{1},a_{2},...,a_{n}\}\) into two subsets \(A_{1}\) and \(A_{2}\) such that the sums of both subsets equal to each other, i.e., \(\sum_{a\in A_{1}}a=\sum_{a\in A_{2}}a\). Throughout this paper, we use filling battery with packets to denote transmitting packets using one battery of energy, and filling period with packets to denote transmitting packets using one period of energy for simplicity. Intuitively, filling the battery with larger packets first would be a good solution. Figure 4 gives an example, \(S=\{16,16,3,3,2,2,2,2\}\), \(C=20\), \(E=20\) and \(K=2\). It only wastes two units of data in this example as shown in Figure 4. This method provides 2-approximation as shown in Theorem 1. **Theorem 1**. : _Filling battery with larger packet first is a 2-approximation algorithm._  
Proof. : The method is described in Algorithm 1. Let OPT be an optimal solution that \(K\) periods of energy are all filled with packets, and no energy is wasted. Then, the amount of data that is transmitted in OPT is \(KC\). We will prove the theorem by proving that the amount of transmitted data in Algorithm 1 is at least \(\frac{K\cdot C}{2}\). For \(k=1,2,...,\lfloor\frac{K}{2}\rfloor\), it is easy to find out that the total amount of data filled in battery \(2k-1\) and \(2k\) is more than \(C\), that is,  
\[\sum_{i:trans(i)=2k-1}s_{i}+\sum_{i:trans(i)=2k}s_{i}>C. \tag{1}\]  
This is easy to understand because, if the total amount of data filled in battery \(2k-1\) and \(2k\) is less than \(C\), then it does not have to fill the data into two batteries, and it only needs to fill the data in one battery (\(2k-1\) or \(2k\)). Summing Inequality (1) up, we have  
\[\sum_{i:trans(i)=\{1,2,...,2,\lfloor\frac{K}{2}\rfloor\}}s_{i}>\lfloor\frac{K} {2}\rfloor C. \tag{2}\]  
If \(K\) is even, we have  
\[\sum_{i:assign(i)=\{1,2,...,K\}}s_{i}>\frac{K}{2}C. \tag{3}\]  
Otherwise, if \(K\) is odd, we only need to consider whether half of the last battery is filled. Because we fill the packets in decreasing order, we always select a packet with a larger size first. Assuming less than half of the last battery is filled, and letting the size of the last packet packed in this battery be \(s_{x}\), there must exist a packet with size \(s_{y}<s_{x}\leq\frac{C}{2}\), and we can fill this packet into this  
Figure 4: An example, (**a**) optimal solution; (**b**) larger packet first. battery, which contradicts the fact that \(s_{x}\) is the last packet packed in this battery. Thus, at least half of the last battery is filled. Therefore, when \(K\) is odd, we still have  
\[\sum_{ixtrans(i)=\{1,2,\cdots,K\}}s_{i}>\frac{K}{2}C. \tag{4}\]  
This completes the proof. A tight example is given as \(S=\{5+\epsilon,5+\epsilon,5+\epsilon,5,5,5,5,5\}\), \(C=10\), \(E=10\) and \(K=3\).