Clustering Based Lifetime Maximizing Aggregation Tree for Wireless Sensor Networks

Clustering Based Lifetime Maximizing Aggregation Tree for Wireless Sensor Networks

• 1.
  Feb. 28 IJASCSE, Vol 2, Issue 1, 2013 Clustering Based Lifetime Maximizing Aggregation Tree for Wireless Sensor Networks Deepali Virmani Satbir Jain CSE BPIT, GGSIPU CSE, NSIT, New Delhi, India New Delhi, India Abstract— Energy efficiency is the most in the network. The entire node present in the important issue in all facets of wireless sensor network sends their data to a root node in the tree networks (WSNs) operations because of the such that minimum distance is being traversed, and limited and non-replenish able energy supply. The minimizing the cost in terms of energy data aggregation mechanism is one of the possible consumption and also the energy consumed is less. solutions to prolong the lifetime of sensor nodes Thus taking all the above factors in mind a final and on the other hand it also helps in eliminating tree is been selected which leads to the the data redundancy and improving the accuracy maximization of network lifetime, minimizing of information gathering, is essential for WSNs. energy consumption, minimizing distance traversed In this paper we propose a Clustering based and minimization of cost. lifetime maximizing aggregation tree (CLMAT) in which we create aggregation tree which aim to II. LITERATURE AND REVIEW reduce energy consumption. A. Data Aggregation Keywords- Aggregation, Energy, Cost, Distance. The data aggregation is a technique used to solve the implosion and overlap problems in data centric I. INTRODUCTION routing. Data coming from multiple sensor nodes WSNs are communication networks which rely on are aggregated as if they are about the same the collective information provided by sensors but attribute of the phenomenon when they reach the not on any individual sensing report. A node in same routing node on the way back to the sink. WSNs, at one specific time may be granted more Data aggregation is a widely used technique in access to the network than all other nodes if the wireless sensor networks. The security issues, data program objective is still satisfied. Network confidentiality and integrity, in data aggregation resources are shared as long as the application become vital when the sensor network is deployed performance is not degraded. As sensors are being in a hostile environment. densely-deployed in WSNs, the detection of a particular stimulus can trigger the response from B. Literature Review many nearby nodes. So instead of data being sent by all the nodes collectively, the data is aggregated Our work bears some resemblance to other research from neighboring sources locally to remove any efforts in the literature. In fact, a number of recent redundancy and produce a more concrete reading works have begun to consider collaborating nearby [7][8]. None of the previous works have considered sensor nodes by the use of a data aggregation the three most important factors (energy, distance, tree/cluster. Such tree/cluster provides event and cost) simultaneously. We focus on sources with a mechanism to refine their readings, constructing a data aggregation tree among any so that only a minimum amount of energy is given set of source nodes present in the initial required to deliver the information to the user. In network keeping all the three factors in view. this section, we provide a summary of these Moreover, the tree is structured in a way that can construction techniques. enhance the lifetime of the sensor network. Reference [9] suggests that extending node lifetime 1) Energy-Aware Data Aggregation Tree (EADAT) is equivalent to increasing the amount of The work in [1] attempts to construct a tree rooted information gathered by the tree root when the data at a base station and spanned all network nodes by rate is not time-varying. We consider a network of extensive use of timers. Motivated by the fact that randomly- deployed sensor nodes in which each only non-leaf nodes in the tree are aggregating and node has an identical transmission range. An event relaying traffic, radios of all leaf nodes are turned that triggers the sensors around it occurs at random off for immediate energy savings. The nodes with www.ijascse.in Page 8
