# OSPG-MAC: An OFDMA-Based Subcarrier Pregrouping MAC Protocol for Underwater Acoustic Wireless Sensor Networks

Authors: Yishan Su; Yongpeng Zuo; Zhigang Jin; Xiaomei Fu
Journal: Journal of Sensors
 (2019)

---

## Abstract

In underwater acoustic wireless sensor networks (UAWSNs), designing media access control (MAC) protocols is highly challenging because of their significant influence on network performance. It is a great challenge to design suitable MAC protocols for UAWSNs because of the specific characteristics of underwater acoustic channels, such as low communication rates, large propagation delays, and limited available bandwidth. Orthogonal frequency division multiple access (OFDMA) is a special case of OFDM-based multicarrier modulation in which multiple user symbols are transmitted simultaneously using different subcarriers with overlapping orthogonal frequency bands. In this paper, we propose an OFDMA-based subcarrier pregrouping MAC protocol for UAWSNs, termed OSPG-MAC. To make it easier to allocate subcarriers and avoid conflict, we group all the subcarriers into fixed subchannels in advance and allocate them in terms of these subchannels. To maximize the total throughput on each subchannel, a bit and power allocation algorithm for the protocol is proposed, termed the OSPG-MAC algorithm. Simulation results show that the performance of OSPG-MAC is better than that of classic underwater MAC protocols, including SFAMA and T-Lohi.


---

## Body

## 1. Introduction

Underwater acoustic wireless sensor networks (UAWSNs) have received tremendous attention in recent years since they can bring about significant benefits in many applications, such as tsunami warning, environment monitoring, disaster prevention, assisted navigation, and resource exploration [1]. The propagation loss of electromagnetic waves in seawater is serious and prevents transmission over long distances under the sea. Acoustic waves, which have been effectively applied to deep-water point-to-point communication, are the most plausible transmission medium for underwater wireless communication. However, due to the propagation of the sea surface and bottom reflection in shallow water, their use would lead to a serious time-varying multipath effect [1]. The propagation speed of sound waves in water is low (about 1500 m/s), is greatly affected by the flow of seawater, and causes serious Doppler effects. Due to the influence of time and weather, there would be serious time-varying effects on the acoustic channel. The particularities of underwater acoustic propagation lead to the unique characteristics of underwater acoustic channels, such as long and variable delays, long multipath delay spread, and limited bandwidth. Therefore, the application of UAWSNs in shallow water still faces great difficulties.In UAWSNs, a media access control (MAC) protocol is used to allocate limited acoustic wireless channel resources among network nodes. Designing a reliable and efficient MAC protocol is one of the most important issues for underwater acoustic wireless sensor networks. The function of the MAC layer protocol is to manage and control the communication channel shared by multiple nodes to avoid collisions and maintain reliable transmission conditions. Unfortunately, most existing terrestrial MAC protocols do not consider the characteristics of underwater channels and therefore cannot be applied to underwater acoustic wireless sensor networks directly [2]. The MAC protocol for UAWSNs should overcome many obstacles, such as energy consumption, transmission delay, and time synchronization, which pose considerable challenges to its design.Orthogonal frequency division multiplexing (OFDM) is one of the most promising physical layer solutions for underwater acoustic communication [3]. OFDM can convert selective fading acoustic channels into parallel and independent acoustic subchannels to achieve flat fading. Multipath delay spread of the acoustic channel, which leads to intersymbol interference (ISI), is solved effectively by using cyclic prefixing (CP) and adding a protection interval [4]. The complexity of an OFDM system can be reduced greatly through the IFFT/FFT hardware implementation structure proposed in [5]. The adjacent subcarriers overlap each other in the frequency domain and are orthogonal in the time domain, which means they are independent of each other. Therefore, OFDM can achieve high bandwidth utilization. Orthogonal frequency division multiple access (OFDMA) is a special case of OFDM-based multicarrier modulation in which multiple user symbols are transmitted simultaneously using different subcarriers in an orthogonal overlapping frequency band. Due to multiuser diversity and frequency diversity, OFDMA has great advantages over other technologies in UAWSNs. Different subcarriers can be allocated to different users. Moreover, OFDMA can exploit multiuser diversity by distributing different orthogonal independent subcarriers to different nodes in wireless multipath fading channels [5]. Because of the above advantages, OFDMA has attracted widespread attention for UAWSN application in recent years.In this paper, we propose an OFDMA-based Subcarriers Pregrouping MAC protocol called OSPG-MAC for underwater acoustic wireless sensor networks. The main feature of OSPG-MAC is the assignment of subcarriers to neighboring nodes in the form of subchannels containing sets of fixed subcarriers. This allows simultaneous transmission between neighboring nodes while avoiding collisions. Through our proposed subchannel allocation scheme, OSPG-MAC can eradicate the hidden terminal and exposed terminal problems that are encountered with most other UAWSN MAC protocols. To maximize the total throughput on the corresponding subchannels, a bit and power allocation algorithm for the protocol, termed OSPG-MAC, which combines the advantages of the water-filling and greedy algorithms, is proposed. The main idea of the OSPG-MAC algorithm is to estimate the discrete values of the power and throughput on each subcarrier through one iteration by a water-filling algorithm and then calculate the exact discrete values of the power and throughput on each subcarrier by a greedy algorithm. Compared with the traditional greedy algorithm, which calculates the values of the power and throughput from zero directly, the computational complexity of our algorithm, which can also find the maximum value of the total throughput, is greatly reduced. Finally, this paper provides extensive simulation experiments to evaluate the OSPG-MAC protocol.The remainder of this paper is organized as follows: In Section2, we present the related work. In Section 3, we introduce the system model. In Section 4, we describe the proposed OSPG-MAC protocol. In Section 5, we give the data subchannels, bit and power allocation algorithm for OSPG-MAC. In Section 6, we give several simulation experiments to evaluate our protocol. In Section 7, we conclude the paper.


## 2. Related Work

