# Towards a Secure Medium Access Control Protocol for Cluster-Based Underwater Wireless Sensor Networks

Authors: Ming Xu; Guangzhong Liu; Jihong Guan
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

The unique characteristics of high bit error rate, low bandwidth, and long propagation delay in underwater environments pose significant challenges to the design of the medium access control (MAC) protocol for underwater wireless sensor networks (UWSNs). Clustering is an effective and practical way to enhance the performance of UWSNs. In this paper, we propose a secure MAC protocol for cluster-based UWSNs, called SC-MAC, which aims to ensure the security of data transmission. In SC-MAC, the clusters are formed and updated dynamically and securely. We leverage MAC layer information by considering the link quality as well as residual energy of the modem’s battery. After the successful mutual authentication, all sensor nodes from different clusters can protect the data transmission in the continuous communication. As the states of sensor nodes may not be observed accurately in a harsh underwater environment, we formulate the channel scheduling process as a stochastic partially observed Markov decision process (POMDP) multiarmed bandit problem and derive the optimal channel scheduling rules hereby. Simulation results show that SC-MAC can perform better than existing state-of-the-art MAC protocols in terms of network throughput, successful delivery ratio, and energy consumption in various circumstances.


---

## Body

## 1. Introduction

Underwater Wireless Sensor Networks (UWSNs) have a lot of potential application areas such as oceanographic data collection, disaster prevention, pollution monitoring, offshore exploration, and military surveillance [1–3]. The individual underwater sensor nodes are capable of sensing their environments, processing the information data locally, and forwarding data to one or more sink nodes in UWSNs. Since radio does not work underwater due to high attenuation, acoustic signals are widely used in underwater networks. Compared with radio channels, acoustic channels feature high error rates, low available bandwidth, and long propagation delays (acoustic signals propagate 5 orders of magnitude slower than electromagnetic waves). To better utilize network bandwidth in the face of channel interference, many medium access control (MAC) protocols have been proposed [4]. In general, MAC protocols can be roughly divided into two categories: contention-free protocols and contention-based protocols [5]. In contention-free protocols, communication channels are separated into time, frequency, or code domains, such as Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), and Code Division Multiple Access (CDMA) [6–8]. TDMA allows sharing the same frequency channel by dividing the signal into different time slots. In order to maintain reliable transmission schedules, all sensor nodes must remain synchronized, which incur additional control packets and scheduling operations. FDMA divides the frequency band into several subbands, but only a narrow available underwater acoustic bandwidth can be used due to the prevalent fading in underwater environments, which results in a low throughput. CDMA is robust against frequency-selective fading and allows receivers to distinguish among signals simultaneously transmitted by multiple devices, which in turn increases channel utilization and reduces packet retransmissions. However, CDMA is not suitable for UWSNs because it is difficult to assign pseudo random codes to a large number of sensor nodes. Also, the inherent near-far problem in CDMA is not well addressed in UWSNs.Contention-based protocols include random access methods and collision avoidance methods [9]. In a random access protocol, the sender sends packets without coordination. When a data packet arrives at a receiver, if the receiver is not receiving any other packets and there is no other packet coming in this period, the receiver can receive this packet successfully. Thus, the packet avoidance is totally probabilistic. While, in a collision avoidance protocol, the sender and receiver capture the medium through control packet exchange before data transmission. For example, Carrier Sense Multiple Access (CSMA) protocols with their variances can improve the system energy efficiency using Request-To-Send/Clear-To-Send (RTS/CTS) like handshaking approaches [10–12]. However, the network throughput is still low since a significant part of system time is used for the handshaking and one time-consuming handshaking process usually only reserves the channel for one sender-receiver pair. Although a couple of newly proposed CSMA-based protocols [13, 14] attempt to address this challenge by enabling channel reuse through concurrent transmission sessions, these protocols still neglect the consideration of complex underwater circumstances and cannot fully exploit the acoustic channel reuse properties.Cluster-based UWSNs have been investigated by researchers to achieve the network scalability and efficiency, which maximize network lifetime and reduce bandwidth consumption by using local collaboration among sensor nodes. However, because of the broadcast nature of acoustic communication, cluster-based UWSNs are vulnerable to many critical security attacks, including Sybil attack, replay attack, and message manipulation attack [15]. Cluster heads, which are elected to manage local clusters, become adversaries’ prime targets. If one cluster head is captured or compromised by adversaries, the entire local cluster will be affected by attacks. These compromised sensor nodes cannot trust one another to be running a given network protocol correctly. This lack of trust between sensor nodes is detrimental to the operation of the whole network. In MAC layer, they might potentially disrupt channel access and cause waste of bandwidth and energy resources. In this paper, we propose a secure MAC protocol for cluster-based UWSNs, called SC-MAC, which aims to ensure the security of data transmission against various attacks. We leverage MAC layer information by considering the link quality as well as residual energy of the modem’s battery with an objective to maximize the network lifetime. As the states of sensor nodes may not be observed accurately in a harsh underwater environment, we formulate the channel scheduling process as a stochastic partially observed Markov decision process (POMDP) multiarmed bandit problem [16] and derive the optimal channel scheduling rules hereby.The remainder of the paper is organized as follows. Section2 presents a brief overview of related work. Section 3 presents the technical details of the proposed scheme. Performance evaluation is described in Section 4. Finally, we conclude the paper in Section 5.


## 2. Related Work

ST-MAC [17] is a variant TDMA protocol that operates by constructing spatial-temporal conflict graph (ST-CG) to describe the conflict delays among transmission links. Moreover, a Mixed Integer Linear Programming (MILP) model is proposed to solve the optimal solution of coloring problem in ST-CG graph. To solve the spatiotemporal uncertainty, Slotted Spatiotemporal Conflict (S-STC) graph [18] considers both the packet propagation delay and link transmission delay in order to describe the propagation delays of the transmission links. S-STC graph is more accurate than the ST-CG [17] since the link transmission delay is not considered in ST-CG and the conflict delay is only a time value. To solve the link scheduling problem, an approximation algorithm called Interference-Aware Spatiotemporal Link Scheduling with Unified traffic load (ISTLS-U) is proposed with constant approximation ratios to the optimum solutions for both unified and weighted traffic load scenarios. TSR [13] is a joint time and spatial reuse MAC protocol that exploits the long propagation delay in UWSN channels as well as the possible sparsity of UWSN network topologies to improve channel utilization. It formalizes the problem of resource assignments to nodes to maximize the per-link channel utilization while avoiding mutual access interference within the communication range. Moreover, it works best in sparse networks.CFDMA [19] is a cognitive FDMA protocol that allocates resources based on the knowledge of a quality metric related to user-channel pairs. In order to assign channels to users in an efficient way, two heuristic methods are proposed that allow finding effective solutions for the redistribution of the channels among the users: (1) the user with largest overall capacity transfers its lowest-frequency channel to the user with smallest capacity; (2) the user with lowest overall capacity acquires the channel where it would experience the best performance among those owned by other users. SC-FDMA [20] is a single carrier frequency division multiple access protocol over underwater acoustic channels. SC-FDMA demodulates each data block separately without relying on channel dependency between adjacent blocks and performs a low complexity carrier frequency offset compensation algorithm to combat the Doppler-effect. However, due to the limited bandwidth of underwater acoustic channels and the vulnerability of limited band systems to fading and multi-path, these FDMA based protocols still suffer from low throughput and the bandwidth of the total FDMA channels is smaller than the coherence bandwidth of original transmission channel.UW-MAC [8] is a transmitter-based CDMA scheme that incorporates a closed-loop distributed algorithm to jointly sets the optimal transmit power and code length to account for the near-far effect. In UW-MAC, each data packet from each node is composed of header and payload, simultaneously accesses the channel using a random access ALOHA-like MAC scheme and adapting its power and code length in a distributed manner as in CDMA schemes (payload). Since no control packets are transmitted before the actual data packet is sent, there is no handshaking occurs during the whole channel access process. POCA-CDMA-MAC [21] is another CDMA-based MAC. By the POCA-CDMA-MAC scheme, each node modulates its packets with a spreading sequence so that the sink can receive packets from multiple neighbors at the same time. Moreover, the nodes in the same path are assigned with the same spreading sequence and they transmit their packets in a round-robin method. In this way, the collision of packets is reduced and the length of the spreading sequence codes is shortened. Compared with TDMA, CDMA is the promising medium access technique without synchronization requirement. However, due to the inherent shortcomings on near-far problem by the CDMA technique, which is a major design challenge to the MAC protocols, the development of CDMA-based MAC protocols is relatively rare.In contention-based protocols, sensor nodes contend to access the channel. T-Lohi [10] is a low energy consumption MAC protocol that employs a tone-based contention resolution mechanism to detect collisions and count contenders. If only one node sends a tone, the data period begins, and the node can transmit its data. Otherwise, reservation period is extended, and contending nodes back off and try again later. To save energy, T-Lohi keeps the modem’s data receiver and the host CPU off as much as possible and activates them only when a tone is detected by the low-power wake-up receiver.MACA-MN [22] is an asynchronous random access handshaking-based protocol that improves the channel utilization by enabling multiple packet trains to neighbors during each round of handshake. Besides adopting the widely known three-way handshake (RTS/CTS/DATA), MACA-MN also allows simultaneous transmission of a train of packets to multiple neighbors, which significantly alleviates the detrimental effect of long propagation delay on network throughput. ROPA [23] is a sender-initiated handshaking based protocol where the sender can immediately switch its role to receive the incoming appended data packets after it finishes transmitting its packets to its own receiver. This greatly reduces the relative proportion of time spent on control signaling. Further, BiC-MAC [24] enhances channel utilization of ROPA using a packet bursting idea, in which a sender-receiver node pair can exchange multiple rounds of bidirectional packet transmissions. SF-MAC [25] is a spatially fair multiple access control protocol that avoids collision by postponing the CTS packet equal to period of RTS contention period. In order to realize this purpose, the receiver collects RTSs from all the contenders during the RTS contention period and determines the earliest sender by estimating the earliest sending probability of each of the remaining contender that has sent its RTS packet earliest with the highest probability. DOTS [14] is an opportunistic transmission scheduling protocol that exploits the key insights from TDMA-based scheduling methods to enhance conventional CSMA-like random channel access with RTS/CTS. It utilizes the delay map that is built by passively observing transmissions to opportunistically schedule simultaneous transmissions for both temporal and spatial reuse. However, the building of a delay map needs nodes’ hardware support as well as the corresponding time synchronization protocols, such as Time Synchronization for High Latency (TSHL) protocol [26]. Moreover, DOTS’ ability of temporal and spatial reuse is limited to the receiver side. There is no support for a sender to open concurrent sessions to the same destination.


