# RSHSC-Routing Algorithm Based on Simplified Harmony Search and Coding for UWSNs

Authors: Meiju Li; Xiujuan Du; Chunyan Peng
Journal: Journal of Sensors
 (2018)

---

## Abstract

With the development of wireless networks and increasingly interest of people in underwater resources and environment, UWSNs are being paid more and more attention. Because of the characteristics of underwater channel and acoustic signal, the protocols used in the terrestrial networks cannot be directly used in UWSNs. In this paper, a reliable and energy-efficient routing protocol based on SHS and coding, called RSHSC, is proposed. Firstly, regular nodes are assigned to cluster heads according to simplified harmony search algorithm. Secondly, partial network encoding is introduced and the next two-hop information is considered when data packets are transmitted to sink nodes from the source node. Only the best next-hop forwards data packets. All data packets from neighbor nodes are used for decoding. Thirdly, two schemes of updating routing are designed and compared. Lastly, extensive simulations prove RSHSC is effective in improving reliability and decreasing energy consumption.


---

## Body

## 1. Introduction

In recent years, UWSNs (underwater wireless sensor networks) attracted more and more attentions because of the wide application such as marine source exploration and pollution monitor [1–3]. Like other wireless networks, it is necessary to improve the communication performance for UWSNs. However, UWSN is different from other wireless networks. UWSN has some characteristics that other wireless networks have not. Firstly, UWSN is provided energy by batteries. Once the battery is exhausted, the node is considered as dead [4]. Meanwhile, the acoustic communication consumes more energy than radio signal and optical signal. Secondly, underwater channel is complex because of shipping, marine organisms, and so on [5]. Besides, the communication quality is affected by multipath resulting from the reflections, water salinity, temperature, and so on [6]. Thirdly, mobile topology [7]. The position of the node is forced to change with the water currents and marine biological activities [8]. Fourthly, the propagation delay is longer than terrestrial networks. The propagation speed of acoustic signal under water is just 1500 m/s, which is five magnitude lower than radio signal on land (3 × 108 m/s) [9]. Because of those factors of UWSNs, the protocols used on the land cannot be directly applied in UWSNs, especially for routing protocols. Therefore, designing a routing protocol special for UWSNs is necessary [10–12].Like most wireless networks, the performances of delay, energy consumption, reliability, and throughput and bandwidth utilization are important in UWSNs [13]. In recent years, more and more routing protocols are proposed. Some of them are to decrease energy consumption, some of them are to shorten delay. They are effective in certain scenarios but cannot take into account multiple performance.The contributions of this paper are showed as follows:(1)
The regular nodes are assigned to the cluster heads based on simplified harmony search algorithm (SHS). Two schemes are designed
(2)
Partial network coding is introduced when routing data from source cluster head to the sink node. Meanwhile, the data from all neighbor nodes are used for decoding, which makes full use of the broadcast characteristics of UWSNs
(3)
Two schemes are compared for maintaining routing timely: when the speed of water flow is constant, scheme 1 is adopted; otherwise, the scheme 2 is used
(4)
Through simulations, the best SHS and routing maintaining algorithm are determined and the performance of RSHSC is evaluated


## 2. Relative Works

Researchers have designed some routing protocols for UWSNs in recent years. In 2008, Yan et al. proposed DBR routing algorithm [14]. In DBR, neighbors with less depth need to wait a certain time to forward data packets. The lengths of waiting time of neighbors are set according to the depth. The more depth, the shorter waiting time. The neighbor will cease to forward if hearing the same data packets during waiting time. DBR has some defects. Therefore, some improved protocols are provided. Residual energy is introduced to select next-hop in EEDBR [15]. DBR-NC uses the coding technique [16]. To avoid selecting next-hop in the void area, next-hop of the next-hop is considered in WDFAD-DBR [17]. Meanwhile, the forwarding area is adjusted according to node dense. LMPC is proposed in [18]. In LMPC, a data packet is delivered along multiple paths according to binary tree. FLMPC improved LMPC in [19]. Nodes are classified into cross nodes and regular nodes. Only the cross nodes generate binary tree. Hao et al. proposed GPNC algorithm [20]. Data packets are forwarded to sink greedily using the sensor nodes’ location information. GPNC incorporates partial network coding. In L2-ABF, the sender selects next-hop by calculating the forwarding angle. CoUWSN uses cost function of distance and SNR of the link to decide the next-hop [21]. Sink mobility pattern is given in DEADs [22]. AEDG is proposed in [23]. In AEDG, AUV is used to collect data. To prevent gateway overloading, the number of associated node with the gateway node is limited. The residual energy and number of neighbors are considered. Hubcode is proposed in [24]. Hubcode is an algorithm based on cluster. Hubcode exchanges coefficient matrix and gets initial data via calculating inverse matrix. In BLOAD [25], the weight of nodes is calculated according to the distance among nodes, the more overlap area in the coverage range of the node, the less importance for the node. In TSBNC, the coding is introduced into the time-slot algorithm [26]. Network coding and cross-layer are used in NCRP [27]. The node with the least weight is selected as the cluster head. In QDAR [28], end-to-end delay and residual energy are introduced into the Q-Learning algorithm. In LB-AGR, the best next-hop is determined based on density, available energy, location, and level difference between neighbor nodes [29]. The characteristics of these protocols are showed as Table 1.Table 1
Protocols characteristics.
Protocol name
Characteristics
Advantage
Disadvantage
DBR
Select next-hop only based on depth
Independent location information, decrease part of redundant forwarding
Long delay, high energy consumption
EEDBR
Residual energy is considered
Prolong network life
Long delay, redundant forwarding
DBR-NC
Coding is introduced
Reliable
Long delay, energy is not considered
WDFAD-DBR
Next two-hop information is considered. Adaptively adjust the forwarding area according to node dense
Avoid selecting the node in the void area as the next-hop
Long delay in sparse network delivery ratio is low
iAMCTD
Courier node is used
Courier node decreases delay, optimized threshold decreases redundant forwarding
Energy unbalance
LMPC
Establish binary tree
Reliable, high delivery ratio
High energy consumption, void node is not considered
FLMPC
Establish binary tree from the sensor nodes which reside near the layer
Copies in the cross node increase the delivery ratio, decrease the retransmission
Routing update is not considered, multiple routing wastes energy
GPNC
Network coding is used based on geographic location information
Reliable, decrease energy consumption, shorten delay
Void node is not considered, energy unbalance
CoUWSN
Uses multiple input multiple output
Save transmit power, increase data rate, extend the communication range
Consume more energy, long delay
DEADs
Cooperative routing is joined with sink mobility
High throughput, prolong network life
Waste energy, energy unbalance
AEDG
Use shortest path tree to assign nodes to gate way
Network lifetime prolongation, throughput maximization
Long delay
Hubcode
Use hubs as relay and encode multiple messages address to the same destination
Reducing the forwarding overheads, increasing the delivery ratio
Energy balance long delay
BLOAD
Addressing energy hole, mixed routing scheme (including directly and multiple hop communication) is used
Balance energy, avoid energy hole
The node with longer distance to sink dies quickly
TSBNC
Theory of network coding is introduced into time-slot based routing algorithm
Decrease energy consumption and collisions
Energy unbalance, long delay
NCRP
Network coding and cross-layer design are used
High delivery ratio, save energy
Void node is not considered, energy unbalance
QDAR
Q-learning algorithm is introduced
Extending network lifetime and short delay
In the mobile network, energy consumption is high. Link quality is not considered
LB-AGR
Nodes are divided into different levels, upstream and downstream are considered when selecting the best-next-hop
Comprehensive factors are considered
The void node is not considered, greedy routing


## 3. Model Analysis

In this sector, network model, energy and propagation model are analyzed.


### 3.1. Network Model

The network model is showed in Figure1. In our network, nodes are deployed in the 3D underwater environment and divided into three types: regular nodes, advanced nodes, and sink nodes. The first two nodes are defined as follows:
(i)
Regular nodes: the nodes have ordinary amount of initial energy, which can communicate with advanced nodes and sink nodes
(ii)
Advanced nodes: the nodes have more initial energy than regular nodes. Advanced nodes can communicate with each other, regular nodes and sink nodes. The advanced node is also called as the cluster head (CH). The advanced nodes with almost depth are divided into the same levelsFigure 1
Network model.In the network, each sink node is equipped with both acoustic modem and RF modem, which are responsible for communicating with underwater nodes (regular nodes and advanced nodes) and data centers, respectively. Each underwater node is equipped with an acoustic modem, which is responsible for communicating with each other and sink nodes. All nodes mobile with water flow. Each node can get the location information of itself.


### 3.2. Channel Model

