1 Introduction

Wireless sensor networks are applicable in many fields such as military surveillance, environmental monitoring, structural monitoring, security and traffic control (Chong and Kumar 2003). Network lifetime (The duration between the network starts functioning to the coverage requirement not satisfied.) play a crucial role in development of the wireless sensor network (WSN). Efficient use of energy can be one factor to develop an efficient WSN because the sensors nodes in WSN are battery powered.

Coverage (The region should be monitored by some sensor nodes according to the degree of reliability.) must be guaranteed in WSN to achieve to the data from the whole area. Position of sensor nodes plays a major role in the algorithms which are designed to achieve the required coverage inside the WSN (Wang et al. 2010). The coverage problem can be classified into two types as: Point or target coverage and Area or region coverage. The meaning of k-coverage in target coverage is that each target nodes must be covered by at least k sensor nodes. The sensor nodes in a region can be deployed in two manners one is random and second is deterministic. In random deployment, the sensor nodes are deployed randomly in an area which is inaccessible to human such as military wars. The only way to achieve the efficiency in WSN is the efficient scheduling of sensor nodes in such a ways that some sensor nodes should be active at a time which provide the proper coverage (Huang and Tseng 2003). The second way of deployment is deterministic, in this; the region of deployment is known apriori. There are two ways to design the efficient WSN one is to find the deployment positions of the sensor nodes that achieves maximum coverage and second is scheduling of sensor nodes. Once the optimized positions of sensor nodes are known, we can schedule the sensor nodes to provide the maximum lifetime. In the further text WSN and network are used interchangeably.

The rest of paper is organized as follows: in Sect. 2, we briefly reviews some related literatures. Section 3 formulates the problem. In Sect. 4, we have explored the proposed approach to solve the considered problem. Section 5 presents the simulation results and discussion about results. Concluding remarks are given in Sect. 6.

2 Related works and motivation

Most of the research on deployment problem focuses on the area coverage. Onur et al. (2005) have focused on quality of deployment and quality measures. Quality of deployment specify that the sufficient area is covered or not and quality measures considered that redeployment is required or not. Bai et al. (2006, 2010) worked on the optimal coverage and deployment pattern that provides more than two-connectivity and proposed diamond and double striped pattern. Diamond pattern can be viewed as a series of evolving patterns; they have given voronoi diagram based methodology for sensor deployment also. Chang et al. (2008) proposed some methods for deployment of sensor nodes that improves the lifetime of the network by mitigating the hotspot around the sink. Yun et al. (2010) considered the problems of Bai et al. (2006) and proposed the sensor deployment pattern for 3-, 4-, 5-, 6-connectivity inside the network. Ozturk et al. (2011) give the ABC (Artificial Bee Colony) algorithm based dynamic sensor deployment method that considers the stationary and mobile sensor nodes on a probabilistic detection model. Many researchers have proposed strategies to solve the sensor scheduling for area coverage problem (Liu et al. 2005; Yen and Cheng 2009; Keshavarzian et al. 2006; Makhoul and Pham 2009; Chang and Chang 2008). Udgata et al. (2009) give an ABC algorithm based deployment strategy, but it can be applied if the numbers of target nodes are more as compared to the number of sensor nodes. They are able to get the energy efficiency by reducing the sensing range of the sensor nodes. Mini et al. (2011) proposes a heuristic algorithm to schedule the sensor nodes inside the network that can increase the lifetime of the network. The heuristic is able to achieve the upper bound for all experimental cases.

In the literature, the deployment and scheduling are considered as independent problems. In this paper, we have considered deployment and scheduling of sensor nodes as one problem. The coverage must be considered as a crucial factor to evaluate the sensor network. The coverage inside the network can depend upon the applications such as for habitat and environmental monitoring the lower level of coverage can be efficient but for tracking a target, we need a higher level of coverage (Li and Gao 2008). The level of coverage can vary for the same application which depends upon the situation, for example, the detection of fire in a forest required less coverage in rainy season as compared to summer season. Sensor deployment and scheduling must be considered as one to increase the lifetime of the network and to provide balanced performance which is crucial for most applications.