## 3. Proposed Scheme

### 3.1. Network Topology and Cluster Formation

We consider that an UWSN is composed of a number of sensor nodes uniformly scattered in monitoring fields and represented byG=(V,E), where V denotes the set of vertexes (nodes) and E is the set of communication links. We assume that the set of n safe nodes is represented as a set Vs and the set of m malicious nodes is represented as a set Vm, where V=Vs∪Vm. Each node only knows whether it is a safe node or a malicious node without any advanced knowledge about other nodes. All sensor nodes are assumed static or they have low mobility with respect to signal propagation speed. Every sensor node has the same transmission range and is able to communicate with other sensor nodes within its range. We also assume that each node is assigned with a triplet of coordinate (x,y,z), where each coordinate represents the hop distance of the node from one anchor. All sensor nodes have the same communication range of r, which is represented as a sphere volume of radius r in an UWSN.Definition 1.
The functionΓ defines the distance between two nodes su and sv in a 3D Euclidean space as(1)δ:V×V⟶Γ,Γ=δu,v=ux-vx2+uy-vy2+uz-vz2,where su∈V and sv∈V. Two nodes su and sv are neighbors and connected by a link if δ(u,v)<r and the link between su and sv is denoted by e(u,v). The node degree of su is the number of links incident to su, which is denoted by Du. We construct the network topology with RNG (Relative Neighborhood Graph) [27], then two nodes become neighbor nodes if and only if for any arbitrary node sp, δ(u,v)≤max⁡{δ(p,u),δ(p,v)}. For a three-dimensional Euler space embedded, if the arcuate area formed by the intersection of two sphere centered at su and sv (with radius δ(u,v)) is empty, then su and sv are adjacent nodes. RNG algorithm is simple and is easily built in a distributed way. There is no crossing edges in a RNG because at least one edge in any pair of crossing edges must be removed according to their definitions and the time complexity is O(n3). While constructing from a Delaunay Triangulation Graph structure, its complexity of lower bound is O(nlog⁡(n)) [28]. In addition, a computational method with the complexity of O(n2) for the RNG in a three-dimensional space is given in [29]. As underwater sensors float with currents, their movements are constrained in different horizontal planes and they are likely to maintain a steady position relative to each other. The construction of RNG does not require that the exact positions of nodes and their neighbors be known. For each node, only the corresponding mutual distances to its neighbors are required. Therefore, RNG is expected to be more suitable in modeling UWSN, which achieves more accurate results and behaves more consistently than other models.Given an UWSN, the whole network is composed of three types of nodes: sink nodes, cluster heads, and cluster members. Sink nodes are placed on the water surface and have unlimited energy resources to communicate with each other through radio frequency (RF) links. They communicate with cluster heads and cluster members through acoustic links. All cluster members connect to their cluster head via single hop. The cluster heads of different clusters connect to a sink node through multiple hops.Figure1 shows the topology of an UWSN after cluster formation. Each circle denotes a cluster member and each concentric circle denotes a cluster head in the UWSN. Each sensor node is assigned a unique identifier (ID) and the number besides each sensor node denotes its residual energy. Each ellipse denotes the range of a cluster and each cluster has and only has one cluster head.Figure 1
The topology of an UWSN after cluster formation.All sensor nodes make autonomous decision about cluster formation without any centralized control. Given an UWSN, all sensor nodes in the network are initially set to be candidates. Then, each candidate either builds a new cluster and becomes a cluster head or joins other cluster and becomes a cluster member. At the end, no candidate remains in the network and every cluster member belongs to a cluster. In an UWSN, whether a candidate can become a cluster head is determined by a certain standard, which is described as the gravity function in this paper. We leverage MAC layer information by considering the link quality as well as residual energy of the modem’s battery with an objective to maximize the network lifetime. Here, we use the RTS/CTS packet exchange between the sender and receiver to acquire the current estimation of Signal-to-Noise-Ratio (SNR), which is commonly used to represent the link quality.Definition 2.
Given a sensor nodesi and its neighboring node sj, the gravity function from si to sj is defined as G→ij and its value is calculated as(2)G→ij=εires·εjresδ2i,j·1+CTSjRTSj,where εires and εjres denote the residual energy of sensor nodes si and sj, δ(i,j) is the Euclidean distance from si to sj, and RTSj and CTSj denote the number of RTS packets sent from sj and the number of CTS packets received at sj. The gravity function in this paper is inspired by Newton’s universal law of gravity. The residual energy of a sensor node in formula (2) is similar to the mass of an object in Newton’s universal law of gravity. The coefficient (1+|CTSj|/|RTSj|) is used to adjust the value of G→ij according to the link quality related to sj.Algorithm1 describes the process of cluster formation in detail.Algorithm 1:Cluster Formation Algorithm.
(1)  Sink node st, si.status∈{CH, CM, CA}, Ci←Φ;
(2)  si.status  ←  CA;
(3)  st.broadcast(Hello, Nt);
(4)  if  si.receive(Hello, st) then
(5)   si.status  ←  CH;
(6)  else  si.broadcast(Hello, Ni);
(7)  endif
(8)  for all (sj∈Ni) and (sk∈Nj) do
(9)  if  ∑|Gji→|>∑|Gkj→|  then
(10)   si.status  ←  CH;
(11)   Ci.CH  ← si;
(12)   if (|Gji→|>|Gkj→|) and (si.receive(Join, sj)) then
(13)    Ci←Ci∪{sj};
(14)    sj.status  ←  CM;
(15)   endif
(16)  else  si.status  ←  CM;
(17)       si.broadcast(Join, Ni);
(18)  for all (sj,sk∈Ni) do
(19)   if (|Gij→|>|Gik→|) and (sj.status = CH) then
(20)    Cj←Cj∪{si};
(21)   endif
(22)  endfor
(23) endif
(24) endforGiven a sensor nodesi, it could be in one of the following states: cluster head (denoted by CH), cluster member (denoted by CM), and cluster head candidate (denoted by CA). Ci is the cluster that contains the sensor node si. Initially, every sensor node is set to be a cluster head candidate. Thus, si is in the CA state as described from line (1) to line (2). To begin with, the sink node st broadcasts aHello packet to its neighboring nodes Nt. If si receives theHello packet from the sink node st, its status is set to CH. Otherwise, si broadcasts aHello packet to its neighboring nodes Ni as described from line (3) to line (7). After that, si compares the sum of gravity function values from its 1-hop neighboring nodes to itself with the sum of gravity function values from its 2-hop neighboring nodes to its 1-hop neighboring nodes. If the former is bigger, the status of si is set to CH and si becomes the cluster head of Ci as described from line (8) to line (11), and then if the gravity function value from sj to si is bigger than the gravity function value from sj to its other neighboring nodes, such as sk, and si also receives aJoin packet from sj, si adds sj into the cluster Ci and changes sj’s status to be CM. Otherwise, si’s status is set to CM and si broadcasts aJoin packet to its neighboring nodes Ni as described from line (12) to line (17). At last, si compares its gravity function value to sj with its gravity function value to sk. If the former is bigger and sj is the cluster head of Cj, si chooses to join the cluster Cj and becomes a cluster member in Cj as described from line (18) to line (24).In a cluster, the cluster head will consume more energy than other sensor nodes. Therefore, it is important for each existing cluster head to determine the point at which to call for a cluster updating phase. During the process of cluster updating, all cluster members as well as the cluster head can join other cluster or reorganize a new cluster and elect a new cluster head. Figure2 shows the topology of an UWSN after cluster updating. Once the residual energy of the cluster head sf goes below a computed threshold value, the cluster updating phase is triggered.Figure 2
The topology of an UWSN after cluster updating.Algorithm2 describes the process of cluster updating in detail.Algorithm 2:Cluster Updating Algorithm.
(1)  sf.status = CH, Cf={sf,sb,se,sj,sk};
(2)  while  εfres<(∑sk∈Cfεkres)/|Cf|  do
(3)  sf.status  ←  CM;
(4)  sf.broadcast(Updating, Cf);
(5)  for all (sf∈Nf) and (sf∈Nh) do
(6)  if  ∑|Gfh→|<∑|Ghc→|  then
(7)   sh.broadcast(Join, Ch);
(8)  elseif (|Gfh→|>|Gkf→|) then
(9)   sh.status  ←  CH;
(10) Ch.CH← sh;
(11) else  sh.status  ←  CM;
(12) sh.broadcast(Join, Nh);
(13) endif
(14) endfor
(15) endwhileInitially,sf is the cluster head of cluster Cf. When the residual energy of sf drops below the average residual energy of cluster Cf, sf’s status is set to CM. After that, sf broadcasts anUpdating packet to all the cluster members in cluster Cf as described from line (1) to line (4), and then different cluster members may choose different actions according to their energy status and location: (1) joining the neighboring cluster and becomes a cluster member of that cluster; (2) building a new cluster and becomes the cluster head of this cluster; (3) joining the new cluster created by the cluster member of the origin cluster with CM status. These scenarios are described from line (5) to line (15).An attacker may participate in the process of cluster formation and updating using malicious nodes. These malicious nodes can launch different attacks. However, as each sensor node has a unique identifier, all unicast messages exchanged between nodes can be authenticated with unique pairwise keys shared with other nodes and broadcast messages can be authenticated with public key based digital signatures. By such means, the process of cluster formation and updating can be executed securely.


