Distributed Adjustment of Load- Balanced Data Aggregation Tree in Probabilistic Wireless Sensor Network

Distributed Adjustment of Load- Balanced Data Aggregation Tree in Probabilistic Wireless Sensor Network

S. Uma Devi1 P. Dhamodharan2

Anna University, Computer Science and Engineering Anna University, Computer Science and Engineering Akshaya College of Engineering and Technology Akshaya College of Engineering and Technology

Coimbatore, India Coimbatore, India

Abstract In wireless sensor networks sensor nodes periodically sense the monitored environment and send the information to the sink at which the gathered or collected information can be further processed for end-user queries. Data gathering trees capable of performing aggregation operations are also referred to as Data Aggregation Trees which are directed trees rooted at the sink and have a unique directed path from each node to the sink. The method constructs Load-Balanced Data Aggregation Tree under the Probabilistic network model. By using this proposed method the Load-Balanced Maximal Independent Set problem, the Connected Maximal Independent Set problem, and the Load- Balanced Data Aggregation Tree construction problem are solved. But additionally provide an algorithm dynamically adjusts tree structure to avoid breaking tree link because of energy drain of the sensor node. The tree adjustment only needs localized information and operations are performed on the sensors side and the tree adjustment is controlled by a sensor's grandparent to avoid loop problem. This adjustment can effectively increase throughput of Probabilistic network model in Wireless sensor network. The adjustment phase reduces the consumption of aging node's energy to prolong network lifetime.

Index TermsLoad balancing, Data aggregation tree, Energy consumption

I. INTRODUCTION

In Wireless Sensor Networks (WSNs), sensor nodes periodically sense the monitored environment and send the information to the sink (or base station), at which the gathered/collected information can be further processed for end-user queries. In this data gathering process, data aggregation can be used to fuse data from different sensors to eliminate redundant transmissions, since the data sensed by different sensors have spatial and temporal correlations .Hence, through this in-network data aggregation technique, the amount of data that needs to be transmitted by a sensor is reduced, which in turn decreases each sensors energy consumption so that the whole network lifetime is extended. For continuous monitoring applications with a periodical traffic pattern, a tree-based topology is often

adopted to gather and aggregate sensing data because of its simplicity.

A WSN consists of nodes with sensing, computing and communication capability connected according to some topology and a sink to communicate with the outside world. Load balancing research in the WSN MAC layer has traditionally focused on clustering schemes,in which the protocol selects cluster head nodes as regional coordinators to bear responsibility for a system task.

A form of dynamic cluster selection is presented in which nodes periodically rotate cluster head responsibilities to balance their energy usage. Sensor nodes probabilistically become cluster heads with probabilities governed by their remaining energy. Balance nodes transmit the data to cluster head first, and cluster heads can be organized hierarchically to assist with delivery back to the sink.

Compared with an arbitrary network of networks, a tree-based network conserves the cost of maintaining a routing table at each node, which is computationally expensive for the sensor nodes with limited resources. For clarification, data gathering trees capable of performing aggregation operations are also to as Data Aggregation Trees, which are directed trees rooted at the sink and have a unique directed path from each node to the sink. Therefore, nodes with the highest remaining energy assume more often the burden of routing and aggregating messages from their peers.

A node-centric load balancing strategy considers the cumulative load of data traffic from child nodes in a routing tree on their parent nodes. The load of child sensor nodes adds to the load of each top parent node in the tree. Hence, the sensor nodes nearest the base station will be the most heavily loaded. For clarification, data gathering trees capable of performing aggregation operations are also referred to as Data Aggregation Trees (DATs), which are directed trees rooted at the sink and have a unique directed path from each node to the sink.

Additionally, in a DAT, sensing data from different sensors are combined at intermediate sensors according to certain aggregation functions including COUNT, MIN, MAX, SUM, and AVERAGE. Data aggregation is to gather and aggregate the sensor data in an energy efficient manner so that network lifetime is enhanced.

It can result in significant energy savings for a wide range of operational scenarios. The gains from aggregation are paid for with potentially higher delay. It aims at eliminating redundant data transmission and thus improves the lifetime of energy constrained wireless sensor network. Data aggregation has been put forward as an essential paradigm for wireless routing in sensor networks.