3 Problem formulation

Let, a region (x × y) contains n targets as {T 1, T 2, T 3 … T n } and m sensor nodes {S 1, S 2, S 3 … S m } should be placed in such a manner that can fulfill the coverage requirements. The objectives that are covered in this paper are:

  • To deploy the sensor nodes in a particular region to achieve the coverage requirement and maximum lifetime.

  • To provide the different schedule of sensor nodes to maximize the optimal network lifetime with optimum coverage.

3.1 Maximum lifetime of the network

Let m sensors nodes {S 1, S 2, S 3 … S m } covers n target nodes {T 1, T 2, T 3 … T n } placed in a region \( \left( {x \times y} \right) \). The sensing range of each sensor node is r and the initial energy of the sensor node is E. The measure by which the sensor Si, 1 ≤ i ≤ m, covers the target Tj, 1 ≤ j ≤ n is given by the coverage matrix (Mij) as:

Let the target node Tj is placed at (a,b) and sensor node Si is placed at (xi,yi) then.

$$ {\text{M}}_{\text{ij}} = \left( {{\text{x}}_{\text{i}} - {\text{a}}} \right)^{2} + \left( {{\text{y}}_{\text{i}} - {\text{b}}} \right)^{2} - r^{2} \quad {\text{for i}} = 1,2,3 \ldots {\text{m and j}} = 1,2,3 \ldots {\text{n}} . $$
(1)

Coverage lifetime factor is given as stated in Onur et al. (2005), Bai et al. (2006).

$$ {\text{Coverage lifetime factor}} \left( {\text{f}} \right) = \min_{j} \left[ {\frac{{\mathop \sum \nolimits_{i} M_{ij} \times b_{i}^{{\prime }} }}{{q_{j} }}} \right] $$
(2)

where \( b_{i}^{{\prime }} = \frac{{E_{i} }}{{e_{i} }} \), ei represents the power consumption rate of Si and Ei shows the initial energy of the sensor node. For k-coverage qj = k. As the Coverage lifetime factor decreased the coverage lifetime increased because negative value of Mij depicts that the target is inside the sensing range of the sensor node.

3.2 Sensor deployment

  1. 1.

    1-Coverage deployment: Given a set of m sensor nodes {S 1, S 2, S 3 … S m } and n target nodes \( \left\{ {T_{1} ,T_{2} ,T_{3} \ldots T_{n} } \right\} \), to satisfy the requirement of 1-coverage the sensor nodes should be deployed in such a manner so that each target is covered by at least one target node and to minimize f.

  2. 2.

    k-Coverage deployment: Given a set of m sensor nodes {S 1, S 2, S 3 … S m } and n target nodes \( \left\{ {T_{1} ,T_{2} ,T_{3} \ldots T_{n} } \right\}. \) For k-coverage deployment each target node must be monitored by k sensor nodes and to minimize f.

3.3 Sensor scheduling

  1. 1.

    1-Coverage scheduling: Suppose m sensor nodes {S 1, S 2, S 3 … S m } are given that can monitor n target nodes \( \left\{ {T_{1} ,T_{2} ,T_{3} \ldots T_{n} } \right\}. \) then 1-coverage schedule {H 1, H 2, H 3 … H c } for times {t 1, t 2, t 3 … t c } means each target node is monitored by at least one sensor node and maximize the network lifetime \( \sum\nolimits_{v = 1}^{c} {t_{v} } \).

  2. 2.

    k-Coverage scheduling: Assume m sensor nodes {S 1, S 2, S 3 … S m } and n target nodes {T 1, T 2, T 3 … T n }. k-coverage schedule {H 1, H 2, H 3 … H c } for times {t 1, t 2, t 3 … t c } means each target node is monitored by k sensor node and maximize the network lifetime \( \sum\nolimits_{v = 1}^{c} {t_{v} } \).

4 Proposed method

