# Grid-Based Hybrid Network Deployment Approach for Energy Efficient Wireless Sensor Networks

Authors: Haleem Farman; Huma Javed; Jamil Ahmad; Bilal Jan; Muhammad Zeeshan
Journal: Journal of Sensors
 (2016)

---

## Abstract

Wireless sensor networks (WSN) empower applications for critical decision-making through collaborative computing, communications, and distributed sensing. However, they face several challenges due to their peculiar use in a wide variety of applications. One of the inherent challenges with any battery operated sensor is the efficient consumption of energy and its effect on network lifetime. In this paper, we introduce a novel grid-based hybrid network deployment (GHND) framework which ensures energy efficiency and load balancing in wireless sensor networks. This research is particularly focused on the merge and split technique to achieve even distribution of sensor nodes across the grid. Low density neighboring zones are merged together whereas high density zones are strategically split to achieve optimum balance. Extensive simulations reveal that the proposed method outperforms state-of-the-art techniques in terms of load balancing, network lifetime, and total energy consumption.


---

## Body

## 1. Introduction

Wireless sensor network with its sole purpose of data collection, processing, and communicating to other nodes in the network is extensively used for diverse sets of applications such as surveillance, weather forecasting, forest fire detection, smart homes, and health care and other biomedical applications. Sensor networks are aimed at operating in unattended hostile environments for longer periods of time. Nodes in WSN are typically battery operated having an inherent energy limitation. The scarce energy resource and the unpleasant environmental constraints make replacement or recharging of the battery very hard or even impossible in certain situations like battle field, volcano detection, deep sea sensing, and so forth. Therefore battery usage must be properly managed in order to minimize energy consumption across the network [1, 2].In WSN single-hop routing, though simpler, consumes more energy where signals are transmitted with large transmission power in order to reach destination. On the other hand, the limited radio range of the node and other environmental factors (obstacles, noise, interference, etc.) make single-hop communication infeasible. In WSN, sensor nodes cooperate with each other to collect data and then forward it in a hierarchical manner [3] making it a multihop network.In WSN nodes are often randomly distributed across a given geographical area. In such situation some regions in the network get densely populated whereas others receive less number of nodes. Cluster-based and grid-based techniques [4, 5] are used to cope with this problem. Cluster-based schemes minimize energy consumption and simplify network management by treating related nodes in groups. Cluster-based approaches increase scalability and robustness and provide load balancing and data aggregation [1, 2, 6]. Grid-based clustering techniques are adopted for efficient clustering where the whole area is divided into virtual grids. The decision of selecting cluster head (CH) per grid is usually done by the nodes themselves which makes it suitable for large scale networks. Grid-based techniques are popular due to its simplicity, scalability, and uniformity in energy consumption across the network [7]. In literature, different energy efficient cluster-based and grid-based algorithms have been proposed such as LEACH [8], PEGASIS [9], CBDAS [10], and GBDD [11] but still load balancing and energy efficiency are open issues because of the randomized nature of WSN. The iterative process of cluster formation and CH reselection requires transmitting continuous control messages which results in extensive energy consumption of the nodes and leads to poor performance of the network.This paper focuses on a technique that can ensure load balancing and intelligent selection and reselection of zone head (ZH) to maximize network lifetime. Our main contribution is to develop a robust network model, which has been developed to deal with variability in deployment area, node density, and grid size. The network is divided into equal squared size grids and the number of nodes in each zone is determined by their coordinates. Merge and split technique is proposed to achieve load balancing. Nodes are merged with their neighboring zones on the basis of Weighted Merge Score (WMS). Furthermore, four splitting strategies are proposed in order to split the zone if the number of nodes exceeds upper bound (UB). After the topology construction, the zone head (ZH) selected is the one having the maximum average distance value (ADV). The role of zone head is rotated to increase network stability and overall network lifetime.The rest of the paper is organized as follows. Section2 is about related work. Section 3 focuses on the proposed network model. Simulation results are discussed in Section 4 and the paper is concluded with future directions.


## 2. Related Work

In existing literature, many researchers [8–22] have discussed different clustering techniques but still issues such as load balancing, ZH selection and reselection, and energy consumption exist. In addition, topology management is also very important to uniformly distribute the nodes in clusters/grids and make the network efficient [2, 3]. Keeping in view the above-mentioned issues, relevant existing approaches are briefly discussed below.


### 2.1. Clustering Approaches

In clustering multihop transmission is used to avoid long transmission between CH and base station (BS) in order to save energy [4–7]. Efficient and scalable sensor network can be achieved through clustering. It has attracted much attention of the researchers and few of them are discussed here. In LEACH [8], nodes form clusters in a distributed manner and are self-organized. CH is randomly selected for each round; CH depends on a random number between 0 and 1. If the selected number is less than a threshold, node becomes a cluster head for the current round. LEACH-C [12] is the modified version of LEACH. The number of cluster heads is determined by BS and varies from round to round due to the lack of coordination between nodes; in LEACH-C the number of cluster heads in each round equals a determined optimum value. These methods address one-hop transmission which is not suitable for large scale networks.The Muruganathan et al. algorithm [13] splits the network into two subclusters which are further divided until the desired number of cluster heads is approached to achieve even load distribution. In Cluster-Based Energy Efficient Data Collecting and Aggregation Protocol (CEDCAP) [14] the sink node selects the cluster head based on the information (location and residual energy) received from the nodes in the cluster. Power Efficient Gathering in Sensor Information Systems (PEGASIS) [9] uses a greedy algorithm to link nodes through chain. Data is fused from node to node and finally forwarded by the leader towards BS. Only one node can transmit data at a time and the node closest to BS is elected as chain leader. PEGASIS improves energy consumption through multihop communication but has high transmission delay if network size is increased.Typically clustering techniques do not ensure load balancing. The techniques discussed here are used to simplify management and minimize the energy consumption of sensor nodes. Besides all these amenities, clustering often leads to hotspot problem where certain number of nodes expire early because of excessive usage of those nodes. This results in network partitioning and polarization of nodes.


### 2.2. Grid-Clustering Approach

Grid-based clustering is one of the popular methods of clustering in which the whole network area is divided into virtual grids [23–25]. In Grid-Based Data Dissemination (GBDD) [11], the network is divided into grids (also called cells) initiated by the BS. The first node interested in communicating data is set as the crossing point (CP) for the grid and its coordinates become the reference point for the grid creation. In Cycle-Based Data Aggregation Scheme (CBDAS) [10], each cell head is linked with another cell head to make a cyclic chain. In each round, a cell head having high residual energy is selected as cycle head by the BS. In both approaches, it is often difficult to achieve preferred number of grids required by the network scenario. One attempt made in literature is the distributed uniform clustering algorithm [15] that decreases differences in cluster sizes.In a similar approach by Zeng [16] the whole network is partitioned into grids based on the node location where midpoints are computed using the membership degree. In another approach [26] the network is divided into two levels of square shaped grids: low level and high level. Low level is for in-cluster data collection whereas high level is used for intercluster data transmission. Fan-Shaped Clustering (FSC) grid-based method is proposed in [27], which divides the whole network into rings and each ring is further subdivided to form fan-shaped clusters. In [24], the authors have used Bollinger Bands method for CH selection of each square shaped grid. In this scheme, the node is elected as CH with maximum and minimum energy change based on upper and lower Bollinger Bands, respectively.One of the main limitations of grid-based clustering is the restriction on the number of grids and suitable grid size. Often it becomes difficult to achieve the desired number of grids for a particular deployment scenario. Secondly, the network performance is affected in case of nonuniform deployment. Moreover, grid-based techniques in some cases do not give fair selection of CH with respect to all nodes in the network.


### 2.3. Variable Clustering

