WSN  Vol.9 No.9 , September 2017
Improved Routing in Wireless Sensor Networks Using Harmony Search Algorithm
ABSTRACT
One of the most important issues of wireless sensor networks is how to transfer information from the network nodes to a base station and choose the best possible path for this purpose. Choosing the best path can be based on different factors such as energy consumption, response time, delay, and data transfer accuracy. Increasing the network lifetime is the most challenging problem. One of the latest energy-aware routing methods is to use the harmony search algorithm in the small-scale sensor networks. The aim of this study is to introduce the harmony search algorithm as a successful metaheuristic algorithm for wireless sensor network routing in order to increase the lifetime of such networks. This study is intended to improve the objective function for energy efficiency in the harmony search algorithm to establish balance between the network energy consumption and path length control. Therefore, it is necessary to choose the initial energy of each node randomly from a certain range as the path energy consumption should be low to choose a path which can consider the residual energy. In other words, a path should be chosen to establish balance between the network energy consumption and the minimum residual energy. The simulation results indicate that the proposed objective function provides a longer lifetime by 26.12% compared with EEHSBR.

1. Introduction

A wireless sensor network is an environmental information acquisition tool on which extensive studies have been conducted [1] . Despite the developments of such networks, small sensor nodes of large quantities still rely on low-power batteries to supply the necessary energy. Moreover, it is not normally possible to recharge or change sensor nodes because of using such networks in harsh and inaccessible environments. Therefore, one of the most important issues of wireless sensor networks is the optimal energy management.

One of the most discussable issues of such networks is how to transfer information from the network nodes to a base station and choose the best possible path for this purpose. Choosing the best path can be based on different factors such as energy consumption, response time, delay, and data transfer accuracy. Network routing is one of the most challenging issues of wireless sensor networks [2] .

Network routing is a method for transferring data and queries from a base station to the nodes selected as targets. On one hand, routing can be regarded as a method of transferring data between sensor nodes. On the other hand, transferring data between sensor network nodes and the final base station can be defined as routing. It is important to find the best path for each sensor node in terms of energy consumption in a way that the fewest nodes are involved, and less energy is consumed.

So far, many studies have been conducted on wireless sensor network routing. One of the proposed methods is to employ the harmony search algorithm. It is obvious that the objective function definition has a major role in the routing process. Given the fact that the initial energy of each node is chosen randomly from a certain range, it is important to choose a path which can establish a balance between the network energy consumption and the path residual energy. Therefore, no studies have been conducted on the effect of residual energy in the nodes on a path, a problem which is investigated in this study with respect to the reduction of network energy consumption.

The aim of this study is to define a new objective function for the harmony search algorithm, taken as a successful metaheuristic algorithm, for wireless sensor network routing in order to increase the lifetime of such networks. The harmony search algorithm is a metaheuristic algorithm developed in 2001 [3] . This algorithm is used in optimization problems [4] . Regarding wireless sensor networks, the harmony search algorithm has been used for clustering [5] , envelopment [6] and positioning [7] .

In a paper [8] , the harmony search algorithm was used to propose a new energy-aware routing method for a small-scale wireless sensor network in 2014. They also proposed a new energy-efficient objective function. This objective function establishes balance between the network energy consumption and the path length control. This paper has been used along with the harmony search algorithm in this study to increase the network lifetime by introducing an appropriate objective function.

Related Works

The HS algorithm was first developed by Zong Woo Geem. It is inspired by a process in which a musician looks at the best intended harmony [9] . The HS algorithms have successfully been effective for resolving many optimization problems such as the traveling salesman problem [9] , succession planning [10] , high-speed network multicast routing [11] , water distribution network design [12] , web document clustering [13] , transfer pipe network design [14] , and transportation paths [15] . The main use of the HS algorithms is to remove the bandwidth delay constraint on the paths of high-speed multicast networks.

[8] used the HS algorithm to solve the WSN problem to maximize the network lifetime. First, they implemented the routing process. Then they improved the harmony memory decryption and the optimization of a new harmony based on the WSN routing attributes. After that, the HS adjusting process was taken into account to propose a routing algorithm including only one specific parameter such as HMCR. However, dynamic matching was introduced for the HMCR parameter to resolve the shortcomings of primary generations and improve the local search. Finally, an effective local search strategy was proposed to improve the convergence speed and accuracy of the algorithm. In addition, the objective function was developed to modify the energy consumption and maximize the network lifetime. This algorithm is used to improve the method proposed by this study.

In [16] proposed the IHSBEER routing algorithm based on saving energy for WSN by using HS. This algorithm is meant to resolve the WSN routing problem with the help of HS. It has resulted in some major developments. First of all, harmony memory decryption has been improved with WSN routing attributes. Second, the new harmony has been improved, too. Then a type of dynamic compatibility has been introduced for HMCR to resolve shortcomings in the primary generation and improve the research capabilities of investigating next generations. At the same time, the matching (compatibility) process of the HS algorithm has been stopped to propose the routing algorithm including fewer parameters. Third, an effective local search algorithm was introduced to improve local search (investigation) capabilities and improve the convergence speed and accuracy of the routing algorithm. In addition, an objective functional model was developed for decreasing energy consumption and considering the path length.

