1 Introduction

Internet of Things (IoT) is one of the popular technology with enormous future possibilities. A wide range of applications of IoT, encourage the researchers to work on different aspects of this technology. Mainly IoT devices take smart decisions based on the collected data from the local environment. Moreover, it is necessary to accumulate the physical environmental data in case of infrastructural use of IoT, where Wireless Sensor Network (WSN) comes into play.

A number of sensor nodes formed a cooperated network, termed as WSN, where each node is equipped CPU, memory unit, transceiver, sensor array embedded [1]. Meanwhile, in MWSN, sensors are capable of movement, enabling them to self re-positioning in a dire situation to increase coverage or to track a target object. In a network, the area covered by its sensors is the coverage of that network. Various types of applications utilize sensor networking technology, like military and defense applications (e.g. battlefield surveillance, security operation, tracking border intrusion, intruder ship detection in sea, target tracking etc.), health care and medical applications (e.g. location tracking and activity monitoring of emergency respondents (ER), telecare system etc.), industrial applications (e.g. intelligent transportation system, smart car parking, smart homes and offices, industrial process, asset management etc.), environmental and agricultural applications (e.g. indoor air quality monitoring and fire detection, outdoor air pollutants monitoring, wildfire detection, precision agriculture, livestock monitoring etc.) and so on [2, 3].

Sensors are deployed depending on the type of application and normally the deployment can be in a random manner or follow a systemic approach [4]. Moreover, sensors can be deployed based on the area-priority concept for such regions that have different priority levels [5]. In a dynamic deployment scenario, sensors are deployed in one place densely which results in lower network coverage. To improve this coverage, dispersion algorithms are used to guide the sensors’ movements. These algorithms can be divided into centralized, distributed and strictly localized. Various algorithms are proposed in [6,7,8,9,10] which are mainly centralized or distributed algorithms. However, these approaches are inapt in WSN as they are quite complex to handle since sensor nodes have low memory as well as low computational power [11].

On the other hand, after completing data collections from an area the sensors nodes are needed to be collected. So it is desired that sensor nodes will gather into one place for easy collection. This gathering method can be divided into two category synchronous gathering and asynchronous gathering [12]. In synchronous gathering, all sensor nodes move simultaneously. Localized motion planning algorithms are proposed for both sensor dispersion and gathering problem in [13]. However, these algorithms do not consider the presence of obstacle in the network. Similar gathering problem has been studied in robotics [14,15,16] and those algorithms are quite complex to implement in sensors.

Different problems in WSN is solved with the help of cellular automaton model in [4, 18,19,20,21,22,23, 25, 26, 39, 40] with low complexity in terms of memory and computation. Choudhury et al. in [20] propose a simple and strictly localized algorithm based on cellular automaton model that serves the dispersion problem. Additionally, Choudhury et al. in [12] propose an algorithm to solve the gathering problem to a common place. However, the model in [12, 20] does not include obstacles in the path of movement which makes it futile for practical scenarios.

In this paper, we design cellular automaton based strictly localized algorithms where sensors disperse themselves autonomously in order to maximize the network coverage by maintaining connectivity and after finishing dispersion they synchronously gather themselves at a single location. We consider that the system contains obstacles which need to be avoided by the sensors at the time of movements. We modify the algorithm in [20] at the commencement of our study of dispersion of sensor nodes which confirms that we need special rules to avoid these obstacles. Additionally, we also modify the algorithm in [12] and propose a synchronous gathering algorithm which guides these dispersed sensors to a common place. The main contribution of this research is a simple guiding algorithm for dispersion and gathering, in the presence of obstacles to improve the network coverage as well as maintain the network connectivity. Moreover It should be noted that as far we know, there is no CA based algorithm to solve the problem we are addressing that works in an obstacle prone system.

The rest of the paper is organized as follows. Section 2 overviews the state-of-the-art in WSN. In Section 3 we discuss some of the basics of cellular automata. In section 4 we describe the CA based motion planning algorithm. Section 5 defines the simulation tool and analyze the numerical results. Finally, Section 6 concludes the paper with possible future research directions.