The Senor nodes can be deployed randomly or deterministically, for deterministic deployment of sensor nodes, it’s possible at sink to determine the best position of the sensor node before actual deployment. The proposed algorithm 1 considers two cases:

  • Case 1: The given n target nodes {T 1, T 2, T 3 … T n } and m sensor nodes {S 1, S 2, S 3 … S m } are not mobile.

  • Case 2: The given n target nodes {T 1, T 2, T 3 … T n } and m sensor nodes {S 1, S 2, S 3 … S m } are mobile with some initial velocities.

Our method is twofold: First fold consists of two cases, for case 1 Simulated Annealing algorithm is used to find the optimal location of the sensor nodes that achieves maximum coverage and lifetime of the network. For case 2 particle swarm optimization algorithm is applied to get the optimal locations of sensor nodes with required velocities, and provides maximum coverage and lifetime of the network. In the other fold it provides the scheduling algorithm that can provide the different schedule for different time slots and maximize the network lifetime.

figure a

4.1 Sensor deployment

Deterministically, the maximum lifetime or minimum coverage lifetime factor of the network can be computed (Onur et al. 2005; Bai et al. 2006). One of these factors can be used as fitness function to find the optimized location of sensor nodes according to the required k-coverage. For getting the optimized location, simulated Annealing (SA) (Kirkpatrick et al. 1983) and Particle swarm optimization (PSO) (Kennedy and Eberhart 1995; Eberhart and Kennedy 1995) can be applied on the basis of mobility of the nodes.

  1. 1.

    SA based sensor deployment: Simulated Annealing is a probabilistic method used in Bai et al. (2010) for achieving the global minima of a cost function that contain many local minima. It depends on a physical process where a solid is slowly cooled so that it eventually gets frozen this occurs at minimum energy configuration.

Suppose the solution population is Y = {(x 1, y 1), (x 2, y 2), (x 3, y 3) …, (x m , y m )}. Initially the sensor nodes {S 1, S 2, S 3 … S m }are randomly deployed inside the region. The target nodes {T 1, T 2, T 3 …T n } are located inside the region. Algorithm 2 elaborates the steps of SA.

figure b

Here k represents Boltzman Constant.

  1. 2.

    PSO based Sensor Deployment: Particle swarm optimization method consists of many swarm particles moving in a search space to provide the optimized solution of a problem. Every particle has a position vector and a velocity vector. Position vector is an actual candidate of the solution. These particles have a small amount of memory that can store its global best position and local best position which are obtained by communicating with neighboring particles (Cheng et al. 2008; Yun et al. 2010).

A particle p occupies position xpd and velocity vpd in the dth dimension of the hyperspace, 1 ≤ p ≤ m and 1 ≤ d ≤ nd. We have taken two dimension (d1,d2) of hyperspace.

Let the target node Tj is placed at (a,b) and sensor node Si is placed at (xid1,xid2) and, if the sensing range of the sensor node is r then

$$ \begin{aligned} M_{ij} & = \left( {x_{{id_{1} }} - a} \right)^{2} + \left( {x_{{id_{2} }} - b} \right)^{2} - r^{2} \\ {\text{For}}\;{\text{i}} = 1,2,3, \ldots {\text{m and j}} = 1,2,3,4 \ldots {\text{n}}. \\ \end{aligned} $$
(3)

Algorithm 3 shows the steps that are used to provide PSO based sensor deployment.

figure c

4.2 Sensor scheduling

As mentioned earlier, second objective of this paper is to schedule the sensor nodes such that it improves the lifetime of the network. The given algorithm 4 is used to find the different set of schedules that monitored the targets according to k-coverage and maximize lifetime of the network.

