# A Cluster-Based Dual-Adaptive Topology Control Approach in Wireless Sensor Networks
## 3 The Improved Clustering Scheme
### Design Issues of the ICV-MIMO Scheme  
We first discuss the connectivity of cluster-based graph consisting of MCHs, SCHs, FCHs, and cluster members:  
**Theorem 1**. : _For any link \(i\!\!\rightarrow\!\!j\) in a connected network formed by the ICV-MIMO scheme, where the MCHs of node \(i\) and \(j\) are node \(u\) and \(v\) respectively, if there exists the inter-cluster link \(u\!\!\rightarrow\!\!v\) in the network, the clustering ranges of node \(u\) and \(v\) are at most \(d_{u,max}/3\)._  
Proof. : If there exists the inter-cluster link \(u\!\!\rightarrow\!\!v\) in the network, the distance between \(u\) and \(v\) (i.e., \(d_{u,v}\)) is not more than \(d_{u,max}\). According to Lemma 1 in [3], the MCHs of any two neighboring nodes in a connected network are either identical or are within range of 3 times the size of clustering range. Since node \(j\) is the neighbor of node \(i\) and node \(v\) (i.e., the MCH of node \(j\)) is the neighboring MCH of node \(u\) (i.e., the MCH of node \(i\)), the clustering ranges of node \(u\) and \(v\) are not more than \(d_{u,max}/3\). Hence, the theorem is proven. The following theorem claims the intra-cluster connectivity of the graph consisting of MCHs, SCHs, FCHs, and cluster members. **Theorem 2**. : _In any cluster with the MCH \(u\), the SCH \(v\), and the FCH \(w\), if any cluster member's maximum transmission range is not less than \(2\mu\!\cdot\!R_{u,av}\), the probability that it can be connected to the FCH \(w\) is 1. Also, if the FCH \(w\)'s maximum transmission range is not less than \(2\mu\!\cdot\!R_{u,av}\), the probability that it can be connected to the SCH \(v\) is 1._  
Proof. : The MCH \(u\) is located in the center of the cluster with the radius \(\mu\!\cdot\!R_{u,av}\) according to the Equation (6), where the SCH \(v\), the FCH \(w\), and cluster members are randomly distributed. Therefore, the distance between any cluster member and the FCH \(w\) is at most \(2\mu\!\cdot\!R_{u,av}\). Also, the distance between the FCH \(w\) and the SCH \(v\) is at most \(2\mu\!\cdot\!R_{u,av}\). Therefore, the theorem is true. Second, we discuss the message and time complexity of the ICV-MIMO scheme in comparison with the CMIMO scheme. **Theorem 3**. : _The message complexity of the ICV-MIMO scheme executed by any node is \(O(N_{nel})\), where \(N_{nei}\) is the number of this node's neighbors with which it directly communicates at its maximum transmission power._  
Proof. : For any given node \(u\), no matter what role (e.g., MCH, SCH, FCH, and cluster member) it plays, the maximum message overhead of its executing the ICV-MIMO scheme occurs in the neighborhood discovery phase (i.e., the Algorithm 1). The complexity for any node \(u\) to broadcast the _hello_ messages (see line 4 in the Algorithm 1) is \(O(1)\) and to receive the _hello_ messages (see lines 8-15 in the Algorithm 1) from its neighbors is \(O(N_{nei})\) respectively. This is because the number of transmitting messages is at a constant level while the received messages may come from the neighbors with which \(u\) directly communicates at its maximum transmission power. So the message complexity of the ICV-MIMO scheme executed by any node is \(O(N_{nei})\). The time complexity of the ICV-MIMO scheme executed by any node is \(max(O(T_{t})\), \(O(N_{nei}\cdot T_{r}))\), where \(T_{t}\) denotes the time duration for the node to successfully access the channel and send a message with a fixed size, and \(T_{r}\) is the time duration for the node to successfully receive and process a message with a fixed size. Proof. : For any given node \(u\), since the complexity for it to broadcast a message is \(O(1)\) (see proof of Theorem 3), its time complexity of broadcasting a message is \(O(T_{t})\). Also, since the complexity for node \(u\) to receive messages is \(O(N_{nei})\) according to Theorem 3, its time complexity of receiving messages from its neighbors is \(O(N_{nei}\cdot T_{r})\). Therefore, the time complexity of the ICV-MIMO scheme executed by any node is \(max\{O(T_{t})\), \(O(N_{nei}\cdot T_{r})\}\).