• 2.
  Feb. 28 IJASCSE, Vol 2, Issue 1, 2013 higher residual energy have a higher chance to construction. The result can be a reduction in the become non leaf tree; thereby enhancing the node’s lifetime and the amount of information likelihood of turning off lower-energy leafs. The collected by the tree root [4]. algorithm requires a given tree root (base station) to initially broadcast a control message and start 5) Balanced Converge cast Tree the tree construction. Each node upon receiving The work in [5] addresses the problem of converge this message for the first time starts a timer that cast (many-to-one) for data aggregation. A tree that expires in time duration inversely proportional to is rooted at the base station is constructed so that its residual energy. A timer is refreshed if a node the link cost from each node to the base station is receives a message during the countdown. After the minimized. The authors further improve the design timer expires, the node broadcasts a similar control by balancing the tree during the construction, message indicating its willingness to be a parent in thereby enhancing the likelihood of simultaneous the tree. aggregation and reducing the latency for converge cast. Furthermore, two Code Division Multiple 2) Maximum Lifetime Data Aggregation Access (CDMA) codes are allocated to nodes for Reference [2] attempts to find a schedule of various collision-free transmissions towards the base directed trees, subject to the requirement that the station. number of rounds during which a base station can aggregate information from all the nodes via these 6) The Energy-Aware Spanning Tree (E-Span) trees is maximized. The protocol assumes that Before starting to describe our LPT algorithm, we nodes are aware of every other’s positions and have outline the basic spanning tree protocol [6] the abilities to directly reach any other sensor followed by presenting an energy-aware variant of (including the base station) in the network. Such a it, namely E-Span. We believe that E-Span shall Maximum Lifetime Data Aggregation (MLDA) provide some insights on how different event problem is approached by coordinating the radio sources should be arranged in the lifetime ranges and data aggregating agents of the various preserving trees and is likely to satisfy our nodes in a way that the resultant flow of traffic objectives for only a few participating source towards the base station maximizes the system nodes. lifetime. 3) Minimum-Cost Convoy Tree III. CLMAT: PROPOSED AGGREGATION More recent work has begun to consider TREE collaborating nearby sensor nodes to generate a more concrete report of the object being tracked. Previous works have considered energy, distance Such issues have been recognized by which further and cost in different scenarios, but none of them provides a dynamic convoy tree-based has considered all these factors together in a single collaboration (DCTC) framework for tracking a scenario. So keeping in mind the limitations of mobile target. The root can dynamically collect and sensor networks i.e. to reduce the energy refine the readings gathered from various tree consumed we have also considered the cost factor nodes. The challenge of their work lies in finding a also, shortest distance covered and providing sequence of minimum cost trees, so called backup for the existing sink [11]. minimum-cost convoy tree sequence, whose coverage of the moving object is above a certain The features of the proposed work are as : threshold. The tree they have considered is the one 1) Enhance network lifetime that has the root being closest to the target. 2) Minimize Energy Consumption Furthermore, all other nodes are arranged in a way 3) Minimize Distance that the cost of sending a packet via some nodes to 4) Minimize Cost Consumption this root is minimized [3]. The branch energy is calculated as follows: brEx,y,A 4) Spanning Tree over Area-Dominating Set = min {ei} (1) i ϵ Ax, ,i The small subset of nodes that covers the ≠x monitoring area is referred to as the area- dominating set. The authors in this paper suggest where the use of a spanning tree, induced by the initial brEx,y,A : Energy of branch Ax leafed at node x and interest flooding over the area-dominating set, for rooted at node y, A ϵ Px,y aggregating reply messages Iz : Set of nodes in given tree rooted at node z from various event sources. The sink where the TEIz : Energy of tree rooted at node z interest is originated from b the root of the Px,y : path b/w node x and y. spanning tree. As with DCTC, the authors did not consider node’s residual energy in the tree The tree energy is calculated as follows: www.ijascse.in Page 9
• 3.
  Feb. 28 IJASCSE, Vol 2, Issue 1, 2013 TEIz = min {ej} (2) j ϵ Iz , j ≠ x 4.) Add Vertex to Graph where addVertex() TEIz : Energy of tree rootes at node 1. i=getIndex(vname) Iz : Set of nodes in given tree rooted at node z 2. if i!=-1 3. Vertex already exists. The cost [10] is calculated as follows: 4. return 5. strcpy(vertices[n],vname) ~ ~ 6. value of ‘n’ is incremented by 1 EC (m,n) = ( emn ) Em-1 + ( enm) En-1 (3) where EC (m,n) : Energy cost for transmitting a packet from node m to node n 5. ) Add Edge To Graph emn : Transmission Energy required for node n to addEdge() transmit a bit to its neighboring node n 1. if n=0 ~ 2. No vertex exists. Em : Residual energy of node m 3. return The distance is calculated as follows: 4. while(True) Dy = Σ dy,a 5. Source vertex v1 is entered 6. i1=getIndex(v1) where 7. if(i1=-1) Dy : Total distance of tree rooted at y 8. source vertex does not exist. 9. else dy,a : Distance from root y to node a 10. Enter energy_vertex[i1] 11. Destination vertex v2 is entered A. Proposed Algorithm 12. i2=getIndex(v2) 1.) Create the graph 13. if(i2=-1) Set ‘n’ to number of sensor nodes. 14. Destination vertex does not exist. Graph() 15. else 1. for i to (n-1) 16. Enter energy_vertex[i2] 2. for j to (n-1) 17. break 3. if i equals j 18. if(energy_vertex[i1]>energy_vertex[i2]) 4. distance[i][j]=0 19. energy_edge[i1][i2]=energy_vertex[i2] 5. else 20. else 6. distance[i][j]=infinity 21. energy_edge[i1][i2]=energy_vertex[i1] 22. Enter distance[i1][i2] 2.) Checking existing edge edgeExists() 6. ) Display Graph 1. for i to (n-1) display() 2. for j to (n-1) 1. if(n=0) 3. if (distance[i][j]!=0) and 2. Graph does not exist. (distance[i][j]!=infinity) 3. return 4. Return true; 4. for i=0 to (n-1) 5. Return false; 5. vertices[i] 6. if edgeExists() 7. for i=0 to (n-1) 8. for j=0 to (n-1) 3.) Get Index for vertex name 9.if((distance[i][j]!=0)and(distance[i][j]!=infinit)) getIndex(*vname) 10.vertices[i]->vertices[j]-distance[i][j]-- 1. for i to (n-1) energy_edge[i][j] 2. if(strcmp(vertices[i],vname)==0) 3. return i; 4. else 5. return -1; www.ijascse.in Page 10