2 Related works

Numerous research works have been done on the dispersion of MWSN. Various centralized and decentralized algorithms are proposed to solve dispersion problems like maximizing coverage of the network, object monitoring, strengthening the connectivity of the nodes etc. In [6], authors propose a “sweep coverage” technique where sensors periodically monitor some points of interest (POI) and make the coverage at each POI as time-dependent. Though a small number of sensors are enough to cover a larger area with this approach, it encumbers the sensors with a large amount of stored data as the sensors are unable to send data all the time. A game theoretic approach is discussed in[8] and utilizes the binary log-linear learning to maximize the coverage. They claim that their scheme asymptotically maximizes the number of covered nodes, provided that the agents have sufficient communication ranges.

An energy efficient minimum weighted trap coverage problem in wireless sensor networks is introduced in [27] where authors present a bounded approximation algorithm and prove that the problem is an NP-hard problem. Gupta et al. [7] study sensor positioning method in an anisotropic network topology and complex terrain. They resort to a stochastic sensor movement strategy to generate a trajectory of the sensors. On the other hand, a node placement strategy for ensuring connected coverage in sensor networks is addressed in [4] where two types of scenarios are considered. First one is to cover a certain region and the second one is to cover a fixed set of nodes. Du et al. [28] propose approximation algorithms for a minimum sensor connected coverage problem. Several algorithms for barrier coverage in sensor networks are also proposed in [29,30,31], . However, these works are not same as the problem we are considering rather similar to our coverage problem. Virtual force approaches for sensor deployment in WSN are proposed in [10]. In virtual force approach, all sensors are considered as an actual coordinate point where a repulsive and attractive force acts among them. However, these approaches are computationally quite complex to handle in a WSN and also does not work for an unbounded area.

On the other hand, a CA based approach is presented in [19] where it is argued that cellular automaton model can be used with success to simulate a large network, verifying the properties in a quick and objective way. CA based algorithms use only local information in the algorithm which suits very well for WSNs applications. In [11], a cellular automaton based localized algorithm is proposed to improve the coverage of the network with a minimum number of moves utilizing dynamic deployment. Their movement depends on the position of neighboring sensors along four quadrants and two predefined parameters. Mobile dispersion algorithm, based on cellular automaton is proposed in [20] where the sensors are placed randomly in an obstacle-free field and allow them to disperse. Three transition rules drive their algorithm to maximize the coverage and strengthening the connectivity. In [32], authors propose an algorithm based on cellular automaton to monitor mobile objects. The aim of their algorithm is not to improve the coverage rather maximize the time of monitoring targeted objects.

A fundamental problem for gathering autonomous robots in one place is discussed in [33] where neighbors of a robot are calculated using a constant euclidean distance. Similar to this problem, an asynchronous gathering of robots is also discussed in [34]. Choudhury et al. [12] propose a CA based synchronous gathering localized algorithm for mobile wireless sensor networks where the authors place sensors in a 2-D grid randomly by maintaining connectivity and gathers these sensors into one location. However, obstacles in the path of movement was not considered here. Ando et al. in [15] and Degener et al. in [14] work on the gathering problem in the study of robotics. In [15], a local algorithm is proposed where each sensor determines the smallest enclosing circle that contains all of its neighbors and moves towards the center of that circle. However, computing this circle is complex compared to any CA based algorithm [12]. Degener et al. [14] prove that running time taken by a sensor is tight which is O(n2) where n is the number of sensors. In [13], localized motion planning algorithms are proposed for both sensor dispersion and gathering problem where authors do not consider the presence of obstacle in the network. Saadatmand et al. [35] proposed a CA based local algorithm for sensor gathering in obstacle free field which has the worst case complexity of O(n) where n is the number of sensors.