Regarding the applications of wireless sensor networks in real life, it is necessary to optimize the performance to extend the network lifetime. The method proposed by [17] is able to practically develop protocols based on centralized clusters supported by optimization methods in wireless receiver network. Based on this framework, a protocol algorithm was designed and implemented for the wireless receiver network by using HSA, a music-based metaheuristic optimization method. This algorithm has been designed to minimize the distance between cluster members and the cluster head (CHS) and to optimize the energy distributed by the wireless receiver network. In this study, a cluster-based protocol (HSA) was employed in a real case in which the wireless receiver network was equipped with the protocol proposed in the internal environment established to monitor the temperature for fire detection. The empirical results indicate that HSA protocol can be used in cluster-based centralized wireless sensor networks to maintain security and monitor applications in construction sites. The results of empirical tests show that the wireless receiver network lifetime was extended by using HSA protocol in comparison with LEACH-C and FCM protocols.

The optimization of energy consumption is the main concern for designing and planning the exploitation of wireless sensor networks. The clustering method is employed to extend the network lifetime by collecting data and balancing energy consumption among the sensor nodes. [18] used the harmony search algorithm to minimize distances inside a node and optimize network energy consumption. A comparison was drawn between cluster-based protocol approaches such as LEACH and heuristic optimization algorithms such as the particle swarm optimization, genetic algorithm, k-means algorithm, and C-Fuzzy clustering algorithms. The simulation results indicate that HSA could decrease the energy consumption and improve the network lifetime.

In wireless sensor networks, the main concern is the network lifetime which depends on the battery or energy unit of sensor nodes existing in the network. [19] investigated energy-efficient algorithms in WSN. They suggested using the harmony search algorithm to select cluster heads in WSN, a method which has shown a better performance compared with the direct transfer of the main cluster protocol. Moreover, functional parameters such as the network lifetime and total energy consumption were investigated to compare LEACH and HAS.

[20] used the hybrid of HSA and the ant colony optimization algorithm as a metaheuristic algorithm to extend the network lifetime in WSN routing. This hybrid algorithm was named HS-ACO in which decreasing energy consumption and distributing energy appropriately among the network nodes extended the network lifetime. This algorithm is able to detect optimal paths and distribute energy among the network nodes appropriately. [21] proposed the energy-aware cluster-based routing scheme (EACBRS) to save energy with the help of hierarchical routing by calculating the optimal number of cluster heads and selecting efficient energy paths towards the sink node. [22] reviewed all the known cluster-based routing algorithms which were mainly focused on energy consumption. Each algorithm was explained in details along with the advantages and disadvantages explained explicitly. Then some of the important criteria such as scalability, message overhead, and algorithm complexity were discussed to compare the cluster-based algorithm.

[23] posed a novel bi-objective optimization problem aimed at jointly minimizing 1) the average Bit Error Rate (BER) of sensing nodes under a majority fusion rule at the central data collection unit; and 2) the mean delay experienced by packets forwarded by such nodes due to multi-hop networking, frequency channel switching time multiplexing at intermediate nodes. [24] proposed the aforementioned Pareto-optimal set of deployment by operating on two different optimization variables: the geographical position on which wireless receivers are to be deployed and their type, which determines not only their coverage range but also their bandwidth and cost. [25] proposed the genetically inspired algorithms have been extensively used so far for solving this optimization problem in a computationally efficient manner. This work extends previous preliminary research carried out by the authors on the application of the heuristic Harmony Search (HS) algorithm to this scenario by presenting further results and derivations on both HS-based centralized and distributed spectrum allocation techniques. [26] proposed a novel two-objective localization approach based on the combination of the harmony search (HS) algorithm and a local search procedure.

Regarding these methods, what matters is that none of them can operate absolutely better than others. In fact, a routing method is chosen according to the requirements of a specific application. For instance, the network response time is very important in some methods; therefore, a specific method may decrease the response time; however, it may decrease the network lifetime, too.

In another application, the response time is not important. What matters the most may be the network lifetime or energy consumption. Therefore, another method should be employed in this case. Given the fact that wireless sensor networks depend on the intended application, it will not be easy to select an optimal routing algorithm for all conditions all the time.

2. The Proposed Method

The routing problem means finding the best path to transfer information from a starting node to the sink node in a way that the lowest amount of energy is wasted in the network. Since each node may tend to send information to the sink node, the proposed algorithm should be able to detect the best path between a starting node and the sink node. This operation is repeated for different starting nodes until a node loses its energy in the network. Sending and receiving information among nodes result in the loss of node energy.