The main work is to combine the data coming from different sources such as eliminating redundancy, minimizing the number of transmissions and thus saving energy.

This paper is organized as follows. In Section II, The network model and problem definition is given. In Section III, The Load balancing in sensor network is described, In section IV,The existing algorithm of load balancing data aggregation tree is described. V. The proposed Distributed adjustment algorithm for load balancing is described.VI,The simulation results, Performance evaluation are described. VII,The conclusion and Future work are presented .

1. NETWORK MODEL AND PROBLEM DEFINITION

   In this section, LBDAT construction problem under the DHT is avoided by distributed adjustment algorithm. We first present the assumptions, and then introduce the multi parent candidate.

   Multiple parent candidates in non-balancing sub tree has a nodes with multiple routes to the sink. Multiple parents node has the sufficient energy for transmit the packets from the childrens node.

   1. Network Model

      Under the Probabilistic Network Model (PNM), we model a WSN as an undirected graph G(V,E,P(E)),where V

      = V_s {V_o } is the set of n + 1 nodes, denoted by V_(i )where 0 i n. i is called the node ID of V

      _(i ).E is the set of lossy links. P(E) = { l_ij | (V_i ,V

      _j) E, 0 l_ij 1}.We assume a static connected WSN with the set of n nodes Vs = { V_1 V_2 V_3V_n } and one sink node V_0 .All the nodes have the same transmission range. The transmission success ratio l_ij associated with each link connecting a pair of nodes V_i,V_J is available..

   2. Problem Definition

2. LOAD BALANCING IN SENSOR NETWORKS

   A node-centric load balancing strategy considers the cumulative load of data traffic from child nodes in a routing tree on their parent candidate nodes. The WSN routing tree is linked to the sink. The load of child sensor nodes includes to the load of each top parent in the data aggregation tree. Hence, the sensor nodes near to the sink or base station will be the most heavily loaded. The goal of node-centric load balancing is to evenly distribute packet traffic generated by sensor nodes across the different branches of the routing tree

   All nodes in the sensor network periodically broadcast their existence, and neighboring information. After collecing this information, the base station constructs the graph G (V, E) (where V is the vertex set while E is the set of all edges). An algorithm is executed on G to construct a load-balanced tree.

   The load associated with a given sensor node represents the amount of data periodically generated by that sensor node. Load balanced trees can be classified into different categories. We define the level to be the distance from a node to the base station. A load-balanced tree could be fully balanced, top-level balanced or hierarchy-balanced.

   A fully balanced tree is a tree in which the branches on the same level carry the same total amount of load. A top- level balanced tree is a tree such that each branch at the top level closest to the base station carries the same amount of load. Both fully balanced trees and top-balanced trees are extreme cases of hierarchy-balanced trees, i.e. a tree in which the branches in certain levels carry the same total amount of load. In this paper, our distributed adjustment algorithm of load balancing technique focuses on constructing a load balanced tree over the sensor network.

3. EXISTING METHOD

1. Approximation Algorithm

   This algorithm can only solve the Load balanced maximal independent set and parent node assignment problem

   The basic idea of Algorithm is

   1 2 n

   1. Solving the relaxed linear programming of load balancing maximal independent set to get the optimal fractional solution ,represented by( *,v*) where *=[ *, *. *].

      i i

   2. Rounding the * to integer ` according to step 6.

      1. Algorithm Steps

         i

         1. Sort sensor nodes by the * value (where 1 i n)

            Since load-balancing is the major problem in the wireless sensor network, the measurement of the traffic load balance under the PNM is critical to solve the LBDAT construction problem. Hence, in this subsection, we first define a novel algorithm called distributed adjustment algorithm (DAA) to balance the load of the sensor nodes in the probabilistic wireless sensor network model.

            in the decreasing order.

         2. Set the sink node to be the independent node, i.e., i `=1.

         3. Set all i ` to be 1.

         4. Start from the first node in the sorted node array A. If there is no node been selected as an independent node in vis 1-hop neighborhood, then let i `=1.

         5. Repeat step 4) till reach the end of array A.

            STEP 10. Else

            STEP finds an adjustable node from the children of

            STEP12.For each

            STEP13.For each PC in of

         6. Repeat step 4) and 5) for 7In(n) / min{ * | v

      i i

      i

      V, * >0} times.