The MAC protocol for terrestrial wireless sensor networks has been studied extensively. However, due to the unique challenges of underwater channels, such as limited bandwidth, high variable propagation delays, channel asymmetry, and severe multipath and fading phenomena, the existing terrestrial MAC protocols are not suitable for underwater environments. In recent years, many MAC protocols have been proposed for underwater acoustic wireless sensor networks [6]. MAC protocols for UAWSNs can be divided into two types: contention-based and contention-free. The contention-based MAC protocols can be categorized as random multiple access-based (such as Aloha) and handshake multiple access-based (such as RTS/CTS). The contention-free MAC protocols can be categorized as FDMA-based, TDMA-based, and CDMA-based.To avoid collisions, some contention-based MAC protocols have been proposed. In [7], Molins and Stojanovic propose the classic slotted FAMA protocol, which is based on a channel access protocol called floor acquisition multiple access (FAMA). Slotted FAMA is a typical handshake multiple access-based MAC protocol that uses time slotting. Time slotting eliminates the need for long control packets, thereby saving energy. Slotted FAMA adds time slotting to the floor acquisition multiple access (FAMA) protocol, in which the timeline is divided into fixed length slots. It combines carrier interception (CS) with a handshake (RTS/CTS) between the sending node and the receiving node for data transmission that requires long control packets and protection time. In addition, slotted FAMA assumes that the clocks of the sensor nodes are fully synchronized. In [8], Syed et al. propose a distributed and energy-efficient MAC protocol called T-Lohi. T-Lohi adopts a new tone-based competition resolution mechanism that uses spatiotemporal uncertainty and high latency to detect conflicts and count competitors, thus achieving good throughput on all provided loads. T-Lohi uses a low power wake-up receiver to significantly reduce energy consumption. The authors obtain the channel in a distributed manner using contention rather than request-to-send/clear-to-send (RTS/CTS) packets. The T-Lohi algorithm divides the time into slots but uses tones instead of controlling packet switching to contend for channels. However, it ignores the problem of hidden and exposed terminals. In addition, the use of tones requires special hardware, which increases the cost and complexity of the sensor nodes. In [9], the authors propose an asynchronous handshaking-based MAC protocol called bidirectional-concurrent MAC with packet bursting (BiC-MAC). To improve the data transmission efficiency, they adopt packet bursting, in which sender-receiver pairs can exchange multiple rounds of bidirectional packet transmissions. In [10], Y. Luo et al. propose a receiver-initiated spectrum management (RISM) system for underwater cognitive acoustic networks (UCANs) and provide a method to jointly assign channel and power to maximize the spectrum utilization, which is evaluated by Aqua-Sim [11], an NS-2 based underwater network simulator, and shows a good performance compared with MMAC-CR [12]. In [13], Y. Dong et al. propose a traffic estimation-based receiver-initiated MAC (TERI-MAC) for UWSNs in order to improve the handshaking efficiency.Some contention-free MAC protocols have been proposed for UASNs with high traffic loads. In [14], the authors propose the multisession FAMA (M-FAMA) algorithm to enable session multiplexing and pipelining. M-FAMA initiates multiple simultaneous sessions using passively acquired local information (i.e., neighboring nodes’ propagation delay maps and expected transmission schedules). The greedy behavior of M-FAMA is controlled by a bandwidth balancing algorithm that guarantees max-min fairness across multiple contending sources. In [15], Tan et al. propose a distributed CDMA-based MAC protocol called PLAN. PLAN is designed for long-latency access networks, which can be used in half-duplex underwater acoustic sensor networks. To reduce Doppler effects in underwater environments, the authors utilize CDMA as the underlying multiple access technique. In [16], Hong et al. propose a TDMA-based MAC protocol that includes lightweight synchronization, defer time, and guard time. In [17], the authors propose a new energy- conserving and collision-free graph coloring MAC protocol called GC-MAC for UAWSNs. GC-MAC uses a TDMA-like principle by assigning separate time slots to every individual color in the network. Therefore, nodes with the same colors can transmit concurrently without any collision. In [18], the authors propose a new guard time setting method for TDMA-based MAC protocol in UAWSNs. The method applies a priori information, such as the maximum propagation delay of the networks and the maximum relative speed of the sensor nodes with respect to the center node and the mechanism of the packet transmission for the sensor nodes. In [19], the authors propose two medium access control (MAC) protocols, namely, Transmit Delay Allocation MAC (TDA-MAC) and Accelerated TDA-MAC, that are capable of providing time division multiple access (TDMA) to sensor nodes without the need for centralized clock synchronization. In [20], the authors focus on the time division multiple access (TDMA) based media access control (MAC) protocol design for UAWSNs. They consider a general 3D underwater communication scenario, and the mobility of sensor nodes is also taken into consideration. The authors introduce a dynamic and flexible spatial reuse strategy for the TDMA protocol design and then formulate the interference scenario as a dynamic interference-free graph according to the nodes’ current position distribution and a preset interference-free threshold. In [21, 22], the authors propose a multichannel MAC protocol called MC-UWMAC for UAWSNs. MC-UWMAC operates on multichannel using a single slotted control channel and multiple data channels. Control channel slots are dedicated for handshaking. Data transmission takes place in a unique data channel especially reserved for each communicating pair. In [23], the authors propose a Distributed Receiver-oriented Adaptive Multichannel MAC (DRAMAC) protocol for UWSNs. DRAMAC contains two key schemes: channel negotiation process based on cooperative correction (NPCC) and receiver-oriented dynamic channel negotiation strategy (DCNS). NPCC scheme can reduce the probability of collision by using the neighbors’ cooperation information. DCNS scheme can help select channel according to the packet length and the receivers network load condition.There has already been some research on OFDMA in terrestrial wireless sensor networks. In [24], the authors study the application of adaptive OFDMA in multiuser downlink scenarios in which the central node sends data to multiple distributed nodes simultaneously. In [25], the authors propose an algorithm for joint subcarrier and power allocation in uplink scenarios in OFDMA systems. In [26], based on the water-filling approach, the authors propose an efficient algorithm for transmitting bit and power allocation in wireless OFDM systems; it maximizes the data rate under a constraint on the total transmit bit and power error rate.Several OFDMA-based MAC protocols for UAWSNs have been put forward. In [27], a MAC protocol called UW-OFDMAC is proposed; it is a transmitter-based OFDMA scheme that integrates an original power and OFDMA parameter self-assignment algorithm to set the optimal transmit power, subcarrier spacing, and guard interval duration. UW-OFDMAC relies on the exchange of many control traffic messages, which casts doubt on its applicability to UAWSNs. In [28], a distance-based MAC protocol is proposed in which the sink node allocates OFDMA subchannels to sensor nodes based on their distances from the sink node. The network nodes must be fully synchronized so that the distance can be measured by round trip times. In addition, the energy consumption of the sink node is much larger than that of the sensor nodes. Moreover, the robustness of the network is very poor. If the sink node is destroyed, the network cannot communicate properly. In [4], a MAC protocol for UAWSNs based on adaptive OFDMA is proposed. The protocol has three modes of operation: random, equal opportunity, and energy-conscious. It is only suitable for static underwater sensor deployment because mobility increases energy expenditure and the already large delay from which acoustic channels suffer.