The network lifetime is regarded as the number of times when the nodes can send their information until a node runs out of energy. Therefore, if we can find more paths on which energy is waste less, more nodes can send information. In other words, the network lifetime increases, and the death of the first node is delayed.

The following algorithm is used to detect a path from a starting node to the sink node. It has been proven that WSN routing for network lifetime maximization is an NP-hard problem [7] . Many researchers have tried to develop heuristic and metaheuristic routing algorithms to solve this problem. There are many aspects of improving energy consumption in some applications of wireless sensor networks. Despite some uncertain variables and serious routing constraints in such networks, the majority of metaheuristic algorithms have not provided appropriate designs for routing such networks. This study is intended to develop a routing algorithm based on the harmony search algorithm to consume sufficient

Figure 1. Energy Consumption Model.

energy in a wireless sensor network.

Since the aim of this study is to investigate the effect of an objective function on increasing the network lifetime, the harmony search algorithm was used. Investigating the effect of the objective function of the improved harmony search algorithm can be regarded as a new problem for future studies.

Before describing the proposed method, the relevant hypotheses are stated. Then the algorithm is dealt with.

Assumptions: assume a wireless sensor network with fixed nodes. Each sensor node can exchange information with the nodes existing within its radio range (Figure 1). Nodes have different powers; however, they share the same radio range. All of the computations are done in the sink. The sink is fixed, and the sizes of sent packets are the same.

The energy consumption model [27] obtained from Equation (1):

E r = ( E e l e c × l ) + ( E a m p × l × d 2 ) , E R = ( E e l e c × l ) (1)

In this equation, E r is the energy consumed by an information-sending node, and E e l e c is the energy needed to send or receive one bit of information. It does not depend on distance. E a m p is the energy needed to strengthen the sent signal over the intended distance, l is the message length. Moreover, d is the distance between a sender and a receiver, and ER is the energy consumed by the receiver. Figure 2 shows the implementation steps of the harmony search algorithm which was used in this paper. Now the problem is described by using the harmony search algorithm.

2.1. The First Step: Initiating the Harmony Memory

This memory is a matrix of ( n + 1 ) × H M S size (HMS is the number of detected paths between a source and the sink node), and n shows the number of nodes in the network. Since the longest path of the network is a path on which all nodes exist, all rows of the harmony memory should be generated randomly first.

After generating each row, it should be checked if it is a path, and there is not a loop along it. Therefore, each node detects the nodes existing within its radio range and regards them as the neighboring nodes (with which information can be exchanged). Then the node starts to select L (defined as 5 here) nearest neighboring nodes. Each node uses the recursive method to detect the nearest paths to the sink node. Figure 3 shows a view of path selection in the wireless sensor network.

In this method, some paths are regarded as the harmony matrix element. They are nearly the shortest paths to the destination (sink node). Therefore, the runtime is improved, and inappropriate paths are not selected in this way. Moreover, using this strategy results in the number of HMS paths of different lengths

Figure 2. Flowchart of EEHSBR Algorithm [16] .

without any loops. After generating the rows, a fitness function is used to determine the fitness value of each row. These values are stored on the last row.

Creating a New Harmony of HM

The harmony matrix has been created so far; however, it does not include the best paths. Therefore, it is necessary to generate new harmonies replacing the worst harmonies, something which will result in movements towards the most appropriate solutions. Then the access to newer harmonies is explained.

A musician has three choices to play the notes in an orchestra: 1) playing famous notes exactly by heart; 2) playing the notes similarly to the notes mentioned (with a little change); and 3) playing random nodes. In the harmony search algorithm, a new harmony vector like Á = ( á 1 , á 2 , , á i , , á n ) can be selected in three ways: 1) using the variables existing in the harmony memory; 2) creating some changes in variables; and 3) creating a variable at random.

These three methods are described now. Regarding the first case, as a player can replay the notes he has already played in an orchestra, a variable can be initiated with a value which has already been given to it and exists in the harmony memory no. It is noteworthy that variables share the same position on all rows of the harmony memory matrix; therefore, when a variable chooses the first

Figure 3. A View of Path Selection in the Wireless Sensor Network.

method, one of the variables of the same column is actually selected on the harmony memory.

The probability of selecting the first case for variables is known as the harmony memory caution rate (HMCR) always ranging between zero and one. If HMCR is very small and close to on, no good solutions will result. It is usually considered that HMCR = [0.5, 0.9] in [10, 6]. Regarding the second case, a musician can make some slight changes to previous nodes existing in the harmony memory in an orchestra, something which is called a pitch adjustment (PA) in music. Likewise, a variable can make some changes in one of the values already selected through HMCR to be stored as a new value in the harmony memory, something which is also referred to as PA. In fact, PA is used to monitor the local solutions with the pitch adjustment rate (PAR). This value always ranges between zero and one. Small values of PAR slow down the convergence because small subspaces of the total solution space are searched. On the other hand, larger values of PAR make the search algorithm work more randomly. It is usually considered that PAR = [0.2, 0.6] in [10, 6].