### 3.2. Authentication Phase

During the authentication phase, all sensor nodes need to be authenticated to each other. Cluster heads are authenticated to sink nodes and cluster members are authenticated to cluster heads. Therefore, sink nodes play an important role during the whole process of authentication. We adopt the following notations throughout the description of the protocol as shown in Notation section.Firstly, cluster heads will be authenticated to sink nodes. Supposesa is a cluster head with 1-hop distance to a sink node st. For the purpose of authentication with the sink node st, the cluster head sa generates its secret key SKa and signs its nonce NCa with SKa, which then becomes SKa(NCa). Moreover, the cluster head sa also generates a hash value Hat0=HIDa,IDt,NCa and signs Hat0 with SKa, which then becomes SIG_SKa(HIDa,IDt,NCa). Both SKa(NCa) and SIG_SKa(HIDa,IDt,NCa) are sent to the sink node st. On the other hand, the sink node st attempts to decrypt SKa(NCa) using sa’s public key PKa and get the original NCa. Furthermore, the sink node st also attempts to decrypt SIG_SKa(HIDa,IDt,NCa) using sa’s public key PKa and get the original Hat0. After that, the sink node st generates a hash value Hat1=HIDa,IDt,NCa and compares Hat1 with Hat0. If Hat1 matches Hat0, then the sink node st generates another hash value Hta0=HIDt,IDa,Nt,Na and signs Hta0 with its secret key SKt, which then becomes SIG_SKt(HIDt,IDa,NCt,NCa). In addition, the sink node st also signs its nonce NCt with SKt, which then becomes SKt(NCt). In turn, the sink node st sends SKt(NCt) and SIG_SKt(HIDt,IDa,NCt,NCa) to the cluster head sa. After receiving SKt(NCt) and SIG_SKt(HIDt,IDa,NCt,NCa), the cluster head sa decrypts them using st’s public key PKt and get the original Hta0 and NCt. Moreover, the cluster head sa generates a hash value Hta1=HIDt,IDa,NCt,NCa and compares Hta1 with Hta0. If Hta1 matches Hta0, then the authentication is successful; otherwise, the authentication is failed. Likewise, cluster members can be authenticated to cluster heads. After the execution of authentication phase, all neighboring nodes are authenticated with each other and they can communicate with each other securely.


### 3.3. Channel Scheduling Scheme