Clusters with different sizes have been widely praised in literature for achieving energy efficiency. In many-to-one data forwarding pattern in clustering, the nodes closer to the BS are frequently used as potential data forwarders thus consuming comparatively more energy [17, 18, 28]. In Unequal Clustering Size Model [19] sensing field is circular and is divided into two layers. Cluster in each layer will have different shape and size. Area covered by clusters can be changed in each layer by changing radius of the layer. In Grid Sectoring [20] the area of interest is further divided into small sectors. This process continues until an optimum number of clusters are achieved (the desired optimum value is 5 percent of the total number of nodes). In these methods number of nodes per cluster can vary greatly and can result in isolated nodes.A nonuniform deterministic node distribution is proposed by Chatterjee and Das [21] in which the number of nodes increases towards sink node. The problem of energy hole due to uniform clustering is addressed in [21]. Energy Aware Distributed Clustering (EADC) [29] is proposed for nonuniform distribution of nodes to balance load across the network. However, the problem is that some of the nodes may be redundant and consume extra energy which was ignored by the authors. This problem has been addressed by Nokhanji et al. [30], by identifying the redundant nodes and turning them off according to a schedule based on their residual energy.Unequal clustering mechanism with intercluster multihop routing is adopted in [31]. In this approach the whole network is partitioned into variable size clusters in which cluster head reserves more energy for intercluster communication in order to avoidhotspot problem. Authors have used energy aware multihop routing system to balance and minimize the energy load of the CH for intercluster communication.Variable size clustering algorithms can result in balanced energy consumption maximizing network lifetime. However, extra advertisements for cluster head selection may lead to extra computation and energy overhead. Looking at the above discussion, we can summarize that the services provided by different clustering techniques still have several shortcomings that need to be addressed, for instance, network management overhead,hotspot problem, and broadcasting issues. The above discussion also shows that grid-based system is a better option but the dynamic nature of sensor networks makes it difficult to predict the size of grids and number of nodes. As mentioned above, the problems ofhotspot, nonuniform distribution of nodes (load balancing), and computation overhead have been addressed in the proposed technique. Furthermore, the proposed technique not only is energy efficient but also performs better on load balancing when compared with state-of-the-art techniques.


## 2.1. Clustering Approaches

In clustering multihop transmission is used to avoid long transmission between CH and base station (BS) in order to save energy [4–7]. Efficient and scalable sensor network can be achieved through clustering. It has attracted much attention of the researchers and few of them are discussed here. In LEACH [8], nodes form clusters in a distributed manner and are self-organized. CH is randomly selected for each round; CH depends on a random number between 0 and 1. If the selected number is less than a threshold, node becomes a cluster head for the current round. LEACH-C [12] is the modified version of LEACH. The number of cluster heads is determined by BS and varies from round to round due to the lack of coordination between nodes; in LEACH-C the number of cluster heads in each round equals a determined optimum value. These methods address one-hop transmission which is not suitable for large scale networks.The Muruganathan et al. algorithm [13] splits the network into two subclusters which are further divided until the desired number of cluster heads is approached to achieve even load distribution. In Cluster-Based Energy Efficient Data Collecting and Aggregation Protocol (CEDCAP) [14] the sink node selects the cluster head based on the information (location and residual energy) received from the nodes in the cluster. Power Efficient Gathering in Sensor Information Systems (PEGASIS) [9] uses a greedy algorithm to link nodes through chain. Data is fused from node to node and finally forwarded by the leader towards BS. Only one node can transmit data at a time and the node closest to BS is elected as chain leader. PEGASIS improves energy consumption through multihop communication but has high transmission delay if network size is increased.Typically clustering techniques do not ensure load balancing. The techniques discussed here are used to simplify management and minimize the energy consumption of sensor nodes. Besides all these amenities, clustering often leads to hotspot problem where certain number of nodes expire early because of excessive usage of those nodes. This results in network partitioning and polarization of nodes.


## 2.2. Grid-Clustering Approach

Grid-based clustering is one of the popular methods of clustering in which the whole network area is divided into virtual grids [23–25]. In Grid-Based Data Dissemination (GBDD) [11], the network is divided into grids (also called cells) initiated by the BS. The first node interested in communicating data is set as the crossing point (CP) for the grid and its coordinates become the reference point for the grid creation. In Cycle-Based Data Aggregation Scheme (CBDAS) [10], each cell head is linked with another cell head to make a cyclic chain. In each round, a cell head having high residual energy is selected as cycle head by the BS. In both approaches, it is often difficult to achieve preferred number of grids required by the network scenario. One attempt made in literature is the distributed uniform clustering algorithm [15] that decreases differences in cluster sizes.In a similar approach by Zeng [16] the whole network is partitioned into grids based on the node location where midpoints are computed using the membership degree. In another approach [26] the network is divided into two levels of square shaped grids: low level and high level. Low level is for in-cluster data collection whereas high level is used for intercluster data transmission. Fan-Shaped Clustering (FSC) grid-based method is proposed in [27], which divides the whole network into rings and each ring is further subdivided to form fan-shaped clusters. In [24], the authors have used Bollinger Bands method for CH selection of each square shaped grid. In this scheme, the node is elected as CH with maximum and minimum energy change based on upper and lower Bollinger Bands, respectively.One of the main limitations of grid-based clustering is the restriction on the number of grids and suitable grid size. Often it becomes difficult to achieve the desired number of grids for a particular deployment scenario. Secondly, the network performance is affected in case of nonuniform deployment. Moreover, grid-based techniques in some cases do not give fair selection of CH with respect to all nodes in the network.


## 2.3. Variable Clustering

Clusters with different sizes have been widely praised in literature for achieving energy efficiency. In many-to-one data forwarding pattern in clustering, the nodes closer to the BS are frequently used as potential data forwarders thus consuming comparatively more energy [17, 18, 28]. In Unequal Clustering Size Model [19] sensing field is circular and is divided into two layers. Cluster in each layer will have different shape and size. Area covered by clusters can be changed in each layer by changing radius of the layer. In Grid Sectoring [20] the area of interest is further divided into small sectors. This process continues until an optimum number of clusters are achieved (the desired optimum value is 5 percent of the total number of nodes). In these methods number of nodes per cluster can vary greatly and can result in isolated nodes.A nonuniform deterministic node distribution is proposed by Chatterjee and Das [21] in which the number of nodes increases towards sink node. The problem of energy hole due to uniform clustering is addressed in [21]. Energy Aware Distributed Clustering (EADC) [29] is proposed for nonuniform distribution of nodes to balance load across the network. However, the problem is that some of the nodes may be redundant and consume extra energy which was ignored by the authors. This problem has been addressed by Nokhanji et al. [30], by identifying the redundant nodes and turning them off according to a schedule based on their residual energy.Unequal clustering mechanism with intercluster multihop routing is adopted in [31]. In this approach the whole network is partitioned into variable size clusters in which cluster head reserves more energy for intercluster communication in order to avoidhotspot problem. Authors have used energy aware multihop routing system to balance and minimize the energy load of the CH for intercluster communication.Variable size clustering algorithms can result in balanced energy consumption maximizing network lifetime. However, extra advertisements for cluster head selection may lead to extra computation and energy overhead. Looking at the above discussion, we can summarize that the services provided by different clustering techniques still have several shortcomings that need to be addressed, for instance, network management overhead,hotspot problem, and broadcasting issues. The above discussion also shows that grid-based system is a better option but the dynamic nature of sensor networks makes it difficult to predict the size of grids and number of nodes. As mentioned above, the problems ofhotspot, nonuniform distribution of nodes (load balancing), and computation overhead have been addressed in the proposed technique. Furthermore, the proposed technique not only is energy efficient but also performs better on load balancing when compared with state-of-the-art techniques.


## 3. Proposed Technique

To address the problem of load balancing and energy consumption mentioned in the previous section, we propose grid-based hybrid network deployment (GHND) framework with variable grid size. The proposed hybrid approach evenly distributes the load across the network, improves network management, and extends network lifetime. Random deployment often leads to uneven distribution of nodes. The proposed technique overcomes this problem by employing merge and split technique. This technique overcomeshotspot problem and improves network management when the nodes are evenly distributed. Figure 1 presents the proposed framework. The process is divided into the following main phases.Figure 1
Framework of the proposed technique.


### 3.1. Deployment Phase

The total number of nodesN (where N=1,2,3,…,n) is randomly deployed in a square targeted area (A=FH×FW), where FH and FW are the field height and width, respectively. We assume some default node parameters, for instance, coordinates, node ID, and energy level. Once the topology is built and nodes are deployed, they share this configuration information with the base station. This information is later used by BS for carrying out the grid formation procedure more efficiently.