## 3. System Model

In this paper, we consider a UAWSN in which many sensor nodes are randomly distributed in the sea; the network topology is shown in Figure1. Each node can collect and store data in the sea and actively request to send (or receive) data to (or from) adjacent nodes. The large dashed circles represent the communication scopes of the corresponding nodes. The solid arrows indicate the directions in which data is transmitted, and the labels on each arrow, such as G1, G3, and G6, represent the data subcarrier groups used by the respective links.Figure 1
Network topology of underwater acoustic wireless sensor networks (UAWSNs).In this paper, sink node, neighboring node, and hidden node are defined as follows: sink node is a node that requests to send or receive data; neighboring node and hidden node are defined according to the communication range of sink node. Neighboring node is a node within the communication range of sink node, while hidden node is a node out of the communication range of a sink node. As shown in Figure1, there are three nodes (nodes 1-3) in the communication range of the sink node, which are called neighboring nodes of sink node. The nodes outside the communication range of sink node (nodes 4-9) are called hidden nodes of sink node.In Figure1, G1, G3, and G6 are already occupied by other nodes before sink node requests data. We can see that within the communication range of node 2, the data subcarrier groups G3 and G6 are occupied and can be heard by node 2. However, G3 and G6 are not in the communication scope of sink node, so sink node cannot hear G3 and G6. If sink node transfers data to node 2 through G3 or G6, there will be a conflict. To avoid collisions, sink node should exclude all data subcarrier groups, such as G1, G3, and G6, that can be heard by all nodes within its communication scope.To make it easier to allocate subcarriers and reduce conflict, N subcarriers (SCs) are interleaved into the M + 1 groups. As shown in Table1, CH is the public subchannel shared by all nodes; it is used to send and receive control messages. The set of subchannels G1,G2,…,GM is allocated to different node pairs. Each Gm, for m∈1,2,…,M, can be used by only one pair; otherwise, there will be a conflict.Table 1
N subcarriers (SCs) are interleaved into the M + 1 groups.
Data subchannels G 1 = S C 1 , S C M + 1 , … , S C S - 1 ∗ M + 1 G 2 = S C 2 , S C M + 2 , … , S C S - 1 ∗ M + 2 … G M = S C M , S C 2 ∗ M , … , S C M ∗ S  Control subchannel C H = S C M ∗ S + 1 , S C M ∗ S + 2 , … , S C NAs shown in Table1, a total of N SCs are grouped as follows: first, the N SCs are labeled from high to low by frequency, and then we get SC=SC1,SC2,…,SCN. Each data subcarrier group Gx (x∈1,2,…,M) contains S SCs (M∗S < N). The subcarriers with higher frequency labeled from 1 to MS constitute data subchannels, while the subcarriers with lower frequency labeled from (M∗S+1) to N constitute control subchannel.


## 4. Proposed OSPC-MAC Protocol

Figure2 illustrates the process of data transmission in the OFDMA-based subcarrier pregrouping MAC (OSPG-MAC) protocol. Different colors represent different subcarriers or subchannels. Figure 2(a) shows the process of sink node sending data to nodes 1, 2, and 3 concurrently. Figure 2(b) shows the process of sink node receiving data from nodes 1, 2, and 3 concurrently. We assume that each node has a unique ID. The process of data transmission in both Figures 2(a) and 2(b) is divided into two phases, namely, Phase 1, the channel reservation phase, and Phase 2, the data transmission phase.Figure 2
The process of data transmission in the OFDMA-based subcarrier pregrouping MAC (OSPG-MAC) protocol. (a) Sink node sends data to nodes 1, 2, and 3 concurrently. (b) Sink node receives data from nodes 1, 2, and 3 concurrently.
(a) (b)Phase 1 (channel reservation phase).
The channel reservation phase in Figure2(a) is the same as that in Figure 2(b). In this phase, sink node confirms the ID of each neighboring node and the data subchannels Gx being used within their corresponding communication ranges. As shown in Figure 2, sink node transports a request-to-send (RTS) packet, which contains the ID number of sink node, on the subcarrier CHw, which is selected from subchannel CH randomly. Then, sink node sends a short H packet on full band to estimate the channel state. After receiving the RTS packet, each neighboring node needs to feed back a clear-to-send (CTS) packet that contains its own ID number, sink node’s ID number, the data subchannel Gx, and the channel state information H.
Each neighbor node needs to listen for a period of time before feeding back the CTS packet to determine the data subcarrier group being used within the respective communication range. For example, as shown in Figure1, before CTS packet is fed back by node 2, listening for a period of time, it can be known that G3 and G6 are being used. The CTS packet fed back by node 2 needs to contain the used data subcarrier groups G3 and G6. After receiving the CTS packet, the sink node knows that G3 and G6 have been used. Node 1, node 2, and node 3, respectively, listen to the used subcarrier groups in their respective communication ranges and obtain a list of used subcarrier groups: LS1=∅, LS2=G3,G6, LS3=G1. Then, LS1, LS2, and LS3 are fed back to sink node through the CTS packets. If sink node uses G3 and G6 to transmit data, node 2 will have a communication conflict with nodes 4, 5, and 6. If sink node uses G1 to transfer data, node 3 will have a communication conflict with nodes 7 and 8. Therefore, sink node cannot use G1, G3, and G6 to transmit data.
There are two measures to avoid collision when neighboring nodes feed back CTS packets. First, each neighboring node can randomly back off for a period no longer than a preset timeτback-off while feeding back CTS packets. The other measure is to randomly select the control subcarriers used for feeding back to CH. Sink node needs to wait τ, which is the maximum possible feedback time, to receive all the CTS packets sent by each neighbor. The maximum possible feedback time τ can be calculated as follows.(1)τ=τback-off+2τdelay+τRTS+τCTSHere, τback-off is the maximal time spent backing off, τdelay is the time required for the maximum communication range, and τRTS and τCTS are the times needed to transmit the RTS and CTS packets, respectively.
After receiving all the CTS packets, sink node stores a list of requesting nodes LN. In the case of Figure1, LN = node 1, node 2, node 3. Then, sink node excludes the used subchannels Gx (G1, G3, and G6 in the case of Figure 1) and receives a list of sink node’s available data subchannels LS. Assuming the total number of subchannels is M = 6 in the case of Figure 1, LS = G2, G4, G5.Phase 2 (data transmission phase).
The data transmission phase in Figure2(a) is different from that in Figure 2(b). After Phase 1, sink node allocates the available data subchannels Gx in LS to one or more requesting nodes in LN (the details for the approach to allocating available data subchannels are presented in Section 5). Then, sink node sends a packet, which includes the allocation scheme for the available data subchannels, to its neighboring nodes. The available data subchannel allocation schemes in Figures 2(a) and 2(b) are included in the allocation scheme and request-to-allocate (RTA) packets, respectively. Each neighboring node obtains the corresponding available data subchannels from the received packet. In the case of Figure 1, sink node allocates G2 to node 1, G4 to node 2, and G5 to node 3. After allocating the available data subchannels, the sender runs the OSPG-MAC algorithm, which is presented in Section 5, to allocate bits and power to each subcarrier of the corresponding subchannels. After calculating the bit and power allocation scheme, the sender (which in Figures 2(a) and 2(b) is sink node and its neighboring node, respectively) sends an allocation scheme packet that contains the allocation information for bits and power on each subcarrier of the corresponding subchannels. After that, the sender sends a DATAx packet to the corresponding subchannels. The receiver (which in Figures 2(a) and 2(b) is the neighboring node and w, respectively) receives the allocation scheme and DATAx packet on the corresponding subchannels. Then, the receiver sends back an ACK or NACK packet to inform the sender of whether the packet has been received successfully or not. The sender repeats the above process until the DATAx packet is received successfully.