After the execution of authentication, all sensor nodes have been authenticated to each other. In cluster-based UWSNs, communication may happen between two sensor nodes that locate within the transmission radius of each other (which is called thedirect communication) or between two sensor nodes that locate out of the transmission radius of each other (which is called theindirect communication).In thedirect communication case, two sensor nodes locate within the transmission radius of each other and they can communicate with each other directly. For example, two sensor nodes sd and si want to communicate with each other as shown in Figure 2. At first, sd sends Certd to si. When si receives Certd from sd, it requests the cluster head sc to authenticate Certd instead of doing it by itself. The cluster head sc confirms whether sd has passed the authentication or not and uses SKic to encrypt E_SKic(NCi,[yes/no]), where SKic is computed by si and sc through Diffie-Hellman key exchange protocol. The nonce value NCi is used to avoid replay attack. After that, the cluster head sc sends E_SKic(NCi,[yes/no]) to si and si decrypts it in order to authenticate sd. If sd passed the authentication, si will send its certificate to sd. Otherwise, si will cancel the connection to sd. In the former case, si sends Certi to sd. sd computes SKdi and uses it to encrypt the randomly generated nonce value NCd to E_SKdi(NCd). After that, sd sends E_SKdi(NCd) to si. si authenticates in order to finish the mutual authentication and uses SKdi to decrypt E_SKdi(NCd). si uses one-way hash function to compute HNCd+1 and uses SKdi to encrypt it as E_SKdi(HNCd+1). Next, si sends E_SKdi(HNCd+1) to sd. sd uses SKdi to decrypt E_SKdi(HNCd+1) and uses one-way hash function to compute HNCd+1. At last, sd compares the receiving digest message HNCd+1 with its HNCd+1. If they are the same, the mutual authentication is successful and finished. Otherwise, sd will cancel the communication. After the successful mutual authentication, sd and si will use SKdi to protect the data in the continuous communication.In theindirect communication case, two sensor nodes locate out of the transmission radius of each other. In this case, cluster head helps them for communication. For example, a sensor node sd wants to communicate with another sensor node sh, but sh is not the 1-hop neighboring nodes of sd as shown in Figure 2. To transmit data in secure, sd uses SKdc to encrypt NCd and sends E_SKdc(NCd) and Certd+1 to the cluster head sc. After that, sc decrypts E_SKdc(NCd) with SKdc and encrypts the message to E_SKhc(NCd) using SKhc. Moreover, sc transmits E_SKhc(NCd) and Certd to sh. sh uses SKhc to decrypt the message E_SKhc(NCd) and obtains PKd from Certd to compute SKdh. After that, sh calculates HNCd+1 and encrypt it as E_SKdh(NCh,HNCd+1) with SKdh. With the help of the cluster sc, sh can send Certh and E_SKdh(NCh,HNCd+1) to sd. After receiving the messages, sd uses PKh in Certh to compute SKdh and decrypt E_SKdh(NCh,HNCd+1) using SKdh, and then sd uses one-way hash function to compute HNCd+1 and compares the receiving digest message HNCd+1 with its HNCd+1. If the two digest messages are not the same, it cancels the communication. Otherwise, sd uses SKdh to encrypt HNCh+1 as E_SKdh(HNCh+1) and responses it to sh. After receiving the messages, sh uses SKdh to decrypt E_SKdh(HNCh+1) and uses one-way hash function to compute HNCh+1. sh compares the receiving digest message with its HNCh+1. If the two digest messages are the same, the mutual authentication is successful and finished. Otherwise, sh cancels the communication. After the successful mutual authentication, sd and sh will use SKdh to protect the data in the continuous communication.Once the member nodes have requested the cluster head for the need of data packet transmission, the cluster head will schedule the channel in an optimal way based on the received requests from all member nodes as well as their channel conditions and residual energy. Since UWSNs are deployed in harsh and hostile underwater environments, their states may not be observed accurately and perfectly. Therefore, we formulate the channel scheduling process as a stochastic partially observed Markov decision process (POMDP) multiarmed bandit problem.We consider that the time axis is divided into equal time slots and each cluster member transmits data packets to the corresponding cluster head in its allocated time slots. Let the state of a sensor nodesn be xkn=(qkn,ekn) at time slot k, where n∈{1,2,…,N}, qkn denotes the link quality of sn, and ekn denotes the residual energy of sn. The link quality condition of each sensor node can be divided into H discrete levels and the residual energy of each sensor node can be divided into L discrete levels. The link quality state space Q includes all link quality state {q1,q2,…,qH} and the residual energy state space E includes all energy states {e1,e2,…,eL}. The states qkn and ekn evolve based on H-state and L-state Markov chains with state transition probability matrix Un and Yn, which are calculated as(3)Un=qijni,j∈Q,whereqijn=Pqk+1n=j∣qkn=i,Yn=eijni,j∈E,whereeijn=Pek+1n=j∣ekn=i.Ifsn is idle at time k, its state xkn=(qkn,ekn) keeps unchanged; that is, qk+1n=qkn and ek+1n=ekn. The state transition probability matrix Tn can be calculated based on Un and Yn. Let an,k denote the action for sensor node sn at time k; if sn is busy at time k+1, an,k=1; else if sn is idle, an,k=0. The action vector at time k, denoted by ak, is a binary vector of size N×1, one decision per sensor node.After action, the sensor nodesn will receive a series of observations, each observation associated with an acknowledgment (ACK) or negative acknowledgment (NAK). Let Ox={ACK,NAK}={ω1,ω2} denote the observation set, where ω1=1 and ω2=0; then, each observation okn∈Ox. The decision about which sensor node is chosen at each time slot for channel access should depend on all the actions and observations history, since the sensor nodes’ states are only partially observable. To this end, information state is developed to derive sufficient statistical information for the past history.Suppose the size of each data packet isr bits with t bits of fault-tolerance, the probability of observation NAK is(4)Pokn=NAK∣xkn,an,k=∑l=t+1rrlPexknl1-Pexknr-l,where Pe(xkn) denotes the expectation value of the Bit Error Ratio (BER) with data transmission at sensor node sn. In a POMDP system, the transition probability is affected by the feedback of last observation and the current node state. Suppose the state of sensor node sn at time slot k is xkn, the transition probability to the state xk+1n at time k+1 slot is calculated as(5)Pxkn,xk+1n,an,k=∑ωk∈Ox∑dkPdkPxqkn,qk+1nPωk∣xkn,an,k×ψek+1n-min⁡⁡ψekn+dk,r,where Px(qkn,qk+1n) denotes the transition probability of link quality, dk is the buffer size at sn, ψ(ekn) and ψ(ek+1n) denote the number of data packets received at time slot k and k+1 of the corresponding residual energy states.Moreover, link quality-related and energy-related costs are considered in our scheme. Letcq(qkn,an,k) denote the link quality-related cost of sensor node sn at time slot k and ce(ekn,an,k) denote the corresponding energy-related cost of sensor node sn at time slot k; then, the instantaneous cost c(xkn,an,k) is calculated as(6)cxkn,an,k=1-λcqqkn,an,k+λ·ceekn,an,k,where 0<λ<1 is the weight factor for these two kinds of costs.In order to design the optimal channel scheduling algorithm, we need to specify a criterion for optimality. For each transmission outcome we need to specify a reward. Since the optimal channel selection maximizes the rewards, they should be defined in a way to capture the desirable performance. LetRn(k) denote the reward generated by sensor node sn at time k; then, (7)Rxkn=Rnk,ifan,k=1;0,ifan,k=0.A channel scheduling policy is one in the form ofπ={π1,π2,…} and consists of some decision making rules that in any time slot k sets a value according to(8)ak=πkxk1,…,xkn,ak-1.The goal is to represent an optimal scheduling policy in order to maximize the obtained reward, which is formulated as(9)Jπ=E∑k=0∞βk∑n=1NRxkn,an,k∣x0n,where βk (0≤βk≤1) is called the discount factor, which is used to give importance to the obtained rewards in early phase. Applying Bellman’s equation [30] which shows the relationship between the value of the state x0n and the immediate occurred state, the expected discount reward is calculated as(10)wnxn=max⁡k>0⁡E∑k=0τ-1βkRxkn∣x0nE∑k=0τ-1βk∣x0n,where wn(xn) is the maximum expected discounted reward per unit of expected discounted time. The maximization is taken over the set of all possible stopping times τ. It represents the maximum possible expected reward rate starting from each state, which is also called theGittins index[31]. The optimal policy at time k is that the sensor node with the largest rewardGittins index at that time should be selected when the reward is the optimization objective, which significantly decreases the computational complexity. In order to calculate theGittins index for each sensor node, we adopt the value iteration algorithm proposed in [16], which works efficiently for sparse networks with limited states and observation states, such as UWSNs. According to the result of this action, the state of sensor node sn reflects the most recent information about its link quality and residual energy. Moreover, its success or idle probabilities will also be updated in a Markovian fashion while the states of other sensor nodes remain unchanged. After each round of data transmission attempt, theGittins indices of sensor nodes within the same cluster will be recalculated according to the results experienced so far, and the sensor node with the highestGittins index will be selected in the next transmission attempt.


### 3.4. Security Analysis

In this section, we discuss how different attacks are prevented by the proposed protocol. We assume that sink nodes cannot be captured by an attacker as they are physically protected.In Sybil attack, an attacker tries to create multiple fabricated identities. In our protocol, all sensor nodes along the communication path are authenticated using Elliptic Curve Cryptography (ECC) public-key algorithm, which is feasible for low-end underwater sensors [32]. The sender signs the hash of a message with its secret key and broadcasts the signature along with the message. The receivers verify the correctness of the signature by using the sender’s public key. As a result, an attacker cannot disguise as a legitimate node and cannot exchange any false information between legitimate nodes.Replay attack is prevented by using a random nonce, which is updated every time the message is broadcasted. Thus, an attacker cannot pass the authentication phase even if a malicious node makes a copy of the previous message.In order to perform message manipulation attack, an intruder tries to drop, modify, or even forge the exchanged messages to interrupt the process of communication. In the proposed protocol, all unicast messages exchanged between nodes can be authenticated with unique pair-wise keys shared with other nodes and broadcast messages can be authenticated with public key based digital signatures. Thus, message manipulation attack is not effective with this protocol.


## 3.1. Network Topology and Cluster Formation