To design a routing algorithm with high bandwidth utilization, energy efficient and reliable for UWSNs, we must learn about the channel model. In UWSNs, channel is affected by absorption loss and spreading loss. The attenuationAd,f is showed as (1) [21].
(1)Ad,f=A0dkαfd.Here,k is the spreading factor, and the value is 1.5 for practical applications. d is the spreading distance. A0 is a normalization constant. αf is presented as (2).
(2)10logαf=0.11f21+f2+44f24100+f2+2.75f2104+0.003dB/km.There are great many types of noise under water. The main noise include turbulence (Nt), shipping (Ns), waves (Nw), and thermal noise (Nth). These noises can be modeled by the power spectral and Gaussian statistics as (3), (4), (5), (6), and (7) [22].
(3)Nf=Ntf+Nsf+Nwf+Nthf,(4)10logNtf=17−30logf,(5)10logNsf=40+20s−0.5+26logf−60logf+0.03,(6)10logNwf=50+7.5w+20logf−40logf+0.4,(7)10logNthf=−15+20logf.Here,s is the shipping factor (varies from 0 to 1), W is the wind velocity (varies from 0 to 10 m/s), and f denotes the carrier frequency.Therefore, the signal to noise (SNR) is showed as (8), which is related to the propagation distance (d) and the carrier frequency (f). B is the bandwidth.
(8)SNRd,f=PAd,fNfB.According to Shannon theory, channel capacity is calculated as (9) [21].
(9)Cd,f=Blog21+SNRd,f.


## 3.1. Network Model

The network model is showed in Figure1. In our network, nodes are deployed in the 3D underwater environment and divided into three types: regular nodes, advanced nodes, and sink nodes. The first two nodes are defined as follows:
(i)
Regular nodes: the nodes have ordinary amount of initial energy, which can communicate with advanced nodes and sink nodes
(ii)
Advanced nodes: the nodes have more initial energy than regular nodes. Advanced nodes can communicate with each other, regular nodes and sink nodes. The advanced node is also called as the cluster head (CH). The advanced nodes with almost depth are divided into the same levelsFigure 1
Network model.In the network, each sink node is equipped with both acoustic modem and RF modem, which are responsible for communicating with underwater nodes (regular nodes and advanced nodes) and data centers, respectively. Each underwater node is equipped with an acoustic modem, which is responsible for communicating with each other and sink nodes. All nodes mobile with water flow. Each node can get the location information of itself.


## 3.2. Channel Model

To design a routing algorithm with high bandwidth utilization, energy efficient and reliable for UWSNs, we must learn about the channel model. In UWSNs, channel is affected by absorption loss and spreading loss. The attenuationAd,f is showed as (1) [21].
(1)Ad,f=A0dkαfd.Here,k is the spreading factor, and the value is 1.5 for practical applications. d is the spreading distance. A0 is a normalization constant. αf is presented as (2).
(2)10logαf=0.11f21+f2+44f24100+f2+2.75f2104+0.003dB/km.There are great many types of noise under water. The main noise include turbulence (Nt), shipping (Ns), waves (Nw), and thermal noise (Nth). These noises can be modeled by the power spectral and Gaussian statistics as (3), (4), (5), (6), and (7) [22].
(3)Nf=Ntf+Nsf+Nwf+Nthf,(4)10logNtf=17−30logf,(5)10logNsf=40+20s−0.5+26logf−60logf+0.03,(6)10logNwf=50+7.5w+20logf−40logf+0.4,(7)10logNthf=−15+20logf.Here,s is the shipping factor (varies from 0 to 1), W is the wind velocity (varies from 0 to 10 m/s), and f denotes the carrier frequency.Therefore, the signal to noise (SNR) is showed as (8), which is related to the propagation distance (d) and the carrier frequency (f). B is the bandwidth.
(8)SNRd,f=PAd,fNfB.According to Shannon theory, channel capacity is calculated as (9) [21].
(9)Cd,f=Blog21+SNRd,f.


## 4. Protocol Design

The implementation of RSHSC consists of four steps: initialization, cluster construction, intercluster routing, and routing maintaining. In initialization phase, sink nodes broadcast beacon signal with the location information of themselves to underwater nodes. Cluster heads broadcast hello packets. Regular nodes broadcast information packets. The details of initialization phase are showed in Section4.1. In cluster construction phase, regular nodes are assigned to the cluster head based on SHS algorithm, which is detailed in Section 4.2. In the interclusters routing phase, the cluster head encodes original packets and selects the best next-hop according to the information of neighbors and next two hop, which is detailed in Section 4.3. Because nodes mobile with the water flow, the routing needs to be updated timely. In routing maintaining phase, two algorithms are provided to decrease the energy consumption and collision results from sending too many nondata packets, which is detailed in Section 5.


### 4.1. Initialization

Sink nodes broadcast beacon signal including location and ID of themselves. After receiving beacon signal, each cluster head calculates and saves the distance between itself and sink nodes. Then, the cluster head broadcasts hello packet, whose format is showed in Table2. “ID” is the source node ID of the hello packet. Seq number is the sequence number of the hello packet. “ID1,” “ID2,” and “ID3” are the ID of member nodes. Initially, the field of “ID1”, “ID2,” and “ID3” are filled with “0.” Address is the location information of the cluster head. “RE_ENERGY” is the residual energy of the cluster head. The regular node sends information packets after receiving a hello packet. The format of information packet is showed in Table 3. “ID1” is the ID number of the cluster head with the highest priority that the regular node joins in. “Distance 1” is the distance to the cluster head with ID1. “ID2” and “Distance 2” are as the ID1 and Distance1. Before receiving less than three information packets from different regular nodes, the corresponding ID is filled with “0.” Analogously, the ID2 and Distance2 are filled with “0” when receiving hello packets with only ID address.Table 2
Format of hello packet.
ID
Seq number
ID1
ID2
ID3
Reserve
RE_ENERGY
AddressTable 3
Format of information packet.
ID
ID1
Distance1
ID2
Distance 2In this phase, on one hand, regular nodes and cluster heads get information from each other; on the other hand, cluster heads get the information of neighbor cluster heads.


### 4.2. Cluster Constructing

In the process of cluster constructing, the harmony search algorithm is introduced.


#### 4.2.1. Harmony Search (HS) Algorithm

HS is a heuristic global search algorithm. The I instruments (I=1,2,…,m) are analogous as the I variables to solve optimization problems, and the harmonic Rj of each musical instrument tone (j=1,2,…,m) is equivalent to the j solution vectors of the optimization problem, and the evolution is analogous to the objective function.The procedure of HS is as follows:(1)
The algorithm generatesm initial solutions into the harmony memory (HM) and searches for new solutions in HM with a probability HR
(2)
The algorithm generates local perturbations to the new solution with probabilityPr. If the new solution objective function value is better than the worst solution in HM, replace it
(3)
Iterate iteratively until the expected number of iterations isTmax
(4)
As above, by introducing HR andPr, HS algorithm is expected to the balance of exploration ability of the solution space, but there is no the recital basis for how to choose the value


#### 4.2.2. Simplified HS

According to the characteristics of UWSNs, the average number of regular nodes managed by each cluster head is small, and it is difficult to get the global information of the whole networks. Therefore, the simplified HS algorithm is proposed for UWSNs.(A)
Taking regular nodes as research objects, the assignment is determined by regular nodes. We simplify the HS (HSA) as follows:(1)
The objective function is(10)F1=α∑i=1CHi~dni−CHiR+β∑i=1i=NCHi~−N¯N¯.
Here,α+β=1. dni−CHi presents the distance between the regular node ni and the cluster head CHi. CHi~ presents the number of members for cluster head CHi. R is the communication radius. When CHi~ is constant, the less F1, the better assignment. The first part reflects the balance among regular nodes, and the second part reflects the balance among cluster heads.
(2)
Because any regular node is assigned to only the cluster head in its communication range, we use the local selection of regular nodes being assigned to the cluster head to replace the global assignment. So theXi=xi,1,xi,2…xi,k…xi,n. n is the number of member nodes of cluster heads CHi and adjacent to CHi. Xi is the HM, xi,k is the ID of the cluster head the regular node ni joining in. For example, in Figure 2, the regular nodes are R=n1,n2,n3,n5,n6,n7, X1=1,2,2,2,1,1. While R=n1,n2,n3,n4,n5,n6,n7,n8, X2=1,2,2,2,3,2,1,1,3
(3)
According to the information of cluster heads recorded in the regular nodes, the HM is adjusted at probabilityP. P is calculated by (11). Here, pi′=1/di, p′=∑i=1i=niˇ1/d11/d1, niˇ is the number of cluster head in the communication range of regular node ni, di is the distance between the node ni and the cluster head. If the adjusted objective function is bigger than the value before, replace it. Otherwise, the HM is kept
(11)P=pi′p′.
(B)
Taking cluster heads as research objects, the assignment is determined by cluster heads. We simplify the HS (HSB) as follows:(1)
The objective function is the same as HSA
(2)
Similar to HSA,Xi=xi,1,xi,2…xi,k…xi,n. xi,k is the aggregate of member nodes in the cluster head CHi. As is showed in Figure 2, R=CH1,CH2,CH3, then Xi=n1,n6,n7,n2,n3,n5,,n3,n4,n8
(3)
According to the information of regular nodes recorded in the cluster heads, the HM is adjusted at probabilityP. P is calculated by (12), pi− is the probability each member ni having only one cluster head, and pi′ is the probability ni being adjusted into another cluster head. pi′ can be gotten from (13). Ri and Rj denote the residual energy of the cluster heads in a regular node communication range, CH~i and CH~j are the number of members in a cluster, respectively, γ1+γ2=1
(12)P=1−∏i=1i=CH~i1−1−pi−pi′,(13)pi′=γ1RiRi+Rj+γ21/CHi~1/CHi~+1/CHj~.Figure 2
Regular node assignment.


### 4.3. Routing Construction

How are data packets transmitted from a source node to the sink node? In this section, the procedure is analyzed.