figure d
  1. 1.

    Optimized Cover by SA: There are three methods that all together used to find the optimized cover:

  2. (a)

    SA cover method: SA cover method is used to provide the different covers that provide the required k-coverage and maximize the lifetime of the network. The optimized solution which has provided less ∆f value is the right choice. The value of b ’ i is decreased by random factor between [0,1]. Algorithm 5 explores the steps of SA cover method.

    figure e
  3. (b)

    Coverage method: This method maintains the coverage matrix as given in Eq. (1). The method, initially applies cover assignment method to find the cover for each target node then applies the coverage method to evaluate the elements of coverage matrix. Algorithm 6 gives the details of coverage method.

    figure f
  4. (c)

    Cover Assignment method: This method is used to provide the maximum number of sensor nodes that cover a particular target node. The information that is provided by cover assignment method is used to find the different covers by using the Dempster Shafer theory.

    figure g
  5. 2.

    Schedules by dempster shafer theory: Dempster Shafer Theory (DST) is a mathematical theory of evidence. DST combines the independent items of evidence from different sources and arrives at a degree of belief (Ozturk et al. 2011; Liu et al. 2005). It is applied to find the different schedules of sensor nodes. The DST calculates three terms:

    • Mass

    • Belief

    • Plausibility

In the following sections, these terms are calculated by using three algorithms as Mass Assignment Algorithm, Belief Assignment Algorithm and Plausibility Assignment respectively.

  1. (a)

    Mass assignment algorithm:

Mass (B) refers to the proportion of all relevant and evidences that supports the reason that actual state belongs to B, where B is a member of the power set of a given hypotheses. If a sensor node (i) covers a target node(j) then the value of cover[j][i] is 1. The algorithm calculates the cover value of each element in the power set of sensor nodes and then evaluates the mass value for each element in the power set. Details are given in Algorithm 8 for assigning the masses to different hypotheses.

figure h
  1. (b)

    Belief assignment algorithm:

Belief (B) is the sum of masses of all subsets of B (including B), where B is a member of hypotheses. Algorithm 9 gives the details of assigning the Belief to each element in the power set of sensor nodes.

figure i
  1. (c)

    Plausibility assignment:

Plausibility (P) is the sum of all members of hypotheses that intersect with B. Algorithm 10 shows the steps of Plausibility Assignment algorithm.

figure j

The Belief interval [Belief (B), Plausibility (B)] is used to find the certainty of the belief. A small difference between Belief and Plausibility shows, we are certain about our belief and a large value depicts, we are uncertain about our belief.

5 Results and discussion

For evaluating the performance of deployment methods, we have used MATLAB 2007b. We have taken 10 and 20 sensor nodes to check the performance of proposed methods. Coverage, we have considered in the evaluation is k-coverage where k = 1, 2, 3, 4, 5. Two scenarios are developed for simulating the deployment algorithm by using simulated annealing. Scenario 1 contains 10 sensor nodes and 10 target nodes; scenario 2 contains 20 sensor nodes and 10 target nodes. The initial position of sensor nodes for scenario 1 is {(4,5), (10,12), (15,10), (2,3), (4,6), (6,10), (1,2), (3,2), (4,3), (20,10)} respectively. Target nodes position for scenario1 and scenario2 is {(2,3), (1, 11), (12,8), (2,3), (2,6), (10,10), (8,4), (4,6), (4,10), (17,12)}. The Battery power (in nJ) for each sensor of scenario 1 is given as {12, 5, 9, 5, 7, 9, 10, 11, 17, 18} respectively. Minimum battery requirement for a sensor node is more than 1 nJ to work as active sensor node inside the sensor network. The sensing range of the sensor nodes is 5 m. Figures 1, 2, 3, 4 and 5 shows the optimized location of sensor nodes after the application of SA based sensor deployment method for different k-coverage in scenario 1.

Fig. 1
figure 1

Optimized location of sensor nodes (1-coverage)

Full size image
Fig. 2
figure 2

Optimized location of sensor nodes (2-coverage)

Full size image
Fig. 3
figure 3

Optimized location of sensor nodes (3-coverage)

Full size image
Fig. 4
figure 4

Optimized location of sensor nodes (4-coverage)

Full size image
Fig. 5
figure 5

Optimized location of sensor nodes (5-coverage)

Full size image

