Energy Efficient TABU Optimization Routing Protocol for WSN Protocolo de enrutamiento de optimización TABU de bajo consumo de energía para WSN Protocolo de Roteamento de Otimização TABU com Eficiência Energética para RSSF

Artículo de investigación. https://doi.org/10.16925/2357-6014.2020.03.07 1 IKG PTU Regional Centre, Jalandhar (Punjab), India Orcid: https://orcid.org/0000-0001-7965-6552 E-mail: barkhabright@gmail.com; varsha.548@ctgroup.in 2 Khalsa College of Engineering & Technology, Amritsar, (Punjab), India. Orcid: https://orcid.org/0000-0002-2752-685X E-mail: drmanju571@gmail.com 3 DAV institute of Engineering, Management & Technology, Jalandhar (Punjab), India. Orcid: https://orcid.org/0000-0001-9598-0280 E-mail: drmanojkumarindia@gmail.com 4 DIT, BBAU (A Central University), Lucknow, India. Orcid: https://orcid.org/0000-0002-2126-2830 E-mail: req.mrt@gmail.com Energy Efficient TABU Optimization Routing Protocol for WSN


INTRODUCTION
Routingis a testing issue in the structure of WSNs, can greatly conserve energy and can also improve the network's life [1], while heterogeneity in WSNs can enhance the quality and time. Here, information sent from the transmitting node to the receiving nodeby lessening the over-head and increasing the throughput is the primary aim of routing. Developing a routing technique for WSNs is extremely critical. The realization of power saving to attain the green networking is the main objective of this paper. Many energy efficient clustering techniques for WSNs were introduced in the past such as SEEC, MSEEC [2] and CBCCP [3] ones, but these studies have not scrutinized the proper arrangement of the nodes to make the protocol more energy efficient and stable [4,5].In the literature of MSEEC, there exists a lack of study to investigate the proper arrangements of different nodes viz. normal, super and advanced nodes and put forward an innovative routing scheme. In order to overcome this limitation, we address the case ofa network formation model which is deployed in the network.
This launches the heterogeneity feature in the network and makes it more extensible.
After that,a cluster formation procedure is introduced which depends upon the higher energy factor of the node and makes the network smooth on the way to WSN. On the contrary, a data transmission procedure is executed, which uses a novel approach towards clustering and routing via the TABU search mechanism for the optimization of energy parameters. The simulation results of this scheme aremore lithe and efficient compared to traditional WSNs [6][7][8].
Our contribution to this work can be summarised in the following order: 1. Network formation for the deployment of nodes is mentioned here. This structure has a network scalability feature and extends up to the 500m×500m level. For energy efficient communication, direct communication between the Normal Node (NN) and Super Node (SN) and alsobe-tweenSNand AdvancedNode (AN) is provided.
2. Consideration to the optimization problem in the proposed scheme with respect to load balancing and energy consumption for the implementation of an effective and scalable network. Thus, TABU-MSEEC is proposed under the influence of cluster formation and data transmission to solve the optimization dilemma. This approach is related to the implementation of the green network.
3. With extensive simulations using a random placement of sensor nodes, the suggested technique outperforms the traditional WSN schemes and are observed to be progressively supported for different applications of WSN.