#### 4.3.1. Review of Routing

According to the initialization procedure, each CH saves the information of neighbor CHs as showed in Table4. After receiving a hello packet, the CH firstly checks the “address” field and calculates the distance between the source node of hello packet and the sink node. Only the cluster head with shorter distance to the sink node has opportunity to be the next-hop. The priority of neighbors is calculated by formula (14). dt is the advanced distance to the sink node. As showed in Figure 3, CH2 is the source cluster head, CH1 is the neighbor of CH2, S is the sink node. The CH2D¯ is the advanced distance to node S. We set the coordinate of CH2, CH1, and S is (x0,y0,z0), (x1,y1,z1), and (0,0,0), respectively. From the coordinate, we can get CH2S¯=xt02+yt02+zt02, CH1S¯=xt12+yt12+zt12, CH2CH1¯=xt0−xt12+yt0−yt12+zt0−zt12, cosθ=CH2CH1¯2+CH2S¯2−CH1S¯2/2CH2CH1¯×CH1S¯. So dt=CH2CH1¯cosθ. The more pt, the higher priority. Only the neighbor cluster head with the highest priority forwards the data packet.
(14)pt=k1ERtEIt+k2dtR.Table 4
Neighbors’ information table of cluster head.
ID
Address
Residual energy
Address of next-hop
Next-hop residual energy
PriorityFigure 3
Advanced distance.As above, the node with bigger advanced distance to sink and more residual energy is selected as the best next-hop. Therefore, the selected next-hop may have far distance to the previous hop, which leads to the big probability of failing to deliver. To enhance the reliability of the network, in our algorithm, coding is introduced.


#### 4.3.2. Network Coding

In most of conventional routing algorithms, the forwarder is responsible for relaying data without any processing. However, in UWSNs, like other wireless communications, broadcast is adopted. Meanwhile, the bandwidth is limited and delay is long. In order to make full use of the characteristics of broadcast and limited bandwidth, network coding is an efficient measure. The basic procedure of network coding is showed in Figure4.Figure 4
Coding theory.
(a)
Without coding
(b)
CodingThe data packeta is from node A. The data packet b is from node B. The node C is a relay.In the network without coding as Figure4(a), the necessary number of time slots to exchange data packets a and b is 4. While in Figure 4(b), the number is 3.Furthermore, we compare the partial network coding with the full network coding. In Figure5, the data packets d1, d2, and d3 are sent from the node A to node B. Here, we make
(15)d=d1d2d3.Figure 5
Full network coding and partial network coding.
(a)
Full network coding
(b)
Partial network codingNode A encode data packetsd into d′.
(16)d′=γ11γ12γ13γ21γ22γ23γ31γ32γ33d.To decode the encoded packets into original data packets, node B needs all data packets. So, the delay to transmit these three data packets is 3T (T is one slot time). In Figure5(b), the partial network coding is showed. Here, d1′=γ1d1, d2′=γ2d1+γ3d2, and d3′=γ4d1+γ5d2+γ6d3. So, in the partial network coding, recovering d1′, d2′, and d3′ into original packets needs T, 2T, and 3T, respectively. The average delay to transmit these three packets is T+2T+3T/3=2T. Comparing the partial network coding with full network coding, we can get the partial network coding is better than full network coding.In our algorithm, partial network coding is adopted. Each relay receives the encoded packets and decodes them. Then the next-hop of relay continues to encode the original data packets until the sink node receives the packets. If the sink node is in the communication range of the relay, the decoded packets are directly forwarded to the sink node.As showed in Figure6, during the routing procedure, the CH receives original data packets from member nodes and encodes the original data packets. The CH hears the data packets from regular nodes which are not its member node, drops them. When it hears a data packet from the neighbor with longer distance to the sink node, the CH checks weather it is helpful to decode if the next-hop of data packets is not the current ID. If received encoded packet have been decoded, CH drops it. If there is no association with the encoded packets saved, CH saves them and broadcasts data packets for a certain time. Otherwise, the received data packet is used to decode. For example, CH1 successively hears encoded packets P1, P2, P3 and P4, P1=d1⊕d2, P2=d2⊕d3, P3=d1⊕d3, and P4=d4⊕d5. We assume d1 have been decoded in CH1, then d2 is decoded using P1, d3 is decoded by P2, however, P3 is helpless for decoding any new original packet, CH1 will drop P3. While there is no association between data packets are encoded into P4 and the encoded packets saved in CH1, so CH1 saves P4 and broadcasts P4 after a certain time.Figure 6
Encoding algorithm flow chart.The procedure of encoding algorithm is showed in Figure6.


#### 4.3.3. Routing Procedure

The detailed routing procedure is showed in Figure7. After receiving a hello packet, cluster head checks three conditions including: (1) the hello packet is from a neighbor nearer to the sink node. (2) The residual energy is more than a preset value Re−th. (3) The source node of D exits next-hop. When these three conditions meet requirements, the node calculates the priority pt of the neighbor as (14). If the pt is bigger than the priority value P0 of the next-hop saved before, pt replaces P0. Otherwise, drop the hello packet.Figure 7
Routing algorithm flow chart.


## 4.1. Initialization

Sink nodes broadcast beacon signal including location and ID of themselves. After receiving beacon signal, each cluster head calculates and saves the distance between itself and sink nodes. Then, the cluster head broadcasts hello packet, whose format is showed in Table2. “ID” is the source node ID of the hello packet. Seq number is the sequence number of the hello packet. “ID1,” “ID2,” and “ID3” are the ID of member nodes. Initially, the field of “ID1”, “ID2,” and “ID3” are filled with “0.” Address is the location information of the cluster head. “RE_ENERGY” is the residual energy of the cluster head. The regular node sends information packets after receiving a hello packet. The format of information packet is showed in Table 3. “ID1” is the ID number of the cluster head with the highest priority that the regular node joins in. “Distance 1” is the distance to the cluster head with ID1. “ID2” and “Distance 2” are as the ID1 and Distance1. Before receiving less than three information packets from different regular nodes, the corresponding ID is filled with “0.” Analogously, the ID2 and Distance2 are filled with “0” when receiving hello packets with only ID address.Table 2
Format of hello packet.
ID
Seq number
ID1
ID2
ID3
Reserve
RE_ENERGY
AddressTable 3
Format of information packet.
ID
ID1
Distance1
ID2
Distance 2In this phase, on one hand, regular nodes and cluster heads get information from each other; on the other hand, cluster heads get the information of neighbor cluster heads.


## 4.2. Cluster Constructing

In the process of cluster constructing, the harmony search algorithm is introduced.


### 4.2.1. Harmony Search (HS) Algorithm

HS is a heuristic global search algorithm. The I instruments (I=1,2,…,m) are analogous as the I variables to solve optimization problems, and the harmonic Rj of each musical instrument tone (j=1,2,…,m) is equivalent to the j solution vectors of the optimization problem, and the evolution is analogous to the objective function.The procedure of HS is as follows:(1)
The algorithm generatesm initial solutions into the harmony memory (HM) and searches for new solutions in HM with a probability HR
(2)
The algorithm generates local perturbations to the new solution with probabilityPr. If the new solution objective function value is better than the worst solution in HM, replace it
(3)
Iterate iteratively until the expected number of iterations isTmax
(4)
As above, by introducing HR andPr, HS algorithm is expected to the balance of exploration ability of the solution space, but there is no the recital basis for how to choose the value


### 4.2.2. Simplified HS

According to the characteristics of UWSNs, the average number of regular nodes managed by each cluster head is small, and it is difficult to get the global information of the whole networks. Therefore, the simplified HS algorithm is proposed for UWSNs.(A)
Taking regular nodes as research objects, the assignment is determined by regular nodes. We simplify the HS (HSA) as follows:(1)
The objective function is(10)F1=α∑i=1CHi~dni−CHiR+β∑i=1i=NCHi~−N¯N¯.
Here,α+β=1. dni−CHi presents the distance between the regular node ni and the cluster head CHi. CHi~ presents the number of members for cluster head CHi. R is the communication radius. When CHi~ is constant, the less F1, the better assignment. The first part reflects the balance among regular nodes, and the second part reflects the balance among cluster heads.
(2)
Because any regular node is assigned to only the cluster head in its communication range, we use the local selection of regular nodes being assigned to the cluster head to replace the global assignment. So theXi=xi,1,xi,2…xi,k…xi,n. n is the number of member nodes of cluster heads CHi and adjacent to CHi. Xi is the HM, xi,k is the ID of the cluster head the regular node ni joining in. For example, in Figure 2, the regular nodes are R=n1,n2,n3,n5,n6,n7, X1=1,2,2,2,1,1. While R=n1,n2,n3,n4,n5,n6,n7,n8, X2=1,2,2,2,3,2,1,1,3
(3)
According to the information of cluster heads recorded in the regular nodes, the HM is adjusted at probabilityP. P is calculated by (11). Here, pi′=1/di, p′=∑i=1i=niˇ1/d11/d1, niˇ is the number of cluster head in the communication range of regular node ni, di is the distance between the node ni and the cluster head. If the adjusted objective function is bigger than the value before, replace it. Otherwise, the HM is kept
(11)P=pi′p′.
(B)
Taking cluster heads as research objects, the assignment is determined by cluster heads. We simplify the HS (HSB) as follows:(1)
The objective function is the same as HSA
(2)
Similar to HSA,Xi=xi,1,xi,2…xi,k…xi,n. xi,k is the aggregate of member nodes in the cluster head CHi. As is showed in Figure 2, R=CH1,CH2,CH3, then Xi=n1,n6,n7,n2,n3,n5,,n3,n4,n8
(3)
According to the information of regular nodes recorded in the cluster heads, the HM is adjusted at probabilityP. P is calculated by (12), pi− is the probability each member ni having only one cluster head, and pi′ is the probability ni being adjusted into another cluster head. pi′ can be gotten from (13). Ri and Rj denote the residual energy of the cluster heads in a regular node communication range, CH~i and CH~j are the number of members in a cluster, respectively, γ1+γ2=1
(12)P=1−∏i=1i=CH~i1−1−pi−pi′,(13)pi′=γ1RiRi+Rj+γ21/CHi~1/CHi~+1/CHj~.Figure 2
Regular node assignment.


