Coverage and network life- time enhancement for wireless sensor networks using clustering and truncated greedy algorithm (TGA) in rising and falling landscape

Coverage and network life- time enhancement for wireless sensor networks using clustering and truncated greedy algorithm (TGA) in rising and falling landscape

1. BALASARASWATHI, Research Scholar,

   APEC,

   Melmaruvathur . balameau2005@gmail.com

2. SHILPA, M.E/ECE,

TCET,

Vandavasi. shilpa.m.e13@gmail.com

Abstract-The foremost crisis in Wireless Sensor Networks (WSNs) is to achieve the maximum lifetime and region coverage for randomly deployed sensors. Recent works focuses on two-dimensional (2D) plane coverage and this plane is assumed to be an ideal one, where the sensors are deployed. But in many real time applications, sensors may also be deployed in three dimensional (3D) rising and falling landscapes. Depending on the landscape features, we face two sort of landscape coverage problem: one is the regular landscape coverage problem and irregular landscape coverage problem. In 2D plane coverage, Cone and Cos-Revolution models were used to manipulate the network lifetime in regular rising and falling landscapes. We intended to improve the coverage and lifetime of the sensor networks using Clustering and Truncated Greedy Algorithm (TGA) along with Digital Elevation Model (DEM), by scheduling and truncating the sleeping nodes in irregular rising and falling landscapes. However the packet losses occur. To overcome the problem of packet loss, clustering algorithm is utilized.

Keywords-Wireless Sensor Networks, Packet Loss, Coverage, Network Lifetime, Rising and Falling Landscapes.

1. INTRODUCTION

   Wireless sensor networks (WSNs), consists of spatially scattered autonomous sensors to examine environmental conditions and pass their info to a foremost locale. The most important uniqueness of a WSNs include: [1] Capability to endure with node failures. [2] Power consumption restrains for nodes using batteries. [3] Capability to survive harsh environmental conditions. [4] Easiness to use. [5] Scalability to hefty scale of deployment. The major applications are area, environmental, industrial, agricultural, structural, smart home monitoring, passive localization and tracking.

   The WSNs is built of nodes and it has several parts: a radio transceiver, an antenna, a microcontroller and a battery. The basic crisis in communication network is to achieve a prescribed message throughput and Quality of Service (QoS). It can be defined in terms of packet loss, message delay, transmission clout and cost of transmission. Depending on

   application, one of numerous basic network topologies can be used.

   The coverage and network lifetime is a major crisis in WSNs. In several real applications such as Terrain monitors [1] and volcano monitors [2], the interested pastures are mountainous regions. However, observing the number of randomly deployed sensors on the mountainous area to attain expected coverage and lifetime becomes a crucial chore for these applications.

   Some related works describing the network lifetime problem and coverage problems are briefly discussed here [1] [2] and [3]. In these papers, there were no frontiers for finding the weight of sub modular set. This complexity creates minimum network lifetime this in turn induces the cost. Thus the network lifetime cannot be achieved greatly by exists work.

   Besides from [1] and [2], we monitor that few mountainous territory are more or less regular and others are irregular. Then we segregate the coverage issues into two kinds: the regular terrain coverage issues and the irregular terrain coverage issues. This paper focuses on coverage enhancement and network lifetime improvement for WSNs using clustering algorithm and Truncated Greedy Algorithm in falling and rising landscapes. Also, we have our main focus on irregular rising and falling landscapes. A Truncated Greedy Algorithm is utilized to improve the network lifetime and to minimize the economic cost. Added to this, we propose a clustering algorithm to improve the coverage of WSNs by alerting the packet loss.

   The major aids of this paper are prescribed as follows:

   a) We intensively scrutinize the relationship between the network lifetime and expected coverage enhancement for falling and rising landscapes. Our scrutiny gives underlying imminent for formative the suitable number of sensors to deploy that attains a necessary network lifetime and coverage enhancement in falling and rising landscapes. b) For irregular falling and rising landscapes, we design a truncated greedy algorithm along with Digital Elevation Model (DEM) to

   achieve the maximum network lifetime and also low economic cost. c) We further propose a clustering algorithm in order to get maximum coverage enhancement by alerting the packet loss. To our finest knowledge, we are the first to study the irregular falling and rising landscapes network lifetime and coverage enhancement problem that how to evaluate the projected coverage enhancement by using clustering algorithm and the maximum network lifetime by using truncated greedy algorithm.

   The remaining of this paper is planned as follows: Section- II highlights the allied works. Section-III nears sensor deployment models. Section-IV deals the model of irregular rising and falling landscapes. Section-V a) Studies the irregular rising and falling landscapes problem and gives appropriate algorithm for maximum network lifetime and minimum cost. b) Studies irregular rising and falling landscapes crisis and gives expected coverage enhancement. Section VI deals simulation authenticates and estimate our proposed algorithms. Section- VII ends with the conclusion.

