MCCM: An Approach for Connectivity and Coverage Maximization

Abstract

The internet of Things (IoT) has attracted significant attention in many applications in both academic and industrial areas. In IoT, each object can have the capabilities of sensing, identifying, networking and processing to communicate with ubiquitous objects and services. Often this paradigm (IoT) using Wireless Sensor Networks must cover large area of interest (AoI) with huge number of devices. As these devices might be battery powered and randomly deployed, their long-term availability and connectivity for area coverage is very important, in particular in harsh environments. Moreover, a poor distribution of devices may lead to coverage holes and degradation to the quality of service. In this paper, we propose an approach for self-organization and coverage maximization. We present a distributed algorithm for “Maintaining Connectivity and Coverage Maximization” called $MCCM$. The algorithm operates on different movable devices in homogeneous and heterogeneous distribution. It does not require high computational complexity. The main goal is to keep the movement of devices as minimal as possible to save energy. Another goal is to reduce the overlapping areas covered by different devices to increase the coverage while maintaining connectivity. Simulation results show that the proposed algorithm can achieve higher coverage and lower nodes’ movement over existing algorithms in the state of the art.

1. Introduction

Growth in technology and computing power is continuously progressing and transforming the way societies connect to each other and to the physical world. The tendency to bring smartness to living and environments to make them more adaptive, autonomous and personalized to human needs, prepares the ground to smart worlds [1]. The Internet of Things (loT) is defined by the International Telecommunication Union (ITU) [2] and the European Research Cluster on the Internet of Things (IERC) [3] as a dynamic global network infrastructure with self-configuring capabilities based on standard and inter-operable communication protocols. Mostly a smart network of linked objects and machines, which communicate information via wireless technology and the cloud [4]. Wireless Sensor Network (WSN) plays an important role in conjunction with IoT. It consists of many distributed sensors for environmental monitoring tasks. It brings more control, precisions, early alerts, monitoring and tracking the environment. This is reflected in many projects such as Array of Things (AoT) [5], NEOM City [6,7], Google’s Loon [8], etc. Google’s Loon project aims to create an aerial wireless network formed by nodes such as satellites, balloons, drones, or fixed-wing aircraft. These flying nodes provide network access and rescue missions over areas in disaster scenarios.

Although IoT has great benefits, it has some major challenges such as: Connectivity and coverage, energy consumption, reliability and privacy. The initial deployment of devices in an area of interest might not always meet the mission needs (rescue or military). The basic requirement after deployment is to have sufficient coverage and connectivity [9]. In many cases, the mobility feature of devices is used to maximize the coverage [10]. Wireless sensor devices can sense, process, and in some applications move and organize themselves for coverage missions. These tasks drain devices’ energy and become very challenging especially for power-constrained devices [11]. For this purpose, energy saving during coverage maximization should be considered, and it is necessary to cover all targets areas with a minimum number of devices.

In this paper, we are interested in maintaining connectivity and coverage in wireless distributed networks composed of heterogeneous mobile devices. Our work consists of three parts (1) a distributed algorithm for Coverage Maximization and Maintaining Connectivity (MCCM) between group of neighboring devices, (2) gaps bridging between disjoint groups, and (3) comparison and validation of the proposed distributed algorithm. The algorithm ensures that each device is connected to at least two other devices in the network. This setup increases the network resistance against failure as well as reliability.

The remaining part of the paper is organized as follows: In Section 2, we investigate related works on connectivity and coverage maximization. The motivation and contribution of the work are presented in Section 3 and Section 4 respectively. The performance of the algorithm as well as a comparative study with related works are discussed in Section 5. Section 6 concludes the paper.

2. Related Works

