A Partition Based Unequally Clustered Multi-Hop Routing Protocol for Wireless Sensor Networks

A Partition Based Unequally Clustered Multi-Hop Routing Protocol for Wireless Sensor Networks

U. Hari1, Chris Johnson A2

Department, of ECE SRM University Tamil Nadu, India

Abstract

Due to limited energy in Wireless Sensor Networks (WSN) many new protocols specifically have been designed for improving energy efficiency. Clustering is a routing technique that promises to reduce the energy consumption. Most Clustering algorithms provide an equal cluster size using nodes ID, residual energy etc. Unequal Clustering provides a way to mitigate the hotspot problem. In this paper we propose a simple clustering algorithm , called partition based unequal clustering multi-hop routing protocol (PUCMR) protocol. To address the problem that the cluster-heads are distributed unevenly in the network and to improve the network lifetime, base station firstly partitions the network monitored area into optimum number of unequal clusters through the partition algorithm. Simulation results show that PUCMR achieves better network lifetime than unequal clustering algorithm.

Keywords

Unequal clustering, multi-hop routing, hot spots, partition, QoS parameters.

1. Introduction

   A wireless sensor network (WSN) consists of large number of low power, low cost sensor nodes (SNs). Generally such SNs are deployed in hostile, inhabitable and harsh environment, with a common objective to sense, collect and transmit data for end users located at a far distance. In recent years, researchers have a lot of studies and proved that clustering is an effective scheme to improve the life time and scalability of the network [1-2]. Clustering protocols deal with organizing nodes into clusters, selecting one node as cluster head (CH) in every cluster, sending data to Base station(BS) through CH. Clustering has been shown to

   improve network lifetime by aggregating data, reducing communication overhead and organizing routing paths efficiently. In [2], it is shown that clustering and data aggregation at least double the network lifetime.

   In order to save the transmission power multi-hop transmission mechanisms are used. The nodes which are farthest from the sink node are most critical nodes in single hop communication, while in multi-hop transmission[3,4] the nodes closest to the sink are burdened with a heavy relay traffic load and die soon and gives rise to hot spot problem.

   To overcome this hot spot problem unequal clustering mechanism is proposed [6,7]. The unequal clustering algorithm organizes the network with size of the cluster varying with the distance of cluster increasing from the sink node.

   This paper proposes a partition based unequal clustered multi-hop routing algorithm (PUCMR). Unlike other unequal clustering, it is not only mitigating hot spot problem, but the issue of uneven cluster head distribution is also eliminated. The proposed PUCMR algorithm uses energy, degree of a node and centroid distance for selection of cluster head and provides a better position in the network. Simulation results shows that our approach extends the network life time.

   The rest of the paper is organized as follows; section II describes the related works, section III describes the problem formulation, section IV describes the system network model and section V presents PUCMR algorithm in detail. Section VI analyze the performance of the PUCMR algorithm.

2. Literature Review

   In the WSN, many clustering algorithms have been proposed in the past few years in order to improve network life time. But less work have been carried out

   to enhance to QoS metrics. The method of clustering in WSN consists of several aspects that depend on the structure and the requirements of particular application. The LEACH[1] is the first proposed clustering algorithm which guarantees the maximum network life time with even load distribution in whole network. The cluster head role is periodically rotated among sensor nodes. It is assumed that all the nodes have necessary processing capabilities and able to coordinate intra cluster transmission aggregation of data. However the uneven distribution of CHs results in unbalanced energy consumption and partitioning in the deployed

   network.

   Mhatre et al. [5] present a comparative study of homogenous and heterogeneous networks in terms of overall cost of the network. They analyze both single hop and multi hop networks. The authors use LEACH as a representative of a homogenous, single hop network, and they compare LEACH with a heterogeneous single hop network. The authors conclude that using multi hop LEACH outperforms single hop LEACH when propagation loss index k is large (k >2).

   EEUC [7] is a distributed unequal clustering algorithm which elects cluster heads based on the residual energy of nodes. Each node becomes a tentative cluster head with a probability T. Tentative cluster heads use uneven competition ranges to construct clusters of uneven sizes. The clusters closer to the BS have smaller sizes than those farther away from it, thus the cluster heads closer to the BS can preserve some energy for the inter-cluster data forwarding. In this way, the energy consumption among cluster heads is balanced. The quality of the generated cluster heads is affected by T, and affects the network lifetime some case of T.

   This paper addresses the issue of improper placement of cluster heads in EEUC. Due to this network is not covered properly and results in lower network lifetime. To solve this issue partitioning concept is introduced. The proposed concept results in better network coverage and promises increase in network lifetime.

3. Problem Formulation

   A fundamental problem in WSN is to maximize the network life time under given energy constraints. In order to achieve this energy consumption must be well balanced among the nodes. By rotating the CHs role dynamically we can obtain balanced energy consumption. But still in uniform clustering, this may lead to hot spot problem. So we choose unequal clustering algorithm like EEUC. But still the number

   of CHs and their position should be optimum, since having many number of CHs also drain out the energy of nodes and position of the CH is important for network coverage. So we propose PUCMR algorithm to overcome this problem, by partitioning the network into optimum number of clusters. We use shortest path algorithm in the network for intra cluster communication between CH and member nodes as well as for inter cluster communication between CHs for multi hop transmission, of data to Base Station.

