Energy Efficient Cluster Based Partial Multihop Algorithm for Hetrogeneous (CPMH) WSN

M. Vasim Babu

Department of Computer Science, Latha Mathavan Engineering College, Madurai (India).

ABSTRACT:

A Wireless Sensor Network (WSN) consists of spatially distributed autonomous sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants. In recent years, there has been a growing interest in wireless sensor networks. One of the major issues in wireless sensor network is developing an energy-efficient routing protocol. The challenge lies in efficiently providing acceptable accuracy while conforming to the many constraints of WSNs. Energy limited is one main bottle-neck for wireless sensor networks. Due to unreasonable cluster head electing and intensive energy consumption of cluster head in clustering algorithm, I propose cluster based partial multihop algorithm for heterogeneous WSN, Which aimed to optimize cluster head voting and balance energy consumption of cluster head. I also propose a hierarchical tree routing method that reduces the distance of cluster-head to the base station.

KEYWORDS: Energy; Routing; Multihop; Partial Cluster selection; heterogeneous

Copy the following to cite this article: Babu M. V. Energy Efficient Cluster Based Partial Multihop Algorithm for Hetrogeneous (CPMH) WSN. Orient. J. Comp. Sci. and Technol;4(1)

Copy the following to cite this URL: Babu M. V. Energy Efficient Cluster Based Partial Multihop Algorithm for Hetrogeneous (CPMH) WSN. Orient. J. Comp. Sci. and Technol;4(1). Available from: http://www.computerscijournal.org/?p=2376

Introduction

Current WSN has become hot in researching. Wireless sensor network collect data to base station by deploying sensor nodes that arrangement themselves in certain region. In WSN, sensor nodes with some initial energy deployed randomly. It is difficult to add energy while the node deployed, so saving energy is very important. Clustering is an important energy-saving method in WSN, and the good performance of WSN is highly dependent on energy efficient clustering routing algorithm¹. Clustering structure can aggregate data efficiently and achieve network load balance². Clustering algorithm is to select a part of nodes in WSN as cluster heads and classify all the nodes reasonably.

Topology control is one of the key technologies in WSN, which consists of planar topology control and hierarchical topology control³.

Due to high conflict rate of data transmission and a demand of much neighbor information, planar topology control is given less attention. Compared to planar topology control, hierarchical topology control with low energy consumption, quickly topology forming, less information needs of neighbors, etc., become the research hot spots.

Recent rapid advances in technology have made it possible to integrate micro sensor, low-power signal processing, computation and low-cost wireless communication into a sensing device. Also, there are many research activities and projects that study sensor network applications. Habitat monitoring on Great Duck Island is one of the projects⁴. Wireless sensor networks usually contain thousands or millions of sensors, which are randomly and widely deployed. Sensors are powered bybattery, which is impossible to get recharged after deployment. But sensor networks are designed to last. Thus, energy efficiency is an important issue in sensor networks. Since routing consumes a lot of energy, an efficient routing scheme in sensor networks is also important.

In this paper, I develop a CPMH (cluster based partial multihop algorithm for heterogeneous WSN) routing protocol. It is a clustering-based protocol that tries to minimize the energy dissipation in sensor networks. The key features of CPMH are: energy dissipation reduction, self-configuration and localized coordination, maximum energy cluster head, hierarchical forwarding, and load balance.

Previous Work

Many clustering algorithms have been proposed for sensor networks in the last few years. Those algorithms consider both residual energy and position of nodes mostly based on different rules. According to the way of electing CHs, clustering algorithm can simply divided into centralized algorithm and distributed algorithm [1]. Centralized algorithm can generate cluster more reasonable, but it is only suitable for small networks. Because of the network must know the global information of the network in cluster processing. Distributed algorithm is suitable for large-scale networks which do not need to know the global information of the network, but it is difficult to control cluster structure. Many networks are large-scale networks⁵, so the study of distributed algorithms is very necessary. A variety of typical clustering algorithms have been proposed.

