A sensor node scheduling algorithm for heterogeneous wireless sensor networks

Abstract

To improve the regional coverage rate and network lifetime of heterogeneous wireless sensor networks, a sensor node scheduling algorithm for heterogeneous wireless sensor networks is proposed. In sensor node scheduling algorithm, heterogeneous perception radius of sensor node is considered. Incomplete coverage constraint and arc coverage interval are analyzed. Regional coverage increment optimization model, arc coverage increment optimization model, and residual energy optimization model are proposed. Multi-objective scheduling model is established using weight factors and integrated function. Furthermore, the heuristic method is proposed to solve the multi-objective optimization model, and scheduling scheme of heterogeneous sensor nodes is obtained. When the network is in operation for a period of time, some sensor nodes are invalid and relevant regions are uncovered. The repair method is proposed to wake up sleep sensor nodes and repair the coverage blind area. The simulation results show that if keeping the same regional coverage rate, sensor node scheduling algorithm improves network lifetime, increases number of living sensor nodes, and keeps average node energy consumption at a low level. Under certain conditions, sensor node scheduling algorithm outperforms DGREEDY, two-tiered scheduling, and minimum connected cover.

Keywords

Heterogeneous wireless sensor networks network lifetime regional coverage arc coverage residual energy

Introduction

Comparing with wired data-collecting devices, wireless sensor networks (WSNs) which are composed of distributed sensor nodes and sink nodes are useful, efficient, and simple data-collecting devices. In WSNs, sensor nodes have the functions such as data perception, data processing, and wireless communication. They are light-weight, small-sized, low-cost, battery-driven, and easy to install.¹ WSNs can be applied to industrial and civil fields such as environment monitoring, intelligent transportation, smart nursing, smart home, and smart factory.²

In WSNs, network coverage and lifetime are limited by node’s energy. High network coverage ensures that sensor nodes can sense the data of most monitoring area. Network coverage is divided into three types according to sensed objects, such as target coverage, barrier coverage, and regional coverage. In target coverage, sensor nodes cover all target points. When there are sufficient target points which spread all over the monitoring area, target coverage can turn into regional coverage. In barrier coverage, sensor nodes completely cover a line. When there are sufficient lines, barrier coverage can turn into regional coverage. Regional coverage is a basic type of network coverage. It is applied to many fields such as environment monitoring and smart factory. Network lifetime is the effective working time of WSNs to collect data. When network lifetime increases, the lifetime of sensor nodes increases and application cost reduces. Therefore, the design of WSNs should keep satisfactory regional coverage rate and keep data collection for months or years in the environment monitoring and some other application fields.³

At present, the study of WSNs got some achievements. Some scholars have studied the coverage problem of static isomorphic sensor nodes. Wang et al.³ use probability theory to study the relationship between network coverage and lifetime. Then they propose some formulae of network lifetime under different kinds of Gaussian distribution. Krause et al.⁴ propose a distribution and scheduling algorithm of sensor nodes. According to cycle analysis of each node, sensor nodes which improve regional coverage rate are added to several disjoint sets. Singh and Rossi⁵ consider the data perception direction of each sensor node and establish lifetime optimization model. They use column generation algorithm to divide the model into master model and sub-model and solve the two models to obtain optimal scheme. Lim and Bleakley⁶ find several sets of sensor nodes and propose greedy algorithm to cover the monitoring area as much as possible. Meanwhile, they use normalized cut clustering algorithm to cluster the sensor nodes and obtain a set of all cluster heads. Finally, they eliminate the sensor nodes which are selected before and use loop iteration to obtain several sets of sensor nodes. However, the literature^3–6 uses centralized algorithms. They need to collect the information of all sensor nodes and require a lot of calculation workload. Tezcan and Wang⁷ propose two-tiered scheduling (TTS) mechanism for energy conservation. TTS proposes node weight formula based on node energy consumption and regional coverage increment. Each sensor node sets delay time which is proportional to the weight and wakes up to judge whether it is covered by other sensor nodes. If it is covered by other sensor nodes, the sensor node is in sleep state. If not, the sensor node is in work state. He et al.⁸ study distributed scheduling algorithm of sensor nodes to cover all regions. In the algorithm, each node calculates its own weight. If the weight is less than the threshold, the sensor node is in sleep state. If not, the sensor node judges whether it is the sensor node of the smallest weight. If it is, the sensor node is in work state. Idrees et al.⁹ propose a distributed optimization algorithm of network lifetime and coverage. In the algorithm, the monitoring area is divided into several subregions, and each subregion has a cluster head. The cluster head collects the information of its members to establish an optimization model for maximizing network coverage and minimizing the number of working sensor nodes. Then the cluster head solves the optimization model and obtains the working state of each sensor node. In short, the literature^3–9 assume that all sensor nodes in the network are the same. Namely they are isomorphic. However, in some special applications, perception radii and energy of sensor nodes are heterogeneous.