### 3.2. Grid Formation

In this phase the information collected from different nodes is used to form zones and construct topology as presented in Algorithm1. We propose a novel technique for grid formation which is further divided into two main steps.Algorithm 1:Zone formation.
(1)procedure  ZoneFormation (2)Input: number of zones, Z; height and width of deployment area, M; zone width, ZW; zone height, ZH; (3)for Zn = 1 to Z  do (4)R=(Zn)/M (5)C=[Zn-1mod⁡M]+1 (6)Zxs=C∗ZH-ZW (7)Zys=R∗ZW-ZH (8)Zxe=Zxs+ZW (9)Zye=Zys+ZH (10)for  n=1 to N  do (11)if  (nx≥Zxs  &  nx<Zxe  &  ny≥Zys  &  ny<Zye)  then (12)IncrementZD(Zn) (13)NodeInZone(n)=Zn (14)end if (15)end for (16)end for (17)end procedure (18)Output: Zone formed, Zn.


#### 3.2.1. Zone Formation

Base station divides the entire network into virtual grids on the basis of the following parameters:Z: number of zones/gridsZn: zone numberNz: number of nodes per zoneZHT: number of zone headsFH: height of fieldFW: width of fieldZH: height of each zone/gridZW: width of each zone/gridR: rowsC: columnsM: dimension of the fieldSC: candidate for splittingZxs, Zys: starting coordinates of zoneZxe, Zye: ending coordinates of zonenz: neighboring zone(nx,ny): coordinates of a node(ZCx,ZCy): centroid coordinates of a zoneEach grid represents a single zone identified by unique zone ID. Once the zone formation phase is completed, BS determines the number of nodes per zone by calculating the starting and ending point of each zone as mentioned in Algorithm1. Figure 2 shows zone formation where nodes are randomly deployed across M×M grids. In this figure, C0 to Cm-1 are the columns and R0 to Rm-1 represent rows. (Zx,Zy) and (Zxe,Zye) represent the start and end of each zone. Zone height (ZH) and zone width (ZW) of each grid are calculated as(1)ZH=FHM,ZW=FWM.Figure 2
Zone formation.


#### 3.2.2. Merging and Splitting

As discussed earlier, sensor nodes are assumed to be deployed randomly which may lead to uneven distribution of nodes. This can intern inhotspot problem where the entire network is split into stern zones where nodes in the particular zone are isolated from the rest of the network. In order to evenly distribute nodes, the merge and split technique is used. Equation (2) calculates threshold scores for both splitting and merging of zones; this score is called Interbound Gap (IBG). If the number of nodes in a particular zone is less than the minimum threshold (lower bound) then BS will merge nodes with its neighboring zone. In case the number exceeds the maximum threshold (upper bound), then the zone will be further split into subzones according to the proposed splitting strategy,(2)IBG=UB-LB.While using merge and split technique, parameters such as density of nodes within a zone, number of grids, and deployment area are considered. The number of grids is inversely proportional to the average number of nodes per zone. If the grid dimension (M) is increased while keeping the node density constant, the average number of nodes per zone will therefore be reduced. In order to achieve optimum grid dimension, the total number of zones must be adjusted according to the number of nodes. This is an important concern for increasing network lifetime. For instance, if there are far fewer nodes per zone, this may result in void zones where node density is less and more computational power is wasted.


#### 3.2.3. Merging of Low Density Zone (LDZ)

Zones having less number of nodes than LB will be merged with nearby zone(s). Merging of nodes depends on the density (den) and distance (dist) from the neighboring zone. If nodes in the LDZ are scattered and are not close to each other, it may not be possible to merge them with one zone, and it may lead towardshotspot problem. To address thehotspot problem, Weighted Merge Score (WMS) is introduced, a metric that will decide to merge nodes with different neighboring zones. In WMS, parameters such as distance and density are given weights represented by D and σ, respectively, as shown in (3).Nodes are merged with their neighboring zones on the basis of WMS. Algorithm2 calculates WMS to determine the best neighboring zone for merging. To calculate the score, distance from center and density of the neighboring zone is considered. Best candidate zone is selected having minimum score. The zone which is to be merged with its neighboring zone is called the interest zone. Nodes having the same color mean they have been combined in one zone as shown in Figure 3,(3)WMS=D∗dist+σ∗den.Algorithm 2:Merging of zones.
(1)procedure  merging of zones (2)Input: height and width of deployment area, M; lower bound for merging, LB; number of zones,Z; weighted score for distance, D; weighted score for density, σ; (3)for Zn = 1 to Z  do (4)if  (zone_density(Zn)<LB)  then (5)R=(Zn/M)+1 (6)C=[Zn-1mod⁡M]+2 (7)neigh_zone_den=zone_density(nz) (8)     Determine the nodes in current zone (Zn) (9)for  j=1 to length(NodesInZn)  do (10)for  i=1 to length(nz)  do (11)dist=nx-ZCx2+ny-ZCy2 (12)den=zone_densitynzi (13)WMS=D∗dist+σ∗den (14)end for (15)Min⁡WMS=nz(min⁡wms) (16)      Assign node to new zone (17)end for (18)     Eliminate merged zone (19)end if (20)end for (21)end procedureFigure 3
Nodes in low density zones are merged with neighboring zones.


#### 3.2.4. Splitting of High Density Zone (HDZ)

In random deployment, zones can be dense. In order to evenly distribute the load and balance the network, HDZ will be split into subzones as shown in Algorithm3. Base station carefully observes the density of nodes in different zones and adopts one of the splitting strategies. Four splitting strategies are proposed for zone splitting: (1) Horizontal Splitting, (2) Vertical Splitting, (3) Diagonal 45° Splitting, and (4) Diagonal 135° Splitting. The percentage of optimal order in which the splitting takes place is shown in Figure 5. This is achieved by running more than 500 simulations (see Figure 4). It is clear from Figure 5 that Horizontal Splitting Ratio (HSR) was adopted most of the time for splitting of zones. Hence, HSR is more commonly employed scheme than Vertical Splitting Ratio (VSR), Diagonal 45∘ Splitting Ratio (D45SR), and Diagonal 135 Splitting Ratio (D135SR).Algorithm 3:Zone splitting.
(1)procedure  Zone splitting (2)Input: Optimal Range Ratio to split the zone, ORR; Candidate zone for splitting, SC; Upper Bound for splitting, UB; height and width of deployment area,M; (3)if  Zone is Cand_zone SC  then (4)if  (zone_density SC>UB)  then (5)    Find the indices of nodes in SC (6)end if (7)R=(SC/M) (8)C=SC-1mod⁡M+1 (9)if  (ORR≥0.75 and ≤1)  then (10)    Split horizontally (11)    Go to End (12)end if (13)if  (ORR≥0.75 and ≤1)  then (14)    Split vertically (15)    Go to End (16)end if (17)if  (ORR≥0.75 and ≤1)  then (18)    Split diagonally(45°) (19)    Go to End (20)end if (21)if  (ORR≥0.75 and ≤1)  then (22)    Split diagonally(135°) (23)    Go to End (24)end if (25)end if (26)end procedureFigure 4
Optimal order for splitting.Figure 5
Nodes distribution after merging and splitting of zones.Optimal range ratio (ORR) is required to split the zones, which is defined from 0.75 to 1.0 after extensive simulations. Various splitting strategies are evaluated in a defined order until a splitting strategy is selected which falls in the required range. Once a strategy is selected, no further computations are required for splitting in that particular iteration. The split zones get unique zone IDs for further processing.In Figure5, the merging and splitting of zones is shown by different colors. Nodes having same color imply that they belong to the same zone. Density ofZone 13 is less than LB and is merged withZone 14. The number of nodes inZone 1 andZone 2 is exceeding the UB limit and that is why they were split into subzones, which is shown in Figure 5.


### 3.3. Zone Head Selection Phase

Zone head selection is very crucial for any energy efficient protocol. ZH is responsible for data aggregation prior to forwarding the data to BS for further processing or making any decision upon the received data. ZH selection is an important process; therefore, it is required to define a criteria before selection of the ZH.