The problem of maintaining both area coverage and network connectivity under energy constraint in WSN has been extensively addressed in the literature and many protocols were proposed to alternate sensor states between active and sleep in order to maximize network lifetime. For example, Xing et al. [6] provide a geometric analysis of the relationship between coverage and connectivity, and propose the Coverage Configuration Protocol (CCP) that dynamically configures the network to guarantee different degrees of coverage depending on the application requirements. In CCP, every node decides its state (Active or Sleep) based on the coverage degree of the intersection points of its sensing circle with those of its neighbors. When coupled with any connectivity maintenance protocol, CCP offers connectivity and K-coverage. Lu et al. ⁶ present Scalable Coverage Maintenance (SCOM), a localized coverage maintenance algorithm where sensors use the same redundancy eligibility rule as in⁷ to decide whether to turn on or turn off. SCOM implements, for each sensor, a back-off timer proportional to its residual energy. The back-off timer allows sensors with lower residual energies to decide about their states before sensors with more energy, making them more likely to turn off than the other sensors, if they find themselves redundant. Chamam and Pierre ⁸ propose a centralized heuristic which dynamically calculates a near-optimal subset of sensors that guarantees a predefined coverage rate while ensuring network connectivity when the transmission range is greater than or equal to twice the sensing range. However, all the works cited above do not address cluster-based architectures. We can see that most of the above algorithms elect CHs firstly, and then common nodes as a member of a cluster by choosing CH based on certain rules. And this all the algorithm can not generated clusters flexibility and does not take into account the residual energy of nodes. This paper proposed a new clustering algorithm With Partial cluster selection which nodes within a sub-area of each cluster/cell are selected to form the connected dominating set (or virtual backbone). In many instances partial clustering is a generalized form of standard clustering, with tunable parameters. By limiting the selection to sub-areas within clusters, this approach imposes more structure on the formation of the backbone. In doing so it also achieves low duty cycle and a more flexible trade-off between energy efficiency and connectivity than standard clustering. The communication both intra-cluster and inter-cluster are in multi-hop way.

Pre-established Cluster-based Routing Algorithms

In this section, we reviewmost important clustering algorithms. Even if they are limited only tothe clusters formation and do not address explicitly inter-cluster routing. It is generally straightforward to apply on top of the clustered topology a routing protocol taking into account only the cluster heads in the route discovery phase.

Low-Energy Adaptive Clustering Hierarchy (LEACH)

(Energy-efficient communication protocol for wireless sensor networks, 2000) is one of themost popular hierarchical routing algorithms for sensor networks. LEACH is a cluster-based protocol with distributed cluster formation with random clusterhead election. A sensor node chooses a random number between 0 and 1. If this random number is less than a threshold value, T(n), the node becomes a clusterhead for the current round. This threshold value is calculated using :

where P is the desired fraction of nodes to be clusterheads, r is the current round and G is the set of nodes that have not been clusterheads in the last 1P round. The elected clusterheads broadcast an advertisement message to inform other nodes about their states. Based on the received signal strength of the advertisement, a non-clusterhead node decides to which cluster it will belong for this round and sends a membership message to its clusterhead. Based on the number of nodes in the cluster, a clusterhead creates a TDMA schedule and assigns each node a time slot in which it can transmit. This schedule is broadcast to all the cluster nodes. This is the end of the so-called advertisement or setup phase of LEACH. Then begins the steady state where different nodes can transmit their sensed data. LEACH clusterhead rotation assume a homogeneous network and can not ensure real load-balancing in case of nodes initially with different amount of energy. A node with very low energy becomes a clusterhead for the same number of rounds as other nodes with higher energy and will die prematurely. This could affect network coverage and connectivity.

LEACH-C

LEACH-C (Chandrakasan et al., 2002) is a centralized version of LEACH where only the advertisement phase differs. At this phase, each node sends information about its current location and residual energy level to the sink. Based on nodes location, the sink builds clusters using the simulated annealing algorithm (Murata, 1994) so the amount of energy required by member nodesto transmit their data to their respective clusterhead is minimized. Collected information about nodes energies allows the sink to discard those with energy below the average network energy. Consequently, energy load is evenly distributed among all the nodes.

Energy Efficient Hierarchical Clustering (EEHC)