Maintaining connectivity between devices and maximizing coverage is big challenge to reduce the cost of deployment, and to ensure the reliability of data. They are key issues in WSNs as they measure how effectively a network field is monitored by its sensor devices. Coverage is to guarantee that each area is monitored by at least one node, and connectivity is to guarantee that any device can communicate with each other [12]. Protocols related to area coverage are classified based on the sensor types (mobile, static) and the coverage requirement (1-coverage or k-coverage) [13]. Different algorithms [14,15,16,17,18,19] were proposed in the literature and have good impact on the coverage optimization. Protocols can be classified into either distributed or centralized. The type of sensors in the network can be homogeneous (The sensors have the same sensing range and technical properties) or heterogeneous. Studies such as $CT{C}_k$ [16] and $DCT{C}_k$ [16] take into account energy efficiency for coverage and connectivity optimization. Their algorithms work for centralized and distributed coverage in heterogeneous networks and tackle the k-coverage problem. In $DCHGA$ [20] (Dynamic Clustering of Heterogeneous WSNs using Genetic Algorithm), authors present a genetic algorithm. The proposed work can operate on both homogeneous and heterogeneous environments. This algorithm requires a Central Station (CS) with advanced resources to control the devices distributed in the network. Another work ($HMRC$) [21] uses the harmony search algorithm to improve connectivity and coverage within an area of interest. The algorithm in [21] only works on networks where the devices are homogeneous and controlled by a Sink Node (SN) or Central Station (CS).

The authors in [22], presented an asynchronous algorithm ($AAEECC$) that is energy efficient and provides integrated coverage and connectivity. It is fully distributed and scalable. They also presented a fault-tolerance connectivity maintenance algorithm ($FTCM$) to increase the resistance against failure that might occur during the nodes scheduling. In [23], authors presented an algorithm based on Voronoi partition. The algorithm eliminates the isolated nodes and reduces the redundant coverage. Nodes move to their final best position to maintain network connectivity. A deployment technique ($ABSDC$) is suggested in [24] to enhance coverage, connectivity, and reliability. The idea is to use the angle between sensor nodes and their neighbors. The work showed higher coverage percentages and good connectivity compared to the Glowworm Swarm Optimization (GSO) approach [25]. This algorithm works on homogeneous environments only. Another algorithm (OPDCC) [26] addresses the $k-$coverage and $m-$connected problem in WSN. It estimates the minimum number of nodes (and their locations) required for the connectivity and coverage. The proposed algorithm requires a central station (CS) to do all the calculations.

Another novel algorithm for Coverage Maximization of Heterogeneous Wireless Network ($CMHN$) is proposed in [27]. The algorithm is centralized. Devices are heterogeneous and the sensing range of each device has a circular shape. The circumference of the circle is represented as an interval of an angle (0, 2$\Pi$). For any two connected devices $D_i$ and $D_j$ with sensing ranges $r_i$ and $r_j$ respectively, the distance $d_{ij}$ between them is less than the sum of their ranges. A device moves (after random deployment) to a position that ensures a maximum coverage and connects to a closest device to maintain connectivity. The main goal is to keep the movement of devices as minimal as possible to save energy. Another goal is to reduce the overlapping areas covered by different devices and keep it to a small margin to maximize the coverage while maintaining connectivity. $CMHN$ ensures that every device is connected to at least $k=2$ devices. In this algorithm, the notion of $m-$ratio is introduced. It adds flexibility in controlling the overall displacement in the network.

$$m(i,j)=m_{ij}=\left.\left\{\begin{array}{cc}m,\hfill & r_i<r_j\hfill \\ \frac{m+1}{2},\hfill & r_i=r_j\hfill \\ 1,\hfill & r_i>r_j\hfill \end{array}\right.\right\}$$

(1)

where $m\in [0,1]$ is a user-defined value. To determine the location to which a device will move, authors introduced two rules (called the “empty-arc” rules). A device $D_i$ has $2\pi$ empty arc when there is no other device $D_j$ such that $d_{ij}<r_i+r_j$. In other words, it has no intersection area with another device on its circumference. An empty arc has initially the value $2\pi r_i$. The value of the circumference starts to decrease when other devices start to intersect with the device $D_i$ until it reaches zero. It is worthy to mention that the device $D_i$ starts to fill this empty arc during the maximization process and any overlapping before the maximization process is ignored by the device $D_i$. If a device $D_i$ has empty arc the minimum required overlapping between $D_i$ and another device $D_j$, is defined by ${\tau }_{ij}=m_{ij}·r_i+m_{ji}·r_j$. $D_i$ moves to a position that guarantees ${\tau }_{ij}$. This is called “circle-circle” connection. Another rule is "circle-two circle" connection. Given two intersecting circles, a new coming device $D_i$, will be able to connect to them if it has an empty arc. $D_i$ moves along the line through the two crossing points of the crossed circles. It chooses the closest point of intersection and connects to the closest circle that has free arc on that point [27]. Simulation results showed a significant improvement in the coverage gain.