The proposed scheme is as follows:
In this convention, NNs, ANs and SNsare utilized depending on their underlying initial energy. ANs have α times and SNs have β times more energy than the NNs. The members of the cluster will send information to advanced and super node's cluster heads. After receiving the frames from the cluster member, the aggregation operation Ingeniería Solidaria e-ISSN 2357-6014 / Vol. 16, no. 3 / 2020 / Bogotá D.C., Colombia Universidad Cooperativa de Colombia is performed to reduce the excessinformation.From that point onward, the information will be sent to the sink.The novelapproach to this paper is with regards to cluster formations for sensor nodes and data transmission procedures to reduce power consumption and to improve the lifetime of the system. The procedure comprises two stages: during the first stage, the cluster formation is made on the basis of the average residual powerin the node. The average residual energy ofthe Cluster Head (CH) node is more prominent than the residualpower in the node in the system and in the second stage a 2-opt method is generated using the TABU search mechanism, which is a noteworthy criterion for routing. In this work, MSEEC protocol using the TABU search mechanism has been recommended which is a strategy with a more elevated heuristic quality for taking care of optimization issues. It can discover the ideal and close ideal answer for issues. Lots of studied have proposed routing techniquesfor saving nodal energy and improving the routing in WSNs. In this work,we address the matter of routing in WSNs utilizing the TABU search with the aim of maximizing the system lifetime. Initially, a new MSEEC protocol using the TABU search for routing in WSNs with the aim of maximizingsystem lifetime in networks of the order of 200m × 200m is proposed.
The rest of the manuscript is in the following order: Section 2 examines the related work. Methodology has been described in Section 3.Section 4 shows thenetwork and procedures utilized.Section 5 depicts the results and discussion. Finally, Section 6 concludes the paper with future directions.

RELATED WORK
The available studies have discussed the applications and limitations of the networks.
It has also given basic ideas of the functioning of the routing mechanisms and optimum low energy framework of the sensor nodes.
Vijayalakshmi et al. [9] have discussed the identification of optimum paths for routing that enhancethe life-time and decrease the power that is consumedby the network. Results showthat the efficiency of the TABU-PSO is increased by improving the formation of cluster heads, the ratio of active nodes and decreasing therate of mean packet loss, but in the paper the parameters are limited depending on the formation of network chosen. Kaur et al. [10]have proposed a hybrid data aggregating technique known as ACO/PSO,which improves the aggregation of data between the clusters.
It is a tree-based algorithm where the selection of CHs iscompletely dependent upon the remaining nodes' energy. The proposed protocol has improved the life of e-ISSN 2357-6014 / Vol. 16, no. 3 / 2020 / Bogotá D.C., Colombia Universidad Cooperativa de Colombia Energy Efficient TABU Optimization Routing Protocol for WSN theWSN over the other techniques but the author has failed to improve the area scalability as the size of network is so small.
Shankar et al. [11]haveexhibited ahybrid approach of a HAS & PSO algorithm for providing better energy efficient cluster heads. These algorithmshaveshown anincrease in residual energy by 83.89% and throughput by 29%when compared tothe PSO algorithm. However, other meta-heuristic optimization techniques make better improvement over the network. Amuthan et al. [12] have reviewed the meta-heuristic techniques which are applied on combinatorial problems. This technique relieves local search methods from the local optima problem and finds the solution from a single point which is fitted in all the aspects of computer science including VANET, software development effort estimation etc, but has not been implemented with TABU. V.Raghavendranet al. [13] have portrayed the system routing research is Swarm Intelligence (SI) which links to the complex behaviour which emerges from exceptionally straightforward individual conduct and communication that is seen naturally, particularly with social flies, for example, honey bees, ants and so forth. Every individual has little knowledge and pursues the essential guidelines utilizing nearby data adjusted from nature. Ants directing is an essential instrument from SI and gives a proficient arrangement. Fifi et al. [14] exhibited the two energy-effective grouping convention, which utilized the ideal number of energetic nodes that accomplishes the base energy utilization for the system. The M-SEEC is a heterogeneous convention and drags out the soundness time frame, expands the energy effectiveness or more normal throughput.
Tandon, Ravi et al. [15]have devoted their efforts to progressively bunched heterogeneous sensor systems. They uncovered that the presented heterogeneity aware conventions could not disperse the utilization of energy consistently. The paper has proposed Cluster Re-election Protocol (CRP),that is aware of heterogeneity and upgrades the system dependability time over prevailing conventions.Shilpaet al. [16] proposed an energy balanced cluster head selecting strategy based on QoSfor WSN, which provides the weight selection method of CH known as Cluster-Chain Weight Metric approach (CCWM) for improving theeffectiveness of the entire network. With this approach the conservation of energy of sensors and load balancing takes place.
Our objective in this paper is to select appropriate cluster headsby enhancing the quality of routing in HWSNs by lessening the general energy utilization, expanding the security time of the system and extending the system lifetime. The summary of work performed by various researchers in the past is given below:  clusters transmit the information stored in the sensors to the CHs. Once a CH gets information outlines from the clusters, the collected information is evaluated to eliminate any excess information. At that point, CHs transmit the collected information to the BS. Although a static environment is good, such type of environment is failed in heterogeneous conditions because all sensor nodes are fixed;hence it is an energy efficient protocol but it suffers from the heterogeneity of a routing protocol. If the Super Node (SN) which acts as a Cluster Head (CH) dies or fails, the whole network will collapse.If a Super Node dies, then a Normal Node will directlycommunicate with an Advanced Node(AN) and energy consumption will be high which will reduce the network lifetime of a network;the whole network is Static and it also causes flooding at the sink or base station.

