# MCCM: An Approach for Connectivity and Coverage Maximization
## 5 Validation, Simulation and Comparison with Existing Algorithms
### Comparative Study
#### 5.1.1 Coverage Gain and Displacement  
Let \(D_{i}^{f}\) be the final position of a device \(D_{i}\) after applying the algorithm. To measure the average number of movements denoted \(mov(\Omega)\), in the network \(\Omega\), we use Equation (2). \[mov(\Omega)=\frac{1}{n}\sum_{i=1}^{n}dist(D_{i},D_{i}^{f}) \tag{2}\]  
As for the coverage gain, we adopt the evaluation method of [PERSON] et al. in [10]. We treat the Area of Interest (AoI) as a matrix \(C\) of dimension \(w\times h\). \(C(i,j)\) presents the cell at position \((i,j)\) in the matrix \(C\) where \(i\leq w\) is a row in \(C\), and \(j\leq h\) is a column \(C\). To exemplify, Figure 7 shows the distribution of two devices in the matrix \(D_{A}\) (the red circle) and \(D_{B}\) (the black circle). The point \(D\) is uncovered, which means there is no device covering this point. The point \(C\) is covered by two devices \(D_{A}\) and \(D_{B}\). The point \(E\) is only covered by the device \(D_{B}\). For any point \((x,y)\) in the matrix \(C\), the probability \(P(x,y,D_{i})\) that the point is covered by a device \(D_{i}\) is given by Equation (3), where \((x_{i},y_{i})\) are the coordinates of the device and \(r_{i}\) is its range. \[P(x,y,D_{i})=\left. \begin{cases}1,&\sqrt{(x-x_{i})^{2}+(y-y_{i})^{2}}<r_{i}\\ 0,&\text{otherwise}\end{cases} \right\} \tag{3}\] \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Name** & **Architecture** & **Distribution** & **Resource** & **Complexity** \\ \hline CMHN [27] & Centralized & Heterogeneous & Low & \(O(nlog(n))\) \\ MCCM & Distributed & Heterogeneous & Low & \(O(nlog(n))\) \\ DCTC\({}_{k}\)[16] & Distributed & Heterogeneous & Low & \(O(p\times q)\) \\ DCHGA [20] & Centralized & Heterogeneous & High & \(O(p\times g\times n)\) \\ HMRC [21] & Centralized & Homogeneous & Medium & \(O(n^{2})\) \\ AAEECC + FTCM [22] & Distributed & Homogeneous & Medium & \(O(n^{2})\) \\ VCACWSN [23] & Centralized & Homogeneous & Medium & \(O(n^{2})\) \\ ABSDC [24] & Centralized & Homogeneous & Low & \(O(nlog(n))\) \\ OPODCC [26] & Centralized & Homogeneous & High & \(O(n^{3})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparative study between our algorithms and existing related works. For the whole network \(\Omega=\{D_{i}\}_{i=1}^{n}\), we will use the above equation to find the probability that the point is covered. It is denoted \(P(x,y,\Omega)\) presented in Equation (4). \[P(x,y,\Omega)=1-\prod_{i=1}^{n}(1-P(x,y,D_{i})) \tag{4}\]  
The coverage of the area of interest \((w\times h)\) in Equation (5), is the summation of all the aforementioned probabilities:  
\[A_{cov}(\Omega)=\sum_{x=1}^{w}\sum_{y=1}^{h}P(x,y,\Omega) \tag{5}\]  
We care about the coverage gained in the network by our algorithm. Therefore, we calculate the difference between the coverage obtained after applying our algorithm (denoted \(A_{cov}^{f}(\Omega)\)) and the coverage before applying the algorithm (\(A_{cov}(\Omega)\)) as shown in Equation (6). \[A_{gain}(\Omega)=\frac{A_{cov}^{f}(\Omega)-A_{cov}(\Omega)}{A_{cov}(\Omega)} \tag{6}\]  
We run 60 scenarios of random deployments with different number of devices. Figure 8a (resp. Figure 8b) clearly depicts that \(MCCM\) and \(CMHN\) are showing least nodes' displacement in heterogeneous (resp. homogeneous) environments. Figure 8c (resp. Figure 8d) represents the coverage gain in the heterogeneous (resp. homogeneous) environments. The centralized algorithms showed higher values in terms of coverage gain over distributed algorithms, as we expected. The reason is that by having the calculation done by a Central Station (CS), all the devices will move to their final optimized position. The centralized algorithm \(CMHN\) showed better results over ABSDC. This is due to the presence of the empty-arc rules that reduce the overlapping between devices and change it according to their ranges. In ABSDC, there are fixed angle and fixed distance between devices which makes the size of the overlapped area higher than \(CMHN\).