# MCCM: An Approach for Connectivity and Coverage Maximization
## 4 Distributed Maintaining Connectivity and Coverage Maximization (MCCM)
### Bridging
#### 4.3.1 Centralized Bridging  
At the end of the maximization process, the network might be composed of different islands in which the coverage is maximized. Thus, we have \(\Omega=\cup_{i=1}^{t}\mathcal{N}_{i}\) where \(t\) is the number of islands in the network. For any two islands \(\mathcal{N}_{i}\in\Omega\) and \(\mathcal{N}_{j}\in\Omega\), we have \(\mathcal{N}_{i}\cap\mathcal{N}_{j}=\phi\) where \(i\
eq j\) (Figure 4). To bridge the islands, we use flying nodes or drones. This is useful in disaster locations that humans cannot reach. The goal is to find the closest points between two islands and bridge with the lowest number of drones. We use alpha shape to determine the boundaries of each island. The alpha-shape algorithm attempts to define the shape of a finite set of points in the plane. Formally, the boundary is a graph \(G_{i}(\mathcal{V}_{i},E_{i})\) (Figure 4), where \(\mathcal{V}_{i}\) is the list of devices on the boundary of \(\mathcal{N}_{i}\) and \(E_{i}\) is the set of edges (\(|E_{i}|=e\)). Figure 3: Neighborhood maximization process of device \(D_{i}\). We denote \(\alpha-\text{shape}(\mathcal{N}_{i})\) the list of edges of an island \(\mathcal{N}_{i}\) (Figure 4). \[E_{i}=\alpha-\text{shape}(\mathcal{N}_{i})=\{(D_{u},D_{v})|D_{u}\in\mathcal{N}_{i },D_{v}\in\mathcal{N}_{i}\}\]  
where \((D_{u},D_{v})\) is an edge between two vertices \(D_{u}\) and \(D_{v}\). The set of devices on the boundaries are denoted \(\mathcal{V}_{i}\) as follows:  
\[\mathcal{V}_{i}=\{D_{q}\in E_{i}|q\in[1,b]\wedge b\leq|\mathcal{N}_{i}|\}\]  
We denote \(\mathcal{N}_{i}^{v}\) the list of sub chains of \(E_{i}\). An island \(\mathcal{N}_{i}\) may have one or more neighboring islands \(\mathcal{N}_{j}\), called adjacent islands. Assume \(\mathcal{N}_{i}\) has \(\beta\) adjacent islands. We denote \(A(\mathcal{V}_{i})\) the set of devices on the edges of the neighboring islands. In other words, it is a set of \(\beta\) adjacent boundary sets \(\mathcal{V}_{j}\) to \(\mathcal{V}_{i}\). \[A(\mathcal{V}_{i})=\cup_{j=1}^{\beta}\{\mathcal{V}_{j}\}=\{D_{q}\in V_{j}|V_{j }\
eq V_{i}\wedge j\leq(t-1)\}\]  
The bridging process is initiated by the central station (CS). Drones are sent to discover the isolated islands using discovery algorithms such as the Fast Neighbor Discovery Algorithm (FNDA) [28]. Drones calculate the boundary set for each neighborhood \(\mathcal{N}_{i}\) using alpha-shape algorithm. After determining the boundaries \(\mathcal{E}_{i}\) of each island \(\mathcal{N}_{i}\), this bridging process starts finding the minimal distance between any two adjacent boundary sets. Computing the minimum distance between two islands \(\mathcal{N}_{i}\) and \(\mathcal{N}_{j}\) (Figure 5) is a well-studied problem in computational geometry [29]. Let \(d(G_{i},G_{j})\) be this distance:  
\[d(G_{i},G_{j})=min\{d(\mathcal{N}_{i}^{v},\mathcal{N}_{j}^{v})\}\]  
where \(\mathcal{N}_{i}^{v}\), \(\mathcal{N}_{j}^{v}\) are linearly separable sub chains of \(\mathcal{N}_{i}\) and \(\mathcal{N}_{j}\) respectively. The problem of determining \(d(G_{i},G_{j})\) is decomposed into a collection of subproblems \(d(\mathcal{N}_{i}^{v},\mathcal{N}_{j}^{v})\)[29]. When both \(G_{i}\) and \(G_{j}\) are convex, their separation can be determined in O(log n) time [30]. If exactly one of \(G_{i}\) or \(G_{j}\) is convex, then their separation can be computed in O(n) time [31]. When neither polygon is convex their separation can be found in O(n log(n)) time by traversing the contour between the polygons in their generalized Voronoi diagram [32]. According to [29], determining a closest pair among all pairs (\(D_{i}\), \(D_{j}\)) where \(D_{i}\in A(\mathcal{V}_{j})\) and \(D_{j}\in A(\mathcal{V}_{i})\), runs in O(log(n)) time. Let \(\Gamma=\{\gamma_{i}(x_{i},y_{i},z_{i},r_{i})\}_{i=1}^{\beta}\) be a set of \(g\) drones \((x_{i},y_{i},z_{i})\) needed for bridging. The range of each drone is \(r_{\Gamma}\).