2. ALLIED WORKS

1. 2D Plane Coverage

   The computational geometry and Voronoi Diagrams are applied to study coverage for wireless sensor networks in author[4].The related and adequate conditions for grid- deployed sensor networks to wrap a bit square region in author[5].The rapport amongst the probability of a development area being K-covered, the number of sensor and sensing radius studied by author[6].The author [7],[8] achieved K-coverage under a dynamic topology and distributed algorithm was proposed for which the sensor nodes to choose the states(sleep or work) of themselves.

   Though this work studies the network lifetime and coverage enhancement problem for the rising and falling landscapes and the surface of rising and falling landscapes is three – dimensional. So transition from 2D to 3D is not effortless. Besides, the 2D coverage results can be applied to the 3D surface would reason the coverage hole problem in author [9]. Hence 2D plane coverage results cannot be suitable for rising and falling landscapes.

2. 3D Space Coverage

   In [10], [11], [12], sensors can be located liberally within a 3D volume for some real applications. The 2D solutions in [8] to 3D can be expanded by author [14], and each point is covered by at least k-sensor was checked. The coverage and connectivity issues in 3D networks were examined in paper [14]. Their target is to find a node placement strategy with cent percent coverage of a 3D space, when reducing the number of nodes required for observation. The full-coverage 3D systems with multiple connectivity construction crisis were studied by author [15]. In 3D volume, sensors can be located freely with in the whole 3D space in above works. In oceans, sensors can be seen almost everywhere in the space and it was free

   deployment in 3D space but deploy only on exposed surface. So the space coverage results cannot be used for rising and falling landscapes.

3. 3D Surface Coverage

In 3D surfae, sensors can be deployed only on the surface was studied by some researchers lately. The surface coverage problem on a 3D terrain model by simulating sensor deployment in the author of [16] was studied. They did not give expected coverage theoretically. The authors of [9], proposed the surface coverage model and simplified expected coverage ratio can be derivated.In this work, triangulation model can be used which is related to DEM and for every sensor the variations in the surface are not substantial within the sensing region. This inference will reason the loss of precision.

In [1], the author proposed the Digital Elevation Model along with approximation algorithm (O (m2n2)) for irregular terrain coverage problem. This work results in minimum network lifetime with high cost and minimum coverage ratio because of packet loss. In our proposed paper, different algorithm can be utilize along with DEM to improve network lifetime and different model along with suitable algorithm can be utilize in order to improve coverage enhancement for rising and falling landscapes without the assumption utilized in [9] and with slight modification in [1].

III SENSOR DEPLOYMENT MODEL

In the design of wireless sensor networks (WSNs), the node deployment acts as a vital role. A various properties such as coverage and network lifetime are intended to maximize by the way of nodes positioned in the particular region. In this work, we think about the stochastic or random deployment of sensors. Here, the sensors can be throwing like a seed in irregular rising and falling landscapes. The most important reasons are a) the random deployment is used in both real applications as well as theoretical studies [17] of WSNs and b) It is hard to deploy hundreds of sensor nodes in complicated hilly regions [1].

In the random or stochastic deployment approach, sensor nodes are deployed on the rising and falling landscapes. In the equivalent region their projections are equally and autonomously dispensed.

1. MODEL OF RISING AND FALLING LANDSCAPES The model which used in this work is Digital Terrain

   Model, is a digital model and the representation of three dimensional terrains surface and exposed terrain surface without any objects like vegetation and construction. A DTM can be represented as a grid of squares or triangular irregular network (TIN) has already analyzed in [1] paper.

   Figure-2: Truncated Nodes Layout

   Figure-1: DEM of Irregular Rising and Falling Landscape