## 4.2.1. Harmony Search (HS) Algorithm

HS is a heuristic global search algorithm. The I instruments (I=1,2,…,m) are analogous as the I variables to solve optimization problems, and the harmonic Rj of each musical instrument tone (j=1,2,…,m) is equivalent to the j solution vectors of the optimization problem, and the evolution is analogous to the objective function.The procedure of HS is as follows:(1)
The algorithm generatesm initial solutions into the harmony memory (HM) and searches for new solutions in HM with a probability HR
(2)
The algorithm generates local perturbations to the new solution with probabilityPr. If the new solution objective function value is better than the worst solution in HM, replace it
(3)
Iterate iteratively until the expected number of iterations isTmax
(4)
As above, by introducing HR andPr, HS algorithm is expected to the balance of exploration ability of the solution space, but there is no the recital basis for how to choose the value


## 4.2.2. Simplified HS

According to the characteristics of UWSNs, the average number of regular nodes managed by each cluster head is small, and it is difficult to get the global information of the whole networks. Therefore, the simplified HS algorithm is proposed for UWSNs.(A)
Taking regular nodes as research objects, the assignment is determined by regular nodes. We simplify the HS (HSA) as follows:(1)
The objective function is(10)F1=α∑i=1CHi~dni−CHiR+β∑i=1i=NCHi~−N¯N¯.
Here,α+β=1. dni−CHi presents the distance between the regular node ni and the cluster head CHi. CHi~ presents the number of members for cluster head CHi. R is the communication radius. When CHi~ is constant, the less F1, the better assignment. The first part reflects the balance among regular nodes, and the second part reflects the balance among cluster heads.
(2)
Because any regular node is assigned to only the cluster head in its communication range, we use the local selection of regular nodes being assigned to the cluster head to replace the global assignment. So theXi=xi,1,xi,2…xi,k…xi,n. n is the number of member nodes of cluster heads CHi and adjacent to CHi. Xi is the HM, xi,k is the ID of the cluster head the regular node ni joining in. For example, in Figure 2, the regular nodes are R=n1,n2,n3,n5,n6,n7, X1=1,2,2,2,1,1. While R=n1,n2,n3,n4,n5,n6,n7,n8, X2=1,2,2,2,3,2,1,1,3
(3)
According to the information of cluster heads recorded in the regular nodes, the HM is adjusted at probabilityP. P is calculated by (11). Here, pi′=1/di, p′=∑i=1i=niˇ1/d11/d1, niˇ is the number of cluster head in the communication range of regular node ni, di is the distance between the node ni and the cluster head. If the adjusted objective function is bigger than the value before, replace it. Otherwise, the HM is kept
(11)P=pi′p′.
(B)
Taking cluster heads as research objects, the assignment is determined by cluster heads. We simplify the HS (HSB) as follows:(1)
The objective function is the same as HSA
(2)
Similar to HSA,Xi=xi,1,xi,2…xi,k…xi,n. xi,k is the aggregate of member nodes in the cluster head CHi. As is showed in Figure 2, R=CH1,CH2,CH3, then Xi=n1,n6,n7,n2,n3,n5,,n3,n4,n8
(3)
According to the information of regular nodes recorded in the cluster heads, the HM is adjusted at probabilityP. P is calculated by (12), pi− is the probability each member ni having only one cluster head, and pi′ is the probability ni being adjusted into another cluster head. pi′ can be gotten from (13). Ri and Rj denote the residual energy of the cluster heads in a regular node communication range, CH~i and CH~j are the number of members in a cluster, respectively, γ1+γ2=1
(12)P=1−∏i=1i=CH~i1−1−pi−pi′,(13)pi′=γ1RiRi+Rj+γ21/CHi~1/CHi~+1/CHj~.Figure 2
Regular node assignment.


## 4.3. Routing Construction

How are data packets transmitted from a source node to the sink node? In this section, the procedure is analyzed.


### 4.3.1. Review of Routing

According to the initialization procedure, each CH saves the information of neighbor CHs as showed in Table4. After receiving a hello packet, the CH firstly checks the “address” field and calculates the distance between the source node of hello packet and the sink node. Only the cluster head with shorter distance to the sink node has opportunity to be the next-hop. The priority of neighbors is calculated by formula (14). dt is the advanced distance to the sink node. As showed in Figure 3, CH2 is the source cluster head, CH1 is the neighbor of CH2, S is the sink node. The CH2D¯ is the advanced distance to node S. We set the coordinate of CH2, CH1, and S is (x0,y0,z0), (x1,y1,z1), and (0,0,0), respectively. From the coordinate, we can get CH2S¯=xt02+yt02+zt02, CH1S¯=xt12+yt12+zt12, CH2CH1¯=xt0−xt12+yt0−yt12+zt0−zt12, cosθ=CH2CH1¯2+CH2S¯2−CH1S¯2/2CH2CH1¯×CH1S¯. So dt=CH2CH1¯cosθ. The more pt, the higher priority. Only the neighbor cluster head with the highest priority forwards the data packet.
(14)pt=k1ERtEIt+k2dtR.Table 4
Neighbors’ information table of cluster head.
ID
Address
Residual energy
Address of next-hop
Next-hop residual energy
PriorityFigure 3
Advanced distance.As above, the node with bigger advanced distance to sink and more residual energy is selected as the best next-hop. Therefore, the selected next-hop may have far distance to the previous hop, which leads to the big probability of failing to deliver. To enhance the reliability of the network, in our algorithm, coding is introduced.


### 4.3.2. Network Coding

In most of conventional routing algorithms, the forwarder is responsible for relaying data without any processing. However, in UWSNs, like other wireless communications, broadcast is adopted. Meanwhile, the bandwidth is limited and delay is long. In order to make full use of the characteristics of broadcast and limited bandwidth, network coding is an efficient measure. The basic procedure of network coding is showed in Figure4.Figure 4
Coding theory.
(a)
Without coding
(b)
CodingThe data packeta is from node A. The data packet b is from node B. The node C is a relay.In the network without coding as Figure4(a), the necessary number of time slots to exchange data packets a and b is 4. While in Figure 4(b), the number is 3.Furthermore, we compare the partial network coding with the full network coding. In Figure5, the data packets d1, d2, and d3 are sent from the node A to node B. Here, we make
(15)d=d1d2d3.Figure 5
Full network coding and partial network coding.
(a)
Full network coding
(b)
Partial network codingNode A encode data packetsd into d′.
(16)d′=γ11γ12γ13γ21γ22γ23γ31γ32γ33d.To decode the encoded packets into original data packets, node B needs all data packets. So, the delay to transmit these three data packets is 3T (T is one slot time). In Figure5(b), the partial network coding is showed. Here, d1′=γ1d1, d2′=γ2d1+γ3d2, and d3′=γ4d1+γ5d2+γ6d3. So, in the partial network coding, recovering d1′, d2′, and d3′ into original packets needs T, 2T, and 3T, respectively. The average delay to transmit these three packets is T+2T+3T/3=2T. Comparing the partial network coding with full network coding, we can get the partial network coding is better than full network coding.In our algorithm, partial network coding is adopted. Each relay receives the encoded packets and decodes them. Then the next-hop of relay continues to encode the original data packets until the sink node receives the packets. If the sink node is in the communication range of the relay, the decoded packets are directly forwarded to the sink node.As showed in Figure6, during the routing procedure, the CH receives original data packets from member nodes and encodes the original data packets. The CH hears the data packets from regular nodes which are not its member node, drops them. When it hears a data packet from the neighbor with longer distance to the sink node, the CH checks weather it is helpful to decode if the next-hop of data packets is not the current ID. If received encoded packet have been decoded, CH drops it. If there is no association with the encoded packets saved, CH saves them and broadcasts data packets for a certain time. Otherwise, the received data packet is used to decode. For example, CH1 successively hears encoded packets P1, P2, P3 and P4, P1=d1⊕d2, P2=d2⊕d3, P3=d1⊕d3, and P4=d4⊕d5. We assume d1 have been decoded in CH1, then d2 is decoded using P1, d3 is decoded by P2, however, P3 is helpless for decoding any new original packet, CH1 will drop P3. While there is no association between data packets are encoded into P4 and the encoded packets saved in CH1, so CH1 saves P4 and broadcasts P4 after a certain time.Figure 6
Encoding algorithm flow chart.The procedure of encoding algorithm is showed in Figure6.


### 4.3.3. Routing Procedure

