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

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.

[ProQuest: [...] denotes non US-ASCII text; see PDF]

Haleem Farman 1 and Huma Javed 1 and Jamil Ahmad 2 and Bilal Jan 3 and Muhammad Zeeshan 4

Academic Editor:S. Khan

1, Department of Computer Science, University of Peshawar, Peshawar, Pakistan

2, College of Electronics and Information Engineering, Sejong University, Seoul, Republic of Korea

3, Department of Computer Science and IT, Sarhad University of Science and Information Technology, Peshawar, Pakistan

4, Institute of IT, Kohat University of Science and Technology, Kohat, Pakistan

Received 19 June 2016; Accepted 28 August 2016

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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. Section 2 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 avoid hotspot 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 of hotspot , 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 overcomes hotspot 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.

[figure omitted; refer to PDF]

3.1. Deployment Phase

The total number of nodes N (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 Algorithm 1. We propose a novel technique for grid formation which is further divided into two main steps.

Algorithm 1: Zone formation.

(1) procedure Zone Formation

(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-1)mod[...]M]+1

(6) _Zxs =C[low *]ZH-ZW

(7) _Zys =R[low *]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/grids

: Zn: zone number

: Nz: number of nodes per zone

: _ZHT : number of zone heads

: _FH : height of field

: _FW : width of field

: _ZH : height of each zone/grid

: _ZW : width of each zone/grid

: R: rows

: C: columns

: M: dimension of the field

: SC: candidate for splitting

: _Zxs , _Zys : starting coordinates of zone

: _Zxe , _Zye : ending coordinates of zone

: nz: neighboring zone

: (_nx ,_ny ): coordinates of a node

: (_ZCx ,_ZCy ): centroid coordinates of a zone

Each 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 Algorithm 1. 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 [figure omitted; refer to PDF]

Figure 2: Zone formation.

[figure omitted; refer to PDF]

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 in hotspot 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, [figure omitted; refer to PDF] 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 towards hotspot problem. To address the hotspot 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. Algorithm 2 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, [figure omitted; refer to PDF]

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-1)mod[...]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 -_ZCx )2} +^{(_ny -_ZCy )2}

(12) den=zone_density(_nz(i) )

(13) WMS=((D[low *]dist)+(σ[low *]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 procedure

Figure 3: Nodes in low density zones are merged with neighboring zones.

[figure omitted; refer to PDF]

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 Algorithm 3. 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 4^{5[composite function]} 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-1)mod[...]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 (4^5° )

(19) Go to End

(20) end if

(21) if (ORR≥0.75 and <=1) then

(22) Split diagonally (13^5° )

(23) Go to End

(24) end if

(25) end if

(26) end procedure

Figure 4: Optimal order for splitting.

[figure omitted; refer to PDF]

Figure 5: Nodes distribution after merging and splitting of zones.

[figure omitted; refer to PDF]

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 Figure 5, the merging and splitting of zones is shown by different colors. Nodes having same color imply that they belong to the same zone. Density of Zone 13 is less than LB and is merged with Zone 14 . The number of nodes in Zone 1 and Zone 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 node i as follows: [figure omitted; refer to PDF] 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 [figure omitted; refer to PDF] 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 [figure omitted; refer to PDF] where cent(i,c) is the center of zone. In order to know the position of the node in its zone, consider [figure omitted; refer to PDF] 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 Zone Head selection

(2) Input : Cumulative Value of node, CV; Threshold Value,

TV; Calculate CV of all Nodes

Zon_e(i) = [CVs of all nodes in _ZH(i) ]

/^{[low *]} select node with maximum CV ^{[low *]} /

_ZH(i) =CV_max(i)

BS exchange Collection list and TV with _ZH(i)

Member nodes register with _ZH(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 Algorithm 5. 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 Zone Head Reselection

(2) Input : Energy Level of Current Zone Head, oldE_LZH ; Threshold Value, TV;

Cumulative Value of each node, CV; Candidate Zone Head, CZH;

difference of Initial and updated CV, X;

(3) if (newE_LZH =oldE_LZH -oldE_LZH ×0.1) then

(4) if E_LZH <=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[arrow left]member_node

(13) ZHnew[arrow left]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 Algorithm 5 the value of X is calculated as in the following equation: [figure omitted; refer to PDF] 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 _Eamp^d2 amount of energy where _Eamp is the consumption of energy while transmitting packets (_Eamp =100 pJ/bit/m² ) 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 (E_TX ) is given by the following: [figure omitted; refer to PDF]

Energy consumption at the receiving end (E_RX ) is shown as [figure omitted; refer to PDF]

Total transmission consumption is generalized as follows: [figure omitted; refer to PDF]

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. Figures 6, 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 energy _E0 =0.25 J.

[figure omitted; refer to PDF]

Figure 7: Number of rounds when 1%, 25%, 50%, 75%, and 100% nodes die in the network with initial energy _E0 =0.5 J.

[figure omitted; refer to PDF]

Figure 8: Number of rounds when 1%, 25%, 50%, 75%, and 100% nodes die in the network with initial energy _E0 =1.0 J.

[figure omitted; refer to PDF]

4.3. Effect of Grid Size

To evaluate the impact of grid size, whole sensor field is partitioned into grid sizes of 6×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 omitted; refer to PDF]

Figure 10: Effect of grid size with respect to number of nodes. Here grid size = 8×8.

[figure omitted; refer to PDF]

Figure 11: Effect of grid size with respect to number of nodes. Here grid size = 10×10.

[figure omitted; refer to PDF]

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. Figures 12, 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 omitted; refer to PDF]