We consider that an UWSN is composed of a number of sensor nodes uniformly scattered in monitoring fields and represented byG=(V,E), where V denotes the set of vertexes (nodes) and E is the set of communication links. We assume that the set of n safe nodes is represented as a set Vs and the set of m malicious nodes is represented as a set Vm, where V=Vs∪Vm. Each node only knows whether it is a safe node or a malicious node without any advanced knowledge about other nodes. All sensor nodes are assumed static or they have low mobility with respect to signal propagation speed. Every sensor node has the same transmission range and is able to communicate with other sensor nodes within its range. We also assume that each node is assigned with a triplet of coordinate (x,y,z), where each coordinate represents the hop distance of the node from one anchor. All sensor nodes have the same communication range of r, which is represented as a sphere volume of radius r in an UWSN.Definition 1.
The functionΓ defines the distance between two nodes su and sv in a 3D Euclidean space as(1)δ:V×V⟶Γ,Γ=δu,v=ux-vx2+uy-vy2+uz-vz2,where su∈V and sv∈V. Two nodes su and sv are neighbors and connected by a link if δ(u,v)<r and the link between su and sv is denoted by e(u,v). The node degree of su is the number of links incident to su, which is denoted by Du. We construct the network topology with RNG (Relative Neighborhood Graph) [27], then two nodes become neighbor nodes if and only if for any arbitrary node sp, δ(u,v)≤max⁡{δ(p,u),δ(p,v)}. For a three-dimensional Euler space embedded, if the arcuate area formed by the intersection of two sphere centered at su and sv (with radius δ(u,v)) is empty, then su and sv are adjacent nodes. RNG algorithm is simple and is easily built in a distributed way. There is no crossing edges in a RNG because at least one edge in any pair of crossing edges must be removed according to their definitions and the time complexity is O(n3). While constructing from a Delaunay Triangulation Graph structure, its complexity of lower bound is O(nlog⁡(n)) [28]. In addition, a computational method with the complexity of O(n2) for the RNG in a three-dimensional space is given in [29]. As underwater sensors float with currents, their movements are constrained in different horizontal planes and they are likely to maintain a steady position relative to each other. The construction of RNG does not require that the exact positions of nodes and their neighbors be known. For each node, only the corresponding mutual distances to its neighbors are required. Therefore, RNG is expected to be more suitable in modeling UWSN, which achieves more accurate results and behaves more consistently than other models.Given an UWSN, the whole network is composed of three types of nodes: sink nodes, cluster heads, and cluster members. Sink nodes are placed on the water surface and have unlimited energy resources to communicate with each other through radio frequency (RF) links. They communicate with cluster heads and cluster members through acoustic links. All cluster members connect to their cluster head via single hop. The cluster heads of different clusters connect to a sink node through multiple hops.Figure1 shows the topology of an UWSN after cluster formation. Each circle denotes a cluster member and each concentric circle denotes a cluster head in the UWSN. Each sensor node is assigned a unique identifier (ID) and the number besides each sensor node denotes its residual energy. Each ellipse denotes the range of a cluster and each cluster has and only has one cluster head.Figure 1
The topology of an UWSN after cluster formation.All sensor nodes make autonomous decision about cluster formation without any centralized control. Given an UWSN, all sensor nodes in the network are initially set to be candidates. Then, each candidate either builds a new cluster and becomes a cluster head or joins other cluster and becomes a cluster member. At the end, no candidate remains in the network and every cluster member belongs to a cluster. In an UWSN, whether a candidate can become a cluster head is determined by a certain standard, which is described as the gravity function in this paper. We leverage MAC layer information by considering the link quality as well as residual energy of the modem’s battery with an objective to maximize the network lifetime. Here, we use the RTS/CTS packet exchange between the sender and receiver to acquire the current estimation of Signal-to-Noise-Ratio (SNR), which is commonly used to represent the link quality.Definition 2.
Given a sensor nodesi and its neighboring node sj, the gravity function from si to sj is defined as G→ij and its value is calculated as(2)G→ij=εires·εjresδ2i,j·1+CTSjRTSj,where εires and εjres denote the residual energy of sensor nodes si and sj, δ(i,j) is the Euclidean distance from si to sj, and RTSj and CTSj denote the number of RTS packets sent from sj and the number of CTS packets received at sj. The gravity function in this paper is inspired by Newton’s universal law of gravity. The residual energy of a sensor node in formula (2) is similar to the mass of an object in Newton’s universal law of gravity. The coefficient (1+|CTSj|/|RTSj|) is used to adjust the value of G→ij according to the link quality related to sj.Algorithm1 describes the process of cluster formation in detail.Algorithm 1:Cluster Formation Algorithm.
(1)  Sink node st, si.status∈{CH, CM, CA}, Ci←Φ;
(2)  si.status  ←  CA;
(3)  st.broadcast(Hello, Nt);
(4)  if  si.receive(Hello, st) then
(5)   si.status  ←  CH;
(6)  else  si.broadcast(Hello, Ni);
(7)  endif
(8)  for all (sj∈Ni) and (sk∈Nj) do
(9)  if  ∑|Gji→|>∑|Gkj→|  then
(10)   si.status  ←  CH;
(11)   Ci.CH  ← si;
(12)   if (|Gji→|>|Gkj→|) and (si.receive(Join, sj)) then
(13)    Ci←Ci∪{sj};
(14)    sj.status  ←  CM;
(15)   endif
(16)  else  si.status  ←  CM;
(17)       si.broadcast(Join, Ni);
(18)  for all (sj,sk∈Ni) do
(19)   if (|Gij→|>|Gik→|) and (sj.status = CH) then
(20)    Cj←Cj∪{si};
(21)   endif
(22)  endfor
(23) endif
(24) endforGiven a sensor nodesi, it could be in one of the following states: cluster head (denoted by CH), cluster member (denoted by CM), and cluster head candidate (denoted by CA). Ci is the cluster that contains the sensor node si. Initially, every sensor node is set to be a cluster head candidate. Thus, si is in the CA state as described from line (1) to line (2). To begin with, the sink node st broadcasts aHello packet to its neighboring nodes Nt. If si receives theHello packet from the sink node st, its status is set to CH. Otherwise, si broadcasts aHello packet to its neighboring nodes Ni as described from line (3) to line (7). After that, si compares the sum of gravity function values from its 1-hop neighboring nodes to itself with the sum of gravity function values from its 2-hop neighboring nodes to its 1-hop neighboring nodes. If the former is bigger, the status of si is set to CH and si becomes the cluster head of Ci as described from line (8) to line (11), and then if the gravity function value from sj to si is bigger than the gravity function value from sj to its other neighboring nodes, such as sk, and si also receives aJoin packet from sj, si adds sj into the cluster Ci and changes sj’s status to be CM. Otherwise, si’s status is set to CM and si broadcasts aJoin packet to its neighboring nodes Ni as described from line (12) to line (17). At last, si compares its gravity function value to sj with its gravity function value to sk. If the former is bigger and sj is the cluster head of Cj, si chooses to join the cluster Cj and becomes a cluster member in Cj as described from line (18) to line (24).In a cluster, the cluster head will consume more energy than other sensor nodes. Therefore, it is important for each existing cluster head to determine the point at which to call for a cluster updating phase. During the process of cluster updating, all cluster members as well as the cluster head can join other cluster or reorganize a new cluster and elect a new cluster head. Figure2 shows the topology of an UWSN after cluster updating. Once the residual energy of the cluster head sf goes below a computed threshold value, the cluster updating phase is triggered.Figure 2
The topology of an UWSN after cluster updating.Algorithm2 describes the process of cluster updating in detail.Algorithm 2:Cluster Updating Algorithm.
(1)  sf.status = CH, Cf={sf,sb,se,sj,sk};
(2)  while  εfres<(∑sk∈Cfεkres)/|Cf|  do
(3)  sf.status  ←  CM;
(4)  sf.broadcast(Updating, Cf);
(5)  for all (sf∈Nf) and (sf∈Nh) do
(6)  if  ∑|Gfh→|<∑|Ghc→|  then
(7)   sh.broadcast(Join, Ch);
(8)  elseif (|Gfh→|>|Gkf→|) then
(9)   sh.status  ←  CH;
(10) Ch.CH← sh;
(11) else  sh.status  ←  CM;
(12) sh.broadcast(Join, Nh);
(13) endif
(14) endfor
(15) endwhileInitially,sf is the cluster head of cluster Cf. When the residual energy of sf drops below the average residual energy of cluster Cf, sf’s status is set to CM. After that, sf broadcasts anUpdating packet to all the cluster members in cluster Cf as described from line (1) to line (4), and then different cluster members may choose different actions according to their energy status and location: (1) joining the neighboring cluster and becomes a cluster member of that cluster; (2) building a new cluster and becomes the cluster head of this cluster; (3) joining the new cluster created by the cluster member of the origin cluster with CM status. These scenarios are described from line (5) to line (15).An attacker may participate in the process of cluster formation and updating using malicious nodes. These malicious nodes can launch different attacks. However, as each sensor node has a unique identifier, all unicast messages exchanged between nodes can be authenticated with unique pairwise keys shared with other nodes and broadcast messages can be authenticated with public key based digital signatures. By such means, the process of cluster formation and updating can be executed securely.


## 3.2. Authentication Phase

