2018 International Conference on Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 227 978-1-5386-6696-8/18/$31.00 ©2018 IEEE Maintain Load Balancing in Wireless Sensor Networks Using Virtual Grid Based Routing Protocol Husam Kareem Directorate of Baghdad Education, Karkh 3 Ministry of Education of Iraq Baghdad, Iraq husam.kar@gmail.com Hadi Jameel Department of Computer Techniques Engineering AL-Mustafa University College Baghdad, Iraq hjhk8891@gmail.com Abstract— Based on the wide variety of applications of wireless sensor networks (WSNs) in different aspects of life, research focusing on WSNs have rapidly increased in the recent few years. Different challenges shorten the operation of sensor nodes over the targeted area for different reasons such as danger, inhospitality, and limited energy resources of the surrounding area. One major issue is the energy required to operate the individual sensor nodes that definitely affect the operation of the entire sensor network. Accordingly, energy consumption must be minimized as possible which requires to compromise sensor network activities as well as network operation. One fundamental solution commonly used for minimizing the energy consumption in each sensor node is using an energy-efficient routing algorithm. In this study, a routing approach depends on the grid topology of the sensor network is presented to maximize the lifetime of WSNs via balancing a load of data traffic among sensor nodes as evenly as possible. The evaluation process is done using CFDASC routing protocol since it represents the most comparable and related algorithm among previous work. Simulation results prove that the presented approach outperformance CFDASC algorithm in terms of network stability and load balancing of the entire network. Keywords—grid-based, wireless sensor network, cell-head, load balancing, the stability period I. INTRODUCTION Generally, a number of spatially distributed sensor nodes each of which contains four major units: a power source, processor, transceiver, and sensor constructs a wireless sensor network [1]. Furthermore, Wireless sensor networks could be utilized in numerous applications such as, sensing and collecting information from the physical environment that usually unable to reach by humans. Thus, in such conditions, sensor nodes are required to survive for a longest possible time at the concerning zone. An essential issue that highly probable to challenge the survival of sensor nodes is the limited resources specifically power source (usually small battery). Therefore, when the power source (battery) is depleted the network will be losing sensor nodes continually and it is difficult to replenish died sensors [2]. The reasons that sensor nodes characterized by such feature is that sensor nodes are basically static. Moreover, in regular conditions, sensor nodes are delivered in an inhospitable area or placed in a physical structure that makes them left unattended. Therefore, energy consumption is a very critical factor that should be managed wisely to extend the network lifetime during the duration of time for the specified mission. Energy consumption in WSNs can be divided into three different reasons: processing, sensing and communications [3]. This research will be mainly focusing on the communication aspect since it consumes a great portion of the sensor nodes energy [3]. Specifically, the way that the sensor network collects the data from the sensing field and delivers that data to the base station. In other words, the routing algorithm that is used to transfer data within the sensor network (intra-network communications) and transfer the data from the sensor network to the base station (inter-network communications). Thus, using a routing algorithm that able to retain sensor network energy and provide an even energy consumption among all sensor nodes can be a perfect solution to keep an efficient and stable operation of WSNs as long as possible. Considering that sensor networks performance reaches its best when all sensor nodes are alive and functioning. If sensor nodes start dying, empty zones will appear and there will be a lack in the required sensing data, which leads the entire WSNs unreliable and insufficient. To settle the prior mentioned issue, we present a routing algorithm that pursues to prolong the lifetime of a balanced and stable WSNs called Virtual Grid Based (VGRP). The VGRP algorithm splits the area that involves sensor nodes into a grid of sub-cells with equal size then collects the sensed data using cluster and chain techniques. II. RELATED WORK Incalculable studies have been carried out to develop the approach of routing the sensed data of WSNs. Among the wide number of approaches, some relevant will be explored for either routing algorithms that aiming to achieve load balancing in WSNs or routing algorithms for grid-based structure WSNs. This is due to the proposed algorithm belongs to Grid-based hierarchical routing algorithms, and aims to achieve load balancing in WSNs. It is worth mentioning that hierarchical routing algorithms are classified into three main sets: clustering, chaining, and hybrid routing algorithms [4].
2018 International Conference on Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 228 EEGDG [5] is a grid-based routing algorithm that combines clustering and chain techniques which make it considered as hybrid routing algorithm. EEGDG algorithm presented to be an energy efficient and consequently, prolong the lifetime of wireless sensor networks by decreasing the hops happened in the standard chain routing algorithms like PEGASIS [6]. In spite of the fact that EEGDG algorithm could achieve its target by increasing the network lifetime but it did not make an optimal solution for the delay in data delivering that occur due to the long chain. An energy efficient load balancing algorithm (EELBC) presented in [7] depending on clustering to gain longer lifetime and load balanced WSNs. In this algorithm, it is assumed that each sensor node is equipped with a GPS unit in order to be aware of its position. EELBC works within two stages; bootstrapping and clustering. This algorithm successfully achieved longer lifetime and more load balanced wireless sensor network but its main flaw is when they assumed that there are supernodes to act as clusters heads which are less energy-constrained compared with other nodes in the network which act as clusters members. Therefore, this algorithm cannot be considered flexible or applicable for many applications since its complex assumptions that require optimal situations. GBDAS [8] divides the sensing field into a grid of cells, each cell consists of a number of sensor nodes. GBDAS algorithm operates in three phases; grid construction, chain formation, and data transmission. The fundamental objective of this algorithm is to decrease the number of dead nodes during the network lifetime. This algorithm collects the sensed data from by using a cell head for each individual cell the forming a very long chain that includes all cell heads in order to gather the sensed data for the entire network. After collecting the data within the chain, a chain head which already selected based on its residual energy will be responsible for sending the collected data to the base station. This algorithm can be considered as a successful algorithm for the applications that require a small sensing area since the chain of cell-heads will be not so long and consequently the delay in data gathering and delivering can be compromised with less energy consumption. In contrast, when the application requires a large sensing area, GBDAS will show a big delay in data gathering and delivery due to the very long chain of cell-heads. In the mobile sink scheme, a virtual grid based dynamic routes adjustment (VGDRA) is proposed to reduce the routes construction cost of sensor nodes [9]. This algorithm divides the sensing field into a number of uniform cells that depends on the total number of sensor nodes. To calculate the desired number of sub-cells and thus the number of cluster heads they utilize the same heuristics of the LEACH algorithm [10] which consider a 5% of the total number of sensor nodes. VGDRA algorithm uses the nodes that have the least distance to the center of each cell to operate as a cluster head. However the technique of selecting the cluster head at each cell can distribute energy consumption evenly among cluster members, it makes the nodes located near the cells centers die very quickly. Since the cluster head node consumes much more energy than the normal members due to receiving and aggregating data from all cluster members and then transmitting the aggregated data to other cluster head in the network. In addition to this issue, implementing a mobile sink approach is not convenient for most of the application. Enhanced chain-cluster based mixed routing algorithm (E- CCM) [11] has introduced to maximize the lifetime and minimize energy consumption of wireless sensor network. E- CCM operates based on grid topology and works within two stages; the initialization stage and transmission stage. E-CCM algorithm considered as hybrid hierarchical routing algorithm since it is built depending on chain and cluster techniques. This algorithm achieves its goals perfectly by outperforms the previous related work like the CCM algorithm [12]. Although the E-CCM algorithm can only function with a uniformly predetermined distribution of sensor nodes it is not designed to be applicable for applications that require a random distribution of sensor nodes. Based on the study of literature, it can be seen that majority of related work has focused on increasing the network lifetime without taking in consideration balance the load evenly among sensor nodes. Moreover, some of the previous algorithms used complex assumption like supernodes (nodes with unrestricted energy source). III. PROBLEM STATEMENT The architecture of wireless sensor network can be described as a set ‘S’ of nodes. We assume that each sensor node is aware of its location using a GPS unit. The goal of using hierarchical schemes; chain, cluster, and hybrid, is to create a virtual structure that facilitates and ease managing data routing in wireless sensor networks. One of the goals of hierarchical routing algorithms is load balancing among sensor nodes. Majority of Grid-based routing algorithms is directly or indirectly rely on clustering technique. The goal of clustering is to select a set of sensor nodes to be cluster heads that cover the whole network. The cluster head would be responsible for receiving and aggregating the sensed data from all cluster members and then forward the aggregated data either to the base station or to the next cluster head based on the routing mechanism. Therefore, the cluster head consumes more energy compared to the energy consumed by a normal cluster member. The problem of load balancing happens when a group of sensor nodes is repeatedly selected to operate as cluster heads. As a result, those nodes will die very fast and the death of nodes will cause empty gaps within the entire network. Those gaps not only can affect the validity of the sensed data but also can affect the communication of the WSNs which are mainly built upon multi-hop communication. Thus, the proposed algorithm aims to keep the load evenly distributed among sensor nodes which lead to retain all sensor nodes alive and functioning as long as possible. IV. VGRP SCHEME Here, will outline the characteristics of the proposed approach Virtual Grid Based routing protocol (VGRP) which aims to keep the robustness and validity of wireless sensor network as long as possible by balancing the load evenly
2018 International Conference on Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 229 among all sensor nodes. VGRP significance appears during the selection of the node that collects and aggregate data from other nodes to avoid overloading specific nodes rather than others. VGRP algorithm tried to achieve this goal by utilizing the factor of remaining energy of individual nodes to decide upon their selection of being a cluster or chain head. The closest related and highest comparable work like Chain-based fast data aggregation algorithm based on suppositional cells has gained a substantial performance in term of transmission delay [13]. However, the remaining energy of each sensor node that selected to act as a cluster or chain head has not taken into consideration. Therefore, a node with almost depleted energy might be selected to represent the head for a group of sensors while a node with much higher energy operates as normal member node that requires only a few amounts of energy to transmit its data to the group head. The proposed algorithm VGRP distribute the duty of being a group head (chain or cluster) by taking into consideration its remaining energy. The operation of the VGRP algorithm can be divided into two main stages; virtual grid setup and data transmission. A. Virtual Grid setup The network topology is initialized based on dividing the sensing field to a virtual grid topology with equal size cells. The field axes are equally divided and numbered according to the number of cells, which are located along each field-axis. For instance, if there are three cells on the x-axis, then the x- axis is numbered as 0, 1, 2 and if there are five cells then the coordinate will be numbered as 0, 1, 2, 3, 4 and so on. Therefore, the numbers on the x-axis can be considered as the column number while the numbers of the y-axis represent the row numbers. Fig. 1. Virtual grid construction Each cell within the grid has a unique cell ID called (CID). The group of sensor nodes that fall into a specific cell can determine its unique cell-ID based on (1). CID = [Cx, Cy] () Where Cx and Cy represent the cell coordinates on the x- axis and y-axis respectively. Fig.1 clarifies an example of sensing field divided into a virtual grid of 5 × 5 equal cells. For instance, the IDs for the first row and from left to right IDs will be [0,0], [1,0], [2,0], [3,0], [4,0] and so on so forth. B. Head nodes selection and data transmission In order to collect, aggregate, and send the sensed data to the base station, nodes called cell-heads and chain heads act as an intermediary between the non-head nodes and the base station. At the first sensing round, all nodes have the same energy hence cell-head nodes will be randomly selected. Then, during the next sensing rounds, the node that has the maximum residual energy will be functioning as the cell-head. After the data get collected in the cell-head nodes, a chain head is selected depending on the same basis of selecting the cell-head, which will be responsible for gathering the data vertically. The job of the head nodes is to collect the sensed data from its nodes, aggregate with its own data and then forward it either to the next head node using multi-hop communication or send it directly to the base station. The process of selecting cell-head nodes, forming a chain that consists of a set of cell-head nodes, and finally select a chain head for each individual chain is accomplished by the base station. In VGRP algorithm, data transmission is done in steps; within the individual cells (intra-cell data transmission) based on clustering technique and between the cell-heads (inter-cell data transmission) based on chain technique. Therefore, there will be two types of head nodes which are cell-head and chain head nodes. Fig.2 shows the flowchart of virtual-grid setup process as well as the intra-cell communications. Fig. 2. Flowchart of virtual-grid setup and the intra-cell communications Intra-Cell Communications: The main structure of the VGRP algorithm is to divide the sensing area to a virtual grid with equal size cells. After constructing the grid and assigning each sensor node to its corresponding cell, a cell head for each group of nodes that belong to the same cell is selected based on its remaining energy. The cell head takes charge of
2018 International Conference on Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 230 gathering the sensed data packets from all non-head nodes that belong to the same cell then aggregate it with its own data and then forward it to the next cell-head node based on multi-hop communications. Fig.3 illustrates network structure after forming the grid of cells and selecting a head node for each individual cell. Fig. 3. Intra-cell communications Inter-Cell Communications: When all data packets are collected within the cell-head nodes, those head nodes will form a chain that includes all cell-heads that fall in the same column. Nodes with maximum remaining energy take the role of being chain head of their respective chains. Data transmission is done using the greedy algorithm like in pegasis [6]. Each sensor node sends its own data packet to its neighbor node (adjacent sensor node toward the chain head). The neighbor node receives the data packet and aggregates it with its own data packet then transmits it to its neighbor and so on so forth till data are all collected in the chain head node. After that, the chain head receives its neighbors' data, aggregates it with its own data and then forwards it to the base station. Fig.4 clarifies the procedure of this process while Fig.5 is a flowchart that demonstrates the vertical chains formation and the inter-cell communications. Fig. 4. Inter-cell communications Fig. 5. Flowchart of vertical chains formation and inter-cell communications V. NETWORK MODEL The sensing field is represented by a 2-D area which is equally partitioned into identical size cells. The base station is fixed and placed outside, far from the sensing field. 50 and 100 sensor nodes respectively are distributed randomly over the sensing area. In order to give comprehensive details about network system model, it is divided into two main sections that include the basic assumptions used in the simulation software and energy model utilized to determine energy consumption due to the transmitting of data packets. A. Basic Assumptions A number of basic assumption must be decided before proceeding with the simulation. • All nodes have awareness of their geographical location based on GPS unit. • All nodes are immobile after the deployment. • All nodes are of homogeneous energy (all nodes contains the same initial energy) [14]. • Each sensor node is aware of its remaining energy. • The amount of energy consumption due to data transfer from point X to point Y is the same as when the transfer is from point Y to point X. • Energy consumption due to aggregation of data packets is equal to 5nJ/bit/packet [15]. For the first assumption, it is assumed that each sensor node is aware of its location to help the sensor nodes to determine the cell that they belong to and then organize themselves into clusters within the corresponding cells. As the second
2018 International Conference on Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 231 assumption, the vast majority of wireless sensor networks applications require stationary sensor nodes [16]. For the simplicity of the simulation process, sensor nodes are assumed homogeneous. Moreover, sensor nodes are aware of their remaining energy and the location of the base station, then the remaining energy factor can be utilized to make the decision of choosing the cell-head nodes and later the decision of choosing chain-head nodes. B. Energy Model In order to evaluate the consumption of energy due to data transmission and receive, the first order radio transceiver is used in this design [6], [11], [16], [17]. Equations (2) and (3) are used to determine the energy cost due to data receiving and due to data transmitting respectively. Energy consumption due to data receiving Erx(k)= Eelec × k () Energy consumption due to data transmission ETx(k, d)= Eelec × k + Eamp × k × d  () Where Eelec represents the energy required to run the transmitter or the receiver, k represents the size of data packets, Eamp stands for the amount of consumed energy to run the amplifier, and d is the distance of transmission. Moreover, there are some fixed parameters used through the simulation process which is shown in Table I. TABLE I. SIMULATION PARAMETERS Simulation parameters Subhead Area of the sensing field (50×50) m2 & (100×100) m2 Basic station location (25,75) & (50,150) Number of sensor nodes 100 Sensor node's initial energy 0.5 Joule Eele 50 nJ/bit Eamp 100 pJ/bit/m2 Data packet size 2000 bit VI. RESULTS AND ANALYSIS VGRP and CFDASC performance are evaluated based on two crucial performance metrics; load balancing, and network stability. A. Load Balancing The load balancing metric represents the proportion of the residual energy of the entire network when the first node dies. The performance of network evaluated based upon this metric has an inverse relationship which means that the network with minimum residual energy when the first node dies is the network that shows the best load balancing [17], [18]. In other words, when the first node of a network dies and the network only has a few portions of the remaining energy. Consequently, it means that the rest of all alive nodes have reached to the minimum amount of energy that makes them alive. In addition, it also means that they are almost dead not in the same round of the first node but might die the next round or after a few rounds (in maximum). Based on the above explanation, we can see that when all nodes die at the same time or even at very close period just because they consumed the same amount of energy during their operation. Which also means that each sensor node in the network has a burden of almost the same amount of a load of data packets traffic. The total residual energy of the entire network when the first node dies using (50 × 50) m2 & (100 × 100) m2 sensing area is shown in Table II and Table III respectively. The routing algorithm with the lowest parameter has the best performance in term of load balancing [17], [18]. TABLE II. TOTAL REMAINING ENERGY WHEN FIRST NODE DIES USING (50×50) M2 SENSING AREA Routing algorithm Total remaining energy (Joule) Percentage of remaining energy VGRP 10.4 20.8% CFDASC 22 44% TABLE III. TOTAL REMAINING ENERGY WHEN FIRST NODE DIES USING (100×100) M2 SENSING AREA Routing algorithm Total remaining energy (Joule) Percentage of remaining energy VGRP 16.92 33.84% CFDASC 29.62 59.24% It can be clearly seen that the proposed algorithm VGRP outperforms CFDASC algorithm in term of load balancing in both (50 × 50) m2 & (100 × 100) m2 sensing area. B. Stability period Stability period of wireless sensor network represents the period of time starting from the first sensing round till the death of the first sensor node [17], [18]. Therefore, without long-term stability period, more data could not be gathered from the sensing field even if the network lifetime is high. Because of that, extending the stability period is crucial for many applications of wireless sensor networks. Fig.4 shows the stability period of the sensor network using (50 × 50) m2 & (100 × 100) m2 sensing area respectively. Fig. 6. Stability period using different sensing area
2018 International Conference on Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 232 As demonstrated in Fig.6, VGRP algorithm shows better performance in term of network stability period using different sensing area. The improvement of VGRP over CFDASC algorithm is almost 40.3% using (50 × 50) m2 sensing area while it is about 51.5% using (100 × 100) m2 . Equation (4) is used to determine the percentage of improvement VGRP over CFDASC algorithm [11]. POI = (Second Value-First Value)/First Value×100% () Where POI stands for the percentage of improvement, hence, in this performance metric, it shows the improvement percentage in network stability period. The First value refers to the sensing round when the first node dies using CFDASC algorithm. Second value stands for the sensing round when the first node dies using VGRP algorithm. VII. CONCLUSION AND FUTURE WORK In this research, a Virtual Grid-Based routing protocol (VGRP) has presented to maintain load balancing and increase stability period of wireless sensor networks. VGRP algorithm divides the sensing area to a grid of cells then treat each cell as an independent cluster. It works within two stages; virtual grid setup and data transmission. In addition, a sensor node, which has maximum remaining energy, is selected to function as a cluster head during intra-cell data transmission and inter-cell data transmission. The evaluation process is done through a simulation program using area (50×50) m2 & (100×100) m2 respectively to check the validity of the proposed algorithm with different sensing area. Simulation results show that VGRP algorithm outperforms CFDASC algorithm in both performance metrics utilized in this study; network load balancing and network stability period. Moreover, in term of stability period, VGRP algorithm shows an improvement over CFDASC algorithm about 40.3% and 51.5% using (50×50) m2 and using (100×100) m2 sensing areas respectively. As part of our future work will try to implement the proposed algorithm in real-life applications, specifically, in home automation systems that involve sensors in their operations [19]. In addition, the performance of the proposed algorithm will be investigated using other performance metrics such as end-to-end delay and network throughput. Moreover, different communication approaches will be explored such as Zigbee and LiFi technologies [20] REFERENCES [1] V. C. Gungor and G. P. Hancke, "Industrial Wireless Sensor Networks: Challenges, Design Principles, and Technical Approaches," in IEEE Transactions on Industrial Electronics, vol. 56, no. 10, pp. 4258-4265, Oct. 2009. [2] Liang, F., et al., "Study on the Rough-set-based Clustering Algorithm for Sensor Networks", Bulletin of Electrical Engineering and Informatics, Vol.3, no.2, pp.77-90, June 2014. [3] J.Y.Choi, et al., "Cell-based energy density-aware routing: a new protocol for improving the lifetime of wireless sensor networks." Computer Communications, vol. 28, no. 11, pp. 1293-1302, Dec. 2005. [4] H.Kareem, et al., "A Survey of State of the Art: Hierarchical Routing Algorithm for Wireless Sensor Networks." Journal of Theoretical & Applied Information Technology vol.62, no.3, pp.769-781, April 2014. [5] Y. F. Huang, et al., "An efficient energy data gathering based on grid- chain for wireless sensor networks," 4th International Conference on Awareness Science and Technology, Seoul, 2012, pp. 78-82. [6] S. Lindsey and C. S. Raghavendra, "PEGASIS: Power-efficient gathering in sensor information systems," Proceedings, IEEE Aerospace Conference, 2002, pp. 3-1125-3-1130 vol.3. [7] P.Kuila, and P.K.Jana. "Energy efficient load-balanced clustering algorithm for wireless sensor networks." Procedia technology 6, pp.771- 777, Nov. 2012. [8] Wang, N. C., et al., "Grid-Based Data Aggregation for Wireless Sensor Networks", Journal of Advances in Computer Networks, vol.1, no.4, pp.329-333, Dec. 2013. [9] A. W. Khan, et al., "VGDRA: A Virtual Grid-Based Dynamic Routes Adjustment Scheme for Mobile Sink-Based Wireless Sensor Networks," in IEEE Sensors Journal, vol. 15, no. 1, pp. 526-534, Jan. 2015. [10] G. J. Pottie, and W. J. Kaiser, "Embedding the Internet: Wireless Integrated Network Sensors", Communications of the ACM, vol. 43, no. 5, pp. 51-58, 2000. [11] H.kareem "Enhanced Chain-Cluster Based Mixed Routing Algorithm for Wireless Sensor Networks" Journal of Engineering, vol.22, no.1, pp.103-117, Jan. 2016. [12] F. Tang, et al., "A chain-cluster based routing algorithm for wireless sensor networks", Journal of intelligent manufacturing, vol. 23, no. 4, pp. 1305-1313, may 2012. [13] Hao Wu, et al., "A Chain-based Fast Data Aggregation Algorithm Based on Suppositional Cells for wireless sensor networks," 2009 2nd International Conference on Power Electronics and Intelligent Transportation System (PEITS), Shenzhen, 2009, pp. 106-109. [14] Haseeb, K., et al. "Grid-based cluster head selection mechanism for the wireless sensor network." Telkomnika (Telecommunication Computing Electronics and Control), Vol.13, no.1, pp. 269-276, March 2015. [15] Marhoon, Haydar Abdulameer, et al. "Performance evaluation of CCM and TSCP routing protocols within/without data fusing in WSNs." Journal of Physics: Conference Series. Vol. 1032. No. 1. IOP Publishing, 2018. [16] Y. K. Chiang, et al., "Cycle-Based Data Aggregation for Grid-Based Wireless Sensor Networks," 2013 Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, Taichung, 2013, pp. 348-353. [17] H. Kareem, et al., "Energy Efficient Two-Stage Chain Routing Protocol (TSCP) for Wireless Sensor Networks," Journal of Theoretical and Applied Information Technology, vol. 59, pp. 442-450, Jan. 2014. [18] R. Sheikhpour and S. Jabbehdari, "A Cluster-Chain based Routing Protocol for Balancing Energy Consumption in Wireless Sensor Networks," International Journal of Multimedia & Ubiquitous Engineering, vol. 7, no. 2, pp. 1-16, April 2012. [19] H.Jameel, and H.kareem, "Low-Cost Energy-Efficient Smart Monitoring System Using Open-Source Microcontrollers." International Review of Automatic Control (IREACO), vol.9, no.6, pp. 423-428, Nov 2016. [20] Dr. Hussam Dheaa Kamel, Hadi Jameel Hadi, “The Characteristic of Li- Fi Technology Comparing with Wi-Fi” International Journal of Computation and Applied Sciences IJOCAAS, Volume2, Issue 2, April 2017.

