An Energy-Efficient Sensor Deployment Scheme for Wireless Sensor Networks Using Ant Colony Optimization Algorithm

Abstract

Sensor deployment is one of the most important issues in wireless sensor networks (WSNs), because an efficient deployment scheme can reduce the cost and enhance the detection capability of the WSNs. Due to packet forwarding, sensors closer to the sink consume more energy than those farther away. In this paper, we propose a sensor deployment scheme, which can achieve full coverage of the monitoring area and prolong network lifetime. We consider a real world situation where the initial energy of the sensors is different from each other. First, to achieve full coverage using as few sensors as possible, we compute the average angle between the sensor nodes. Then, we provide two methods to achieve energy balance. In the first method, we propose a sweep-based scheme to move the sensors as requested. In the second method, we transform the deployment problem into the multiple knapsack problem and based on ant colony optimization algorithm, we propose a deployment strategy to improve the network lifetime.

1 Introduction

Wireless sensor networks (WSNs) consist of a large number of tiny sensor nodes [1, 8]. In addition to measuring real world phenomena, these sensor nodes are also capable of storing, processing and transferring the measurements [24]. They can also move to appropriate positions to increase the coverage region. The sensors can measure various parameters of the environment and use hop-by-hop communication to transmit the collected data to sinks. The sink processes the collected data and forwards it to the users after processing. WSNs are an upcoming and growing technology, which have a wide range of applications like target tracking, natural disaster relief, biomedical or health care monitoring, real-time monitoring and interaction with the physical environment in which there are still some unpredictable conditions.

However, in order to be practically viable, any application involving WSNs should take into account the limited availability of the resources like energy, computational power and memory in the sensor nodes [7]. In order to save energy and bandwidth, recent advances in WSNs have enabled the development of low-cost and low-power sensor nodes that are small in size and communicate over short range. The sensor nodes typically operate on batteries and have limited lifetime. On the contrary, many applications requires the sensor nodes to be active for months or years, while replacing the batteries is too expensive or impractical. For example in applications where sensor nodes monitor the places that are too deep, high, far or dangerous for humans to go, it may be impossible to replace the batteries of the sensor nodes and network operation and lifetime are typically restricted by the energy consumption of the sensor nodes. Therefore, it is very important to prolong battery life of the sensor nodes.

Coverage is an important issue in WSNs and is related to energy saving, connectivity, and network reconfiguration. Coverage mainly addresses the problem of deployment of the sensor nodes to achieve sufficient coverage of the service area, so that every point in the service area should be monitored by at least one sensor [9, 11, 14, 15, 17]. Efficient deployment of the sensor nodes can increase the coverage region and reduce the communication cost of the sensor nodes. Therefore, an efficient deployment strategy is vital in order to improve coverage, achieve load balance, and prolong the network lifetime. Sensor deployment schemes can be broadly classified as deterministic or random deployment scheme. In deterministic deployment, the sensor nodes are deployed at pre-determined locations. On the other hand, in random deployment, the sensor nodes are scattered randomly in the service region.

The network lifetime of WSNs refers to the time period, the deployed WSNs can function properly [22]. It can be defined as the interval between the time when the network is set up and the time when the network cannot guarantee certain coverage or connectivity requirements. In WSNs, the data traffic follows a many-to-one communication pattern in which the sensor nodes transmit their collected data to the sink. Due to packet forwarding, nodes closer the sink have to deal with heavier traffic load and hence they consume more energy than the sensors that farther away from the sink. Eventually, these sensor nodes run out of energy, leading to what is called an energy hole between the sink and other active nodes. As a result, not all the sensing data can be delivered back to the sink and the sensor network becomes malfunctioning. As a result, the network lifetime ends soon and much energy of the nodes is wasted.

A concept of non-uniform deployment for the sensor network was proposed to solve the above mentioned problem [5, 6, 12, 16, 20]. The sensor density for each area (ring) of the monitoring region can be determined based on the proposed algorithm. The area that is closer to the sink should have higher sensor density, so that more number of sensors can share the load of data-forwarding. However, how to achieve complete coverage of the monitoring region for non-uniform deployment was not mentioned in the reference paper. In this paper, we propose a sensor deployment scheme that maximizes the coverage of the monitoring region for a given number of sensors as well as achieves energy consumption balance.

The rest of the paper is organized as follows. Section 2 describes related work in deployment for wireless sensor networks. Section 3 presents problem formulation. Section 4 presents our proposed deployment schemes. Section 5 discusses experimental results and Sect. 6 concludes this paper.

2 Related Work

As a measure of the quality of service in the sensing field, there are many studies about coverage problem in WSNs. Many papers are mainly concerned about uniformly distributing the sensors to provide load balancing and area coverage. There are recent research works focusing on improving the initial deployment of WSNs using sensors’ mobile ability [6, 16, 20]. In [6], they studied the flip-based deployment mechanism to achieve the maximum coverage. They assume the sensor can only flip once, and divide the whole network into multiple square regions. The centralized algorithm maximizes the number of regions that are covered by at least one sensor node with the minimum moving cost. In [21], a scan-based distributed protocol with the goal of uniformly distributing sensors via sensor relocation. A scanning mechanism is used to balance the number of sensors first for each row of clusters and then for each column of clusters. The goals in [6, 21] involve improving the coverage and achieving load balance with uniform sensor densities.