Therefore, some scholars have studied coverage problem of static heterogeneous sensor nodes. Li¹⁰ considers heterogeneous perception radii of sensor nodes and proposes a scheduling algorithm of heterogeneous sensor nodes. The algorithm establishes a multi-objective scheduling model. It uses a differential evolution algorithm to solve the model and obtains optimal scheme. Du et al.¹¹ turn regional coverage problem into multi-line coverage problem. Then they propose an optimization model of mobile sensor nodes, solve the optimization model by linear algorithm, and obtain the shortest movement scheme. However, the literature^10,11 uses centralized algorithms. The computation workload rises sharply when number of sensor nodes increases. Lin et al.¹² establish a disjoint connection coverage set which meets the requirement of perception coverage and network connection. They analyze number constraint of connection coverage set, coverage constraint, connection constraint, and routing constraint. Then they establish an optimization model and use ant algorithm to obtain optimal scheming. According to locations of neighbor nodes, Sun et al.¹³ use redundancy algorithm to judge the state of sensor nodes. If the sensor node is a redundant node, it turns into sleep state. Khedr and Osamy¹⁴ propose minimum connected cover (MCC) algorithm of a query region. MCC considers several heterogeneous sensor nodes in the monitoring area and uses a scheduling algorithm of sensor nodes to obtain MCC of monitoring area. The literature^12–14 uses distributed algorithms, but they neglect network lifetime. When sensor nodes exhaust energy or are damaged, the sensor nodes are invalid and coverage blind area appears. They also neglect the repair problem of coverage blind area.

In short, the coverage optimization algorithms of static isomorphic sensor nodes have good performance. However, they do not consider heterogeneous sensor nodes and cannot be applied to coverage optimization of static heterogeneous sensor nodes. On the other hand, because more parameters need to be considered, and the model and solution are more complicated, the coverage optimization algorithms of static heterogeneous sensor nodes do not consider network lifetime, regional coverage rate, and coverage repair simultaneously. Therefore, a sensor node scheduling algorithm (SNSA) for heterogeneous WSNs is proposed based on above references. In SNSA, regional coverage increment optimization model, arc coverage increment optimization model, and residual energy optimization model are established. Weight factors and integrated function are used to establish a multi-objective scheduling model. Heuristic method is proposed to solve the model and obtain the scheduling scheme of static heterogeneous sensor nodes. When the network is in operation for a period of time, some sensor nodes are invalid and relevant regions are uncovered. Repair method is proposed to wake up sleep sensor nodes and repair the coverage blind area. Therefore, SNSA obtains maximum regional coverage rate and improves network lifetime.

Principle of SNSA

In SNSA, we assume that

In two-dimensional WSNs, there are heterogeneous sensor nodes and sink node. All nodes are static.

Sensor nodes have different perception radius. Namely they are heterogeneous.

Sensor nodes can obtain their own locations according to GPS, Beidou satellite positioning module or other positioning algorithms.

Sensor nodes have two schedulable state such as work state and sleep state. Sensor nodes in work state sense data and send the data to sink node.

Sensor nodes have the same communication radius and initial energy. Sink node has larger initial energy and longer lifetime. Therefore, the energy of sink node is considered as unlimited within limited network lifetime.

Sensor nodes are randomly distributed in the monitoring area and can obtain their own locations, as shown in Figure 1. When the network starts, sink node and sensor nodes periodically send information packages of their own and receive information packages of neighbor nodes. The information package contains location, perception radius, residual energy, etc. Then they update the information table of neighbor sensor nodes. In some nodes, the multi-objective scheduling model with information of neighbor sensor nodes is established and solved. Optimal scheduling scheme of neighbor sensor nodes is obtained. The neighbor nodes are informed into work static or sleep static. When a sensor node exhausts energy or is damaged, coverage blind area appears. The relevant sensor nodes analyze the scheduling states of neighbor sensor nodes to judge whether there is coverage blind area. If there is coverage blind area, some sleep sensor nodes are waked up to repair the coverage blind area. It can improve regional coverage rate and network lifetime. However, SNSA needs to solve the following three problems. First, how to establish the multi-objective scheduling model with the information of neighbor nodes, such as locations, perception radii, and residual energy. Second, how to solve the multi-objective scheduling model and obtain scheduling scheme of neighbor sensor nodes. Third, how to schedule sleep sensor nodes to repair the coverage blind area and improve network lifetime when there is coverage blind area. The three problems are solved as follows.

Figure 1.

Principle of SNSA.

Multi-objective scheduling model establishment

When SNSA starts, all sensor nodes are in work state. As shown in Figure 2, first sink node broadcasts information collecting package to neighbor sensor nodes. When the neighbor sensor nodes receive the information collecting package, they send information packages of their own. The information package contains location, perception radius, residual energy, current state, and so on. According to above information, sink node establishes scheduling model and solves to obtain scheduling scheme of neighbor sensor nodes. Sink node sends scheduling state acknowledge package and scheduling calculation start package to inform its neighbor sensor nodes. Second, if a sensor node receives scheduling state acknowledge package, it turns into the state which is required in the package. If a sensor node receives scheduling calculation start package, it establishes scheduling model and starts scheduling calculation which is the same as sink node. Then it sends scheduling state acknowledge package and scheduling calculation start package to inform its neighbor nodes. Third, when a sensor node does not receive scheduling information, it tries to find data communication path to sink node. If the path to sink node exists, the sensor node starts scheduling calculation. Finally, all sensor nodes receive or calculate their states. The establishment of scheduling model is as follows.

