Keywords

1 Introduction

With the rapid development of wireless communications and sensor technology, Wireless Sensor Network (WSN), the core technology of the internet of things, has become a hot research topic [1–5]. A typical WSN which consists of a large number of sensor nodes is able to collect and send information within a monitoring area [6]. Over the last decade, WSN has been widely studied and applied in many fields, such as the environmental monitoring [7], the battlefield, the medical diagnosis, the habitat monitoring of animals [8–11], etc. A large-scale WSN is normally deployed by a group of high-density sensor nodes. A sensor node’s energy is limited due to the usage of battery and the replacement of battery for distributed sensor nodes is impractical. A key to the success of a WSN application is for the purpose of minimizing energy consumption of the nodes energy consumption and prolong the life time of the network [12] as long as possible, which has attracted much research attention.

In the literature, the researchers have proposed a lot of solutions and algorithms for the sensor nodes scheduling problem in WSN. By using accurate location information of nodes to judge whether a node covers other redundant nodes, we can select some redundant nodes to be dormant, so as to prolong the network’s life time. In [13], the dismissal unqualified rules (i.e. off-duty eligibility ride) are proposed to compute the angle and the coverage redundancies of nodes according to the location and communication information of nodes. Zhang [14] discussed the network coverage and the topology structure, and proposed an Optimal Geographical Density Control (OGDC) algorithm. OGDC calculates the redundancies of coverage according to nodes’ position information. However, through the GPS [15–18] or a compass to get the location information consumes a majority of node energy and also makes the network system become more complex. At present, the triangular lattice node sequence which optimizes the coverage performance and deployment of nodes has been proposed in the literature [16]. However, the demand of the precise location of the node consumes a lot of power which reduces the lifetime of a WSN [14–18]. Therefore, aiming to extend the life cycle of a WSN, the node scheduling algorithms without requiring the geographic information become the research focus. In [19], a light weight deployment-aware scheduling (LDAS) method was proposed, which achieves the probability of coverage by acquiring the number of neighbor nodes within two-hops (i.e. twice the sensing range of a node). LDAS algorithm ignores the disturbance among nodes due to the high node density, which leads to the appearance of a lot of redundant nodes. Based on the high probability to active status of boundary nodes, the relationship between the coverage area and the tolerance coverage area has been analyzed in [20], and a Tolerable Coverage Area based Node Scheduling (TCA) algorithm is then proposed. Although TCA solves the fast dying speed of boundary nodes, however, it does not consider the interference among a large number of nodes within the monitoring area, thus the coverage redundant problem still exists.

Based on [19, 20], there are two improvements in [21]: (1) introducing the parameter of relative residual energy E remain to optimize the cover tolerable decision strategy; (2) improving the distribution of nodes’ status by using the “pre-active” and “rollback” status, and then an ECONS is proposed. Due to the randomly selection of candidate nodes, it could not guarantee to obtain a satisfied quality of coverage each time.

For these problems in the literature, a new low redundancy and high cover (LRHC) node scheduling algorithm has been designed based on the cellular network model in this paper. The LRHC algorithm searches suitable active nodes according to characteristics of the cellular network. After the node scheduling, when the node dead occurs, a sleeping node compensation will immediately start. This compensation solves both the uneven selection of nodes and the unstable threshold settings, which provides continuous coverage and ensures the coverage quality.

The rest paper is organized as follows. In Sect. 2, we describe the relate work. Section 3 presents the proposed LRHC node scheduling algorithm. We evaluate our algorithm by experiments and summarize the obtained results in Sect. 4. Finally Sect. 5 concludes our work in this paper.

2 The Related Work

In [19–21], the node is scheduled after the end of the previous round of scheduling, which may make the energy of active nodes in this round is insufficient to support till the end of this round, the coverage holes thus occur.

In [19, 21], the relative residual energy value is to decline constantly with the consuming of nodes energy, then the probability of node entering the active state becomes smaller. Since E remain is the ratio of the residual energy, those nodes may never enter the active state when some residual energy becomes very small and little change in the threshold value. So when E remain  × B i /E r within a region is less than a given threshold, the region will cause a coverage hole.

In [19–21], because of a large number of nodes deployed within the monitoring area, the judge interference among these nodes may result in some nodes to sleep at the same time, which reduces the coverage quality of the network.

In [19–21], the probability P of node i to sleep, is calculated as p i  = 1-n0.609 n−1-(n/6-0.109) n−1 [19], in which n represents the quantity of neighboring nodes in the active status. For instance, if n is 9, p i  = 0.8297, it means that if node i wants to sleep, more neighboring nodes are needed to be active. And when many these active nodes focus on one place, it causes not only the coverage hole, but also the redundancy. Based on the above observations, we propose a low redundancy and high coverage node scheduling algorithm by using idea of the cellular network. Since we can theoretically prove that the cellular network model can provide a complete coverage of the target area with minimized number of active sensor nodes in a WSN network.

3 The Low Redundancy and High Coverage Node Scheduling Algorithm