In [20], their method is to deploy as few sensors as possible to maintain both coverage and connectivity. Figure 1 shows the sensor deployment in four layers. In order to get the request of few sensors, they compute the fix distance between two neighboring sensors. They did fully cover the monitored area, but their method did not consider the location of sink. The node energy consumption correlates closely with the location of sink.

Fig. 1

Sensor deployment without considering the location of sink

The uniform deployment is ineffective when the energy of sensors is not the same. The sensors with little energy will consume their energy soon, and end the lifetime of the whole network. Also, the uniform deployment does not consider the location of the sink. In order to prolong network lifetime, reducing the node energy consumption has been studied as an important issue. The uniform deployment is not the best method for increasing the network lifetime because of the transmission load of the sensors nearer the sink is heavier. Several non-uniform deployment methods have been proposed recently [2, 4, 13, 18, 19, 23].

With uniform distribution of nodes, it points out that the nodes close to the sink deplete their energy quickly, even combine with sleep scheduling scheme [18]. They provide the distribution of nodes in the deployment vary as a function of the distance from the sink. It means the area that is closer to the sink has the higher sensor density. Deploying nodes non-uniformly, nodes share the duty of data forwarding to achieve energy consumption balance. But they don’t consider how the sensors move to achieve varying density. Their density is not the accurate value of requirement. There is error because they do not compute the requirement as reality energy, but to compute the requirement as number of sensors. The error will increase when the energy of sensors is not the same.

In [2, 19], they proposed a moving algorithm based on Voronoi diagram for achieving the non-uniform deployment. The Voronoi cell creates an area for every node. This area can be an index for nodes to adjust their density. The area is smaller with the higher sensor density. Calculate sensors’ moving vector by using the Voronoi cell create area, the mobile sensors can move to appropriate density which is computed by the function in [18]. Therefore, the sensors adjust the distance with other sensors to achieve the desired density, also remove coverage holes. Since the density function is not the accurate requirement of energy, the network will not achieve energy consumption balance after their moving algorithm especially when the energy of sensors is not the same.

In [23], they consider a one-time sensor flip mobility model to reposition sensors. The movement plan is computed by the sink using a max-flow min-cost approach. Their goal is to achieve non-uniform sensor densities using a centralized algorithm when sensors can move by flipping at most once. In [4], they present a distributed approach to improve the movement plan. To further control the sensor distribution and to ensure communication to adjacent regions, they consider the network to be virtually partitioned in coronas and sectors. Then they present a corona-radius scanning mechanism that divided into two parts, corona scans and radius scans. The corona scans balance the number of sensors per corona, and in the radius scan, sensors are redistributed on segments according to the desired sensor density. It will achieve overlap and waste the source according to the virtually partitioned they used. Also, the network will not achieve energy consumption balance after their moving algorithm, because of the density function is not the accurate requirement of energy. The theories might reduce the efficiency especially when the energy of sensors is not the same.

The previous researches focus on how to deploy the sensors to achieve much better energy efficiency [2, 4, 18, 23]. Their methods are based on the premise that the energy of the sensors is the same. The methods might reduce the efficiency or even not work in a situation that the energy of the sensors is not the same.

3 Problem Formulation

The network lifetime of WSNs refers to the time the deployed WSNs can function properly. It can be defined as the interval between the time when the network is set up and the time when the network cannot guarantee certain coverage or connectivity requirements. The network lifetime can be prolonged by finding several subsets of sensors and schedule them to relay data to the sink. As a result, power consumption balance is achieved by sensor deployment scheme.

In our problem formulation, we divide the monitored area into virtually divided coronas as shown in Fig. 2 [4, 22, 23]. Let $R_c$ be the communication range and $R_s$ be the sensing range of each sensor, and $R_c =2\cdot R_s$. The width of corona is $d$. To maintain both coverage and connectivity, we further divide a corona into thinner coronas $C_{1}, C_{2},\ldots ,C_{k}$ of width $d/2$. We deploy sensors only on the circumference of the coronas of width $d/2$. Therefore, any sensor on circumference of corona $C_{k}$ is directly connected to the sensors on circumference of corona $C_{k+1}$ and $C_{k-1}$. A sensor in corona $C_{k}$ transmits its own messages and helps the sensors in corona $C_{k +1}$ in forwarding their messages. A message transmitted from corona $C_{k}$ is forwarded by sensor nodes in coronas $C_{k-1}, C_{k-2}$, and so on, until it reaches corona $C_{1}$, from where it is transmitted to the sink.

Fig. 2

Division of monitored area

In this paper, we consider WSNs with $m$ sensors randomly deployed for periodical monitoring of an area centered by a sink and the energy level of the sensors may be different from each other. Table 1 shows the parameter notation used in our problem formulation.

Table 1 Model notations

4 Energy-Efficient Deployment Scheme

Our sensor deployment scheme is to achieve full coverage and maximize the lifetime of the network. Our scheme is divided into three parts. First, to achieve full coverage, we compute the average angle between sensors to get the minimum number of sensors $\textit{NL}_k$ to be deployed in the monitored area. Then, we provide two methods, sweep-based scheme and ant colony optimization (ACO) scheme to move the sensors in each corona to achieve energy balance [10]. In sweep-based scheme, the sensors are moved as request. In ACO scheme, we formulate the deployment problem to the multiple knapsack problem. Based on ACO algorithm, we propose a deployment strategy to improve the network lifetime.

4.1 Centralized Scheme for Full Coverage