Network Model
An energy-efficient communication environment has been formalised as illustrated in Figure  in which the base station is stationary and normal nodes are also static. In Figure   1(b) the nodes are changed after each round and SNs are located at a distance R2

Energy required for the Network
The nodes must be identified for evaluating the entire energy of heterogeneous systems with three levels.M AN of ANs has an initial energy of (1+α) E 0 . Similarly, M SN of SN's has an initial energy of (1+β ) E 0 and n1 of NN hasapreliminary energy of E 0 . So the entirepreliminary energy required is In this manner, the three-level M-SEEC has (α .M AN +β. M SN ) times more energy.

Total quantity of rounds in the network
It is necessary to compute the total quantity of rounds in the lifetime of the network for all three kinds of node for evaluating the required energy of that system.In the fol-

Improvised Energy Efficient TABU Optimization Routing Protocol
In the first case, an improvised TABU optimization routing protocol that has high energy efficiency has been proposedfor WSN in the presence of node heterogeneity with the routing done by TABU search in the stable environment. In this,the threekinds of nodes areon the basis of their energy value in the initial stage. The position of ANs and SNs are fixed but the position of NNs is not fixed.M SN, which represents the super node, is the ratio of the nodes having α times higher energy than NNs to the total nodes. The rest of the nodeshave energy E 0 . P=p1+p2 where p1 is the overall number ofNNslinked to ANs and p2 is the overallNNslinked to SNs.The overall energy of the triple layered networks is represented by: Therefore, the three-level M-SEEC has (α .M AN +β. M SN ) times more energy.

=
The nodes are spread in the network in a random manner and every group has a cluster head.

AsLength * Breadth >> ×
The optional length of the path from the node in uppermost cell to the bottommost cell is by using Euclidian distance.

= ×√
The meanpower consumed by the nodes in every cluster is represented by

Level of heterogeneity
The level of heterogeneity is represented by the given formula that is

Optimumcount of ANs
The amount of power that is consumed at the time of single transferis expressed by following condition (18) E AN = n A . L. E elec + n A .L. E DA +L. E elec + L. e fs .R1 2 Where E DA represents the data aggregation cost and R1 represents the distance between advanced node and base station. The energy utilized by normal nodes is expressed by the following equation

ALGORITHMS UTILIZED
These are several algorithms/procedures developed and utilized to reach our objectives.These algorithms are given below:

Network Formation Procedure
The TABU-MSEEC model considers a structure made out of a predefined quantity of nodes placed discretionarily in a testing area. The entire group of nodes have a starting energy that is proportional to E0. In the proposed estimation, 3 stages are invoked.
The first stage is a network formation procedure where the roles of different nodes are selected. The accompanying stage is the cluster formation procedure and this is where the clusters are formed. The last one is the data transmission procedure, where the routing is done via the process of theTABU algorithm.
Step 2: The AN is situated at a location that is R1 units away from the BS. Step 3: The SN is located at a position of distance R2 with respect to the remaining area(M2×M2)-(M1×M1).
Step 4: The normal nodes are randomly deployed.