Moreover, in recent years, a number of problems are solved by cellular automaton in the field of WSN. In [36], a non-volatile two-dimensional cellular automaton model is proposed to analyze the space-time dynamics of a WSN. Sang et al. [37] propose a moving object tracking CA based model in a distributed mobile wireless sensor network. Furthermore, “The lightweight 2-dimensional (2-D) cellular automata based symmetric key encryption” algorithm (L2D-CASKE) is proposed in [23]. Intruder detection system based on cellular automaton theory is presented in [17] which is scalable, self-organized and easily implementable. This system utilizes periodic wake sensor barrier (wave) that sweep the sensor field and able to endure frequent communication failures, obstacles, and sensor failures. A cellular automaton based key management scheme, CAB is proposed in [24] which allows sensors to establish pairwise keys during any stage of the network operation.

3 The cellular automaton model

A Cellular Automaton (CA) model is a biologically inspired model which is used in different physical systems. We can model a two dimensional cellular automaton, following Moore neighborhood [38], as a two dimensional grid. Each cell of the grid can be in a state from a finite set of states. The states of the cells change after discrete time interval and changes depend on the local information rather than the global information. We define a cellular automaton as a quadruple, CA = {C, Q, δ, N}. Here C represents the cells of the grid, Q represents the states of the cells, δ represents the rules for transition of the automation and last of all, N is the neighborhood of a cell. At any moment t, each cell c𝜖C has a state q𝜖Q. At time t + 1, the state of every cell is determined by the transition rules (δ) and state of the neighboring cells. Cells having less Chebyshev distance than the radius i conform the neighbor N of a cell c. In a typical cellular automaton, all cells check the status of its neighbors and change their state according to the transition rules synchronously.

4 Problem formulation and algorithms

We consider a 2-D cellular automaton model where a set of homogeneous sensors Σ and some random obstacles are deployed. The sensors can move within the 2-D grid which is an unbounded area. Our goal is to disperse these sensors in a fashion where they can maximize the area coverage by maintaining connectivity and finally gather all these sensors at a single location so that we can use them for later purpose. In the following subsections, we discuss the characteristics of the cellular automaton model (cell, state, neighborhood), existing localized algorithms and obstacle avoidance motion planning algorithms.

4.1 Cell

A collection of cells are arranged in a 2-D square grid where one square is considered as one cell. We consider that a cell can contain more than one sensor as a typical CA cell can hold multiple mobile sensors. The sensors can move to one cell in one time step and, hence, they can move in the positive and negative x-direction as well as in the positive and negative y-direction.

4.2 State

We define states of each cell as a triplet (M, Sx, Sy). Here M denotes the types of a cell as “sensors”, “empty” and “obstacles” and Sx, Sy denotes the previous movement position of a sensor in x-direction and y-direction respectively. A set of types M ∈ {0, 1, 2} is defined for a cell where 1 denotes the presence of sensors in the cell, 2 represents the presence of obstacles in the cell and 0 represents an empty cell. For M ∈ {0, 2}, we replace Sx, Sy with ∅ as neither an empty cell nor a cell with obstacle holds sensors. Hence, we define Sx, Sy ∈ {0, 1, − 1, ∅} for a cell where 0 indicates that the sensor in this cell is staying in the same cell from previous time step, 1 and − 1 implies that the sensor in this cell is moved from positive and negative x and y-direction respectively. The state of each cell changes in discrete time steps and it depends on a set of self-deployment rules of mobile sensors. In Fig. 1, we have shown the positions to which the sensor s allowed to move in positive and negative x and y-direction. The sensor can move to the positions of a+, b+ and c+ in positive x-direction and a−, b− and c− in negative x-direction. Similarly, positions of positive and negative y-direction are a−, a0, a+ and c−, c0, c+ respectively.

Fig. 1
figure 1

Positions to which the sensor s allowed to move in x and y-direction

Full size image

4.3 Neighborhood

The simplest neighborhood in our cellular automaton model for any given cell is the cell itself and its eight adjacent neighbors. A sensor has communication radius Rc and within this communication radius, all cells are considered as neighbors of the cell of that sensor. Two sensors are directly connected if they are placed within their communication radius and the network is connected if any two sensors can be connected by a path of connected sensors. The sensors also have sensing radius Rs which specifies the monitoring function of the network and the cells within this sensing radius is covered by the sensors. The area covered by the largest connected sensors components of the network is called the total coverage of the network. In order to avoid long chains in the network and maintain the strong connectivity among sensors, we consider scenarios where communication radius is greater than sensing radius [20].