As shown in Fig. 1, each active node has six active neighboring nodes that can enter a dormant state. Without considering the coverage redundancy between nodes, the detection range of each node is the area of the hexagon with R as its side length, which can be calculated as \( 1.5\sqrt 3 R^{2} \). Theoretically, for the area S, the number of nodes required is \( 2S/3\sqrt 3 R^{2} \) in the cellular network model.

Fig. 1.
figure 1

The update of sensors’ status based on the cellular network model.

Full size image

3.1 Initialize the Neighborhood Location Information

At this stage, the node broadcasts its finding information to neighboring nodes within the scope. For any node i, if its neighboring node set is defined as \( N(i) = \) \( \{ j \in \eta |d(i,j) \le \sqrt 3 R,i \in \eta ,j \ne i\} \) , where \( d(i,j) \) represents the distances between node i and j, R is the sensing radius of nodes. Each node has five states: Active: the working mode; Sleep: the sleeping mode; Pre-active: the transient state before the active mode; Pre-sleep: the transient state before the sleeping mode; Dead: the node’s energy is used up.

3.2 The Update of Status of Sensors Based on the Cellular Network

Based on the cellular network model described above, the new LRHC algorithm divides the monitoring area into multiple cellular. However, the randomly distributed nodes which do not have the location information, may not satisfy the cellular network coverage. To solve the above problem, we use the following steps.

3.2.1 The Random Selection of the Starting Nodes

Firstly, all sensor nodes are in sleep status. A stochastic node is selected as an active node to send messages to neighboring nodes. As can be seen in Fig. 1, ideally, after the division, each cellular within the monitoring area has the characteristics of the cellular network model.

3.2.2 Iterative Traversal

After an active node is selected, the relatively optimal neighboring node is selected as the active neighboring node. All the neighboring nodes update the status, location information until all nodes have updated their information.

3.3 The Checking and Repairment of the Coverage Holes

Theorem.

When the side length of the triangle is not greater than the radius of the sensing nodes multiplied by \( \sqrt 3 \), then, the three nodes of triangle vertex fully cover the area.

Proof. In Fig. 2, if the side length of the ∆ABC is \( \sqrt 3 R \) (R represents the sensing radius of a node), the area of the ∆ABC is fully covered by nodes A, B and C. If AB = AC = R, when the length of BC decreases (see the ∆ADC), it is easy to know DO < AO = R (O is the crossover point of three circles), then the circle with D as the center and R as the radius must cover node O. So the area of ∆ADC is fully covered with the triangle vertex of three nodes A, D and C. Similarly, if there are two or three sides are less than \( \sqrt 3 R \), the area of ∆ABC is fully covered with the triangle vertex of three nodes.

Fig. 2.
figure 2

An example of the triangle coverage.

Full size image

Lemma. When the side lengths of the triangle are less than \( \sqrt 3 R \), the nodes inside the area of triangle can be in the sleep status, and the distances between the sleep nodes and the vertices of triangle are less than \( \sqrt 3 R \). It means that when a node has three active neighboring nodes which are not overlapped, and the distances to the three vertex nodes are less than \( \sqrt 3 R \), then the node can go to sleep.

As shown in Fig. 2, When the radius of node sensing is R, the side length of the equilateral ∆COB is \( \sqrt 3 R \), then any node inside the ∆COB with the distances to three active vertex nodes are less than\( \sqrt 3 R \), such nodes inside the area of ∆COB do not need to wake up sleeping nodes to check and repair. If there is no node within a small area C, while there is node in the area O′ (the side \( DO^{\prime} > \sqrt 3 R \) of the ∆DOO′), then the area of ∆DOO′ must have some coverage holes, and need to wake up sleeping nodes to check and repair the coverage holes.

After steps 3.1 and 3.2, check the active nodes near the sleeping node. If in the range of the round area which uses the sleeping or pre-sleeping node as the center and \( \sqrt 3 R \) as the radius, there are less than three active neighboring nodes, then the sleeping or pre-sleeping node enters the pre-active state. For the node that is in the pre-active state, after a random delay time t_w, check the area of the pre-active node (using pre-active node as the circle center and \( \sqrt 3 R \) as the radius), if the active neighboring nodes are less than three, the node will be in the active status, otherwise it maintains the sleep status (Fig. 3).

3.4 The Node Scheduling

This section describes the procedure of scheduling. At beginning, assuming all nodes are in the sleep mode:

  1. 1.

    Randomly select a starting point in the monitoring area, based on the information of its neighbors to find the best suitable nodes (see ②)(satisfy the cellular network model distribution) and update the states of traversed nodes using the procedure described in Sect. 3.2., Start from the new active points, traverse all nodes and repeat the above procedure.

  2. 2.

    Active node sends the sleep information to its neighboring nodes that are in pre-sleeping state. If the number of the sleep information received by the pre-sleeping node is not less than 3, then the node enters the sleeping state (see ⑤) otherwise enters the pre-active mode (see ③).

  3. 3.

    Each pre-active node randomly selects a rollback time t_w, and sends the sleep request to its active or pre-active neighboring nodes. If the number of received reply message is greater than or equal to 3 (see Sect. 3.3), then it enters a pre-sleep state (see ④), otherwise enters an active state (see ①).

  4. 4.

    The active node sends the sleep information to its neighbors that are in pre-sleeping state. If the number of received sleep information of the current node is greater than or equal to 3, then the node enters the sleeping state directly (see ⑦), otherwise it enters an active mode (see ⑥).

