Localization Based Evolutionary Routing (LOBER) for Efficient Aggregation in Wir

Ashwinth Janarthanan and Dhananjay Kumar

Abstract:Efficient aggregation in wireless sensor nodes helps reduce network traffic and reduce energy consumption.The objective of this work Localization Based Evolutionary Routing (LOBER) is to achieve global optimization for aggregation and WMSN lifetime.Improved localization is achieved by a novel Centroid Based Octant Localization (CBOL)technique considering an arbitrary hexagonal region.Geometric principles of hexagon are used to locate the unknown nodes in the centroid positions of partitioned regions.Flower pollination algorithm,a meta heuristic evolutionary algorithm that is extensively applied in solving real life,complex and nonlinear optimization problems in engineering and industry is modified as Enhanced Flower Pollination Algorithm (EFPA) to fit into WMSN and enhance routing mechanism and ensure efficiency in data aggregation.The system is simulated using MATLAB and found to have a considerable improvement in the optimization process.

Keywords:Wireless multimedia sensor networks,aggregation,efficiency,enhanced flower pollination algorithm,centroid based octant localization,localization based evolutionary routing.

1 Introduction

A Sensor network is highly distributed network of lightweight and small wireless node deployed densely in large numbers in order to monitor the environment or system by the measurement of physical parameters such as temperature,percentage of gases,pressure or relative humidity,and various parameters that constitute pollution levels of air.The nodes send the sensed data about the environmental changes to other nodes over flexible network architecture.Sample sensor network architecture is demonstrated in Fig.1.Deploying sensor nodes in vast geographical areas or hostile environment is highly beneficial.The wirelessly connected nodes in a wireless multimedia sensor network are capable of retrieving multimedia content from the environment such as audio and streaming videos,still images as well as scalar data and processing,storing,transmitting the obtained data.This advancement of equipping sensor nodes with audio and visual collection capabilities has enabled wireless multimedia sensor networks to enhance the exiting sensor network applications as well as support several new applications.

Figure1:Architecture of a wireless multimedia sensor network

Know ledge on various fields such as networking,information management,and digital signal processing,networking protocols and distributed algorithms is required for successful planning,implementation,deployment and operation of sensor networks.Most of the applications where sensor networks are deployed are resource constrained.One major resource constraint arises when battery operated nodes run unattended.Therefore these constraints show that considering physical,networking and application layers in a combined way and making major trade- of fs is the best approach to sensor network in a hostile manner.

Sensor networks pose many design issues.A major drawback in the operation of sensor nodes is the availability of energy.Sensors normally rely upon their battery for energy,which in lots of instances cannot be recharged or replaced.As a result,the available power at the nodes should be considered as a major constraint.The other issues with sensor networks are Energy-efficient design,Collaborative information processing and routing,Network discovery and organization etc.

Localization of sensor nodes is a necessary issue for sensor network management and operation.Once the sensor nodes are deployed their position cannot be known using any of the available supporting infrastructures in order to locate and manage them,if they are deployed without know ledge of their current locations in advance.The aim of localization is to determine the physical location of sensors,which are unaware of their location information in advance,once they are deployed.An accurate and efficient localization algorithm for sensor nodes must be capable of satisfying the following requirements:A) the localization algorithmic rule ought to be distributed because a centralized approach needs high calculation at selective nodes to estimate the position of nodes within the whole setting.This will increase communication information measure and additionally puts further load on nodes near to central node.B) Know ledge of the node location can be used to implement energy efficient routing protocols in sensor networks.C) Localization algorithms need to be sturdy enough to localize the screw ups and lack of nodes.It should be resistant to mistakes in physical measurements.D) The accuracy of the localization increases with the number of beacons.A beacon is a node that has know ledge of its current location.However,the primary issue with high number of beacons is that they are costlier than different sensor nodes and as soon as the unknown stationary nodes have been localized using beacon nodes then the beacons grow to be in vain.E) Methods that rely on measuring the ranging statistics from signal power and time of arrival require improved hardware this is typically no longer available on sensor nodes.F) Localization algorithm should be accurate,scalable and support movement of nodes.

