Wireless Sensor Network
Vol. 4  No. 5 (2012) , Article ID: 18959 , 6 pages DOI:10.4236/wsn.2012.45018

Optimal Node Scheduling for Desired Percentage of Coverage in Wireless Sensor Networks

Hamid Khosravi

Institute for Informatics and Automation Problems, National Academy of Science of Armenia, Yerevan, Republic of Armenia

Email: khosravi@ipia.sci.am

Received March 15, 2012; revised April 20, 2012; accepted May 2, 2012

Keywords: Wireless Sensor Networks; Connected Sensor Cover; Connectivity; Coverage; Energy Conservation

ABSTRACT

Recent developments in wireless communication and embedded computing technologies have led to the advent of wireless sensor network technology. Hundreds of thousands of these micro sensors can be deployed in many areas including health, environment and battlefield in order to monitor the domain with desired level of accuracy. When wireless sensors are deployed in an area, the lifetime of the network should last as long as possible according to the original amount of energy. Therefore, reducing energy consumption in WSNs is of primary concern. We have proposed a node scheduling solution that solves the coverage and connectivity problem in sensor networks in an integrated manner. In this way we will divide network life time to finite number of rounds and in each round we will generate a coverage bitmap of sensors of the domain and based on this bitmap it will decided which sensors remain active or go to sleep. We will check the connection of the sensor network by using Laplacian of adjancy graph of active nodes in each round. Also the network will be capable of producing desired percentage of coverage by using coverage bitmap. We will define the connected coverage problem as an optimization problem and we will seek a solution for the problem by using Genetic Algorithm optimization method.

1. Introduction

Recent advancements in wireless technology have paved the way for wireless sensor network technology. Monitoring accuracy, which was hardly achievable by other technology, is now more easily available by wireless sensor networks, even monitoring of some hazardous area, which was, previously impossible or hard to achieve are now possible [1-3].

In many environment when network nodes are deployed it is hard to get physical access to them for maintenance or adjusting their physical location, therefore, usually we should deploy more sensors than necessary to account for misplaced or faulty nodes. In the other hand deploying some ten times sensors as needed in specific area is more easy than ten times deployment, therefore, we prefer to deploy all sensors at once and keep unnecessary ones off until the appropriate time comes. Thus, when a wireless sensor network was deployed, its lifetime must last as long as possible. In the other word, reducing energy consumption is the main concern of wireless sensor networks.

One of the approach to prolong network lifetime is topology control [4-6] which is referred to using node redundancy for sensing or communication subsystem, when we have more nodes than sufficient, to achieve desired level of connectivity or coverage in the network. Power management category is another approach [2,7], which is referred to switching off the radio of active nodes when there is no data to transfer.

In this work, we have used topology control to prolong network lifetime. In the same time we have devised a mechanism to provide specified percentage of coverage and we will use this concept to further extend the network lifetime when appropriate. We will review some important related work in next section. The problem definition and solution will be presented in Section 3 and the simulation and results will be provided in Section 4. In Section 5, we will conclude this paper.

2. Related Works

Many sensor network applications require high number of nodes to be deployed in monitoring area, in such application it is often undesirable to have all nodes active, and in order to increase network lifetime often sleep scheduling mechanism are used. Both random and synchronized or even deterministic mechanism are presented in literature, the main point here is to provide sufficient coverage and connectivity while keeping off as many node as possible. There have been some researchers who try to trade some coverage percentage or latency for increase in lifetime of the network.

In [8] authors presented a method for self sleep scheduling to prolong network life time, the main feature of presented algorithm is its distributed nature, when each node decide for itself make the protocol robust and scalable, another main future of this protocol is that it can provide desirable degree of coverage. In this paper the authors proof that when Rc ≥ 2Rs (where Rc is communication radius and Rs is sensing radius), the Ks-coverage (Ks-coverage means an area is covered at least Ks times) guaranty Kc-Connectivity (Kc-Connectivity means there is Kc node disjoint path between each to node of the network). However, they do not provide any guarantee for the case which Rc < 2Rs rather they suggest using modified version of SPAN [9] simultaneously to guarantee connectivity. The basic idea of SPAN and CCP is somehow similar. In SPAN each node send periodic HELLO messages providing its current state (regarding connection with other nodes and if it is participating in forwarding other nodes packets or not) and the state of its neighbors, and each node will decide to participate in packet forwarding when it detect that some of its neighbors do not have sufficient access. In CCP [10] the similar way is used for coverage, each node periodically send a hello message providing its position and current state, and also position and states of its neighbors. Base on this information a node will decide to go to sleep for a specified period if it detect that other nodes already cover its coverage area. In [11] author try to relax the ratio between sensing and communication radius and provide solution when these radius are not the same for all nodes of the network. Huang et al. proved a sufficient and necessary condition for k-coverage in a two-dimensional area. This paper is the first paper which has considered the problem of Ks-Coverage and Kc-Connectivity in integrated manner and has provided the algorithm to ensure (Ks-Kc)-CC in the network. [12] is a well-known paper regarding optimality of selected nodes.