The detailed routing procedure is showed in Figure7. After receiving a hello packet, cluster head checks three conditions including: (1) the hello packet is from a neighbor nearer to the sink node. (2) The residual energy is more than a preset value Re−th. (3) The source node of D exits next-hop. When these three conditions meet requirements, the node calculates the priority pt of the neighbor as (14). If the pt is bigger than the priority value P0 of the next-hop saved before, pt replaces P0. Otherwise, drop the hello packet.Figure 7
Routing algorithm flow chart.


## 4.3.1. Review of Routing

According to the initialization procedure, each CH saves the information of neighbor CHs as showed in Table4. After receiving a hello packet, the CH firstly checks the “address” field and calculates the distance between the source node of hello packet and the sink node. Only the cluster head with shorter distance to the sink node has opportunity to be the next-hop. The priority of neighbors is calculated by formula (14). dt is the advanced distance to the sink node. As showed in Figure 3, CH2 is the source cluster head, CH1 is the neighbor of CH2, S is the sink node. The CH2D¯ is the advanced distance to node S. We set the coordinate of CH2, CH1, and S is (x0,y0,z0), (x1,y1,z1), and (0,0,0), respectively. From the coordinate, we can get CH2S¯=xt02+yt02+zt02, CH1S¯=xt12+yt12+zt12, CH2CH1¯=xt0−xt12+yt0−yt12+zt0−zt12, cosθ=CH2CH1¯2+CH2S¯2−CH1S¯2/2CH2CH1¯×CH1S¯. So dt=CH2CH1¯cosθ. The more pt, the higher priority. Only the neighbor cluster head with the highest priority forwards the data packet.
(14)pt=k1ERtEIt+k2dtR.Table 4
Neighbors’ information table of cluster head.
ID
Address
Residual energy
Address of next-hop
Next-hop residual energy
PriorityFigure 3
Advanced distance.As above, the node with bigger advanced distance to sink and more residual energy is selected as the best next-hop. Therefore, the selected next-hop may have far distance to the previous hop, which leads to the big probability of failing to deliver. To enhance the reliability of the network, in our algorithm, coding is introduced.


## 4.3.2. Network Coding

In most of conventional routing algorithms, the forwarder is responsible for relaying data without any processing. However, in UWSNs, like other wireless communications, broadcast is adopted. Meanwhile, the bandwidth is limited and delay is long. In order to make full use of the characteristics of broadcast and limited bandwidth, network coding is an efficient measure. The basic procedure of network coding is showed in Figure4.Figure 4
Coding theory.
(a)
Without coding
(b)
CodingThe data packeta is from node A. The data packet b is from node B. The node C is a relay.In the network without coding as Figure4(a), the necessary number of time slots to exchange data packets a and b is 4. While in Figure 4(b), the number is 3.Furthermore, we compare the partial network coding with the full network coding. In Figure5, the data packets d1, d2, and d3 are sent from the node A to node B. Here, we make
(15)d=d1d2d3.Figure 5
Full network coding and partial network coding.
(a)
Full network coding
(b)
Partial network codingNode A encode data packetsd into d′.
(16)d′=γ11γ12γ13γ21γ22γ23γ31γ32γ33d.To decode the encoded packets into original data packets, node B needs all data packets. So, the delay to transmit these three data packets is 3T (T is one slot time). In Figure5(b), the partial network coding is showed. Here, d1′=γ1d1, d2′=γ2d1+γ3d2, and d3′=γ4d1+γ5d2+γ6d3. So, in the partial network coding, recovering d1′, d2′, and d3′ into original packets needs T, 2T, and 3T, respectively. The average delay to transmit these three packets is T+2T+3T/3=2T. Comparing the partial network coding with full network coding, we can get the partial network coding is better than full network coding.In our algorithm, partial network coding is adopted. Each relay receives the encoded packets and decodes them. Then the next-hop of relay continues to encode the original data packets until the sink node receives the packets. If the sink node is in the communication range of the relay, the decoded packets are directly forwarded to the sink node.As showed in Figure6, during the routing procedure, the CH receives original data packets from member nodes and encodes the original data packets. The CH hears the data packets from regular nodes which are not its member node, drops them. When it hears a data packet from the neighbor with longer distance to the sink node, the CH checks weather it is helpful to decode if the next-hop of data packets is not the current ID. If received encoded packet have been decoded, CH drops it. If there is no association with the encoded packets saved, CH saves them and broadcasts data packets for a certain time. Otherwise, the received data packet is used to decode. For example, CH1 successively hears encoded packets P1, P2, P3 and P4, P1=d1⊕d2, P2=d2⊕d3, P3=d1⊕d3, and P4=d4⊕d5. We assume d1 have been decoded in CH1, then d2 is decoded using P1, d3 is decoded by P2, however, P3 is helpless for decoding any new original packet, CH1 will drop P3. While there is no association between data packets are encoded into P4 and the encoded packets saved in CH1, so CH1 saves P4 and broadcasts P4 after a certain time.Figure 6
Encoding algorithm flow chart.The procedure of encoding algorithm is showed in Figure6.


## 4.3.3. Routing Procedure

The detailed routing procedure is showed in Figure7. After receiving a hello packet, cluster head checks three conditions including: (1) the hello packet is from a neighbor nearer to the sink node. (2) The residual energy is more than a preset value Re−th. (3) The source node of D exits next-hop. When these three conditions meet requirements, the node calculates the priority pt of the neighbor as (14). If the pt is bigger than the priority value P0 of the next-hop saved before, pt replaces P0. Otherwise, drop the hello packet.Figure 7
Routing algorithm flow chart.


## 5. Routing Maintained and Update

Because of the topology is mobile as the time goes by, routing needs to be updated timely. Here, there are two schemes to update route.


### 5.1. Scheme 1

In our protocol, data is transmitted block by block [27]. In scheme 1, control packets are introduced. After receiving the last packets in a block, the next-hop node reply ACK packets including the number and ID of recovered packets and unrecovered packets. When the ratio of recovered packets to transmitted packets is lower than 70%, the previous hop resends the unrecovered original packets. Meanwhile, the cluster head sends request packets to update routing. The neighbor nodes send reply packets after receiving hello packets according to the requirements in Figure 7. The node calculates the priority and updates the best next-hop.The scheme 1 is simple to realize, and period broadcasting control packets is avoided. Extra control packets are decreased compared with the previous routing update algorithms, which decreases the collisions and energy consumption. Meanwhile, only the next-hop with lower delivery ratio is updated, and other nodes are not affected.However, the back and forth time of the control packets is too long because of the long propagation delay in UWSNs. The unstable stage results in the failing to deliver data packets. Therefore, the scheme 2 of updating routing is proposed.


### 5.2. Scheme 2

We know, in our algorithm, the location information of nodes can be gotten. The updating algorithm can be designed according to the location information. As Figure8, CH1 is the sender and CH2 and CH3 are the neighbors of CH1 with the shorter distance to the sink node. With the water flow by, CH2 and CH3 may run out of the communication range of CH1 in some time. Because of the distance between CH1 and its neighbors is different, the time varies. To get the average time of running out of the current cluster head for each neighbor, the expected value of time is calculated.Figure 8
Expected time.Comparing with the horizontal movement, the motion of vertical direction has a small range and can be ignored. The neighbors with shorter distance to the sink node are set as uniform distribution. The expected distance,Ed¯, running out of communication range is showed as (17). The expected time is Et¯ as showed in (18). Here, v is the water flow speed. The period of updating routing is set as Et¯.
(17)Ed¯=∫0R∫0RR2−y2−xdxdy,(18)Et¯=Ed¯v.


## 5.1. Scheme 1

In our protocol, data is transmitted block by block [27]. In scheme 1, control packets are introduced. After receiving the last packets in a block, the next-hop node reply ACK packets including the number and ID of recovered packets and unrecovered packets. When the ratio of recovered packets to transmitted packets is lower than 70%, the previous hop resends the unrecovered original packets. Meanwhile, the cluster head sends request packets to update routing. The neighbor nodes send reply packets after receiving hello packets according to the requirements in Figure 7. The node calculates the priority and updates the best next-hop.The scheme 1 is simple to realize, and period broadcasting control packets is avoided. Extra control packets are decreased compared with the previous routing update algorithms, which decreases the collisions and energy consumption. Meanwhile, only the next-hop with lower delivery ratio is updated, and other nodes are not affected.However, the back and forth time of the control packets is too long because of the long propagation delay in UWSNs. The unstable stage results in the failing to deliver data packets. Therefore, the scheme 2 of updating routing is proposed.


## 5.2. Scheme 2

We know, in our algorithm, the location information of nodes can be gotten. The updating algorithm can be designed according to the location information. As Figure8, CH1 is the sender and CH2 and CH3 are the neighbors of CH1 with the shorter distance to the sink node. With the water flow by, CH2 and CH3 may run out of the communication range of CH1 in some time. Because of the distance between CH1 and its neighbors is different, the time varies. To get the average time of running out of the current cluster head for each neighbor, the expected value of time is calculated.Figure 8
Expected time.Comparing with the horizontal movement, the motion of vertical direction has a small range and can be ignored. The neighbors with shorter distance to the sink node are set as uniform distribution. The expected distance,Ed¯, running out of communication range is showed as (17). The expected time is Et¯ as showed in (18). Here, v is the water flow speed. The period of updating routing is set as Et¯.
(17)Ed¯=∫0R∫0RR2−y2−xdxdy,(18)Et¯=Ed¯v.