## 5. Approach to Allocating Data Subchannels, Bits, and Power for OSPG-MAC

### 5.1. Approach to Allocating Available Data Subchannels

As seen in Phase2 of OSPG-MAC in Section 4, sink node needs to allocate the available data subchannels Gx in LS to one or more requesting nodes in LN. To make the allocation of available data subchannels more reasonable, we set different priorities for different requesting nodes. Each requesting node in LN is given a priority list P. Then, according to P, the requesting nodes in LN are reordered, the requesting nodes with the higher priorities are placed in front, and the requesting nodes with the lower priorities are placed behind. Let LN＇ denote the list of requesting nodes reordered according to P. Finally, all the available data subchannels Gx in LS are sequentially assigned to different requesting nodes in the order determined by LN＇.First, suppose the number of available data subchannels in LS is greater than the number of requesting nodes in LN; for example, consider LS =G2, G4, G5, G8, G9, G10, LN = node 1, node 2, node 3, and P = P1, P2, P3 = 3, 3, 1. The request nodes in LN are reordered according to P as LN＇ = node 3, node 1, node 2. The result of the allocation is that G4,9 are assigned to node 1, G5,10 are assigned to node 2, and G2,8 are assigned to node 3. Now, suppose the number of available data subchannels in LS is less than the number of requesting nodes in LN; for example, consider LS = G2, G4, G5, G8, LN = node 1, node 2, node 3, node 4, node 5, node 6, and P = P1, P2, P3, P4, P5, P6 = 3, 3, 1, 4, 2, 1. The request nodes in LN are reordered according to P as LN＇ = node 3, node 6, node 5, node 1, node 2, node 4. The result of the allocation is that G2 is assigned to node 3, G4 is assigned to node 6, G5 is assigned to node 5, and G8 is assigned to node 1. Based on the allocation results, we can see that no available data subchannels are assigned to nodes 2 and 4. In this case, after the communication of other nodes ends and a new available data subchannel appears, the remaining requesting nodes are allocated to the remaining data subchannels.


### 5.2. Bit and Power Allocation Algorithm (OSPG-MAC Algorithm)