Given a set of nodes, the minimum connected sensor cover (MCSC) problem is to find a minimum number of nodes that need to be turned on at any given point in time, such that they completely cover the region while also guaranteeing a connected-network [13].

They have also presented the distributed self-organized version of the algorithm and propose several optimization to reduce communication overhead of the algorithm. In any case, as the energy efficiency of topology control protocols is tightly related to the nodes density, also the achievable gain in terms of network lifetime depends on the actual density.

It has been shown that topology control protocol can typically increase the network lifetime by a factor of 2 - 3 with respect to a network with nodes always on [7]. This value may be not acceptable for many practical applications. To this end, topology control protocols should be coupled with other kinds of energy conservation techniques, such as power management techniques. However, the simultaneous application of multiple energy conservation schemes may lead to unforeseen consequences.

In fact, although the combination of protocols should be transparent to the applications, actually the obtained results may be very different from what one would expect [7]. Therefore this area of research require further explored yet.

3. Problem Definition

In this section we are going to formulate coverage and connectivity problem as an optimization problem so that we can solve it by means of general optimization algorithms like Genetic Algorithm.

We assume a set of sensor S = {s1, s2, ∙∙∙, sn} in a 2D area A, and further assume each sensor si is located at location (xi, yi), and has sensing radious Rs. Therefore si can detect events located at maximum distance Rs. (we have assumed a binary disk model for sensing), we make no assumption regarding the ratio of sensing radious Rs to Communication radous Rc.

A point p in A is said to be covered by si if it’s within si sensing range ai. Given an integer Ks, a point p is said to be Ks-covered if it covered at least by Ks sensors. The sensor network is said to be Ks-covered if all point in area A are Ks-covered. If for each sensor si we define a membership function di(p) such that di(p) = 1 if and di(p) = 0 if we can represent Ks-covered sensor network by:

For the set of sensors S we define communication graph Gc = (V, Ec), where V is set of sensors participating in routing and Ei is the set of edge such that edge exist between any two node of V if they can communicate with each other (we have assumed a general case where only a subset nodes V participate in routing). The degree of node is defined as the number of its one-hop neighbors. The graph Gc is said to be Kc-node connected if for any pair of nodes in V there exist at least Kc mutually node-disjoint path connecting them. For set of sensors S in area A, where each sensor si has coverage area ai, the sensing field is said (Kc – Ks) – CC if A is Ks-covered and Gc is Kc-node connected.

The network life time can be divided to some specified number of round where in each round a subset of sensors remain active and all other sensors goes to sleep mode to save their power. To simplify the problem at hand we assume that all active nodes participate in routing. Therefore for subset at each round of network life time the network will be (Kc – Ks) – CC if following conditions is met.

&

For each sensor si at round k of network lifetime, we define xik such that xik = 1 if and xik = 0 otherwise. Now we can define the Connected Sensor Cover problem as follow:

For sensor network S over monitoring area A, given a collection of (Kc – Ks) – CC subsets such as S' from S, Which are not necessarily disjoint, with time weight tk, for each round k of the network lifetime. The problem is to maximize following equation:

Subjected to following constrains:

where e is energy consumption of node in watts, Ei is total energy of node i, and γ is ratio of energy consumption of a node in sleep mode to energy consumption of node in active mode.

In this paper we will develop a centralized heuristic to solve the problem. We can consider both number of rounds r and duration of each round tk as independent variable but for simplicity we will assume a constant number of round and let tk choose any appropriate value. We can now maximize network lifetime subjected to following constraints

&

&

where the constraint number one is coverage constraint, the constraint number two is connectivity constraint and the third one is energy constraint.

3.1. Coverage Constraint

In this section we will introduce a modified version of our previous method which we have used to check the coverage of the sensor network [14]. This method can guarantee One-Cover of the network with desired percentage of coverage. We have developed an improved version of this method which is able to check Ks-covered network with desired percentage of coverage but to keep this paper short this improved version as long as the results will be introduced in our next paper.