Energy Efficient Hierarchical Clustering (EEHC) (Bandyopadhyay and Coyle, 2004) can be seen as an extension of LEACH with multi-hop intra clusters and a hierarchy of cluster heads to route data to the sink. In the single-level clustering of EEHC, each sensor in the network becomes a Volunteer cluster head with probability p. Itannounces this to the sensors within k hops radio range. Any sensor that receives such advertisements and is not itself a cluster head joins the closest cluster. If a sensor does not receive a clusterhead advertisement within a certain time duration it can infer that it is not within k hops of any volunteer cluster head and hence becomes a forced cluster head. Data transmission to the sinkcan be performed using multi-hop routing through cluster heads organization in a multi-level hierarchy rooted at the sink. To do so, the single-level clustering is repeated recursively at the level of cluster heads. This distributed process allows EEHC to have a time complexity of O(k1 +k2 +…+kh) where h is the number of levels and ki is the maximumnumber of hops between a member node and its cluster head in the ith level of hierarchy. Since spent energy in the network depends on p and k, the authors provide methods to compute the optimal values of these parameters that ensure minimum consumed energy. Simulation results showed significant energy saving when using the optimal parameter values.

Hybrid Energy-Efficient Distributed Clustering (HEED)

Both EEHC and LEACH do not consider energy in selecting cluster heads. HEED (Younis and Fahmy, 2004) brings one more step toward energy-efficient cluster-based routing with explicit consideration of energy. Selected cluster heads in HEED have relatively high average residual energy compared to member nodes. Additionally, HEED aims to get a well-distributed cluster heads set over the sensor field. Indeed, in HEED, the probability that two nodes within the transmission range of each other to be cluster heads is small. It is worth mentioning that the main drawback of LEACH is that the random election of cluster heads does not ensure their even distribution in the sensing field. It is quite possible to get multiple cluster heads concentrated in a small area. In this case, this area sensors are likely to exhaust their energy more quickly which may lead to insufficient coverage and network disconnection. Distributing cluster heads evenly in the sensing area is one important goal to be met in order to ensure load balancing and hence longer network lifetime. However, HEED suffers from a consequent overhead since it needs several iterations to form clusters. In each iteration, a lot of packets are broadcast.

Network Environments and Assumptions

Assume that a set of sensors are dispersed on a random monitoring region. We adopt the following same properties and assumptions about the network:

1. The nodes in the network are quasi-stationary.
2. Nodes left unattended after deployment.
3. All nodes begin with the same amount of energy and the amount of energy a cluster-head consumes is more than the amount of a non-cluster head.
4. All nodes can adjust transmitting power.
5. No limit of the number of hop.

Energy dissipation model of sensor nodes consists of sensor model, process model and radio model, as shown in Figure 1, while most of node’s energy is dissipated to transmit information. The operation of clustering algorithm is divided into rounds. Each round begins with a set-up phase when the clusters are organized, followed by a steady-state phase when data are transferred from the nodes to the cluster head and on to the BS. The steady-state phase is broken into frames, where nodes send their data to the cluster head at most once per frame during their allocated transmission slot. Once the cluster head receives all the data, it performs data aggregation to enhance the common signal and reduce the uncorrelated noise among the signals. The resultant data are sent from cluster head to the BS. The energy dissipation of communication is far greater than that of processing data [9], therefore, in this paper, we do not take into account the energy dissipation of processing data.

Figure 1: Energy dissipation of nodes Click here to View figure

 

The energy dissipated in each cluster head during a single frame is

where k is the number of bits in each data message, E_elec is the energy dissipation to run the electronics, M is number of non-cluster head nodes in each cluster. Therefore, The energy dissipation of all non-cluster head nodes of each cluster during a single frame is

E_elec depends on factors such as the digital coding, modulation, filtering, and spreading of the signal, whereas ξ_amp depends on the distance to the receiver and M depends on the needs of network. Based on the above analysis, we reduce that energy dissipation can be brought down by reducing the value of Σ dⁿ_iCH

Multi-hop Partial  clustering algorithm

In order to design good algorithm for WSN, multi-hop Partial clustering algorithm assume the following techniques to achieve the design goals stated: 1) each node can use power control to set the transmit power and evaluate the distance by the transmit ; 2) each node is equipped with directional antennas, which can evaluate orientation information from the receiving signal; 3) each node can perform data aggregation and compression to fuse the receiving data packets and its own data packet into a constant data packet . Furthermore, each node owns a different ID. The operation of multi-hop clustering algorithm is also divided into rounds. Each round includes two phases: cluster head selection phase, cluster formulation phase.

Cluster head selection