Cluster Formation Procedure
Once the network model is fixed, the next aim is to identify the cluster head from the entire network. A CH should be selected on the basis of their highest energy parameter. Since all the sensor nodes have extremely restricted energy, the CH must gather all the node data and after that, forward it to the sink;the rest of the energy of the node ought to be viewed while picking the CH. Thechoosing process of the CH is as follows:

Cluster Formation Procedure
Step 1: As per the directions of the nodes in every locale, the focal point of locale's gravity is determined. This point (X f ,Y f ) ought to be correspond with the slightest square and least separation of nodes in the network, and the following formula is used. ) ) (X f ,Y f ) = min N Where(X f , Y f )is the direction of every node; Step 2: The distance between the nodes and its focal point of gravity is obtained by equation d= ) ) Step 3:Compute the normal remaining power in the nodes of every group.

Now, E rem at time t is calculated by utilisingexpression E rem = E i -E (t)
Step 4: If the remaining energy of the nodes is more prominent than every node in the mean residual energy, then that node is chosen as the head. If not, then the next node is compared. A sensor node whose energy is more prominent than the mean remaining energy is identified as the CH.

Data Transmission Procedure
In the TABU-MSEEC protocol, the TABU technique is employed in order to make the network more energy-saving. A cluster in the network is chosen on the basis of its energy parameter and these clusters gather details from their members and send it to the sink [17,18]. For the transmission phase, the TABU technique is used, which makes the network more methodical and reliable. In order to perceive the optimal solution,the initial solution is produced by the TABU search achievably and simultaneously.The inceptive solution becomes the best solution and the current solution is placed in the TABU list which is the memory list and is usedinorder to avert the cycling. The first selected element in the list is replaced by a novel oneif the existing list is already filled. Step 2: In order to producethe neighbourhood solutions, the 2 opt method is utilized which is performed by swapping the position of two randomly selected solutions. By doing so,"n*(n-1)/2" sequences are generated. The framework is initiated with a randomly generatedpreliminary solution and travels from one neighbour to anotherwhile continuously altering the value of the objective functions. E.g., let the initial sequence be (1,2,……a,…b……n).After exchanging the positions of the two solutions, the newly obtained sequence will be(1,2,……b,…a,….n), which will become the new solution for every iteration in the list. Step 3: In accordance with the aspiration criteria, the neighbourhood solution is found and the current solution is then amended in the TABU list. If the solution is good when compared to the existing optimum solution, then it is updatedin the list and the solution is monitoredto verify if itis a TABU. If it is, then choose the next ideal solution and if it is not, then the existing oneis updated as the present solution and updated in the list.
The process of steps from 1 to 3 is repeated with a specific iterated step and the lastvalue of shortest route among the entire network is given as the output.

Begin
Select a preliminary solution i in solution space. to be dead when their energy parameters value is zero. For the evaluation, the radio energy model that was proposed byHeinzelman [21] is utilised. Results of MSEEC arerelated with TABU-MSEEC protocol.They are assessed on the basis of these parameterswhich are mentioned below in Table 4.  On applying the TABU search mechanism, the following results are obtained. For the simulation,the MATLAB 2013a tool is used for easy computing of results.All results were compared with the basic multi-level protocol which has high energy efficiency and stability. The performance metrics used in the results show that the proposed TABU based MSEEC protocol is stable for a longer time,has higher energy efficiency and higher throughput when compared to basic multi-level clustering protocols. For simulation, we analyse the results based on two conditions i.e. with static nodes and moving normal nodes with each round.