#### 3.3.1. ZH Selection Criteria

The performance of a zone directly depends on the ZH; therefore, it is significant to select the best node as the ZH among available nodes. In the proposed technique two parameters (1) energy level (EL) and (2) average distance value (ADV) are aggregated to come up with Cumulative Value (CV) of a single nodei as follows:(4)CVi=AggregateELi+1ADVi.The energy level of the node i is represented by EL; initially it will be the same for all nodes. Higher value of EL increases the chance of the candidate node for becoming the ZH, where ADV is the average distance value of each individual node in that specific zone as shown in (7). The ADV is the distance of a node from all other nodes within the zone and from center of the zone as shown in (5) and (6), respectively. Minimum value of ADV, calculated by BS, will increase node’s chance to be a ZH. Base station will get the ADV of all nodes within the network, which will be calculated once(5)di,j=ix-jx2+iy-cy2,where d(i,j) is distance of a node from other nodes in its zone. In order to know how far a node is from other nodes which are in direct transmission with it, consider(6)centi,c=ix-cx2+iy-cy2,where cent(i,c) is the center of zone. In order to know the position of the node in its zone, consider(7)ADVi=α∗centi,c+βn-1∑j=1ndi,j,j≠i,where α and β are weighted indices assigned to centroid and distance from other nodes.


#### 3.3.2. Zone Head Selection

Once the ZH criteria are set and zones are formed, ZH is selected for each individual zone according to (4). Base station will have the collection list that will have CV of all nodes against each zone in the network. Node with maximum CV will be selected as ZH for that specific zone as shown in Algorithm 4.Algorithm 4:Zone head selection.
(1)procedure  ZoneHead selection (2)Input: Cumulative Value of node, CV; Threshold Value, TV; Calculate CV of all Nodes Zone(i) = [CVs of all nodes in ZH(i)] /∗ select node with maximum CV ∗/ ZH(i)=CVmax(i) BS exchange Collection list and TV withZH(i) Member nodes register withZH(i) (3)if  CVZH(i)>TV  then (4)      Remain ZH (5)else (6)      Reselect ZH (7)end if (8)end procedure (9)Output: Zone Head, ZH.The main advantage of having a collection list is to avoid any broadcast and communication of any maintenance messages during reselection process of ZH. The reselection process is decentralized where the base station is not involved. This approach significantly reduces the number of messages exchanged (in broadcast or unicast) in the reselection process of ZH in a zone eventually reducing energy consumption and thus maximizing network lifetime. The lifetime of a ZH for one complete iteration is determined by a Threshold Value (TV). Further details about TV are discussed in the reselection phase.


### 3.4. Data Transmission Phase

Once nodes join ZH they will start sending their sensed data to the ZH as per their assigned schedule of transmission. Nodes will share their data with their respective ZH according to TDMA schedule. Member nodes will transmit collected data to ZH during their assigned time slot. This enables nodes to keep their radio off until its transmission time occurs. The sleep periods save node energy. In wakeup periods ZHs will aggregate and compress the received data and will forward it to the BS.


### 3.5. Reselection Phase

In this phase, the focus is to minimize the energy consumption in reselection process of ZH. Instead of carrying out periodic reselection of ZH that leads to extra energy consumption and network overhead, GHND dynamically initiates the process of reselection based on the energy level (EL) of the zone head. In a given iteration, if the EL value is less than or equal to TV (EL ≤ TV) the corresponding zone head will change as shown in Algorithm5. The number of iterations is independent of the zone and the reselection is carried out per zone when required. The number of iterations can be different for each zone to minimize the traffic generated in the network and also to not disturb the overall network.Algorithm 5:Zone head reselection process.
(1)procedure  ZoneHeadReselection (2)Input: Energy Level of Current Zone Head, oldELZH; Threshold Value, TV; Cumulative Value of each node, CV; Candidate Zone Head, CZH; difference of Initial and updated CV,X; (3)if  (newELZH=oldELZH-oldELZH×0.1)  then (4)if  ELZH≤TV  then (5)     Ask first CZH to send updated CV (6)if  first CZH reply exceeds timer  then (7)       Fetch CV from second CZH (8)else (9)       Compare updated_CV and initial_CV (10)if  difference<X  then (11)        Select first CZH as new ZH (12)ZHcurrent←member_node (13)ZHnew←first_CZH (14)else (15)        Fetch CV from second CZH (16)end if (17)end if (18)else (19)     Remain as ZH (20)end if (21)else (22)   Continue Transmission (23)end if (24)end procedure (25)Output: New Zone Head, ZHnew.In Algorithm5 the value of X is calculated as in the following equation: (8)X=initial_CVi-updated_CVi-EFP.Here EFP (Error Factor Percent) represents the percentage of marginal error.The value of TV is not fixed but is varied according to the traffic generated by the ZH. In case of fixing TV to a certain value, a situation arises where all candidate nodes fail to be elected as ZH leading to flat network scenario. In order to prevent such occurrence, the value of TV is set to change with respect to decrease in the EL and is therefore periodically monitored by ZH. For this purpose every ZH maintains two lists, trusted and untrusted. Nodes in the trusted list are normal nodes and can compete for ZH selection process whereas untrusted list contains black listed nodes which are taken out of the process. Any drastic change in EL will put the node in the not trusted list and will be shared with BS.


## 3.1. Deployment Phase

The total number of nodesN (where N=1,2,3,…,n) is randomly deployed in a square targeted area (A=FH×FW), where FH and FW are the field height and width, respectively. We assume some default node parameters, for instance, coordinates, node ID, and energy level. Once the topology is built and nodes are deployed, they share this configuration information with the base station. This information is later used by BS for carrying out the grid formation procedure more efficiently.


## 3.2. Grid Formation

In this phase the information collected from different nodes is used to form zones and construct topology as presented in Algorithm1. We propose a novel technique for grid formation which is further divided into two main steps.Algorithm 1:Zone formation.
(1)procedure  ZoneFormation (2)Input: number of zones, Z; height and width of deployment area, M; zone width, ZW; zone height, ZH; (3)for Zn = 1 to Z  do (4)R=(Zn)/M (5)C=[Zn-1mod⁡M]+1 (6)Zxs=C∗ZH-ZW (7)Zys=R∗ZW-ZH (8)Zxe=Zxs+ZW (9)Zye=Zys+ZH (10)for  n=1 to N  do (11)if  (nx≥Zxs  &  nx<Zxe  &  ny≥Zys  &  ny<Zye)  then (12)IncrementZD(Zn) (13)NodeInZone(n)=Zn (14)end if (15)end for (16)end for (17)end procedure (18)Output: Zone formed, Zn.


### 3.2.1. Zone Formation

Base station divides the entire network into virtual grids on the basis of the following parameters:Z: number of zones/gridsZn: zone numberNz: number of nodes per zoneZHT: number of zone headsFH: height of fieldFW: width of fieldZH: height of each zone/gridZW: width of each zone/gridR: rowsC: columnsM: dimension of the fieldSC: candidate for splittingZxs, Zys: starting coordinates of zoneZxe, Zye: ending coordinates of zonenz: neighboring zone(nx,ny): coordinates of a node(ZCx,ZCy): centroid coordinates of a zoneEach grid represents a single zone identified by unique zone ID. Once the zone formation phase is completed, BS determines the number of nodes per zone by calculating the starting and ending point of each zone as mentioned in Algorithm1. Figure 2 shows zone formation where nodes are randomly deployed across M×M grids. In this figure, C0 to Cm-1 are the columns and R0 to Rm-1 represent rows. (Zx,Zy) and (Zxe,Zye) represent the start and end of each zone. Zone height (ZH) and zone width (ZW) of each grid are calculated as(1)ZH=FHM,ZW=FWM.Figure 2
Zone formation.


### 3.2.2. Merging and Splitting

