## 3 Charging-Aware Multi-Mode Routing Protocol
### Charging-Aware Multi-Mode Routing Protocol (CMRP)
After then, the cluster heads send their data to the sink directly. The sunlight coverage transfers periodically. All sensors will reevaluate their current locations with the sunlight area when the location of sunlight coverage changes. At this time, each sensor can know which type it should be. In practical implementation, under-charging sensors can use message flooding to indicate the other sensors or the energy replenish rate can be applied to identify the corresponding type of each sensor. The algorithm is given in Algorithm 1. ``` n: the number of deployed sensors T: the time period that sunlight area changes Tr: the remaining time period that sunlight area will change S\({}_{\mathrm{S}}\): the sink node P(S): parent node of S according to the minimum-transmitting spanning tree cls(S): Type of sensor S p(S): the next propagation target of sensor S E(S): the remaining energy of the sensor S C(S, t): the amount of charging energy of sensor S after time period t Deep(S): the depth of S on the minimum spanning tree Initialization
1 Build the minimum-transmitting spanning tree with root in sink. 2 For each S,
3 stores the P(S),
4 set cls(S) according to the current location of sunlight Periodically update, triggered as current location of sunlight changes
1 For each S,
2 Update cls(S) according to the current location of sunlight
3 Z = [Sm] for all sensors Sm with cls(Sm) = {1, 2}
4 Link the sensors in Z as a circle by using the ring-based protocol. 5 Set the next hop of each sensor in Z according to the Equation (5)Chaining the Sensors in Circular with Multi-Level Convex Hull

The coordinates of sensors are the positions of the vertices on the Euclidean plane shown as Figure 1a. Chaining the vertices as a circle with minimal distance is known to be an NP-Complete problem. The heuristic method that randomly starts from a vertex and greedily selects the next one which has the shortest distance often creates a circle which at least two edges cross together like the CD and FG in Figure 1a. These cross edges indicate that at least one better solution exists to shorten the linking distance of the circle when the cross edges are removed. For example, the distance of the link C-D-E-F-G in Figure 2a is \(22+22+33+63=140\). However, if the link changes to C-F-E-D-G shown as Figure 2b, the cross edges CD and FG can be removed. The distance changes to \(29+33+22+17=101\). A cross edge removing method proposed in [24] requires great computation overhead as the number of vertices increases. Figure 1: _Cont._

Figure 2: Four cases to merge two adjacent circles. (**a**) the breaking edge of the inner circle is \(S_{y}S_{y+1}\) and the edge of outer circle is \(S_{x}S_{x+1}\). They are \(\overline{\mathrm{QP}}\) and \(\overline{\mathrm{OG}}\); (**b**) the breaking edge of the inner circle is \(S_{y}S_{y+1}\) and the edge of outer circle is \(S_{x}S_{x-1}\). They are \(\overline{\mathrm{QP}}\) and \(\overline{\mathrm{ON}}\); (**c**) the breaking edge of the inner circle is \(S_{y}S_{y-1}\) and the edge of outer circle is \(S_{x}S_{x+1}\). They are \(\mathrm{PM}\) and \(\overline{\mathrm{OG}}\); (**d**) the breaking edge of the inner circle is \(S_{y}S_{y-1}\) and the edge of outer circle is \(S_{x}S_{x-1}\). They are \(\overline{\mathrm{PM}}\) and \(\overline{\mathrm{ON}}\). Figure 1: Construct regular itinerary for mobile chargers. (**a**) chain the sensors starting from node A and greedily select the next one which has the shortest distance; (**b**) remove the cross edges CD and FG in (**a**) to shorten the total distance of chain; (**c**) construct multiple non-overlapped circles by using convex-hull algorithm; (**d**) merge the inner nodes G and H to adjacent outer convex-hull chain; (**e**) the final merged chain of the multiple non-overlapped circles in (c). The cross-edge problem occurs when the locations of the current vertex and next linked target are at the opposite side of an existing edge.