Based on the characteristics of the cellular network described in Sect. 3.4, the above four steps reduce the mutual interference among nodes and optimize the network coverage quality (Fig. 4).

Fig. 3.
figure 3

The pseudo code of the detection of the pre-sleep node to its neighboring nodes

Full size image
Fig. 4.
figure 4

A node state transition diagram in LRHC

Full size image

4 The Experimental Results and Analysis

Assuming that the monitoring area is deployed with random sensor nodes, the monitoring scope of any node i satisfies: the round area whose radius is R and the center is r, denoted as \( S(R_{i} ) \). The neighboring nodes of any node i meets the following:\( N(i)\,\, = \,\,\left\{ {j\, \in \,\eta |d(i,j)\, \le \,\sqrt 3 R,i\, \in \,\eta ,j\, \ne \,i} \right\}\quad \circ \quad \quad \eta \) is the node set within the monitoring area. \( d(i,j) \) is the distance between node i and node j. Without using GPS, Beidou system or other positioning method to obtain the location information, the selection of active nodes depends on the communication between neighboring nodes.

We evaluate the performance of LRHC algorithm compared with two algorithms TCA and ECONS in the literature in this section.

We use Matlab as the simulation tool. We apply the energy model in [13], the energy consumption of the radio of communication, sleep and reception (idle) are 20:4:0.01. The life time is 550–650 s for the idle (pre-sleep and pre-active) node. In the area of \( 150^{2} {\text{m}}^{2} \), nodes are randomly deployed with the sensing range of 10 meters, and the communication range of a node is \( 10\sqrt 3 \) meters, the dormant time is 2 seconds. As defined in [20], there are two different states include the idle and sleep states, while when the node is dormant means that it is sleeping.

4.1 The Comparison of Network Life Time

In the first group of experiments, we deploy the same number of nodes N (200, 400, 500 and 1000, respectively) in the \( 150^{2} {\text{m}}^{2} \) area, the same sensing radius (10 m), and the same coverage quality requirement (95 %) are set in the experiments. The comparison of network life time after the scheduling of LRHC, compared with TCAI and ECONS are shown in Fig. 5. Figure 5(a) shows that the LRHC algorithm can obtain a longer life time than that of TCAI and ECONS. And its death time of the first dead node is later than the TCAI and ECONS. With the growing number of nodes deployed, the performance of LRHC becomes even better compared with other two algorithm s. After the node selection of step 3.1 and 3.2, LRHC can obtain a high quality of coverage (QOC). It demonstrates that using the cellular network model LRHC can achieve a higher coverage rate with few nodes to prolong the network life time.

From Fig. 6 we can see that, with different coverage quality requirements, the LRHC algorithm always has slower increase of death nodes than those of TCAI and ECONS in terms of the network life time.

4.2 The Comparison of the Number of Active Nodes

In this experiment section, different number of sensor nodes are deployed, i.e. 200, 400, 500 and 1000, in the region of \( 150^{2} {\text{m}}^{2} \). The sensing radius is 10 m, and the required coverage quality is 95 %. We compare the number of nodes that is needed by LRHC, TCAI and ECONS. Each algorithm was tested 20 times for each network size.

Fig. 5.
figure 5

The comparison of network life time (R = 10, QOC = 0.95).

Full size image
Fig. 6.
figure 6

The network’s survival situation when R = 10 and N = 500.

Full size image

Table 1 shows that the number of active nodes needed by LRHC is significantly less than that by ECONS and TCAI. The reason is that LRHC only needs to schedule a small amount of nodes to reach a higher level of coverage by using the cellular network model and the schedule strategies described in Sect. 3. It also shows that the growth of active nodes needed by LRHC is obviously less than that of ECONS and TCAI.

Table 1. The number of active nodes needed for three algorithms (QOC = 0.95)
Full size table

5 Conclusion

We proposed a low redundancy and high coverage node scheduling algorithm LRHC in this paper,. On the one hand, this algorithm brings in the cellular network model to select the active node which reduces the required active neighboring nodes so that the total energy consumption is saved and the network life time is thus prolonged. On the other hand, a new triangle coverage method has been proposed to improve the coverage quality. In addition, a pre-processing procedure is designed to wake up some neighbors in time before the death of an active node to avoid the coverage hole. The simulation experiments demonstrate that the proposed LRHC can obtain a high coverage rate with a relatively less nodes compared with other two algorithms in the literature. In our future work, we plan to further improve the selection method of active nodes.