1. PROPOSED METHOD

1. Distributed Adjustment Algorithm

   Assume a node keeps the information of , j after it received all TREPs from its children, and

   LBFi1. The node attempts to adjust to obtain a new that is closest to 1. The nodes and

   are children.Node first checks whether =

   =1 or

   If yes, is a load- balancing tree; otherwise, is a non-load-balancing tree, and then attempts to adjust to form a complete or approximate load-balancing tree. When is a non-load- balancing tree selects an appropriate and adjustable grandchild from .

   Next, adds the information of into agclist, which is a list of adjustable grandchildren. One item of agclist is ( ), where is the adjusted grandchild node nagc's ID, is nagc's old parent ID, is nagc's new parent ID. This process is repeated until all adjustable grandchildren are identified.

2. Algorithm For Tree Adjustment After Node Selected Its Parent Candidate, Adjusts The Tree Of Its Children.

   : set agclist as NULL, where one item of agclist is

   < >

   STEP 1. nagc is an adjustable grandchild, NLBFi is the new LBFi,TLBFi is test LBFi

   STEP 2.

   STEP 3and 4.if has received all TREPs from its children then

   STEP 5. finds from and sets as NULL ,

   STEP 6.

   STEP 7.

   STEP 8. If = 1 or = 1 then STEP 9. is a load balancing tree and exit this

   algorithm

   STEP14. If and then is the number of sensor nodes in STi

   STEP15. TLBFi =Min(nstchim+nstchix,nstchiM-nstchiX) / Max (nstchim+nstchix,nstchiM-nstchiX)

   If TLBFi > then

   STEP16.

   STEP17.If not equal to 0 then

   STEP18. changes the parent to in TTi STEP19. adds ( ) to agclist STEP20. The process is repeated from step 5.

1. SIMULATION RESULT

   The timing performance considers the number of nodes taken for simulation with time. The distributed adjustment of load-balanced data aggregation tree time increases according to the number of nodes increases is measured and it is shown in the fig 6.1

   Figure 6.1 Timing performance of distributed adjustment algorithm in wireless sensor network

   6.1.1performance Evaluation

   The performance of the distributed adjustment algorithm in PNM in WSN for load balancing is implemented by adding multiple parent candidates in non-balancing sub tree.A node has multiple routes to the sink by multiple parent candidates. The multiple routes can balance the traffic flows.

2. CONCLUSION AND FUTURE SCOPE

The existing method has the problem of the load balanced maximal independent set and the parent node assignment problem and the method considers only one parent candidate in the data aggregation tree .In which by using the existing approximation algorithm the energy consumption will not be reduced and there is a chance for the non leaf nodes i.e., child nodes without parent node. But the proposed adjustment algorithm dynamically adjusts tree structure to avoid the breaking tree link. In this the tree adjustment needs localized information and operation of the sensor nodes .Moreover, the tree adjustment is controlled by a sensors grandparent to avoid loop problem. The Distributed adjustment algorithm has many advantages in which it reduces the traffic between the sensor nodes, Load is balanced and most important factor energy consumption by each sensor nodes available in the wireless sensor network is reduced.The proposed protocols can effectively increase converge cast throughput. The simulation result shows that the proposed algorithm can extend network lifetime significantly.

In which the distributed adjustment algorithm is used in probabilistic network model of the wireless sensor network adding multiple parent candidates in non balancing sub tree. A node has multiple routes to the sink by multiple parent candidates. When a node detects the difference between energy of the parent candidates, it dynamically selects one parent candidates. The multiple routes can balance the traffic flows.

ACKNOWLEDGEMENT

The success of a work depends on the team and its cooperation. I take this opportunity to express my gratitude and sincere thanks to everyone who helped me in my project. First and foremost, I would like to thank the Management for the Excellent Infrastructure, facilities and the constant support provided for the successful completion of the project work.