As discussed earlier, sensor nodes are assumed to be deployed randomly which may lead to uneven distribution of nodes. This can intern inhotspot problem where the entire network is split into stern zones where nodes in the particular zone are isolated from the rest of the network. In order to evenly distribute nodes, the merge and split technique is used. Equation (2) calculates threshold scores for both splitting and merging of zones; this score is called Interbound Gap (IBG). If the number of nodes in a particular zone is less than the minimum threshold (lower bound) then BS will merge nodes with its neighboring zone. In case the number exceeds the maximum threshold (upper bound), then the zone will be further split into subzones according to the proposed splitting strategy,(2)IBG=UB-LB.While using merge and split technique, parameters such as density of nodes within a zone, number of grids, and deployment area are considered. The number of grids is inversely proportional to the average number of nodes per zone. If the grid dimension (M) is increased while keeping the node density constant, the average number of nodes per zone will therefore be reduced. In order to achieve optimum grid dimension, the total number of zones must be adjusted according to the number of nodes. This is an important concern for increasing network lifetime. For instance, if there are far fewer nodes per zone, this may result in void zones where node density is less and more computational power is wasted.


### 3.2.3. Merging of Low Density Zone (LDZ)

Zones having less number of nodes than LB will be merged with nearby zone(s). Merging of nodes depends on the density (den) and distance (dist) from the neighboring zone. If nodes in the LDZ are scattered and are not close to each other, it may not be possible to merge them with one zone, and it may lead towardshotspot problem. To address thehotspot problem, Weighted Merge Score (WMS) is introduced, a metric that will decide to merge nodes with different neighboring zones. In WMS, parameters such as distance and density are given weights represented by D and σ, respectively, as shown in (3).Nodes are merged with their neighboring zones on the basis of WMS. Algorithm2 calculates WMS to determine the best neighboring zone for merging. To calculate the score, distance from center and density of the neighboring zone is considered. Best candidate zone is selected having minimum score. The zone which is to be merged with its neighboring zone is called the interest zone. Nodes having the same color mean they have been combined in one zone as shown in Figure 3,(3)WMS=D∗dist+σ∗den.Algorithm 2:Merging of zones.
(1)procedure  merging of zones (2)Input: height and width of deployment area, M; lower bound for merging, LB; number of zones,Z; weighted score for distance, D; weighted score for density, σ; (3)for Zn = 1 to Z  do (4)if  (zone_density(Zn)<LB)  then (5)R=(Zn/M)+1 (6)C=[Zn-1mod⁡M]+2 (7)neigh_zone_den=zone_density(nz) (8)     Determine the nodes in current zone (Zn) (9)for  j=1 to length(NodesInZn)  do (10)for  i=1 to length(nz)  do (11)dist=nx-ZCx2+ny-ZCy2 (12)den=zone_densitynzi (13)WMS=D∗dist+σ∗den (14)end for (15)Min⁡WMS=nz(min⁡wms) (16)      Assign node to new zone (17)end for (18)     Eliminate merged zone (19)end if (20)end for (21)end procedureFigure 3
Nodes in low density zones are merged with neighboring zones.


### 3.2.4. Splitting of High Density Zone (HDZ)

In random deployment, zones can be dense. In order to evenly distribute the load and balance the network, HDZ will be split into subzones as shown in Algorithm3. Base station carefully observes the density of nodes in different zones and adopts one of the splitting strategies. Four splitting strategies are proposed for zone splitting: (1) Horizontal Splitting, (2) Vertical Splitting, (3) Diagonal 45° Splitting, and (4) Diagonal 135° Splitting. The percentage of optimal order in which the splitting takes place is shown in Figure 5. This is achieved by running more than 500 simulations (see Figure 4). It is clear from Figure 5 that Horizontal Splitting Ratio (HSR) was adopted most of the time for splitting of zones. Hence, HSR is more commonly employed scheme than Vertical Splitting Ratio (VSR), Diagonal 45∘ Splitting Ratio (D45SR), and Diagonal 135 Splitting Ratio (D135SR).Algorithm 3:Zone splitting.
(1)procedure  Zone splitting (2)Input: Optimal Range Ratio to split the zone, ORR; Candidate zone for splitting, SC; Upper Bound for splitting, UB; height and width of deployment area,M; (3)if  Zone is Cand_zone SC  then (4)if  (zone_density SC>UB)  then (5)    Find the indices of nodes in SC (6)end if (7)R=(SC/M) (8)C=SC-1mod⁡M+1 (9)if  (ORR≥0.75 and ≤1)  then (10)    Split horizontally (11)    Go to End (12)end if (13)if  (ORR≥0.75 and ≤1)  then (14)    Split vertically (15)    Go to End (16)end if (17)if  (ORR≥0.75 and ≤1)  then (18)    Split diagonally(45°) (19)    Go to End (20)end if (21)if  (ORR≥0.75 and ≤1)  then (22)    Split diagonally(135°) (23)    Go to End (24)end if (25)end if (26)end procedureFigure 4
Optimal order for splitting.Figure 5
Nodes distribution after merging and splitting of zones.Optimal range ratio (ORR) is required to split the zones, which is defined from 0.75 to 1.0 after extensive simulations. Various splitting strategies are evaluated in a defined order until a splitting strategy is selected which falls in the required range. Once a strategy is selected, no further computations are required for splitting in that particular iteration. The split zones get unique zone IDs for further processing.In Figure5, the merging and splitting of zones is shown by different colors. Nodes having same color imply that they belong to the same zone. Density ofZone 13 is less than LB and is merged withZone 14. The number of nodes inZone 1 andZone 2 is exceeding the UB limit and that is why they were split into subzones, which is shown in Figure 5.


## 3.2.1. Zone Formation

Base station divides the entire network into virtual grids on the basis of the following parameters:Z: number of zones/gridsZn: zone numberNz: number of nodes per zoneZHT: number of zone headsFH: height of fieldFW: width of fieldZH: height of each zone/gridZW: width of each zone/gridR: rowsC: columnsM: dimension of the fieldSC: candidate for splittingZxs, Zys: starting coordinates of zoneZxe, Zye: ending coordinates of zonenz: neighboring zone(nx,ny): coordinates of a node(ZCx,ZCy): centroid coordinates of a zoneEach grid represents a single zone identified by unique zone ID. Once the zone formation phase is completed, BS determines the number of nodes per zone by calculating the starting and ending point of each zone as mentioned in Algorithm1. Figure 2 shows zone formation where nodes are randomly deployed across M×M grids. In this figure, C0 to Cm-1 are the columns and R0 to Rm-1 represent rows. (Zx,Zy) and (Zxe,Zye) represent the start and end of each zone. Zone height (ZH) and zone width (ZW) of each grid are calculated as(1)ZH=FHM,ZW=FWM.Figure 2
Zone formation.


## 3.2.2. Merging and Splitting

As discussed earlier, sensor nodes are assumed to be deployed randomly which may lead to uneven distribution of nodes. This can intern inhotspot problem where the entire network is split into stern zones where nodes in the particular zone are isolated from the rest of the network. In order to evenly distribute nodes, the merge and split technique is used. Equation (2) calculates threshold scores for both splitting and merging of zones; this score is called Interbound Gap (IBG). If the number of nodes in a particular zone is less than the minimum threshold (lower bound) then BS will merge nodes with its neighboring zone. In case the number exceeds the maximum threshold (upper bound), then the zone will be further split into subzones according to the proposed splitting strategy,(2)IBG=UB-LB.While using merge and split technique, parameters such as density of nodes within a zone, number of grids, and deployment area are considered. The number of grids is inversely proportional to the average number of nodes per zone. If the grid dimension (M) is increased while keeping the node density constant, the average number of nodes per zone will therefore be reduced. In order to achieve optimum grid dimension, the total number of zones must be adjusted according to the number of nodes. This is an important concern for increasing network lifetime. For instance, if there are far fewer nodes per zone, this may result in void zones where node density is less and more computational power is wasted.


## 3.2.3. Merging of Low Density Zone (LDZ)