3. Motivation

The examined algorithms in the related works require higher computational resources like $DCHGA$ [20], $HMRC$ [21], $VCACWSN$ [23], $OPDCC$ [26], $DCT{C}_k$ [16], and $AAEECC$ [22]. We will present this part in Section 5. Applying the aforementioned algorithms in distributed environments to run locally on each device, drains the battery energy quickly. Consequently, they might not behave well in networks where devices are energy-constrained. Although $ABSDC$ [24] presents an efficient algorithm and requires low energy consumption. However, authors adopted the triangular circular packing idea. This approach forces a fixed angle between the connected devices as well as a fixed distance between them. Every device should be $r\ast \sqrt{3}$ apart from its neighbor devices where r is the device’s range. This restricted the algorithm to work on homogeneous environments only. Also, the overlapping between devices is constant and is the same between all devices which is not suitable for heterogeneous environments.

$CMHN$ [27] is designed to maintain connectivity and maximize the coverage. It minimizes energy consumption by reducing the number of nodes’ displacement in the network. However, it is a centralized algorithm. In some scenarios, the devices need to take decisions locally, without waiting to be told what to do by a central station, such as in harsh environments, wide forests, monitoring huge amounts of cattle. In such situations, the adoption of distributed algorithm is more appropriate. By investigating the behavior of this algorithm, we noticed the formation of gaps/holes in some scattered distributions. It occurs when a device $D_i$ moves to its final position, it tries to find the closest device $D_j$ that can intersect with (i.e., a device that has enough free arc on its circular range for connection).

In this paper, our work is based on $CMHN$. We propose a distributed version called $MCCM$, for maintaining connectivity and maximizing coverage in disaster and harsh scenarios. The basic idea is that devices are deployed randomly and need to re-organize themselves. Every device takes the decision to move to a nearest location to maximize its coverage while maintaining connectivity with others. We aim to have fewer movements and energy drain. Another part we tackle in this work is that after the self-organizing process is done, disjoints groups of connected devices might appear in the network. We call them "islands" of devices. We bridge the islands to ensure more connectivity using alpha-shape technique to find the islands’ boundaries and shortest path between adjacent boundary sets.

4. Distributed Maintaining Connectivity and Coverage Maximization (MCCM)

In this section, we present the two main parts of our work. The first is $MCCM$; a distributed algorithm which runs independently on each device $D_i$ for coverage maximization. Then, the bridging part that connects the isolated islands using alpha-shape method. The approach consists of three steps as shown in Figure 1: Neighborhood discovery, coverage maximization and bridging process.

4.1. Neighborhood Discovery Process

This process builds the neighborhood list for each device $D_i$. Every device will know about the other devices connected directly or indirectly to it. We denote $\mathsf{\Omega }$ the set of n heterogeneous devices in the network:

$$\mathsf{\Omega }=\left\{D_i\right|i\in [1,n]\}$$

We denote $D_i$ the $i-$th device in the network with center $\left(x_i,y_i\right)$ and range $r_i$. The distance $dist\left(D_i,D_j\right)$ between two devices $D_i$ and $D_j$ is the Euclidean distance denoted $d_{ij}$. We say two devices $D_i$ and $D_j$ are “neighbors”, if their sensing ranges intersect.

$D_i$ is directly connected to $D_j$ when $d_{ij}<r_i+r_j$ and both devices have minimal overlapping ${\tau }_{ij}$ according to [27]. In this case, we denote $D_i\diamond D_j$.

