Hierarchical Approach for Efficient Decentralized Averaging in Wireless Packet Network

Hierarchical Approach for Efficient Decentralized Averaging in Wireless Packet Network

1Roopa R M, 2Mrs. Lakshmipriya

1,2 Department of Electronics And Communication Engineering , T John Institute of Technology, Bangalore VTU, India

Abstract – The hierarchical algorithm is used for solving the distributed average consensus problem in wireless sensor networks and overhead of message. The algorithm deals the problem by recursively partitioning a given network into sub networks. Initially, nodes at the finest scale gossip to compute local averages. Using multi-hop communication and geographic routing to gossip between nodes that are not directly connected, local averages are used to compute global average. To attain hierarchical scheme with k levels this is competitive with state- of-the-art randomized gossip algorithms in terms of accuracy, message complexity, node memory. Characterizing scaling laws or the rate at which the communication cost increases as a function of network size and to achieve two goals the longest distance a message travels should be much shorter than previous methods and also Distributing the computation evenly across network. In networks this results in less congestion and resource usage by reducing message retransmissions. Using MATLAB, Simulations of the proposed scheme compared with theory and existing algorithms based on averaging along paths.

Keywords: Consensus algorithms, distributed signal processing, hierarchical processing, Wireless sensor Networks ,scaling laws.

1. INTRODUCTION

   Distributed signal and information processing applications arise in a variety of contexts including Wireless sensor networks, smart-grid, mobile social networks and large-scale unmanned surveillance. Applications demand protocols and algorithms that are robust, fault-tolerant, and scalable. Energy-efficiency is an important factor [1]. When a system is using battery powered nodes or agents equipped with wireless radios for transmission. Such as in wireless sensor networks energy-efficiency require few message transmissions since consumes bandwidth, each wireless transmission consumes battery resources [2]

   In wireless sensor network applications, graphs of random geometric are a typical model for connectivity since communication is restricted to nearby nodes. In 2- dimensional graph of random geometric model, nodes are randomly assigned coordinates uniformly in the unit square. Thus motivated for efficient gossip algorithm for wireless

   networks in a number of interesting directions. Computation while enforcing the constraint that information only be exchanged between neighboring nodes each iteration.

   Always there is a tradeoff between algorithmic simplicity and performance [3,4]. Its allows only pair wise communication between neighboring nodes, we cannot beat barriers. If we have the additional knowledge of geographical information for each node and its neighbors, we can make use of geographic routing [5] and with the added complexity of averaging [6] over paths we can bring the message complexity down to linear at the expense of messages having to travel potentially over hops. However to improve upon the performance achievable using pair wise communication between neighboring nodes, additional complexity is introduced.

   1. Objective and Scope of the project

      The project introduces the concept of hierarchical approach to solve distributed average consensus problem in wireless sensor network. Primary measure of performance is communication costthe number of messages required to compute an estimate to accuracy. We are interested in characterizing scaling laws or the rate at which the communication cost increases as a function of network size. The main scope of the proposed algorithm is to improve the Network lifetime, the number of active nodes and also improve less congestion and resource usage, constant message size which is independent of the Network size, it also provides efficient energy and robustness.

      CHALLLENGES: Self-Configuration and Adaptation, Energy Efficiency, Responsiveness, Robustness, Scalability, Heterogeneity, Systematic Design, Privacy and security.

   2. Existing Systems

      Earlier in many algorithms were only considering the distance to find the shortest path from source to destination. But it will not consider the remaining energy in nodes. And faith-full transmission of data packet is not

      possible. Since there are chances that one of the node in a selected path may not have much energy to forward the data packet towards the sink node and hence the data will get lost and hence the energy is wasted.

      If a node is getting used in many transmissions then it will lose its energy and will die at the early stage. The distance between the nodes increases and after that more energy is required to forward the data packet. Because of this all reasons networks life time decreases. Since the nodes have limited amount of energy and cannot be recharged, We have to use the energy of all nodes very effectively to increase the life time of a network and reduce the cost.

      Disadvantages of Existing methods:

      1. If message lost, large number of nodes affected

      2. If messages sent over many hops , size increases because accumulates information of intermediate nodes

      3. Message size depends on

   length of path and network size.

2. THE PROPOSED ALGORITHM

The algorithm performs averaging in a hierarchical manner. At each moment only nodes in the same level of hierarchy do computations at a local scale and computation at one level begins after the previous level has finished. Decomposing the initial graph into sub graphs in hierarchically, we obtain order in the computation. for a specific decomposition it is possible to divide the overall work into a small number of linear sub-problems and thus obtain very close to linear complexity in the size of the network.

Assume we have a random geometric graph G = (V,E) and each node knows its own coordinates in the unit square and the locations of its neighbours. Each node knows the total number of nodes in the network and k levels desired of hierarchy levels. Figure 1 illustrates an example with k = 3. We use the convention that level k is the lowest level where the unit square is split into small cells. Level 1 is at top level where we have big cells. All cells at the same level have the same area. We split each cell into subcells is directed by a subdivision constant a = 2/3. If a cell contains n nodes, it is split into n1-a cells.

Fig.1: Hierarchical subdivision of the unit square