Regarding the third case, as a musician can play random notes in an orchestra, a variable can choose some values randomly in the harmony search algorithm. The third method is referred to as randomization hereafter. The use of randomization drives the algorithm towards a global search resulting in a global optimal solution.

2.2. Defining the Fitness Function

As explained earlier, the aim of this study is to introduce an appropriate objective function for the harmony search algorithm to increase the most important parameter of such networks, i.e. the network lifetime. Moreover, decreasing the residual energy consumption and the energy consumed by sensor nodes on a path should also be taken into account to extend the network lifetime. In this step, it is important to select an appropriate fitness function. Since the aim of this study is to present a fitness function which can extend the network lifetime, some functions have been investigated in terms of the factors influencing path determination. The simulation results are discussed in the next chapter. The investigations indicated that the following fitness function could have the best results on wireless sensor networks.

F ( X ) = 1 E min × E ( X ) (2)

Updating the Harmony Memory: this fitness function decreases the energy consumption and distributes it well to find the appropriate solution. Then the fitness function is calculated for all of the rows. The rest of the proposed algorithm is as follows:

for (i = 0; i < tmax; i++)

for (j = 0; j < HMS; j++)

for each index in row

if (Rnd < HMCR(

Then using HMC

if (Rnd < PAR)

Then using PA

Else

Using Randomization

In this algorithm, tmax is the maximum number of repetitions, which was considered 100 at the end of this paper. HMS is the number of rows in the harmony memory, and Rnd is a random number between zero and one. HMCR and PAR are numbers between zero and one. They have previously been set. In this pseudo code, the harmony memory rows are monitored for tmax times, and a new solution is generated for each row by using randomization and HMC.

The first node of the new solution is exactly the same as the starting node. The other elements are generated by using randomization and HMC. It should be noted that this new solution is temporary. It will finally replace the main row by meeting the fitness function if it is better than the worst solution in the harmony memory. These two parameters are described now.

Randomization: this parameter looks exactly like the selection of an element to generate a path randomly for initiating the harmony memory. In fact, when an element should be generated, a random element is selected by considering the conditions that there is a path without any loops. The selected element should not equal the temporary solution element on the main row. Now there may be a dead end. In other words, there may not be any choices meeting the two main conditions. In this case, the previous step is repeated. In fact, the previous element is regenerated to continue the path.

HMC: to use HMC, one of the elements should be selected randomly from the intended column in a way that there is a path without any loops. It should be noted that the element itself is among the options. In this case, a dead end may be probable. Therefore, the same procedure should be adopted.

PA: in this case, a row is selected randomly first. Then HMC procedure is employed to select from the elements on the row and improve the proposed path.

After calculating the new row of the fitness function, this row is also calculated to replace the row having the worst values of the fitness function. As mentioned earlier, these operations are repeated 100 times. Finally, a row with the smallest value of fitness function is returned. All of these operations are done for a node regarded as the starting node. Then the next starting node is selected randomly. This procedure is repeated until the first node runs out of energy.

2.3. Defining the New Fitness Function

There are three important factors influencing path selection: 1) the average energy consumed along the path; 2) the average energy remaining in the nodes on the path; and 3) the minimum energy remaining the nodes on the path.

The aim of this paper is to define a fitness function which can have the greatest effect on the extension of the network lifetime. To investigate the effect of each factor and see which one has the greatest effect, the objective function should be based on them. Then the intended algorithm is implemented to select the most effective fitness function.

Before introducing the fitness functions, the following definitions should be taken into account:

Emin indicates the minimum energy remaining in the nodes on the path x, and Eavg indicates the average energy of the nodes participating on the path x. Moreover, E(x) is the total energy consumed (for sending and receiving messages) along the path x and is calculated through the following formula [8] [16] :

E ( X ) = E r ( s ) + [ x X { s , d } E r ( x ) + E R ( x ) ] + E R ( d ) (3)

In this equation, E r is the energy consumed by the node which sends information, and E R is the energy consumed by the node which receives the information. These values are obtained from Equation (1). Table 1 shows the functions defined as the fitness function. These formulas have been written according to the following hypotheses.

1) An appropriate path is a path having the lowest E ( X ) and highest E a v g and E min (because the minimum objective function is intended). In fact, the objective function should be directly related to E ( X ) and inversely related to the other two factors. Such an objective function results in the detection of shorter with the maximal energy along the path.

2) Equation (1) is used without E a v g to investigate its different effects in the previous objective function.

3) The third formula has been based on the hypothesis that path selection is directly related to the highest values of E a v g and E min ; whereas, it is inversely related to the consumed energy E ( X ) (selecting a short path).