Our objective is to deploy as few sensors as possible to maintain both coverage and connectivity. To achieve full coverage, the least number of sensors to be deployed in the $k\mathrm{th}$ corona be an integer $\textit{NL}_k$. As shown in Fig. 3, we deploy $\textit{NL}_k$ number of sensors uniformly in the corona $C_{k}$ and the angle between two sensors is given by $2\cdot \theta _k =360^{\circ }/\textit{NL}_k$.

Fig. 3

The angle between two sensors is $2\cdot \theta _k =360^{\circ }/\textit{NL}_k$

We can compute the value of $2\cdot \theta _k =360^{\circ }/\textit{NL}_k$ as follows. In Fig. 4, the sensor $S_i$ intersects the sensor $S_j$ at the point $a$. The line segment $\overline{S_i S_j }$ passes through the sink and is perpendicular to $\overline{S_i S_j }$ at point $b$. To cover the region that is not covered, the necessary condition is

$$\begin{aligned} \overline{sa} =k\cdot d \end{aligned}$$

(1)

If $\overline{sa} =k\cdot d$, the point $a$ lies on the circumference of the corona $C_k$, thus fully covers the width of $C_k$. This means that $C_k$ will be fully covered by the sensors present in $C_k$. In order to ensure the complete coverage of the monitored area, we have to compute the length of the line segment $\overline{sa}$, which is given by:

$$\begin{aligned} \overline{sa} =\overline{sb} +\overline{ba} \end{aligned}$$

(2)

Fig. 4

The red region is not covered. (Color figure online)

Using trigonometric function, we can obtain the length of the line segment $\overline{sb}$ as,

$$\begin{aligned} \overline{sb} =\cos \theta _k \cdot d_k \end{aligned}$$

(3)

We also know that

$$\begin{aligned} \sin \theta _k&= \frac{\overline{bS_j } }{d_k }\nonumber \\ \overline{bS_j }&= \sin \theta _k \cdot d_k \end{aligned}$$

(4)

$$\begin{aligned} R_s ^{2}&= \overline{ba} ^{2}+\overline{bS_j } ^{2} \end{aligned}$$

(5)

From Eqs. (4) and (5), we can obtain the length of $\overline{ba}$ as,

$$\begin{aligned} \overline{ba} =\sqrt{R_s ^{2}-(\sin \theta _k )^{2}\cdot d_k ^{2}} \end{aligned}$$

(6)

Substituting the length of $\overline{ba}$ and $\overline{sb}$ from Eqs. (3) and (6) into Eq. (2), we get

$$\begin{aligned} \overline{sa} =\overline{sb} +\overline{ba} =\sqrt{R_s ^{2}-(\sin \theta _k )^{2}\cdot d_k ^{2}}+\cos \theta _k \cdot d_k \end{aligned}$$

(7)

That is to say,

$$\begin{aligned} \sqrt{R_s ^{2}-(\sin \theta _k )^{2}\cdot d_k ^{2}}+\cos \theta _k \cdot d_k \ge k\cdot d \end{aligned}$$

(8)

We can obtain the value of $\theta _k$ from Eq. (8) as,

$$\begin{aligned} \theta _k =\cos ^{-1}\left( {\frac{d\cdot \left( {2k^{2}-k+\frac{1}{4}} \right) }{2\cdot k}} \right) \end{aligned}$$

(9)

Each corona $C_k$ has its own average angle $\theta _k$. Using the value of $\theta _k$, we can obtain the value of $\textit{NL}_k$ as,

$$\begin{aligned} \textit{NL}_k =\frac{360^{\circ }}{2\cdot \theta _k } \end{aligned}$$

(10)

$\textit{NL}_k$ is an integer and its value is different for different coronas. The value of $C_k$ because the area of corona $C_{k+1}$ is greater than that of corona $C_k$. Let us denote $N$ as the least number of sensors required for full coverage of the monitored region and $N$ is given by:

$$\begin{aligned} N=\sum _1^\ell {\textit{NL}_k } =\sum _1^\ell {\frac{360^{\circ }}{2\cdot \theta _k }} \end{aligned}$$

(11)

$N$ is an integer. Substituting Eq. (9) into Eq. (11), we can get the value of $N$ as follow,

$$\begin{aligned} N=\sum _1^\ell {\textit{NL}_k } =\sum _1^\ell {\frac{360^{\circ }}{2\cdot \theta _k }} =\sum _1^\ell {\frac{360^{\circ }}{2\cdot \cos ^{-1}\left( {\frac{d\cdot \left( {2k^{2}-k+\frac{1}{4}} \right) }{2\cdot k}} \right) }} \end{aligned}$$

(12)

Assuming $d=x\cdot R_s$, where $x$ is an integer,

$$\begin{aligned} N=\left\lceil \sum _1^\ell \frac{360^{\circ }}{2\cdot \cos ^{-1}\left( {\frac{x\cdot R_s \cdot \left( {2k^{2}-k+\frac{1}{4}} \right) }{2\cdot k}} \right) } \right\rceil \end{aligned}$$

(13)

After implementation of our deployment scheme, the monitored area will be fully covered.

4.2 Sweep-Based Scheme

Let us assume that the frequency of the event occurring in the network area follows the normal distribution. The sink is located at the center i.e., layer 0, of network and it responds to collection sensing information from the other sensors. The sensors closer to the sink tend to consume more energy than those farther away from the sink. This is because of the fact that, besides transmitting their won packets, they also forward packets on behalf of other sensors that are located far away.