4.4 Existing localized algorithms

A cellular automaton based mobile algorithms CAMPA for sensor dispersion and synchronous gathering are proposed in [20] and [12] where an obstacle-free field is considered to deploy mobile sensors. Three local rules to define the dispersion of the sensors in each of the time steps are discussed in [20]. To gather all these sensors at a single location, a synchronous gathering algorithm is proposed in [12]. The local rules for the dispersion of the sensors are : i) Rules for Movement of Sensors ii) Rules for Blocking Movement and iii) Rules for Moving back. In the following subsections, we describe these three rules and synchronous gathering rules with their behavior while facing obstacles. However, details explanation of these rules is discussed in [20] and [12] respectively.

4.4.1 Rules for movement of sensors

CAMPA algorithm determines the movement of a sensor s based on the weighted number of neighbors of s. The weights for the neighbors of s depends on the distance between neighbors and s. As distance gets increased between a neighbor and s, the amount of weight of that neighbor gets lower. As an example, in case of Rc = 3, the weights of the neighbors of s at distance 1, 2, 3 are 4, 2, 1 respectively. Let, the sum of weights of neighbors of s in the negative x-direction and positive x-direction are \(w_{x_{-}}\) and \(w_{x_{+}}\), respectively. Similarly, the sum of weights of neighbors of s in the negative y-direction and positive y-direction are \(w_{y_{-}}\) and \(w_{y_{+}}\), respectively. The decision of movement of s in the x-direction is defined as

  1. (i)

    if \(w_{x_{-}} = w_{x_{+}}\) then, s does not move in the x direction

  2. (ii)

    if \(w_{x_{-}} > w_{x_{+}}\) then, s moves to the positive x direction

  3. (iii)

    if \(w_{x_{-}} < w_{x_{+}}\) then, s moves to the negative x direction

Here, movement in y- direction is calculated analogously.

4.4.2 Rules for blocking movement

Two rules for blocking movement are introduced in CAMPA algorithm to prevent the network from losing connectivity. First one is Rc − 1 blocking rule where a sensor s does not move in the positive x-direction if it does not see any neighbors within distance Rc − 1 in the negative x-direction and other three directions follow the same rule. Another one is square blocking rule where if two sensors are connected diagonally with the distance of Rc and all other cells of the square with this diagonal are empty, then this two sensor does not move any of the places outside of that square. In case of Rc − 1 and square blocking rule, if multiple sensors are placed into one cell then only one sensor applies the blocking rule and others apply the movement rule to move any other directions.

4.4.3 Rules for moving back

As we are concerned about the connectivity of the network, CAMPA algorithm introduces a move back rule which decreases the hop-distance between individual sensors to ensure the strong connectivity of the network. In move back rule, a sensor remembers only whether or not there were neighbors in the direction opposite to the current movement. At any given time t, before moving to the positive x-direction, a sensor s remembers if there are any neighbors in the negative x-direction. If the sensor does not see any neighbor in the negative x-direction at t + 1 time but it had at least one neighbor at time t in negative x-direction, then the sensor moves back to the negative x-direction. Move back in y-direction is calculated correspondingly. In case of multiple sensors in one cell, move back rule is applied for only one of them and rest of them apply movement rule to move any direction.

In CAMPA algorithm, these rules are giving good result in terms of coverage if there is no obstacle in the field. However, in case of obstacles, these rules do not perform well to maximize the coverage. In the following example in Fig. 2, all the sensor are failed to move any directions in CAMPA algorithm (cell marked as red contains obstacles). Here, some cells are in state 0 where sensors can move and increase the coverage as well as maintain the connectivity, but CAMPA algorithm fails to make these movements. In this paper, we propose obstacle-avoidance movement rules where sensors can move around obstacles and increase the total network coverage by maintaining network connectivity.

Fig. 2
figure 2

Sensors are failed to move in any directions for CAMPA algorithm

Full size image