Maintain load balancing in wireless sensor networks using virtual grid based routing protocol

  • 1.
    2018 International Conferenceon Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 227 978-1-5386-6696-8/18/$31.00 ©2018 IEEE Maintain Load Balancing in Wireless Sensor Networks Using Virtual Grid Based Routing Protocol Husam Kareem Directorate of Baghdad Education, Karkh 3 Ministry of Education of Iraq Baghdad, Iraq husam.kar@gmail.com Hadi Jameel Department of Computer Techniques Engineering AL-Mustafa University College Baghdad, Iraq hjhk8891@gmail.com Abstract— Based on the wide variety of applications of wireless sensor networks (WSNs) in different aspects of life, research focusing on WSNs have rapidly increased in the recent few years. Different challenges shorten the operation of sensor nodes over the targeted area for different reasons such as danger, inhospitality, and limited energy resources of the surrounding area. One major issue is the energy required to operate the individual sensor nodes that definitely affect the operation of the entire sensor network. Accordingly, energy consumption must be minimized as possible which requires to compromise sensor network activities as well as network operation. One fundamental solution commonly used for minimizing the energy consumption in each sensor node is using an energy-efficient routing algorithm. In this study, a routing approach depends on the grid topology of the sensor network is presented to maximize the lifetime of WSNs via balancing a load of data traffic among sensor nodes as evenly as possible. The evaluation process is done using CFDASC routing protocol since it represents the most comparable and related algorithm among previous work. Simulation results prove that the presented approach outperformance CFDASC algorithm in terms of network stability and load balancing of the entire network. Keywords—grid-based, wireless sensor network, cell-head, load balancing, the stability period I. INTRODUCTION Generally, a number of spatially distributed sensor nodes each of which contains four major units: a power source, processor, transceiver, and sensor constructs a wireless sensor network [1]. Furthermore, Wireless sensor networks could be utilized in numerous applications such as, sensing and collecting information from the physical environment that usually unable to reach by humans. Thus, in such conditions, sensor nodes are required to survive for a longest possible time at the concerning zone. An essential issue that highly probable to challenge the survival of sensor nodes is the limited resources specifically power source (usually small battery). Therefore, when the power source (battery) is depleted the network will be losing sensor nodes continually and it is difficult to replenish died sensors [2]. The reasons that sensor nodes characterized by such feature is that sensor nodes are basically static. Moreover, in regular conditions, sensor nodes are delivered in an inhospitable area or placed in a physical structure that makes them left unattended. Therefore, energy consumption is a very critical factor that should be managed wisely to extend the network lifetime during the duration of time for the specified mission. Energy consumption in WSNs can be divided into three different reasons: processing, sensing and communications [3]. This research will be mainly focusing on the communication aspect since it consumes a great portion of the sensor nodes energy [3]. Specifically, the way that the sensor network collects the data from the sensing field and delivers that data to the base station. In other words, the routing algorithm that is used to transfer data within the sensor network (intra-network communications) and transfer the data from the sensor network to the base station (inter-network communications). Thus, using a routing algorithm that able to retain sensor network energy and provide an even energy consumption among all sensor nodes can be a perfect solution to keep an efficient and stable operation of WSNs as long as possible. Considering that sensor networks performance reaches its best when all sensor nodes are alive and functioning. If sensor nodes start dying, empty zones will appear and there will be a lack in the required sensing data, which leads the entire WSNs unreliable and insufficient. To settle the prior mentioned issue, we present a routing algorithm that pursues to prolong the lifetime of a balanced and stable WSNs called Virtual Grid Based (VGRP). The VGRP algorithm splits the area that involves sensor nodes into a grid of sub-cells with equal size then collects the sensed data using cluster and chain techniques. II. RELATED WORK Incalculable studies have been carried out to develop the approach of routing the sensed data of WSNs. Among the wide number of approaches, some relevant will be explored for either routing algorithms that aiming to achieve load balancing in WSNs or routing algorithms for grid-based structure WSNs. This is due to the proposed algorithm belongs to Grid-based hierarchical routing algorithms, and aims to achieve load balancing in WSNs. It is worth mentioning that hierarchical routing algorithms are classified into three main sets: clustering, chaining, and hybrid routing algorithms [4].
  • 2.
    2018 International Conferenceon Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 228 EEGDG [5] is a grid-based routing algorithm that combines clustering and chain techniques which make it considered as hybrid routing algorithm. EEGDG algorithm presented to be an energy efficient and consequently, prolong the lifetime of wireless sensor networks by decreasing the hops happened in the standard chain routing algorithms like PEGASIS [6]. In spite of the fact that EEGDG algorithm could achieve its target by increasing the network lifetime but it did not make an optimal solution for the delay in data delivering that occur due to the long chain. An energy efficient load balancing algorithm (EELBC) presented in [7] depending on clustering to gain longer lifetime and load balanced WSNs. In this algorithm, it is assumed that each sensor node is equipped with a GPS unit in order to be aware of its position. EELBC works within two stages; bootstrapping and clustering. This algorithm successfully achieved longer lifetime and more load balanced wireless sensor network but its main flaw is when they assumed that there are supernodes to act as clusters heads which are less energy-constrained compared with other nodes in the network which act as clusters members. Therefore, this algorithm cannot be considered flexible or applicable for many applications since its complex assumptions that require optimal situations. GBDAS [8] divides the sensing field into a grid of cells, each cell consists of a number of sensor nodes. GBDAS algorithm operates in three phases; grid construction, chain formation, and data transmission. The fundamental objective of this algorithm is to decrease the number of dead nodes during the network lifetime. This algorithm collects the sensed data from by using a cell head for each individual cell the forming a very long chain that includes all cell heads in order to gather the sensed data for the entire network. After collecting the data within the chain, a chain head which already selected based on its residual energy will be responsible for sending the collected data to the base station. This algorithm can be considered as a successful algorithm for the applications that require a small sensing area since the chain of cell-heads will be not so long and consequently the delay in data gathering and delivering can be compromised with less energy consumption. In contrast, when the application requires a large sensing area, GBDAS will show a big delay in data gathering and delivery due to the very long chain of cell-heads. In the mobile sink scheme, a virtual grid based dynamic routes adjustment (VGDRA) is proposed to reduce the routes construction cost of sensor nodes [9]. This algorithm divides the sensing field into a number of uniform cells that depends on the total number of sensor nodes. To calculate the desired number of sub-cells and thus the number of cluster heads they utilize the same heuristics of the LEACH algorithm [10] which consider a 5% of the total number of sensor nodes. VGDRA algorithm uses the nodes that have the least distance to the center of each cell to operate as a cluster head. However the technique of selecting the cluster head at each cell can distribute energy consumption evenly among cluster members, it makes the nodes located near the cells centers die very quickly. Since the cluster head node consumes much more energy than the normal members due to receiving and aggregating data from all cluster members and then transmitting the aggregated data to other cluster head in the network. In addition to this issue, implementing a mobile sink approach is not convenient for most of the application. Enhanced chain-cluster based mixed routing algorithm (E- CCM) [11] has introduced to maximize the lifetime and minimize energy consumption of wireless sensor network. E- CCM operates based on grid topology and works within two stages; the initialization stage and transmission stage. E-CCM algorithm considered as hybrid hierarchical routing algorithm since it is built depending on chain and cluster techniques. This algorithm achieves its goals perfectly by outperforms the previous related work like the CCM algorithm [12]. Although the E-CCM algorithm can only function with a uniformly predetermined distribution of sensor nodes it is not designed to be applicable for applications that require a random distribution of sensor nodes. Based on the study of literature, it can be seen that majority of related work has focused on increasing the network lifetime without taking in consideration balance the load evenly among sensor nodes. Moreover, some of the previous algorithms used complex assumption like supernodes (nodes with unrestricted energy source). III. PROBLEM STATEMENT The architecture of wireless sensor network can be described as a set ‘S’ of nodes. We assume that each sensor node is aware of its location using a GPS unit. The goal of using hierarchical schemes; chain, cluster, and hybrid, is to create a virtual structure that facilitates and ease managing data routing in wireless sensor networks. One of the goals of hierarchical routing algorithms is load balancing among sensor nodes. Majority of Grid-based routing algorithms is directly or indirectly rely on clustering technique. The goal of clustering is to select a set of sensor nodes to be cluster heads that cover the whole network. The cluster head would be responsible for receiving and aggregating the sensed data from all cluster members and then forward the aggregated data either to the base station or to the next cluster head based on the routing mechanism. Therefore, the cluster head consumes more energy compared to the energy consumed by a normal cluster member. The problem of load balancing happens when a group of sensor nodes is repeatedly selected to operate as cluster heads. As a result, those nodes will die very fast and the death of nodes will cause empty gaps within the entire network. Those gaps not only can affect the validity of the sensed data but also can affect the communication of the WSNs which are mainly built upon multi-hop communication. Thus, the proposed algorithm aims to keep the load evenly distributed among sensor nodes which lead to retain all sensor nodes alive and functioning as long as possible. IV. VGRP SCHEME Here, will outline the characteristics of the proposed approach Virtual Grid Based routing protocol (VGRP) which aims to keep the robustness and validity of wireless sensor network as long as possible by balancing the load evenly
  • 3.
    2018 International Conferenceon Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 229 among all sensor nodes. VGRP significance appears during the selection of the node that collects and aggregate data from other nodes to avoid overloading specific nodes rather than others. VGRP algorithm tried to achieve this goal by utilizing the factor of remaining energy of individual nodes to decide upon their selection of being a cluster or chain head. The closest related and highest comparable work like Chain-based fast data aggregation algorithm based on suppositional cells has gained a substantial performance in term of transmission delay [13]. However, the remaining energy of each sensor node that selected to act as a cluster or chain head has not taken into consideration. Therefore, a node with almost depleted energy might be selected to represent the head for a group of sensors while a node with much higher energy operates as normal member node that requires only a few amounts of energy to transmit its data to the group head. The proposed algorithm VGRP distribute the duty of being a group head (chain or cluster) by taking into consideration its remaining energy. The operation of the VGRP algorithm can be divided into two main stages; virtual grid setup and data transmission. A. Virtual Grid setup The network topology is initialized based on dividing the sensing field to a virtual grid topology with equal size cells. The field axes are equally divided and numbered according to the number of cells, which are located along each field-axis. For instance, if there are three cells on the x-axis, then the x- axis is numbered as 0, 1, 2 and if there are five cells then the coordinate will be numbered as 0, 1, 2, 3, 4 and so on. Therefore, the numbers on the x-axis can be considered as the column number while the numbers of the y-axis represent the row numbers. Fig. 1. Virtual grid construction Each cell within the grid has a unique cell ID called (CID). The group of sensor nodes that fall into a specific cell can determine its unique cell-ID based on (1). CID = [Cx, Cy] () Where Cx and Cy represent the cell coordinates on the x- axis and y-axis respectively. Fig.1 clarifies an example of sensing field divided into a virtual grid of 5 × 5 equal cells. For instance, the IDs for the first row and from left to right IDs will be [0,0], [1,0], [2,0], [3,0], [4,0] and so on so forth. B. Head nodes selection and data transmission In order to collect, aggregate, and send the sensed data to the base station, nodes called cell-heads and chain heads act as an intermediary between the non-head nodes and the base station. At the first sensing round, all nodes have the same energy hence cell-head nodes will be randomly selected. Then, during the next sensing rounds, the node that has the maximum residual energy will be functioning as the cell-head. After the data get collected in the cell-head nodes, a chain head is selected depending on the same basis of selecting the cell-head, which will be responsible for gathering the data vertically. The job of the head nodes is to collect the sensed data from its nodes, aggregate with its own data and then forward it either to the next head node using multi-hop communication or send it directly to the base station. The process of selecting cell-head nodes, forming a chain that consists of a set of cell-head nodes, and finally select a chain head for each individual chain is accomplished by the base station. In VGRP algorithm, data transmission is done in steps; within the individual cells (intra-cell data transmission) based on clustering technique and between the cell-heads (inter-cell data transmission) based on chain technique. Therefore, there will be two types of head nodes which are cell-head and chain head nodes. Fig.2 shows the flowchart of virtual-grid setup process as well as the intra-cell communications. Fig. 2. Flowchart of virtual-grid setup and the intra-cell communications Intra-Cell Communications: The main structure of the VGRP algorithm is to divide the sensing area to a virtual grid with equal size cells. After constructing the grid and assigning each sensor node to its corresponding cell, a cell head for each group of nodes that belong to the same cell is selected based on its remaining energy. The cell head takes charge of
  • 4.
    2018 International Conferenceon Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 230 gathering the sensed data packets from all non-head nodes that belong to the same cell then aggregate it with its own data and then forward it to the next cell-head node based on multi-hop communications. Fig.3 illustrates network structure after forming the grid of cells and selecting a head node for each individual cell. Fig. 3. Intra-cell communications Inter-Cell Communications: When all data packets are collected within the cell-head nodes, those head nodes will form a chain that includes all cell-heads that fall in the same column. Nodes with maximum remaining energy take the role of being chain head of their respective chains. Data transmission is done using the greedy algorithm like in pegasis [6]. Each sensor node sends its own data packet to its neighbor node (adjacent sensor node toward the chain head). The neighbor node receives the data packet and aggregates it with its own data packet then transmits it to its neighbor and so on so forth till data are all collected in the chain head node. After that, the chain head receives its neighbors' data, aggregates it with its own data and then forwards it to the base station. Fig.4 clarifies the procedure of this process while Fig.5 is a flowchart that demonstrates the vertical chains formation and the inter-cell communications. Fig. 4. Inter-cell communications Fig. 5. Flowchart of vertical chains formation and inter-cell communications V. NETWORK MODEL The sensing field is represented by a 2-D area which is equally partitioned into identical size cells. The base station is fixed and placed outside, far from the sensing field. 50 and 100 sensor nodes respectively are distributed randomly over the sensing area. In order to give comprehensive details about network system model, it is divided into two main sections that include the basic assumptions used in the simulation software and energy model utilized to determine energy consumption due to the transmitting of data packets. A. Basic Assumptions A number of basic assumption must be decided before proceeding with the simulation. • All nodes have awareness of their geographical location based on GPS unit. • All nodes are immobile after the deployment. • All nodes are of homogeneous energy (all nodes contains the same initial energy) [14]. • Each sensor node is aware of its remaining energy. • The amount of energy consumption due to data transfer from point X to point Y is the same as when the transfer is from point Y to point X. • Energy consumption due to aggregation of data packets is equal to 5nJ/bit/packet [15]. For the first assumption, it is assumed that each sensor node is aware of its location to help the sensor nodes to determine the cell that they belong to and then organize themselves into clusters within the corresponding cells. As the second
  • 5.
    2018 International Conferenceon Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 231 assumption, the vast majority of wireless sensor networks applications require stationary sensor nodes [16]. For the simplicity of the simulation process, sensor nodes are assumed homogeneous. Moreover, sensor nodes are aware of their remaining energy and the location of the base station, then the remaining energy factor can be utilized to make the decision of choosing the cell-head nodes and later the decision of choosing chain-head nodes. B. Energy Model In order to evaluate the consumption of energy due to data transmission and receive, the first order radio transceiver is used in this design [6], [11], [16], [17]. Equations (2) and (3) are used to determine the energy cost due to data receiving and due to data transmitting respectively. Energy consumption due to data receiving Erx(k)= Eelec × k () Energy consumption due to data transmission ETx(k, d)= Eelec × k + Eamp × k × d  () Where Eelec represents the energy required to run the transmitter or the receiver, k represents the size of data packets, Eamp stands for the amount of consumed energy to run the amplifier, and d is the distance of transmission. Moreover, there are some fixed parameters used through the simulation process which is shown in Table I. TABLE I. SIMULATION PARAMETERS Simulation parameters Subhead Area of the sensing field (50×50) m2 & (100×100) m2 Basic station location (25,75) & (50,150) Number of sensor nodes 100 Sensor node's initial energy 0.5 Joule Eele 50 nJ/bit Eamp 100 pJ/bit/m2 Data packet size 2000 bit VI. RESULTS AND ANALYSIS VGRP and CFDASC performance are evaluated based on two crucial performance metrics; load balancing, and network stability. A. Load Balancing The load balancing metric represents the proportion of the residual energy of the entire network when the first node dies. The performance of network evaluated based upon this metric has an inverse relationship which means that the network with minimum residual energy when the first node dies is the network that shows the best load balancing [17], [18]. In other words, when the first node of a network dies and the network only has a few portions of the remaining energy. Consequently, it means that the rest of all alive nodes have reached to the minimum amount of energy that makes them alive. In addition, it also means that they are almost dead not in the same round of the first node but might die the next round or after a few rounds (in maximum). Based on the above explanation, we can see that when all nodes die at the same time or even at very close period just because they consumed the same amount of energy during their operation. Which also means that each sensor node in the network has a burden of almost the same amount of a load of data packets traffic. The total residual energy of the entire network when the first node dies using (50 × 50) m2 & (100 × 100) m2 sensing area is shown in Table II and Table III respectively. The routing algorithm with the lowest parameter has the best performance in term of load balancing [17], [18]. TABLE II. TOTAL REMAINING ENERGY WHEN FIRST NODE DIES USING (50×50) M2 SENSING AREA Routing algorithm Total remaining energy (Joule) Percentage of remaining energy VGRP 10.4 20.8% CFDASC 22 44% TABLE III. TOTAL REMAINING ENERGY WHEN FIRST NODE DIES USING (100×100) M2 SENSING AREA Routing algorithm Total remaining energy (Joule) Percentage of remaining energy VGRP 16.92 33.84% CFDASC 29.62 59.24% It can be clearly seen that the proposed algorithm VGRP outperforms CFDASC algorithm in term of load balancing in both (50 × 50) m2 & (100 × 100) m2 sensing area. B. Stability period Stability period of wireless sensor network represents the period of time starting from the first sensing round till the death of the first sensor node [17], [18]. Therefore, without long-term stability period, more data could not be gathered from the sensing field even if the network lifetime is high. Because of that, extending the stability period is crucial for many applications of wireless sensor networks. Fig.4 shows the stability period of the sensor network using (50 × 50) m2 & (100 × 100) m2 sensing area respectively. Fig. 6. Stability period using different sensing area
  • 6.
    2018 International Conferenceon Advanced Science and Engineering (ICOASE), Kurdistan Region, Iraq 232 As demonstrated in Fig.6, VGRP algorithm shows better performance in term of network stability period using different sensing area. The improvement of VGRP over CFDASC algorithm is almost 40.3% using (50 × 50) m2 sensing area while it is about 51.5% using (100 × 100) m2 . Equation (4) is used to determine the percentage of improvement VGRP over CFDASC algorithm [11]. POI = (Second Value-First Value)/First Value×100% () Where POI stands for the percentage of improvement, hence, in this performance metric, it shows the improvement percentage in network stability period. The First value refers to the sensing round when the first node dies using CFDASC algorithm. Second value stands for the sensing round when the first node dies using VGRP algorithm. VII. CONCLUSION AND FUTURE WORK In this research, a Virtual Grid-Based routing protocol (VGRP) has presented to maintain load balancing and increase stability period of wireless sensor networks. VGRP algorithm divides the sensing area to a grid of cells then treat each cell as an independent cluster. It works within two stages; virtual grid setup and data transmission. In addition, a sensor node, which has maximum remaining energy, is selected to function as a cluster head during intra-cell data transmission and inter-cell data transmission. The evaluation process is done through a simulation program using area (50×50) m2 & (100×100) m2 respectively to check the validity of the proposed algorithm with different sensing area. Simulation results show that VGRP algorithm outperforms CFDASC algorithm in both performance metrics utilized in this study; network load balancing and network stability period. Moreover, in term of stability period, VGRP algorithm shows an improvement over CFDASC algorithm about 40.3% and 51.5% using (50×50) m2 and using (100×100) m2 sensing areas respectively. As part of our future work will try to implement the proposed algorithm in real-life applications, specifically, in home automation systems that involve sensors in their operations [19]. In addition, the performance of the proposed algorithm will be investigated using other performance metrics such as end-to-end delay and network throughput. Moreover, different communication approaches will be explored such as Zigbee and LiFi technologies [20] REFERENCES [1] V. C. Gungor and G. P. Hancke, "Industrial Wireless Sensor Networks: Challenges, Design Principles, and Technical Approaches," in IEEE Transactions on Industrial Electronics, vol. 56, no. 10, pp. 4258-4265, Oct. 2009. [2] Liang, F., et al., "Study on the Rough-set-based Clustering Algorithm for Sensor Networks", Bulletin of Electrical Engineering and Informatics, Vol.3, no.2, pp.77-90, June 2014. [3] J.Y.Choi, et al., "Cell-based energy density-aware routing: a new protocol for improving the lifetime of wireless sensor networks." Computer Communications, vol. 28, no. 11, pp. 1293-1302, Dec. 2005. [4] H.Kareem, et al., "A Survey of State of the Art: Hierarchical Routing Algorithm for Wireless Sensor Networks." Journal of Theoretical & Applied Information Technology vol.62, no.3, pp.769-781, April 2014. [5] Y. F. Huang, et al., "An efficient energy data gathering based on grid- chain for wireless sensor networks," 4th International Conference on Awareness Science and Technology, Seoul, 2012, pp. 78-82. [6] S. Lindsey and C. S. Raghavendra, "PEGASIS: Power-efficient gathering in sensor information systems," Proceedings, IEEE Aerospace Conference, 2002, pp. 3-1125-3-1130 vol.3. [7] P.Kuila, and P.K.Jana. "Energy efficient load-balanced clustering algorithm for wireless sensor networks." Procedia technology 6, pp.771- 777, Nov. 2012. [8] Wang, N. C., et al., "Grid-Based Data Aggregation for Wireless Sensor Networks", Journal of Advances in Computer Networks, vol.1, no.4, pp.329-333, Dec. 2013. [9] A. W. Khan, et al., "VGDRA: A Virtual Grid-Based Dynamic Routes Adjustment Scheme for Mobile Sink-Based Wireless Sensor Networks," in IEEE Sensors Journal, vol. 15, no. 1, pp. 526-534, Jan. 2015. [10] G. J. Pottie, and W. J. Kaiser, "Embedding the Internet: Wireless Integrated Network Sensors", Communications of the ACM, vol. 43, no. 5, pp. 51-58, 2000. [11] H.kareem "Enhanced Chain-Cluster Based Mixed Routing Algorithm for Wireless Sensor Networks" Journal of Engineering, vol.22, no.1, pp.103-117, Jan. 2016. [12] F. Tang, et al., "A chain-cluster based routing algorithm for wireless sensor networks", Journal of intelligent manufacturing, vol. 23, no. 4, pp. 1305-1313, may 2012. [13] Hao Wu, et al., "A Chain-based Fast Data Aggregation Algorithm Based on Suppositional Cells for wireless sensor networks," 2009 2nd International Conference on Power Electronics and Intelligent Transportation System (PEITS), Shenzhen, 2009, pp. 106-109. [14] Haseeb, K., et al. "Grid-based cluster head selection mechanism for the wireless sensor network." Telkomnika (Telecommunication Computing Electronics and Control), Vol.13, no.1, pp. 269-276, March 2015. [15] Marhoon, Haydar Abdulameer, et al. "Performance evaluation of CCM and TSCP routing protocols within/without data fusing in WSNs." Journal of Physics: Conference Series. Vol. 1032. No. 1. IOP Publishing, 2018. [16] Y. K. Chiang, et al., "Cycle-Based Data Aggregation for Grid-Based Wireless Sensor Networks," 2013 Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, Taichung, 2013, pp. 348-353. [17] H. Kareem, et al., "Energy Efficient Two-Stage Chain Routing Protocol (TSCP) for Wireless Sensor Networks," Journal of Theoretical and Applied Information Technology, vol. 59, pp. 442-450, Jan. 2014. [18] R. Sheikhpour and S. Jabbehdari, "A Cluster-Chain based Routing Protocol for Balancing Energy Consumption in Wireless Sensor Networks," International Journal of Multimedia & Ubiquitous Engineering, vol. 7, no. 2, pp. 1-16, April 2012. [19] H.Jameel, and H.kareem, "Low-Cost Energy-Efficient Smart Monitoring System Using Open-Source Microcontrollers." International Review of Automatic Control (IREACO), vol.9, no.6, pp. 423-428, Nov 2016. [20] Dr. Hussam Dheaa Kamel, Hadi Jameel Hadi, “The Characteristic of Li- Fi Technology Comparing with Wi-Fi” International Journal of Computation and Applied Sciences IJOCAAS, Volume2, Issue 2, April 2017.