Data aggregation is a process of compressing or reducing the duplicate sensor data using aggregation techniques such as LEACH (Low Energy Adaptive Cluster Hierarchy),HEED (Hybrid Energy Efficient Distributed),TAG (Tiny Aggregation),clustered diffusion with dynamic data aggregation (CLUDDA) in order to perform in-network processing and filtering of data which results in elimination of duplicate data transmission and thus minimizing the number of data transmissions.Power consumed by sensor node is less during processing of data than when compared to data transmission.Hence aggregation of data leads to reduced energy consumption which in turn enhances the total lifetime of the sensor network.Efficiency of aggregation algorithm can be determined in terms of processing delay and energy gain.Optimal aggregation involves finding the optimal aggregator which is an NP- hard problem in WMSN.Hence determining the most efficient algorithm to find an optimal aggregation solution is being an area of research.

2 Literature survey

Gao et al.[Gao,Song,Cheng,et al (2018)] propose a multi objective evolutionary algorithm,to predict the three-dimensional structure of protein from its one-dimensional sequence.It operates upon an innovative solvent accessible surface area as third objective.The approach resulted in better accuracy when compared with existing methods,using 66 benchmark protein structures.Efficiency of meta heuristic algorithms are better with multi objective optimizations according to Yang [Yang (2013)].The firefly algorithm is extended to solve multi objective optimization problems.To solve design optimization benchmarks,a subset of test functions was proposed and successfully validated.

A novel training algorithm based on whale optimization algorithm is proposed by Alijarah et al.[Alijarah,Fans and M irjalili (2018)] to outperform the current algorithms in terms of local optima avoidance and convergence speed.The proposed algorithm obtains a solution for a wide range of optimization problems in comparison to back propagation and many other evolutionary techniques.

Pena et al.[Pena,Robles,Larranga et al.(2004)] propose a hybrid approach based on genetic algorithm and estimation of distribution algorithms (GA-EDA) for optimization.Localization can be done with the aid of deploying beacon nodes within the vertices and the centre of hexagon,which is the basic architecture of cell used as a network [Jin and Rencheng (2016)].Unknown nodes are scattered randomly within the hexagon.Because of fixed structure of cellular network,the geometrical characteristic is made complete use of and the network is split into several regions.The minimal connecting hop between nodes varies in every region.According to respective relationship among unknown nodes hop information and divided regions,the node to be localized known as unknown node is identified in a very small region.Through calculating centroid of the small region,the localization primarily based on range-free technique is well completed.On the basis of the e simulation outcomes,it is shown that the localization algorithm based on region partition of cellular mobile has improved positioning performances,when compared with the standard processing methods.A factual subjective investigation of the Flower Pollination Algorithm is performed [Draa and Amer (2015)].Since its development,this star-rising meta heuristic has picked up a major enthusiasm for the group of met heuristic stream lining.This makes it hard to settle on the relevance of this new met heuristic in genuine applications.This paper subjectively and quantitatively examines this meta heuristic.The subjective examination concentrates on the fundamental variation of the FPA and a few augmentations of it.

Altered application in Floyd-Warshall’s calculation to get to all conceivable most brief ways in system at any given time and makes utilization of hand-shaking to demonstrate effective information transmission,accordingly supporting productive directing [Khan,Konar and Chakraborty (2014)].The proposed calculation registers the briefest way accessible contemplating a coordinated diagram and nearness of affirmation way of each navigated way.This calculation gets all the accessible most limited ways from each node to the next at once.

The analysis of various QoS parameters such as throughput,latency,error rate,jitter and residual energy and various models based on those parameters for estimating streaming capabilities in WSN are evaluated.From the obtained results it can be concluded that various parameters impact QoS parameters for multimedia streaming in WSN and by optimizing these parameters it is possible to maximize Quality of Service for multimedia streaming while minimizing error count and the packet latency.Most common parameters that can define QoS in a network are throughput (number of useful bits per second received at the data sink);Latency (delay between transmission and the reception) of a data packet;Error rate (percentage of dropped packets);Jitter-deviation in delay (latency).

3 Existing system s

3.1 Localization-Localization based on regional partition of cellular network