• 4.
  Feb. 28 IJASCSE, Vol 2, Issue 1, 2013 7.) Find Shortest Path & Cost of path traversed & 8.) Comparison of Aggregation Trees Energy of tree findShortestPathCostEnergy() CompareTrees( ) 1. if(n=0) 1. a=Total_Distance[0] 2. Graph does not exist. 2. for i=0 to n-1 3. return 3. if(Total_Distance[i] <a) 4. while(True) 4. a= Total_Distance[i]; 5. src=getIndex(source) 5. k=i; 6. if(src=-1) 6. b=Tree_Energy[k] 7. Source vertex does not exist. 7. c=cost_tree[k] 8. else 8. ith tree is the final tree with a, b &c as 9. break distance, energy & cost 10. for i=0 to (n-1) 9. If two trees have same parameters, their depth 11. Distance[i]=distance[src][i] traversal is considered. 12. Final[i]=0 13. Final[src]=1 14. for i=0 to (n-1) 15. for j=0 to (n-1) 16. if(Final[j]=0) 17. v=j 18. break 19. for j=0 to (n-1) 20.if (Final[j]=0) and (Distance[j]<Distance[v]) 21. v=j 22. Final[v]=1 23. for w=0 to (n-1) 24. if(Final[w]=0) 25. if(Distance[v]+distance[v][w]<Distance[w]) 26. Distance[w]=Distance[v]+distance[v][w] 27. for i=0 to (n-1) 28. for j=0 to n-1 29. if(Distance[j]=infinity) 30. source->vertices[j]=No path 31. else 32. source->vertices[j]=Distance[j] 33.if(energy_vertex[i]>energy_vertex[j]) 34.Edge _Energy[i][j]=energy_vertex[j] 35.else 36. Edge_Energy[i][j] = energy_vertex[i] 37. Total_Distance[i] = Total_Distance[i] + Distance[j] 38. a=Edge_Energy[0][1] 38. for i=0 to n-1 39. for j=0 to n-1 40. if(Edge_Energy[i][j]<a) 41. Tree_Energy[i]=Edge_Energy[i][j] 42. Residual_Energy1 = energy_vertex1- Tree_Energy 43. Residual_Energy2 = energy_vertex2 - Tree_Energy 44.cost_edge[n][n]=( energy_vertex1 / Residual_Energy1)+(energy_vertex2 / Residual_Energy2) 45.for i=0 to n-1 46.for j=0 to n-1 47. cost_tree[i]=cost_tree[i] + cost_edge[i][j] www.ijascse.in Page 11
• 5.
  Feb. 28 IJASCSE, Vol 2, Issue 1, 2013 9.) Clustering Based Lifetime Maximizing Aggregation Tree (CLMAT) Main() 1. do 2. Switch(ch) 3. if ch=1 4. addVertex() 5. break 6. if ch=2 7. addEdge() 8. break 9. If ch=3 10. display() 11. break 12. if ch=4 13. findShortestPathCostEnergy() 14. break 15. if ch=5 Energy: 3J, Cost: 21.978, Distance: 27 16. CompareTrees() Figure 3: Node B as an Aggregator node 17. if ch=6 18. exit() 19. while(ch!=6) A. Aggregation Trees Energy: 3J, Cost: 22.278, Distance: 20 Figure 4: Node C as an Aggregator node Figure 1: Graph Assumed (Initial Scenario) Energy: 3J, Cost: 22.378, Distance: 20 Energy: 3J, Cost: 22.056, Distance: 25 Figure 5: Node D as an Aggregator node Figure 2: Node A as an Aggregator node www.ijascse.in Page 12