Evaluation of MSEEC and TABU-MSEEC in terms of alive nodes
It is the amount of individual types of nodes and also the aggregate amount of nodes which has not used their entire energy.This measurement demonstrates the entire lifespan of the system. All the more essentially, it providesa portion of the covered area  Hence, it may be concluded from the comparison in Table 1that the optimum results are obtained when the energy value of nodes is increasing. This also indicates that TABU-MSEEC has more valuable results than the MSEEC protocol.  Similarly, for TABU-MSEEC, FND begins at around 3050 rounds, whereas LND begins at around 17000: because the TABU takes time to find the best solution initially.

Evaluation of MSEEC and TABU-M-SEEC in terms of dead nodes
The performance of MSEEC and TABU-MSEEC protocol is also determined on another parameter; dead nodes. Here, the dead node parameter is calculated among NNs, ANs, SNsand the total nodes in the network.  This is because the advanced nodes and super nodes lose their lifeslower than the normal nodes.

Evaluation of MSEEC and TABU-MSEEC in terms of throughput
Throughput is the amount of data packets which are obtained at the sink. It is considered as the totaldata which is transferred through the network, the total data sent from ANs or SNs to the BS. It can also be considered as the total data sent from the NNs to the ANs and SNs.When the proposed protocol is compared with existing protocol, it can be seen that the proposed protocol shows improved throughput.  received at the BS. The network's lifespan is goodwhen the death rate of the nodes is less and vice-versa. When the alive nodes are high, it will send more data to theBS.
It has been shown that TABU-MSEEC proved to be better than MSEEC. In MSEEC,the packets which aresent to the BS is at 12050 rounds while for TABU-MSEEC it is after 17000 rounds.

Evaluation of MSEEC and TABU-MSEEC in terms of remaining average energy
It is the amount of energy left with sensor nodes. It is computed in the beginning of each round during execution of the algorithm. This parameter helps to determine the stability period, consumption of energy and lifetime of WSNs. The residual energy is a major parameter to be considered for WSNs, that is calculated using Where E rr (Nd) is the energy of Nd th node for n th round.
Here,it is seen from the results that the average energy consumed is around 2200 rounds in MSEEC, whereasforTABU-MSEEC, it occurs even after 3500 rounds in the case of NNs.In the case of ANs, the average energy consumed is after 7500 rounds in MSEEC,while it occurs in the case of TABU-MSEEC even after 11500 rounds.
In the case of super nodes the average energy consumed is after 12000 rounds in MSEEC,while it occurs in the case of TABU-MSEEC even after 17000 rounds.Here, the observations reveal that the performance of TABUsearch is very high when compared to the MSEEC protocol because TABU search chooses the most effective solution.

CONCLUSION AND FUTURE DIRECTIONS
The TABU-MSEEC protocol presents an improvement over the MSEEC protocol. The method adopted for transmission is governed by the candidate solution of the TABU.
If the proposed solution has greater effectivenessthanthe existing optimum solution, then it is updated into the TABU list and the solution is judged to be a TABU.If it is TABU, then the 2 nd best solution is selectedfor the steps and if it is not TABU, then the solution is updated as the existing solution and the TABU list is updated. This approach may lead to a greater stability period and makes the network more efficient.
The proposed techniqueis better than the existing one since the remaining energy in the network is increased by 62% compared to normal nodes in MSEEC, 65% compared to advanced nodes in MSEEC and 70% compared to super nodes in MSEEC.
The network lifetime is also enhanced by 70.8% when compared to MSEEC. The simulated results shows the improvements of TABU-MSEEC over MSEEC. The FND is delayed by 1450, 1950 and 3500 rounds in NN, ANand SN respectively. Also, the LND is delayed by 100, 4200 and 5000 rounds in NN, AN and SN respectively. As a future work, the gathered data can be utilized to decide the impact of the path loss in applications that rely upon RSSI and the path loss exponent, for example, RSS-based confinement and energy analysis and also work on clustering and routing with other bio-inspired algorithms like cuckoo search, flower pollination, spider monkey optimization, Glow-worm and Meerkat Clan Algorithm.