In this work we have generated a bitmap of the domain, and by using this bitmap we have calculated coverage percentage. Each sensor si is located at location (xi, yi), and has sensing radious Rs we have considerd monitoring area A as a rectangle area of length Lx and Ly. We have divided this area to cells with dimension dx*dy where each cell represented by Aij (see Figure 1). This has lead to n*m cells in the domain so that Lx = ndx and Ly = mdy. We have created an n*m bit matrix C such that each bit of the matrix Cij is associated to cell Aij in real domain (see Figure 2).

In this way, each cell represent a small area in monitoring domain therefore by increase or decrease of these virtual cells dimensions we can get desirable accuracy for calculation of coverage. Next we will calculate the distance between each cell center and each of the nodes, if distance from center of a cell to any active sensor was lower than sensor coverage radius, this cell will be marked covered and the bit associated to it in C Matrix will become one.

Now we define the coverage as follow; for each active sensor k at position (xk, yk) cell Aij will be covered by this sensor if the distance between each point of the cell Aij and sensor k be little than or equal to sensor sensing radius Rs. For any bit of matrix C if its associated cell is

Figure 1. Area A divided to small cells.

Figure 2. Matrix C represents covered area in Domain A.

covered by sensor k we set it equal to one otherwise the value of this bit will be zero, we can represent this statement as follow:

In which (xAij, yAij) is the position of the center of cell Aij. This process will be repeated for each active sensor and finally all cells that their associated bit is not set to one are considered uncovered the coverage is calculated as follow;

Now we represent coverage constraint as follow Coverage >= Desired Coverage In which minimum desired coverage of the domain should be defined at the beginning. In this way we will have one constraint for each round of network life time. 

3.2. Connectivity Constraint

In related works section we reviewed some previous work which where able to guarantee integrated coverage and connectivity in this work we will present a novel idea based on graph theory to check the connectivity of the network. By using this method we are able to guarantee one-connect of the network. Currently we are working to improve this method so that we can check Kc-node connected network.

For communication graph Gc = (V, Ec) of the network to be connected the Laplacian of this graph should have just one zero eigenvalue, therefore in each round we will construct the laplacian of active nodes of the network and check to see if communication graph is a connected graph or not.

By definition the laplacian of graph is formed as follow

where di is degree of node i, If we sort eigenvalues of matrix L as follow

We know that l1 is always zero, therefore we check for l2. If l2 was not equal to zero we have a connected graph. In this way we will have one constraint for each round of network life time.

3.3. Energy Constraint

As we know when a node is in active state it will consume a power for sensing and communication, and when it goes to sleep it will consume small amount of energy, but total amount of energy that each node consume during network life time could not exceed its initial energy. We have written this constrain previously as follow

Therefore for each node of the network we will have one such constraint. In the next section we will present the simulation result and conclude the work.

4. Simulation and Results

We have developed a C++ code to solve this optimization problem Genetic Algorithm is used internally for optimization and Armadillo package (which itself internally uses LAPACK and BLAS) is used for eigenvalue computations.

4.1. Medium Size Network

We will consider three networks of 16, 25 and 50 nodes uniformly distributed over the area of 100 × 100 m2. Further we will assume sensing radius of network nodes Rs = 50 m and communication radius of each node Rc = 2Rs, Initial energy of each node is considered as 30 J and ratio of sleep power consumption to active power consumption gamma = 0.1.

In Figure 3 we have plotted the network life time versus desired percentage of coverage for all these networks

Figure 3. Network life time vs. desired percentage of coverage for three medium sized networks.

in one graph it is obvious that the same pattern is repeated in all networks. As can be seen in figure network life time increases when percentage coverage slightly decreases from 100 percent, but there is not linear relationship between desired percentage of coverage and network life time. The rate of increasing network life decreases with the decreases of desired percentage of coverage. Therefore the network designer should choose between the more life time and percentage of coverage based on specific application of the sensor network. In Figure 4 we have plotted the network life time versus number of deployed nodes when desired percentage of coverage has been 80%. It has shown when number of deployed nodes increases the network life time also increases but the relationship is not linear.

4.2. Large Size Network

Next we will consider three dense networks of 100, 150 and 200 nodes uniformly distributed over an area of 100 × 100 m2. Further we will assume sensing radius of network nodes Rs = 50 m and communication radius of each node Rc = 2Rs, Initial energy of each node is considered as 30 J and ratio of sleep power consumption to active power consumption gamma = 0.1.

In Figure 5 all percentage coverage curves are plotted in the same figure for comparison. As it can be seen in Figure 5 slight decrease in percentage of coverage from 100 percent to 90 percent, will nearly double the network life time. It is shown that in all cases decreasing the percentage of coverage will increase the network life time, and for all network this relationship is not linear. The rate of increasing network life time will be decreased with decreasing percentage of coverage. In Figure 6 the network life time is plotted vs. number of deployed nodes. It’s shown that the network life time will be increased with increasing number of deployed nodes and although this relationship is not linear it is close to linear one.