During the authentication phase, all sensor nodes need to be authenticated to each other. Cluster heads are authenticated to sink nodes and cluster members are authenticated to cluster heads. Therefore, sink nodes play an important role during the whole process of authentication. We adopt the following notations throughout the description of the protocol as shown in Notation section.Firstly, cluster heads will be authenticated to sink nodes. Supposesa is a cluster head with 1-hop distance to a sink node st. For the purpose of authentication with the sink node st, the cluster head sa generates its secret key SKa and signs its nonce NCa with SKa, which then becomes SKa(NCa). Moreover, the cluster head sa also generates a hash value Hat0=HIDa,IDt,NCa and signs Hat0 with SKa, which then becomes SIG_SKa(HIDa,IDt,NCa). Both SKa(NCa) and SIG_SKa(HIDa,IDt,NCa) are sent to the sink node st. On the other hand, the sink node st attempts to decrypt SKa(NCa) using sa’s public key PKa and get the original NCa. Furthermore, the sink node st also attempts to decrypt SIG_SKa(HIDa,IDt,NCa) using sa’s public key PKa and get the original Hat0. After that, the sink node st generates a hash value Hat1=HIDa,IDt,NCa and compares Hat1 with Hat0. If Hat1 matches Hat0, then the sink node st generates another hash value Hta0=HIDt,IDa,Nt,Na and signs Hta0 with its secret key SKt, which then becomes SIG_SKt(HIDt,IDa,NCt,NCa). In addition, the sink node st also signs its nonce NCt with SKt, which then becomes SKt(NCt). In turn, the sink node st sends SKt(NCt) and SIG_SKt(HIDt,IDa,NCt,NCa) to the cluster head sa. After receiving SKt(NCt) and SIG_SKt(HIDt,IDa,NCt,NCa), the cluster head sa decrypts them using st’s public key PKt and get the original Hta0 and NCt. Moreover, the cluster head sa generates a hash value Hta1=HIDt,IDa,NCt,NCa and compares Hta1 with Hta0. If Hta1 matches Hta0, then the authentication is successful; otherwise, the authentication is failed. Likewise, cluster members can be authenticated to cluster heads. After the execution of authentication phase, all neighboring nodes are authenticated with each other and they can communicate with each other securely.


## 3.3. Channel Scheduling Scheme

After the execution of authentication, all sensor nodes have been authenticated to each other. In cluster-based UWSNs, communication may happen between two sensor nodes that locate within the transmission radius of each other (which is called thedirect communication) or between two sensor nodes that locate out of the transmission radius of each other (which is called theindirect communication).In thedirect communication case, two sensor nodes locate within the transmission radius of each other and they can communicate with each other directly. For example, two sensor nodes sd and si want to communicate with each other as shown in Figure 2. At first, sd sends Certd to si. When si receives Certd from sd, it requests the cluster head sc to authenticate Certd instead of doing it by itself. The cluster head sc confirms whether sd has passed the authentication or not and uses SKic to encrypt E_SKic(NCi,[yes/no]), where SKic is computed by si and sc through Diffie-Hellman key exchange protocol. The nonce value NCi is used to avoid replay attack. After that, the cluster head sc sends E_SKic(NCi,[yes/no]) to si and si decrypts it in order to authenticate sd. If sd passed the authentication, si will send its certificate to sd. Otherwise, si will cancel the connection to sd. In the former case, si sends Certi to sd. sd computes SKdi and uses it to encrypt the randomly generated nonce value NCd to E_SKdi(NCd). After that, sd sends E_SKdi(NCd) to si. si authenticates in order to finish the mutual authentication and uses SKdi to decrypt E_SKdi(NCd). si uses one-way hash function to compute HNCd+1 and uses SKdi to encrypt it as E_SKdi(HNCd+1). Next, si sends E_SKdi(HNCd+1) to sd. sd uses SKdi to decrypt E_SKdi(HNCd+1) and uses one-way hash function to compute HNCd+1. At last, sd compares the receiving digest message HNCd+1 with its HNCd+1. If they are the same, the mutual authentication is successful and finished. Otherwise, sd will cancel the communication. After the successful mutual authentication, sd and si will use SKdi to protect the data in the continuous communication.In theindirect communication case, two sensor nodes locate out of the transmission radius of each other. In this case, cluster head helps them for communication. For example, a sensor node sd wants to communicate with another sensor node sh, but sh is not the 1-hop neighboring nodes of sd as shown in Figure 2. To transmit data in secure, sd uses SKdc to encrypt NCd and sends E_SKdc(NCd) and Certd+1 to the cluster head sc. After that, sc decrypts E_SKdc(NCd) with SKdc and encrypts the message to E_SKhc(NCd) using SKhc. Moreover, sc transmits E_SKhc(NCd) and Certd to sh. sh uses SKhc to decrypt the message E_SKhc(NCd) and obtains PKd from Certd to compute SKdh. After that, sh calculates HNCd+1 and encrypt it as E_SKdh(NCh,HNCd+1) with SKdh. With the help of the cluster sc, sh can send Certh and E_SKdh(NCh,HNCd+1) to sd. After receiving the messages, sd uses PKh in Certh to compute SKdh and decrypt E_SKdh(NCh,HNCd+1) using SKdh, and then sd uses one-way hash function to compute HNCd+1 and compares the receiving digest message HNCd+1 with its HNCd+1. If the two digest messages are not the same, it cancels the communication. Otherwise, sd uses SKdh to encrypt HNCh+1 as E_SKdh(HNCh+1) and responses it to sh. After receiving the messages, sh uses SKdh to decrypt E_SKdh(HNCh+1) and uses one-way hash function to compute HNCh+1. sh compares the receiving digest message with its HNCh+1. If the two digest messages are the same, the mutual authentication is successful and finished. Otherwise, sh cancels the communication. After the successful mutual authentication, sd and sh will use SKdh to protect the data in the continuous communication.Once the member nodes have requested the cluster head for the need of data packet transmission, the cluster head will schedule the channel in an optimal way based on the received requests from all member nodes as well as their channel conditions and residual energy. Since UWSNs are deployed in harsh and hostile underwater environments, their states may not be observed accurately and perfectly. Therefore, we formulate the channel scheduling process as a stochastic partially observed Markov decision process (POMDP) multiarmed bandit problem.We consider that the time axis is divided into equal time slots and each cluster member transmits data packets to the corresponding cluster head in its allocated time slots. Let the state of a sensor nodesn be xkn=(qkn,ekn) at time slot k, where n∈{1,2,…,N}, qkn denotes the link quality of sn, and ekn denotes the residual energy of sn. The link quality condition of each sensor node can be divided into H discrete levels and the residual energy of each sensor node can be divided into L discrete levels. The link quality state space Q includes all link quality state {q1,q2,…,qH} and the residual energy state space E includes all energy states {e1,e2,…,eL}. The states qkn and ekn evolve based on H-state and L-state Markov chains with state transition probability matrix Un and Yn, which are calculated as(3)Un=qijni,j∈Q,whereqijn=Pqk+1n=j∣qkn=i,Yn=eijni,j∈E,whereeijn=Pek+1n=j∣ekn=i.Ifsn is idle at time k, its state xkn=(qkn,ekn) keeps unchanged; that is, qk+1n=qkn and ek+1n=ekn. The state transition probability matrix Tn can be calculated based on Un and Yn. Let an,k denote the action for sensor node sn at time k; if sn is busy at time k+1, an,k=1; else if sn is idle, an,k=0. The action vector at time k, denoted by ak, is a binary vector of size N×1, one decision per sensor node.After action, the sensor nodesn will receive a series of observations, each observation associated with an acknowledgment (ACK) or negative acknowledgment (NAK). Let Ox={ACK,NAK}={ω1,ω2} denote the observation set, where ω1=1 and ω2=0; then, each observation okn∈Ox. The decision about which sensor node is chosen at each time slot for channel access should depend on all the actions and observations history, since the sensor nodes’ states are only partially observable. To this end, information state is developed to derive sufficient statistical information for the past history.Suppose the size of each data packet isr bits with t bits of fault-tolerance, the probability of observation NAK is(4)Pokn=NAK∣xkn,an,k=∑l=t+1rrlPexknl1-Pexknr-l,where Pe(xkn) denotes the expectation value of the Bit Error Ratio (BER) with data transmission at sensor node sn. In a POMDP system, the transition probability is affected by the feedback of last observation and the current node state. Suppose the state of sensor node sn at time slot k is xkn, the transition probability to the state xk+1n at time k+1 slot is calculated as(5)Pxkn,xk+1n,an,k=∑ωk∈Ox∑dkPdkPxqkn,qk+1nPωk∣xkn,an,k×ψek+1n-min⁡⁡ψekn+dk,r,where Px(qkn,qk+1n) denotes the transition probability of link quality, dk is the buffer size at sn, ψ(ekn) and ψ(ek+1n) denote the number of data packets received at time slot k and k+1 of the corresponding residual energy states.Moreover, link quality-related and energy-related costs are considered in our scheme. Letcq(qkn,an,k) denote the link quality-related cost of sensor node sn at time slot k and ce(ekn,an,k) denote the corresponding energy-related cost of sensor node sn at time slot k; then, the instantaneous cost c(xkn,an,k) is calculated as(6)cxkn,an,k=1-λcqqkn,an,k+λ·ceekn,an,k,where 0<λ<1 is the weight factor for these two kinds of costs.In order to design the optimal channel scheduling algorithm, we need to specify a criterion for optimality. For each transmission outcome we need to specify a reward. Since the optimal channel selection maximizes the rewards, they should be defined in a way to capture the desirable performance. LetRn(k) denote the reward generated by sensor node sn at time k; then, (7)Rxkn=Rnk,ifan,k=1;0,ifan,k=0.A channel scheduling policy is one in the form ofπ={π1,π2,…} and consists of some decision making rules that in any time slot k sets a value according to(8)ak=πkxk1,…,xkn,ak-1.The goal is to represent an optimal scheduling policy in order to maximize the obtained reward, which is formulated as(9)Jπ=E∑k=0∞βk∑n=1NRxkn,an,k∣x0n,where βk (0≤βk≤1) is called the discount factor, which is used to give importance to the obtained rewards in early phase. Applying Bellman’s equation [30] which shows the relationship between the value of the state x0n and the immediate occurred state, the expected discount reward is calculated as(10)wnxn=max⁡k>0⁡E∑k=0τ-1βkRxkn∣x0nE∑k=0τ-1βk∣x0n,where wn(xn) is the maximum expected discounted reward per unit of expected discounted time. The maximization is taken over the set of all possible stopping times τ. It represents the maximum possible expected reward rate starting from each state, which is also called theGittins index[31]. The optimal policy at time k is that the sensor node with the largest rewardGittins index at that time should be selected when the reward is the optimization objective, which significantly decreases the computational complexity. In order to calculate theGittins index for each sensor node, we adopt the value iteration algorithm proposed in [16], which works efficiently for sparse networks with limited states and observation states, such as UWSNs. According to the result of this action, the state of sensor node sn reflects the most recent information about its link quality and residual energy. Moreover, its success or idle probabilities will also be updated in a Markovian fashion while the states of other sensor nodes remain unchanged. After each round of data transmission attempt, theGittins indices of sensor nodes within the same cluster will be recalculated according to the results experienced so far, and the sensor node with the highestGittins index will be selected in the next transmission attempt.