The unknown nodes inside a regular hexagonal region are localized by using seven anchor nodes,by fixing six nodes in the vertices and one node in the center of the hexagon.The anchor nodes broadcast hop count and location information to all unknown nodes during initialization phase.Hop matrices are constructed based on hop count information received by the unknown nodes.The positioning phase involves identification of position of unknown nodes in the centroid position of divided regions using geometrical principles of hexagon.The hop count from seven anchor nodes to the unknown node Pn is referred to as hn1,hn2,hn3,hn4,hn5,hn6,hn7 and hop matrices Hn1and Hn2are formulated as given below,

Scalability,Controlled computations,Better expansibility and lower complexity,compared to traditional algorithms are the advantages of the e algorithm.

Limitations of the e algorithm is that only the points shown in Fig.2 are considered while localizing,minimizing the accuracy of localization,leaving the remaining regions of the e boundary unattended.Also the algorithm cannot be adopted for shapes other than hexagonal regions which confines the usage of algorithm in particular sensor network applications involving placement of nodes in hexagonally spaced areas rather than deployment in regions of random shapes and surfaces.

Figure2:Identified unknown nodes inside hexagonal region

3.2 Routing-Flower pollination algorithm

Pollination in flowering plants results in formation of fruits and seeds.It is the processoftransfer of pollen grains from anther (male) of one flower to stigma (female) of another flower belonging to same or different plant.Transfer of pollen between flowers belonging to same plant is termed as abiotic pollination and transfer involving flowers belonging to two different plants is known as biotic pollination.Biotic pollination is performed with the help of pollinators such as birds,animals and insects.Pollinators moving between two flowers follow the Levy’s flight behavior.Their flying steps also follow the Levy’s flight distribution.The term flower constancy refers to interdependence between pollinators and flowers where certain birds or insects fly or jump to a specific flower species and flower support this interdependence by providing adequate food to those pollinators.

Based on the above characteristics in flowering plants,four major rules are formulated in flower pollination algorithm,which are as follows:

1.Biotic and cross-pollination,by pollinators following Levy flights,can be considered as processes of global pollination.

2.Abiotic pollination and self-pollination can be considered as local pollination.

3.Flower constancy is comparable to the reproduction possibility proportional to the two matching flowers involved.

4.The switch probability p∈[0,1] controls the shift between local and global pollination.

4 Problem definition

Accumulation and sending of information to its destination is one of the vital capacities Wireless Multimedia Sensor Networks.Subsequently learning about position and location of sensor nodes in the system gets to be basic in the vast majority of the applications.While the Global Positioning System (GPS) is a standout amongst the most well-known locating advances which is broadly open,the shortcoming of high cost and vitality devouring makes it distinctive to introduce in each node.To decrease the vitality utilization and cost,just a couple of hubs which are called reference point hubs contain the GPS modules.Other nodes can determine their location through localization technique.A desirable localization technique must be scalable,low-cost,and must have high accuracy to calculate the position of unknown nodes with minimal error rate.The algorithm should also be of less complexity thus reducing the time taken to compute location of the desired nodes.Localization based on region partition of a cellular network[Jin and Rencheng (2016)] is a localization scheme in order to determine the position of the unknown nodes inside an arbitrary hexagonal region.The algorithm aims to estimate the unknown nodes in the midpoint and centroid regions of the e triangular areas formed by the partitioning of considered hexagonal cellular regions.The algorithm aims to achieve scalability by extending it to clusters of hexagonal regions.Algorithm ensures low cost and reduced complexity due to usage of simple geometric principles for computation.The algorithm fails to identify the node positions other than those in the centroid positions.The proposed Centroid Based Octant Localization (CBOL) aims to improve the accuracy of the algorithm by using additional properties of the e considered hexagonal regions and computing the positions of nodes at the previously uncovered regions.

Sensor nodes in WMSN have battery powered devices,and their lifetime and processing capacity and abilities are limited,and in addition their transmission ranges are restricted.Conventional protocols for routing in Wireless sensor systems are in charge of keeping up the courses in the networks and need to guarantee trustable multi-hop communication under these conditions.An efficient routing protocol to provide routing capabilities by using minimal energy of sensor nodes is required.Hence determining the most appropriate algorithm that aims to find an optimal solution for the above mentioned constraints of Wireless Sensor Networks is being an area of research.Several nature inspired algorithms are being used to find most accurate solution to NP-hard problems in order to obtain the best optimal solution.But these Genetic and heuristic algorithms are not energy aware when applied in WMSN,thus algorithm should be energy efficient and also has least impact on sensors resources while sustaining computational speed.QoS parameters of WMSN are also to be considered by routing protocols.Thus,an evolutionary algorithm comes to light.They have relatively less computational difficulties of genetic algorithm and most of all the procedures of evolutionary algorithms resemble the very aspect of nature itself.Routing and data aggregation in WMSN when coupled with evolutionary algorithms will not only result in efficiency but also a futuristic optimization.