4.4.4 Rules for synchronous gathering

A large number of sensors are dispersed to increase the coverage of the network but these sensors need to move independently to a single location where they can be collected for later use. A cellular automaton based synchronous gathering rules are discussed in [12] where a set of mobile sensors are deployed sparsely in a two-dimensional obstacle free grid and their movement rules gather all the sensors into one cell. In this movement rule, if a sensor sees any neighbors within distance Rc in the positive x-direction and does not see any neighbors within distance Rc in negative x-direction then the sensor moves towards the positive x-direction. If a sensor does not see any neighbors within distance Rc in both positive and negative x-direction or sees at lest one neighbor within distance Rc in both positive and negative x-direction then the sensor does not move in the x-direction. The same rules apply to the y-direction. In this rule, when the enclosing sensors make a 2 × 2 square or a 1 × 2 rectangle, the sensors enter into a cycle. Only for this cases, if a sensor sees a sensor directly to the positive x-direction and no sensor in negative y-direction, then the sensor moves directly to the positive x-direction. Similarly, if a sensor sees another sensor directly to the negative y-direction and no sensor in directly or diagonally (c+) positive x-direction, then the sensor moves directly toward negative y-direction. Finally, if a sensor sees another sensor diagonally (c+) towards positive x-direction then the sensor moves diagonally (c+) to the positive x-direction. Nevertheless, details description of these rules is discussed in [12].

4.5 Obstacle avoidance movement rules

The main contribution of this paper is discussed in this section. We propose an obstacle avoidance movement rules for both sensor dispersion and gathering movement where the rule is applied in three different scenarios. These scenarios are discussed in the following.

4.5.1 Scenario 1

In this scenario, a sensor s wants to move only positive x-direction (position of b+) and gets blocked by obstacles. In this case, our movement rule considers the movement in y-direction to avoid the obstacle. As the movement on b+ is blocked, our algorithm immediately checks the other two positions in positive x-direction (a+ and c+) for the movement of the sensor. If these positions are not blocked by an obstacle or any blocking rules then, the sensor chooses any of this positions randomly. It is noted that, our algorithm is localized and choosing any position between two available positions generates same results in terms of network coverage and connectivity. If both the positions (a+ and c+) are blocked then, the sensor does not move in any directions. Figure 3 shows an example of obstacle avoidance movement in only positive x-direction where cell marked as red contains obstacles. Movement in the only negative x-direction is determined analogously.

Fig. 3
figure 3

Obstacle avoidance movement in the only positive x-direction

Full size image

4.5.2 Scenario 2

In this scenario, a sensor s wants to move only positive y-direction (position of a0) and gets blocked by an obstacle. For the movement of the sensor, our movement rule checks the other two positions in positive y-direction (a− and a+) and chooses one position randomly if they are not blocked by an obstacle or any blocking rules. Figure 4 shows an example of obstacle avoidance movement in the only positive y-direction. Movement in the only negative y direction is calculated correspondingly.

Fig. 4
figure 4

Obstacle avoidance movement in the only positive y-direction

Full size image

4.5.3 Scenario 3

In this case of obstacle blocking scenario where a sensor s wants to move in both positive x and positive y-direction (position of a+) and gets blocked by an obstacle. Here, our movement rule considers the other two positions in positive y-direction and positive x-direction (a0 and b+ respectively) and chooses one position randomly if they are not blocked by an obstacle or any blocking rule. Movement in a−, c+ and c− is determined in the same fashion. Figure 5 depicts an example of obstacle avoidance movement in positive x and positive y-direction.

Fig. 5
figure 5

Obstacle avoidance movement in both positive x and y-direction

Full size image

4.6 Obstacle avoidance motion planning algorithms