In this section, we present a sweep-based scheme using a corona-radius scanning mechanism similar to [4]. The notations of sweep-base scheme are shown in Table 2. However, we combine the corona scan and the radius scan into one mechanism and we do not need to scan the corona to compute the number of sensors because we propose a centralized scheme in this paper. After implementing the centralized scheme given in Sect. 4.1, we can achieve full coverage of the monitored area using as few as sensors as possible. We assume there are $m$ sensors to be deployed in the monitored area.

Table 2 Sweep-based scheme notations

Initially, we consider a virtual division of the monitored area as shown in Fig. 5. To further control the sensor distribution and to ensure communication to adjacent regions, we consider partitioning of monitored region into several circle points. There are $\textit{NL}_{k}$ circle points in corona $C_{k}$. The circle points on angle $0^{\circ }$ of each corona are denoted as the first ones and other circle points are numbered counterclockwise as ${C_{({k,a})}}$, where $1\le a\le \textit{NL}_k , 1\le k\le \ell$.

For example, there are two coronas in Fig. 5. Each corona $C_{k}$ has $\textit{NL}_{k}$ circle points. There are 9 circle points in $C_2$ and 4 circle points in $C_1$. The circle point on angle $0^{\circ }$ of corona $C_2$ will be numbered as $C_{\left( {2,1}\right) }$, and the next circle points will be $C_{\left( {2,2} \right) }$ and so on. The circle points on other coronas are numbered in a similar manner.

At least one sensor must be deployed in the predetermined circle points of each corona. One of the sensors in each circle point is selected as the sensor head, which takes care of the movement of all the sensors in its circle point to prolong the network lifetime. A sensor head collects information on remaining energy of all sensors in its circle point. Our goal is to propose a mechanism to move sensors to proper circle point to prolong the lifetime of the network.

The energy of a circle point depends on the corona to which that circle point belongs and is computed as follows. The energy consumption rate $\textit{RL}_{k}$ of corona $C_{k}$ is given by:

$$\begin{aligned} \textit{RL}_k =\sum _{i=k}^\ell {\textit{NL}_i \lambda \cdot e} \end{aligned}$$

(14)

This implies that the sensors in corona $C_{k}$ not only transmit their own packets, they also forward packets on behalf of other sensors that are located in farther coronas.

Fig. 5

An example of circle points $C_{\left( {k,a} \right) }$ in two coronas

We denote ${\mathop {\textit{EL}}\limits ^\wedge }_k$ as the total energy of corona $C_{k}$. It is also the sum of the total energy $E(C_{\left( {k,a} \right) })$ of circle points $C_{\left( {k,a} \right) }$ of corona $C_{k}$

$$\begin{aligned} {\mathop {\textit{EL}}\limits ^\wedge }_k =\sum _{a=1}^{\textit{NL}_k } {E\left( C_{\left( {k,a} \right) } \right) } \end{aligned}$$

(15)

The total energy of whole network$E$is sum of $\textit{EL}_k$

$$\begin{aligned} {\mathop {\textit{EL}}\limits ^\wedge }_1 +{\mathop {\textit{EL}}\limits ^\wedge }_2 +\cdots +{\mathop {\textit{EL}}\limits ^\wedge }_\ell =E \end{aligned}$$

(16)

To maximize the network lifetime, we must ensure that all coronas have the same lifetime. In order to do that, the total energy of each corona should be proportional to its energy consumption rate. Hence, we have

$$\begin{aligned} \frac{\textit{EL}_1}{\textit{RL}_1 }=\frac{{\textit{EL}}_2}{\textit{RL}_2}=\cdots =\frac{{\textit{EL}}_\ell }{{\textit{RL}}_\ell }=\frac{E}{\sum \nolimits _{k=1}^\ell {\textit{RL}_k }} \end{aligned}$$

(17)

The initial energy of each corona is random, and it will not achieve the same lifetime for all the coronas. Hence, based on Eq. (17), we can compute the new total energy of corona $C_{k}$ as

$$\begin{aligned} \textit{EL}_k =E\cdot \frac{\textit{RL}_k }{\sum \nolimits _{k=1}^\ell {RL_k }} \end{aligned}$$

(18)

A sweep-based scheme will balance the energy in all the coronas. At the end of the sweep, the energy in each corona will be proportional to its energy consumption rate and all circle points in the same corona will have same energy. First, the sweep scans the circle points from circle point 1 to $\textit{NL}_\ell$ in the last corona $C_\ell$. During the first sweep, the representative of each circle point $C_{\left( {\ell ,a} \right) }$ receives the value of $\frac{\textit{EL}_\ell }{\textit{NL}_\ell }$ from the circle point $C_{\left( {\ell ,a-1} \right) }$ and computes $E(C_{\left( {\ell ,a} \right) } )-\frac{\textit{EL}_\ell }{NL_\ell }$, where $E(C_{\left( {\ell ,a} \right) } )$ is the total energy circle point $C_{\left( {\ell ,a} \right) } , 1\le a\le \textit{NL}_k$. The representative of each circle point $C_{\left( {\ell ,a} \right) }$ receives one message (Balanced, RequestSensors, or MoveSensors) from the upstream circle point $C_{\left( {\ell ,a-1} \right) }$ and sends one message (Balanced, RequestSensors, or MoveSensors) to the downstream circle point $C_{\left( {\ell ,a+1} \right) }$. Exceptions are the first $C_{\left( {\ell ,1} \right) }$ and the last $C_{\left( {\ell ,\textit{NL}_\ell } \right) }$ circle points. The first circle point being the initiator of the sweep process does not receive a message and the last circle point being the finisher of the sweep process sends one message (Balanced, RequestSensors, or MoveSensors) to the first circle point $C_{\left( {\ell -1,1} \right) }$ in the corona $C_{\ell -1}$. Then the first circle point $C_{\left( {\ell -1,1} \right) }$ starts the same sweep process in corona $C_{\ell -1}$. The sweep process is performed from the outer most corona $C_\ell$ until the inner most corona $C_1$.