For scenario 2 the sensor nodes are initially positions at {(14, 11), (12, 2), (5, 23), (5, 6), (8, 1), (15, 7), (3, 7), (1, 4), (14, 8), (13, 6), (10, 20), (23, 12), (6, 5), (7, 9), (11, 23), (5, 4), (7, 4), (3, 8), (3, 1), (12, 1)}. The Battery power (in nJ) for these sensor nodes is {12.3, 5, 9, 5, 7, 9, 10, 11, 17.6,18, 23, 43, 7.1, 8, 12, 23, 11, 10.4, 9, 20} respectively. Minimum battery requirement for a sensor node is more than 1 nJ to work as active sensor node inside the sensor network. The sensing range of the sensor nodes is 5 m. Figures 6, 7, 8, 9 and 10 shows the optimized location of sensor nodes for scenario 2 with different k-coverage.

Fig. 6
figure 6

Optimized location of sensor nodes (1-coverage)

Full size image
Fig. 7
figure 7

Optimized location of sensor nodes (2-coverage)

Full size image
Fig. 8
figure 8

Optimized location of sensor nodes (3-coverage)

Full size image
Fig. 9
figure 9

Optimized location of sensor nodes (4-coverage)

Full size image
Fig. 10
figure 10

Optimized location of sensor nodes (5-coverage)

Full size image

For evaluating the performance of PSO based sensor nodes deployment algorithm, we have designed two scenarios. Scenario 1 consists of 10 sensor nodes and 10 target nodes which are placed at {(4, 5), (10, 12), (15, 10), (2, 3), (4, 6), (6, 10), (1, 2), (3, 2), (4, 3), (20, 10)} and {(2, 3), (1, 11), (12, 8), (2, 3), (2, 6), (10, 10), (8, 4), (4, 6), (4, 10), (17, 12)} respectively. The sensor nodes contain the battery power (nJ) as {12, 5, 9, 5, 7, 9, 10, 11, 17, 18}. The coverage is k-coverage where k = 1, 2, 3, 4, 5 and the minimum power required by a sensor node to work in active mode is 1 nJ. Figure 11 shows the optimized position of sensor nodes and target nodes. Figure 11 shows the optimized location of sensor nodes in first iteration, middle iterations and last iteration in left to right order. In the same manner Figs. 12, 13, 14 and 15 shows the optimized positions of sensor nodes and target nodes.

Fig. 11
figure 11

Optimized location of sensor nodes and target nodes (1-coverage)

Full size image
Fig. 12
figure 12

Optimized location of sensor nodes and target nodes (2-coverage)

Full size image
Fig. 13
figure 13

Optimized location of sensor nodes and target nodes (3-coverage)

Full size image
Fig. 14
figure 14

Optimized location of sensor nodes and target nodes (4-coverage)

Full size image
Fig. 15
figure 15

Optimized location of sensor nodes and target nodes (5-coverage)

Full size image

In the second scenario for evaluating the PSO based sensor deployment algorithm, we have considered 20 sensor nodes and 20 target nodes which are positioned at {(14, 11), (12, 2), (5, 23), (5, 6), (8, 1), (15, 7), (3, 7), (1, 4), (14, 8), (13, 6), (10, 20), (23, 12), (6, 5), (7, 9), (11, 23), (5, 4), (7, 4), (3, 8), (3, 1), (12, 1)} and {(2, 3), (15, 7), (9, 2), (10, 7), (2, 8), (10, 12), (12, 22), (14, 11), (23, 2), (8, 5), (14, 9), (12, 10), (11, 8), (7, 13), (18, 10), (20, 12), (21, 9), (15, 8), (17, 8), (9, 12)} respectively. The battery power (in nJ) of sensor nodes is as {12, 4, 9, 12, 13, 17.1, 21, 22, 56, 43, 7, 8, 11, 10.2, 14, 17, 19, 21, 16.3, 22}. The sensing range of each sensor nodes is as 5 m. Minimum battery required by a sensor node to work as active is 1 nJ. Figure 16 shows the position of sensor nodes and target nodes in first iteration, mid-iterations and last iteration from left to right order. In the same way Figs. 17, 18, 19 and 20 show the optimized location of sensor nodes and target nodes.

Fig. 16
figure 16

Optimized location of sensor nodes and target nodes (1-coverage)

Full size image
Fig. 17
figure 17