4) Selecting shorter path and establishing balance between the greatest minimum energy remaining in nodes and energy consumption on the path: E a v g helps us choose shorter paths; however, E min can help us choose longer paths with the minimum residual energy. If the minimum residual energy is an appropriate value, the other values of energy will definitely be good, too, and the path will be appropriate. Therefore, the objective function is inversely related to E ( X ) and E min .

5) This formula is a function of Equation (4). Now this factor is considered to have an inverse relationship with E ( X ) and E min as a summation. The effect of E a v g on the objective function should be regarded as either a multiplication or summation.

6) If the path length is not important, and there is a balance between the path length and the residual energy in the network, it can be assumed that the objective function is inversely related to all three factors. Since E a v g is the average energy remaining on the path and depends on the number of nodes on the path, it cannot help choose a longer path because we always consider the average value. However, E min can help choose a longer path with the minimum residual energy because if the minimum residual energy is an appropriate value, the other values of energy will definitely be good, and an appropriate path has been chosen. Thus, it can be considered that the objective function is inversely related to E ( X ) and E min .

7) The seventh formula enables us to choose paths with greatest values of minimum energy remaining in nodes and the lowest energy consumed along the path.

The harmony search algorithm was implemented to compare these functions with each other. Regarding the fitness function, each of these equations were replaced to calculate the network lifetime for each of them. Figure 4 shows the results of the network lifetime for each function.

Table 1. Functions regarded as the fitness function.

Figure 4. The network lifetime for each function.

According to this diagram, Equations ((1)-(3), and (5)) have considered the effect of energy remaining in the nodes on the selected path. Therefore, the average effect of residual energy can be ignored on the path because the routing loops are not maximized in these functions. Equation (6) resulted in the greatest value of the network lifetime; therefore, the fitness function will be as follows:

F ( x ) = 1 E min × E ( X ) (4)

Now the defined fitness function is compared with the fitness function proposed by [8] . To investigate the efficiency. Since the aim of this study is to compare the effect of fitness function on the extension of the network lifetime, a comparison was made with the basic algorithm for better evaluation so that the algorithms could be only different in fitness functions. Therefore, comparisons can be made more appropriately.

3. Simulation and Output Analysis

Java was used to simulate the proposed method. Two experiments were conducted to investigate the performances of the proposed and EEHSBR algorithms. In this step, ten wireless sensor networks are regarded as sample graphs with different number of nodes. There are 200 × 200 m2 (10 nodes), 300 × 300 m2 (20 nodes), 400 × 400 m2 (30 nodes), 500 × 500 m2 (40 nodes), 600 × 600 m2 (50 nodes), 700 × 700 m2 (60 nodes), 800 × 800 m2 (70 nodes), 900 × 900 m2 (10 nodes), 1000 × 1000 m2 (90 nodes), and 1100 × 1100 m2 (100 nodes) generated randomly. Figure 5 shows the networks used in this experiment. In this implementation, the radio ranges of all groups were 150 (the same as the radio range in the paper by [8] ). The default values of the energy consumption model are as follows [8] :

E e l e c = 50 n J b i t E f s = 10 p J b i t m 2 l = 4098 bit

Regarding the harmony search algorithm, the following parameters were used:

H M C R = [ 0.5 , 0.9 ] , P A R = [ 0.2 , 0.6 ]

These values lead to better results in this algorithm [8] . The Euclidean dis-

Figure 5. The ten scenarios. (a) 10 node; (b) 20 node; (c) 30 node; (d) 40 node; (e) 50 node; (f) 60 node; (g) 70 node; (h) 80 node; (i) 90 node; (j) 100 node.

tance was used to determine the distance between nodes. The information pertaining to the distance between nodes is stored in a matrix which can be used as a connectivity matrix to become aware of connections between two nodes. There is also another matrix used to store the energy. After each routing period, the information is updated in this matrix. In this experiment, the nodes started to send data to the destination periodically until the destination node received 10,000 packets.

Four criteria should be investigated to compare the two cases:

1) The average residual energy indicates the average energy remaining in all nodes of the sensor network.

2) The standard deviation from the residual energy indicates the standard deviation from energy levels remaining in all nodes of the sensor network.

3) The minimum residual energy indicates the lowest energy level remaining in a node.

4) The network lifetime indicates the number of routing loops until the first node runs out of energy.

In this paper, the proposed algorithm was compared with the EEHSBR algorithm. Some Extensive experiments were conducted:

Experiment 1: in all the ten networks, the energy level was adjusted to 0.5 J. In each routing period, the starting nodes were selected randomly. Then they started sending packets to the destination node (specified in each sample network).

Experiment 2: in all the ten networks, the energy level was adjusted to a value in [0.4, 0.5] J. In each routing period, the starting nodes were selected randomly. Then they started sending packets to the destination node (specified in each sample network).

Experiment 3: for the number of different sent packets, the average residual energy and the standard deviation from the average residual energy were investigated and evaluated.

