## 6 LECP-CP Analysis  
**Theorem 1:** The CH set generated by LECP-CP can cover all of the network nodes, and there is at most one CH within the cluster radius \(R_{a}\) of any CH. **Proof:**\(t_{i}=ratio(s_{i})\cdot T_{2}\cdot V_{r}\) according to Formula (4). Thus, we can obtain \(t_{i}<T_{2}\) since \(ratio(s_{i})<1\) and \(V_{r}<1\). That is, the waiting time \(t_{i}\) of any node \(s_{i}\) is smaller than \(T_{2}\). Thus, any expected CH will broadcast a \(Head\_Msg\) and become a CH before \(T_{2}\) expiring, which can avoid the generation of \"isolate points\". As we stated previously, Formula (4) ensures that different nodes have different waiting times. We assume that node \(s_{i}\) has a shorter waiting time than others and broadcasts the \(Head\_Msg\) within radius \(R_{a}\). Thus, all of the nodes within this range will give up the competition and become CMs. Therefore, there is no more than one CH within the radius \(R_{a}\) of any CH. **Lemma 1:** Given a maximal independent set \(S\) of an undirected connected graph \(G(V,E)\), if the number of nodes in \(S\) is no less than two, then there must exist at least one node in \(S\) within three hops of every node \(v\) in \(S\). **Theorem 2:** If the inter-cluster transmission range \(R_{inter-CH}\) and the intra-cluster transmission range \(R_{intra-CH}\) satisfy that \(R_{\mathrm{inter-}CH}\geq 3R_{\mathrm{intra-}CH}\), then the CH set generated by LECP-CP algorithm is a connected dominating set of the network. **Proof:** Firstly, we prove that the CH set \(S\) generated by LECP-CP algorithm is a dominating set. According to Theorem 1, there is no more than one CH within a cluster, so the CH set \(S\) must be an independent set. After the execution of the LECP-CP algorithm, each node in the network either is the CH, or the member node of one cluster, and any plain node adding to the cluster head set will destroy its independence; so, the CH set \(S\) is the maximum independent set. Since the maximum independent set is also a dominating set, the CH set generated by the LECP-CP algorithm is a dominating set of the network. Then, we prove that CHs in the dominating set \(S\) are connected if the inter-cluster transmission range \(R_{inter-CH}\) and the intra-cluster transmission range \(R_{intra-CH}\) satisfy that \(R_{\mathrm{inter-}CH}\geq 3R_{\mathrm{intra-}CH}\). According to Lemma 1, there must exist at least one cluster head node in \(S\) within three hops of any CH \(s_{i}\) of \(S\). Figure 3 depicts a case exhibiting the longest distance between two adjacent CHs. In this worst-case configuration, it is clear that when the transmission range \(R_{inter-CH}\) of a CH is not less than three-times \(R_{intra-CH}\), the overlay graph composed of CHs will be connected. **Lemma 2:** Suppose that the network area is \(A\) and the cluster radius is \(R_{a}\), then the expected number of CHs generated in the network is \(M_{\mathrm{exp}}=\left\lceil\frac{4A}{3\sqrt{3}R_{a}^{2}}\right\rceil\). **Proof:** Clusters generated by the clustering algorithm need to cover all nodes in the network, that is they need to cover the whole network. Since there are overlaps among clusters and there is only one CH in any cluster, thus when the overlaps among clusters are the most, the number of CHs achieves the maximum; to the contrary, there is the least number of CHs in the network when the overlaps among clusters are the least. BPEC [16] shows the cases of minimum cluster area and maximum cluster area, depicted by Figure 4. On these occasions, we can correspondingly obtain the maximum number of CHs \(M_{\mathrm{max}}=\left\lceil\frac{2A}{\sqrt{3}R_{a}^{2}}\right\rceil\) and the minimum number of CHs \(M_{\mathrm{min}}=\left\lceil\frac{2A}{3\sqrt{3}R_{a}^{2}}\right\rceil\), respectively. Since the maximum and minimum cluster area are both proportional to \(R_{a}^{2}\), thus we can deduce that the cluster area in the practical network is also proportional to \(R_{a}^{2}\).