Figure 4. Network life time vs. number of deployed nodes.

Figure 5. Network life time vs. desired coverage percentage for 100, 150 and 200 nodes networks.

Figure 6. Network life time vs. Number of deployed nodes.

5. Conclusions

In this paper we have simulated six network of medium and large size and we have tried to find optimum node scheduling pattern to optimize network life time. We believe that these results are theoretical band to this optimization problem and it can be used as performance measure for distributed node scheduling protocols. Also we have shown that small decrease in domain coverage percentage will result in large increase of network life time which may be very beneficiary in some sensor network applications that coverage of all points of monitoring area is not critical. Also we have shown that increasing number of deployed nodes in monitoring area will increase the network life time and although this relationship is not linear it’s very close to linear one.

It should be noted that we have tried to find maximum life time extension which is possible as a result of slight decrease in coverage percentage of monitored area by selecting disjoint sets of sensors at each round of network life time. But in actual implementation of distributed protocol this level of optimization may not be possible and thus we expect that in real situation network life time will be less than result we obtained in these simulations. But still these results help us in evaluating the performance of any distributed protocol which may be implemented for this purpose.

REFERENCES

  1. I. Akyildiz, “Wireless Sensor Networks: A Survey,” Computer Networks, Vol. 38, No. 4, 2002, pp. 393-422. doi:10.1016/S1389-1286(01)00302-4
  2. C. F. Garcia-Hernández, P. H. Ibarguengoytia-González and J. A. Pérez-Diaz, “Wireless Sensor Networks and Applications: A Survey,” International Journal of Computer Science and Network Security (IJCSNS), Vol. 7, No. 3, 2007, pp. 264-273.
  3. H. Alemdar and C. Ersoy, “Wireless Sensor Networks for Healthcare: A Survey,” Computer Networks, Vol. 54, No. 15, 2010, pp. 2688-2710. doi:10.1016/j.comnet.2010.05.003
  4. S. Mahfoudh and P. Minet, “Survey of Energy Efficient Strategies in Wireless Ad Hoc and Sensor Networks,” International Conference on Networking (ICN), IEEE, 13- 18 April 2008, pp. 1-7.
  5. H. Üster and H. Lin, “Integrated Topology Control and Routing in Wireless Sensor Networks for Prolonged Network Lifetime,” Ad Hoc Networks, Vol. 9, No. 5, 2011, pp. 835-851. doi:10.1016/j.adhoc.2010.09.010
  6. M. Li and B. Yang, “A Survey on Topology Issues in Wireless Sensor Network,” International Conference on Wireless Networks (ICWN), 2006.
  7. G. Anastasi, M. Conti, M. Di Francesco and A. Passarella, “Energy Conservation in Wireless Sensor Networks: A Survey,” Ad Hoc Networks, Vol. 7, No. 3, 2009, pp. 537-568. doi:10.1016/j.adhoc.2008.06.003
  8. X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless and C. Gill, “Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks,” Proceedings of the First International Conference on Embedded Networked Sensor Systems (SenSys’03), 2003, p. 28.
  9. B. Chen, K. Jamieson, H. Balakrishnan and R. Morris, “Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” Wireless Networks, Vol. 8, No. 5, 2002, pp. 481-494. doi:10.1023/A:1016542229220
  10. X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless and C. Gill, “Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks,” ACM International Conference on Embedded Networked Sensor Systems (SenSys), ACM Press, New York, 2003, p. 28. doi:10.1145/958491.958496
  11. C.-F. Huang, Y.-C. Tseng and H.-L. Wu, “Distributed Protocols for Ensuring both Coverage and Connectivity of a Wireless Sensor Network,” ACM Transactions on Sensor Networks (TOSN), Vol. 3, No. 1, 2007, p. 5-es.
  12. S. Das and H. Gupta, “Connected K-Coverage Problem in Sensor Networks,” Proceedings of 13th International Conference on Computer Communications and Networks, 11-13 October 2004, pp. 373-378.
  13. A. Ghosh and S. K. Das, “A Distributed Greedy Algorithm for Connected Sensor Cover in Dense Sensor Networks,” Distributed Computing in Sensor Systems, Vol. 3560, 2005, pp. 340-353.
  14. H. Khosravi and L. Aslanyan, “SOCCP: Self Organize Coverage and Connectivity Protocol,” 2011 Third International Conference on Computational Intelligence, Modelling & Simulation (CIMSiM), 20-22 September 2011, pp. 317-322.