## 3.4. Security Analysis

In this section, we discuss how different attacks are prevented by the proposed protocol. We assume that sink nodes cannot be captured by an attacker as they are physically protected.In Sybil attack, an attacker tries to create multiple fabricated identities. In our protocol, all sensor nodes along the communication path are authenticated using Elliptic Curve Cryptography (ECC) public-key algorithm, which is feasible for low-end underwater sensors [32]. The sender signs the hash of a message with its secret key and broadcasts the signature along with the message. The receivers verify the correctness of the signature by using the sender’s public key. As a result, an attacker cannot disguise as a legitimate node and cannot exchange any false information between legitimate nodes.Replay attack is prevented by using a random nonce, which is updated every time the message is broadcasted. Thus, an attacker cannot pass the authentication phase even if a malicious node makes a copy of the previous message.In order to perform message manipulation attack, an intruder tries to drop, modify, or even forge the exchanged messages to interrupt the process of communication. In the proposed protocol, all unicast messages exchanged between nodes can be authenticated with unique pair-wise keys shared with other nodes and broadcast messages can be authenticated with public key based digital signatures. Thus, message manipulation attack is not effective with this protocol.


## 4. Performance Evaluation

### 4.1. Simulation Settings

We use Aqua-Sim [33] as simulation framework to evaluate our approach. The data packets are also generated by the simulator. Aqua-Sim is an ns-2 based underwater sensor network simulator developed by underwater sensor network lab at University of Connecticut. To simulate acoustic channels, we extend Aqua-Sim with spherical path loss and Thorp attenuation [34].Simulation parameters and their default values are listed in Table1.Table 1
Simulation parameters and their default values.
Simulation parameters
Default values
Number of sink nodes
8
Number of sensor nodes
50
Ratio of malicious nodes
10%
The size of region
2 km × 2 km × 2 km
Acoustic speed
1500 m/s
Packet generation rate
0.10 pkts/s
The size of data packet
256 bytes
The size of control packet
16 bytes
Transmitting power
1.78 W
Receiving power
0.20 W
Idle listening power
16.8 mWWe compared the performance of SC-MAC protocol with that of SF-MAC [25] and T-Lohi [10] protocols. We use three metrics to evaluate the performance of different MAC protocols, namely, network throughput, successful delivery ratio and energy consumption. The results are obtained by averaging 100 runs from 500 seconds simulation of each protocol. Network throughput refers to the total amount of data successfully transmitted by the network within a given period of time. Successful delivery ratio is defined as the ratio of successfully received number of data packets to the total amount of generated data packets. Energy consumption is obtained by dividing the overall energy consumption in the network by the successfully transmitted data bytes, which is measured in millijoule per byte.


### 4.2. Simulation Results

In the first set of simulations, we compare the network throughput with the number of nodes in different MAC protocols. The ratio of malicious nodes is set to 0.10. As shown in Figure3, the network throughput of the three protocols is proportional to the number of nodes. As the number of nodes increases, the network throughput increases correspondingly and finally reaches the saturation status. SC-MAC achieves higher network throughput than that of SF-MAC and T-Lohi when their number of nodes are the same. This is because SC-MAC takes the link quality into consideration in channel scheduling. In T-Lohi, they do not consider the hidden terminal problem, and therefore the network throughput is lower than that of SC-MAC and SF-MAC. Specifically, SC-MAC improves 23.8% of the network throughput than that of SF-MAC and 34.8% of the network throughput than that of T-Lohi on average.Figure 3
Network throughput versus number of nodes.Next, we study how the ratio of malicious nodes affects the performance. This time, the number of nodes is set to 50 and the ratio of malicious nodes increases from 0.02 to 0.20. As shown in Figure4, the network throughput of the three protocols decreases linearly with the ratio of malicious nodes. SC-MAC performs better than other MAC protocols in the same circumstances. Moreover, the curve of SC-MAC exhibits a slower decline compared with that of SF-MAC and T-Lohi, which proves the effectiveness of the proposed protocol. On the other side, although SC-MAC can protect the system from the intrusion of malicious nodes, these malicious nodes would never participate in the work of data transmission, which in turn decreases the network throughput to some extent. On average, SC-MAC increases 27.8% of the network throughput than that of SF-MAC and 40.6% of the network throughput than that of T-Lohi.Figure 4
Network throughput versus ratio of malicious nodes.In the second set of simulations, we compare the successful delivery ratio with the number of nodes in different MAC protocols. The ratio of malicious nodes is set to 0.10. As shown in Figure5, the successful delivery ratio of the three protocols is inversely proportional to the number of nodes. SC-MAC achieves higher successful delivery ratio than that of SF-MAC and T-Lohi when their number of nodes are the same. The reason is that, in T-Lohi scheme, the senders may always contend with each other and the order of RTS changes in each contention period. In SC-MAC, each cluster head starts the cluster updating process when its residual energy drops below the average residual energy of the cluster, which in turn reduces the competitive intension. SF-MAC protocol avoids data collision by postponing the CTS packets. When the number of nodes keeps in a low level, this mechanism works well; but when the number of nodes reaches a high level, the postponed CTS packets still have potentially high risk of collision. Specifically, the successful delivery ratio of SC-MAC is 12.5% higher than that of SF-MAC and 27.4% higher than that of T-Lohi on average.Figure 5
Successful delivery ratio versus number of nodes.Then, we investigate the effect of varying ratio of malicious nodes to the successful delivery ratio while the number of nodes is kept fixed to 50. As shown in Figure6, the successful delivery ratio of the three protocols decreases linearly with the ratio of malicious nodes. This is because with the increase of malicious nodes, they not only refuse of make contribution to the data transmission, but also interfere in matters of other safe sensor nodes. SC-MAC performs better than other two protocols with the protection of its additionally secure measures. On average, the successful delivery ratio of SC-MAC is 15.3% higher than that of SF-MAC and 32.6% higher than that of T-Lohi.Figure 6
Successful delivery ratio versus ratio of malicious nodes.In the third set of simulations, we compare the energy consumption with the number of nodes in different MAC protocols. The ratio of malicious nodes is set to 0.10. As shown in Figure7, the energy consumption of the three protocols is inversely proportional to the number of nodes. The reason is that with the increase of the node density, the distance between different nodes decreases and less energy is wasted on long distance communications. SF-MAC consumes the highest energy among the three protocols in that it does not adopt any energy conservation measures. T-Lohi conserves energy by employing a wake-up tone receiver that allows very low-power listening for wake-up tones. Specifically, SC-MAC decreases 50.3% of the energy consumption than that of SF-MAC and 23.2% of the energy consumption than that of T-Lohi on average.Figure 7
Energy consumption versus number of nodes.Further, we investigate the effect of varying ratio of malicious nodes while the number of nodes is kept fixed to 50. As shown in Figure8, the energy consumption of the three protocols is proportional to the ratio of malicious nodes. This is because with the increase of the malicious nodes, more energy will be wasted on unsuccessful data transmission and idle listening activities. Compared with other two protocols, SC-MAC achieves much high energy efficiency under the same conditions. On average, SC-MAC decreases 54.5% of the energy consumption than that of SF-MAC and 29.8% of the energy consumption than that of T-Lohi.Figure 8
Energy consumption versus number of nodes.