As seen in Phase2 of OSPG-MAC in Section 4, the sender runs the OSPG-MAC algorithm presented in this section to maximize the total throughput on the corresponding subchannels. The inputs and outputs of the algorithm are as follows.The inputs of the OSPG-MAC algorithm are the estimated value of the corresponding subchannel state H, the available total transmit powerpk(max) of node k (sender), the indices Dk of subcarriers in the corresponding subchannels, and the total number N of subcarriers.The outputs of the OSPG-MAC algorithm are the bit loadsbn on each subcarrier of the corresponding subchannels and the transmit power pn of each subcarrier of the corresponding subchannels.The goal of the OSPG-MAC algorithm is to maximize the total throughput on the corresponding subchannels under the constraint that the total transmit power is not greater than the available transmit power. The number of bits in subcarrier n can be expressed as(2)bn=log2⁡1+hnpnwhere bn(bn∈0,1,2,3,…) is the bit of the subcarrier n, hn is the channel state of subcarrier n, pn is the transmit power of subcarrier n.The transmit power of subcarrier n can be expressed as follows through (2):(3)pn=1hn2bn-1where pn is the transmit power of subcarrier n.The total bits and total transmit power of node k can be expressed as follows, respectively:(4)bk=⁡∑nϵDkbn(5)pk=∑nϵDkpnwhere Dk is the index of the subcarrier allocated of node k.The proposed protocol is based on a mathematical model that achieves the maximum possible total throughput of node k under the constraint that the total transmit power is not greater than the maximum total transmit power of node k. The problem can be formulated as follows:(6)maxfpn=∑nϵDklog21+hnpns.t.pn≥0,∀n∈Dkpk≤pkmaxwhere pk(max) is the maximum total transmit power of node k.The solution to the above optimization problem is(7)pn=β-1Hn+,∀n∈Dkwhere β is called the power water-filling level and [.]+ indicates a projection onto the positive real numbers, as pn cannot be negative in real systems.In case the transmission power is large enough or the channel state is good enough, we get the following.(8)pn=β-1hn>0,∀n∈DkFrom (8), we can estimate β as follows.(9)β=pn+1hn,∀n∈DkFrom (9), we get(10)β=1Nk∑nϵDkpn+1hnwhere Nk is the total number of subcarriers in Dk.To make full use of the total powerpk, we let pk=pk(max). From (10), we can estimate β as follows: (11)β=1Nkpkmax+∑nϵDk1hnwhere Nk is the total number of subcarriers in Dk.From (2) and (8), we get(12)bn=log2βhnwhere [x] is a rounding function that omits fractional parts smaller than 0.5 and counts all others, including 0.5, as 1.Let us introduce the idea of our algorithm. First, the approximate values of the transmit powerpn of subcarrier n and the number of bits bn in subcarrier n are calculated from the estimate of β, for which the value of bn is of practical significance because of the rounding function [.]. Then, the greedy algorithm is used to obtain the exact values of pn and bn.Power water filling is a global optimization algorithm, while the greedy algorithm is a local optimization algorithm. The core idea of the greedy algorithm is to allocate 1 bit per step to minimize the power required until the desired transmission rate is reached. In the greedy algorithm, every step is optimal. Therefore, the greedy algorithm uses local optima instead of global optima. The greatest disadvantage of the greedy algorithm is the large amount of computation. The computational complexity of the greedy algorithm is O(bN) where b is the total number of bits and N is the number of subcarriers.The OSPG-MAC algorithm takes the approximate values ofpn and bn calculated by the power water-filling level β as the initial values for the greedy algorithm, which can greatly reduce its computational complexity. The detailed steps of our algorithm are shown in Algorithm 1.Algorithm 1:OSPG-MAC algorithm.
Initialization: Estimate the water-filling levelβ by Formula (11), estimate the discrete values of the transmit powerpn, the bits bn, and the total transmit powerpk by Formulas (12), (3), and (5), respectively. Step  1 : Calculate the additional power required for each subcarrier to add one bit. For allnϵDk, calculate ∆pn=1/hn2bn, letnmin∗=arg⁡min⁡∆pn, nmax∗=arg⁡max⁡∆pn. Step  2 :If pk≤pk(max), go to Step 3. Otherwise, go to Step 4. Step  3 : If(pk+∆pnmin∗)>pk(max), end. Otherwise, load one bit on the subcarrier that requires the least power: b n m i n ∗ =  b n m i n ∗ + 1, pk=pk+∆pnmin∗, return to Step 1. Step  4 : Remove one bit from the subcarrier that requires the most power:bnmax∗=bnmax∗-1, pk=pk-1/2∆pnmax∗. Ifpk≤pkmax, end. Otherwise, return to Step 1.The purpose of Initialization is to estimate the discrete values ofbn and pn through the water-filling level β. The purpose of Steps 1 through 4 is to find the exact discrete values of bn and pn by the greedy algorithm. When the SNR is high enough, the computational complexity of this algorithm is far less than that of the traditional greedy algorithm. Figures 3(a) and 3(b) show the flow chart of greedy algorithm and OSPG-MAC algorithm, respectively.Figure 3
Flow chart of bit and power allocation algorithm. (a) Greedy algorithm. (b) OSPG-MAC algorithm.
(a) (b)


## 5.1. Approach to Allocating Available Data Subchannels

As seen in Phase2 of OSPG-MAC in Section 4, sink node needs to allocate the available data subchannels Gx in LS to one or more requesting nodes in LN. To make the allocation of available data subchannels more reasonable, we set different priorities for different requesting nodes. Each requesting node in LN is given a priority list P. Then, according to P, the requesting nodes in LN are reordered, the requesting nodes with the higher priorities are placed in front, and the requesting nodes with the lower priorities are placed behind. Let LN＇ denote the list of requesting nodes reordered according to P. Finally, all the available data subchannels Gx in LS are sequentially assigned to different requesting nodes in the order determined by LN＇.First, suppose the number of available data subchannels in LS is greater than the number of requesting nodes in LN; for example, consider LS =G2, G4, G5, G8, G9, G10, LN = node 1, node 2, node 3, and P = P1, P2, P3 = 3, 3, 1. The request nodes in LN are reordered according to P as LN＇ = node 3, node 1, node 2. The result of the allocation is that G4,9 are assigned to node 1, G5,10 are assigned to node 2, and G2,8 are assigned to node 3. Now, suppose the number of available data subchannels in LS is less than the number of requesting nodes in LN; for example, consider LS = G2, G4, G5, G8, LN = node 1, node 2, node 3, node 4, node 5, node 6, and P = P1, P2, P3, P4, P5, P6 = 3, 3, 1, 4, 2, 1. The request nodes in LN are reordered according to P as LN＇ = node 3, node 6, node 5, node 1, node 2, node 4. The result of the allocation is that G2 is assigned to node 3, G4 is assigned to node 6, G5 is assigned to node 5, and G8 is assigned to node 1. Based on the allocation results, we can see that no available data subchannels are assigned to nodes 2 and 4. In this case, after the communication of other nodes ends and a new available data subchannel appears, the remaining requesting nodes are allocated to the remaining data subchannels.


## 5.2. Bit and Power Allocation Algorithm (OSPG-MAC Algorithm)

