AIRCC PUBLISHING CORPORATION
FUZZY BASED CLUSTERING AND ENERGY EFFICIENTROUTING FOR UNDERWATER WIRELESS SENSOR
Sihem Souiki1, Mourad Hadjila1 and Mohammed Feham
Department of Telecommunication, Tlemcen University, Algeria.
Underwater Wireless Sensor Network (UWSN) is a particular kind of sensor networks which ischaracterized by using acoustic channels for communication. UWSN is challenged by great issues speciallythe energy supply of sensor node which can be wasted rapidly by several factors. The most proposedrouting protocols for terrestrial sensor networks are not adequate for UWSN, thus new design of routingprotocols must be adapted to this constrain. In this paper we propose two new clustering algorithms basedon Fuzzy C-Means mechanisms. In the first proposition, the cluster head is elected initially based on thecloseness to the center of the cluster, then the node having the higher residual energy elects itself as acluster head. All non-cluster head nodes transmit sensed data to the cluster head. This latter performs dataaggregation and transmits the data directly to the base station. The second algorithm uses the sameprinciple in forming clusters and electing cluster heads but operates in multi-hop mode to forward datafrom cluster heads to the underwater sink (uw-sink). Furthermore the two proposed algorithms are testedfor static and dynamic deployment. Simulation results demonstrate the effectiveness of the proposedalgorithms resulting in an extension of the network lifetime.
UWSN, Routing, Clustering, Fuzzy C-Means, Energy efficiency
In recent years, underwater wireless sensor network has emerged as a powerful technique in orderto discover and exploit this harsh environment. As over 70% of the earth’s surface is covered bywater, it is advantageous to deploy underwater sensor networks to support several categories ofapplications such as oceanographic data collection, pollution monitoring, offshore exploration,disaster prevention, assisted navigation and tactical surveillance applications . To make theseapplications viable, there is a need to enable underwater communications among underwaterdevices. The underwater communication may include the transmission of information in threeforms (sound, electromagnetic (EM), or optical waves). Each of these techniques has advantagesand drawbacks. Electromagnetic signals deliver very poor performance underwater, providingtransmission ranges of only a few meters at the typical RF sensor transmission power. Opticalcommunication for underwater sensor networks using light waves has also been investigated;however these methods either require high precision or high power if the distances betweensensor nodes are large. Consequently, acoustic networks enabled by sound waves become idealalternatives since acoustic signals propagate well through water and require much less power thanRF and light signals for the same communication range .An underwater sensor network is usually formed by several autonomous and individual sensornodes used to collect and forward data to the uw-sink. The most important challenges ofdeploying such a network are the cost, the computational power, the memory, the communicationrange and most of all the limited battery resources of each sensor node. The lifetime of UWSN islargely restricted because the number of sensor nodes that stop working due to the energy wastageincreases with a deployment time. Then the high energy consumption is particularly significantdefy for researchers to achieve long operating time without affecting system performance.Generally routing is the backbone for any network, and routing protocols are considered to be incharge for discovering and maintaining the routes. Most of the proposed protocols for terrestrialsensor networks cannot be immediately used in UWSN owing to the continuous exchange ofoverhead messages applied (proactive ad hoc routing) or the route discovery process based on theflooding technique (reactive ad hoc routing) although the major protocols are designed for astationary deployment, thus these solutions are ineffective in large scale UWSN because theyexhaust energy and bandwidth resources. Therefore new energy efficient protocols must bedesigned for UWSN.In this paper we present a hierarchical fuzzy based energy efficient routing algorithms where theclusters are formed by the Fuzzy C-Means method. The nodes are deployed randomly in threedimensional environments. The first proposed algorithm employs a single hop transmissionbetween cluster heads and the uw-sink. Whereas the second proposition uses the multihoptransmission between cluster heads and uw-sink; both algorithms are simulated for static anddynamic topologies.The remainder of the paper is organized as follows. In section 2, a related work on hierarchicalouting in both terrestrial and underwater wireless sensor networks are presented. Section 3 givesa detail description of our routing algorithms simulated in static and dynamic topologies. Section4 shows the simulations results. Finally, the last section concludes the paper.
2. RELATED WORKS
Energy saving is a primordial issue in UWSNs because sensor nodes are supplied by batteries,which are difficult to replace or recharge in hostile underwater environments. Designing robust,scalable and energy aware routing protocols in this kind of networks is a fundamental researchchallenge. In the ground based wireless sensor networks, numerous routing protocols have beendeveloped which can be divided into following classes according to deployment: flat,geographical, and hierarchal routing. In a flat topology, all nodes perform the same tasks and havethe same functionalities in the network. Data transmission is performed by flooding in hop by hopmanner. Flooding , Gossiping  and SPIN  are example of flat routing protocols. Thesecond class is based on the position information of each node to determine forwarding path. The
typical geographic routing protocols in WSNs include [6,7].Owing to satisfy the scalability aimand extending network lifetime in WSN, grouping nodes into clusters has been widely adopted bythe research community. The hierarchical routing protocols involve cluster-based structure of thesensor nodes. Generally, each cluster constitutes a leader referred to as cluster head (CH) usuallyperforms the special tasks (fusion and aggregation) and other member nodes (collection of data
and monitoring). The first clustering routing protocol proposed for WSNs includes Low-energyAdaptive Clustering Hierarchy (LEACH) . The key idea of this protocol is to select randomly aset of sensor nodes as cluster head and rotate this task to uniformly distribute the energy loadamong the nodes in the network. There are two phases of LEACH protocol: The setup and steadyphases. Firstly, in the setup phase clusters are formed and the cluster head (CH) selection isperformed by the member nodes. Secondly the cluster head (CH) compress the gathered dataInternational Journal of Computer Networks & Communications (IJCNC) Vol.7, No.2, March 201535from diverse nodes that belong to the respective cluster. Then the cluster head forwardsaggregated data to the base station by single hop communication. Multiple variants of LEACHprotocol are proposed to overcome some drawbacks of this protocol such as: LEACH-C , MRLEACH and HEED .However, these protocols are not appropriate for UWSNs because they assume that the sensornetwork is stationary and they are not well adapted to the intrinsic properties of underwaterenvironments, such as long propagation delays, low data rates and difficulty of synchronization.On the other hand, some hierarchical routing protocols have been designed for UWSN such asDucs , Mccp  and HydroCast .DUCS protocol is designed for long-term non-time critical applications where the sensor nodesare grouped into clusters using a distributed algorithm. The protocol operates in two stages: thefirst stagecontaining the clusters formation and the selection of the cluster head based on theremaining energy. In addition a randomized rotation of CH is performed among different nodeswithin a cluster in order to alleviate fast draining of the sensor node energy. In the second stagethe data are transmitted to the sink using multi-hop routing through other cluster heads.In MCCP protocol (Minimum Cost Clustering Protocol), the clusters are created based on a costmetric. The cost metric is calculated on the basis of three important parameters: (1) the totalenergy consumption of the cluster members for sending data to the cluster head; (2) the residualenergy of the cluster head and its cluster members; and (3) the relative location between thecluster head and the uw-sink. The proposed protocol selects a set of non-overlapping clustersfrom all potential clusters based on the cost metric affected to each potential cluster and attemptsto reduce the cost of the selected clusters. MCCP can adapt geographical cluster head distributionto the traffic pattern in the network and thus avoid the formation of hot spots around the uw-sink.It can also balance the traffic load between cluster heads and cluster members through periodicalre-clustering the sensor nodes in the network.The global idea of HydroCast is based on a routing decision which is made after comparing thelocal pressure or depth information, such that data packets are greedily forwarded towards a nodewith the lowest pressure level among the neighbor nodes. In HydroCast scheme, each localmaximum node maintains a recovery route towards a neighboring node with higher depth thanitself. After one or several forwarding’s through local maxima, a data packet can be routed out ofthe void region and can be switched back to the greedy mode.
3. THE PROPOSED ALGORITHMS
In the following, we briefly introduce the basic theory of Fuzzy C-Means (FCM) used in clusterformation of our propositions, and then we give a detailed description of the proposed approaches.
3.1. Basic theory of Fuzzy C-Means
Fuzzy C-Means clustering algorithm , is a kind of clustering algorithm using membership todescribe the possibility of cluster. However FCM is a local optimization algorithm, which is verysensitive to initialization and gets into the local minimum value easily.The finite vectors xi (i=1, 2,…, n) are divided into c (1<c<n) classes, and the clustering center ofeach class is solved to make membership minimum as the non-similarity index.International JournalThe objective function can be defined as follows:
Where Uij is the membership of the group, ci is the clustering center; dij is the special distancefrom vector ci to xj. m is the weighted index.The steps of algorithm are as the following:
• Initializing the membership matrix U to make it satisfy the following formula
• Calculating the clustering center using the following formula.
• Calculating the objective function according to the formula (1). If the objective function isless than a threshold or the relative value function change value last time is less than athreshold, the algorithm stops.
• Updating the matrix by the following formula and returning to step2.
3.2. Single-Hop Fuzzy based Energy Efficient Routing algorithm for UWSN (SHFEER):
SH-FEER is a fuzzy based energy efficient algorithm where clusters are formed by using theFuzzy C-Means method. We suppose that underwater sensor nodes always have data to be sent tothe sink and the set of nodes have the same amount of energy .We assume in this approach that the nodes organize themselves inside clusters randomly withunequal sizes and one node is selected as a cluster-head for each cluster. All non-cluster headnodes forward their data to their cluster head via a single hop; the cluster-head node receives datafrom all cluster members, performs signal processing functions on the data (e.g. aggregation) andtransmits the data to the sink using single-hop routing. The cluster heads are responsible forcoordination among nodes within their clusters (intra-cluster coordination) and communication between each other(inter-cluster coordination).SH-FEER incorporates rotation of the cluster-head among the sensors to avoid rapid draining of
the batteries of specific underwater sensors. In this way, the energy consumption is distributed.The operation mode of SH-FEER is composed to three phases: clusters formation during the firstInternational Journal of Computer Networks &Communications (IJCNC) Vol.7, No.2, March 201537step and secondly the cluster head are selected. Initially, the closest node to the center is selectedas cluster head and in the next rounds the selection is based on the residual energy of each node;the third step is the transmission of data towards the sink.
The algorithm of this first proposition is mentioned as follows:
Step 1: Clusters formation
Apply FCM algorithm to form clusters.
Each cluster K(i) contains a number of nodes, i=1, …, N
Initially all nodes have the same amount of energy.
Step 2: Cluster head selection
maxE is a row vector contains N zeros
R_max: maximum number of rounds
TE: total energy of network
while(RR_max || TE>0)
for i = 1 to N do
calculate the distance d (nodei ,center) // between nodei and center of cluster.
Assign ICH (i) of the cluster in which d(nodei , center) is minimum.else
for j=1 to length(k(i)) do
Step 3: Data transmission
for i = 1 to N do
for j=1 to length(k(i)) do
k(i).j send data to CH(i)
Transmission from CHs to the uw-sink
for i = 1 to N do
CH(i) aggregates and forwards directly the data to uw-sink
3.3. Multi-Hop Fuzzy based Energy Efficient Routing algorithm for UWSN (MHFEER):
MH-FEER mimics the first proposed algorithm; it uses the same two first phases of SH-FEER(clusters formation and cluster head selection). However the process of data forwarding towardthe uw-sink is different by using multi-hop routing between cluster heads and uw-sink. The dataare transferred through multiple cluster-heads in the direction of the uw-sink choosing the shortestpath; this is repeated until it reaches the uw-sink.Since the mode of clusters formation and the cluster heads selection is the same as the firstalgorithm, we present below only the pseudo-code relating to the data forwarding from the clusterheads to uw-sink.Calculation of distances between CHs and distances between CHs and uw-sink
For i=1 to N
For j=1 to N do
4. PERFORMANCE EVALUATION
In this section, we evaluate the performance of the proposed algorithms through extensivesimulations under Matlab environment. Firstly, we define the performance metrics and thesimulation methodology, and then we present the energy model used. Moreover we evaluate hownetwork parameters such as node density, node mobility affect the performance of the proposedalgorithms.International Journal of Computer Networks & Communications (IJCNC) Vol.7, No.2, March 2015 39
4.1. Metrics and Methodology
In this paper two metrics are used to analyze the performance of the proposed algorithms: totalenergy consumption and the number of alive nodes
(i) Total energy consumption ET: is the sum of energy amount consumed by the all sensor nodes formed the networks
(ii) Number of alive nodes: is the number of sensor nodes where the energy is different to 0during (r) rounds.
4.1.2. Simulation Methodology
In our simulation we make some assumptions then we present the energy model used.
– Sensor nodes as well as the uw-sink are stationary after being deployed in the field.
– The network is considered homogeneous and all of the sensor nodes have the same initialenergy.
– Each sensor node knows its own geographical position.
– The underwater sink is not limited in terms of energy, memory and computational power.
– Underwater sink is located outside the area of the sensors nodes (at the surface).
– All nodes measure the environmental parameters at a fixed rate and send it periodically to thereceiver nodes.
– Each sensor node can operate either in sensing mode to monitor the environment parameters andtransmit to the underwater sink, cluster head (to compress and forward it to the uw-sink).
The Parameters setting of the simulation are shown in Table1
• Energy model
We use the same energy model as used in , which was proposed for underwater acousticnetworks. According to this model, to achieve a power level P0 at a receiver at a distance d, thetransmitter power Etx(d) must be:
Where 67, measured in dB/m, is a medium absorption coefficient depending on the frequencyrange of interest under given water temperature and salinity, 7is given by
Where 7 is the carrier frequency for transmission in KHz. The reception power is assumed to 1/3thof the transmission power.
4.2. Simulation1: static topology
The figure 1 depicts the total energy consumption of the two proposed algorithms and a comparison is performed with the direct transmission. As shown in this figure we observe thatthe MH-FEER algorithm consumes less energy comparing with SH-FEER, this is due to themulti-hop routing used between cluster heads and the sink i.e. MH-FEER avoid the long distancestransmission utilized in the SH-FEER between CH and the sink. Although this figure shows thatthe energy depletion of the two proposed algorithms is better than the direct transmission
From the simulation result shown in figure 2 and 3, we can see that the first node dies in directtransmission algorithm after 30 rounds while in SH-FEER and MH-FEER first node dies after 87and 31 rounds respectively. We also observe that the last node dies in direct transmissionalgorithm after 89 rounds while in SH-FEER and MH-FEER last node dies after 162 and 241rounds respectively. Therefore, in this set of simulations, we note that MH-FEER about 32.78 %more efficient in term of network lifetime compared to SH-FEER and about 63.07 % than thedirect transmission algorithm.Furthermore, the number of alive nodes decreases speedily with direct transmission and SHFEERcases in comparing to the MH-FEER algorithm.
4.4. Impact of density and mobility
In order to check the effect of density and mobility we choose the second proposition MH-FEERin this set of simulations where all nodes are mobile with the same speed and we change thenumber of nodes from 200 to 1000 nodes, the simulations results are plotted in the followingfigures.
Figures 7 and 8 depict the impact of density on the total energy consumption and the alive noderespectively. The total energy consumption increases when the number of nodes increases sincemore nodes are involved in packettransmission. However the number of alive nodes remainsstable but it’s eventually decreased rapidly.In this section of simulation we vary the mobility speed of each node from 1.5 m/s to 5.5 m/swhen using 100 nodes.
It can be seen from figure 9 that the total energy consumption increases with the growth of thenode speed, however, the number of alive nodes reduces more when increasing the speed as illustrated in figure 10.
In this paper we address the issue of routing energy efficiency in underwater wireless sensornetworks. Firstly, we have proposed two algorithms which utilize a clustering method based onFuzzy C-Means, using these algorithms; we study the effect of two key parameters (scalabilityand mobility) on the performance of UWSN. Moreover theses approaches are deployed on staticand mobile environments. The simulation results show a promising performance, in terms ofenergy consumption and network lifetime, with the proposed SH-FEER and MH-FEERalgorithms, than the direct transmission. In the future works we aim to investigate intelligentalgorithms such as genetic algorithms or ant colony, specially to find the shortest path betweenthe cluster heads and the underwater sink.
 I.F. Akyildiz, D. Pompili, and T. Melodia, “Underwater acoustic sensor networks: Researchchallenges”, Ad Hoc Networks, pp. 257–279, 2005.
 L. Liu, S. Zhou, and J.H .Cui, “Prospects and Problems of Wireless Communication for UnderwaterSensor Networks”, WILEY WCMC, pp. 977-994, 2008.
 Z.J. Haas, J.Y. Halpern and L. Li, “Gossip-Based Ad Hoc Routing”, Proceedings of the 19thConference of the IEEE Communications Society (INFOCOM), pp. 1707–1716, 2002.
 J. Kulik, W.R. Heinzelman and H. Balakrishnan, “Negotiation based protocols for disseminatinginformation in wireless sensor networks”, Wirel.Netw, pp. 169–185, 2002.
 C. Intanagonwiwat, R. Govindan, D. Estrin and J.Heidemann, “Directed diffusion for wireless sensornetworking”, IEEE/ACM Trans.Netw, pp. 2–16, 2003.
 Y. Xiu, J. Heidemann, and D. Estrin, “Geography-informed energy conservation for ad-hoc routing”,Proceedings ACM/IEEE MobiCom’01, pp. 70-84, 2001.
 Y. Yu, R. Govindan, and D.Estrin, “Geographical and energy aware routing: A recursive datadissemination protocol for wireless sensor networks”, Technical Report UCLA/CSD-TR-01-0023,UCLA Computer Science Department, 2001.
 W.R. Heinzelman, A. Chandrakasan, H. Balakrishnan, “Energy-Efficient Communication Protocol forWireless Microsensor Networks”, In Proceedings of the 33rd Annual Hawaii InternationalConference on System Sciences, pp. 10–19, 2000.
 W.B. Heinzelman, A.P. Chandrakasan, H. Balakrishnan, “An application-specific protocolarchitecture for wireless microsensor networks”, Wireless Commun, pp. 660–670, 2002.
 A.B. Dogar, G.A. Shah and M.O. Farooq, “MR-LEACH: Multi-hop routing with low energy adaptiveclustering hierarchy”, Fourth International Conference on Sensor Technologies and Applications(SENSORCOMM), pp. 262-268, 2010.
 O. Younis, S. Fahmy, “A hybrid energy-efficient, distributed clustering approach for ad hoc sensornetworks”, Mobile Comput, IEEE Trans, pp. 366–79, 2004.
 M.C. Domingo, R. Prior, “A distributed clustering scheme for underwater wireless sensor networks.in personal, indoor and mobile radio communications”, Proceedings of the IEEE 18th International Symposium on PIMRC,2007.
 W. Pu, L. Cheng and Z. Jun, “Distributed minimum-cost clustering protocol for underwater sensornetworks (UWSNs) “, Proceedings of the IEEE international conference on communications, ICC ’07,2007.
 L. Uichin, et al., “Pressure routing for underwater sensor networks”, Proceedings of the IEEE INFOCOM, 2010.
 M. Zhang, J. Yu, “Fuzzy partitional clustering algorithms”, J journal of Software, pp.6-859, 2004.
 M. Hadjila, H. Guyennet and M. Feham, “Energy-Efficient in Wireless Sensor Networks using FuzzyC-Means Clustering Approach”, International Journal of Sensors and Sensor Networks, pp. 21-26,2013.
 E. Sozer, M. Stojanovic, and J. Proakis, “Underwater acoustic networks”, IEEE Journal of OceanicEngineering, pp. 72-83, 2000.