A circle point $C_{\left( {k,a} \right) }$ updates its energy depending on the type of message it receives from the circle point $C_{\left( {k,a-1} \right) }$ and sends one of the following three messages to circle point $C_{\left( {k,a+1} \right) }$.

Case 1 If $E(C_{\left( {k,a} \right) } )=\frac{\textit{EL}_k}{\textit{NL}_k}$, then the state of this circle point is neutral. Hence, it does not have to send or receive any sensors.

Case 2 If $E(C_{\left( {k,a} \right) } )>\frac{\textit{EL}_k}{\textit{NL}_k}$, then the circle point is a source region. Hence, it sends sensors, whose sum of energy is $E(C_{\left( {k,a} \right) } )-\frac{\textit{EL}_k}{\textit{NL}_k }$ to the downstream circle point $C_{\left( {k,a+1} \right) }$.

Case 3 If $E(C_{\left( {k,a} \right) } )<\frac{\textit{EL}_k}{NL_k}$, then the circle point is a hole region and it requires additional sensors whose sum of energy is $\frac{\textit{EL}_k}{\textit{NL}_k }-E(C_{\left( {k,a} \right) })$.

Hence, it requests additional sensors from the circle point $C_{\left( {k,a+1} \right) }$ using the RequestSensors message. The RequestSensors message keeps track of the circle points, which request additional sensors. If $C_{\left( {k,a+1} \right) }$ does not have additional energy of amount $\frac{\textit{EL}_k}{\textit{NL}_k}-E(C_{\left( {k,a} \right) })$ to fulfill the requirement of $C_{\left( {k,a} \right) }$, it sends the RequestSensors message to the next circle point $C_{\left( {k,a+2} \right) }$. This process continues until a circle point is found, which has enough additional energy. The region has to receive sensors before forwarding. At the end of the sweep, all the circle points in the same corona will have the same energy $\frac{\textit{EL}_k}{NL_k }$, and the energy $\textit{EL}_k$ in each corona will be proportional to its energy consumption rate $1\le j\le n$.

We present the greedy method of choosing sensors. To make the sum of the energy in sensors is the same to the moving requirement.

4.3 ACO Scheme

In this section, we propose a mechanism to move sensors to proper circle point, in order to prolong the lifetime of the network. This sensor redeployment problem can be transformed into multiple knapsack problem (MKP). The MKP is considered where $n$ items are to be packed into $m$ knapsack of distinct capacities $c_{i}, i=1 ,{\ldots },m$ [3]. Each item $j$ is associated with a value $p_{j}$ and a weight $w_{j}$. The problem is to select $m$ disjoined subsets of items, such that subset $i$ fits into capacity $c_{i}$ and the total profit of the selected items is maximized. The MKP can be formulated as follows:

$$\begin{aligned} \begin{array}{ll} \hbox {maximize}&{}\sum \nolimits _{i=1}^m {p_j x_{ij} }\\ \hbox {subject to}&{} \sum \nolimits _{j=1}^n {w_j x_{ij}} \le c_i ,i=1,\ldots ,m\\ &{}\sum \nolimits _{i=1}^m {x_{ij} \le 1,j=1,\ldots ,n}\\ &{}\qquad x_{ij} \in \{0,\;1\},\;i=1,\ldots ,m;\;j=1,\ldots ,n\\ \end{array} \end{aligned}$$

(19)

The parameter notations used in our problem formulation are shown in Table 3.

Table 3 ACO scheme notations

The total energy of the sensors $n_{(k,a)}$ in the circle point $C_{\left( {k,a} \right) }$ is given by:

$$\begin{aligned} E\left( C_{\left( {k,a} \right) }\right) =\sum _{j=1}^{n_{(k,a)} } {E\left( S_{(k,a)}^j\right) } \quad \hbox {where }1\le a\le \textit{NL}_k , 1\le k\le \ell . \end{aligned}$$

(20)

The energy consumption rate $P(C_{(k,a)})$ for circle point $C_{(k,a)}$ is given by:

$$\begin{aligned} P(C_{(k,a)})=\frac{\textit{RL}_k }{\textit{NL}_k } \end{aligned}$$

(21)

where $\textit{RL}_k$ is the energy consumption rate in kth corona, $\textit{NL}_k$ is the number of circle points in kth corona and $C_{(k,a)}$. From Eqs. (20) and (21), the lifetime $\textit{LT}(C_{(k,a)})$ of the circle point $C_{(k,a)}$ is given by:

$$\begin{aligned} \textit{LT}(C_{(k,a)})=E(C_{\left( {k,a}\right) })/P(C_{(k,a)}) \end{aligned}$$

(22)

Let $N_{(k,a)}$ be the number of neighbor circle points of $C_{\left( {k,a} \right) }$, and $CN_{(k,a)} =\{C_{\left( {k,a} \right) }^i |\;1\le i\le N_{(k,a)} \}$ be the set of $N_{(k,a)}$ neighboring circle points of $C_{(k,a)}$. We number the neighboring circle points in the increasing order of the angle between $C_{\left( {k,a} \right) }$ and $C_{\left( {k,a} \right) }^i$. The neighboring circle point having the smallest angle is numbered as $0^{\circ }$ and the one with largest angle is numbered as $C_{\left( {k,a} \right) }^1$.