Zones having less number of nodes than LB will be merged with nearby zone(s). Merging of nodes depends on the density (den) and distance (dist) from the neighboring zone. If nodes in the LDZ are scattered and are not close to each other, it may not be possible to merge them with one zone, and it may lead towardshotspot problem. To address thehotspot problem, Weighted Merge Score (WMS) is introduced, a metric that will decide to merge nodes with different neighboring zones. In WMS, parameters such as distance and density are given weights represented by D and σ, respectively, as shown in (3).Nodes are merged with their neighboring zones on the basis of WMS. Algorithm2 calculates WMS to determine the best neighboring zone for merging. To calculate the score, distance from center and density of the neighboring zone is considered. Best candidate zone is selected having minimum score. The zone which is to be merged with its neighboring zone is called the interest zone. Nodes having the same color mean they have been combined in one zone as shown in Figure 3,(3)WMS=D∗dist+σ∗den.Algorithm 2:Merging of zones.
(1)procedure  merging of zones (2)Input: height and width of deployment area, M; lower bound for merging, LB; number of zones,Z; weighted score for distance, D; weighted score for density, σ; (3)for Zn = 1 to Z  do (4)if  (zone_density(Zn)<LB)  then (5)R=(Zn/M)+1 (6)C=[Zn-1mod⁡M]+2 (7)neigh_zone_den=zone_density(nz) (8)     Determine the nodes in current zone (Zn) (9)for  j=1 to length(NodesInZn)  do (10)for  i=1 to length(nz)  do (11)dist=nx-ZCx2+ny-ZCy2 (12)den=zone_densitynzi (13)WMS=D∗dist+σ∗den (14)end for (15)Min⁡WMS=nz(min⁡wms) (16)      Assign node to new zone (17)end for (18)     Eliminate merged zone (19)end if (20)end for (21)end procedureFigure 3
Nodes in low density zones are merged with neighboring zones.


## 3.2.4. Splitting of High Density Zone (HDZ)

In random deployment, zones can be dense. In order to evenly distribute the load and balance the network, HDZ will be split into subzones as shown in Algorithm3. Base station carefully observes the density of nodes in different zones and adopts one of the splitting strategies. Four splitting strategies are proposed for zone splitting: (1) Horizontal Splitting, (2) Vertical Splitting, (3) Diagonal 45° Splitting, and (4) Diagonal 135° Splitting. The percentage of optimal order in which the splitting takes place is shown in Figure 5. This is achieved by running more than 500 simulations (see Figure 4). It is clear from Figure 5 that Horizontal Splitting Ratio (HSR) was adopted most of the time for splitting of zones. Hence, HSR is more commonly employed scheme than Vertical Splitting Ratio (VSR), Diagonal 45∘ Splitting Ratio (D45SR), and Diagonal 135 Splitting Ratio (D135SR).Algorithm 3:Zone splitting.
(1)procedure  Zone splitting (2)Input: Optimal Range Ratio to split the zone, ORR; Candidate zone for splitting, SC; Upper Bound for splitting, UB; height and width of deployment area,M; (3)if  Zone is Cand_zone SC  then (4)if  (zone_density SC>UB)  then (5)    Find the indices of nodes in SC (6)end if (7)R=(SC/M) (8)C=SC-1mod⁡M+1 (9)if  (ORR≥0.75 and ≤1)  then (10)    Split horizontally (11)    Go to End (12)end if (13)if  (ORR≥0.75 and ≤1)  then (14)    Split vertically (15)    Go to End (16)end if (17)if  (ORR≥0.75 and ≤1)  then (18)    Split diagonally(45°) (19)    Go to End (20)end if (21)if  (ORR≥0.75 and ≤1)  then (22)    Split diagonally(135°) (23)    Go to End (24)end if (25)end if (26)end procedureFigure 4
Optimal order for splitting.Figure 5
Nodes distribution after merging and splitting of zones.Optimal range ratio (ORR) is required to split the zones, which is defined from 0.75 to 1.0 after extensive simulations. Various splitting strategies are evaluated in a defined order until a splitting strategy is selected which falls in the required range. Once a strategy is selected, no further computations are required for splitting in that particular iteration. The split zones get unique zone IDs for further processing.In Figure5, the merging and splitting of zones is shown by different colors. Nodes having same color imply that they belong to the same zone. Density ofZone 13 is less than LB and is merged withZone 14. The number of nodes inZone 1 andZone 2 is exceeding the UB limit and that is why they were split into subzones, which is shown in Figure 5.


## 3.3. Zone Head Selection Phase

Zone head selection is very crucial for any energy efficient protocol. ZH is responsible for data aggregation prior to forwarding the data to BS for further processing or making any decision upon the received data. ZH selection is an important process; therefore, it is required to define a criteria before selection of the ZH.


### 3.3.1. ZH Selection Criteria

The performance of a zone directly depends on the ZH; therefore, it is significant to select the best node as the ZH among available nodes. In the proposed technique two parameters (1) energy level (EL) and (2) average distance value (ADV) are aggregated to come up with Cumulative Value (CV) of a single nodei as follows:(4)CVi=AggregateELi+1ADVi.The energy level of the node i is represented by EL; initially it will be the same for all nodes. Higher value of EL increases the chance of the candidate node for becoming the ZH, where ADV is the average distance value of each individual node in that specific zone as shown in (7). The ADV is the distance of a node from all other nodes within the zone and from center of the zone as shown in (5) and (6), respectively. Minimum value of ADV, calculated by BS, will increase node’s chance to be a ZH. Base station will get the ADV of all nodes within the network, which will be calculated once(5)di,j=ix-jx2+iy-cy2,where d(i,j) is distance of a node from other nodes in its zone. In order to know how far a node is from other nodes which are in direct transmission with it, consider(6)centi,c=ix-cx2+iy-cy2,where cent(i,c) is the center of zone. In order to know the position of the node in its zone, consider(7)ADVi=α∗centi,c+βn-1∑j=1ndi,j,j≠i,where α and β are weighted indices assigned to centroid and distance from other nodes.


### 3.3.2. Zone Head Selection

Once the ZH criteria are set and zones are formed, ZH is selected for each individual zone according to (4). Base station will have the collection list that will have CV of all nodes against each zone in the network. Node with maximum CV will be selected as ZH for that specific zone as shown in Algorithm 4.Algorithm 4:Zone head selection.
(1)procedure  ZoneHead selection (2)Input: Cumulative Value of node, CV; Threshold Value, TV; Calculate CV of all Nodes Zone(i) = [CVs of all nodes in ZH(i)] /∗ select node with maximum CV ∗/ ZH(i)=CVmax(i) BS exchange Collection list and TV withZH(i) Member nodes register withZH(i) (3)if  CVZH(i)>TV  then (4)      Remain ZH (5)else (6)      Reselect ZH (7)end if (8)end procedure (9)Output: Zone Head, ZH.The main advantage of having a collection list is to avoid any broadcast and communication of any maintenance messages during reselection process of ZH. The reselection process is decentralized where the base station is not involved. This approach significantly reduces the number of messages exchanged (in broadcast or unicast) in the reselection process of ZH in a zone eventually reducing energy consumption and thus maximizing network lifetime. The lifetime of a ZH for one complete iteration is determined by a Threshold Value (TV). Further details about TV are discussed in the reselection phase.


## 3.3.1. ZH Selection Criteria

The performance of a zone directly depends on the ZH; therefore, it is significant to select the best node as the ZH among available nodes. In the proposed technique two parameters (1) energy level (EL) and (2) average distance value (ADV) are aggregated to come up with Cumulative Value (CV) of a single nodei as follows:(4)CVi=AggregateELi+1ADVi.The energy level of the node i is represented by EL; initially it will be the same for all nodes. Higher value of EL increases the chance of the candidate node for becoming the ZH, where ADV is the average distance value of each individual node in that specific zone as shown in (7). The ADV is the distance of a node from all other nodes within the zone and from center of the zone as shown in (5) and (6), respectively. Minimum value of ADV, calculated by BS, will increase node’s chance to be a ZH. Base station will get the ADV of all nodes within the network, which will be calculated once(5)di,j=ix-jx2+iy-cy2,where d(i,j) is distance of a node from other nodes in its zone. In order to know how far a node is from other nodes which are in direct transmission with it, consider(6)centi,c=ix-cx2+iy-cy2,where cent(i,c) is the center of zone. In order to know the position of the node in its zone, consider(7)ADVi=α∗centi,c+βn-1∑j=1ndi,j,j≠i,where α and β are weighted indices assigned to centroid and distance from other nodes.