We say $D_i$ is indirectly connected to $D_j$ when there is another device $D_f$, such that $D_i\diamond D_f$ and $D_j$ is directly/indirectly connected to $D_f$. We denote this case $D_i•D_j$.

An island (or group) of connected devices to $D_i$ is denoted ${\mathcal{N}}_i$. It is the set of k devices that includes $D_i$ and its neighbors as follows:

$${\mathcal{N}}_i=\{D_j\in \mathsf{\Omega }|D_j\diamond D_i\vee D_j•D_i\}$$

where $|{\mathcal{N}}_i|=k$ and $k\le n$.

Figure 2 shows how the discovery process occurs on a device $D_i\in {\mathcal{N}}_i$.

The main steps are as follows:

• Any device $D_i$ waits for a certain amount of time t to emit a discovery signal. It is allowed to make c trials.
• Upon receiving a signal from a device $D_j$, both devices start the “Add to neighborhood list” process, only if they have empty arcs on their circumferences. If so $D_j$ is added to ${\mathcal{N}}_i$. The devices in ${\mathcal{N}}_i$ update their list about the newly coming device $D_j$.
• When the emit counter exceeds c times, the device goes to sleep for a certain period of time n. Then, it tries again until the sleeping count exceeds a value s.
• The discovery process ends when the device does not have any more empty arcs or the sleeping counter reaches s.

4.2. Coverage Maximization

This process starts once the discovery process finishes. It occurs in each island ${\mathcal{N}}_i$, if it has more than one device (i.e., |${\mathcal{N}}_i$|>1). Figure 3 shows how the maximization process works. The main idea is to find for each device $D_i$ its location, to maximize the coverage.

The steps are as follows:

• A device $D_i\in {\mathcal{N}}_i$ calculates the mean coordinates $\mathcal{M}(x_m,y_m)$. It is the mean location of the devices in ${\mathcal{N}}_i$, where $x_m=\frac{1}{k}{\sum }_{l=1}^k\left(x_l\right)$, and $y_m=\frac{1}{k}{\sum }_{l=1}^k\left(y_l\right)$, such that $D_l(x_l,y_l)\in {\mathcal{N}}_i.$
• A device $D_i$ moves to the location $\mathcal{M}(x_m,y_m)$ if it is the closest device to it, thus:

  $$dist(D_i,\mathcal{M})=min\{dist(D,\mathcal{M}),\forall D\in {\mathcal{N}}_i\}$$
  The device then updates its status to ready for the monitoring mission.
• Otherwise, $D_i$ finds its next location by guessing the behavior of its adjacent devices located closer to $\mathcal{M}$. $D_i$ orders its neighbors by their initial position with respect to the mean location $\mathcal{M}$. Then it chooses the neighbors that are closer to $\mathcal{M}$. It estimates their positions and moves according to the estimated position. Assume the sequence $D_{i+1}$, $D_i$, $D_{i-1}$ and $D_{i-2}$ is ordered from the farthest to the closest devices to $\mathcal{M}$. Device $D_{i+1}$ is the farthest one. $D_i$ calculates its final position in two ways: (1) either it relies on $D_{i-1}$ estimated position, if the circle-to-circle method is to be applied, (2) or it relies on $D_{i-1}$ and $D_{i-2}$ positions if the circle-to-two circles method is to be used. $D_{i+1}$ does the same. It relies on $D_i$ and/or $D_{i-1}$ estimated positions, and so. For instance, let $\mathsf{\zeta }$ be the set of devices located between $D_i$ and $\mathcal{M}(x_m,y_m)$.
  $$\mathsf{\zeta }=\{D\in {\mathcal{N}}_i|min(y_i,y_m)\le y_D\le max(y_i,y_m)\wedge min(x_i,x_m)\le x_D\le max(x_i,x_m)\}$$
  $D_i$ evaluates the possible location of each device $D\in \mathsf{\zeta }$ by applying the empty-arc rules. Then it moves towards the closest device $D_k$ and connects to it, where $D_k=f(D_i,\mathsf{\zeta })$:

  $$f(D_i,\mathsf{\zeta })=\{D_k\in \mathsf{\zeta }|(D_k\diamond \mathcal{M}\vee D_k•\mathcal{M})\wedge dist(D_i,D_k)=min\left\{dist(D_i,D)\right\}\}$$