5 Centroid based octant localization (CBOL)

The proposed localization algorithm improves the localization technique by identifying unknown nodes in various regions of hexagon which are uncovered in preceding algorithm.The process of localization is performed according to the proposed “centroid based octant localization” algorithm using additional iterative step.The iteration step involves using the computed position of sensor nodes as beacon nodes and further continues localization process.The proposed algorithm is explained below.The hop count from the beacon nodes is used,by the unknown node Pnwhose position is to be computed,in order to construct the hop matrices Hn1and Hn2.Hn1consists of hop of beacon nodes placed at the vertices of the e considered hexagonal region.Hn2consists of the e hop count of the node placed at the center of the hexagon to that of the unknown node.The number of 1s in the matrix Hn1is computed as sum,based on the value of the calculated sum the different cases are formulated.

If the value of sum is equal to zero,Pnis located at the center of the hexagonal regional which is position of beacon node at the center.

If the value of sum equals to one Pnposition is identified based on value of Hn7,if Hn7is any value other than one then Pnis located at the center otherwise Pnis concluded to be placed at position of the vertex for which the corresponding hop matrix Hn1 value is 1.

If value of sum is equal 2,and if the hop count of node is a similar value from two consecutive beacon nodes placed at any two consecutive vertices the (say vertex v and v1)then Pnis located at the midpoint of v and v1.Otherwise the position of Pnis computed in the centroids region of hexagon units based on the calculated avn values and comparison with threshold value q.

When sum values equal 3,Pnis located at m idpoint of lines joining the position of beacon nodes at the center and those at the vertices of the e hexagon.These nodes are fixed as the beacon nodes for computing the nodes lying at the m idpoint positions between the new beacon nodes and the previously placed beacon nodes at the ends and vertices of the e hexagon.

The position of nodes computed using improved CBOL algorithm is as shown in Fig.3.

Figure3:Nodes computed using the improved CBOL algorithm

6 Enhanced flower pollination algorithm (EFPA)

The Enhanced Flower Pollination Algorithm is an evolutionary algorithm that is known to have achieved improved performance in optimizing an objective function which it is applied to.The architecture of the proposed EFPA optimization is as presented in Fig.4.

Figure4:Architecture of EFPA

6.1 Cluster formation

The general assumptions for cluster formation are made as follows:

i.The sensor nodes are static,not mobile or dynamic.

ii.Clusters are formed with cluster heads with a minimal hop count.

iii.Cluster heads and network topology remains unchanged unless a failure of node occurs.

6.1.1 Objective function

Objective function is the input parameter for EFPA.Selecting objective functions depends on various applications of WMSN,generally the below QoS parameters are constructed as objective functions.

a) Transmission energy

b) Network bandwidth

c) Packet delivery ratio

d) Processing speed

e) Time delay

This project concentrates on formulating Transmission energy as an objective function to be given as input for EFPA.

6.2 Transm ission power

The objective function is proposed based on Alijarah et al.[Alijarah,Fans and M irjalili(2018)] which relies on energy model of radio propagation.The transmission energy consumption of k bits data to a node is as the sum of processing energy and amplifier energy consumed to send or receive data.

ET(k,d)-Transmission energy consumption k bits data to a node in distance at d.

EPR(k)-Energy dissipation per bit used to run the transmitter circuitry.

EAMP_FS(k,d)-amplifier parameter of transmission corresponding to the free-space model of radio wave propagation.

EAMP_TR(k,d)-amplifier parameter of transmission corresponding to the free-two ray model of radio wave propagation.

d0-transmission distance threshold.

Energy of Amplifier parametersoftransmission can be calculated as below:

where,

Pt-Transmitted signal power.