## 3.3.2. Zone Head Selection

Once the ZH criteria are set and zones are formed, ZH is selected for each individual zone according to (4). Base station will have the collection list that will have CV of all nodes against each zone in the network. Node with maximum CV will be selected as ZH for that specific zone as shown in Algorithm 4.Algorithm 4:Zone head selection.
(1)procedure  ZoneHead selection (2)Input: Cumulative Value of node, CV; Threshold Value, TV; Calculate CV of all Nodes Zone(i) = [CVs of all nodes in ZH(i)] /∗ select node with maximum CV ∗/ ZH(i)=CVmax(i) BS exchange Collection list and TV withZH(i) Member nodes register withZH(i) (3)if  CVZH(i)>TV  then (4)      Remain ZH (5)else (6)      Reselect ZH (7)end if (8)end procedure (9)Output: Zone Head, ZH.The main advantage of having a collection list is to avoid any broadcast and communication of any maintenance messages during reselection process of ZH. The reselection process is decentralized where the base station is not involved. This approach significantly reduces the number of messages exchanged (in broadcast or unicast) in the reselection process of ZH in a zone eventually reducing energy consumption and thus maximizing network lifetime. The lifetime of a ZH for one complete iteration is determined by a Threshold Value (TV). Further details about TV are discussed in the reselection phase.


## 3.4. Data Transmission Phase

Once nodes join ZH they will start sending their sensed data to the ZH as per their assigned schedule of transmission. Nodes will share their data with their respective ZH according to TDMA schedule. Member nodes will transmit collected data to ZH during their assigned time slot. This enables nodes to keep their radio off until its transmission time occurs. The sleep periods save node energy. In wakeup periods ZHs will aggregate and compress the received data and will forward it to the BS.


## 3.5. Reselection Phase

In this phase, the focus is to minimize the energy consumption in reselection process of ZH. Instead of carrying out periodic reselection of ZH that leads to extra energy consumption and network overhead, GHND dynamically initiates the process of reselection based on the energy level (EL) of the zone head. In a given iteration, if the EL value is less than or equal to TV (EL ≤ TV) the corresponding zone head will change as shown in Algorithm5. The number of iterations is independent of the zone and the reselection is carried out per zone when required. The number of iterations can be different for each zone to minimize the traffic generated in the network and also to not disturb the overall network.Algorithm 5:Zone head reselection process.
(1)procedure  ZoneHeadReselection (2)Input: Energy Level of Current Zone Head, oldELZH; Threshold Value, TV; Cumulative Value of each node, CV; Candidate Zone Head, CZH; difference of Initial and updated CV,X; (3)if  (newELZH=oldELZH-oldELZH×0.1)  then (4)if  ELZH≤TV  then (5)     Ask first CZH to send updated CV (6)if  first CZH reply exceeds timer  then (7)       Fetch CV from second CZH (8)else (9)       Compare updated_CV and initial_CV (10)if  difference<X  then (11)        Select first CZH as new ZH (12)ZHcurrent←member_node (13)ZHnew←first_CZH (14)else (15)        Fetch CV from second CZH (16)end if (17)end if (18)else (19)     Remain as ZH (20)end if (21)else (22)   Continue Transmission (23)end if (24)end procedure (25)Output: New Zone Head, ZHnew.In Algorithm5 the value of X is calculated as in the following equation: (8)X=initial_CVi-updated_CVi-EFP.Here EFP (Error Factor Percent) represents the percentage of marginal error.The value of TV is not fixed but is varied according to the traffic generated by the ZH. In case of fixing TV to a certain value, a situation arises where all candidate nodes fail to be elected as ZH leading to flat network scenario. In order to prevent such occurrence, the value of TV is set to change with respect to decrease in the EL and is therefore periodically monitored by ZH. For this purpose every ZH maintains two lists, trusted and untrusted. Nodes in the trusted list are normal nodes and can compete for ZH selection process whereas untrusted list contains black listed nodes which are taken out of the process. Any drastic change in EL will put the node in the not trusted list and will be shared with BS.


## 4. Simulation and Results

To start with the simulation setup, we have made few assumptions such as the following:(1)
all the sensor nodes and BS are static after deployment;(2)
BS is located outside the field boundary and is known to every node in the network;(3)
sensor nodes have the information of their location and initial energy;(4)
nodes already have their unique IDs.Performance of the proposed algorithm is evaluated by carrying out extensive simulations. We have also compared the performance with several state-of-the-art energy efficient cluster-based and grid-based protocols including LEACH [8], CBDAS [10], PEGASIS [9], and Direct. The simulation results reveal that total energy consumption during zone formation, ZH selection, reselection of ZH, and transmission has been reduced. All simulations were carried out using MATLAB R2013a.


### 4.1. Simulation Setup

To analyze the energy consumption of each node, first-order radio model [12] is used as shown in (9), (10), and (11), respectively. To run circuitry of the transmitter and receiver, a radio dissipates Eelec=50 nJ/bit, where Eelec is the circuit energy consumption. At the sender node, transmission amplifier further consumes Eampd2 amount of energy where Eamp is the consumption of energy while transmitting packets (Eamp=100  pJ/bit/m2) and d is the distance between nodes. To transmit k bits of message over a distance d by using first-order radio model, the transmission energy consumed (ETX) is given by the following:(9)ETXk,d=Eelec×k+Eamp×k×d2.Energy consumption at the receiving end (ERX) is shown as(10)ERXk=Eelec×k.Total transmission consumption is generalized as follows:(11)Etotalk=Eelec×k+Eamp×k×d2+Eelec×k.Performance results for different metrics have been obtained by varying certain parameters: initial energy, grid size, number of nodes, network lifespan, and total energy consumed. These parameters are discussed in the following.


### 4.2. Effect of Initial Energy

The initial energy of all nodes is set to 0.25 J, 0.5 J, and 1.0 J for evaluating Direct, LEACH, CBDAS, PEGASIS, and our proposed method (GHND) to determine the number of rounds when 1%, 25%, 50%, 75%, and 100% nodes of the network die. Figures6, 7, and 8 show that our proposed method has larger number of rounds than other techniques. This is because the control messages are reduced in ZH selection and reselection process. This increases the number of rounds and maximizes network lifetime as shown in Figures 6, 7, and 8.Figure 6
Number of rounds when 1%, 25%, 50%, 75%, and 100% nodes die in the network with initial energyE0=0.25 J.Figure 7
Number of rounds when 1%, 25%, 50%, 75%, and 100% nodes die in the network with initial energyE0=0.5 J.Figure 8
Number of rounds when 1%, 25%, 50%, 75%, and 100% nodes die in the network with initial energyE0=1.0 J.


### 4.3. Effect of Grid Size

To evaluate the impact of grid size, whole sensor field is partitioned into grid sizes of6×6, 8×8, and 10×10 grids as illustrated in Figures 9, 10, and 11. LEACH is not included in this evaluation as it is not a grid-based protocol. The proposed technique is better than other approaches in terms of number of rounds achieved as shown in Figures 9, 10, and 11. In all three approaches the proposed technique has achieved maximum number of rounds thereby improving network lifetime. This technique is approximately 1.3, 1.2, and 1.4 times better than CBDAS approach for grid sizes 6×6, 8×8, and 10×10, respectively. In comparison, grid size 10×10 has the maximum number of rounds among the three approaches by keeping the same parameters such as number of nodes (300), initial energy (E0=0.5 J), and packet size (2000 bits).Figure 9
Effect of grid size with respect to number of nodes. Here grid size =6×6.Figure 10
Effect of grid size with respect to number of nodes. Here grid size =8×8.Figure 11
Effect of grid size with respect to number of nodes. Here grid size =10×10.


### 4.4. Effect of Number of Nodes