2. PROPOSED ALGORITHMS FOR IRREGULAR RISING AND FALLING LANDSCAPES

   In previous work [1] they were used O (m2n2) time algorithm. The difficulty of this algorithm is within polynomial time, it consumes much time, reduces battery life and increase economic cost by the usage of more number of nodes. Obviously our algorithm gives minimum usage of nodes by scheduling the nodes (active and sleep) and it truncate the sleep node information. This minimizes the cost, time and improves the batter life. Even though packet loss is happening that can be alerted by clustering algorithm.

   1. Truncated Greedy Algorithm (TGA)

      TGA is centralized architecture and explicit. It prohibits the sleep node information. In this truncated octahedron placement strategy, the transmission range must be at least 1.7889 times the sensing range in order to maintain connectivity among nodes. If the transmission range is between 1.4142 and 1.7889 times the sensing range, then an O (m2n2) should be used. Although the required number of nodes in the O (m2n2) time placement strategies is the same, this number is 43.25% higher than the number of nodes required by the truncated octahedron placement strategy. We verify by simulation that our placement strategies indeed guarantee limited usage of nodes. We believe that our approach and our results presented in this paper could be used for improving network lifetime.

      Steps

      1: Function RESOURCEAWARE (Integer k, Sensor m, List R)

      2: Peer List fmg

      // Step 1: The broadcast step

      3: Send a message with ms identity m: ID, sensing area

      m: Area, and object count m:Count to ms neighbor Peers

      4: If Receive a message from a peer p, i.e., (p: ID, p: Area, p: count) then

      5: Add the message to Peer List

      6: If m has found an adequate number of objects, then 7: Send a notification message to ms neighbors

      8: end if

      9: If some ms neighbor has not found an adequate number of objects, then

      10: Forward the message to ms neighbors 11: end if

      12: end if

      // Step 2: The cloaked area step 13: S fmg

      14: Compute a score for each peer in Peer List

      15: Repeatedly select the peer with the highest score from Peer List to S until the total number of objects in S is at least k

      16: Area a minimum bounding rectangle of the senor nodes in S

      17: N the total number of objects in S

      // Step 3: The validation step

      18: if No containment relationship with Area and R 2 R then

      19: Send area; NÞ to the peers within Area and the server

      20: else if ms sensing area is contained by some R 2 R then

      21: Randomly select a R0 2 R such that R0: Area contains ms sensing area

      22: Send R0 to the peers within R0: Area and the server

      23: else

      24: Send Area with a cloaked N to the peers within Area and the server

      25: end if

   2. Clustering Algorithm

      1. Find the packet loss node among its neighbors as CH

      2. If (cluster_head_ID = Node ID)

      3. Cluster_head_msg (Node ID, final_CH, packet)

      4. Else

      5. Alert_cluster (cluster_head_ID, Node ID)

      6. Else

      7. Cluster_head_msg (Node ID, final_CH, packet)