As seen in Phase2 of OSPG-MAC in Section 4, the sender runs the OSPG-MAC algorithm presented in this section to maximize the total throughput on the corresponding subchannels. The inputs and outputs of the algorithm are as follows.The inputs of the OSPG-MAC algorithm are the estimated value of the corresponding subchannel state H, the available total transmit powerpk(max) of node k (sender), the indices Dk of subcarriers in the corresponding subchannels, and the total number N of subcarriers.The outputs of the OSPG-MAC algorithm are the bit loadsbn on each subcarrier of the corresponding subchannels and the transmit power pn of each subcarrier of the corresponding subchannels.The goal of the OSPG-MAC algorithm is to maximize the total throughput on the corresponding subchannels under the constraint that the total transmit power is not greater than the available transmit power. The number of bits in subcarrier n can be expressed as(2)bn=log2⁡1+hnpnwhere bn(bn∈0,1,2,3,…) is the bit of the subcarrier n, hn is the channel state of subcarrier n, pn is the transmit power of subcarrier n.The transmit power of subcarrier n can be expressed as follows through (2):(3)pn=1hn2bn-1where pn is the transmit power of subcarrier n.The total bits and total transmit power of node k can be expressed as follows, respectively:(4)bk=⁡∑nϵDkbn(5)pk=∑nϵDkpnwhere Dk is the index of the subcarrier allocated of node k.The proposed protocol is based on a mathematical model that achieves the maximum possible total throughput of node k under the constraint that the total transmit power is not greater than the maximum total transmit power of node k. The problem can be formulated as follows:(6)maxfpn=∑nϵDklog21+hnpns.t.pn≥0,∀n∈Dkpk≤pkmaxwhere pk(max) is the maximum total transmit power of node k.The solution to the above optimization problem is(7)pn=β-1Hn+,∀n∈Dkwhere β is called the power water-filling level and [.]+ indicates a projection onto the positive real numbers, as pn cannot be negative in real systems.In case the transmission power is large enough or the channel state is good enough, we get the following.(8)pn=β-1hn>0,∀n∈DkFrom (8), we can estimate β as follows.(9)β=pn+1hn,∀n∈DkFrom (9), we get(10)β=1Nk∑nϵDkpn+1hnwhere Nk is the total number of subcarriers in Dk.To make full use of the total powerpk, we let pk=pk(max). From (10), we can estimate β as follows: (11)β=1Nkpkmax+∑nϵDk1hnwhere Nk is the total number of subcarriers in Dk.From (2) and (8), we get(12)bn=log2βhnwhere [x] is a rounding function that omits fractional parts smaller than 0.5 and counts all others, including 0.5, as 1.Let us introduce the idea of our algorithm. First, the approximate values of the transmit powerpn of subcarrier n and the number of bits bn in subcarrier n are calculated from the estimate of β, for which the value of bn is of practical significance because of the rounding function [.]. Then, the greedy algorithm is used to obtain the exact values of pn and bn.Power water filling is a global optimization algorithm, while the greedy algorithm is a local optimization algorithm. The core idea of the greedy algorithm is to allocate 1 bit per step to minimize the power required until the desired transmission rate is reached. In the greedy algorithm, every step is optimal. Therefore, the greedy algorithm uses local optima instead of global optima. The greatest disadvantage of the greedy algorithm is the large amount of computation. The computational complexity of the greedy algorithm is O(bN) where b is the total number of bits and N is the number of subcarriers.The OSPG-MAC algorithm takes the approximate values ofpn and bn calculated by the power water-filling level β as the initial values for the greedy algorithm, which can greatly reduce its computational complexity. The detailed steps of our algorithm are shown in Algorithm 1.Algorithm 1:OSPG-MAC algorithm.
Initialization: Estimate the water-filling levelβ by Formula (11), estimate the discrete values of the transmit powerpn, the bits bn, and the total transmit powerpk by Formulas (12), (3), and (5), respectively. Step  1 : Calculate the additional power required for each subcarrier to add one bit. For allnϵDk, calculate ∆pn=1/hn2bn, letnmin∗=arg⁡min⁡∆pn, nmax∗=arg⁡max⁡∆pn. Step  2 :If pk≤pk(max), go to Step 3. Otherwise, go to Step 4. Step  3 : If(pk+∆pnmin∗)>pk(max), end. Otherwise, load one bit on the subcarrier that requires the least power: b n m i n ∗ =  b n m i n ∗ + 1, pk=pk+∆pnmin∗, return to Step 1. Step  4 : Remove one bit from the subcarrier that requires the most power:bnmax∗=bnmax∗-1, pk=pk-1/2∆pnmax∗. Ifpk≤pkmax, end. Otherwise, return to Step 1.The purpose of Initialization is to estimate the discrete values ofbn and pn through the water-filling level β. The purpose of Steps 1 through 4 is to find the exact discrete values of bn and pn by the greedy algorithm. When the SNR is high enough, the computational complexity of this algorithm is far less than that of the traditional greedy algorithm. Figures 3(a) and 3(b) show the flow chart of greedy algorithm and OSPG-MAC algorithm, respectively.Figure 3
Flow chart of bit and power allocation algorithm. (a) Greedy algorithm. (b) OSPG-MAC algorithm.
(a) (b)


## 6. Simulations

To evaluate the performance of the OSPG-MAC protocol, several simulation experiments are conducted on different aspects.


### 6.1. The Effect of M on the Performance of the Network