Figure 2.

Information collection of sensor nodes.

$X_{i}^{Z} = [x_{1}, x_{2}, \dots, x_{N_{i}^{z}}]$ represents current state set of node i’s neighbor nodes which are not scheduled before. $N_{i}^{Z}$ represents the number of node i’s neighbor nodes which are not scheduled before. $x_{v}$ is $1 \times 2$ dimensional array $[a_{v}, b_{v}]$ . $a_{v}$ represents the ID of node. $b_{v}$ represents state flag of sensor node. $b_{v} = 1$ represents that the node is in work state. $b_{v} = 0$ represents that the node is in sleep state. The perception range of each sensor node under work state in $X_{i}^{Z}$ cannot be fully covered by the perception range of neighbor sensor nodes. Therefore, the incomplete coverage constraint is

\begin{matrix} ‖ P_{a_{v}} - P_{a_{w}} ‖ \geq | G_{a_{v}} - G_{a_{w}} |, b_{v} = b_{w} = 1, \\ \forall a_{v} \in X_{i}^{Z}, \forall a_{w} \in X_{i}^{C} \end{matrix}

(1)

where $P_{a_{v}}$ represents location coordinates of node $a_{v}$ , $‖ P_{a_{v}} - P_{a_{w}} ‖$ represents the distance between two nodes, $G_{a_{v}}$ represents perception radius of node $a_{v}$ , and $X_{i}^{C}$ represents scheduling state set of node i’s neighbor sensor nodes whose states are determined before.

One target for scheduling neighbor sensor nodes is to improve regional coverage rate. Regional coverage increment optimization model is established as follows

\max (Δ cov {er}_{i})

(2a)

s . t . Δ cov {er}_{i} = cov er (X_{i}^{C} \cup X_{i}^{z}) - cov er (X_{i}^{C})

(2b)

where $Δ cov {er}_{i}$ represents regional coverage increment of node i, $cov er (X_{i}^{C} \cup X_{i}^{z})$ represents regional coverage rate according to node scheduling state set $X_{i}^{C} \cup X_{i}^{z}$ , and $cov er (X_{i}^{C})$ represents regional coverage rate according to node scheduling state set $X_{i}^{C}$ .

For convenient calculation of regional coverage rate, the area is divided into several grids as shown in Figure 3. The grid’s coordinates are defined as its center’s location coordinates. If grid’s center locates in the perception range of one working sensor node, the grid is covered, namely