Figure 13: Effect of number of nodes with respect to initial energy. _E0 =0.5 J.

[figure omitted; refer to PDF]

Figure 14: Effect of number of nodes with respect to initial energy. _E0 =1.0 J.

[figure omitted; refer to PDF]

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 Figures 15, 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 omitted; refer to PDF]

Figure 16: Network lifespan with respect to initial energy. _E0 =0.5 J.

[figure omitted; refer to PDF]

Figure 17: Network lifespan with respect to initial energy. _E0 =1.0 J.

[figure omitted; refer to PDF]

4.6. Total Energy Consumed

Figure 18 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.

[figure omitted; refer to PDF]

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.

References

[1] H.-Y. Kim, "An energy-efficient load balancing scheme to extend lifetime in wireless sensor networks," Cluster Computing , vol. 19, no. 1, pp. 279-283, 2016.

[2] F. Chiti, R. Fantacci, R. Mastandrea, G. Rigazzi, Á. S. Sarmiento, E. M. M. López, "A distributed clustering scheme with self nomination: proposal and application to critical monitoring," Wireless Networks , vol. 21, no. 1, pp. 329-345, 2015.

[3] M. Younis, I. F. Senturk, K. Akkaya, S. Lee, F. Senel, "Topology management techniques for tolerating node failures in wireless sensor networks: a survey," Computer Networks , vol. 58, no. 1, pp. 254-283, 2014.

[4] X. Liu, "A survey on clustering routing protocols in wireless sensor networks," Sensors (Switzerland) , vol. 12, no. 8, pp. 11113-11153, 2012.