In both cases, there were 10,000 packets sent to the destination node. Then the results were investigated with respect to the four abovementioned parameters.

3.1. Experiment 1

Figures 6(a)-(d), show the average residual energy of nodes, the standard deviation from the average residual energy of all nodes, the minimum residual energy, and the network lifetime in different networks.

According to these figures, the average residual energy of network is lower in most cases in the proposed method compared with the EEHSBR algorithm, except for two cases where there are 20 and 50 nodes. The average standard deviation of the proposed method is lower than that of the EEHSBR algorithm. However, when there are 50 and 70 nodes, the EEHSBR has a lower standard deviation. Regarding the minimum residual energy, the proposed method resulted in greater levels, except for the case where there were 100 nodes so that the EEHSBR algorithm was better. Although the average energy consumption was higher in the proposed method, more energy was consumed due to the selection of longer paths compared with the EEHSBR algorithm.

However, nodes of higher energy were used for routing, something which elongates the network lifetime. Given this experiment, the efficiency of the new fitness function is totally tangible for energy consumption, and the harmony search algorithm can use this fitness function to find the optimal path.

According to the diagram in Figure 6(c), the EEHSBR improved the new fit-

Figure 6. The performances of NOF and EEHSBR in WSN. (a) Standard Deviation of Residual Energy; (b) Average Residual Energy; (c) Life of Time (rounds); (d) Minimum Residual Energy.

ness function of the proposed method. The values 128.02%, 147.83%, 57.02%, 118.70%, 73.89%, 186.17%, 127.79%, 63.13%, 26.12%, and 132.91% have been observed according to the number of nodes in the network.

3.2. Experiment 2

The initial energy of sensor nodes is something in [0.4, 0.5] J, then all the experiments are reconducted. The aim of this experiment is to investigate different values of initial energy on the new fitness function. As it is observed, the residual network energy is lower in most cases in the proposed method than in the EEHSBR algorithm, something which can show the selection of longer paths in the proposed method resulting in higher energy consumption. Therefore, the residual energy of the network has been lower than the EEHSBR method. Regarding the minimal energy, Figure 7(b) shows the average standard deviation of residual energy in nodes. The values are nearly close and lower in some cases in the proposed method.

According to the diagram in Figure 7(c), the proposed method improved the new fitness function with the EEHSBR algorithm. The values of improvement are 110.92%, 175.21%, 37.05%, 164.49%, 63.44%, 170.35%, 125.88%, 54.85%, 25.14%, and 78.82%, respectively.

The Reasons for High and Low Values on Diagrams

Experiment 1 was reconducted, and the number of repeating HMC was written down to generate paths. According to Table 2, the values of diagrams are related to the number of times HMC was used. The results were more inappropriate where this method was repeated more. For instance, the average residual energy on the path is 0.355 for ten nodes. When there were 20 nodes, the average residual energy reduced to 0.220; therefore, the average residual energy becomes lower or worse as HMC is used more often. This is true in other cases, too.

3.3. Experiment 3

In this experiment, the sensor network includes 100 nodes, and 1200 - 1300 packets are sent to the destination node (the same as the paper by [16] ). In each period, the average residual energy and standard deviation are evaluated.

According to Figure 8, the average standard deviation from the residual energy is lower in the proposed method compared with EEHSBR algorithm. Moreover, Figure 9 shows the average residual energy of sensor nodes is nearly close or lower than the EEHSBR algorithm. The better the distribution of energy is among sensor nodes, the lower the standard deviation will be from the residual energy of nodes. As observed, the new function decreases standard deviation and increased the average energy consumption to a great extent. Therefore, the network lifetime increases because of an appropriate balance between energy consumption and energy distribution. Although the average energy consumption is higher in the proposed method, nodes of higher energy were used in routing by considering the energy of nodes involved in routing. Therefore, the network lifetime has increased. According to this experiment, the efficiency of the new fitness function is quite tangible for an appropriate distribution of energy consumption, and the harmony search algorithm can use this fitness function to optimize paths well.

Figure 7. Performances of NOF and EEHSBR in WSN. (a) Standard Deviation of Residual Energy; (b) Average Residual Energy; (c) Life of Time; (d) Minimum Residual Energy.

Table 2. Comparing the HMC frequency with the standard deviation from the average residual energy on Path, Eavg, and Emin.

Figure 8. Standard deviation of residual energy.

Figure 9. Average residual energy.

4. Conclusions

The aim of this paper was to introduce a new fitness function for the wireless sensor network routing to increase the lifetime of such networks in the harmony search algorithm known as a successful metaheuristic algorithm. The new objective function is based on three important factors influencing the network: Emin which is the minimum residual energy of the nodes on a path; Eavg which is the average energy of the nodes participating in a path; and E(X) which is the total energy consumed (for sending and receiving messages) along a path. The most effective function has been selected through some calculations.