4. System Model

   To simplify the network mode, let us consider a wireless sensor networks consists of N sensor nodes and adopt some reasonable assumptions about the network.

   • N nodes are uniformly distributed with a square area MxM. BS is far away and are at corner of network.

   • All the nodes and BS are stationary

   • All the nodes are homogeneous and have the same capabilities and initial energy.

   • Each node is assigned with a unique ID.

   Figure 1: Model of the unequal clustered network.

   The size of the cluster is increasing with the distance from base station increases.

   The RF energy analytical model of transceiver unit in sensor node is given in [1]. The energy spent for transmitting l bits over a distance d is

   l*Eelec + l*Efs*d2, d < do

   ETx(l,d) =

   l*Eelec + l*Emp*d4, d do, (1)

   maximum value of the weight Wi and it informs the appropriate node as cluster head for next round. After cluster head has been selected it broadcasts CH_ADV

   where Eelec is energy consumed to transmit or receive a bit, Efs is transmitter amplifier energy for free-space, Emp is transmitter amplifier energy for multipath and do=(Efs/Emp) = 87m as in[1].

   While receiving l bits, radio consumes energy of

   ERx = l * Eelec (2)

   In addition the cluster head consumes EDA J/bit for data aggregation.

5. Partition based Unequal Clustered Multi- hop Routing protocol

   The partition based unequal clustered multi-hop algorithm configures cluster heads in every round. The process is divided into two phases, such as cluster setup phase and data transmission phase.

   1. Cluster formation Phase

      Initially the base station partitions the network into optimum number of clusters. It then broadcasts the hello packet to all the nodes throughout the network. This packet contains node-ID, cluster ID, initial energy Eo, number of neighbouring nodes or node degree Di and distance to centroid Ci.

      In this phase a node with maximum weight (Wi) in each partitioned cluster becomes cluster head(CH). The cluster head selection is performed by computing the weight of node i. The node with maximum weight in a cluster is selected as

      packet. Then each CH receives JOIN_REQ packet, which contains the node ID and cluster ID from all member nodes.

   2. Data Transmission Phase

      Data transmission starts after cluster formation phase ends.This phase consists of two sub-phases.

      1. intra-cluster transmission

      2. inter-cluster transmission

      1. Intra- cluster transmission

         Each cluster head initially computes the distance, d for all member nodes and searches for any node which is located beyond critical distance dCM. If cluster head finds any member node with d dCM in the sector then it finds shortest path to those nodes with multi-hop routing. Then it sends a control packet to the relay node with node-Id of multi-hop node. If the multihop node has data to transmit then it transmits data to relay node. The relay node combine the data with its own data and it transmits to its cluster head.

      2. Inter-cluster transmission

      The cluster head collects data from all the member nodes and perform data fusion. The CH sends the aggregated data to base station through multi-hops. A critical distance (dcc) is introduced. If a nodes distance to the base station is smaller than dcc, it transmits its data to the base station directly; otherwise its better to find a relay node which can forward its data to the base station.

      The neighboring cluster head set SCH of cluster head si is defined as

      si .SCH = {s j | d(si , s j ) xSi , d(s j , BS) < d(si , BS)} (4)

      Di

      Di

      Wi 1 P

      P

      1

      1

      Ck

      • P k 1

        C

      • Eri

      E

      (3)

      x is the minimum integer that lets si .SCH

      contain at

      P

      P

      Dk i 0

      k 1

      where Eri is the remaining energy of node i, Eo is the initial energy, Di is the degree of the node, Ci is the distance of the node from the centroid of the cluster and P is the number of nodes in cluster. In the subsequent rounds the new cluster head in a cluster is chosen by the cluster head of previous round. The CH of the existing round receives remaining energy Eri from all the member nodes. Then using tables of degree Di, and distance to the centroid Ci of each node in the sector the CH computes the weight Wi. Then it selects the

      least one neighbor cluster head. (if there doesnt exist such an x, cluster head si will send its own data together with forwarding data directly to the base station).

      The relay node with more residual energy balances the energy consumption and extends the network lifetime. On the other hand, decreasing the energy cost per packet also contributes to the network lifetime. A greedy geographic forwarding algorithm that aims to minimize the energy cost per packet. Suppose si chooses sj as its relay node. The energy consumed by si and sj in delivering l bits to base station is same as equation in[1].

      Erelay(si , sj ) = d2(si , sj ) + d2(sj , BS) (5)

      The bigger the Erelay is, the more energy will be consumed for transmitting packets on the path. So the selection of relay node sj for cluster si from si .SCH is important. The choice of eligible cluster head from the set si.SCH is given by

      si .Seligible={sj | sj si.SCH, Erelay(si,sj) is smallest} (6)

      The energy consumption of a single cluster is divided into four parts. The energy consumption of broadcasting the shortest path is

      ECH-C = lc* Eelec + lc*Efs * d2 CH (7) where dCH is the distance between cluster head and

      the member node and lc is the length of control packet. The energy consumption of receiving the shortest path table, by member nodes in a single cluster is

      EM-C = lc* Eelec * (Nk 1 ) (8) where Nk is the number of nodes in the

      partitioned cluster k. The energy consumption by

      cluster head node on receiving packets from all member nodes in one cluster is

      ECH-D = l * Eelec * Nk + EDA* l * Nk + l*Efs d2 (9)

      where d is the distance of the neighbouring cluster head for multi-hop data transmission. The energy spent by member nodes for transmitting data packets to the cluster head is

      CH

      CH

      EM-D = l * (Nk 1) * Eelec + l *( Nk 1) * Efs d2 (10)

      The total energy consumed by the cluster is the sum of all above energy equations

      Ec= ECH-C + EM-C + ECH-D + EM-D (11)

      The rate of energy consumption (ER) by a node in the network is given by the equation