3. SIMULATION RESULTS OF IRREGULAR RISING AND FALLING LANDSCAPES

   1. Simulation Results of Truncated Greedy Algorithm

      1. NAM

         The below result shows some nodes are red color for

         Figure-3: Clustering of Nodes

         Nodes can be divided in to a small number of groups, called clusters, for collecting data through well-organized network. In common, every cluster has a cluster-head which synchronizes the data gathering and collecting process in a particular cluster. Every cluster member forwards its data packets to the cluster- head in author [18]. Our proposed clustering algorithm acts as packet loss alerting algorithm. Cluster-head supervises the data packets whether going to the receiver. If not, it alerts the sender node when packet loss occurs. So the loosed data again send by

         indicating the nodes are active and some nodes are green for indicating the nodes are inactive and the black circles for indicating the sensing process. Generally in WSNs all the nodes in active state. But here after applying our Truncated Greedy Algorithm (TGA), we make some nodes in active mode and some nodes in sleep mode and also this algorithm excludes the sleep node value and takes only the active node value. In this algorithm, we can schedule the nodes according to our needs. Here by usage of limited number of nodes, the network life time is increased and economic cost is minimized.

         the sender node to the receiver node by coverage node or

         cluster-head node. The merits of this algorithm are: 1) alerts the packet loss.2) achieves the maximum coverage.

         Steps

         1. Initialize

            1. Snbr {: lies within the cluster range}

            2. Broadcast Snbr

      2. X-Graph

         Figure-4: Result of Truncated Greedy Algorithm

         1. Is_final_CHFALSE

         2. Get the node ID of the packet loss node among its neighbors

         3. Send alert to sender node

      1. Repeat

         UNTIL CHprovious =1

      2. Finalize

         1. If (is_final_CH=FALSE)

         2. If ((SCH: is a final CH) ø)

         3. Our _cluster_head packet_loss (SCH)

         4. Alert_cluster (cluster_head_ID, Node ID)

         5. Else

         /ol>

   This is time versus energy graph, y-axis clearly shows that when the energy of battery usage decreases which tends to increase period of system life in x-axis.

   Figure-5: Energy versus Time

   1. Simulation Results of Clustering Algorithm

   1. NAM

      The below result shows some sensors are deployed

      Figure-7: Minimum Packet loss versus Coverage

      The both algorithm which we used here is centralized architecture. All the nodes depend on one main node. If one node fails, sometimes it collapses the entire system. This

      randomly. In that only one node acts as a head which indicated

      in green. It supervises the neighboring node whether a packet reaching the receiver node which is in blue. If not it alerts the

      problem can be overcome distributed nature.

      by the algorithm which has

      sender which is in red to redo again for packet lost node. So the packet lost has greatly reduced by this algorithm. Hence the coverage has also enhanced greatly.

      VII CONCLUSION

      This work studied the irregular rising and falling landscape coverage and network lifetime problem. As to the improvement of network lifetime, we implemented Truncated Greedy Algorithm and as to the improvement of coverage, we implemented clustering algorithm. The results of this paper are on the basis of centralized architecture. But we think our implements can be extended to the distributed architecture.

      REFERENCES

   2. X-Graph

   Figure- 6: Result of Clustering Algorithm

   1. Liang Liu and Huadong Ma, On Coverage of Wireless Sensor Networks for Rolling Terrains,IEEE Trans. Parallel and Distributed Systems,vol.23,no.1,Jan. 2012.

   2. G.W Allen et al., Deploying a Wireless Sensor Networks on an Active Volcano, IEEE Internet Computing, vol. 10, no. 2, pp. 18-25, March- 2006.

   3. http: // blog. Xbow. Com// xblog/2009/06/ land-slide-detection- for-mountanious-region.html, 2011.

      This is packet loss versus coverage graph; y-axis clearly

      shows that when the packet loss reduces which tends to maximum coverage period in x-axis.

   4. S. Meguerdichian et al., Coverage Problems in Wireless Ad-Hoc Sensor Networks, Proc, INFOCOM 01, pp. 1380-1387, Mar. 2001.

   5. S.Shakkottai, R.Srikant, and N.B. Shroff, Unreliable Sensor

      Grids: Coverage, Connectivity and Diameter, Proc.INFOCOM 03, pp. 1073-1083, Apr. 2003.

   6. P. Wan and C. Yi, Coverage by Randomly Deployed Wireless Sensor Networks,IEEE Trans. Information Theory, vol. 52, no. 06, pp. 2658-2669, June 2006.

   7. X.Wang,G.Xing, Y.Zhang,C.Lu,R.Pless, and C.Gill, Integrated

      Coverage and Connectivity Configuration in Wireless Sensor

      Networks, Proc. ACM First Intl Conf. Wireless Sensor Network and Applications (WSNA), pp. 28- 39, Nov. 2003.

   8. C.Huang and Y.Tseng, The Coverage Problem in a Wireless Sensor Network, Proc. Second ACM Intl Conf. Wireless Sensor Networks and Applications (WSNA), pp. 115-121, Sep.2003.

   9. M.Zhao et al., Surface Coverage in Wireless Sensor Networks, Proc. IEEE INFOCOM 09, Apr.2009.

   10. M.Li and Y.Liu, Underground Coal Mine Monitoring with Wireless Sensor Networks, ACM Trans. Sensor Network, vol. 5, no. 2, pp. 1-29, Mar. 2009.

   11. E. Cayirci, H.Tezcan, Y. Dogan, and V.Coskum, Wireless Sensor Networks for Underwater Surveillance Systems, Elseveir Ad Hoc Networks, vol. 4, no. 4, pp.431-446, 2006.

   12. Y. Liu, K.Liu, and M.Li, Passive Diagnosis for Wireless Sensor Networks, IEEE/ACM Trans. Networking, vol. 18, no. 4, pp. 1132-1144, Aug. 2010.

   13. C.Huang, Y, Tseng, and L.Lo, The Coverage Problem in Three- Dimensional Wireless Sensor Networks, Proc. IEEE Global Telecomm. Conf. (GLOBECOM 04), Nov. 2004.

   14. S.M Alam and Z.J.Haas, Coverage and Connectivity in Three Dimensional Networks, Proc. ACM MobiCom 06, pp. 346-357, 2006.

   15. X.Bai, C. Zhang, D. Xuan, and W.Jia, Full-Coverage and k- Connectivity (k=14; 6) Three Dimensional Networks, Proc. IEEE INFOCOM 09, Apr. 2009.

   16. S.Oktug, A.Khalilov, and H.Tezcan,3D Coverage Analysis under Heterogeneous Deployment Strategies in Wireless Sensor Networks, Proc. Fourth Advanced Intl Conf. Telecom. (AICT08), 2008.

   17. L.Mo et al., Canopy Closure Estimates with Greenorbs: Sustainable Sensing in the Forest, SenSys09: Proc. Seventh ACM Conf. Embedded Networked Sensor Systems, Nov. 2009.

   18. Hesong Huang and Jie Wu,A Probabilistic Clustering Algorithm in Wireless Sensor Networks, Florida Atlantic University, Boca Raton, FL 33431.

   19. http: // www.ieee-xplore.com.

   20. http: // www.sciencedirect.com.