4.3. Bridging

In the earlier section, we introduced the maximization process which runs in a distributed manner. Every device knows about the devices that belong to the same neighborhood only. This might form a network with different disconnected neighborhoods (islands) or isolated devices. We mean by isolated device, the one that does not belong to any neighborhood, and we refer to it as an island with only one device. One of the real examples for such problems is losing the connectivity between the different troops in the battle fields. To provide connectivity between the different isolated islands. We need to build connections (bridges) between these islands. These bridges do not need to cover the whole area. It is enough to have them between these islands and the central station to maintain the flow of data. In this section, we provide two different type of bridging: A distributed and centralized 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 $\mathsf{\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 \mathsf{\Omega }$ and ${\mathcal{N}}_j\in \mathsf{\Omega }$, we have ${\mathcal{N}}_i\cap {\mathcal{N}}_j=\varphi$ where $i\ne 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$).

We denote $\alpha -$shape$\left({\mathcal{N}}_i\right)$ the list of edges of an island ${\mathcal{N}}_i$ (Figure 4).

$$E_i=\alpha -\mathrm{shape}\left({\mathcal{N}}_i\right)=\left\{(D_u,D_v)\right|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\le |{\mathcal{N}}_i\left|\right\}$$

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\left({\mathcal{V}}_i\right)$ 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\left({\mathcal{V}}_i\right)={\cup }_{j=1}^{\beta }\left\{{\mathcal{V}}_j\right\}=\{D_q\in V_j|V_j\ne V_i\wedge j\le (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\left({\mathcal{N}}_i^v,{\mathcal{N}}_j^v)\right\}$$

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\left({\mathcal{N}}_i^v,{\mathcal{N}}_j^v\right)$ [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\left({\mathcal{V}}_j\right)$ and $D_j\in A\left({\mathcal{V}}_i\right)$, runs in O(log(n)) time.

Let $\mathsf{\Gamma }={\left\{{\gamma }_i(x_i,y_i,z_i,r_i)\right\}}_{i=1}^g$ be a set of g drones $(x_i,y_i,z_i)$ needed for bridging. The range of each drone is $r_{\mathsf{\Gamma }}$. The central station (CS) calculates the required number of drones as well as the position of each drone on the shortest path between ${\mathcal{N}}_i$ and its adjacent island ${\mathcal{N}}_j$. The number of drones is equal to $d(G_i,G_j)/r_{\mathsf{\Gamma }}$.

4.3.2. Distributed Bridging

A large enough number of drones are deployed in the area of interest. The steps are as follows:

• Drones start scanning the area of interest using coverage path planning algorithms to find any neighborhood or isolated devices.
• If a drone finds a neighborhood, the drone stack to the closest point between the neighborhood and the central station. The drone becomes part of this island and all the devices in the neighborhood knows about it. The chain of connected drones continues growing as straight line between the neighborhood and the central station. Drones either connect to a device at the edge of the island or to another drone. This connection is established using the $\tau$ formula.
• The process of discovery continues till all the links are established between the central station and the neighborhoods or isolated devices if any.

Both ways can be used to form a connected network between all the devices in the area of interest. However, the distributed approach requires greater deployed number of drones. We opt to use the centralized approach.

5. Validation, Simulation and Comparison with Existing Algorithms

We consider terrain where nodes can move without blockage in their ways and have enough energy to reach the final destination. Our goal is to understand how the coverage maximization algorithm behaves. We run different simulations to measure the performance of MCCM algorithm. The number of devices in each scenario varied between 25 and 150 devices ($N=\{25,50,75,100,125,150\}$). They were distributed randomly in the area of interest. We tested the algorithm using homogeneous and heterogeneous distributions. We mean by homogeneous, the presence of sensors with the same characteristics and technical properties. In heterogeneous distributions, sensors are different in sensing ranges and characteristics. We choose the sensing range of the devices in the homogeneous distributions to be 5 m. It varies between 3 m and 8 m for heterogeneous distributions. For a better study, we followed the statistical approach by taking a sample of 10 runs for each deployment. We chose the area of interest to be a rectangular area of 250 m × 250 m. The simulation parameters are presented in

Table 1. Simulation parameters.

Parameter	Values
Area size	250 m × 250 m
Number of nodes	25, 50, 75, 100, 125, 150
Sensing range (meter)	3, 5, 8
Battery voltage	11.1 V
Horizontal Movement $H_e$	2.8 J/m
Energy Capacity C	4900 mAh
Battery Energy	195,804 J
Speed	2 m/s

. The device characteristics are picked similarly to [33].

Figure 6 shows the simulation results for 150 devices in both heterogeneous and homogeneous environments. The blue colored figures represent the deployment before applying our algorithm, the red colored figures represent the result after applying our algorithm and the green circles represent drones.

Figure 6a shows a random deployment of 150 devices in a homogeneous environment and Figure 6b shows the result after applying our algorithm. The coverage gain is 90%. The average device displacement is $18.21$ m. Each device $D_i$ has at least three devices directly connected to it. Figure 6c shows a random deployment of 150 devices in a heterogeneous environment, and Figure 6d shows the result after applying our algorithm. The coverage gain reached 87%. The average device displacement is $22.13$ m. Each device $D_i$ has at least four devices directly connected to it. In the next section we present a comparative study with other related works.

5.1. Comparative Study

In this section, we present the key features of $MCCM$ and existing algorithms in the state of the art. We discuss the coverage gain, the displacement of nodes as well as the energy gain by the algorithms.

Table 2. Comparative study between our algorithms and existing related works.

Name	Architecture	Distribution	Resource	Complexity
CMHN [27]	Centralized	Heterogeneous	Low	$O\left(nlog\right(n\left)\right)$
MCCM	Distributed	Heterogeneous	Low	$O\left(nlog\right(n\left)\right)$
DCTCk [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\left(n^2\right)$
AAEECC + FTCM [22]	Distributed	Homogeneous	Medium	$O\left(n^2\right)$
VCACWSN [23]	Centralized	Homogeneous	Medium	$O\left(n^2\right)$
ABSDC [24]	Centralized	Homogeneous	Low	$O\left(nlog\right(n\left)\right)$
OPODCC [26]	Centralized	Homogeneous	High	$O\left(n^3\right)$

lists the following characteristics: The algorithm’s architecture (Centralized or Distributed), the type of distribution (Homogeneous or Heterogeneous), the resource usage (low, high, medium) and the time complexity.

The time complexity of $MCCM$ is O(nlog(n)) similarly to $CMHN$ and $ABSDC$, where n is the number of devices. Other algorithms (such as $OPODCC$ and $HMRC$) require high computational resources. They are either centralized or suitable for homogeneous environments only. For instance, $DCHGA$ uses genetic code approach to calculate the final positions of the devices within the network. It requires high resources since the required memory allocation is $n\times p\times g$ where n is the number of devices, p is the population size, and g is the number of generations.

In the next section, we rely on the following indicators to measure the performance of our algorithm: (1) the average number of movements per device $mov\left(\mathsf{\Omega }\right)$ related to distance, (2) the coverage gain $A_{gain}\left(\mathsf{\Omega }\right)$, which is the probability that each point in the area is covered and (3) the energy depleted by the moving devices denoted E.

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\left(\mathsf{\Omega }\right)$, in the network $\mathsf{\Omega }$, we use Equation (2).

$$mov\left(\mathsf{\Omega }\right)=\frac{1}{n}\sum _{i=1}^{n}dist(D_i,D_i^f)$$

(2)

As for the coverage gain, we adopt the evaluation method of Abo-Zahhad 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\le w$ is a row in C, and $j\le 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.\left\{\begin{array}{cc}1,\hfill & \sqrt{{(x-x_i)}^2+{(y-y_i)}^2}<r_i\hfill \\ 0,\hfill & otherwise\hfill \end{array}\right.\right\}$$

(3)

For the whole network $\mathsf{\Omega }={\left\{D_i\right\}}_{i=1}^n$, we will use the above equation to find the probability that the point is covered. It is denoted $P(x,y,\mathsf{\Omega })$ presented in Equation (4).

$$P(x,y,\mathsf{\Omega })=1-\prod _{i=1}^n(1-P(x,y,D_i))$$

(4)

The coverage of the area of interest $(w\times h)$ in Equation (5), is the summation of all the aforementioned probabilities:

$$A_{cov}\left(\mathsf{\Omega }\right)=\sum _{x=1}^w\sum _{y=1}^{h}P(x,y,\mathsf{\Omega })$$

(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\left(\mathsf{\Omega }\right)$) and the coverage before applying the algorithm ($A_{cov}\left(\mathsf{\Omega }\right)$) as shown in Equation (6).

$$A_{gain}\left(\mathsf{\Omega }\right)=\frac{A_{cov}^f\left(\mathsf{\Omega }\right)-A_{cov}\left(\mathsf{\Omega }\right)}{A_{cov}\left(\mathsf{\Omega }\right)}$$

(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$. Both algorithms require low computational resources and they use simple mathematical formulas. $ABSDC$ achieved $143\%$ coverage gain while algorithm $CMHN$ achieved $185\%$ coverage gain. This means $42\%$ more coverage gain over $ABSDC$.

$MCCM$ showed better results compared to the distributed algorithms $DCT{C}_k$ and $DCHGA$. $DCT{C}_k$ achieved $75\%$ coverage gain while $MCCM$ achieved $87\%$ coverage gain. This means that our algorithm increases the coverage gain by $12\%$ in heterogeneous environment. As for the homogeneous environment scenarios, our algorithm achieves $9\%$ gain over $DCT{C}_k$. The latter reached a gain of $81\%$ when $MCCM$ attained $90\%$. As a result, our algorithm performed better coverage gain in homogeneous environment. Similar results are obtained in the heterogeneous environment.

As for the displacement, Figure 8b shows the displacement made by each algorithm to maximize the network coverage. $CMHN$ has better results than the other centralized algorithms. $MCCM$ achieves lower average node’s displacement and better coverage over the other distributed algorithms ($DCT{C}_k$ and $DCHGA$).

Table 3. MCCM performance over existing related works.

HOMOGENEOUS
Number of nodes	50		75		100		125		150
MCCM versus	DCTCk	DCHGA	DCTCk	DCHGA	DCTCk	DCHGA	DCTCk	DCHG	DCTCk	DCHGA
Increase in coverage gain in MCCM	15%	19%	14%	14%	12%	12%	15%	16%	11%	13%
Reduction in Displacement	11.65%	35.55%	29.75%	33.31%	0.35%	15.42%	4.13%	15.12%	8.35%	15.58%
HETEROGENEOUS
Number of nodes	50		75		100		125		150
MCCM versus	DCTCk	DCHGA	DCTCk	DCHGA	DCTCk	DCHGA	DCTCk	DCHGA	DCTCk	DCHGA
Increase in coverage gain in MCCM	0%	5%	3%	3%	13%	13%	13%	18%	16%	26%
Reduction in Displacement	11.86%	38.67%	1.21%	22.87%	0.13%	21.24%	5%	10.46%	0.09%	10.69%

summarizes the average overall performance of $MCCM$ compared to the distributed algorithms $DCT{C}_k$ and $DCHGA$ in homogeneous and heterogeneous environments. It increases the coverage gain up to 19% and reduces the nodes displacement by 35.55% compared to the algorithms in the table. In the next section, the results obtained in Figure 8 are interpreted from the energy saving perspective.

5.1.2. Energy Consumption

As the energy consumption is proportional to the displacement, we adopt the formula in Equation (7). It measures the energy depleted by a moving device, where $H_e$ is the energy required to move one meter $(J/m)$ and d is the displacement $\left(m\right)$.

$$E=H_e\ast d$$

(7)

$CMHN$ and $ABSDC$ are both centralized algorithms. However, $ABSDC$ operates only in homogeneous environments. For fair comparison we run both in scenarios composed of 150 homogeneous devices. The results were as follows: $ABSDC$ required an average displacement of $47.3$ m to maximize the coverage. Consequently, the energy consumed by the devices in $ABSDC$ was: $E_{ABSDC}=2.8\times 47.3=132.44$ J. $CMHN$ required $39.06$ m displacement to maximize the coverage. The energy consumed is $E_{CMHN}=2.8\times 39.06=109.368$ J. Hence, the centralized version of MCCM algorithm reduced the displacement and improved the coverage by saving 17.4% of energy in the network:

$$\frac{E_{\left(CMHN\right)}-E_{\left(ABSDC\right)}}{E_{\left(ABSDC\right)}}=\frac{109.368-132.44}{132.44}=-0.174$$

$MCCM$ and $DCT{C}_k$ are distributed algorithms and can operate on different network environments (homogeneous and heterogeneous). $DCT{C}_k$ requires higher computational resources than $MCCM$ (as shown in Table 2). The comparison of the two algorithms in a homogeneous environment of 150 devices depicted the following:

$DCT{C}_k$ required an average of $19.87$ m displacement to maximize the coverage. The consumed energy is $E_{DCT{C}_k}=2.8\times 19.87=55.636$ J. Whereas the $MCCM$ required $18.21$ m displacement to maximize the coverage, the energy is $E_{MCCM}=2.8\times 18.21=50.988$ J. We can notice that $MCCM$ algorithm reduced the nodes displacement by saving $8\%$ of energy over $DCT{C}_k$ algorithm:

$$\frac{E_{\left(MCCM\right)}-E_{\left(DCT{C}_k\right)}}{E_{\left(DCT{C}_k\right)}}=\frac{50.988-55.636}{55.636}=-0.08$$

$MCCM$ behaves similarly in other scenarios. Displacements results in Table 3 showed an energy saving up to 35.5% in $MCCM$ compared to $DCT{C}_k$ and $DCHGA$.

6. Conclusions and Future Works

The collaboration between UAV and WSN into the Internet of things (IoT), is gaining a lot of attention, as a solution to detect emergency events especially in rural and harsh environments. It guarantees an autonomous network healing and quick actions during long-distance missions. Nonetheless, it contributes to a rural transformation by motivating people to live in rural area and facilitating their daily activities. The main issue in harsh and disaster environments is to maintain connectivity between all the objects (devices) and to maximize the coverage between them. Reducing the mobility of devices is also another issue. Many constraints have been considered and handled in this article such as the distributed environment, the heterogeneity and mobility of devices. The main goal is to keep the movement of devices as minimal as possible to save energy. Another goal is to reduce the overlapping areas covered by different devices and keep it to a small margin to maximize the coverage while maintaining connectivity. We proposed $MCCM$ a distributed algorithm for coverage maximization, in which each mobile device re-organizes itself to maximize the coverage in its neighborhood. Since the random deployment and the movement of devices, might form isolated groups or “islands”, we bridge these groups using alpha-shape technique. Simulation results showed an increase in coverage gain and reduction in nodes’ displacement and energy consumption, compared to other algorithms in both homogeneous and heterogeneous environments.

We noticed the following about $MCCM$: It may happens that a device $D_i$ trying to maximize the coverage in an island ${\mathcal{N}}_i$, might meet another device $D_j$ from another island ${\mathcal{N}}_j$ on his way. The two devices might overlap at their final positions and might not be located in their optimal position with respect to each other (as they belong to two different islands). The reason is that the maximization process applies only inside an island and not when two islands meet. This behavior can be beneficial in scenarios where overlapping gets less priority, while the presence of redundancy enhances network reliability. From the coverage optimization perspective, it is recommended to have the least overlapping area among devices while maximizing coverage. In the future works, we intend to tackle this matter by adapting the m-ratio and ${\tau }_{ij}$ constraints when combining islands together. We also aim to do more experimentation with industrial fields and concrete case studies.