First, an experiment is carried out to show the effect of the number of data subchannels M on the performance of the network.Figure4(a) shows the effect of different data subchannel numbers M on the total feedback from the sink node’s communication range. In this paper, total feedback refers to the total number of subcarrier groups included in the used subcarrier group list LSx in the CTS packets fed back by all neighboring nodes. For example, in the case of Figure 1, the number of subcarrier groups included in the used subcarrier group list LS1=∅, LS2=G3, G6, LS3={G1 in the CTS packets fed back by node 1, node 2, and node 3 is, respectively, n1=0, n2=2, n3=1. The total feedback is n1 + n2 + n3 = 0 + 2 + 1 = 3. The larger the total feedback, the longer the length of the used subcarrier group list LSx, and the lower the accuracy of neighboring node listening for the used subcarrier group.Figure 4
The influence of different values of M on the performance of the network. (a) The influence of M on feedback from neighbors. (b) The influence of M on subcarrier allocation (M = 1, M = 2, M = 4).
(a) (b)Among them, the number of nodes in the sink node’s communication range is T (T = 10, T = 20, T = 30). As shown in Figure4(a), the total amount of feedback in the communication range of the sink node increases with an increase in the number of nodes T in the communication range of the sink node as well as with an increase in the number of data subchannels M. Therefore, we can reduce the total feedback from the sink node’s communication range by reducing the number of data subchannels M. Suppose the total number of OFDMA subcarriers is N = 256. In Figure 4(a), the total amount of feedback in the case M = N = 256 is much higher than that for M = 10. From this experiment, we can see the necessity of grouping subcarriers into M subchannels; this can effectively reduce feedback and conflict. In addition, another experiment is carried out to show the effect of different values of M on the allocation results for the data subchannels.Figure4(b) shows the results of different data subchannel allocations. To simplify the analysis, it is assumed that all data subchannels are unoccupied when the sink node allocates data subchannels; thus, all data subchannels are available. For the case M = 1, only one neighbor, which is node 1 in Figure 4(b), is allocated; it receives almost all the subcarriers and achieves the highest data rate, which is approximately 7500 bps. For the case M = 2, no more than 2 neighbor nodes, node 1 and node 2 in Figure 4(b), are allocated with nearly a half of the whole subcarriers and achieve a lower data rate, approximately 4000 bps. For the case M = 4, no more than 4 neighbor nodes, which are nodes 1, 2, 3, and 4 in Figure 4(b), are each allocated nearly a quarter of the subcarriers and achieve data rates of approximately 2000 bps.Through an analysis of Figures4(a) and 4(b), we can conclude that an appropriate value of M, neither too large nor too small, is necessary for the network to perform well.In actual network, the optimal value of M is selected as follows: maximize the value of M, under the constraint that the network collision rate is within a tolerable range, in the network scenario of maximum network density.


### 6.2. OSPG-MAC Algorithm

Figure5 shows a comparison between the iterations of OSPG-MAC algorithm and those of the greedy algorithm at different signal-to-noise ratios (SNRs). Figure 5(a) shows that the number of iterations increases with an increase in SNR, but the increase for the OSPG-MAC algorithm is obviously less than that for the greedy algorithm. As shown in Figure 5(b), the performance of the OSPG-MAC algorithm is slightly worse than that of the greedy algorithm, although the difference between them is very small. Therefore, compared with the greedy algorithm, the superiority of the OSPG-MAC algorithm is obvious.Figure 5
Comparison of the OSPG-MAC algorithm with the greedy algorithm. (a) Number of iterations. (b) Average throughput per subcarrier (bps).
(a) (b)


### 6.3. Performance Comparison

As seen in Figure6, we simulate a 40 km × 40 km 2D network area with many randomly distributed sensor nodes. The communication radius of each node is 5 km. We randomly select one node in each 10 km × 10 km area as the sink node and replace the sink node every 10 minutes. Here, N = 256 and M = 10. The bandwidth is 25 kHz, the packet size is 3000 bits, and the average transmission rate of each subchannel is 500 bps. The sink node collects data from all its neighbor nodes every T minutes.Figure 6
Simulated network model.We compared the performance of three MAC protocols: OSPG-MAC, SFAMA, and T-Lohi. In the OSPG-MAC protocol, the sink node collects data from its neighbors every minute (T = 1). In the SFAMA protocol and T-Lohi protocols, each sensor node in the network requests communication every minute.Figure7(a) shows the total throughput of OSPG-MAC, SFAMA, and T-Lohi as the number of nodes increases. Figure 7(a) shows that, with an increase in the number of nodes, the total throughput of OSPG-MAC increases significantly, while the overall throughputs of SFAMA and T-Lohi change a little. This is because OSPG-MAC makes full use of OFDM technology, different subcarriers are independent of each other, and bandwidth utilization is very high.Figure 7
Comparison of the performances of OSPG-MAC, SFAMA, and T-Lohi. (a) Total throughput (T = 1). (b) Average energy consumption (T = 1).
(a) (b)Figure7(b) shows the average energy consumption per bit of OSPG-MAC, SFAMA, and T-Lohi as the number of nodes increases. Figure 7(b) shows that, with an increase in the number of nodes, the average energy consumption per bit for OSPG-MAC does not change much, while the average energy consumption per bit for SFAMA and T-Lohi increases significantly. This is because the subcarrier pregrouping mechanism of OSPG-MAC significantly reduces feedback and collisions and improves energy utilization.Figure8 shows the difference between the OSPG-MAC and the NOde Grouped Ofdma MAC (NOGO-MAC) in [24] (T = 1, T = 2, T = 3). Figures 8(a) and 8(b) show the changes in network lifetime and total throughput, respectively, as the number of nodes increases. NOGO-MAC network is a heterogeneous network in which the sink node and sensor nodes are unchangeable. Among them, the sensor nodes are responsible for collecting data in the ocean and the sink node is responsible for aggregating the data collected by the sensor nodes. In cluster networks, if the sink node is damaged, the entire network will fail. In our proposed network model, nodes can take turns being the sink node, which greatly improves the robustness of the network and prolongs its overall life.Figure 8
Comparison of OSPG-MAC and NOGO-MAC. (a) Network lifetime (T = 1, T = 2, T = 3). (b) Total throughput.
(a) (b)As in Figure8(a), with an increase in the number of sensor nodes, the network lifetime of the proposed OSPG-MAC network increases while that of NOGO-MAC network decreases. In OSPG-MAC network, with an increase in the number of sensor nodes, the cycle of each node’s turn as the sink node becomes longer, so the lifetime of OSPG-MAC network increases. On the other hand, in NOGO-MAC network, with an increase in the number of sensor nodes, the task of the sink node becomes heavier, so the lifetime of the network decreases.Figure8(b) shows that the total throughput of NOGO-MAC network is slightly less than that of OSPG-MAC network because the remaining power of the sink node in the NOGO-MAC network is lower than that in the OSPG-MAC network.


## 6.1. The Effect of M on the Performance of the Network

First, an experiment is carried out to show the effect of the number of data subchannels M on the performance of the network.Figure4(a) shows the effect of different data subchannel numbers M on the total feedback from the sink node’s communication range. In this paper, total feedback refers to the total number of subcarrier groups included in the used subcarrier group list LSx in the CTS packets fed back by all neighboring nodes. For example, in the case of Figure 1, the number of subcarrier groups included in the used subcarrier group list LS1=∅, LS2=G3, G6, LS3={G1 in the CTS packets fed back by node 1, node 2, and node 3 is, respectively, n1=0, n2=2, n3=1. The total feedback is n1 + n2 + n3 = 0 + 2 + 1 = 3. The larger the total feedback, the longer the length of the used subcarrier group list LSx, and the lower the accuracy of neighboring node listening for the used subcarrier group.Figure 4
The influence of different values of M on the performance of the network. (a) The influence of M on feedback from neighbors. (b) The influence of M on subcarrier allocation (M = 1, M = 2, M = 4).
(a) (b)Among them, the number of nodes in the sink node’s communication range is T (T = 10, T = 20, T = 30). As shown in Figure4(a), the total amount of feedback in the communication range of the sink node increases with an increase in the number of nodes T in the communication range of the sink node as well as with an increase in the number of data subchannels M. Therefore, we can reduce the total feedback from the sink node’s communication range by reducing the number of data subchannels M. Suppose the total number of OFDMA subcarriers is N = 256. In Figure 4(a), the total amount of feedback in the case M = N = 256 is much higher than that for M = 10. From this experiment, we can see the necessity of grouping subcarriers into M subchannels; this can effectively reduce feedback and conflict. In addition, another experiment is carried out to show the effect of different values of M on the allocation results for the data subchannels.Figure4(b) shows the results of different data subchannel allocations. To simplify the analysis, it is assumed that all data subchannels are unoccupied when the sink node allocates data subchannels; thus, all data subchannels are available. For the case M = 1, only one neighbor, which is node 1 in Figure 4(b), is allocated; it receives almost all the subcarriers and achieves the highest data rate, which is approximately 7500 bps. For the case M = 2, no more than 2 neighbor nodes, node 1 and node 2 in Figure 4(b), are allocated with nearly a half of the whole subcarriers and achieve a lower data rate, approximately 4000 bps. For the case M = 4, no more than 4 neighbor nodes, which are nodes 1, 2, 3, and 4 in Figure 4(b), are each allocated nearly a quarter of the subcarriers and achieve data rates of approximately 2000 bps.Through an analysis of Figures4(a) and 4(b), we can conclude that an appropriate value of M, neither too large nor too small, is necessary for the network to perform well.In actual network, the optimal value of M is selected as follows: maximize the value of M, under the constraint that the network collision rate is within a tolerable range, in the network scenario of maximum network density.


## 6.2. OSPG-MAC Algorithm

Figure5 shows a comparison between the iterations of OSPG-MAC algorithm and those of the greedy algorithm at different signal-to-noise ratios (SNRs). Figure 5(a) shows that the number of iterations increases with an increase in SNR, but the increase for the OSPG-MAC algorithm is obviously less than that for the greedy algorithm. As shown in Figure 5(b), the performance of the OSPG-MAC algorithm is slightly worse than that of the greedy algorithm, although the difference between them is very small. Therefore, compared with the greedy algorithm, the superiority of the OSPG-MAC algorithm is obvious.Figure 5
Comparison of the OSPG-MAC algorithm with the greedy algorithm. (a) Number of iterations. (b) Average throughput per subcarrier (bps).
(a) (b)


## 6.3. Performance Comparison

As seen in Figure6, we simulate a 40 km × 40 km 2D network area with many randomly distributed sensor nodes. The communication radius of each node is 5 km. We randomly select one node in each 10 km × 10 km area as the sink node and replace the sink node every 10 minutes. Here, N = 256 and M = 10. The bandwidth is 25 kHz, the packet size is 3000 bits, and the average transmission rate of each subchannel is 500 bps. The sink node collects data from all its neighbor nodes every T minutes.Figure 6
Simulated network model.We compared the performance of three MAC protocols: OSPG-MAC, SFAMA, and T-Lohi. In the OSPG-MAC protocol, the sink node collects data from its neighbors every minute (T = 1). In the SFAMA protocol and T-Lohi protocols, each sensor node in the network requests communication every minute.Figure7(a) shows the total throughput of OSPG-MAC, SFAMA, and T-Lohi as the number of nodes increases. Figure 7(a) shows that, with an increase in the number of nodes, the total throughput of OSPG-MAC increases significantly, while the overall throughputs of SFAMA and T-Lohi change a little. This is because OSPG-MAC makes full use of OFDM technology, different subcarriers are independent of each other, and bandwidth utilization is very high.Figure 7
Comparison of the performances of OSPG-MAC, SFAMA, and T-Lohi. (a) Total throughput (T = 1). (b) Average energy consumption (T = 1).
(a) (b)Figure7(b) shows the average energy consumption per bit of OSPG-MAC, SFAMA, and T-Lohi as the number of nodes increases. Figure 7(b) shows that, with an increase in the number of nodes, the average energy consumption per bit for OSPG-MAC does not change much, while the average energy consumption per bit for SFAMA and T-Lohi increases significantly. This is because the subcarrier pregrouping mechanism of OSPG-MAC significantly reduces feedback and collisions and improves energy utilization.Figure8 shows the difference between the OSPG-MAC and the NOde Grouped Ofdma MAC (NOGO-MAC) in [24] (T = 1, T = 2, T = 3). Figures 8(a) and 8(b) show the changes in network lifetime and total throughput, respectively, as the number of nodes increases. NOGO-MAC network is a heterogeneous network in which the sink node and sensor nodes are unchangeable. Among them, the sensor nodes are responsible for collecting data in the ocean and the sink node is responsible for aggregating the data collected by the sensor nodes. In cluster networks, if the sink node is damaged, the entire network will fail. In our proposed network model, nodes can take turns being the sink node, which greatly improves the robustness of the network and prolongs its overall life.Figure 8
Comparison of OSPG-MAC and NOGO-MAC. (a) Network lifetime (T = 1, T = 2, T = 3). (b) Total throughput.
(a) (b)As in Figure8(a), with an increase in the number of sensor nodes, the network lifetime of the proposed OSPG-MAC network increases while that of NOGO-MAC network decreases. In OSPG-MAC network, with an increase in the number of sensor nodes, the cycle of each node’s turn as the sink node becomes longer, so the lifetime of OSPG-MAC network increases. On the other hand, in NOGO-MAC network, with an increase in the number of sensor nodes, the task of the sink node becomes heavier, so the lifetime of the network decreases.Figure8(b) shows that the total throughput of NOGO-MAC network is slightly less than that of OSPG-MAC network because the remaining power of the sink node in the NOGO-MAC network is lower than that in the OSPG-MAC network.


## 7. Conclusions

This paper presented an OFDMA-based MAC protocol called OSPG-MAC for underwater acoustic wireless sensor networks. The use of subchannels made it much easier to allocate subcarriers and avoid conflict. We also proposed an OSPG-MAC algorithm to maximize the total throughput on the corresponding subchannels. Simulation results verified the effectiveness of the OSPG-MAC protocol.



---

*Source: 4965231-2019-06-16.xml*