C_{g_{v}} (X_{i}) = {\begin{matrix} 1, ‖ P_{g_{v}} - P_{a_{v}} ‖ \leq G_{a_{v}}, \exists a_{v} \in X_{i} \\ 0, others \end{matrix}

(3)

where $X_{i} = X_{i}^{C} \cup X_{i}^{Z}$ represents scheduling state set of node i’s all neighbor sensor nodes and $P_{g_{v}}$ represents location coordinates of gird $g_{v}$ . $C_{g_{v}} (X_{i})$ is a flag. $C_{g_{v}} (X_{i}) = 1$ represents that grid $g_{v}$ is covered by set $X_{i}$ . The calculation formula of regional coverage rate is as follows

cov er (X_{i}) = \sum_{g_{v}} \frac{C_{g_{v}} (X_{i})}{N_{grid}}

(4)

Figure 3.

Coverage calculation method of sensor node.

where $N_{grid}$ represents the total number of grids.

In order to avoid coverage blind area, the arc of perception circle needs to be completely covered by other neighbor nodes. We assume that the location coordinates of two sensor nodes are $(x_{A}, y_{A})$ and $(x_{B}, y_{B})$ , and perception radii of node A and B are r_A and r_B (r_B > r_A). The distance between node A and B is $d_{AB} = \sqrt{{(x_{A} - x_{B})}^{2} + {(y_{A} - y_{B})}^{2}}$ . When $d_{AB} \leq | r_{B} - r_{A} |$ , sensor node A is completely covered by sensor node B, and sensor node A is in sleep state. When $[0, 2 π]$ , there is no interaction between sensor node A and sensor node B. When $| r_{A} - r_{B} | < d_{AB} < | r_{A} + r_{B} |$ , there is interaction between sensor node A and sensor node B. The arc coverage interval of sensor node A covered by sensor node B needs to be calculated.

When $r_{B} \leq d_{AB} < | r_{A} + r_{B} |$ , there are four kinds of interaction between sensor node A and sensor node B, as shown in Figure 4. C is the interaction point of upper arc and vertical line through point A. $θ_{1} = ∠ BAC$ , $θ_{2} = ∠ BAD$ . The value of $θ_{1}$ and $θ_{2}$ is

θ_{1} = arc \cos (\frac{r_{A}^{2} + d_{AB}^{2} - d_{BC}^{2}}{2 r_{A} d_{AB}})

(5)

θ_{2} = arc \cos (\frac{r_{A}^{2} + d_{AB}^{2} - r_{B}^{2}}{2 r_{A} d_{AB}})

(6)

Figure 4.

Four kinds of arc coverage interval between two intersecting circles: (a) is arc coverage interval when $x_{B} \geq x_{A}$ and $θ_{1} \geq θ_{2}$ , (b) is arc coverage interval when $x_{B} \geq x_{A}$ and $θ_{1} < θ_{2}$ , (c) is arc coverage interval when $x_{B} < x_{A}$ and $θ_{1} \geq θ_{2}$ , and (d) is arc coverage interval when $x_{B} < x_{A}$ and $θ_{1} < θ_{2}$ .

where $d_{BC} = \sqrt{{(x_{A} - x_{B})}^{2} + {(r_{A} + y_{A} - y_{B})}^{2}}$ .

$β_{AB}$ represents arc coverage interval of circle A covered by circle B, and $β_{AB} \subseteq [0, 2 π]$ . As shown in Figure 4 (a), when $x_{B} \geq x_{A}$ and $θ_{1} \geq θ_{2}$

β_{AB} = [θ_{1} - θ_{2}, θ_{1} + θ_{2}]

(7)

As shown in Figure 4(b), when $x_{B} \geq x_{A}$ and $θ_{1} < θ_{2}$ , line AB cuts $β_{AB}$ into two parts, namely

β_{AB} = [2 π + θ_{1} - θ_{2}, 2 π] \cup [0, θ_{1} + θ_{2}]

(8)

As shown in Figure 4(c), when $x_{B} < x_{A}$ and $θ_{1} \geq θ_{2}$

β_{AB} = [2 π - θ_{1} - θ_{2}, 2 π - θ_{1} + θ_{2}]

(9)

As shown in Figure 4(d), when $x_{B} < x_{A}$ and $θ_{1} < θ_{2}$ , line AB cuts $β_{AB}$ into two parts, namely

β_{AB} = [2 π - θ_{1} - θ_{2}, 2 π] \cup [0, θ_{2} - θ_{1}]

(10)

Likewise, when $| r_{B} - r_{A} | < d_{AB} < r_{B}$ , arc coverage interval calculation method of circle A covered by circle B is similar as when $r_{B} \leq d_{AB} < | r_{A} + r_{B} |$ . Circle B′ is symmetry with circle B about the line DE, as shown in Figure 5. The arc coverage interval calculation problem is converted to the problem in Figure 4. Namely the arc coverage interval between circle B and circle A is complement of arc coverage interval between circle B′ and circle A

θ'_{1} = π - arc \cos (\frac{r_{A}^{2} + d_{AB}^{2} - d_{BC}^{2}}{2 r_{A} d_{AB}})

(11)

Figure 5.

Symmetric change of circle B.

Then

β_{AB} = {\begin{matrix} [0, {θ'}_{1} - θ_{2}] \cup [{θ'}_{1} + θ_{2}, 2 π], x_{B} \leq x_{A} and {θ'}_{1} \geq θ_{2} \\ [{θ'}_{1} + θ_{2}, 2 π + {θ'}_{1} - θ_{2}], x_{B} \leq x_{A} and {θ'}_{1} < θ_{2} \\ [0, 2 π - {θ'}_{1} + θ_{2}] \cup [2 π - {θ'}_{1} - θ_{2}, 2 π], x_{B} > x_{A} and {θ'}_{1} \geq θ_{2} \\ [θ_{2} - {θ'}_{1}, 2 π - {θ'}_{1} - θ_{2}], x_{B} > x_{A} and {θ'}_{1} > θ_{2} \end{matrix}

(12)

Each sensor node’s arc should be completely covered by neighbor sensor nodes. Namely neighbor nodes are scheduled to improve coverage increment of each node’s perception arc. Therefore, arc coverage increment optimization model is established

\max (Δ Y_{cov er}^{i})

(13a)

s . t . Δ Y_{cov er}^{i} = Y_{cov er} (X_{i}) - Y_{cov er} (X_{i}^{C})

(13b)

Y_{cov er} (X_{i}) = \cup β_{i a_{v}} / 2 π, \forall a_{v} \in X_{i}

(13c)

Y_{cov er} (X_{i}^{C}) = \cup β_{i a_{v}} / 2 π, \forall a_{v} \in X_{i}^{C}

(13d)

X_{i} = X_{i}^{C} \cup X_{i}^{Z}

(13e)

β_{i a_{v}} \subseteq [0, 2 π]

(13f)

where $Δ Y_{cov er}^{i}$ represents arc coverage rate increment of sensor node i, $Y_{cov er} (X_{i})$ represents arc coverage rate of sensor node i according to node scheduling state set $X_{i}$ , and $Y_{cov er} (X_{i}^{C})$ represents arc coverage rate of sensor node i according to node scheduling state set $X_{i}^{C}$ .

In order to improve network lifetime and let sensor nodes with more residual energy turn into work state, residual energy optimization model is established as follows

\max (\frac{E_{ava}^{i}}{E_{in}})

(14a)

s . t . E_{ava}^{i} = (\sum_{a_{v}} E_{a_{v}}^{s}) / N_{i}^{X}

(14b)

E_{a_{v}}^{s} \geq 0, \forall a_{v}

(14c)

where $E_{a_{v}}^{s}$ represents residual energy of sensor node $a_{v}$ , $E_{ava}^{i}$ represents average residual energy of neighbor nodes in work state, $E_{in}$ represents initial energy of sensor node, and $N_{i}^{X}$ represents the number of neighbor sensor nodes in work state. In short, the scheduling problem of sensor nodes is converted into a multi-objective optimization problem. Integrated function is introduced and multi-objective scheduling model is established.

\max f (X_{i}) = w_{1} Δ cov {er}_{i} + w_{2} Δ Y_{cov er}^{i} + w_{3} E_{ava}^{i} / E_{in}

(15)

$s . t . w_{1} + w_{2} + w_{3} = 1$

Formulae (2b), (13b)–(13f), (14b), (14c). Where $f (X_{i})$ represents multi-objective integrated function of node scheduling state set X_i. $w_{1}$ , $w_{2}$ , and $w_{3}$ are weight factors. The sum of $w_{1}$ , $w_{2}$ , and $w_{3}$ is 1.

Model solution with heuristic method

The multi-objective scheduling model equation (15) can be solved by genetic algorithm, particle swarm optimization algorithm, and so on. However, the solving process is complicated, and it needs high-quality processer and a lot of calculation time. Therefore, heuristic method is proposed to obtain suboptimal solution of optimization model (equation (15)). All sensor nodes confirm their own states with multi-level calculation from inside to outside. The specific methods of scheduling calculation and data transmission are as follows.

$V_{s}$ represents set of scheduled sensor nodes. $V_{Z}$ represents set of sensor nodes which are not scheduled before. Sink node uses the following steps to schedule neighbor sensor nodes. Sensor node sets threshold value of node schedule judging time which is determined by network size of WSNs. If one sensor node receives scheduling calculation start package within the threshold time, the sensor node uses the following steps to schedule neighbor sensor nodes which are not scheduled before:

Step 1: The node obtains its own location, perception radius, and the information of neighbor sensor nodes in set $V_{Z}$ . Then it calculates full coverage set, interaction set, and disjoint set of neighbor sensor nodes with inequalities such as $d_{AB} \leq | r_{B} - r_{A} |$ , $| r_{A} - r_{B} | < d_{AB} < | r_{A} + r_{B} |$ , and $| r_{B} + r_{A} | \leq d_{AB}$ .

Step 2: The node informs full coverage nodes to turn into sleep state and adds them to set $V_{s}$ . Then it obtains interaction node set $V_{Z}^{1}$ and number $N_{s}^{Z}$ of interaction nodes and let determined sensor node set $V_{s}^{Z} = \emptyset$ . k = 1.

Step 3: The node calculates regional coverage rate, arc coverage rate and average residual energy according to the information of all sensor nodes in set $V_{s} \cup V_{s}^{Z}$ .

Step 4: The node selects kth sensor node in $V_{Z}^{1}$ , recalculates regional coverage rate, arc coverage rate, and average residual energy when the kth sensor node is in work state. Then the node obtains the weight according to the following formula

f_{k} = w_{1} Δ cov {er}_{i} + w_{2} Δ Y_{cov er}^{i} + w_{3} E_{ava}^{i} / E_{in}

(16)

Step 5: k = k + 1. If $k \leq N_{s}^{Z}$ , go to step 4. If not, the node lets the sensor node with largest weight into work state according to weights of all sensor nodes in $V_{Z}^{1}$ . Then the node adds the sensor node into set $V_{s}^{Z}$ and removes the sensor node from set $V_{Z}^{1}$ .

Step 6: The node judges whether $V_{Z}^{1}$ is an empty set. If $V_{Z}^{1}$ is an empty set, go to step 7. If not, the node judges whether its arc coverage interval is $[0, 2 π]$ according to the node states in $V_{s} \cup V_{s}^{Z}$ . If it is, go to step 7. If not, go to step 3.

Step 7: The node sends scheduling state acknowledge package to neighbor sensor nodes according to present scheduling information. It calculates the arc coverage intervals of sensor nodes which change into work state. Then it sends scheduling calculation start package to the sensor nodes whose arcs are not completely covered.

The sensor nodes in the monitoring area receive other nodes, scheduling state acknowledge package to determine the state of its own. Or they receive scheduling calculation start package to determine the states of their neighbor sensor nodes. However, after running for a period of time, some sensor nodes exhaust energy or are damaged. It leads to network division. Some sensor nodes fail to receive scheduling state acknowledge package and determine its own state. In order to avoid above problem, after scheduling judge time, if a sensor node cannot receive scheduling state acknowledge package, it is waked up to find data communication path to sink node and schedule sleep sensor nodes through the following steps:

Step 1: The sensor node turns into work state and broadcasts path query package which contains its information such as ID and location.

Step 2: If other sensor node receives the path query package, it judges whether the data communication path to sink node exists. If the path exists, the sensor node is informed along the path backward, and the sleep nodes in the path turn into work state.

Step 3: If the sensor node obtains the data communication path to sink node, it uses distributed Bellman_Ford algorithm¹⁵ to calculate path weight. Then it sends path weight to its neighbor sensor nodes. If the sensor node does not obtain the path to sink node, it turns into sleep state.

According to above steps, sink node and sensor nodes in work state establish fully connected network. They directly use distributed Bellman_Ford algorithm to send and route data.

Repair method of coverage blind area

When network is in operation, energy exhaustion or damage of sensor node may lead to the following results. Part of area changes into uncovered area (coverage blind area). When coverage blind area appears, if there are sleep sensor nodes in the vicinity, the sleep sensor nodes are scheduled into work state for repairing the coverage blind area. Namely if sensor node will exhaust energy, it sends energy invalid information package to neighbor sensor nodes. Then the neighbor sensor nodes start to schedule sleep sensor node after delaying a period of time which is proportional to residual energy. The steps of repair method are as follows:

Step 1: If the sensor node receives an invalid information package of neighbor sensor node, it sets delay time which is proportional to the residual energy.

Step 2: After delay time, the sensor node judges whether its arc is completely covered without considering the invalid neighbor sensor nodes. If it is, jump out and end. If not, the sensor node calculates uncovered arc interval $α_{1}$ .

Step 3: The sensor node obtains the set $V_{S}$ of neighbor sleep sensor nodes and the number $N_{L}$ from information table of neighbor sensor nodes, and calculates arc coverage interval $β_{i}$ between each sleep sensor node and its own according to formulae (5)–(10). k = 1.

Step 4: If $\cup β_{i}, \forall i \in V_{s}$ contains or intersects with $α_{1}$ , go to step 5, else jump out and end.

Step 5: The sensor node calculates regional coverage rate increment, arc coverage rate increment, and average residual energy when each sleep sensor node in $V_{S}$ is waken up. Then it calculates weight of each sleep sensor node in $V_{S}$ according to formula (16).

Step 6: The sensor node selects the sleep sensor node with maximum weight, informs it to turn into work state, and removes it from the set $V_{S}$ . Then it judges whether its arc is completely covered. If the arc is not, it updates the uncovered arc interval $α_{1}$ and go to step 4, else jump out and end.

The sensor node which changes from sleep state into work state informs its neighbor nodes. Its neighbor sensor nodes update their information table.

Algorithm implementation

When network starts, sink node and sensor nodes execute different algorithms. Sink node sends scheduling state acknowledge package or scheduling calculation start package to sensor nodes and receives data from sensor nodes. Each sensor node monitors several types of packages, determines the corresponding situation, and implements the corresponding operation, as shown in Figure 6. It is an event-driven algorithm.

Situation 1: If a sensor node receives scheduling state acknowledge package from sink node or other sensor nodes, it confirms its own state and decides to turn into the state which is required in the package.

Situation 2: If a sensor node receives scheduling calculation start package from sink node or other sensor nodes, it calculates the state of neighbor sensor nodes which are not scheduled before. Then it sends scheduling state acknowledge package and scheduling calculation start package to related sensor nodes.

Situation 3: After scheduling judge time, if a sensor node does not receive scheduling state acknowledge package or scheduling calculation start package, it finds data communication path to sink node. If the path to sink node exists, the sensor node turns into work state. Then it schedules sleep sensor nodes into work state in the path, calculates the state of neighbor sleep sensor nodes, and sends scheduling state acknowledge package and scheduling calculation start package to related sensor nodes. If the data communication path to sink node does not exist, the sensor node turns into sleep state.

Situation 4: If a sensor node receives the information package from other sensor nodes, it updates information table of neighbor sensor nodes.

Situation 5: If a sensor node receives energy invalid information package from neighbor sensor node, it uses repair method of coverage blind area after delaying a period of time.

Situation 6: If a sensor node is in work state, it senses data and uses distributed Bellman_Ford algorithm to send and route data. If a sensor node will exhaust energy, it sends energy invalid information package to neighbor sensor nodes.

Figure 6.

Work flow chart of sensor node in SNSA.

Algorithm simulation

Simulation parameters selection

In the simulation, MATLAB software is used and only wireless communication energy consumption of data perception in WSNs is considered. Other energy consumption such as energy consumption of information package transmission and energy consumption of data calculation is not considered. According to above algorithm analysis, perception radii of sensor nodes are generated randomly and uniformly within an interval [50 m, 150 m]. Position distribution of sensor nodes in the monitoring area is also generated randomly and uniformly. The following parameters are selected for simulation and relevant performance parameters are obtained. Length and width of monitoring area are both 1000 m. Maximum communication radius of sensor nodes is 200 m. Data sensing rate of sensor node is 1 kbit/min. Initial energy $E_{inital}$ is 1000 J. The size of grids is 20 m × 20 m. The energy consumption model of all nodes is the following model which is widely adopted in academia

E_{f} = g_{ij} E_{elec} + g_{ij} ε_{fs} d_{ij}^{2}

(17)

E_{j} = g_{ij} E_{elec}

(18)

where $E_{f}$ represents data transmission energy consumption of node, $E_{j}$ represents data receiving energy consumption of node, $g_{ij}$ represents data transmission amount from node i to neighbor node j, E_elec represents energy consumption parameter of data processing, and ε_fs represents energy consumption parameter of data transmission.

Network lifetime of x% regional coverage is defined as the effective working time of WSNs for keeping the regional coverage rate over x% when the network is in operation. Data collection period (DCP) is defined as the time period in which current sensor nodes do not change their states and sends their data to sink node. Then in the simulation, DCP is 1000 min and network lifetime of x% regional coverage is the number of DCP for keeping the regional coverage rate over x%. Influence of weight factors (w₁, w₂ and w₃) to network lifetime is studies. In the simulation, w₁ separately selects 0, 0.1,…,1. w₂ separately selects 0, 0.1,…, 1−w₁. $w_{3} = 1 - w_{1} - w_{2}$ . The number of sensor nodes is 200. Then, network lifetimes of 100% regional coverage are calculated. As shown in Figure 7, when $w_{1}$ and $w_{2}$ are small, the number of DCP when regional coverage rate is 100% is relatively more. When $w_{1}$ , $w_{2}$ , and $w_{3}$ are similar, the number of DCP is larger. Therefore, $w_{1} = 0.3$ , $w_{2} = 0.3$ , and $w_{3} = 0.4$ are selected in the simulation of SNSA.

Figure 7.

Influence of weight factors to network lifetime of 100% regional coverage.

Simulation result and analysis

In order to verify the effectiveness of SNSA, 200 sensor nodes and the simulation parameters are selected to calculate regional coverage rate and number of living sensor nodes of DGREEDY (disturbed greedy algorithm),⁶ TTS,⁷ MCC,¹⁴ and SNSA in each DCP. DGREEDY is distributed application of GREEDY in Lim and Bleakley.⁶ In DGREEDY, each sensor node calculates delay time according to regional coverage increment and wakes up to determine whether turning into work state after the delay time. TTS in Tezcan and Wang⁷ and MCC in Khedr and Osamy¹⁴ do not consider the repair of coverage blind area. For convenient comparison, TTS and MCC are calculated periodically in the simulation, and the state of sensor nodes are also updated periodically to repair the coverage blind area.

As shown in Figure 8, when number of DCP increases, regional coverage rates of the four algorithms decrease. However, the curve of regional coverage rate in SNSA decreases less. Namely in the same regional coverage rate, number of DCP in SNSA is more than number of DCP in DGREEDY, TTS, and MCC. The reason is that SNSA considers many factors to schedule sensor nodes, such as regional coverage increment, arc coverage increment, and residual energy. It establishes and solves the multi-objective scheduling model. Then SNSA determines the states of sensor nodes and improves network lifetime. DGREEDY and MCC do not consider the influence of residual energy on the scheduling of sensor nodes. DGREEDY and TTS do not consider the heterogeneous sensor nodes. Therefore, network lifetime of DGREEDY, TTS, and MCC is less than network lifetime of SNSA.

Figure 8.

Comparison of regional coverage rate.

As shown in Figure 9, when number of DCP increases, some sensor nodes die due to energy exhaustion or damage. Therefore, the number of living sensor nodes in each algorithm decreases. In a short time, the number of living sensor nodes in TTS is more than other three algorithms. But the number of living sensor nodes in SNSA is more than DGREEDY, TTS, and MCC during the most time. The reason is that SNSA considers many factors such as regional coverage rate and residual energy, and schedules appropriate number of sensor nodes to work. It can let sensor nodes with low energy turn into sleep state. Therefore, average node energy consumption is less.

Figure 9.

Comparison of number of living sensor nodes.

Finally, number 160, 180, 200, 220, 240, 260, 280, 300 of sensor nodes is respectively selected. 10 uniform distribution topologies of sensor nodes are generated randomly. Then network lifetime and average node energy consumption of 100% and 90% regional coverage in DGREEDY, TTS, MCC, and SNSA are calculated. The average values in each algorithm are calculated as simulation results.

As shown in Figures 10 and 11, network lifetime of 90% regional coverage is longer than network lifetime of 100% regional coverage. When number of sensor nodes increases, network lifetime of all four algorithms increases. But when regional coverage rate is either 100% or over 90%, the network lifetime of SNSA is longer than network lifetime of DGREEDY, TTS, and MCC. The reason is that when number of sensor nodes increases, more sensor nodes can be selected to work in the monitoring area, and the time for keeping the same regional coverage rate increases. Simultaneously, TTS considers residual energy of sensor nodes. Therefore, its network lifetime is basically longer than MCC and DGREEDY. The network lifetime of MCC and DGREEDY goes up and down. SNSA considers heterogeneous sensor nodes and uses better scheduling scheme of sensor nodes. Its network lifetime is longest.

Figure 10.

Comparison of network lifetime of 100% regional coverage.

Figure 11.

Comparison of network lifetime of 90% regional coverage.

As shown in Figures 12 and 13, DGREEDY schedules sensor nodes with maximum regional coverage increment to work. In DGREEDY, the number of sensor nodes in work state is fewer and the data transmission amount is less. Therefore, its residual energy of sensor nodes is more, and energy consumption of sensor nodes in DGREEDY is relatively less. When SNSA schedules sensor nodes, it considers residual energy and coverage blind area and reduces average residual energy. Therefore, when regional coverage is either 100% or over 90%, the average node energy consumption of DGREEDY and SNSA is less than average node energy consumption of TTS and MCC. But there is not much difference of average node energy consumption between DGREEDY and SNSA, and the curses of average node energy consumption in DGREEDY and SNSA go up and down.

Figure 12.

Comparison of average node energy consumption of 100% regional coverage.

Figure 13.

Comparison of average node energy consumption of 90% regional coverage.

Conclusion

SNSA for heterogeneous WSNs is proposed. First, algorithm assumption and basic principle are given. Second, regional coverage increment, arc coverage increment, and residual energy are analyzed. Three single optimization models are established and multi-objective scheduling model is established. Heuristic method is proposed to solve the multi-objective scheduling model and obtain scheduling scheme of sensor nodes. Distributed Bellman_Ford algorithm is used to route and send data. Sleep sensor nodes are waken up to repair the coverage blind area. Third, realization steps of SNSA are given. Finally, simulation parameters are given. Influence of weight factors to network lifetime is analyzed, and the performances of DGREEDY, TTS, MCC, and SNSA are compared.

In conclusion, comparing with DGREEDY, TTS, and MCC, SNSA improves network lifetime and number of living sensor nodes and keeps average node energy consumption at a low level. However, SNSA only considers the scheduling of static sensor nodes. When some key sensor nodes exhaust energy, energy hole problem appears and causes network division. Some sensor nodes fail to send data to sink node. Therefore, our objective of the next stage is to consider mobile sensor nodes in heterogeneous WSNs and study optimization scheduling algorithm of mobile heterogeneous sensor nodes to prolong the network lifetime.

Footnotes

Handling Editor: Wei Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Public Welfare Technology Application and Research Projects of Zhejiang Province of China under Grant No. LGG19F010011 and No. LGF18F010005, the National Natural Science Foundation of China under Grant No. 61501403, the Major Science and Technology Special Project of Zhejiang Science and Technology Department of China under Grant No.2015C01033, and the Natural Science Foundation of Zhejiang Province of China under Grant No. LQ18F030005.

ORCID iD

Yourong Chen

References

Castillo

Tobajas

Esper-Chain

et al . Hardware platform for wide-area vehicular sensor networks with mobile nodes. Veh Commun 2016; 3(1): 21–30.

Antolin

Medrano

Calvo

Reliable lifespan evaluation of a remote environment monitoring system based on wireless sensor networks and global system for mobile communications. J Sens 2016; 2016: 4248230.

Wang

Xie

Agrawal

DP.

Coverage and lifetime optimization of wireless sensor networks with Gaussian distribution. IEEE T Mobile Comput 2008; 7(12): 1444–1458.

Krause

Rajagopal

Gupta

et al . Simultaneous optimization of sensor placements and balanced schedules. IEEE T Automat Contr 2011; 56(10): 2390–2405.

Singh

Rossi

A genetic algorithm based exact approach for lifetime maximization of directional sensor networks. Ad Hoc Netw 2013; 11(3): 1006–1021.

Lim

Bleakley

CJ.

Trading sensing coverage for an extended network lifetime. Telecommun Syst 2013; 52(4): 2667–2675.

Tezcan

Wang

TTS: a two tiered scheduling mechanism for energy conservation in wireless sensor networks. Int J Sens Netw 2006; 1(3–4): 213–228.

Chen

et al . Leveraging prediction to improve the coverage of wireless sensor networks. IEEE T Parallel Distrib Syst 2012; 23(4): 701–712.

Idrees

Deschinkel

Salomon

et al . Distributed lifetime coverage optimization protocol in wireless sensor networks. J Supercomput 2015; 71(12): 4578–4593.

10.

A weighted multiple coverage node scheduling scheme based on differential evolution algorithm for heterogeneous sensor networks. Chin J Sens Actuat 2012; 25(6): 826–830.

11.

Sun

Guo

et al . Coverage optimization algorithm for heterogeneous WSNs. J Electr Inf Technol 2014; 36(3): 696–702.

12.

Lin

Zhang

Chung

et al . An ant colony optimization approach for maximizing the lifetime of heterogeneous wireless sensor networks. IEEE T Syst Man Cyb 2012; 42(3): 408–420.

13.

Sun

Wei

Guo

et al . Node scheduling algorithm for heterogeneous wireless sensor networks. Acta Electron Sinica 2014; 42(10): 1907–1912.

14.

Khedr

Osamy

Minimum connected cover of a query region in heterogeneous wireless sensor networks. Inf Sci 2013; 223(2): 153–163.

15.

Chen

Wang

Cheng

et al . Lifetime optimized routing algorithm based on shortest path tree. Chin J Sens Actuat 2012; 25(3): 406–412.