• 6.
  Feb. 28 IJASCSE, Vol 2, Issue 1, 2013 Energy: 3J, Cost: 23.978, Distance: 39 Energy: 3J, Cost: 22.378, Distance: 16 Figure 6: Node E as an Aggregator node Figure 9: Node H as an Aggregator node B. Final Aggregation Tree Energy: 3J, Cost: 24.878, Distance: 25 Figure 7: Node F as an Aggregator node Energy: 3J, Cost: 22.378, Distance: 16 Figure 10: Node H as an Aggregator node So it is clear by applying the above proposed CLMTA algorithm we able to achieve the best possible aggregation tree. The achieved tree uses minimum energy, traversing minimum distance and cost in terms of energy is minimized for the achieved tree having H as the aggregator node. Energy: 3J, Cost: 22.378, Distance: 16 Figure 8: Node G as an Aggregator node www.ijascse.in Page 13
• 7.
  Feb. 28 IJASCSE, Vol 2, Issue 1, 2013 [4] J. Carle and D. Simplot-Ryl, “Energy-efficient area monitoring for sensor networks,”IEEE Computer Magazine, IV. CONCLUSION & FUTURE WORK vol. 37, no. 2, pp. 40-46, Feb. 2004. In this paper we proposed a clustering based [5] S. Upadhyayula, V. Annamalai, S. K. S. Gupta, “A low- lifetime maximizing aggregation tree (CLMAT) latency and energy-efficient algorithm for converge cast,“ in Proc. of IEEE Global Telecommunications Conference in which creates an aggregation tree which aims (GLOBECOM’03), vol. 6, pp. 3525-3530, Dec. 2003. to reduce energy consumption, minimize the distance traversed and minimize the cost in terms [6] R. Perlman, “Interconnections: Bridges, routers, of energy consumption. In CLMAT the node switches”, and internetworking protocol, 2nd ed., Addison- Wesley Professional Computing Series, Reading, MA, 1999. having maximum available energy is used as parent node/ aggregator node. The final tree [7] I. Nikolaidis, J. J. Harms, and S. Zhou, “On sensor data produced using the proposed algorithm proves to aggregation with redundancy removal,” in Proc. of 22nd use minimum energy as well as traverses the Biennial Symposium on Communications, Ontario, CA, May 2004. minimum distance and uses the minimum cost in terms of energy consumption. Hence by [8] A. Boulis, S. Ganeriwal, and M. B. Srivastava, achieving the above mentioned parameters the “Aggregation in sensor networks: An energy-accuracy trade- obtained aggregation tree proves to be the best off,” in Proc. of IEEE International Workshop on Sensor Network Protocols and Applications (SNPA’03), Anchorage, for enhancing the network lifetime. AK, pp. 128-138, May 2003. [9] E. J. Duarte-Melo, M. Liu, and A. Misra, “A modeling REFERENCES framework for computing lifetime and information capacity in wireless sensor networks,” in Proc. of 2nd [1] M.Ding, X.Cheng, and G.Xue, “Aggregation tree WiOpt:Modeling and Optimization in Mobile, Ad Hoc and construction in sensor networks,” in Proc. of IEEE Vehicular Wireless Networks, Cambridge, UK, pp. 45-52,Mar. 2004. Technology Conference (VTC’03), vol. 4, Orlando, FL, pp. 2168-2172, Oct. 2003. [10] Sourabh Jain, Praveen Kaushik, Jyoti Singhai, “Energy efficient maximum lifetime routing for swireless sensor”, [2] K. Dasgupta, K. Kalpakis, and P. Namjoshi, “An efficient Department of Computer Sciene and Engineering Maulana clustering-based heuristic for data gathering and aggregation Azad National Institute of Technology, Bhopal, pp. 2122- in sensor networks,” in Proc. of IEEE Wireless 2129,January2012. Communications and Networking Conference (WCNC’03), New Orleans, LA, pp. 1948-1953, Mar. 2003. [11] Construction Of Decentralized Lifetime Maximizing Tree for Data Aggregation in Wireless Sensor Networks By [3] W. Zhang and G. Cao, “DCTC: Dynamic convoy tree- Deepali Virmani , Satbir Jain ,PWASET VOLUME 40 based collaboration for target tracking in sensor networks,” APRIL 2009 ISSN 2070-3740 . IEEE Trans. Wireless Commun., vol. 3, no. 5, pp. 1689- 1701, Sept. 2004. www.ijascse.in Page 14