Because of the distributed nature of our protocol, sensors from the circle point $C_{\left( {k,a} \right) }^{N_{(k,a)}}$ can be moved only to the circle point $C_{(k,a)}$. Thus, we will compare the lifetime $\textit{LT}(C_{(k,a)})$ with $\textit{LT}(C_{(k,a)}^i )$. Let $\Gamma =\left\{ C_{\left( {k,a} \right) }^i |\textit{LT}(C_{\left( {k,a} \right) }^i )<\textit{LT}(C)_{\left( {k,a} \right) } \right\} ,\;1\le i\le N_{(k,a)}$. That is, the set of all the neighboring circle points $C_{\left( {k,a} \right) }^i$, whose lifetime is less than that of the circle point $C_{\left( {k,a} \right) }^i$. We can define total energy $\textit{TE}$ as:

$$\begin{aligned} \textit{TE}=\sum _{i\in LT\left( C_{\left( {k,a} \right) }^i \right) <LT\left( C_{\left( {k,a} \right) }\right) } {E\left( C_{\left( {k,a} \right) }^i \right) } +E\left( C_{\left( {k,a} \right) }\right) \end{aligned}$$

(23)

Next, we compute total energy consumption rate TP of $\Gamma \cup C_{(k,a)}$, which is given by:

$$\begin{aligned} \textit{TP}=P\left( C_{(k,a)}\right) +\sum _{i\in LT\left( C_{\left( {k,a} \right) }^i \right) <LT\left( C_{\left( {k,a} \right) }\right) } {P\left( C_{\left( {k,a} \right) }^i \right) } \end{aligned}$$

(24)

The mean lifetime $\overline{LT} (C_{(k,a)})$ of $\Gamma \cup C_{(k,a)}$ is given by:

$$\begin{aligned} \overline{\textit{LT}} (C_{(k,a)})=\textit{TE}/\textit{TP} \end{aligned}$$

(25)

If the lifetime of $C_{\left( {k,a} \right) }^i \in \Gamma$ is greater than $\overline{LT} (C_{(k,a)})$, we remove $C_{\left( {k,a} \right) }^i$ from $\Gamma$ and recaculate $\overline{LT} (C_{(k,a)})$. That is to say that $C_{(k,a)}$ moves its sensors only to those $C_{\left( {k,a} \right) }^i$, whose $LT(C_{\left( {k,a} \right) }^i)$ is less than $\overline{LT} (C_{(k,a)})$.

Now, we compute the demand energy $\textit{ED}(C_{\left( {k,a} \right) }^i)$ of $C_{\left( {k,a} \right) }^i \in \Gamma$, which is given by:

$$\begin{aligned} \textit{ED}\left( C_{\left( {k,a} \right) }^i \right) =\overline{LT} \left( C_{\left( {k,a} \right) }^i \right) \times P\left( C_{\left( {k,a} \right) }^i \right) -E\left( C_{\left( {k,a} \right) }^i \right) , \mathrm{if}\, C_{\left( {k,a} \right) }^i \in \Gamma \end{aligned}$$

(26)

From Eq. (26), we can compute the provided energy $\textit{EP}(C_{(k,a)})$ of $C_{(k,a)}$, which is given by:

$$\begin{aligned} \textit{EP}(C_{(k,a)})=\sum _{i=1}^{N_{(k,a)} \}} {\textit{ED}\left( C_{\left( {k,a} \right) }^i \right) } ,\hbox { if }C_{\left( {k,a} \right) }^i \in \Gamma \end{aligned}$$

(27)

We can get that each $C_{(k,a)}$ can provide $\textit{EP}(C_{(k,a)})$ energy to the demand energy of $\textit{ED}(C_{\left( {k,a} \right) }^i)$ of $C_{\left( {k,a} \right) }^i \in \Gamma$. Now, the sensor redeployment problem can be defined as the problem of distributing $\textit{EP}(C_{(k,a)})$ amount of energy among the circle points $\textit{ED}(C_{\left( {k,a} \right) }^i )$ in order to compensate their demand energy $C_{\left( {k,a} \right) }^i \in \Gamma$, so that the lifetime of the network can be maximized. This sensor redeployment problem can be transformed into multiple knapsack problems. Our sensor deployment problem can be as follows. Where $n_{(k,a)}$ sensors in circle point $C_{(k,a)}$ can be move to the neighbor circle point $C_{\left( {k,a} \right) }^i$ of $C_{(k,a)}$. $\Gamma$ is denoted that the lifetime of $C_{(k,a)},$ neighboring circle points $C_{\left( {k,a} \right) }^i$ are less than the lifetime of circle point $C_{(k,a)}$, these $C_{\left( {k,a} \right) }^i$ will be added to the set $\Gamma$. Thus, the $i\in \Gamma =\{i|C_{(k,a)}^i \}$. $E(S_{(k,a)}^j )$ is denoted the energy of sensor $S_{(k,a)}^j$ in the circle point $C_{(k,a)}, E(C_{\left( {k,a} \right) }^i )$ is denoted the total energy of the neighboring circle point $C_{\left( {k,a} \right) }^i$ of circle point $C_{(k,a)}$, and $P(C_{\left( {k,a} \right) }^i)$ is denoted the energy consumtion rate of the neighboring circle point $C_{\left( {k,a} \right) }^i$ of circle point $C_{(k,a)}$. $\textit{ED}(C_{\left( {k,a} \right) }^i )$ is denoted the demand energy of the neighboring circle point $C_{\left( {k,a} \right) }^i$ of circle point $C_{(k,a)}$.