Gt-Antenna gainsoftransmitter.

Gr-Antenna gainsoftransmitter.

L-System Loss (db).

Λ-Wavelength of transmission signal.

ht-Height of transmitter antenna.

hr-Height of receiver antenna.

6.3 Objective function optim ization

The objective function is optimized by any of the two pollination functions.The selection of pollination function is based on the direction of data flowin the network.

Figure5:Mapping of pollination technique

The optimization applied to the objective function is highly dependent on the location of the node(s),and can be formulated as shown in Tab.1.

Table1:Mapping of pollination technique with type of interaction between nodes

6.4 Storing route information

Routes are established within clusters by exchange of the conventional Route Request(RREQ) from member nodes to cluster head and Route Reply (RREP) from the cluster head to the member nodes as shown in Fig.6.

Figure6:Route Establishment between cluster heads and member nodes

In a particular iteration if the Gbesthas been found,it has to be updated back to the cluster heads or previous nodes for better routing in the next iteration.If a best solution is found the route table update request will be sent back to the previous node via RREP packets.

The flow diagram of proposed EFPA algorithm is as shown in Fig.7.

Figure7:Flow of EFPA implementation

The route information thus obtained by EFPA routing algorithm,using accurate localization by the improved localization algorithm CBOL is found to be outnumbering contemporary algorithms that address data aggregation requirements of various applications.The LOBER approach was implemented using MATLAB on the following pattern of clustering tesselation shown in Fig.8.

Figure8:Sample cluster tesselation structure for implementation of LOBER

The performance of the approach was compared against contemporary approaches as in Section 7.

7 Performance evaluation

The proposed LOBER approach for energy efficient aggregation using evolutionary routing and CBOL localization is compared with existing algorithms like dynamic vector hop algorithm and region partitioning algorithm based on the following parameters:

i.Localization Accuracy

ii.Error Rate

iii.Energy Consumed

7.1 Localization accuracy

The CBOL algorithm employs the concept of centroid which is the geometric point in which the gravitational force is constant at the entire surface,therefore,centroid based localization ensures that the energy spent of localizing a node anywhere in the cluster is always a constant value.The performance of CBOL was compared against that of the regional partitioning based localization algorithm and the result is given in Tab.2.

Table2:Comparison of localization accuracy

The performance of the CBOL approach was found to be better in all cases of sample hexagons taken,as seen in Fig.9.

7.2 Error rate

The average rate of error and false positives of the e LOBER approach was compared against that of the DV hop and the regional partitioning algorithms and the following values were obtained as in Tab.3.The LOBER approach clearly outperforms the traditional region partitioning and the DV hop algorithms as the error rates of LOBER are relatively low as shown in Fig.10.

Table3:Comparison of error rate

Figure10:Comparison of error rate

7.3 Energy Consumed (in Joules)

The amount of energy consumed (in joules) of the LOBER approach against DV hop and regional partitioning algorithms and the following values were obtained as in Tab.4.

Table4:Comparison of energy consumed

It is noted that the LOBER approach succumbs to the performance of DV hop algorithm in the initial stages of lesser number of nodes used as samples.As the network size is increased exceeding 200 nodes,the rate of increase in energy consumption is lesser than the other algorithms.A conclusion could be drawn that the performance of the LOBER approach increases with increase in the network size and the approach boasts a high level of scalability as shown in Fig.11.

Figure11:Comparison of energy consumption

8 Conclusion and future work

This project exposes LOBER algorithm to WMSN domain for optim ization in aggregation.CBOL algorithm involves usage of fixed areas of sensor network considered in the shape of hexagon to ultimately locate the positions sensor nodes within that hexagonal area.One major drawback for this technique can be irregular shapes of sensor network regions being used in most applications.Hence an algorithm that can compute the geometric positions of unknown nodes within regions of varying shapes by applying geometric principles corresponding that shape can be focused on in the future work.EFPA is mapped with WMSN architecture for routing and data aggregation mechanism.The proposed objective function is coupled with EFPA to obtain optimum parameter values.The nodes are localized using regional partition of cellular network.The areas that are not considered will be covered in our proposed algorithm to improve the accuracy of this existing technique.The future work will be focused on multi objective QoS functions and applying EFPA for mobile WMSN.