According to the selected objective function, it is observed that the minimum residual energy of nodes and the total energy consumed on the path had great effects on the selection of an appropriate path. In fact, an appropriate path can also be selected without considering the average energy of nodes. However, the effect of this value has been considered in the objective function introduced by the EEHSBR algorithm. Since this value depends on the path length, the effect of path length should also be taken into account to avoid selecting long paths. However, it is not necessary to calculate these two values in the defined objective function here. Therefore, it can be stated that the proposed objective function needs fewer calculations.

The proposed algorithm was compared with the EEHSBR algorithm for efficiency evaluation. There are four important criteria for comparing algorithms: minimum residual energy, average residual energy, the standard deviation from residual energy of nodes, and the network lifetime. Three experiments were conducted to calculate each of these three variables. The first and second experiments were meant to investigate the effect of each algorithm on the network lifetime extension. In the first experiment, all of the nodes are the same. In this case, the proposed algorithm improved the network lifetime by 128.02%, 147.83%, 57.02%, 118.70%, 73.89%, 186.17%, 127.79%, 63.13%, 26.12%, and 132.91% for different numbers of nodes (10 - 100), respectively, compared with the EEHSBR algorithm. In the second experiment, the initial energy levels of nodes were selected randomly from [0.4, 0.5]. In this case, the proposed algorithm improved the network lifetime by 110.92%, 175.21%, 164.49%, 63.44%, 170.35%, 125.88%, 54.85%, 25.14%, and 78.82% for different numbers of nodes compared with the EEHSBR algorithm. Finally, the third experiment was conducted to investigate the energy distribution in the network. The proposed algorithm improved the energy distribution by 6.12%, 2.22%, 1.89%, 1.8%, 2.12%, 1.99%, 2.22%, 2.16%, 0.33% and 2.11% compared with the EEHSBR algorithm.

Now some suggestions are made for future studies. Due to its simple structure, the harmony search algorithm can be combined with other metaheuristic algorithms [28] . Therefore, other metaheuristic algorithms can be used to improve the harmony search to solve this problem. For instance, the gravity search algorithm or the ant colony algorithm can be used to determine initial paths for the initiation of the harmony memory.

The proposed algorithm is a centralized algorithm in which all of the calculations are done in the sink. Making the proposed method compatible in a distributed way can be a topic for future works. Furthermore, the proposed function can be used in the improved harmony search to investigate the effect of the objective function in the network lifetime extension according to the results.

Cite this paper
Rahimkhani, K. and Forouzesh, F. (2017) Improved Routing in Wireless Sensor Networks Using Harmony Search Algorithm. Wireless Sensor Network, 9, 333-353. doi: 10.4236/wsn.2017.99019.
References
[1]   Akyildiz, I.F., et al. (2002) Wireless Sensor Networks: A Survey. Computer Networks, 38, 393-422.

[2]   Chong, C.-Y. and Kumar, S.P. (2003) Sensor Networks: Evolution, Opportunities, and Challenges. Proceedings of the IEEE, 91, 1247-1256.
https://doi.org/10.1109/JPROC.2003.814918

[3]   Moh’d Alia, O. and Rajeswari, M. (2011) The Variants of the Harmony Search Algorithm: An Overview. Artificial Intelligence Review, 36, 49-68. https://doi.org/10.1007/s10462-010-9201-y

[4]   Wang, N., Huang, Y. and Liu, W. (2008) A Fuzzy-Based Transport Protocol for Mobile Ad Hoc Networks. IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, Taichung, 11-13 June 2008, 320-325. https://doi.org/10.1109/SUTC.2008.52

[5]   Lee, K. and Geem, Z. (2005) A New Meta-Heuristic Algorithm for Continuous Engineering Optimization: Harmony Search Theory and Practice. Computer Methods in Applied Mechanics and Engineering, 194, 3902-3933.

[6]   Manjarres, D., Del Ser, J., Gil-Lopez, S., Vecchio, M., Landa-Torres, I. and Lopez-Valcarce, R. (2013) A Novel Heuristic Approach for Distance- and Connectivity-Based Multihop Node Localization in Wireless Sensor Networks. Soft Computing, 17, 17-28.
https://doi.org/10.1007/s00500-012-0897-2

[7]   Park, J. and Sahni, S. (2006) An Online Heuristic for Maximum Lifetime Routing in Wireless Sensor Networks. IEEE Transactions on Computers, 55, 1048-1056.
https://doi.org/10.1109/TC.2006.116

[8]   Zeng, B. and Yan, D. (2014) An Energy Efficient Harmony Search Based Routing Algorithm for Small-Scale Wireless Sensor Networks. IEEE 17th International Conference on Computational Science and Engineering, Chengdu, 19-21 December 2014, 362-367.

[9]   Geem, Z.W., Kim, J.H. and Loganathan, G. (2001) A New Heuristic Optimization Algorithm: Harmony Search. Simulation, 76, 60-68. https://doi.org/10.1177/003754970107600201