Optimized location of sensor nodes and target nodes (2-coverage)

Full size image
Fig. 18
figure 18

Optimized location of sensor nodes and target nodes (3-coverage)

Full size image
Fig. 19
figure 19

Optimized location of sensor nodes and target nodes (4-coverage)

Full size image
Fig. 20
figure 20

Optimized location of sensor nodes and target nodes (5-coverage)

Full size image

As mentioned in the above text, we have applied the Dempster Shafer Theory to get the schedules of sensor nodes. The group of sensor nodes that provides minimum difference between belief and plausibility are good candidate for selection. On the basis of this selection, we have achieved the lifetime of the sensor network. We have compared the lifetime of the WSN after application of Dempster Shafer Theory with the lifetime of the WSN with random deployment of the senor nodes. Two scenarios are considered, scenario1 contains 10 sensor nodes and 10 target nodes and scenario 2 has 14 sensor nodes and 10 target nodes, with the sensing range of senor nodes as 5 m and k-coverage where k = 1, 2, 3, 4, 5 for both scenarios. Figures 21, 22, 23, 24, 25 shows the belief- plausibility difference for different groups of sensor nodes with different k-coverage where k = 1, 2, 3, 4, 5 for scenario 1. The result of comparison for scenario 1 is shown in Fig. 26. The belief- plausibility difference for different groups of sensor nodes with different k-coverage where k = 1, 2, 3, 4, 5 for scenario 2 is given in Figs. 27, 28, 29, 30, 31 and the figure for comparison of lifetime is shown in Fig. 32.

Fig. 21
figure 21

Belief-Plausibility difference for different group of sensor nodes (1-coverage)

Full size image
Fig. 22
figure 22

Belief-Plausibility difference for different group of sensor nodes (2-coverage)

Full size image
Fig. 23
figure 23

Belief-Plausibility difference for different group of sensor nodes (3-coverage)

Full size image
Fig. 24
figure 24

Belief-Plausibility difference for different group of sensor nodes (4-coverage)

Full size image
Fig. 25
figure 25

Belief-Plausibility difference for different group of sensor nodes (5-coverage)

Full size image
Fig. 26
figure 26

Lifetime of the network for 10 sensor nodes (comparison between random deployment and after application of proposed method)

Full size image
Fig. 27
figure 27

Belief-Plausibility difference for different group of sensor nodes (1-coverage)

Full size image
Fig. 28
figure 28

Belief-Plausibility difference for different group of sensor nodes (2-coverage)

Full size image
Fig. 29
figure 29

Belief-Plausibility difference for different group of sensor nodes (3-coverage)

Full size image
Fig. 30
figure 30

Belief-Plausibility difference for different group of sensor nodes (4-coverage)

Full size image
Fig. 31
figure 31

Belief-Plausibility difference for different group of sensor nodes (5-coverage)

Full size image
Fig. 32
figure 32

Lifetime of the Network for 14 sensor nodes (Comparison between random deployment and after application of proposed method)

Full size image

5.1 Key findings

We have simulated the proposed methods and found the following important results (shown in Tables 1, 2)

Table 1 Increase in lifetime
Full size table
Table 2 Increase in lifetime
Full size table

From the data given in Tables 1 and 2, we can conclude that for 10 sensor nodes in average the increment in the lifetime for k-coverage is 27.795 % and for 14 sensor nodes in average the improvement in the lifetime of the sensor network is 33.4266 %.

6 Conclusion

In this paper, Simulated Annealing and Particle Swarm Optimization approaches are used to calculate the optimized location of sensor nodes for deployment in a region which have some target nodes. These approaches depend on the mobility of sensor and target nodes. In order to increase the lifetime of the wireless sensor network, the approach of scheduling the sensor nodes is applied, for this purpose Simulated Annealing and Dempster Shafer Theory is used. The Dempster Shafer Theory provides the different schedules for sensor nodes that cover the target nodes according to k-coverage requirement. The schedule that contains minimum sensor nodes and fulfills the coverage needs has higher priority than the schedule that has more sensor nodes.