Algorithm describes hierarchical approach in a recursive manner. The initial call to the algorithm has as arguments, the vector of initial node values (xinit), the unit square (C = [0; 1] x [0; 1]), the network size n, the top level q = 1, the desired number of hierarchy levels k and the desired error tolerance to be used by each invocation of randomized gossip. In down-pass unit square is split into smaller and smaller cells all the way to the C(k;) cells. After gossiping in the G(k;_) subgraphs in Line 15, the representatives adjust their values (Line 16). if k is large enough, each G(k;_) is a complete graph. Each node knows the locations of neighbours (needed for geographic routing), at level k we can compute the size of each G(k;_) graph which is needed for the reweighting. The up-pass begins with the L(k;_) representatives forming the G(k-1;_) grid graphs (Line 8) and then running gossip in all of them in parallel. Between consecutive levels we use a = 2/3 to deide how many C(r+1;_) cells fit in each C(r;_) cell. Notice the pseudocode mimics a sequential single processor execution. However, it should be emphasized that the algorithm is intended for and can be implemented in a distributed fashion. The notation xinit(C) or xinit(L) indicates that we only select the entries of xinit corresponding to nodes in cell C or representatives L.

The ideal scenario for hierarchical approach is if computation inside each cell stops automatically when the desired accuracy is reached. This way no messages are wasted .However in practice for cells at the same level may need to gossip on graphs of different sizes that take different numbers of messages to converge. This needs for a node synchronization so that all computation in one level is finished before the next level can begin. To alleviate the synchronization issue, we can fix the number of randomized gossip iterations per level so that all computation between different sub graphs at the same level takes practically the same amount of time.

steps.

III METHODOLOGY

This project aims at the above goals by following

Step 1: Make all the initial assumptions.

Step 2: Checks the condition Q<K(Q is variables).

Step3: If condition is not exist it will reweight nodes with averages.

Step4: If condition exist then, Divide into n^(1-a) No. of nodes of n^(a-1/2) X n^(a-1/2) dimension cells.(n=no of nodes, a= constant-> (2/3)).

Step 5: Choose Representative Node in each cluster and Communicate with a node in cluster and find average .Repeat this for all cluster.

Step 6: Call multiscale gossip for all cells.

Step 7: Update average value to all representatives. Step 8: Draw grid lines of representative nodes.

Step 9: Checks the condition Q=K?, If condition is not exist,It will goes to step2.

Step 10: If condition exist, distribute multiscale average value to all nodes.

ADVANTAGES:

1. Message size is constant and Independent of network size

2. Nodes update their estimate at each iteration iii.Less congestion and resource usage iv.Energy efficient and robustness.

PERFORMANCE METRICS: Message complexity, Accuracy, Congestion, Resource usage, Energy efficiency, robustness, scalability, self-configuration etc.

IV RESULTS

In addition to theoretical results, compare hierarchical approach with path averaging via simulation in MATLAB.

Fig: No of message transmission reduced versusNumber of nodes for hierarchy

level3

Fig: No of transmission messages v/s desired hierarchical levels

Fig: Compared No of transmission message required v/s network size for hierarchical level 3,4& 5 with path averaging

CONCLUSION

The experiments, presented, suggest that hierarchical approach has superior performance for graphs of up to many thousands or nodes. Also include an evaluation in scenarios with unreliable transmissions. Compare Hierarchical approach against path averaging which is in theory the fastest algorithm for gossiping on random geometric graphs. It is worth emphasizing that both algorithms operate under the same two assumptions. First, each nodes know the coordinates of itself and its neighborhood the unit square. Second, each node know the size of the network n. In path averaging this is implicit since each message needs to be routed back to the source through the same path. It is thus necessary that nodes have global unique Ids which are equivalent to knowing the maximum id and thus the size of the network. In hierarchical approach, network size is used

for each node to determine its role in the logical hierarchy and also decide the number of hierarchy levels. Advantages are like Message size constant and independent of network size. Nodes update their estimate at each iteration. Less congestion and resource usage, Energy efficient and robustness.In this paper the result is discussed for 3,4,and 5 gossiping level and compared with each other as shown in the above graphs.

ACKNOWLEDGMENT

The author would like to thank the staff and students of the Electronics and Communication Department, T. John Institute of Technology for their guidance and support during the course work.

REFERENCES

1. Shutao Sun , Simin He , Wen Gao, Bin Pang Multiscale load adaptive scheduling for energy efficient transmission over wireless networks Personal, Indoor and Mobile Radio Communications, 2003. PIMRC 2003. 14th IEEE Proceedings

2. F. Benezit, A. Dimakis, P. Thiran, and M. Vetterli, Gossip along the way: Order-optimal consensus through randomized path averaging, in Proc. Allerton Conf. on Comm., Control, and Comp., Urbana- Champaign, IL, Sep. 2007.

3. A. Dimakis, A. Sarwate, and M. Wainwright, Geographic gossip: Efficient averaging for sensor networks, IEEE Trans. Signal Processing, vol. 56, no. 3, pp. 12051216, Mar. 2008.

4. B. Oreshkin, M. Coates, and M. Rabbat, Optimization and analysis of distributed averaging with short node memory, To appear IEEE Trans. Signal Processing, 2010.

5. Blywis, Reinecke, Gunes, Gossip routing, percolation, and restart in wireless multi-hop networks Wireless Communications and Networking Conference (WCNC), 2012 IEEE

6. MengZheng ;Goldenbaum, M. ; Stanczak, S. ; Haibin Yu Fast average consensus in clustered wireless sensor networks by superposition gossiping Wireless Communications and Networking Conference (WCNC), 2012 IEEE

AUTHOUR PROFILE

Miss.Roopa R M, received B.E Degree in Electronics and Communication from Visvesvaraya Technological University in 2013, Currently Pursuing M.Tech Degree in Digital Communication and Networking from Visvesvaraya Technological University in 2015, Department of Electronics and Communication Engineering, T John Institute of Technology Bangalore, India. Main research Interests in Wireless communication and Networking

Mrs.Lakshmipriya, received B.E Degree from Pune University in 2002, M.Tech Degree from Anna University Chennai in 2006, She is working as Assistant Professor.Department of Electronics and communication Engineering, T John Institute of Technology, Bangalore, India. Main Research Interests in image processing and digital signal processing.