I thank Associate Professor MrP.Dhamodharan M.E., (Ph.D), Head of the Department, Computer Science and Engineering, for his valuable guidance, continuous support and suggestions to improve the quality of the project work. I express my special thanks to my guide, Associate Professor, MrP.Dhamodharan M.E., (Ph.D) for his valuable guidance, insightful comments and continuous support to carry out the project work.

I express my deep sense of gratitude to all the Faculty members and supporting staff for their continuous support in completing this project work successfully. My sincere thanks to my family members and friends for their support and motivation to carry out this project successfully.

REFERENCES

[1]. Jing He,Shouling Ji,Yi Pan,Ying Shu Li, Constructing Load Balanced Data Aggregation Tres in Probabilistic Wireless Sensor Network, July 2014

[2]. Adon Hwang,Dario Vlah,H.T.Kung,Pai-Hsiang Hsiao, Load-Balancing Routing for Wireless Access Networks,IEEE transaction,December 2008.

[3]. Agrawal,A.Manjeshwar,IEEE, Routing protocol for Enhanced Efficiency in Wireless Sensor,December 2001.

[4]. Anandhan.D,Manjula.P,Sivakumar.B,Venkatesan.B,Ve nkatraman.K,IEEEEffectual Data Collection in WSN with Path Controlled Mobile Sinks,Feburary 2012.

[5]. Chen Shigang,Zhan Zhang,International Conference, Localized Algorithm for Aggregate Fairness in Wireless Sensor Networks,April 2006.

[6]. Gupta.S.K.S,Schwieber.I,IEEE,On Tree-Based Convergecasting in Wireless Sensor Networks,April 2012.

[7]. Huseyin Ozg ur Tan and Ibrahim Korpeo,IEEE, Power Efficient Data Gathering and Aggregationin Wireless Sensor Networks,December 2003.

[8]. Konstantinos Kalpakis,KoustuvDasgupta, and Namjoshi,IEEE,Efficient Algorithms for Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks, November 2005.

[9]. Kaoru Sezaki.Niwat Thepvilojanapong,Yoshito tobe,IEEE, Hierarchy-Based Anycast Routing Protocol for Wireless Sensor Networks,Feburary 2005.

[10]. Liu.J.S and Lin pp.C.H.P,IEEE, Power-Efficiency Clustering Method With Power-limit Constraint for Sensor Networks,April 2003.

[11]. Longjiang Guo,Sushil K. Prasad,Yingshu Li,IEEE, An Energy-Efficient Distributed Algorithm for Minimum-Latency Aggregation Scheduling in wireless Sensor Network,September 2011.

[12]. Mishra.A,Raghuwanshi.S, IEEE, A Self-Adaptive Clustering Based Algorithm For Increased Energy- Efficiency and Scalability in Wireless Sensor Networks,October 2003.

[13]. Par.J and Sahni.S,IEEE,Maximum Lifetime broadcasting in Wireless Networks,December 2005.

[14]. Raheem Beyah,Shouling Ji,IEEE, Snap/shot/Continuous Data Collection Capacity for large Scale Probabilistic Wireless Sensor Networks,March 2014.

[15]. Shouling Ji,Zhipeng Cai,IEEE, Distributed Data Collection and its Capacity in Asynchronous Wireless Sensor Network,August 2013.

Authors Profile

S.Uma Devi received the B.E. degree in Computer Science and Engineering from the Karpagam College of Engineering,(Autonomous) myleripalayam, Coimbatore, Anna University, Chennai, India, in 2013.Currently doing M.E. in Computer

Science and Engineering in Akshaya college of engineering & technology,Kinathukadavu, Coimbatore, India.

Authors Profile

MrP.Dhamodharan received the M.E. degree in Computer Science and Engineering from Coimbatore Institute of Engineering and Technology and has 10 years of experience in Teaching. Currently doing Ph.D in Computer Science and

Engineering in Anna University Chennai, India His research interest includes Datamining, Networking and Cloud Computing, Image Processing.