## 3 Charging-Aware Multi-Mode Routing Protocol
### Charging-Aware Multi-Mode Routing Protocol (CMRP)
This paper proposes a new vertices connection method by creating multiple non-overlapped circles from outer to inner similar to the concentric circles named multi-level convex hull circle (MCC). Then all these circles are linked into an irregular big cycle. Let \(\Psi\) be the set of vertices on the plane. The convex-hull algorithm is applied to find the smallest set of vertices \(\Omega_{1}|\Omega_{1}\subset\Psi\) which can enclose all vertices in \(\Psi\). The set \(\Omega_{1}\) in the example of Figure 1 organized the circle A-F-E-Q-P-M-L-J shown as Figure 1c. Next, the vertices in \(\Omega_{1}\) are removed from \(\Psi\) and \(\Psi=\Psi-\Omega_{1}\) and the vertices set \(\Omega_{2}\) which encloses the remaining vertices in \(\Psi\) are computed in the same procedure. The vertices organized the circle B-C-D-O-N-I-K are included in set \(\Omega_{2}\) shown as the inner circle in Figure 1c. This procedure continuously removes the vertices from \(\Psi\) until \(|\Psi|\leq 2\). Assume that the last set including the remaining vertices in \(\Psi\) be \(\Omega_{k}\). Let \(\Pi\) be the final circle containing all vertices in the network. If all vertices are removed from set \(\Psi\), \(\Pi\) is initially set to \(\Omega_{k}\). On the contrary, if the last \(\Psi\) is not empty, \(\Pi\) is initially set to \(\Omega_{k-1}\) and all remaining vertices in \(\Omega_{k}\) are inserted into \(\Pi\). To minimize the linked distance of the final circle, the concatenation position of each vertex in \(\Omega_{k}\) is the location that generates minimum distance. Therefore, for each vertex \(S_{u}\subset\Omega_{k}\), and each vertex \(S_{v}\subset\Pi\), the insertion point on the circle \(\Pi\) is at the vertex with minimum \(|S_{u}S_{v}|\). The \(S_{u}\) can be inserted in to the circle \(\Pi\) before or after the vertex \(S_{v}\). The decision is computed according to (7). \[\min(|S_{u}S_{v}|+|S_{u}S_{v+1}|-|S_{v}S_{v+1}|,|S_{u}S_{v}|+|S_{u}S_{v-1}|-|S_ {v-1}S_{v}|) \tag{7}\]

As the example in the Figure 1d, all vertices in \(\Omega_{2}\) are initially added into set \(\Pi\). Vertex G is one of the remaining vertices in \(\Psi\) and the closest vertex in set \(\Pi\) is D. The vertices before and after G are C and O respectively. The distance cost for inserting G between D and O is 27 and the cost is 29 if G is inserted between C and D. According to (7), vertex G is inserted into the circle \(\Pi\) at the position between C and O. The insertion position of vertex H is similar and the position is between I and N.

The next circle to merge with \(\Pi\) is adjacent one. The merge procedure starts from inner circles to outer ones sequentially. To merge two circles into a big one, both the circle \(\Pi\) and its adjacent circle need to break an edge. Then the two ends of their break edges are linked with each other. Let \(\Omega_{j}\) be the vertices set of the adjacent circle. Let \(S_{x}\subset\Omega_{j}\) and \(S_{y}\subset\Pi\). The edge that generates minimum \(|S_{x}S_{y}|\) is the candidate one to be selected as one of the merged edge. When edge \(S_{x}S_{y}\) is selected, the other merged edge has four possible cases. They are \(|S_{x+1}S_{y+1}|\), \(|S_{x+1}S_{y-1}|\), \(|S_{x-1}S_{y+1}|\), and \(|S_{x-1}S_{y-1}|\). The vertices \(\{S_{x-1},\,S_{x+1}\}\subset\Omega_{j}\), and each of them represents the vertex in front of and in back of the vertex \(S_{x}\) in the circle \(\Omega_{j}\). Similarly, the \(\{S_{y-1},\,S_{y+1}\}\subset\Pi\), they represent that of the \(S_{y}\) in the circle of \(\Pi\). The other edge is determined by the (8)

\[min\left( \begin{array}{c}S_{x}S_{y}|+|S_{x+1}S_{y+1}|-|S_{x}S_{x+1}|-|S_{y}S _{y+1}|\\ S_{x}S_{y}|+|S_{x+1}S_{y-1}|-|S_{x}S_{x+1}|-|S_{y-1}S_{y}\\ S_{x}S_{y}|+|S_{x-1}S_{y+1}|-|S_{x-1}S_{x}|-|S_{y}S_{y+1}\\ S_{x}S_{y}|+|S_{x-1}S_{y-1}|-|S_{x-1}S_{x}|-|S_{y-1}S_{y}|\end{array} \right) \tag{8}\]

The procedure continues and does not stop until all circles are included into the set \(\Pi\).