Abstract
Scheduling the redundant nodes to sleep is an effective technology to sufficiently prolong the life circle of wireless sensor network on the premise of meeting the coverage quality. According to position distribution of the neighboring nodes, a node scheduling algorithm of wireless sensor network is proposed on the basis of the necessary condition that a node becomes a redundant one and whether the complementary neighboring nodes meet the circle cover. The new algorithm reduces the computational complexity. Simulation results show that the new algorithm is effective to schedule the redundant node to sleep for energy-saving. It predicates nearly 26 % nodes to sleep when the perception radius is 10 meters and coverage rate is unchanged. It identifies more than 50 % nodes to sleep with 15 meters radius.
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
Wireless sensor networks [1] is a monitoring networks composed by a large number of micro computer equipment which is randomly deployed to task area through wireless self-composition. Wireless sensor networks can be applied in military invasion, environmental monitoring, industrial data collection, health monitoring, smart home and precision agriculture. The coverage control [2] is often described as a standard in monitoring the QoS (quality of service) of the wireless sensor network, which is the basis of other networking technologies such as routing protocols and positioning design. In special applications or the inaccessible areas, dense (density up to 20 node/m3) and large-scale deployment is commonly applied in the deployment of the sensor network nodes to ensure the performance of the network coverage [3], but which leads to data redundancy, conflict between the packets and reduce network throughput. On the other hand, the wireless sensor node is provided by the battery, which makes it difficult to replace or recharge the energy. The energy consumption of the node determines the lifetime of the wireless sensor network, thus, the design of the sensor network coverage control must provide the maximum network life cycle under the premise of ensuring the quality of coverage.
In the application of the high-density and randomly-deployed wireless sensor network, redundant nodes whose coverage area is completely covered by the neighboring nodes are often turned off to reduce the node density of the local area, while extending the life cycle of the network through node scheduling. VSGCA [4] identifies the redundant node by virtual Meshing, that is, the sense coverage of each node is divided into a virtual grid. It is identified as a redundant node when its grid is covered by the neighboring node. TIAN [5] proposed the Off-duty eligibility rule to determine the redundant nodes, which calculates the covering relations between nodes according to the location of the nodes or the angle of the signal. Based on probability analysis, NDNS [6] (non-uniform distribution node scheduling) system identifies the redundancy of the node according to the distance between nodes and their neighboring ones. Based on numbers of the neighboring nodes, Gao [7] analyzes the redundant node coverage probability model, points out when there are 11 neighboring nodes, the probability of the node becoming a redundant node is over 90 %. AEKYU [8] uses sponsored sector and the effective angle to determine whether a node is redundant ones or not. HUANG [9] considers the coverage circumference of each sensor node, then determines whether a given circumference of the sensor node is completely covered by the neighbor nodes. If the circumference of a node is completely covered, the node becomes a redundant node. Based on the circumference covering, LIU X [10] proposes that in the premise of ensuring the coverage of network, the lifetime of the network can be improved by putting the redundant nodes in dormancy. Based on greedy node scheduling algorithm, ERGS [11] uses the position relationship between the nodes and residual energy to determine whether the node is dormant. Reference [12] proposes an algorithm that ordinary node competes to determine whether it is dormant, and which is necessarily managed by high capacity nodes. EBNDNS [13] determines whether a node is dormant by depending on the distance between the sensor nodes, the way is simple, but the conclusion is insufficient, causing coverage gap. ECHS and EDHS [14] designed a heuristic algorithm based on energy-aware to complete node scheduling. Based on residual energy and signal strength, EECDS [15] selects the backbone nodes to constitute coverage sets to save energy, those algorithms [4–7] depend on accurate position information of neighboring nodes, in which calculation are more complicated. The judgments of circumference coverage [8–10] are insufficient. When taking the neighbor nodes within a radius of perception only in consideration, the criteria are stricter, and the redundant nodes are usually judge as backbone ones, causing inaccurate judgments. When considering neighbor nodes within perception radius of two times, the criteria are less strict, and the backbone nodes are often regarded as the redundant ones, causing false judgments. Algorithms in [11–15] are based on heuristic designing ideas, proposing that the residual energy of the sensor network nodes can be used to form the working set of nodes, but the calculation is complicated. According to the position relationship between neighboring nodes, this paper proposes the necessary conditions that node becomes redundant ones, and combining the judgments based on complement of partly radius angle, which reduces the computational complexity and further solves the inaccurate and false judgment problems caused by the inadequate judgment conditions of the circumference covering algorithm.
2 System Model and Problem Description
2.1 Network Model
Generally, wireless sensor networks can be abstracted as an undirected graph\(G = (V,E) \), \( {\text{V}} = \{ {\text{s}}_{ 1}, {\text{s}}_{ 2}, \ldots,{\text{s}}_{{{\text{i}},}} \ldots, {\text{s}}_{\text{n}} \} \) is the set of nodes in wireless sensor networks. \( {\text{E}} = \{ {\text{e}}_{ 1}, {\text{e}}_{ 2}, \ldots,{\text{e}}_{{{\text{j}},}} \ldots {\text{e}}_{\text{m}} \} \) is the set of edges that can communicate with each other between the nodes, \( {\text{e}}_{\text{j}} = \left( {{\text{u,}}\,{\text{v}}} \right) \) represents the link by which node u and v can transmit data directly. The sensing radius of sensor node is r, communication radius is R, when the network covers the task area, it requires the mutual communication between nodes, and there is no isolated node. All nodes have positioning capability and obstacles in the monitoring area are not considered in the research.
2.2 Coverage Model
Definition 1:
The Euclidean Distance of sensor node S(xs,ys) and P(xp,yp) is shown as Eq. 1.
Definition 2:
If any point within a certain area is not covered by any sensor node, then this area is called blind zone.
Definition 3:
The coordinate of sensor node S in two-dimensional plane R2 is (x,y), then the coverage area of node S is a circular region called as the coverage circle with its center of point(x,y) and its sensor radius is r, which shows as Eq. 2.
Definition 4:
The coverage model is described as Eq. 3.
3 Maintaining Coverage Node Scheduling Algorithm
3.1 Related Concepts
Definition 5:
Neighbor Node. The neighboring node of the any node si refers to the node Sj whose distance from si is less than the communication radius R. It is described as Eq. 4.
Definition 6:
Redundant Node. When the coverage circle of the node Si is covered by the coverage circle of the neighbor node set N(Si), then the node Si is a redundant node. It is described as Eq. 5.
Definition 7:
Inter-neighbor Node: The inter-neighbor node of the node Si refers to the node set constituted of the node Sj whose distance from Si is less than the sensor radius r. It is described as Eq. 6.
Definition 8:
Outer-neighbor Node: The outer-neighbor node of the nodes Si refers to node set constituted of the node Sj whose distance from Si is larger than r, smaller than R. It is described as Eq. 7.
Definition 9:
Coverage Sponsor Region: The coverage sponsor region of Sj to Si refers to the part that the covering circle of node Si is covered by the covering circle of Sj. It is shown in Fig. 1. The sponsor region is described as Eq. 8.
Theorem 1:
The necessary condition that the node Si becomes redundant node is that there must be at least one node is distributed in the coverage circle of Si.
Proving:
(contradiction proving), Suppose the node Si is a redundant node, and there is no any inter-neighboring node Sj which located in its covering circle, that is all the neighboring nodes are outer-neighbor nodes, which meets to the condition:\(r < dsit(s_{j}, s_{i} ) \le R \). Dot Si meets the condition: \( {\text{s}}_{\text{i}} \notin {\text{ca(s}}_{\text{j}} ) \), that is point Si is not covered by its any neighbor node Sj. If no neighboring node Sj covers point Si, then the set of the neighbor nodes doesn’t cover circle point Si, it is described as Eq. 9.
It doesn’t meet to the criteria in Eq. 5. Therefore the assumption is false, and the theorem is proved to be true.
3.2 The Basic Steps of Node Scheduling Algorithm
The operation of new algorithm is broken up into rounds, where each round traverses every sensor node ascended by the node ID numbers. When traversing to the sensor node Si, It judges itself whether in working state or sleep by four steps of inter-neighbor node discovery, neighbor node discovery, redundant node determination and node scheduling. It is shown in Fig. 2.
The step of inter-neighbor node discovery is to detect if there is inter-neighbor node in the covering circle of node Si. Neighbor node discovery is to collect the information of the neighbor nodes in the premise of detecting inter-neighbor nodes. Redundant node determination is to judge if node Si applies to dormant conditions. Node scheduling is to complete state transition.
3.2.1 Inter-neighbor Node Discovery
The processes of inter-neighbor node discovery are: (1) node Si broadcasts query message within scope of circle with radius r. (2) The node which receives message makes response that includes the node number ID and their positions. (3) Node Si counts the response message, and calculates the sponsor circle angle \( \theta_{{s_{j} \to s_{i} }} (s_{j} ) \) of the inter-neighbor node according to formula 8. It is concluded that \( \theta_{{s_{j} \to s_{i} }} (s_{j} ) \ge {\raise0.7ex\hbox{${2\pi }$} \!\mathord{\left/ {\vphantom {{2\pi } 3}}\right.\kern-0pt} \!\lower0.7ex\hbox{$3$}} \). If node Si gets no response message, it means node Si has no inter-neighbor node. According to theorem 1, node Si doesn’t apply to the condition of the redundant node, then node Si will quit the process of the dormant scheduling immediately. It plays a key role in reducing the complexity of the algorithm.
3.2.2 Neighbor Node Discovery
If node Si detects the inter-neighboring node Sj, it will get in the process of detecting the neighbor node discovery, the processes are: (1) node Si broadcasts query message within scope of circle with radius R. (2) Node Sk that received message makes response that include ID number of the node and its position. (3) According to the received position information, node Si makes sure whether Sk located in the sector area of the sponsored circle angles of \( \theta_{{s_{j} \to s_{i} }} (s_{j} ) \), if it locates in this area, then node Sk is neglected, or Sk will be recorded in the complementary set of Sector(S j). It is described as Eq. 10.
3.2.3 Redundant Node Judgment
It traverses all the nodes of the set of \( \overline{{{\text{Sector}}\left( {{\text{s}}_{\text{j}} } \right)}} \), and marks the circle angles with Si as A(L) and A(R). It is ascended as the A(L) order. If there is no intermission from the minimum of A(L) to the maximum of A(R), meanwhile, applies to conditions of the following Eq. 11, then node Si is a redundant node.
3.2.4 Sleep Scheduling of Node
It is divided the state of nodes into three kinds: active state, sleep state and wait state. When round k begins, all the nodes are in the active state, and distributed the ID number randomly. The steps of the sleep scheduling of node are:
Step 1: If the traversed present nodes leave to solve problems, It is still in active state, and if there is nothing to do, it get into step 2.
Step 2: running stated in 3.2.1 to detect an inter-neighboring node, if there is no such one, node Si keep active state and quit from the process of sleep node scheduling to traverse the next node. Otherwise, node Si calculates \( \theta_{{s_{j} \to s_{i} }} (s_{j} ) \) and \( \sec ter(\theta_{{s_{j} \to s_{i} }} ) \), then get into step 3.
Step 3: Detecting neighboring nodes with means stated in 3.2.2 to obtain set of the \( \overline{{{\text{Sector}}\left( {{\text{s}}_{\text{j}} } \right)}} \). If it is equivalent to \( \phi \), then node Si keeps in active state and traverse the next node, Otherwise, it get into step 4.
Step 4: Judging the redundant node according to state in 3.2.3, if it is a redundant node, node Si transfer into sleep state. Otherwise, node Si keeps active state.
Step 5: After the sleep stage over, nodes Si turns into wait state to get in the next dormant scheduling.
4 Performance Evaluation
4.1 Performance Analysis
It supposes n sensor nodes distributed in the task area A, then the probability that there is no inter-neighboring node in the covering circle of node Si is shown as Eq. 12.
If there is no inter-neighboring node detected when the algorithm traverses, node Si quits the present redundant node scheduling process. Therefore, the algorithm quits the running of redundant node scheduling as the probability \( p_{r} (s_{i} ) \), In the comparison, the circle coverage algorithm performs all the steps of the process of redundant node scheduling. When the algorithm detects that node Si has an inter-neighboring node, it is necessary to judge the coverage within two times of the sensor radius r, and the probability that node Si has k neighboring node is shown in Eq. 13.
The average neighboring nodes number is calculated as Eq. 14.
What necessary is only to calculate the coverage that neighboring nodes in area \( \overline{{{\text{Sector}}\left( {{\text{s}}_{\text{j}} } \right)}} \) covers the circle of node Si. The average neighboring nodes number is shown as the Eq. 15.
Z is the average executing frequency of the algorithm to judge the redundant nodes of step 4. In a contrast, the circle coverage algorithm is \( (n - 1)\frac{{\pi (2r)^{2} }}{A} \). Therefore, compared to circle coverage algorithm, the new algorithm reduces one third performance frequency in Step 4. Performance in Step 4 itself is very complicated, since it is necessary for every node to count two angles that overlaps the circle of node Si, and it must ascends order and judges intermission.
4.2 Simulation Experiment
4.2.1 Coverage Rate
Coverage rate refers to the ratio of the covering area of the working nodes and the task area A. In MATLAB R2012a, with task area A = 100 m*100 m, sensor nodes are deployed with different numbers and different radius of perception as 5 m, 10 m, 15 m. Coverage rate that before and after the new algorithm running is shown as Fig. 3.
4.2.2 The Number of Sleep Nodes
We deploy different number of sensor nodes and set the sensor radius r as 5 m, 10 m and 15 m, then the number of sleep nodes is shown as Fig. 4. The result combined with Figs. 3 and 4 shows that the coverage rate increases with more nodes are deployed regardless of the algorithm to perform or not. After the running of the algorithm, when the sensor radius is 5, the sleep nodes is little, and the coverage rate almost doesn’t change, and when the sensor radius be comes 10, the sleep nodes are about 25 %, the coverage rate decreases about 0.1 %, and when the sensor radius comes to 15, the sleep nodes are about 50 %, the coverage rate decreases about 0.1 %. These data show that on the premise of full coverage, the algorithm proposed in the paper can effectively schedule nodes to the sleep state as well as reduce energy consumption and prolong lifetime of the network.
5 Conclusion
Coverage control is the basic problem of the sensor network. The important requirement of designing coverage control is to reduce energy consumption to prolong lifetime of the network. We analyze the necessary condition that node becomes redundant nodes is the existence of at least one inter-neighbor node. The neighboring node covers at least 1/3 area for this node, and the rest areas are determined according to the circle covering. It greatly reduces calculating complexity, and reduces energy consumption by putting the redundant nodes in sleep state. On the premise of keeping coverage, the performance analysis and simulation show that the proposed algorithm can reduce the calculating complexity of judging the redundant nodes, and it also can judge the redundant nodes accurately, which puts those nodes into sleep state to reduce energy consumption and prolong lifetime of the network.
References
Ren, F.Y., Huang, H.N., Lin, C.: Wireless sensor network. J. Softw. 14(7), 1282–1291 (2003)
Tao, D., Sun, Y., Cheng, H.J.: Worst_case coverage detection and repair algorithm for video sensor networks. Acta Electronica Sin. 37(10), 2284–2290 (2009). (In Chinese)
Shih, E., Cho, S., Ickes, N.: Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In: Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, pp. 272–287. ACM Press, Rome (2001)
Liu, Y., Suo, L., Sun, D., Wanga, A.: Virtual square grid-based coverage algorithm of redundant node for wireless sensor network. J. Netw. Comput. Appl. 36(5), 811–817 (2013)
Tian, D., Georganas, N.: A coverage-preserving node scheduling scheme for large wireless sensor networks. In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, pp. 32–41. ACM Press, Atlanta (2002)
Fan, G.J., Sun, L.J., Wang, H.P.: Non-uniform distribution node scheme in wireless sensor networks. J. Commun. 32(1), 10–17 (2011). (In Chinese)
Gao, Y., Wu, K., Li, F.: Analysis on the redundancy of wireless sensor networks. In: Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, pp. 108–114. ACM Press, San Diego (2003)
Aekyu, C., Gilsoo, K., Taekyoung, K., et al.: A distributed node scheduling protocol considering sensing coverage in wireless sensor networks. In: IEEE 66th Vehicular Technology Conference, pp. 352–356. IEEE Computer Society, Baltimore (2007)
Huang, C.F., Tseng, Y.C.: The Coverage Problem in a Wireless Sensor Network, pp. 115–121. ACM Press, New York (2003)
Liu, X., Zhang, J., Wang, X.: SCCP: self-adjusting of circle coverage protocol in wireless sensor network. Appl. Res. Comput. 27(4), 1407–1409 (2010). (In Chinese)
Singaram, M., Finney, S., Sathish, K.N., Chandraprasad, V.: Energy efficient self-scheduling algorithm for wireless sensor networks. Int. J. Sci. Technol. Res. 3(1), 44–78 (2014)
Fatemeh, M.K., Ahmad, K.: Coverage problem in heterogeneous wireless sensor networks. Eur. Sci. J. 27(9), 81–96 (2013)
Ma, S.S., Qian, J.S.: Energy balanced non-uniform distribution node scheduling algorithm for wireless sensor networks. Appl. Math. Inf. Sci. 8(4), 1997–2003 (2014)
Hong, J.C., Guo, R.L.: Service-oriented node scheduling schemes with energy efficiency in wireless sensor networks. Distrib. Sens. Netw. 12, 1155–1165 (2014)
Sajjad, R., Hassaan, K.Q., Syed, A.K.: An energy efficient topology control algorithm for connected area coverage in wireless sensor networks. J. Netw. Comput. Appl. 35(4), 597–605 (2012)
Acknowledgement
This research was supported by Natural Science Foundation of Yunnan (2011FZ176), China. The authors thank the anonymous reviewers whose comments have significantly improved the quality of this article.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Qian, K., Shen, S., Dai, Z., Duan, R. (2015). Maintaining Coverage Node Scheduling Algorithm in Wireless Sensor Network. In: Sun, L., Ma, H., Fang, D., Niu, J., Wang, W. (eds) Advances in Wireless Sensor Networks. CWSN 2014. Communications in Computer and Information Science, vol 501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46981-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-662-46981-1_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46980-4
Online ISBN: 978-3-662-46981-1
eBook Packages: Computer ScienceComputer Science (R0)