Obstacle avoidance motion planning algorithm for sensor dispersion and synchronous gathering is presented in Algorithm 1. In this algorithm, at each time step, all the sensors run the algorithm locally in order to determine their next position. Thus, the algorithm runs synchronously at all sensors. At the beginning of the Algorithm 1, all the sensors disperse themselves until they reach at a time period tthreshold. After tthreshold time period, all the sensors synchronously gather themselves into one location. In Algorithm 1, dispersion of all the sensors is executed in line 2–8 where we call Algorithm 2 at each time period to calculate the dispersion rule for each of the sensors. The sensors within the radius of communication Rc are considered as neighbors of a sensor. In Algorithm 2, each sensor checks whether it breaks the connectivity with previous sensors at the previous state using the “Moveback” rules. If the “Moveback” condition is satisfied in line 2 of Algorithm 2, a sensor steps back to its previous state. It is noteworthy that, at the initial stage there is no previous state thus no move back action occurs. Mainly this move back action strengthens the connectivity. If the “Moveback” condition is not satisfied (i.e. connectivity has not broken) then Movement rule is applied in line 5 of Algorithm 2. However, that calculated position might be an obstacle. In that case, the next location is updated based on the rule for the obstacles in line 7 of Algorithm 2. Even after that, a sensor may end up in a position where it can not move due to the blocking rules. In line 10 of Algorithm 2, next location is checked, whether it is blocked by any blocking rule. Only if the next location is not blocked, the sensor moves to the next location.

figure a
figure b

At tthreshold time period, all the sensors are dispersed to maximize the network and we need to gather all these sensors into one cell so that we can use them for later purpose. In Algorithm 1, synchronous gathering of all the sensors is executed in line 2–8 where we call Algorithm 3 at each time period to calculate the gathering rule for each of the sensors. A “synchronous gathering movement rule” is applied in line 2 of Algorithm 3 to calculate the next location for a sensor s. However, this calculated position might be an obstacle. In that case, the next location is updated based on the rule for the obstacles in line 4 of Algorithm 3. If the calculated next location is also blocked by obstacle then the sensor does not move to any directions.

figure c

4.7 Analysis

We consider a deterministic and probabilistic approach for the sensor dispersion algorithm. In the deterministic approach, one sensor checks all the rules at each time period to determine whether it should move from the current cell or not. In the probabilistic approach, each sensor verifies the rules with some probability at each time period and probabilistic approach in dispersion algorithm provides better coverage than the deterministic approach similar to [20]. However it takes more time than the deterministic approach to reach a final configuration. In Fig. 6, an example of deterministic and probabilistic approach of our proposed dispersion algorithm is shown where probabilistic approach outperforms the deterministic approach in terms of coverage. However, in case of synchronous gathering we consider a deterministic approach to gather all the sensors into one cell.

Fig. 6
figure 6

Comparison of final configurations with 16 mobile sensors (Rc, Rs = 3, 1): a Initial configuration b Final configuration after the deterministic approach of our dispersion algorithm (coverage 100) c Final configuration after the probabilistic approach of our dispersion algorithm (coverage 144)

Full size image

We examine the same example of Fig. 2 for our obstacle avoidance dispersion movement rules. Figure 7 shows the final configuration of Fig. 2 for proposed algorithm. It is clear that in our proposed movement rule sensors can move around the obstacles and increase the network coverage.

Fig. 7
figure 7

Final configuration of Fig. 2 for proposed algorithm

Full size image

Theorem 1

The synchronous gathering rules never increase distance among the sensors with the presence of obstacles.

Proof

In synchronous gathering rule at any given time t, a sensor moves closer to another sensor because it moves away from the empty direction. If this movement is blocked by an obstacle, the sensor looks for another cell in the same direction (away from empty direction). Here, consider the scenario of Fig. 8 where the next location of sensor 1 and 3 is in 1‘ (south-east) and 3‘ (north-west) respectively. If the cell labeled with 1‘ is blocked by an obstacle then the scenario matches with the scenario 3 of obstacle avoidance movement rule. According to the scenario 3 of obstacle avoidance movement rule, the sensor should move to any cell between directly right or directly below from its current location. If the sensor moves directly right, then the distance between sensor 2 and 1 remains same. The distance between 2 and 1 decreases if sensor 1 moves directly below from its current location. It is noted that, if all three potions are blocked then the sensor remains in its current cell. Movement of sensor 3 is also calculated in the same fashion. Similarly, for other scenarios, we can show that a sensor always moves opposite to the empty region with the presence of obstacles. Since a sensor never moves to an empty direction, it never increases the distance with other sensors. □