## 4.1. Simulation Settings

We use Aqua-Sim [33] as simulation framework to evaluate our approach. The data packets are also generated by the simulator. Aqua-Sim is an ns-2 based underwater sensor network simulator developed by underwater sensor network lab at University of Connecticut. To simulate acoustic channels, we extend Aqua-Sim with spherical path loss and Thorp attenuation [34].Simulation parameters and their default values are listed in Table1.Table 1
Simulation parameters and their default values.
Simulation parameters
Default values
Number of sink nodes
8
Number of sensor nodes
50
Ratio of malicious nodes
10%
The size of region
2 km × 2 km × 2 km
Acoustic speed
1500 m/s
Packet generation rate
0.10 pkts/s
The size of data packet
256 bytes
The size of control packet
16 bytes
Transmitting power
1.78 W
Receiving power
0.20 W
Idle listening power
16.8 mWWe compared the performance of SC-MAC protocol with that of SF-MAC [25] and T-Lohi [10] protocols. We use three metrics to evaluate the performance of different MAC protocols, namely, network throughput, successful delivery ratio and energy consumption. The results are obtained by averaging 100 runs from 500 seconds simulation of each protocol. Network throughput refers to the total amount of data successfully transmitted by the network within a given period of time. Successful delivery ratio is defined as the ratio of successfully received number of data packets to the total amount of generated data packets. Energy consumption is obtained by dividing the overall energy consumption in the network by the successfully transmitted data bytes, which is measured in millijoule per byte.


## 4.2. Simulation Results

In the first set of simulations, we compare the network throughput with the number of nodes in different MAC protocols. The ratio of malicious nodes is set to 0.10. As shown in Figure3, the network throughput of the three protocols is proportional to the number of nodes. As the number of nodes increases, the network throughput increases correspondingly and finally reaches the saturation status. SC-MAC achieves higher network throughput than that of SF-MAC and T-Lohi when their number of nodes are the same. This is because SC-MAC takes the link quality into consideration in channel scheduling. In T-Lohi, they do not consider the hidden terminal problem, and therefore the network throughput is lower than that of SC-MAC and SF-MAC. Specifically, SC-MAC improves 23.8% of the network throughput than that of SF-MAC and 34.8% of the network throughput than that of T-Lohi on average.Figure 3
Network throughput versus number of nodes.Next, we study how the ratio of malicious nodes affects the performance. This time, the number of nodes is set to 50 and the ratio of malicious nodes increases from 0.02 to 0.20. As shown in Figure4, the network throughput of the three protocols decreases linearly with the ratio of malicious nodes. SC-MAC performs better than other MAC protocols in the same circumstances. Moreover, the curve of SC-MAC exhibits a slower decline compared with that of SF-MAC and T-Lohi, which proves the effectiveness of the proposed protocol. On the other side, although SC-MAC can protect the system from the intrusion of malicious nodes, these malicious nodes would never participate in the work of data transmission, which in turn decreases the network throughput to some extent. On average, SC-MAC increases 27.8% of the network throughput than that of SF-MAC and 40.6% of the network throughput than that of T-Lohi.Figure 4
Network throughput versus ratio of malicious nodes.In the second set of simulations, we compare the successful delivery ratio with the number of nodes in different MAC protocols. The ratio of malicious nodes is set to 0.10. As shown in Figure5, the successful delivery ratio of the three protocols is inversely proportional to the number of nodes. SC-MAC achieves higher successful delivery ratio than that of SF-MAC and T-Lohi when their number of nodes are the same. The reason is that, in T-Lohi scheme, the senders may always contend with each other and the order of RTS changes in each contention period. In SC-MAC, each cluster head starts the cluster updating process when its residual energy drops below the average residual energy of the cluster, which in turn reduces the competitive intension. SF-MAC protocol avoids data collision by postponing the CTS packets. When the number of nodes keeps in a low level, this mechanism works well; but when the number of nodes reaches a high level, the postponed CTS packets still have potentially high risk of collision. Specifically, the successful delivery ratio of SC-MAC is 12.5% higher than that of SF-MAC and 27.4% higher than that of T-Lohi on average.Figure 5
Successful delivery ratio versus number of nodes.Then, we investigate the effect of varying ratio of malicious nodes to the successful delivery ratio while the number of nodes is kept fixed to 50. As shown in Figure6, the successful delivery ratio of the three protocols decreases linearly with the ratio of malicious nodes. This is because with the increase of malicious nodes, they not only refuse of make contribution to the data transmission, but also interfere in matters of other safe sensor nodes. SC-MAC performs better than other two protocols with the protection of its additionally secure measures. On average, the successful delivery ratio of SC-MAC is 15.3% higher than that of SF-MAC and 32.6% higher than that of T-Lohi.Figure 6
Successful delivery ratio versus ratio of malicious nodes.In the third set of simulations, we compare the energy consumption with the number of nodes in different MAC protocols. The ratio of malicious nodes is set to 0.10. As shown in Figure7, the energy consumption of the three protocols is inversely proportional to the number of nodes. The reason is that with the increase of the node density, the distance between different nodes decreases and less energy is wasted on long distance communications. SF-MAC consumes the highest energy among the three protocols in that it does not adopt any energy conservation measures. T-Lohi conserves energy by employing a wake-up tone receiver that allows very low-power listening for wake-up tones. Specifically, SC-MAC decreases 50.3% of the energy consumption than that of SF-MAC and 23.2% of the energy consumption than that of T-Lohi on average.Figure 7
Energy consumption versus number of nodes.Further, we investigate the effect of varying ratio of malicious nodes while the number of nodes is kept fixed to 50. As shown in Figure8, the energy consumption of the three protocols is proportional to the ratio of malicious nodes. This is because with the increase of the malicious nodes, more energy will be wasted on unsuccessful data transmission and idle listening activities. Compared with other two protocols, SC-MAC achieves much high energy efficiency under the same conditions. On average, SC-MAC decreases 54.5% of the energy consumption than that of SF-MAC and 29.8% of the energy consumption than that of T-Lohi.Figure 8
Energy consumption versus number of nodes.


## 5. Conclusion

This paper proposed a secure MAC protocol for cluster-based UWSNs, called SC-MAC, which aims to ensure the security of data transmission under harsh and hostile underwater environments against different attacks, including Sybil attack, replay attack, and message manipulation attack. In SC-MAC, the clusters are formed and updated dynamically and securely. We leverage MAC layer information by considering the link quality as well as residual energy of the modem’s battery with an objective to maximize the network lifetime. After the successful mutual authentication between different sensor nodes, we formulated the channel scheduling process as a stochastic partially observed Markov decision process multiarmed bandit problem and derived the optimal channel scheduling rules. Simulation results show that SC-MAC can perform better than existing state-of-the-art MAC protocols in terms of network throughput, successful delivery ratio, and energy consumption in various circumstances.



---

*Source: 325474-2015-05-14.xml*