Our sensor redeployment problem can be similar to the multiple knapsack problem (MKP) as follows. Suppose there are several ants to be the solutions. We compare the lifetime between each neighboring circle point in an ant, and choose the neighboring circle point which has the smallest lifetime. Then, we compare the lifetime between ants. The ant which has the biggest lifetime be the optimal solution.

$$\begin{aligned} \begin{array}{ll} \max &{} \left( \mathop {\min }\nolimits _{i\in \Gamma =\{i|C_{\left( {k,a} \right) }^i \}} \frac{\sum \nolimits _{j=1}^{n_{(k,a)} } {E\left( S_{(k,a)}^j \right) x_{ij} } }{P\left( C_{\left( {k,a} \right) }^i \right) }+\frac{E\left( C_{\left( {k,a} \right) }^i \right) }{P\left( C_{\left( {k,a} \right) }^i \right) }\right) \\ \hbox {subject to} &{} \sum \nolimits _{j=1}^{n_{(k,a)} } {E\left( S_{(k,a)}^j \right) x_{ij} } \le \textit{ED}\left( C_{\left( {k,a} \right) }^i \right) ,\;\;i\in \Gamma =\{i|C_{\left( {k,a} \right) }^i\}\\ &{}\sum \limits _{i\in \Gamma =\{i|C_{\left( {k,a} \right) }^i \}} {x_{ij} \le 1,\;j=1,\ldots ,n_{(k,a)}}\\ &{}\qquad x_{ij} \in \{0,\;1\},\;i\in \Gamma ^{\prime }=\left\{ i|C_a^i \right\} ;\;j=1,\ldots ,n_{(k,a)}\\ \end{array} \end{aligned}$$

(28)

In an ant colony system, a colony of artificial ants is used to construct solutions guided by the pheromone trails and heuristic information [10]. Ant colony system was inspired by the foraging behavior of the real ants. This behavior enables the ants to find the shortest paths between food sources and their nest. Initially, ants explore the area surrounding their nest in a random manner. As soon as an ant finds a source of food, it evaluates the quantity and quality of the food and carries some of it to the nest. During the return trip, the ant deposits a pheromone trail on the ground. The quantity of deposited pheromone depends on the quantity and quality of the food and it guides other ants to the food source. This indirect communication between the ants via the pheromone trails allows them to find the shortest path between their nest and the food sources. This functionality of real ant colonies is exploited in artificial ant colonies in order to solve optimization problems. In the ant colony system, the pheromone trails are simulated via a parameterized probabilistic model called the pheromone model. The pheromone model consists of a set of model parameters whose values are called the pheromone values. The basic ingredient of the ant colony system is a constructive heuristic that is used for the probabilistic construction of solutions using the pheromone values.

In the following paragraphs, we will describe how to move sensors to maximize the lifetime of the network using an ant colony algorithm and illustrate how our proposed algorithm works. The ant colony algorithm consists of three steps. First step is to select a set of sensors, whose sum of the energy is equal to the provided energy $EP(C_{(k,a)})$ of $C_{(k,a)}$. Second step is to move the selected sensors from the circle point $C_{(k,a)}$ to its neighboring circle point $C_{\left( {k,a} \right) }^i$, based on the probabilistic model discussed below and update the energy of the source and destination circle points of the sensors and the final step is to update the pheromone trails on the sensor nodes.

As already discussed, we can move a sensor only to its neighboring circle points. The probability $C_{\left( {k,a} \right) }^i$ of movement of sensor $S_{(k,a)}^j$ from the circle point $C_{(k,a)}$ to the circle point $C_{\left( {k,a} \right) }^i$ is given by:

$$\begin{aligned} \left\{ \begin{array}{l} p^{k}\left( {i,j} \right) =\frac{\left[ \tau \left( {i,j} \right) \right] ^{\alpha }\left[ \eta \left( {i,j} \right) \right] ^{\beta }}{\sum \nolimits _{j=1,\ldots ,n} {\sum \nolimits _{i\in \Gamma ^{{\prime }}=\left\{ {i\left| {C_{(k,a)}^i } \right. } \right\} } {\left[ \tau \left( {i,j} \right) \right] ^{\alpha }\left[ \eta \left( {i,j} \right) \right] ^{\beta }} } },\; \mathrm{if}\;\textit{ED}\left( C_{\left( {k,a} \right) }^i \right) \ge E\left( S_{(k,a)}^j \right) \\ p^{k}\left( {i,j} \right) =0 \quad \mathrm{otherwise} \\ \end{array} \right. \end{aligned}$$

(29)

$\tau \left( {i,j} \right)$ is the pheromone level to update the pheromone table of head sensor from $S_{(k,a)}^j$ move to the neighboring circle point $C_{\left( {k,a} \right) }^i$. $\beta$ is the parameters which determine the relative influence of the pheromone trail and the heuristic information. The parameter $\eta (i,\;j)$ is given by:

$$\begin{aligned} \eta (i,\;j)=\textit{ED}\left( C_{(k,a)}^i \right) \cdot E\left( S_{(k,a)}^j \right) \end{aligned}$$

(30)

From Eqs. (29) and (30), we can conclude that, if the energy of the sensor $S_{(k,a)}^j$ increases, the probability of movement of the sensor also increases. After selecting the sensor $S_{(k,a)}^j$ for movement from $C_z$ to $1\le j\le n$, the circle points $E(S_{(k,a)}^j )$ and $S_{(k,a)}^j$ will update their energies as given by Eqs. (31) and (32).

$$\begin{aligned} \textit{ED}\left( C_{(k,a)}^i\right)&= \textit{ED}\left( C_{(k,a)}^i\right) -E\left( S_{(k,a)}^j\right) \end{aligned}$$

(31)

$$\begin{aligned} \textit{EP}(C_{(k,a)})&= \textit{EP}(C_{(k,a)})-E\left( S_{(k,a)}^j \right) \end{aligned}$$

(32)

Once all ants have built the solution, pheromone level is updated in pheromone table according to Eq. (33).

$$\begin{aligned} \tau (i,\;j)=(1-\rho )\tau (i,\;j)+\rho \cdot \Delta \tau (i,\;j) \end{aligned}$$

(33)

where $\rho$ is the pheromone evaporation parameter, the deposited pheromone is discounted. This results in the new pheromone level between the evaporation and new addition pheromone.

5 Simulation Results

In this section, we first show the performance of the centralized deployment scheme for complete coverage of the monitoring network. Then we show the performance of our sweep-based sensor deployment scheme. We compare our method with scan-based method and uniform distribution method. For these simulation experiments, at least 1,500 nodes were disseminated in the monitoring network and energy of each sensor node randomly varies between 50 and 300 Joules. The other simulation parameters are given in Table 4.

Table 4 Simulation notations

Figure 6 compares the lifetime of the network for sweep-based method, scan-based method and uniform distribution when the energy of the sensors may be different from each other. We can observe that the lifetime of the network for uniform distribution is shorter than that for sweep method and scan-based method. This is because the fact that the inner coronas consume more energy than the outer coronas, hence the sensors in the inner coronas will die soon in the uniform distribution. The sweep-based method computes the required energy in the circle points, and moves the sensors to those circle points, which require additional energy. With increase in number of sensors in the network, the lifetime of the network also increases. This is due to the fact that after moving the sensors to the require regions, there still will be a difference between the required energy and the actual energy of the circle points. When the number of sensors in the network increases, the number of energy levels of the sensors also increases and the difference in required and actual energy of the circle points decreases. Hence, the energy requirement of all the circle points can be satisfied more accurately, which results in prolonged network lifetime. The lifetime of the network for ACO scheme is more than that for the sweep-based method, as in ACO scheme there is more flexibility in choosing the sensors from a variety of energy levels to satisfy the additional energy requirement of the circle points. Similarly, the network lifetime for the scan-based method is less than that for the sweep-based method, as energy difference between the required energy and the actual energy of the circle points is more in case of the scan-based method because of performing their scan as twice.

Fig. 6

Network lifetime versus number of sensors when the energy of sensors is different from each other

In Fig. 7, we compare the sweep method with the scan-based method and uniform distribution, when the energy of all the sensors in the network is same. The results show that the network lifetime in case of Fig. 7 is shorter than that in case of Fig. 6. When energy of all the sensors is the same, we do not have the choice to select the sensors having required energy level to move to the energy deficit regions. Hence, the difference between the required energy and the actual energy of the circle points will be more and the network lifetime will reduce. It does not compare the requirement by actual energy, but by number of sensors. The distinction is increased with the error between the requirements compute separately by actual energy and the number of sensors.

Fig. 7

Network lifetime versus number of sensors when energy of all the sensors is the same

In Fig. 8, we compare the message transmission overhead for different deployment schemes. In ACO scheme, the circle points have to exchange message with all of their neighboring circle points. Hence, the message transmission overhead in this case is highest. In sweep-based scheme, the circle points transmit messages only to the next circle point. Hence, the message exchange overhead in this case is less than that of scan-based method, which performs their scan as twice.

Fig. 8

Message transmission overhead with varying number of coronas

Figure 9 presents the simulation results for total number of sensor movements for different deployment schemes. The scan-based method partitions the network into more number of coronas than the sweep-based method. As a result, the number of movements of the sensors in case of scan-based method is more than the sweep-based method. However, the number of movement in case of sweep-based method is more than that in case of ACO scheme. This is because of the fact that the in ACO scheme, sensors are moved only to those circle points, which require additional energy. On the other hand, in sweep-based scheme, if a circle point possess additional energy, it will move its sensors to the next circle point, irrespective of the energy requirement of the next circle point.

Fig. 9

The total movement distance of ACO, sweep-based, and scan-base methods varying the number of sensors

6 Conclusion

In this paper, we have proposed an energy-efficient sensor deployment scheme, which can ensure a complete coverage of the monitoring area and prolong the lifetime of the network. While proposing the deployment scheme, we consider the real world environment, where the initial energy of the sensors may be different from each other. Our deployment scheme is divided into three parts. First, to achieve full coverage using as few sensors as possible, we compute the average angle between the sensors nodes. Then, we provide two methods to achieve energy balance. We propose a sweep-based scheme to move the sensors as request. We also transform the deployment problem into the multiple knapsack problem. And based on ACO algorithm, we propose a deployment strategy to prolong the network lifetime. The simulation results show that our strategy ensures prolonged network lifetime significantly, especially in case when the initial energy of the sensors is different from each other.