## 6. Performance Evaluation

### 6.1. Theoretical Analysis

#### 6.1.1. The Size of a Block

To get the information of recovered data packets in next-hop, an ACK packet is necessary from the next-hop. To decrease the number of ACK packets, an ACK packet is sent for a block. The bigger the block, the less ACK to transmit constant data packets. However, because of the harsh environment under water, the bigger the block, the less probability of a successful delivery, which leads to too many re-transmission of original data packets. We know, the more original packets being transmission, the more energy consumption.For the size of block isnb packets and the packets is l bits, we assume the probability failing to deliver one bit is p. The probability of a block successfully delivery to next-hop is P as (19).
(19)P=1−plnb=1−pnbl.Therefore, we should select moderate block size to balance the delivery ratio and energy consumption.


#### 6.1.2. The Number of Encoded Packets

From the basic theory of coding, we know the number of sending encoded packets should be more than original packets to decode them into initial packets. In fact, the more linearly independent encoded packets are sent, the easier they are to decode. However, too many packets being transmitted wastes energy and results in collision. The effective transmission is defined as (20). μ can be adjusted according to ACK from the next-hop. When the ratio recovered packets to total transmitted original packets is lower than α0, the number of sending encoded packets must be adjusted according to (21). αt is the number ratio of recovered packets to total transmitted original packets at time t.
(20)μ=numberofsendingencodedpacketsnumberoforiginaldatapackets,(21)μt+1=μt+μtα0−αt.


#### 6.1.3. The Energy Consumption

We assume the total number of original packets isn0 and the average ratio sending encoded packets to original packets is μ0. Because the number ratio of recovered packets to total transmitted original packets fluctuates near α0, the average value is set as α0. The average hop is nh. Therefore, the total number of sending data packets N′ is showed as (22).
(22)N′=n01+μ0+n01−α0.In addition, the ACK packets are sent, and the number of ACK packets is relative with the size of block. So, the number of ACK packetsna is showed in (23)
(23)na=n0nb.During initial phase and routing updating phase, the control packets are sent. The number of control packets is increased as the number of nodes. We assume the value is constantnc. During routing update phase, in scheme 1, only the recovered ratio is lowered than 70%, the node sends request packet, and the neighbor sends reply packets. We set the number of control packets as ncu. In scheme 2, the node update routing according to Et¯. The number of sending control packets is nu=Tl/Et¯nc.In our algorithm, for simplicity, the energy consumption of receiving packets is ignored, the energy consumption of sending a data packets and a control packet is set ased and ec. Therefore, the energy consumption E in scheme 1 and scheme 2 are showed, respectively, as (24) and (25).
(24)E=N′ed+nc+ncuec,(25)E=N′ed+nc+TlEt¯ncec.


### 6.2. Simulation Analysis

Because the cost of arranging the UWSNs is too high, simulations are adopted to evaluate the performance of the designed protocol. NS3 is a popular simulator to simulate UWSNs. NS3 offers some characteristics that other simulators have not, such as underpinning to discrete-event-driven networks, simulation of high-fidelity UWSNs channels, complete protocol stack, and mobile 3D networks. Firstly, the schemes of constructing cluster and updating routing are evaluated. Secondly, the influence of the node density and the number ratio of regular nodes to cluster heads on the performance of the system is tested. Lastly, we compare RSHSC with NCRP and VBF. NCRP uses network coding to greedily forward data packets to the sink. VBF constructs a vector pipe from the source node to the sink node. Only the nodes in the pipe forward data.In our simulations, the nodes are deployed in a 3D area with 3000 m∗3000 m∗2000 m. The number of data packets is set as 60 in a block. When a node energy is exhausted, the simulation of this round is over. We show the average value of 50 runs. The detailed parameters are set as follows:The data rate is 10 kbps. The center frequency is 12 KHZ. The bandwidth is 10 KHZ. Packet error rate model is ns3: UanPhyPerNoCode. Mode type is FSK. Signal noise model is ns3 :: Uan Phy Calc Sinr Default. Acoustic propagation speed is 1500 m/s. UAN Propagation model is ns3 :: Uan Prop Model Thorp. Energy model is acoustic modem energy model. MAC model is CWMAC. The mobility model is random walk 2D mobility model (speed: 2 ∼ 4 m/s, directions are chosen randomly). The payload of DATA is 64 bytes, and the number of data packets in each block is 60. Deployment region is 3D region of 3 × 3 × 2 km3. Node number is 20–75. The initial energy of advanced nodes is set as 100 J, and regular nodes is set as 25 J.


#### 6.2.1. Performance at Different Cases

In our design, the ways of constructing clusters include SHSA and SHSB. Maintaining routing includes scheme 1 and scheme 2. Here, the number ratio of regular nodes to advanced node is 2 : 1. To evaluate the performance of each scheme, four cases are studied as Table4. Delivery ratio and network life are two important parameters to evaluate the performance of the protocol. Delivery ratio is the ratio of number of sink nodes received data packets to the number of regular nodes sent data packets. Network life is total performing time until the first node drains its energy. For simplicity, we replace network life with the ratio of network life to evaluate the performance of the protocol.From Figure9(a) (Supplementary material (available here)), the delivery ratio of SHSA is almost the same with SHSB. The SHSA is based on regular based during constructing cluster, which can make each regular node assigned to a cluster head. Some regular nodes are kicked out by all cluster heads in its coverage in SHSB, which leads to the data packets collected by these nodes cannot be delivered to the sink node. The delivery ratio of scheme 2 is lower than scheme 1. On the one hand, a large number of control packets cause collisions. On the other hand, the instability of the whole network leads to the failure of delivery. The instable stage in scheme 1 also leads to failure of delivery. However, the successful reception of an original packet may increase the delivery rate. Because the reception of an original packet can help to decode multiple encoding packets. The different cases are showed in Table 5. In Figure 9(b), the network life ratio is not almost affected by the SHSA and SHSB (Supplementary material). The network life of case 1 and case 2 is longer than case 3 and case 4. Because scheme 2 produces many control packets, which wastes energy. Combining the above simulation results, we continue to study the performance of the protocol based on case 1.Figure 9
Affection of different schemes.
(a)
The delivery ratio
(b)
The network life ratioTable 5
Four cases.
Case number
Constructing cluster
Maintaining routing
Case 1
SHSA
Scheme 1
Case 2
SHSB
Scheme 1
Case 3
SHSA
Scheme 2
Case 4
SHSB
Scheme 2


#### 6.2.2. The Affection of Number Ratio of Regular Nodes to Advanced Nodes (RRTA)

In Figure10 (Supplementary material), N presents the layer numbers of advanced node being layout along vertical direction. We can see that the network life ratio decreases with the RRTA increasing, which is because the node first drains energy is regular node when the ratio is small. The regular nodes are in charge of only collecting data. The lifetime of regular nodes is related with the frequency of producing data packets and the initial energy. Meanwhile, the network life ratio decreases with the layer numbers increasing, because of the more layers, upper cluster heads consuming more energy than below nodes. In our simulation, the deliver ratio is about 60% when the communication range of nodes is 1000 m [27], and the vertical depth of the research area is 2000 m. Therefore, we select N=3 and RRTA=3.Figure 10
Affection of RRTA.


#### 6.2.3. Comparation with NCRP and VBF

NCRP is a cross-layer routing protocol based on network coding (NCRP) for UWSNs, which utilizes network coding and cross-layer design to greedily forward data packets to sink nodes efficiently [27]. We set 60 data packets in each transmission block. The degree distribution is degree value = [1 4 6], degree probability distribution = [0.500 0.075 0.425], and average degree = 3.35. In VBF, a vector pipe is created from the source to the sink node [30]. Only the node in the pipe is qualified to be the next-hop. To limit the number of forwarding nodes, the delay time of forwarding data for each node is set. In simulations, the routing pipe radius is set as 300 m, the time interval of forwarding a packet is set as Tadaption=α×Tdelay+R−d/v0, α is calculated according to [30], Tdelay is set as 0.02d¯, d¯ is the average distance among all nodes. R is the transmission radius. d is the distance between the current node and the forwarder. The other simulation parameters of VBF and NCRP are the same with the RSHSC.From Figure11(a) (Supplementary material), the delivery ratio of RSHSC is higher than VBF. Because in VBF, only the nodes in the pipe can forward data packets. However, in the sparse network, there may be no nodes in the pipeline, which leads to the failure of delivery. The delivery ratio of RSHSC is higher than NCRP. Although both the two protocols use coding techniques, the information of the next two hop is considered in RSHSC and avoids selecting void node as the next-hop. Figure 11(b) shows the comparation of energy consumption (Supplementary material). The energy consumption of VBF is higher than others, because VBF needs to send a large number of control packets. In addition, redundant forwarding exists in VBF. The energy consumption of RSHSC is lower than NCRP. In NCRP, the secondary nodes join to forward data packets, which wastes energy. While in RSHSC, only the best next-hop forwards data packets, and the data packets from other neighbors just join to decode. In addition, simplified harmony search algorithm is helpful to save energy of regular nodes and balance the energy among cluster heads. Figure 11(c) indicates the end-to-end delay of RSHSC is almost equal to NCRP and lower than VBF. Because VBF needs to wait to forward data packets, while NCRP and RSHSC transmit data block by block, the node immediately forward once received a data packet. After transmitting a block, the acknowledgement is sent, which shortens waiting time.Figure 11
Comparation of performance.
(a)
Delivery ratio
(b)
Energy consumption per packet
(c)
End-to-end delay