Fig. 8
figure 8

Scenario for synchronous gathering

Full size image

5 Performance evaluation

The aim of this paper is to propose a decentralized algorithm that disperses sensors to maximize the area coverage as well as maintain the connectivity of the network and then gathers all the sensors into one location after reaching to the final configuration. All the sensors maintain a threshold time tthreshold which determines the time of dispersion of each sensor. It is noted that all the sensors start the execution of gathering rules at the same time. We measure the performance of dispersion algorithm using the coverage and connectivity of the network. The performance of synchronous gathering algorithm is measured based on the state of the cells. It is noted that synchronous gathering algorithms run in deterministic approach [12]. We consider different scenarios to evaluate the coverage of the network where (Rc, Rs) is (3, 1) and (3, 2). In some cases, the sensor deployment can create long chains to maximize the coverage of the network which is not useful in practice. Therefore, we determine the performance of our algorithm in terms of the strongly connected coverage of a network (aSCC). The value of aSCC consisting of n sensors is the ratio between the average coverage of the network (aCOV) and the average hop distance of the network (aHD) [20]. Here, the average hop distance of a network (aHD) consisting of n sensors is

$$ aHD = \frac{{\sum}_{s_{1} \neq s_{2}} hd(s_{1}, s_{2})}{n(n-1)}, $$
(1)

where hd(s1, s2) represents the length of the shortest path of sensors connecting s1 and s2. We compare the result of our algorithm with the CAMPA algorithm. It is noted that we distribute obstacles within maximum possible coverage area randomly. We apply the probabilistic approach with probability 0.1,0.2 and 0.3 where 0.1 probability takes more time than 0.2 probability to reach the final configuration and 0.3 probability has more chances of sensors being disconnected. In Fig. 6, performance comparison between deterministic and probabilistic approach is discussed. In case of sensor deployment, probabilistic approach provides better network coverage than the deterministic approach [20]. We find that the probabilistic approach with 0.2 probability gives a better result than all other variants. We implement all the algorithms using the programming language python (Version 3.6). Next, we describe some of the input scenarios and results of our algorithm. It should be noted that all results are calculated based on 20 experiments.

We place 100 mobile sensors in the middle of the grid as in Fig. 9 where the value of (Rc, Rs) is (3,1). Figure 9 also shows the final configuration of CAMPA and our proposed algorithm. In case of CAMPA algorithm, most of the sensors get blocked and can not avoid obstacles to maximize the coverage. In our proposed algorithm, sensors move around the obstacles due to the obstacle avoidance movement rule and maximize the total network coverage. Figure 10 shows the coverage of the algorithms through time. We calculate the optimal coverage considering CAMPA algorithm in an obstacle-free field. Therefore, it is clear that total coverage for our algorithm is very close to the optimal coverage as well as provides much better result than the CAMPA algorithm. We measure the performance of synchronous gathering algorithm using the number of the cell which contains mobile sensor at each time period. In Table 1 we show the total number of cells that contains sensors in the 2-D grid for our proposed algorithm and CAMPA algorithm. At time 2000 all the sensors are in their final configuration for dispersion algorithm. After that, they initiate the synchronous gathering and all the sensors try to gather into one cell. In our proposed algorithm finally, one cell remains which contains all the sensors which indicate that all the sensors are gathered in one location. Meanwhile, in CAMPA finally all the sensors move to 6 different cells. From Fig. 9 we can see that for CAMPA algorithm most of the sensors remain inside the free spaces covered by obstacles. Therefore, for synchronous gathering algorithm most of the sensors able to meet in one location as in the final configuration they meet in 6 different locations.

Fig. 9
figure 9

Comparison of final configurations with 100 mobile sensors: a Initial Configuration b Final Configuration of Proposed Algorithm c Final Configuration of CAMPA

Full size image
Fig. 10
figure 10

Comparison of the total coverage for different probabilistic algorithms (Scenario of Fig. 9)