[10]   Wang, L., et al. (2013) An Enhanced Harmony Search Algorithm for Assembly Sequence Planning. International Journal of Modelling, Identification and Control, 18, 18-25.
https://doi.org/10.1504/IJMIC.2013.051929

[11]   Forsati, R., Haghighat, A.T. and Mahdavi, M. (2008) Harmony Search Based Algorithms for Bandwidth-Delay-Constrained Least-Cost Multicast Routing. Computer Communications, 31, 2505-2519.

[12]   Lee, H.M., et al. (2016) Optimal Cost Design of Water Distribution Networks using a Decomposition Approach. Engineering Optimization, 48, 2141-2156.

[13]   Mahdavi, M., et al. (2008) Novel Meta-Heuristic Algorithms for Clustering Web Documents. Applied Mathematics and Computation, 201, 441-451.

[14]   Geem, Z.W., Kim, J.H. and Loganathan, G.V. (2002) Harmony Search Optimization: Application to Pipe Network Design. International Journal of Modelling and Simulation, 22, 125-133.

[15]   Geem, Z.W., Lee, K.S. and Park, Y. (2005) Application of Harmony Search to Vehicle Routing. American Journal of Applied Sciences, 2, 1552-1557.
https://doi.org/10.3844/ajassp.2005.1552.1557

[16]   Zeng, B. and Yan, D. (1999) An Improved Harmony Search Based Energy-Efficient Routing Algorithm for Wireless Sensor Networks. Applied Soft Computing, 41, 135-147. Kahn, J.M., Katz, R.H. and Pister, K.S.J. (2016) Next Century Challenges: Mobile Networking for Smart Dust. The 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, 271-278.

[17]   Hoang, D.C., et al. (2014) Real-Time Implementation of a Harmony Search Algorithm-Based Clustering Protocol for Energy-Efficient Wireless Sensor Networks. IEEE Transactions on Industrial Informatics, 10, 774-783. https://doi.org/10.1109/TII.2013.2273739

[18]   Hoang, D.C., et al. (2010) A Robust Harmony Search Algorithm Based Clustering Protocol for Wireless Sensor Networks. IEEE International Conference on Communications Workshops, Capetown, 23-27 May 2010, 1-5. https://doi.org/10.1109/ICCW.2010.5503895

[19]   Shankar, T., Shanmugavel, S. and Karthikeyan, A. (2013) Modified Harmony Search Algorithm for Energy Optimization in WSN. International Review on Computers and Software, 8, 1469-1475.

[20]   Kamaei, Z., Bakhshi, H. and Masoumi, B. (2015) Combining Harmony Search Algorithm and Ant Colony Optimization Algorithm to Increase the Lifetime of Wireless Sensor Networks. Journal of Advances in Computer Engineering and Technology, 1, 9-16.

[21]   Dehghania, S., Pourzaferanib, M. and Barekatainc, B. (2015) Comparison on Energy-Efficient Cluster Based Routing Algorithms in Wireless Sensor Network. The Third Information Systems International Conference, 72, 535-542.

[22]   Roy, S. (2015) Energy Aware Cluster Based Routing Scheme for Wireless Sensor Network. Foundations of Computing and Decision Sciences, 40, 203-222.

[23]   Del Ser, J., et al. (2016) Joint Topology Optimization, Power Control and Spectrum Allocation for Intra-Vehicular Multi-Hop Sensor Networks Using Dandelion-Encoded Heuristics. In: European Conference on the Applications of Evolutionary Computation, Springer, Cham.
https://doi.org/10.1007/978-3-319-31204-0_16

[24]   Sobron, I., et al. (2017) Wireless Network Optimization for Massive V2I Data Collection using Multi-Objective Harmony Search Heuristics. In: International Conference on Harmony Search Algorithm, Springer, Singapore. https://doi.org/10.1007/978-981-10-3728-3_20

[25]   Del Ser, J., et al. (2012) Centralized and Distributed Spectrum Channel Assignment in Cognitive Wireless Networks: A Harmony Search Approach. Applied Soft Computting, 12, 921-930.

[26]   Manjarres, D., et al. (2013) On the Design of a Novel Two-Objective Harmony Search Approach for Distance- and Connectivity-Based Localization in Wireless Sensor Networks. Engineering Applications of Artificial Intelligence, 26, 669-676.

[27]   Handy, M., Hasse, M. and Timmermann, D. (2002) Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster Head Selection. Mobile and Wireless Communications Network, 9-11 September 2002, 368-372.

[28]   Hong, L. and Li, L. (2007) A Novel Hybrid Particle Swarm Optimization Algorithm Combined with Harmony Search for High Dimensional Optimization Problems, Intelligent Pervasive Computing. The International Conference on IPC, Jeju City, 11-13 October 2007, 94-97.

 
 
Top