## 6.1. Theoretical Analysis

### 6.1.1. The Size of a Block

To get the information of recovered data packets in next-hop, an ACK packet is necessary from the next-hop. To decrease the number of ACK packets, an ACK packet is sent for a block. The bigger the block, the less ACK to transmit constant data packets. However, because of the harsh environment under water, the bigger the block, the less probability of a successful delivery, which leads to too many re-transmission of original data packets. We know, the more original packets being transmission, the more energy consumption.For the size of block isnb packets and the packets is l bits, we assume the probability failing to deliver one bit is p. The probability of a block successfully delivery to next-hop is P as (19).
(19)P=1−plnb=1−pnbl.Therefore, we should select moderate block size to balance the delivery ratio and energy consumption.


### 6.1.2. The Number of Encoded Packets

From the basic theory of coding, we know the number of sending encoded packets should be more than original packets to decode them into initial packets. In fact, the more linearly independent encoded packets are sent, the easier they are to decode. However, too many packets being transmitted wastes energy and results in collision. The effective transmission is defined as (20). μ can be adjusted according to ACK from the next-hop. When the ratio recovered packets to total transmitted original packets is lower than α0, the number of sending encoded packets must be adjusted according to (21). αt is the number ratio of recovered packets to total transmitted original packets at time t.
(20)μ=numberofsendingencodedpacketsnumberoforiginaldatapackets,(21)μt+1=μt+μtα0−αt.


### 6.1.3. The Energy Consumption

We assume the total number of original packets isn0 and the average ratio sending encoded packets to original packets is μ0. Because the number ratio of recovered packets to total transmitted original packets fluctuates near α0, the average value is set as α0. The average hop is nh. Therefore, the total number of sending data packets N′ is showed as (22).
(22)N′=n01+μ0+n01−α0.In addition, the ACK packets are sent, and the number of ACK packets is relative with the size of block. So, the number of ACK packetsna is showed in (23)
(23)na=n0nb.During initial phase and routing updating phase, the control packets are sent. The number of control packets is increased as the number of nodes. We assume the value is constantnc. During routing update phase, in scheme 1, only the recovered ratio is lowered than 70%, the node sends request packet, and the neighbor sends reply packets. We set the number of control packets as ncu. In scheme 2, the node update routing according to Et¯. The number of sending control packets is nu=Tl/Et¯nc.In our algorithm, for simplicity, the energy consumption of receiving packets is ignored, the energy consumption of sending a data packets and a control packet is set ased and ec. Therefore, the energy consumption E in scheme 1 and scheme 2 are showed, respectively, as (24) and (25).
(24)E=N′ed+nc+ncuec,(25)E=N′ed+nc+TlEt¯ncec.


## 6.1.1. The Size of a Block

To get the information of recovered data packets in next-hop, an ACK packet is necessary from the next-hop. To decrease the number of ACK packets, an ACK packet is sent for a block. The bigger the block, the less ACK to transmit constant data packets. However, because of the harsh environment under water, the bigger the block, the less probability of a successful delivery, which leads to too many re-transmission of original data packets. We know, the more original packets being transmission, the more energy consumption.For the size of block isnb packets and the packets is l bits, we assume the probability failing to deliver one bit is p. The probability of a block successfully delivery to next-hop is P as (19).
(19)P=1−plnb=1−pnbl.Therefore, we should select moderate block size to balance the delivery ratio and energy consumption.


## 6.1.2. The Number of Encoded Packets

From the basic theory of coding, we know the number of sending encoded packets should be more than original packets to decode them into initial packets. In fact, the more linearly independent encoded packets are sent, the easier they are to decode. However, too many packets being transmitted wastes energy and results in collision. The effective transmission is defined as (20). μ can be adjusted according to ACK from the next-hop. When the ratio recovered packets to total transmitted original packets is lower than α0, the number of sending encoded packets must be adjusted according to (21). αt is the number ratio of recovered packets to total transmitted original packets at time t.
(20)μ=numberofsendingencodedpacketsnumberoforiginaldatapackets,(21)μt+1=μt+μtα0−αt.


## 6.1.3. The Energy Consumption

We assume the total number of original packets isn0 and the average ratio sending encoded packets to original packets is μ0. Because the number ratio of recovered packets to total transmitted original packets fluctuates near α0, the average value is set as α0. The average hop is nh. Therefore, the total number of sending data packets N′ is showed as (22).
(22)N′=n01+μ0+n01−α0.In addition, the ACK packets are sent, and the number of ACK packets is relative with the size of block. So, the number of ACK packetsna is showed in (23)
(23)na=n0nb.During initial phase and routing updating phase, the control packets are sent. The number of control packets is increased as the number of nodes. We assume the value is constantnc. During routing update phase, in scheme 1, only the recovered ratio is lowered than 70%, the node sends request packet, and the neighbor sends reply packets. We set the number of control packets as ncu. In scheme 2, the node update routing according to Et¯. The number of sending control packets is nu=Tl/Et¯nc.In our algorithm, for simplicity, the energy consumption of receiving packets is ignored, the energy consumption of sending a data packets and a control packet is set ased and ec. Therefore, the energy consumption E in scheme 1 and scheme 2 are showed, respectively, as (24) and (25).
(24)E=N′ed+nc+ncuec,(25)E=N′ed+nc+TlEt¯ncec.


## 6.2. Simulation Analysis

Because the cost of arranging the UWSNs is too high, simulations are adopted to evaluate the performance of the designed protocol. NS3 is a popular simulator to simulate UWSNs. NS3 offers some characteristics that other simulators have not, such as underpinning to discrete-event-driven networks, simulation of high-fidelity UWSNs channels, complete protocol stack, and mobile 3D networks. Firstly, the schemes of constructing cluster and updating routing are evaluated. Secondly, the influence of the node density and the number ratio of regular nodes to cluster heads on the performance of the system is tested. Lastly, we compare RSHSC with NCRP and VBF. NCRP uses network coding to greedily forward data packets to the sink. VBF constructs a vector pipe from the source node to the sink node. Only the nodes in the pipe forward data.In our simulations, the nodes are deployed in a 3D area with 3000 m∗3000 m∗2000 m. The number of data packets is set as 60 in a block. When a node energy is exhausted, the simulation of this round is over. We show the average value of 50 runs. The detailed parameters are set as follows:The data rate is 10 kbps. The center frequency is 12 KHZ. The bandwidth is 10 KHZ. Packet error rate model is ns3: UanPhyPerNoCode. Mode type is FSK. Signal noise model is ns3 :: Uan Phy Calc Sinr Default. Acoustic propagation speed is 1500 m/s. UAN Propagation model is ns3 :: Uan Prop Model Thorp. Energy model is acoustic modem energy model. MAC model is CWMAC. The mobility model is random walk 2D mobility model (speed: 2 ∼ 4 m/s, directions are chosen randomly). The payload of DATA is 64 bytes, and the number of data packets in each block is 60. Deployment region is 3D region of 3 × 3 × 2 km3. Node number is 20–75. The initial energy of advanced nodes is set as 100 J, and regular nodes is set as 25 J.


### 6.2.1. Performance at Different Cases

In our design, the ways of constructing clusters include SHSA and SHSB. Maintaining routing includes scheme 1 and scheme 2. Here, the number ratio of regular nodes to advanced node is 2 : 1. To evaluate the performance of each scheme, four cases are studied as Table4. Delivery ratio and network life are two important parameters to evaluate the performance of the protocol. Delivery ratio is the ratio of number of sink nodes received data packets to the number of regular nodes sent data packets. Network life is total performing time until the first node drains its energy. For simplicity, we replace network life with the ratio of network life to evaluate the performance of the protocol.From Figure9(a) (Supplementary material (available here)), the delivery ratio of SHSA is almost the same with SHSB. The SHSA is based on regular based during constructing cluster, which can make each regular node assigned to a cluster head. Some regular nodes are kicked out by all cluster heads in its coverage in SHSB, which leads to the data packets collected by these nodes cannot be delivered to the sink node. The delivery ratio of scheme 2 is lower than scheme 1. On the one hand, a large number of control packets cause collisions. On the other hand, the instability of the whole network leads to the failure of delivery. The instable stage in scheme 1 also leads to failure of delivery. However, the successful reception of an original packet may increase the delivery rate. Because the reception of an original packet can help to decode multiple encoding packets. The different cases are showed in Table 5. In Figure 9(b), the network life ratio is not almost affected by the SHSA and SHSB (Supplementary material). The network life of case 1 and case 2 is longer than case 3 and case 4. Because scheme 2 produces many control packets, which wastes energy. Combining the above simulation results, we continue to study the performance of the protocol based on case 1.Figure 9
Affection of different schemes.
(a)
The delivery ratio
(b)
The network life ratioTable 5
Four cases.
Case number
Constructing cluster
Maintaining routing
Case 1
SHSA
Scheme 1
Case 2
SHSB
Scheme 1
Case 3
SHSA
Scheme 2
Case 4
SHSB
Scheme 2