In each approach, the effect of node density and initial energy is found out. In this case the number of nodes is varied from 100 to 500 with different initial energy values 0.25 J, 0.5 J, and 1.0 J. Figures12, 13, and 14 show the number of rounds from nodes 100 to 500 with initial energy values 0.25 J, 0.5 J, and 1.0 J, respectively. The graphs in these figures show that, for every approach, the number of rounds increases by increasing the node density except for the Direct method where comparatively very small change is detected in the number of rounds. In all these figures, GHND has more number of rounds than other approaches for all cases of node density and initial energy. The resulting network has better lifetime because, by increasing the node density, the responsibilities of each zone head is distributed.Figure 12
Effect of number of nodes with respect to initial energy.E0=0.25 J.Figure 13
Effect of number of nodes with respect to initial energy.E0=0.5 J.Figure 14
Effect of number of nodes with respect to initial energy.E0=1.0 J.


### 4.5. Network Lifespan

To analyze the network lifespan against each method, various simulations were run for different initial energy values (0.25 J, 0.50 J, and 1.0 J) for 100 nodes and packet size of 2000 bits. In Figures15, 16, and 17, the proposed method GHND has maximum number of rounds resulting in prolonged network lifetime. This shows that the proposed method surpasses the currently employed approaches in load balancing, in energy efficiency, and in prolonging the lifetime.Figure 15
Network lifespan with respect to initial energy.E0=0.25 J.Figure 16
Network lifespan with respect to initial energy.E0=0.5 J.Figure 17
Network lifespan with respect to initial energy.E0=1.0 J.


### 4.6. Total Energy Consumed

Figure18 shows total energy consumed (in sensing, computation, and communication) plotted against the number of rounds for total nodes. The graph shows that energy consumed by the proposed method is less than other approaches with increase in number of rounds. This is due to the even distribution of nodes across the network resulting in steady energy consumption. In comparison with LEACH, CBDAS, and PEGASIS, the proposed method maximizes the number of rounds approximately by 25.14%, 12.12%, and 46.2%, respectively.Figure 18
Total energy consumed.


## 4.1. Simulation Setup

To analyze the energy consumption of each node, first-order radio model [12] is used as shown in (9), (10), and (11), respectively. To run circuitry of the transmitter and receiver, a radio dissipates Eelec=50 nJ/bit, where Eelec is the circuit energy consumption. At the sender node, transmission amplifier further consumes Eampd2 amount of energy where Eamp is the consumption of energy while transmitting packets (Eamp=100  pJ/bit/m2) and d is the distance between nodes. To transmit k bits of message over a distance d by using first-order radio model, the transmission energy consumed (ETX) is given by the following:(9)ETXk,d=Eelec×k+Eamp×k×d2.Energy consumption at the receiving end (ERX) is shown as(10)ERXk=Eelec×k.Total transmission consumption is generalized as follows:(11)Etotalk=Eelec×k+Eamp×k×d2+Eelec×k.Performance results for different metrics have been obtained by varying certain parameters: initial energy, grid size, number of nodes, network lifespan, and total energy consumed. These parameters are discussed in the following.


## 4.2. Effect of Initial Energy

The initial energy of all nodes is set to 0.25 J, 0.5 J, and 1.0 J for evaluating Direct, LEACH, CBDAS, PEGASIS, and our proposed method (GHND) to determine the number of rounds when 1%, 25%, 50%, 75%, and 100% nodes of the network die. Figures6, 7, and 8 show that our proposed method has larger number of rounds than other techniques. This is because the control messages are reduced in ZH selection and reselection process. This increases the number of rounds and maximizes network lifetime as shown in Figures 6, 7, and 8.Figure 6
Number of rounds when 1%, 25%, 50%, 75%, and 100% nodes die in the network with initial energyE0=0.25 J.Figure 7
Number of rounds when 1%, 25%, 50%, 75%, and 100% nodes die in the network with initial energyE0=0.5 J.Figure 8
Number of rounds when 1%, 25%, 50%, 75%, and 100% nodes die in the network with initial energyE0=1.0 J.


## 4.3. Effect of Grid Size

To evaluate the impact of grid size, whole sensor field is partitioned into grid sizes of6×6, 8×8, and 10×10 grids as illustrated in Figures 9, 10, and 11. LEACH is not included in this evaluation as it is not a grid-based protocol. The proposed technique is better than other approaches in terms of number of rounds achieved as shown in Figures 9, 10, and 11. In all three approaches the proposed technique has achieved maximum number of rounds thereby improving network lifetime. This technique is approximately 1.3, 1.2, and 1.4 times better than CBDAS approach for grid sizes 6×6, 8×8, and 10×10, respectively. In comparison, grid size 10×10 has the maximum number of rounds among the three approaches by keeping the same parameters such as number of nodes (300), initial energy (E0=0.5 J), and packet size (2000 bits).Figure 9
Effect of grid size with respect to number of nodes. Here grid size =6×6.Figure 10
Effect of grid size with respect to number of nodes. Here grid size =8×8.Figure 11
Effect of grid size with respect to number of nodes. Here grid size =10×10.


## 4.4. Effect of Number of Nodes

In each approach, the effect of node density and initial energy is found out. In this case the number of nodes is varied from 100 to 500 with different initial energy values 0.25 J, 0.5 J, and 1.0 J. Figures12, 13, and 14 show the number of rounds from nodes 100 to 500 with initial energy values 0.25 J, 0.5 J, and 1.0 J, respectively. The graphs in these figures show that, for every approach, the number of rounds increases by increasing the node density except for the Direct method where comparatively very small change is detected in the number of rounds. In all these figures, GHND has more number of rounds than other approaches for all cases of node density and initial energy. The resulting network has better lifetime because, by increasing the node density, the responsibilities of each zone head is distributed.Figure 12
Effect of number of nodes with respect to initial energy.E0=0.25 J.Figure 13
Effect of number of nodes with respect to initial energy.E0=0.5 J.Figure 14
Effect of number of nodes with respect to initial energy.E0=1.0 J.


## 4.5. Network Lifespan

To analyze the network lifespan against each method, various simulations were run for different initial energy values (0.25 J, 0.50 J, and 1.0 J) for 100 nodes and packet size of 2000 bits. In Figures15, 16, and 17, the proposed method GHND has maximum number of rounds resulting in prolonged network lifetime. This shows that the proposed method surpasses the currently employed approaches in load balancing, in energy efficiency, and in prolonging the lifetime.Figure 15
Network lifespan with respect to initial energy.E0=0.25 J.Figure 16
Network lifespan with respect to initial energy.E0=0.5 J.Figure 17
Network lifespan with respect to initial energy.E0=1.0 J.


## 4.6. Total Energy Consumed

Figure18 shows total energy consumed (in sensing, computation, and communication) plotted against the number of rounds for total nodes. The graph shows that energy consumed by the proposed method is less than other approaches with increase in number of rounds. This is due to the even distribution of nodes across the network resulting in steady energy consumption. In comparison with LEACH, CBDAS, and PEGASIS, the proposed method maximizes the number of rounds approximately by 25.14%, 12.12%, and 46.2%, respectively.Figure 18
Total energy consumed.


## 5. Conclusion and Future Work

In this paper, we have proposed a grid-based hybrid network deployment framework for load balancing to ensure energy efficiency in WSN. For a random node deployment scenario, the proposed method constructs a grid by dividing the deployment area into zones. All the nodes are associated with their respective zones by the BS. To evenly distribute load across the network, low density zones are merged with their neighboring zones and high density zones are split into subzones. Merge and split technique is used to solve the hotspot problem. Once the network topology is constructed, node with maximum CV is selected as ZH across every zone. The overhead messages and reselection process are simplified in our approach which helps to maximize network lifetime. The proposed method is compared with other approaches such as LEACH, PEGASIS, CBDAS, and Direct. Simulation results show that the proposed method is better than the above-mentioned state-of-the-art techniques by evenly placing ZH across the field and balanced grid formation. Our algorithm also outperforms these approaches in terms of varying initial energy, grid dimensions, node density, network lifetime, and total energy consumption.This work will also be extended as an underlying topology for other energy efficient routing and load balancing protocols. In addition, further research is needed to make the network framework adaptive by automatically optimizing IBG, lower bound, upper bound, and number of grids for a given number of nodes and network area.



---

*Source: 2326917-2016-10-18.xml*