[5] N. Zaman, T. J. Low, T. Alghamdi, "Enhancing routing energy efficiency of wireless sensor networks," in Proceedings of the 17th International Conference on Advanced Communications Technology (ICACT '15), pp. 587-595, IEEE, Seoul, Republic of Korea, July 2015.

[6] M. Pant, B. Dey, S. Nandi, "A multihop routing protocol for wireless sensor network based on grid clustering," in Proceedings of the 2nd International Conference on Applications and Innovations in Mobile Computing (AIMoC '15), pp. 137-140, Kolkata, India, February 2015.

[7] J.-Y. Chang, P.-H. Ju, "An energy-saving routing architecture with a uniform clustering algorithm for wireless body sensor networks," Special Section: Integration of Cloud Computing and Body Sensor Networks; Guest Editors: Giancarlo Fortino and Mukaddim Pathan Future Generation Computer Systems , vol. 35, pp. 128-140, 2014.

[8] W. R. Heinzelman, A. Chandrakasan, H. Balakrish-Nan, "Energy-efficient communication protocol for wireless microsensor networks," in Proceedings of the IEEE 33rd Annual Hawaii International Conference on System Sciences (HICSS '00), vol. 2, pp. 10, January 2000.

[9] S. Lindsey, C. S. Raghavendra, "PEGASIS: power-efficient gathering in sensor information systems," in Proceedings of the IEEE Aerospace Conference, vol. 3, pp. 3-1125-3-1130, IEEE, March 2002.

[10] Y.-K. Chiang, N.-C. Wang, C.-H. Hsieh, "Cycle-based data aggregation for grid-based wireless sensor networks," in Proceedings of the 7th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS '13), pp. 348-353, July 2013.

[11] T. P. Sharma, R. C. Joshi, M. Misra, "GBDD: grid based data dissemination in wireless sensor networks," in Proceedings of the 16th International Conference on Advanced Computing and Communications (ADCOM '08), pp. 234-240, IEEE, Chennai, India, December 2008.

[12] W. B. Heinzelman, A. P. Chandrakasan, H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," IEEE Transactions on Wireless Communications , vol. 1, no. 4, pp. 660-670, 2002.

[13] S. D. Muruganathan, D. C. F. Ma, R. I. Bhasin, A. O. Fapojuwo, "A centralized energy-efficient routing protocol for wireless sensor networks," IEEE Communications Magazine , vol. 43, no. 3, pp. S8-S13, 2005.

[14] W. Wang, B. Wang, Z. Liu, L. Guo, W. Xiong, "A cluster-based and tree-based power efficient data collection and aggregation protocol for wireless sensor networks," Information Technology Journal , vol. 10, no. 3, pp. 557-564, 2011.

[15] R. N. Enam, R. Qureshi, S. Misbahuddin, "A uniform clustering mechanism for wireless sensor networks," International Journal of Distributed Sensor Networks , vol. 10, no. 3, 2014.

[16] J. Zeng, "A clustering method of combining grid and genetic algorithm in wireless sensor networks," Proceedings of the International Conference on Information Engineering and Applications (IEA) 2012: Volume 3 , vol. 3, pp. 773-779, Springer, London, UK, 2013.

[17] G. Jain, S. R. Biradar, B. K. Chaurasia, "Transactions on computational science XXV," Cluster Head Selection Heuristic Using Weight and Rank in WSN , pp. 135-147, Springer, Berlin, Germany, 2015.

[18] J. Yu, Y. Qi, G. Wang, Q. Guo, X. Gu, "An energy-aware distributed unequal clustering protocol for wireless sensor networks," International Journal of Distributed Sensor Networks , vol. 7, no. 1, 2011.

[19] S. Soro, W. B. Heinzelman, "Prolonging the lifetime of wireless sensor networks via unequal clustering," in Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS '05), pp. 8, IEEE, April 2005.

[20] A. Thonklin, W. Suntiamorntut, "Load balanced and energy efficient cluster head election in wireless sensor networks," in Proceedings of the 8th Electrical Engineering/ Electronics, Computer, Telecommunications and Information Technology (ECTI '11), pp. 421-424, Khon Kaen, Thailand, May 2011.

[21] P. Chatterjee, N. Das, "Coverage constrained non-uniform node deployment in wireless sensor networks for load balancing," in Proceedings of the 1st International Conference on Applications and Innovations in Mobile Computing (AIMoC '14), pp. 126-132, Kolkata, India, February 2014.

[22] K. Haseeb, K. Abu Bakar, A. H. Abdullah, T. Darwish, "Adaptive energy aware cluster-based routing protocol for wireless sensor networks," Wireless Networks , 2016.

[23] A. Thakkar, K. Kotecha, "A new Bollinger Band based energy efficient routing for clustered wireless sensor network," Applied Soft Computing , vol. 32, pp. 144-153, 2015.

[24] W. Z. W. Ismail, S. A. Manaf, "Study on coverage in wireless sensor network using grid based strategy and particle swarm optimization," in Proceedings of the Asia Pacific Conference on Circuits and System (APCCAS '10), pp. 1175-1178, IEEE, Kuala Lumpur, Malaysia, December 2010.

[25] N. Wang, Y. Chiang, C. Hsieh, "A path-based approach for data aggregation in grid-based wireless sensor networks," Journal of Electronic Science and Technology , vol. 12, no. 3, pp. 313-317, 2014.

[26] C. Chen, Z. He, H. Sun, J. Kuang, D.-M. Bai, C. Yang, "A grid-based energy efficient routing protocol in Wireless Sensor Networks," in Proceedings of the International Symposium on Wireless and Pervasive Computing (ISWPC '13), pp. 1-6, Taipei, Taiwan, November 2013.

[27] H. Lin, L. Wang, R. Kong, "Energy efficient clustering protocol for large-scale sensor networks," IEEE Sensors Journal , vol. 15, no. 12, pp. 7150-7160, 2015.

[28] S. Jannu, P. K. Jana, "Energy efficient grid based clustering and routing algorithms for wireless sensor networks," in Proceedings of the 4th International Conference on Communication Systems and Network Technologies (CSNT '14), pp. 63-68, IEEE, Bhopal, India, April 2014.

[29] J. Yu, Y. Qi, G. Wang, X. Gu, "A cluster-based routing protocol for wireless sensor networks with nonuniform node distribution," AEU--International Journal of Electronics and Communications , vol. 66, no. 1, pp. 54-61, 2012.

[30] N. Nokhanji, Z. M. Hanapi, S. Subramaniam, M. A. Mohamed, "A scheduled activity energy aware distributed clustering algorithm for wireless sensor networks with nonuniform node distribution," International Journal of Distributed Sensor Networks , vol. 10, no. 7, 2014.

[31] J. Chang-Jiang, S. Wei-Ren, T. Xian-Lun, W. Ping, X. Min, "Energy-balanced unequal clustering routing protocol for wireless sensor networks," The Journal of China Universities of Posts and Telecommunications , vol. 17, no. 4, pp. 94-99, 2010.