### 6.2.2. The Affection of Number Ratio of Regular Nodes to Advanced Nodes (RRTA)

In Figure10 (Supplementary material), N presents the layer numbers of advanced node being layout along vertical direction. We can see that the network life ratio decreases with the RRTA increasing, which is because the node first drains energy is regular node when the ratio is small. The regular nodes are in charge of only collecting data. The lifetime of regular nodes is related with the frequency of producing data packets and the initial energy. Meanwhile, the network life ratio decreases with the layer numbers increasing, because of the more layers, upper cluster heads consuming more energy than below nodes. In our simulation, the deliver ratio is about 60% when the communication range of nodes is 1000 m [27], and the vertical depth of the research area is 2000 m. Therefore, we select N=3 and RRTA=3.Figure 10
Affection of RRTA.


### 6.2.3. Comparation with NCRP and VBF

NCRP is a cross-layer routing protocol based on network coding (NCRP) for UWSNs, which utilizes network coding and cross-layer design to greedily forward data packets to sink nodes efficiently [27]. We set 60 data packets in each transmission block. The degree distribution is degree value = [1 4 6], degree probability distribution = [0.500 0.075 0.425], and average degree = 3.35. In VBF, a vector pipe is created from the source to the sink node [30]. Only the node in the pipe is qualified to be the next-hop. To limit the number of forwarding nodes, the delay time of forwarding data for each node is set. In simulations, the routing pipe radius is set as 300 m, the time interval of forwarding a packet is set as Tadaption=α×Tdelay+R−d/v0, α is calculated according to [30], Tdelay is set as 0.02d¯, d¯ is the average distance among all nodes. R is the transmission radius. d is the distance between the current node and the forwarder. The other simulation parameters of VBF and NCRP are the same with the RSHSC.From Figure11(a) (Supplementary material), the delivery ratio of RSHSC is higher than VBF. Because in VBF, only the nodes in the pipe can forward data packets. However, in the sparse network, there may be no nodes in the pipeline, which leads to the failure of delivery. The delivery ratio of RSHSC is higher than NCRP. Although both the two protocols use coding techniques, the information of the next two hop is considered in RSHSC and avoids selecting void node as the next-hop. Figure 11(b) shows the comparation of energy consumption (Supplementary material). The energy consumption of VBF is higher than others, because VBF needs to send a large number of control packets. In addition, redundant forwarding exists in VBF. The energy consumption of RSHSC is lower than NCRP. In NCRP, the secondary nodes join to forward data packets, which wastes energy. While in RSHSC, only the best next-hop forwards data packets, and the data packets from other neighbors just join to decode. In addition, simplified harmony search algorithm is helpful to save energy of regular nodes and balance the energy among cluster heads. Figure 11(c) indicates the end-to-end delay of RSHSC is almost equal to NCRP and lower than VBF. Because VBF needs to wait to forward data packets, while NCRP and RSHSC transmit data block by block, the node immediately forward once received a data packet. After transmitting a block, the acknowledgement is sent, which shortens waiting time.Figure 11
Comparation of performance.
(a)
Delivery ratio
(b)
Energy consumption per packet
(c)
End-to-end delay


## 6.2.1. Performance at Different Cases

In our design, the ways of constructing clusters include SHSA and SHSB. Maintaining routing includes scheme 1 and scheme 2. Here, the number ratio of regular nodes to advanced node is 2 : 1. To evaluate the performance of each scheme, four cases are studied as Table4. Delivery ratio and network life are two important parameters to evaluate the performance of the protocol. Delivery ratio is the ratio of number of sink nodes received data packets to the number of regular nodes sent data packets. Network life is total performing time until the first node drains its energy. For simplicity, we replace network life with the ratio of network life to evaluate the performance of the protocol.From Figure9(a) (Supplementary material (available here)), the delivery ratio of SHSA is almost the same with SHSB. The SHSA is based on regular based during constructing cluster, which can make each regular node assigned to a cluster head. Some regular nodes are kicked out by all cluster heads in its coverage in SHSB, which leads to the data packets collected by these nodes cannot be delivered to the sink node. The delivery ratio of scheme 2 is lower than scheme 1. On the one hand, a large number of control packets cause collisions. On the other hand, the instability of the whole network leads to the failure of delivery. The instable stage in scheme 1 also leads to failure of delivery. However, the successful reception of an original packet may increase the delivery rate. Because the reception of an original packet can help to decode multiple encoding packets. The different cases are showed in Table 5. In Figure 9(b), the network life ratio is not almost affected by the SHSA and SHSB (Supplementary material). The network life of case 1 and case 2 is longer than case 3 and case 4. Because scheme 2 produces many control packets, which wastes energy. Combining the above simulation results, we continue to study the performance of the protocol based on case 1.Figure 9
Affection of different schemes.
(a)
The delivery ratio
(b)
The network life ratioTable 5
Four cases.
Case number
Constructing cluster
Maintaining routing
Case 1
SHSA
Scheme 1
Case 2
SHSB
Scheme 1
Case 3
SHSA
Scheme 2
Case 4
SHSB
Scheme 2


## 6.2.2. The Affection of Number Ratio of Regular Nodes to Advanced Nodes (RRTA)

In Figure10 (Supplementary material), N presents the layer numbers of advanced node being layout along vertical direction. We can see that the network life ratio decreases with the RRTA increasing, which is because the node first drains energy is regular node when the ratio is small. The regular nodes are in charge of only collecting data. The lifetime of regular nodes is related with the frequency of producing data packets and the initial energy. Meanwhile, the network life ratio decreases with the layer numbers increasing, because of the more layers, upper cluster heads consuming more energy than below nodes. In our simulation, the deliver ratio is about 60% when the communication range of nodes is 1000 m [27], and the vertical depth of the research area is 2000 m. Therefore, we select N=3 and RRTA=3.Figure 10
Affection of RRTA.


## 6.2.3. Comparation with NCRP and VBF

NCRP is a cross-layer routing protocol based on network coding (NCRP) for UWSNs, which utilizes network coding and cross-layer design to greedily forward data packets to sink nodes efficiently [27]. We set 60 data packets in each transmission block. The degree distribution is degree value = [1 4 6], degree probability distribution = [0.500 0.075 0.425], and average degree = 3.35. In VBF, a vector pipe is created from the source to the sink node [30]. Only the node in the pipe is qualified to be the next-hop. To limit the number of forwarding nodes, the delay time of forwarding data for each node is set. In simulations, the routing pipe radius is set as 300 m, the time interval of forwarding a packet is set as Tadaption=α×Tdelay+R−d/v0, α is calculated according to [30], Tdelay is set as 0.02d¯, d¯ is the average distance among all nodes. R is the transmission radius. d is the distance between the current node and the forwarder. The other simulation parameters of VBF and NCRP are the same with the RSHSC.From Figure11(a) (Supplementary material), the delivery ratio of RSHSC is higher than VBF. Because in VBF, only the nodes in the pipe can forward data packets. However, in the sparse network, there may be no nodes in the pipeline, which leads to the failure of delivery. The delivery ratio of RSHSC is higher than NCRP. Although both the two protocols use coding techniques, the information of the next two hop is considered in RSHSC and avoids selecting void node as the next-hop. Figure 11(b) shows the comparation of energy consumption (Supplementary material). The energy consumption of VBF is higher than others, because VBF needs to send a large number of control packets. In addition, redundant forwarding exists in VBF. The energy consumption of RSHSC is lower than NCRP. In NCRP, the secondary nodes join to forward data packets, which wastes energy. While in RSHSC, only the best next-hop forwards data packets, and the data packets from other neighbors just join to decode. In addition, simplified harmony search algorithm is helpful to save energy of regular nodes and balance the energy among cluster heads. Figure 11(c) indicates the end-to-end delay of RSHSC is almost equal to NCRP and lower than VBF. Because VBF needs to wait to forward data packets, while NCRP and RSHSC transmit data block by block, the node immediately forward once received a data packet. After transmitting a block, the acknowledgement is sent, which shortens waiting time.Figure 11
Comparation of performance.
(a)
Delivery ratio
(b)
Energy consumption per packet
(c)
End-to-end delay


## 7. Conclusion

In this paper, RSHSC, an energy effective and reliable routing protocol based on harmony search algorithm and coding, is proposed for UWSNs. The process of RSHSC can be mainly divided into four parts: initialization, constructing clusters, intercluster routing and routing maintenance. In the initialization phase, the control packets are sent and nodes got the information of each other. In the process of constructing routing, each regular node is assigned to a cluster head according to simplified harmony search algorithm. The energy balance between cluster heads and the energy between ordinary nodes are taken into account when assigning. During the process of constructing routing, data packets are encoded. The best next-hop is responsible for forwarding data packets. The data packets from other neighbors is used to decode. The utilization of data packets from other neighbors increases the channel utilization. Meanwhile, the next two-hop is considered when selecting the best next-hop, which avoids the void node being selected as the next-hop. Two schemes are compared in the phase of maintaining routing. We get that scheme 1 is effective to save energy via theoretical analysis. Lastly, extensive simulations are conducted based NS-3. The results show that RSHSC is more effective than VBF and NCRP in decreasing energy consumption and increasing delivery ratio. In the future work, we will explore the implement of RSHSC and the better topology for improving the performance of UWSNs.



---

*Source: 1091630-2018-11-13.xml*