Full size image
Table 1 Comparison of the no of cells in the state of having sensors in synchronous gathering rules with 100 mobile sensors
Full size table

To get different scenario we place 200 sensors (as Fig. 11) in the center divided into two clusters but in communication range. Here, for CAMPA algorithm, sensors placed on the bottom left side fail to avoid the obstacles in the final configuration but in our proposed algorithm sensors avoids the obstacles and maximizes the coverage. Figure 12 shows the coverage rate for this scenario where our algo- rithm provides better coverage than CAMPA algorithm. Table 2 shows the performance between proposed algorithm and CAMPA algorithm for synchronous gathering problem. Here, in our proposed algorithm all the sensors are able to meet in one cell whereas CAMPA fails to gather them in one location due to the presence of obstacles. From Tables 1 and 2 it is clear that our algorithm outperforms CAMPA algorithm in terms of synchronous gathering problem.

Fig. 11
figure 11

Comparison of final configurations with 200 mobile sensors: a Initial Configuration b Final Configuration of Proposed Algorithm c Final Configuration of CAMPA

Full size image
Fig. 12
figure 12

Comparison of the total coverage for different probabilistic algorithms (Scenario of Fig. 11)

Full size image
Table 2 Comparison of the no of cells in the state of having sensors in synchronous gathering rules with 200 mobile sensors
Full size table

Figure 13 shows the comparison of coverage of final configuration between two algorithms for various amount of obstacles with the same initial configuration of 100 mobile sensors. Here, in case of CAMPA algorithm, the total coverage of final configuration gets decreased with the increasing amount of obstacles, but our proposed algorithm maintains better coverage than CAMPA algorithm in this cases.

Fig. 13
figure 13

Comparison of coverage of final configuration between two probabilistic algorithms for various amount of obstacles with 100 mobile sensors

Full size image

Figure 14a and b show the comparison based on the metric of average strongly connected coverage (aSCC) with Rc, Rs = (3, 1) and Rc, Rs = (3, 2) respectively. These figures indicate that our proposed algorithm maintains pleasant result with compare to CAMPA algorithm. It should be noted that in some cases, sensors got disconnected to form multiple clusters while using CAMPA algorithm, but our proposed algorithm does not face that type of problem. In some cases, sensors are more strongly connected in CAMPA algorithm as most of the sensors cannot pass through obstacles and remain close to each other.

Fig. 14
figure 14

Comparison of aSCC between two probabilistic algorithms for various numbers of mobile sensors

Full size image

In Fig. 15 we show the final configuration after completing synchronous algorithm for both proposed algorithm and CAMPA algorithm. Here, we distribute all the sensors randomly in a 2-D grid and run only synchronous gathering portion of both the algorithms. Figure 15b and c shows the final configuration of our proposed algorithm and CAMPA algorithm respectively. Our algorithm gathers all the sensors into one cell whereas CAMPA algorithm fails to gather them due to the presence of obstacles. Summarizing above simulation results, we can conclude that our proposed algorithm outperforms existing algorithms in both the coverage maximization and synchronous gathering problem.

Fig. 15
figure 15

Comparison between synchronous gathering algorithms with 100 mobile sensors: a Initial Configuration b Final Configuration after gathering using Proposed Algorithm c Final Configuration after gathering using CAMPA algorithm

Full size image

6 Conclusion and future work

We consider a locomotion problem in presence of obstacles for MWSN where the main goal is to increase the network coverage while maintaining the connectivity of the network and finally gather all the sensors into one location. A cellular automaton based model is considered where mobile sensors are placed in a 2-D square grid. We propose a probabilistic approach in our coverage maximization algorithm where mobile sensors can avoid obstacles and disperse them to maximize the coverage area of the network. Our experiment shows that our algorithm outperforms existing cellular automaton based algorithm and provides result near to optimal result. We also propose a deterministic synchronous algorithm where all the sensors move around the obstacle and meet in one location. However, our algorithm provides a better result than the existing algorithm for synchronous gathering problem. In our future work, we want to study the behavior of the system where obstacles are also in motion.