6. Simulation Results

In this section, the performance of PUCMR which is implemented in MATLAB. The simulation parameters are listed in Table I and the parameters of the radio model are same as LEACH. The view of the simulated topology of the network is shown in Figure

1. Life time is the important criteria for evaluating the performance. The network life time is shown in the Figure 3. which justifies that our proposed algorithm PUCMR increases network lifetime 83% than LEACH as well as 39% than unequal clustering algorithm(EEUC) respectively. The reason to increase life time of network is better positioning of the cluster heads. After the first node dead the energy is more evenly distributed than LEACH and EEUC protocols. Figure 4 shows the rate of energy consumption of a node in PUCMR, LEACH and EEUC. It is shown that energy consumption of a node per round in PUCMR is lesser than EEUC and LEACH. So PUCMR algorithm is simple as well as it uses various parameters such as remaining energy, number of neighbour nodes and position of sensors to select CH which in turn enhances the network lifetime.

   Figure 2: PUCMR protocol deployed network

   ER E0 Eri

   E0

   (12)

   where E0 is the intial energy and Eri is the residual energy.

   International Journal of Engineering Research & Technology (IJERT)

   ISSN: 2278-0181

   Vol. 2 Issue 5, May – 2013

   Figure 3: Number of Alive nodes comparison

   Figure 4: Rate of Energy Consumption Table 1: Simulation Parameters

   Parameter	Value
   Network Coverage	200m X 200m
   BS location	100m, 220m
   N	100
   Initial Energy, Eo	1J
   Eelec	50nJ/bit
   Efs	10pJ/bit/m2
   Emp	0.0013pJ / bit/m4
   do	87m
   EDA	5nJ/bit
   Data packet size	4096 bits
   Control packet size	200 bits

   1. Conclusion and Future Work

      In this paper a prtition based unequal clustering mechanism that enables a node to have multi-hop for intra-cluster and inter-cluster data transmission is proposed. This unequal clustering topology strategy is based on remaining energy,

      node degree and distance from the centroid. This is a simple multi-hop unequal clustering algorithm which provides balanced energy consumption among the CHs and mitigates hot spot problem. The multi-hop transmission in this protocol can improve QoS parameters like error and data rates. Simulation results shows that PUCMR extends the network life time better than EEUC and LEACH protocols by 39% and 83% respectively.

      Network performance like latency, robust network are still to be improved. Cooperative MIMO has gained considerable importance in WSN for its high efficiency, low power. As future work, improvements in QoS parameters like latency will be investigated with Cooperative MIMO.

   2. References

[1]. W. Heinzelman, et. al.,An application-specific protocol architecture for wireless microsensor networks", IEEE Transactions on Wireless Communications, 1(4):660-669, 2002.

[2]. Ossama Younis, and Sonia Fahmy, "HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks", IEEE Transaction on Mobile Computing,Vol.3, No.3, pp 349- 366, 2004.

[3]. Guitang Wang et al,The Clustering Algorithm of Wireless Sensor Networks Based on Multi-Hop between Clusters, in proc.of WCCSIE-2009,IEEE computer society,pp 177-181.

[4]. Dilip kumar and RB patel,Multi-hop data communication algorithm for clustered wireless sensor networks, International Journal of Distributed sensor networks,.Article id 984795, pp 1-10,2011.

[5]. V. Mhatre, C. Rosenberg, "Homogenous vs. Heterogeneous Clustered networks: A comparative study," in Proceedings of IEEE ICC, June 2004.

[6].S Lee et al,LUCA:An energy efficient unequal clustering algorithm, using location information for WSN,in Springer,Wireless personal communication, vol-56,pp 715-731,2011

[7]. Li C F , et al, "An energy-efficient unequal clustering mechanism for wireless sensor networks"

,Proceedings of the 2nd IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS 2005) , Washington , DC ,2005[C] .