Training and Learning Swarm Intelligence Algorithm (TLSIA) for Selecting the Optimal Cluster Head in Wireless Sensor Networks
Research Areas : Wireless Network
Ali Sedighimanesh
1
Hessam Zandhessami
2
Mahmood Alborzi
3
mohammadsadegh Khayyatian
4
Keywords: Hierarchical routing, TLBO algorithm, TS algorithm, wireless sensor network,
Abstract :
Background: Wireless sensor networks include a set of non-rechargeable sensor nodes that interact for particular purposes. Since the sensors are non-rechargeable, one of the most important challenges of the wireless sensor network is the optimal use of the energy of sensors. The selection of the appropriate cluster heads for clustering and hierarchical routing is effective in enhancing the performance and reducing the energy consumption of sensors. Aim: Clustering sensors in different groups is one way to reduce the energy consumption of sensor nodes. In the clustering process, selecting the appropriate sensor nodes for clustering plays an important role in clustering. The use of multistep routes to transmit the data collected by the cluster heads also has a key role in the cluster head energy consumption. Multistep routing uses less energy to send information. Methods: In this paper, after distributing the sensor nodes in the environment, we use a Teaching-Learning-Based Optimization (TLBO) algorithm to select the appropriate cluster heads from the existing sensor nodes. The teaching-learning philosophy has been inspired by a classroom and imitates the effect of a teacher on learner output. After collecting the data of each cluster to send the information to the sink, the cluster heads use the Tabu Search (TS) algorithm and determine the subsequent step for the transmission of information. Findings: The simulation results indicate that the protocol proposed in this research (TLSIA) has a higher last node dead than the LEACH algorithm by 75%, ASLPR algorithm by 25%, and COARP algorithm by 10%. Conclusion: Given the limited energy of the sensors and the non-rechargeability of the batteries, the use of swarm intelligence algorithms in WSNs can decrease the energy consumption of sensor nodes and, eventually, increase the WSN lifetime.
[1] A. Belfkih, C. Duvallet, and B. Sadeg, “A survey on wireless sensor network databases,” Wirel. Networks, vol. 25, no. 8, pp. 4921–4946, 2019.
[2] M. Sedighimanesh* and H. Z. and A. Sedighimanesh, “Presenting the Hybrid Algorithm of Honeybee - Harmony in Clustering and Routing of Wireless Sensor Networks,” International Journal of Sensors, Wireless Communications and Control, vol. 9, no. 3. pp. 357–371, 2019.
[3] A. Kochhar, P. Kaur, P. Singh, and S. Sharma, “Protocols for wireless sensor networks: A survey,” Journal of Telecommunications and Information Technology. 2018.
[4] Z. Ullah, “A Survey on Hybrid, Energy Efficient and Distributed (HEED) Based Energy Efficient Clustering Protocols for Wireless Sensor Networks,” Wirel. Pers. Commun., vol. 112, no. 4, pp. 2685–2713, 2020.
[5] A. Shahraki, A. Taherkordi, Ø. Haugen, and F. Eliassen, “Clustering objectives in wireless sensor networks: A survey and research direction analysis,” Comput. Networks, vol. 180, p. 107376, 2020.
[6] S. A. Susan T and B. Nithya, “Cluster Based Key Management Schemes in Wireless Sensor Networks: A Survey,” Procedia Comput. Sci., vol. 171, pp. 2684–2693, 2020.
[7] P. Sarzaeim, O. Bozorg-Haddad, and X. Chu, “Teaching-Learning-Based Optimization (TLBO) Algorithm BT - Advanced Optimization by Nature-Inspired Algorithms,” O. Bozorg-Haddad, Ed. Singapore: Springer Singapore, 2018, pp. 51–58.
[8] M. Gendreau, “An Introduction to Tabu Search,” in Handbook of Metaheuristics, 2006.
[9] U. E. Zachariah and L. Kuppusamy, “A hybrid approach to energy efficient clustering and routing in wireless sensor networks,” Evol. Intell., 2021.
[10] F. Fanian and M. K. Rafsanjani, “Cluster-based routing protocols in wireless sensor networks: A survey based on methodology,” J. Netw. Comput. Appl., vol. 142, pp. 111–142, 2019.
[11] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks,” System Sciences, 2000. Proceedings of the 33rd Annual Hawaii International Conference on. p. 10 pp. vol.2, 2000.
[12] M. Shokouhifar and A. Jalali, “A new evolutionary based application specific routing protocol for clustered wireless sensor networks,” AEU - Int. J. Electron. Commun., vol. 69, no. 1, pp. 432–441, Jan. 2015.
[13] M. Khabiri and A. Ghaffari, “Energy-Aware Clustering-Based Routing in Wireless Sensor Networks Using Cuckoo Optimization Algorithm,” Wirel. Pers. Commun., vol. 98, no. 3, pp. 2473–2495, 2018.
[14] P. K. Roy, C. Paul, and S. Sultana, “Oppositional teaching learning based optimization approach for combined heat and power dispatch,” Int. J. Electr. Power Energy Syst., 2014.
[15] W. Shao, D. Pi, and Z. Shao, “An extended teaching-learning based optimization algorithm for solving no-wait flow shop scheduling problem,” Appl. Soft Comput. J., 2017.
[16] X. Wang, L. Wang, and Y. Wu, “An Optimal Algorithm for Prufer Codes,” JSEA, vol. 2, pp. 111–115, Jan. 2009.
http://jist.acecr.org ISSN 2322-1437 / EISSN:2345-2773 |
Journal of Information Systems and Telecommunication
|
Training and Learning Swarm Intelligence Algorithm (TLSIA) for Selecting the Optimal Cluster Head in Wireless Sensor Networks |
Ali Sedighimanesh1, Hessam Zandhessami1*, Mahmood Alborzi1, Mohammadsadegh Khayyatian2
|
1.Department of Management and Economics, Science and Research branch, Islamic Azad University, Tehran, Iran 2.Institute for science and technology studies, shahid Beheshti university, Tehran, Iran |
Received: 28 Nov 2020 / Revised: 29 Apr 2021/ Accepted: 29 May 2021 |
Abstract
Background: Wireless sensor networks include a set of non-rechargeable sensor nodes that interact for particular purposes. Since the sensors are non-rechargeable, one of the most important challenges of the wireless sensor network is the optimal use of the energy of sensors. The selection of the appropriate cluster heads for clustering and hierarchical routing is effective in enhancing the performance and reducing the energy consumption of sensors. Aim: Clustering sensors in different groups is one way to reduce the energy consumption of sensor nodes. In the clustering process, selecting the appropriate sensor nodes for clustering plays an important role in clustering. The use of multistep routes to transmit the data collected by the cluster heads also has a key role in the cluster head energy consumption. Multistep routing uses less energy to send information.
Methods: In this paper, after distributing the sensor nodes in the environment, we use a Teaching-Learning-Based Optimization (TLBO) algorithm to select the appropriate cluster heads from the existing sensor nodes. The teaching-learning philosophy has been inspired by a classroom and imitates the effect of a teacher on learner output. After collecting the data of each cluster to send the information to the sink, the cluster heads use the Tabu Search (TS) algorithm and determine the subsequent step for the transmission of information. Findings: The simulation results indicate that the protocol proposed in this research (TLSIA) has a higher last node dead than the LEACH algorithm by 75%, ASLPR algorithm by 25%, and COARP algorithm by 10%.
Conclusion: Given the limited energy of the sensors and the non-rechargeability of the batteries, the use of swarm intelligence algorithms in WSNs can decrease the energy consumption of sensor nodes and, eventually, increase the WSN lifetime.
Keywords: Hierarchical Routing; TLBO Algorithm; TS Algorithm; Wireless Sensor Network.
1- Introduction
The wireless sensor network consists of several non-rechargeable sensor nodes applied for particular purposes [1]. One of the most important issues and challenges related to wireless sensor networks is the use of methods to reduce the energy consumption of sensor nodes. One of the methods is the clustering of the sensor nodes; instead of the sensor nodes consuming a great deal of energy and transmitting the data directly to the sink, they fall into a group called the cluster and send the data to the cluster head, and the cluster heads are required to transmit the data, thus consuming less energy of the sensor nodes and extending the network’s lifetime [2]. Cluster heads can either send the received data directly to the sink or work together to send the data to the sink in a hierarchical routing process. In general, transmitting data hierarchically reduces the energy consumption of cluster heads farther from the sink [3],[4].
The process of selecting cluster heads from available sensors and the routing between clusters to transmit data to the sink are of the optimization issues; therefore, the use of optimization algorithms has an effective role in the proper performance of these two processes, and ultimately, the efficiency of the wireless sensor network [5],[6]. Teaching-Learning-Based Optimization (TLBO) algorithm is one of the modern intelligent optimization algorithms implemented in two stages (phases) and can lead to optimization through being inspired by the learning and teaching process. In the teaching phase, the best member of the community is selected as the teacher and directs the average population towards himself/herself; this is similar to what a teacher does in the real world. In the learning phase, the people in the population work together to increase their knowledge, and it is similar to what happens in the company of friends and classmates [7].
The Tabu Search (TS) [8] algorithm is also one of the most powerful algorithms for solving optimization problems, especially graph-based and combinatorial optimization problems. The TS algorithm applies a list named the taboo list, which has been designed to prevent the algorithm from falling at the local optimal point. In summary, TS starts from a point or solution and searches for neighbors around that point, chooses the best neighbor and moves to that point, and continues this search until a stopping criterion to be satisfied. The optimal point is reported at the end of the search.
In the present article, the TLBO swarm intelligence algorithm is applied to select the appropriate cluster heads from the available sensor nodes. Once the cluster heads are identified, the members of each cluster become the member of the nearest cluster head and send the data to their cluster heads. The cluster heads receive data from their members and process and aggregate them subsequently. Then, the TS algorithm is used to transmit data to the sink by cluster heads until the best routes are formed for sending data, which reduces the energy consumption of cluster heads to transfer data. The rest of the article is structured as follows. Section 2 presents the previous work. Section 3 addresses the Proposed algorithm. Section 4 discusses the findings of the article. In Section 5, the authors present open problems for wireless sensor networks, and also the results are presented.
In this research, we will address several routing protocols that have attracted interest in recent years, namely the following: LEACH, ASLPR, and COARP[9][10].
2-1- Low- Energy Adaptive Clustering Hierarchy (LEACH)
In the LEACH protocol [11], there is a probability P for each sensor to be a cluster head (CH) in every round. In other words, LEACH creates groups using a distributed algorithm, in which the sensors automatically decide to become a cluster head and there is no centralized control. Each sensor can be a cluster head only once in 1/P consecutive rounds. First, each sensor makes a decision with a probability of P to become a cluster head. The cluster head roles changes in rounds between the group nodes, and this is to create an equilibrium in the energy consumption distribution. One can divide the performance of LEACH in each round into two phases. These phases are the setup and steady-state phases. A random number between 0 and 1 is chosen by every sensor in the setup phase. If that number is smaller than T(n), the sensor n becomes a CH for that round. The value of T(n) is computed based on (1), where P is the tendency of the sensor to be a node, and r represents the round number. Moreover, G denotes the set of all sensors that have not been chosen as a cluster head during the last 1/P rounds.
| (1) |
After the cluster heads are selected, they are announced to all the sensors in the network as cluster heads. When non-cluster head sensor receives an announcement from the cluster heads, it selects the cluster head closest in terms of communication.
2-2- Application- Specific Low Power Routing (ASLPR) protocol
The ASLPR protocol [12] collects specific pieces of information, such as remaining energy, distance from the base station, and distance between the CHs and sensor node, to select the cluster head nodes. Then, each node selects a random number between zero and 1. If the random number selected by a node is less than in (2), this node is converted to a cluster head.
| (2) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (3) |
| (4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (5) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (6) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (7) |
TLSIA Algorithm |
Select nodes in sensing area for clustering 1 CHs= TLBO 2 For i=1: number of nodes 3 If node(i) is in sensing area && node(i) is normal node 4 node(i) joins to nearest CH 5 end if 6 end for Routing to send cluster head information 7 Route= TS 8 For i= Cluster heads 9 CH(i) joins to route; 10 end for |
3-1- Node Distribution and Sink Location
During the simulation, the sensor nodes are randomly distributed in an environment. Then, the location of the sink is determined, which is usually outside the environment.
Fig. 1. Random distribution of the nodes in the environment
The process of choosing the optimal cluster heads from between the sensors in the network is performed using the Teaching-Learning-Based Optimization (TLBO) algorithm. The teaching-learning philosophy has been inspired by a classroom and imitates a teacher’s effect on the learner output. Similar to other swarm intelligence algorithms, the TLBO algorithm is a population-based evolutionary optimization algorithm and consists of a teaching phase and a learner phase.
In the teaching phase, the teacher has the main role and attempts to transfer their knowledge to all the learners in the classroom to increase the average score. The average result of the learners and the improvement in results completely depends on the teacher. In each step, the best learner in the population is selected as the teacher, and, accordingly, the cost function and the average position for improving the position of the learners are computed.
In the learning phase, the learners increase their knowledge either via the teacher or via interacting with each other. The main difference between the teaching and learning phases is that in the teaching phase, the teacher transfers the knowledge to the learners, but in the learning phase, the learners gain knowledge from the teacher and by communicating with each other. In population-based optimization methods, a population has a set of members, each of which has a number of variables. Every member of the population is a solution to the optimization problem. In this paper, we first form an initial population consisting of a number of members, named learners, to determine the cluster head. Each learner includes 2 variables: Position, which consists of a string of variables, and cost. The figure below shows an overview of a population.
Learner 01 | Position | Node 01 | Node 02 | Node 03 | …. | Node (n-1) | Node (n) |
Cost | |||||||
Learner 02 | Position | Node 01 | Node 02 | Node 03 | …. | Node (n-1) | Node (n) |
Cost | |||||||
. | |||||||
. | |||||||
. | |||||||
Learner 0N | Position | Node 01 | Node 02 | Node 03 | …. | Node (n-1) | Node (n) |
| Cost |
Fig. 2. Overview of a population
First, the variables inside the position are given a random value between 0 and 1 (0 ≤ Position (i) ≤ 1). The most important issue in optimization algorithms is how to determine the cost for the learners in the population. In this paper, the cost is equal to (8):
(8)
In the above formula, x is the variable inside the population member, RE is the remaining energy of each variable, density is the ratio of the number of neighbors to the total number of nodes, centrality is the sum of distances of the nodes from the neighbors, Beta= -0.3, Alpha= -0.5, and Gamma=0.2.
In the TLBO method, every member of the population is considered a learner. In every iteration of the TLBO algorithm, we select the member with the lowest cost between the population members as the best member of the population. Then, we sort the variables inside the selected member in descending order and select 10% of these variables as the optimal cluster head. For example, if after the end of the maximum iteration of the algorithm, the output is as follows:
|
| 01 | 02 | 03 |
| n-1 | n |
Learner 01 | Position | 0.36 | 0.47 | 0.25 | …. | 0.12 | 0.22 |
Cost= -1.25 | |||||||
Learner 02 | Position | 0.26 | 0.17 | 0.45 | …. | 0.32 | 0.52 |
Cost=-1.35 | |||||||
. . . | |||||||
Learner N | Position | 0.14 | 0.32 | 0.54 | …. | 0.33 | 0.63 |
Cost=-1.05 |
Learner 02 is selected as the best member of the population; hence, the variables inside this member are sorted in descending order, and 10% of them are considered as the cluster head.
In implementing the TLBO algorithm, 3 values have a vital role in the optimal performance of the algorithm: (1) initialization of the learners, (2) updating of the teaching phase, and (3) updating of the learning phase.
Learner initialization: In this method, we first create a random population and calculate the second population from the first using (9). Subsequently, we combine the 2 populations and compute and sort the costs of the learners. Then, we select from the learners with less cost a number equal to the learner members of the population[14], [15].
Fig. 3. Opposition-based learning and quasi-oppositional learning[15].
| (9) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (10) |
| (11) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (12) |
| (13) |
where newXi is the ith learner’s position, represents the learners chosen randomly from the class, and
and
respectively denote the fitness values of the learners
and
. In addition, rand denotes a random vector in the [0, 1] range.
TLSIA Clustering Algorithm |
1 Initialize learners; 2 Evaluate learners; 3 For all learners 4 For i=each dimension 5 6 7 End_For 8 End_For 9 Combine first population and Quasi-opposite population; 10 Select best learners as new population; 11 Xteacher=best learner; 12 Xmean=average of learners; 13 While (stopping condition is not met) 14 For i=all learners 15 TF = round (1 + rand (0,1)); 16 Xnewi=Xi+rand*(Xteacher-TF*Xmean); 17 End_For 18 Evaluate new learners; 19 If new learner is better than old one 20 Xi=Xnewi; 21 End_If 22 For i=all learners 23 Randomly select another learner which is different from i (Xk); 24 If Xi is better than Xk 25 Xnewi=Xi+rand*(Xi-Xk); 26 Else 27 Xnewi=Xi+rand*(Xk-Xi); 28 End_If 29 End_For 30 If new learner is better than existing 31 Xi=Xnewi; 32 End_If 33 Xteacher=best learner; 34 Xmean=average of learners; 35 End_While |
Solution | Position | Node 01 | Node 02 | Node 03 | …. | Node (n-1) | Node (n) |
Cost |
In the TS algorithm, a number of actions are performed on the solution variables so as to optimize the solution cost. These actions are reversion, swap, and insertion.
To optimize routing using the TS algorithm, we use the Prüfer algorithm [16] to create a tree between the cluster head nodes. This algorithm maps a sequence of numbers to the corresponding tree.
First, we create a solution that assigns a random number between 0 and 1 to each position variable. Then, the solution cost is computed. To calculate the cost of each solution, we first convert it to the corresponding tree using the Prüfer algorithm. Then, the routing is performed according to the obtained tree, and the cost is calculated from (14). E1 is the network energy before applying the routing, and E2 is the computed energy after applying the routing.
| (14) |
| (15) |
|
| 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
Solution | Position | 0.37 | 0.26 | 0.88 | 0.76 | 0.44 | 0.55 | 0.45 | 0.35 | 0.25 |
Cost= 2 |
For the cost, we first convert this position into integers and obtain the corresponding array 5 4 10 9 5 7 6 5 4. This array is given to the Prüfer algorithm, and an equivalent tree is created. The cost is equal to the energy consumption of the cluster heads during the transmission of information to the sink according to this tree and route, and we seek to reduce the cost of the problem solution. After the initial solution is known, the desired actions are applied according to the obtained solution and the position and cost of the optimal solution are obtained. if a lower cost results, it replaces the best solution, and the action is not performed for a specific amount of time. This is continued until the cost is optimized. Finally, the obtained solution is converted to a tree via the Prüfer algorithm, which represents our optimal route.
TLSIA Routing Algorithm |
1 Create initiate solution; 2 Sbest=best solution; 3 While (stopping condition is not met) 4 Generate candidate solutions in the neighborhood of Sbest 5 For i=candidate solutions 6 If candidate_i is not in TabuList 7 If candidate_i is better than bestnewsol 8 Bestnewsol=candidate_i 9 End_If 10 End_If 11 End_For 12 If bestnewsol is better than Sbest 13 Sbest= bestnewsol 14 End_If 15 Push the bestnewsol to TabuList 16 If TabuListSize>maxTabuListSize 17 Remove the first element from TabuList; 18 End_If 19 End_While |
3-4- Network Operations and Energy Consumption Computation
The network operations in the proposed algorithm are divided into start-up and register phases. The energy consumption of every node in each round is computed by examining what has occurred in both phases.
3-4-1- Start-up Phase
The sink uses the control packet to communicate with the sensor nodes. These
control packets contain short messages that request the ID, position, and the level of energy from each of the sensor nodes. The energy
is consumed in the process of receiving the control packets from the sink according to (16). Moreover, all the nodes utilize the energy
to transfer to the sink the control packets that contain data relating to the IDs, positions, and levels of energy.
| (16) | ||
| (17) |
| (18) |
| (19) |
| (20) |
Parameter | Value |
Population or Learner | 50 |
Number of iterations | 100 |
Number of Variables | length (Alive Nodes) |
Variables Lower Bound | VarMin= 0 |
Variables Upper Bound | VarMax=1 |
Table 2: Adjusting the parameters of the TS algorithm
Parameter | Value |
Population or Solution | 1 |
Number of iterations | 100 |
Number of Variables | Nch-1 (Nch= Number of Cluster Head) |
Variables Lower Bound | VarMin= 0 |
Variables Upper Bound | VarMax=1 |
NAction | NSwap+NReversion+NInsertion |
NSwap = NReversion | N × (N-1)/2 |
NInsertion | N × N (N=Number of position variables) |
Table 3: Simulation parameters
Parameter | Value |
Initial energy of the nodes | 1j |
| 10 (pj/bit/m2) |
| 0.0013 (pj/bit/m4) |
Eelec | 50 (nJ/bit) |
Eda | 5 (nJ/bit) |
Data packet size | 4100 (bit) |
In this section, the authors take into account eight scenarios according to Table (4) to evaluate the proposed algorithm. The number of sensors, the size of the environment, and the sink location are the parameters investigated in these scenarios to evaluate the algorithms in which the parameters change in each scenario.
Table 4: Used scenarios
Number | Number of sensors | Network size | Sink location |
1 | 100 | 200m × 200m | (100m, 250m) |
2 | 100 | (250m, 550m) | |
3 | 200 | 200m × 200m | (100m, 250m) |
4 | 200 | 500m × 500m | (250m, 550m) |
5 | 500 | 200m × 200m | (100m, 250m) |
6 | 500 | 500m × 500m | (250m, 550m) |
7 | 2000 | 200m × 200m | (100m, 250m) |
8 | 2000 | 500m × 500m | (250m, 550m) |
According to Table (4), the scenarios are simulated in two environments of sizes 200m×200m, and 500m×500m and the number of sensor nodes 100, 200, 500, and 2000, and their results are analyzed. Three factors are investigated in these scenarios: 1) the number of live nodes, 2) energy consumption of the network, 3) packets sent to the sink in each round.
Fig. 4. Number of live nodes in each round in the first scenario.
According to the results obtained in Figure (4) in the first scenario, FND1, HND2 and LND3 in the proposed algorithm are better compared to other approaches and indicates that in the Proposed algorithm, the energy consumption of sensors in each round is less than other methods. In Figure (5), the network’s lifetime has been compared; in the Proposed algorithm, the networks’ lifetime has increased compared to other methods, which shows the proper performance of the proposed algorithm in clustering and data transmission.
Fig. 5. Network’s energy consumption in each round in the first scenario.
Fig. 6. Packets sent to the sink in each round in the first scenario.
In the simulations, the higher the number of intact packets sent to the sink, the better the performance of the sensor nodes and cluster heads, which leads to an increase in the performance of the wireless sensor network. As shown in Figure (6), in the Proposed algorithm, the number of packets sent to the sink in each round is more than other methods, which indicates the proper performance of the sensor nodes and cluster heads within the wireless sensor network in the TLSIA method.