In the cluster head selection phase, two bound variables: node’s residual energy and distance among cluster heads, are introduced, so that nodes who hold a large residual energy will have a better chance to become cluster heads. The specific process of the cluster head election is as follows. Each node transmits its residual energy message to cluster head in its last transmission slot per round. When the cluster head receives all messages during the last frame, it chooses three nodes with the largest residual energy as preliminary cluster heads (CHpre) and broadcasts the message to its non-cluster head nodes. Each CHpre sets a timer, and time of each timer is inversely to the residual energy. When time of one timer is first over, the CHprep broadcasts a message to let all the nodes in the network know, and the rest two CHpreps become non-cluster head nodes after receiving the message. Once the first cluster head is elected, the rest CHs are elected among the CHpreps of other clusters with a bound variable—average radius of cluster R. That is CHpreps , which distances between each other are most closest to R , will become cluster heads.

Cluster formation Units

Once nodes have elected themselves to be cluster heads, the cluster heads broadcast the resultant message using a non-persistent carrier-sensor multiple access (CSMA) MAC protocol. This message is a small message containing the node’s ID. Each non-cluster head node determines its cluster for this round by choosing the cluster head that requires the minimum communication energy, based on the received signal strength of the advertisement from each cluster head. According to the direction of join-request message and the transmit power from each node, the cluster head estimates the orientation and distance informationof each node. Once the cluster head has received all join-request messages, based on the whole cluster structure and distance information, the cluster head calculates a optimal multi-hop data transmission path for each node.

Figure 2: Each node chooses its optimal multi-hop data transmission path to reduce energy dissipation Click here to View figure

 

The optimal multi-hop data transmission path for each node is shown in Figure 2. When a node chooses an another node as its next-hop node, the chosen node must satisfy two demands. Firstly, the chosen node must have a closer distance to the cluster head. Secondly, the angle composing by the original node, the original node’s next-hop node, and the original node’s secondary-hop node or cluster head must be an obtuse angle. If the next-hop node does not satisfy the secondary demand, the original node will choose the secondary-hop node as its next-hop node and calculate whether or not satisfy the demands. Therefore, the reason node i choosing node j as its next-hop node in Figure 2 is

where d²_i-j, d²_j-k, d²_i-k are the distance between node i and node j , node j and node k ,node i and node k respectively. Once the cluster head has calculated the optimal multi-hop paths, it broadcasts the resultant message and TDMA code to the cluster. All the non-cluster nodes look for their optimal transmission paths from the advisement message. To reduce conflict rate of data transmission, in the paper, we assume node which has the more hops will occupy the more front of the transmission slot per frame.

Partial clustering methods

In partial clustering, the field is first partitioned into cells and then a sub-area is selected within each cell. In order to maintain connectivity, the partition and the sub-area selection need to satisfy the following 2 conditions.

Condition 1

Any sensor in a sub-area is connected directly to all sensors in the sub-areas within neighboring cells.

Condition 2

Within a cell, sensors outside the sub-area can communicate directly with any sensor in the sub-area.

Comparing partial clustering with clustering, denoting by Dp and Dc the respective average duty cycle, we have the Following

where n_p and n_c are the number of cells in a partial clustering and standard clustering methods, respectively. Thus so long as np < nc, partial clustering achieves lower average duty cycle.

The sub-areas are chosen as the shaded co-centered squares, as illustrated in Figures 3(a) and (b). For any square cell, the 4 square cells adjacent to its sides are considered its neighboring clusters. From Figure 3(b), we can see that the largest distance from any sensor in a cell to a node in the sub-area of the cell is less than R. Furthermore, the largest distance between two nodes in neighboring sub-areas equals R.

Figure 3: (a) P-S(y): One sensor needs to be chosen in each shaded sub-area. (b) Details of P-S(y): Square ABCD is a cell  Click here to View figure

 

The side length -y is also easily obtainable from Figure 3(b). we can see that the largest distance from any sensor in a cell to a node in the sub-area of the cell is less than R. Furthermore, the largest distance between two nodes in neighboring sub-areas equals R.

The key to the distributed partial clustering algorithm is illustrated in Figure 4. In a the hexagon based partial clustering essentially attempts to form a .ring. of active nodes (12 of them to be precise) around an area in which all nodes can go to sleep. If a node can Find such a ring of nodes (subsequently called supports) to be active, then the node can safely switch off (such a node is subsequently called a head). Once this ring of supports are identified, all other nodes surrounded by this ring can also become heads and switch off. The head node will be off for a pre-specified period of time and wake up; the ring of supports will be relieved of their role, and the process will repeat. A node that is neither a head nor a support will be called a regular node.

