## 2 Hybrid Charging Scheme
### Clustering and Cluster Head Centric Charging in the First Stage  
Popular clustering algorithms, such as the k-means algorithm [21], typically require a predetermined number of cluster heads. However, when the number of cluster heads is erroneously set, the clustering pattern deviates substantially from the visual classification.  
In this paper, a heuristic clustering algorithm devised specifically for this charging method is used. The clustering of the sensor nodes is executed by the mobile charger, since it knows the locations of the sensor nodes, and does not require signaling overhead between sensor nodes and the mobile charger. Each cluster head in a cluster is chosen by a maximum inclusion criterion. An inclusion circle is placed with its center at each sensor node location. As seen in Figure 2a, the sensor nodes associated with their respective inclusion circles have an identical radius \(R_{cl}\). As an example of the clustering process, let us focus on seven inclusion circles around the sensor node \(\text{SN}_{1}\) in the right-top section of Figure 2a. First, the number of sensor nodes within each inclusion circle is counted and compared with the others. Within its inclusion circle the sensor node with the index \(\text{SN}_{1}\) includes seven sensor nodes (six other sensor nodes and itself), and it has the largest number of sensor nodes of all inclusion circles in the figure. For this reason, \(\text{SN}_{1}\) is chosen as the cluster head and the other six sensor nodes become member nodes of this cluster. This can be mathematically described by  
\[\text{SN}_{1}=\underset{i}{\text{argmax}}N_{R_{cl}}(i),\qquad i=1,...,N_{T} \tag{5}\]  
where \(N_{R_{cl}}(i)\) indicates the number of sensor nodes within the inclusion circle of the \(i\)-th sensor node. At this point, the cluster head \(\text{SN}_{1}\) and its associated member nodes are no longer considered for further clustering. The sensor nodes classified into the first cluster are marked by the dim-colored dots in Figure 2b. When two sensor nodes have the same number of sensor nodes within their inclusion circles, the first cluster head is selected randomly. This procedure is then repeated to select the second cluster head, whose inclusion circle includes the largest number of remaining sensor nodes. Whole process of finding cluster heads is completed when all the cluster heads, the \(N_{cl}\) cluster heads, are found. Some sensor nodes such as \(\text{SN}_{3}\) and \(\text{SN}_{5}\) in the figure form single node clusters. As the cluster heads are mostly located at the centers of geographically grouped sensor nodes, the cluster head centric charging affects most of the member nodes, for both omnidirectional and directional transmissions of energy. In [22], a similar heuristic clustering method was used. For clustering, a grid is formed and only some grid points are chosen as the stopping positions of the mobile sink to collect the data from sensors. These stopping points can be considered locations of virtual cluster heads. Thus, stopping positions are not sensor node locations. In the case of our clustering method, locations of cluster heads are locations of some sensor nodes. In addition, in [22], a post processing to eliminate the redundant stopping positions was executed whereas our method has no such post processing.