Figure 4: Partition of the communication area of the head node (in dark) and the connected ring of supports (in white). All non-support sensors inside the big circle are potential heads Click here to View figure

 

Performance Analysis

This section presents the performance analysis of clustering protocols namely LEACH, HEED, used MATLAB as the simulation environment. Here I used network of 100 nodes placed in an area of 100 x 100 m. The BS location is taken as (50,150) m. All clustering protocols are evaluated with and without (conventional) the discrete power selection Each simulation experiment is performed on a unique topology and consists of several rounds of cluster set up phase and data transmission phase. In each round a set of new cluster heads is elected and the non-cluster head nodes send five data packets to their associated cluster head.

Figure 5(a): Comparison of LEACH With Proposed Algorithm (b): Comparison of HEED With Proposed Algorithm Click here to View figure

 

I also assume that the cluster head is capable of data aggregation and data received from member nodes is therefore sent in aggregated form. In performance analysis of different clustering schemes using both conventional and discrete power model remains on metrics related to energy conservation. Figure 5 (a) and(b) illustrates results for the random topology where y-axis indicates the mean residual energy of the system normalized to number of nodes and x-axis denotes the number of rounds. It can be observed that the mean residual energy of the system in case of discrete power model is lower than that of the conventional model for all protocols. A sharp slope in case of the discrete power model is indicative of the sensor nodes losing their energy at a much faster rate as compared to the conventional model.

Conclusion

In this paper, we have presented CPMH, an energy efficient Partial clustering method for heterogeneous WSNs and compared it to the LEACH And HEED protocol. Results from oursimulations show that CPMH provides better performance for energy efficiency and network lifetime. However our protocol can be classified as a protocol with continuous data transfer just like LEACH, which in its general form is intended for static networks. With some modifications, CPMH can handle networks with some mobile nodes With multi-hop routing algorithm can be implemented for all nodes in the network. This means that when a cluster-head has a packet to send to the BS, it would route the packet using all nodes including both cluster-heads and members to find the optimal route.

 References

1. Shen bo, Zhang shiyong, Zhong yipping. Cluster-Based Routing Protocol for Wireless Sensor Networks, journal of software. 17(7): 1588-1600 (2006).
2. Saad, E.M.; Awadalla, M.H.; Saleh, M.A.; Keshk, H.; Darwish, R.R. Adaptive and Energy Efficient Clustering Architecture for Dynamic Sensor Networks Soft Computing Applications, 2007. SOFA 2007. 2nd International Workshop on 21-23: 221-225 (2007).
3. Bao L, Garcia-Luna-Aceves J J. Topology management in ad hoc networks. In: Proc 4th ACM Int’l Symp on Mobile Ad Hop Networking and Computing (MobiHoc 2003), Annapolis, Maryland. 129~140 (2003).
4. Habitat monitoring on Great Duck Island (http://www.greatduckisland.net/)
5. Estrin D, Govindan R, Heidemann J, Kumar S. Next century challenges: Scalable coordinate in a sensor network. In: Proceedings of the 5th ACM/IEEE International Conference on Mobile Computing and Networking. Seattle: IEEE Computer Society, 1999, 263~270.
6. G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks,” ACM Trans. Sensor Networks, 1(1): 36-72 (2005).
7. J. Lu, J. Wang, and T. Suda, “Scalable Coverage Maintenance for Dense Wireless Sensor Networks,” Proc. Third Ann. IEEE Comm. Soc. Conf. Sensor and Ad Hoc Comm. and Networks (SECON ’06), 2: 651-660 (2006).
8. A. Chamam and S. Pierre, “Dynamic Sensor Activation for Maximizing Network Lifetime under Coverage Constraint,” Proc. Intel Symp. Comm. and Information Technologies (ISCIT ’07), 971- 976 (2007).
9. Szewczyk R, Ferencz A. Energy implications of network sensor designs. http:// www.cs.berkeley.edu/~szewczyk/cs252/ paper.pdf.
10. Abbasi, A. A., and Younis, M., A survey on clustering algorithms for wireless sensor networks, Comput. Commun. 30(14-15): 2826–2841 (2007).

---

This work is licensed under a Creative Commons Attribution 4.0 International License.