PMAC: A Real-world Case Study of Underwater MAC

Son N. Le∗ , Yibo Zhu∗ , Zheng Peng∗ , Jun-Hong Cui∗ and Zaihan Jiang
{son,yibo.zhu,zhengpeng,jcui}@engr.uconn.edu
∗
Computer Science and Engineering Department, University of Connecticut, Storrs, CT 06269

Acoustic Division, Naval Research Laboratory, Washington, DC 20375

ABSTRACT SASHA [4], UW-Aloha [5], and PMAC. PMAC, short for
In this paper we document the design, implementation and Pipelining MAC, is specifically designed to take advantage
testing of a scheduling-based MAC protocol, called PMAC, of this topology while the other two can be used in more
for a 2012’s sea trial, and experience gained from this pro- general scenarios. The string topology, although simple, has
cess. In this experiment, the topology was a straight line, its real applications, for example monitoring of oil pipes or
and PMAC is specifically design to take advantage of it: submarine cables. In our test, data are sent from one end of
network nodes take turn to send and those that are three the string to the other.
hops apart are allowed to do so simultaneously. The result PMAC is a scheduling-based MAC protocol. It optimizes
shows that although PMAC’s performance is much better network performance by parallelizing data transmissions in
compared to other protocols in the same experiment, there such a way that every two nodes that are three hops apart
is room for improvement by selecting an appropriate packet are allowed to send data simultaneously. A data transmis-
size and scheduling scheme. Besides that, the result reveals sion occurs completely within one time slot, and a node
an important factor which we will show has significant im- sends data in its designated time slot. In the subsequent
pact on protocol design, yet is usually ignored in theoretical time slot, if the node either hears this packet being for-
work: modem processing delay. The modem processing de- warded or receives an explicit acknowledgment, it proceeds
lay is in fact not negligible, and increasing with packet size. to the next packet. Otherwise, it stays with the current
The paper also presents important lessons from this field packet in the next designated time slot. Therefore, the result
test which are useful for similar future efforts. that we introduce in this paper is not specific to PMAC; it is
also applicable to slot-based protocols, for instance, Slotted
FAMA [6].
1. INTRODUCTION The main contributions of the paper are following. First,
Underwater acoustic networks (UANs) [1–3] are often re- we design and implement PMAC and test it in an open
ferred to as a set of protocols and algorithms that together sea offshore New Jersey. Second, through different metrics,
can enable a wide range of applications, such as weather we show that there are important practical factors that are
forecasting, sea exploration, and undersea surveillance. De- usually neglected in state-of-the-art protocol designs. The
spite research efforts over past decades, practical protocol most significant of these factors is the modem processing de-
design for UANs is still a challenging issue, which is in part lay, which is increasing with packet size. The difference in
due to scarcity of real-world data and experience. Real sea processing between a 800 B packet and a 20 B one can be
tests are costly, and therefore many studies are conducted about 0.8 s, which is comparable to the propagation delay.
in constrained environments such as in a lake or a pool. This phenomenon has substantial impact on PMAC’s per-
Although these small scale experiments can be used for ini- formance. Third, we summarize important experience which
tial evaluation of a protocol, they are not sufficient to study is useful for similar field tests in the future. Finally, we in-
what really happens in open areas. In this paper, we doc- troduce a method to improve PMAC’s performance through
ument the design, implementation and testing of a MAC choosing a suitable packet size.
protocol, called PMAC, in Atlantic Ocean, and experience The rest of this paper is organized as follows. In Sec. 2,
gained from this process, which can be helpful for similar we review several MAC protocols for UANs. Sec. 3 lays
efforts in the future. out the initial design of PMAC. Sec. 4 presents experiment
In our recent sea trial in 2012, we use a string topol- settings and how data are collected. Sec. 5 provides data
ogy, with different number of nodes to test three protocols: analysis, including performance metrics, time drift and mo-
dem processing delay. Sec. 6 introduces a distributed algo-
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are not
rithm which chooses the suboptimal packet length to deal
made or distributed for profit or commercial advantage and that copies bear with varying environment condition and time drift. The al-
this notice and the full citation on the first page. Copyrights for components gorithm efficiency is demonstrated using simulation. Sec. 7
of this work owned by others than ACM must be honored. Abstracting with concludes this paper.
credit is permitted. To copy otherwise, or republish, to post on servers or to
redistribute to lists, requires prior specific permission and/or a fee. Request
permissions from permissions@acm.org. 2. RELATED WORK
WUWNet November 11-13, 2013, Kaohsiung, Taiwan
Copyright 2013 ACM 978-1-4503-2584-4/13/11...$15.00. Many scheduling-based MAC protocols have been pro-
http://dx.doi.org/10.1145/2532378.2532380. posed for UANs. Due to high experiment cost, most of
these protocols are verified with simulation. ST-MAC [7]
schedules signals from different sources such that they do Slot 1 Slot 2 Slot 3 Slot 4 Slot 5 Slot 6
not overlap at a receiver, henceforth improving performance
by avoiding collisions and parallelizing transmissions. This Node 1 • • ?• • • ?• •
d,1 a,1 d,2 a,2
protocol requires global topology information, and thus is
not scalable in practice.  
T-Lohi [8] tries to reserve the channel before data trans- Node 2 • • • ?• • • ?•
mission using short tones. The fact that the tones’ dura- d,1 a,1 d,2 a,2

tions are shorter than the propagation delay reduces colli-  

sion probability and allows for counting contenders. Node 3 • • • • ?• • •
With S-FAMA [6], network nodes compete for the chan- d,1 a,1 d,2
nel using the RTS/CTS mechanism. While a node is trans-
mitting data, all neighbor nodes stay silent and request for
 
Node 4 • • • • • ?• •
the channel afterward. R-MAC [9] is similar to S-FAMA; d,1 a,1
however, multiple data transmissions are scheduled by the
receiver. Both S-FAMA and R-MAC face the schedule mis- 
Node 5 • • • • • • ?•
match problem when neighboring node(s) could not receive
d,1 a,1
the transmission schedule.
Different from the above protocols, PMAC is designed 
specifically for string networks. Although its operations are Node 6 • • • • • •
slot-based, PMAC deals with the schedule mismatch issue by
assigning each node with a specific set of time slot, which Figure 1: Transmission pipeline. A straight solid
allows for parallel data transmissions. Furthermore, after arrow represents a packet sent from one node to
the slot assignment, we do not need to reserve the channel another, and a squiggly one denotes an overheard
for each data packet. packet: (1) the arrow direction indicates where the
There are efforts to implement UAN protocol in the real corresponding packet originates, and (2) the arrow
world. SeaWeb, first deployed in 1998 [10], is probably label has two components: the corresponding packet
the path breaker with tight software/hardware integration, type (‘a’ means acknowledgment and ‘d’ data) and
which allows for better optimization. However, little per- packet sequence number.
formance information is revealed. Various approaches have
been experimented: TCP/IP tunnelling [11], SUNSET [12],
N2 waits until S2 to forward the data to N3 . By the end
DESERT [13]. Our work is different from the above in many
of this slot, the forwarded P1 not only reaches N3 but also
aspects. It documents detailed implementation and design
is overheard by N1 , implicitly acknowledging N2 ’s success-
of PMAC which is implemented on top of Aqua-Net [14].
ful reception of P1 . This process is repeated by successive
Besides protocol performance metrics, we also present the
nodes on the string, and note that while N4 is forwarding P1
experience and new findings from the test which is useful
to N5 , N1 is sending P2 to N2 . This concurrency is possible
for future field tests and studies.
because N3 is unable to hear the data packet from N1 and
neither is N2 from N4 . Therefore, no collision occurs while
3. PIPELINING MAC PROTOCOL N2 is receiving P2 from N1 and N3 overhears the implicit
In this section, we begin with an overview of how pipelined acknowledgment for P1 from N4 .
transmission works in PMAC and then proceed to describing From this description, implicit acknowledgments are em-
technical details of the protocol. ployed to minimize exchange of control packets. This proto-
col however does not eliminate the use of explicit acknowl-
3.1 Overview edgments. In Fig. 1, when P1 reaches the last node, N6 in
The transmission pipeline of PMAC is illustrated in Fig. 1. this example, this node explicitly acknowledges the recep-
Following this protocol, time is divided into identical slots, tion of P1 for it does not forward the data any further. A
each of which is denoted by a dashed line between two black more general scenario is when a node has already finished
dots. For any network node, its start time of a new slot is forwarding a particular packet, but still received the same
synchronized with others’. packet from the preceding node, because of lost implicit ac-
PMAC is designed for a string network which is assumed knowledgments for instance. In this case, an explicit ac-
to be deployed such that every two nodes that are three knowledgment is needed to tell the preceding node to move
hops apart, or having two nodes in the middle, are able to on to the next packet.
transmit data simultaneously without collisions. The ratio- There are also situations that we use piggybacked implicit
nale behind this assumption is that if nodes 1 and 4 start acknowledgments. A forwarder may accumulate more than
to transmit at the same time, the signal at node 2 is more one packet in its incoming queue because the link quality
likely to be from node 1 because it is stronger and arrives of the current hop is not as good as that of the preceding.
earlier than that from node 4. When this node forwards a packet, it implicitly acknowl-
In order to facilitate detailed description, let Nk denote edges the last packet that it receives successfully.
the k-th node on the string, Si the i-th slot, and Pl the l-th Before we have the network transmission pipeline as in
packet. Fig. 1, there are two major issues to solve. First, the network
Every node is restricted to limit any of its data transmis- needs to determine a uniform slot length to use. Second,
sions within one time slot. Take Fig. 1 as an example: N1 because transmissions occur on the slot basis, and a uniform
starts first by sending P1 in S1 . After receiving this packet, slot length is adopted across the network, the start time of
 tsP,i : Ni sends • O • tp,n : Pipeline start time
PROBE τi
$  
δtn−1 =tsT ,n −tp,n
• trP,i+1 : Ni+1 receives
•O tsT,n : Nn sends
Δti =tsA,i+1 −trP,i+1
 TIME ALIGN τn−1
•O tsA,i+1 : Ni+1 sends
} 
ACK PROBE τi trT,n−1 : Nn−1 receives •
z 
trA,i : Ni receives • ACK TIME ALIGN
!
 •
•
TRIGGER Figure 3: Timeline alignment
$
•
ACK TRIGGER
z an ACK TRIGGER packet. If Ni does not receive the ACK TRIGGER
•
within 2τi units of time, it resends the TRIGGER packet. Note
Figure 2: Slot length estimation that the TRIGGER packet can also be implicitly acknowledged
by Ni overhearing a PROBE packet from Ni+1 .
By the end of this phase, Nn has the slot length to use
the first slot must be synchronized on all nodes. In other in the network. This information however is unknown to
words, each node needs to align its transmission timeline to the rest of the network. The following section introduces
match others. These issues are addressed in the following a mechanism to both propagate the information and align
subsections. node’s timelines.

3.2 Slot Length Estimation 3.3 Timeline Alignment

Slot length is estimated on a per-hop basis, spreading from This phase is initiated by Nn and performed on hop by
one end of the string network until the other end is reached. hop. Fig. 3 gives an illustration for the hop between Nn
In this section, we assume that the packet size is predeter- and Nn−1 . Nn , after receiveing a TRIGGER packet, picks a
mined and uniform in the network; therefore, the slot length starting time for its pipeline transmission, tp,n , starting from
must be sufficient for any node to transmit a packet to its which, Nn updates its slot count every τ units of time. After
neighbors. If we let τi be the time needed to transmit a that, Nn sends a TIME ALIGN packet to Nn−1 , which carries
packet on the link between Ni and Ni+1 , the appropriate the slot length τ , its sending token, and time gap δtn−1 from
slot length will be maxn k=1 {τi }, where n is the number of tp,n to when this packet is sent.
nodes. Similar to PROBE or ACK PROBE packets, a TIME ALIGN packet
In our protocol, this estimation phase is implemented re- is zero padded so that its size equals the predetermined
cursively. Let us assume that Ni−1 has calculated the slot value. This padding is crucial because it ensures that the
length of the network segment from the first node to itself, transfer of a TIME ALIGN packet takes as long as that of a
k=1 {τk }. Ni−1 then informs Ni of this value, so that Ni
maxi−1 PROBE packet, and allows Nn−1 to estimate the pipeline start
can start its estimation as illustrated in Fig. 2. In this es- time using
timation, four packet types are involved: PROBE, ACK PROBE,
TRIGGER and ACK TRIGGER. Ni first sends a PROBE to Ni+1 tp,n−1 = trT,n−1 − δtn−1 − τn−1 , (2)
and record the event time as tsP,i . Ni+1 after receiving where trT,n−1 is the time when Nn−1 receives the TIME ALIGN
the packet, acknowledges it with an ACK PROBE. PROBE and packet and τn−1 is the aggregate delay of transferring a
ACK PROBE packets are zero padded so that their sizes match packet of the predetermined size from Nn to Nn−1 or vice
the predetermined value to guarantee that the transfer de- versa. This value is known to Nn−1 from the slot length
lays for PROBE and ACK PROBE are close. ACK PROBE also car- estimation phase.
ries the latency, Δti from when the corresponding PROBE is Similar to the PROBE-ACK PROBE exchange in Sec. 3.2, sev-
received to when it is acknowledged to improve estimation eral TIME ALIGN packets are sent in each hop to improve es-
accuracy. timation accuracy. After Nn−1 receives the last TIME ALIGN
After Ni receives the ACK PROBE, it calculates its τi as packet from Nn , it follows the same procedure that Nn takes
follows to help Nn−2 determine the pipeline starting time and so
τi = (trA,i − tsP,i − Δti ) /2, (1) on. Nn considers a TIME ALIGN packet to be successfully re-
ceived if it receives an ACK TIME ALIGN packet from Nn−1 ,
where trA,i is the time when the ACK PROBE arrives at Ni . which acknowledges the TIME ALIGN packet. Different from
In order to mitigate the effect of randomness, this PROBE- an ACK PROBE packet, an ACK TIME ALIGN packet need not
ACK PROBE exchange is run several times on each hop to ob- be zero padded; it carries the sequence number of the cor-
tain the average value. responding TIME ALIGN packet.
Upon completion of this estimation process, Ni wraps After a node finishes estimating the pipeline starting time,
max{maxi−1k=1 {τk }, τi } = maxk=1 {τk } in a TRIGGER packet
i
it counts time slots in a circular progression fashion on three
and sends to Ni+1 . This node recursively repeats the above numbers, 1, 2, and 3. Namely, if we let SI be the index of
procedure. The last node in this chain will have the slot the current time slot, and SI+1 be that of the next one,
length to use in the network, maxnk=1 {τi }. A TRIGGER packet SI+1 can be written as
is much shorter than a PROBE or ACK PROBE; it carries only
maxik=1 {τk }. Ni+1 acknowledges the TRIGGER packet with SI+1 = (SI mod 3) + 1. (3)
 ' #$%)
Table 1: Data set parameters
Number Packet size Bit rate Packet rate
of nodes (bytes) (bps) (packets/s)
Set 1 5 500 600 0.015
Set 2 5 200 300 0.015
Set 3 5 500 600 0.020
Set 4 6 200 300 0.005
'#$%)
Set 5 9 200 300 0.005

• an ATM-885 MF modem from Benthos.

The Gumstix board is connected to other devices via serial

ports.
#$%)
Due to time and logistics limitation, we are only able to
conduct 5 tests with PMAC. Each test has a different num-
ber of nodes, packet size, bit rate, and packet rate as listed
in Table 1. While the first two parameters are self-explained,
clarification is needed for the other two:

  • A bit rate determines how fast the acoustic modems

 
   !
(#$%) send data. Varying environmental conditions is the
       main reason for the use of different bit rates.
"#$%& "'#$%& "#$%&
• A packet rate is the frequency of a new packet being
Figure 4: Test site area sent out at the sender. In this field test, packets are
generated in such a way that the inter-packet interval
is Poisson distributed.
As a side note, Ni can always know the current time slot
index using the following equation As described earlier, the string topology is used to validate
protocols. In each experiment, there is only one sender and
SI = (tnow,i − tp,i ) /τ  mod 3 + 1, (4) one receiver, corresponding to the two far ends of the string.
where tnow,i is the current time in Ni ’s timeline.
As described in Sec. 3.1, a node is only allowed to transmit
4.2 Data collection
data within one slot. This mechanism is implemented with Raw data are collected in the form of protocol log files,
the notion of token mentioned earlier in this section. A where events are captured with nanosecond time resolution
node occupies a time slot only when its token matches the using POSIX’s gettimeofday(). Although it is intuitive to
slot index. As the initiator of the time alignment phase, Nn send debugging information on-the-fly back to the control
is free to choose it token, which is either 1, 2 or 3. Nn−1 station, one should pay special attention on the amount of
when receiving a TIME ALIGN packet from Nn , computes its this information and how it is transmitted.
token in an inverse circular progression. Let Tn be the token Let us consider a simplified scenario in which a protocol
of Nn , and Tn−1 be that of Nn−1 , Tn−1 is obtained from Tn logs debug messages with printf() on a regular computer
as follows and the Gumstix. On a regular computer, since standard
 output is connected to the monitor, these function calls re-
Tn − 1, Tn = 2, 3 turn immediately. However, in our field test, standard out-
Tn−1 = . (5)
3, Tn = 1 put is connected to an RF modem. The fact that the mo-
dem offers certain degree of reliability can stall the calling
4. EXPERIMENT SETTINGS thread. This phenomenon happens frequently at sea where
We implemented PMAC in Aqua-Net [14], a framework RF communication is often unstable, and can falsify exper-
for underwater networking, as a MAC layer module and iment results if not handled correctly. The impact of this
tested it in a sea experiment organized by the Naval Re- phenomenon is severe in that a sending thread may accumu-
search Laboratory in early September of 2012. The test site, late scheduled packets and send them out much later than
shown in Fig. 4, is about 100 miles offshore New Jersey. the intended time.
There are at least two methods to deal with this issue:
4.1 Experiment parameters redirecting standard output to /dev/null, and running test
In this test, we have 9 network nodes, each of which is a programs in a GNU Screen∗ session. The latter is more
standalone system with the following instruments: convenient than the former because Screen handles standard
output, and provides users with latest debug messages. The
• a Gumstix Verdex Pro XM4 microcomputer running number of messages depends only on Screen’s buffer size.
Embedded Linux which hosts the protocol stack,
• a GPS receiver to track its position, 5. DATA ANALYSIS
∗
• an RF modem to monitor the node from our boat, and http://www.gnu.org/software/screen/
 Table 2: Performance result Table 5: Parallel reception statistics
End-to-end Average Slot Total Short-short Short-long Long-long
goodput e2e delay length runtime S1 C2 F3 S1 C2 F3 S1 C2 F3
(bps) (s) (s) Set 1 1 1 0 1 26 25 9 0 28
Set 1 51.14 226.42 12.54 2972.14 Set 2 0 0 0 0 18 2 1 0 42
Set 2 23.63 94.77 10.91 2978.48 Set 3 0 0 1 8 45 98 15 0 80
Set 3 44.64 523.42 12.63 8601.47 Set 4 3 0 0 0 1 8 8 0 42
Set 4 11.07 184.79 12.56 2601.68 Set 5 0 0 1 21 20 48 57 0 416
Set 5 6.92 2653.43 10.96 11 090.43 1 2 3
success crossing failure

Table 3: Per-hop delivery ratio

5.2 Presence of time drift
Set 1 Set 2 Set 3 Set 4 Set 5 In this experiment, since each node is a standalone system,
Hop 1 39/79 46/92 112/228 27/78 70/175 it is not possible to derive time drift using absolute time from
Hop 2 40/70 45/64 102/212 22/30 49/239 the log file because protocol instances were started at slightly
Hop 3 60/66 48/50 159/175 18/22 55/98 different time. Fortunately, since all nodes use a uniform slot
Hop 4 38/39 44/45 96/96 31/58 91/181 length, we can characterize time drift by calculating actual
Hop 5 12/20 94/334 slot lengths from log files. The descriptive statistics of slot
Hop 6 74/132 lengths for Set 5 are given in Table 4. From this table, the
Hop 7 57/67 reader can notice that some nodes are about 0.0005 s faster
Hop 8 48/49 than others, which will make a difference of roughly 0.5 s
with 1000 samples. Time division protocols, therefore, need
to have certain guard time to compensate this time drift and
In this section we first introduce end-to-end performance periodic time synchronization to realign nodes’ timelines.
evaluation of PMAC, and delve into more in-depth data
analysis on time drift and modem processing delay. 5.3 Impact of packet length on collision
5.1 End-to-end performance evaluation A common assumption in protocol design is that short
packets have a smaller chance of causing collisions; however,
The following end-to-end metrics are used to for perfor-
it is not so simple to implement in practice. In this section,
mance evaluation:
we show that such packets if not scheduled carefully can
• End-to-end goodput is the average rate of non du- severely degrade network performance.
plicate packet delivery from the source to the destina- Let us consider a 4-node segment of a string network con-
tion. sisting of nodes Ni , . . . , Ni+3 . According to PMAC’s design,
in each their designated slots, Ni and Ni+3 are allowed to
• Average end-to-end delay is the average time needed transmit data simultaneously. There are three possible com-
to transfer a packet from the source to the destination. binations of parallel transmissions in terms of packet dura-
The end-to-end performance results for PMAC are com- tion: short-short, short-long and long-long. In PMAC, short
piled in Table 2. The slot length for each set is measured packets are explicit acknowledgments and long packets are
by the protocol. Since PMAC waits 3 slots to send a data data.
packet, be it new or retransmitted, the rate of one packet While Ni and Ni+3 are transmitting, signals at Ni+1 and
every 3 slots is called the saturation threshold. If the packet Ni+2 are most vulnerable to interference. There are three
rate exceeds the threshold, data generation is totally con- reception scenarios that can happen at Ni+1 and Ni+2 :
trolled by PMAC. The reader can realize that all the packet
• Success is when Ni+1 receives the message from Ni
rates in Table 1 are not saturated. In this case, PMAC may
and so does Ni+2 from Ni+3 .
have partial control on data generation if retransmissions
occur. • Crossing is when success does not take place, and
The first three set of data was obtained on the 7th and 8th Ni+2 receives the message from Ni , or Ni+1 from Ni+3 .
of September, under rather favorable weather compared to
Set 4 and 5 because the latter were conducted right before • Failure is when neither success nor crossing occurs.
a storm. We can easily notice this fact by the correlation Statistics of these groups are provided in Table 5. From
between the total run time and the number of packets suc- this table, we can see that the short-short case happens much
cessfully received at the sink. This reality is also confirmed less frequently than the other two. The number of short-
by Table 3 which shows that per-hop delivery ratios in Set long successes is less than that of long-long ones. Moreover,
4 and 5 are much lower than those in the rest. except for Set 5, successes make a smaller percentage in
Although PMAC performs much better than other pro- short-long events than in long-long ones. This fact is an
tocols in the same experiment [15], and can be used as a indicator short packet’s negative effect.
comparison baseline, results in Table 2 are not optimal. In Let us further consider the length of corrupted packets, ,
the design of PMAC, we assume that nodes that are 3 hops in crossings and failures in two following scenarios:
away can transmit data simultaneously; in actuality, this
depends largely on environmental conditions and thus does • Short-long: Ni is sending a short packet and Ni+3
not always hold. Discrepancies in hardware timing can also sending a long one. The time from the beginning of the
degrade protocol performance. slot to when Ni+2 reports a CRC error is calculated.
 Table 4: Descriptive statistics of time slots
Node Max (s) Min (s) Count Mean (s) Stddev (s) Q1 (s) Q2 (s) Q3 (s)
1 10.961 92 10.977 09 1090 10.969 91 0.002 10 10.9696 10.9704 10.9709
2 10.963 56 10.977 53 1376 10.970 46 0.000 39 10.9704 10.9705 10.9706
3 10.961 95 10.977 31 1083 10.969 89 0.002 10 10.9696 10.9704 10.9708
4 10.962 09 10.978 02 1054 10.969 91 0.002 08 10.9697 10.9703 10.9708
5 10.962 01 10.976 81 1030 10.969 99 0.001 82 10.9702 10.9703 10.9704
6 10.961 97 10.977 35 1046 10.970 40 0.002 07 10.9689 10.9704 10.9708
7 10.961 92 10.977 79 1062 10.970 90 0.002 18 10.9712 10.9715 10.9716
8 10.962 06 10.976 20 1075 10.970 03 0.001 83 10.9698 10.9703 10.9707
9 10.962 05 10.977 96 1033 10.970 87 0.002 05 10.9712 10.9714 10.9716

Table 6: Length of corrupted packets 4.6

Short-long Long-long 4.5

N a μ b(s) σ c(s) N a μ b(s) σ c(s) 4.4

Set 1 51 4.211 0.058 28 11.227 0.258 4.3

Processing delay (s)

Set 2 20 4.581 0.050 3 9.930 0.041 4.2
Set 3 151 4.221 0.067 78 10.656 0.708
4.1
Set 4 3 6.099 0.029 8 10.896 0.560
Set 5 30 4.950 0.839 234 9.228 0.851 4

a b c 3.9
population size mean value variance
3.8

3.7
• Long-long: Both Ni and Ni+3 are sending a long
3.6
packet. The durations from the beginning of the the 0 100 200 300 400 500 600 700 800
Packet length (bytes)
slot to when Ni+1 and Ni+2 report CRC errors are
calculated and averaged.
Figure 5: Modem processing delay
Table 6 shows the statistics of . By comparing Table 5
and 6, it happens frequently in the short-long scenario that
Ni+2 reports a CRC error shortly after Ni and Ni+3 send
their packets. Since a packet is CRC checked by the mo- Due to the varying link quality both in time and space and
dem before passing to Aqua-Net, the packet must be avail- difference in time ticking, a fixed maximum length, even ini-
able in its entirety. Moreover, as we can see from the long- tially considering environmental conditions, will not deliver
long scenario, it takes much longer to transmit a long-long a good performance if the network is to operate for a long
packet; therefore, the packet that Ni+2 receives is not the time. In this section, we consider an adaptive method to
data packet sent by Ni+3 but the explicit acknowledgment select the value.
by Ni . This means that the processing delay for a short
packet is significantly less than that for a long one because 6.1 Optimal Hop-based Packet Size
Ni+3 is closer to Ni+2 than Ni .
To facilitate our discussion, let us consider a string net-
Processing delay measurement with Benthos modems is
work of n hops. Denote
conducted after the field test to confirm this hypothesis. We
measure the time between when a packet is written to the • l as the packet length,
serial port to when the modem starts to emit signal. An
example is shown in Fig. 5, which is conducted with 3 s • τ (l) as the length of the slot in which a packet of size
forwarding delay† , 300 bps acoustic bit rate. The difference l can be transferred. In this work, t(l) is estimated by
in preparation delay between a 800 bytes and 1 bytes can a linear function: t(l) = αl + β, where α, β > 0.
be 0.9 s which is comparable to the propagation delay.
The presence of preparation delay negatively affects time • pi (l) be the probability that packet of size l gets through
sensitive algorithms, such as time synchronization or schedul- the i-th link. If we let γi be the bit error rate (BER)
ing based protocols if they are designed without awareness of Li , pi (l) can be written as
of this delay. With the delay, the practical impact of small
packets is not small if they are not scheduled carefully. This pi (l) = (1 − γi )l , (6)
fact emphasizes the necessity of an efficient cross-layer ar-
chitecture which allows designers to deal with hardware con- • Li as the i-th link,
straints more effectively.
• S as the chunk of data to send, and |S| as its size.
6. IMPROVING PERFORMANCE OF PMAC We would like to minimize the time it takes to transfer S
† to from one end of the string to another. One can realize
Forwarding delay determines how long a modem accumu-
late data from the serial line before sending them out. that S will be passed through all links before it reaches the
destination. Therefore, one heuristic solution to the origi- 6.3 Simulation Results
nal problem is to minimize the average time that the chunk In this section, we use MATLAB simulation to verify the
spends on each link: efficiency of our algorithm. In the simulation scenario, we
li = arg min (|S|ti (l)/l) = arg min (ti (l)/l) , (7) assume a 10-hop network where the BER of a link is either
l l q1 = 0.00001 or q2 = 0.0002‡ . In each simulation, and 1
where ti (l) is the average time needed to send a packet of MiB of data is transmitted from one end to another. For
size l over Li . any packet size, 1000 rounds are run to measure the transfer
Let Rl be the event that a packet of size l is received delays and obtain their average value. A transfer delay is
successfully. Rl is equivalent to the event that the packet the time needed to transmit the given data completely from
reaches the next node, and its acknowledgment reaches the the one end of the string to the other.
sender. Therefore, the probability of this event is Let γ = {γ1 , γ2 , . . . , γ10 } denote the BER vector in the
network. We realize that two permutations of the same γ
Pr[Rl ] = p2i (l). (8) give us very close transmission length, especially when the
Let Xi be the number of retransmissions for a packet of number of runs increases. An example is given in Table 7. In
size l. Since the packet is retransmitted until it is success- this table, γ (1) = {q1 , q2 , q2 , q1 , q1 , q2 , q2 , q1 , q1 } and γ (2) =
fully received, Xi follows a geometric distribution with pa- {q2 , q2 , q2 , q2 , q1 , q1 , q1 , q1 , q1 }.
rameter p2i (l), meaning Based on this remark, it is sufficient to consider unordered
 k−1 2 BER vectors. For a 10-hop network, there are 11 such vec-
Pr[Xi = k] = 1 − p2i (l) pi (l). (9) tors. We denote an unordered vector as γ (k,10−k) , which
indicates there are k components equal to q2 and 10 − k
Each retransmission will delay a packet for 3 time slots;
components equal to q1 . We do not consider homogeneous
thus, the average delay that a packet of size l experiences
cases, γ (0,10) and γ (10,0) , because our algorithm will give the
on Li is
optimal value. Therefore, there are 9 vectors left and we
ti (n) = E[3τ (l) X1 ] = 3 p−2
i (l) (αl + β), (10) compare the following strategies on them:
where E[X] denotes the expected value of a random variable • MIN lmin = min1≤i≤10 {li },
X. Hence, Eq. 7 becomes
  • MAX lmax = max1≤i≤10 {li },
3(αl + β) α β
li = arg min = arg min + . (11)
l lp2i (n) l p2i (l) lp2i (l) • OPT lopt , the optimal packet length.
We can prove [16] that the value of li is
 The actual optimal packet length is obtained by searching
1 2αβ (1 + (1 − γi )2 ) α+β for a value between lmin and lmax that minimizes the average
li = α2 + β 2 + − . (12) transmission length. From Table 8, we can see that the abso-
2α 1 − (1 − γi )2 2α
lute difference between the optimal transmission length and
6.2 PMAC with Adaptive Packet Size our sub-optimal solution decreases when the number of bad
links increase. In the case with one bad link, the transmis-
When the network is initially deployed, we assume that no sion length difference is about 5000 seconds, which is around
environmental information is available. The protocol, there- 6% the optimal value. Picking the maximum packet length
fore, initializes with a default packet size. After the network is definitely not a good choice, because it doubles the trans-
is in operation, a node Ni can collect the packet error mission length. In homogeneous cases, γ (0,10) and γ (10,0) ,
rate (PER) the link Li to the node Ni+1 . The procedure the optimal packet length is identical to that by our proto-
involves Ni keeping track of the number of retries for every col. Transmission length for γ (0,10) and γ (10,0) is 81791.66 s
data packet an Ni+1 adding the number of times it receives and 41049.22 s, respectively. The optimal packet length is
the same data packet in the acknowledgment packet. 154 B for γ (0,10) and 890 B for γ (10,0) .
Let the number of retransmissions and of successful recep- Basagni et al. consider choosing the packet size [17] in a
(k)
tions for the packet of with sequence number k be Rrt and more general case than this paper. The authors use DACAP
(k)
Rsr respectively. PER of Li is calculated as and CSMA in their study; however, the fact that they are
 (k)  (k) different from PMAC does not allow us to compare the re-
P ERi = Rrt / Rsr . (13) sults numerically. In our scenario, since the size of given data
k i
is fixed, maximizing the throughput is equivalent to mini-
Let l be the current packet size BER of Li is obtained by mizing the average total transfer delay. Moreover, by having
a uniform BER as in Basagni’s work, we haved proved that
γi = 1 − (1 − P ERi )1/l . (14)
there exists an optimal packet size as in Eq. 11. This means
Periodically, a new packet size is chosen so that the net- that in our special case throughput efficiency does not in-
work adapts to environmental changes. The refreshment crease monotonically with packet size even when the BER
procedure is initiated by N1 computing the best packet length is 10−6 . Nevertheless, the smaller is the BER, the greater
l1 for L1 using Eq. 12 and passes this information to N2 . the packet size becomes.
N2 , in turn, computes l2 , compares it with l1 and sends the
smaller value to N3 . As the last node, Nn has the short- 7. CONCLUSIONS
est optimal length, l = min{l1 , . . . , ln−1 }. Nn passes l to
Nn−1 , and Nn−1 passes on the value to Nn−2 and so on. ‡
With a BER equal to q1 , a 400 byte packet is sucessfully
Eventually, N1 receives l and initiates a new transmission delivered with probability 0.97. The probability drops to
pipeline. 0.53 if the BER equals q2 .
 An Underwater Sensor Network Architecture: Design,
Table 7: Transmission length (in seconds) of permu- Implementation, and Initial Testing,” in Proc.
tated BER vectors IEEE/MTS OCEANS, 2009.
Packet size γ (1) γ (2) [6] M. Molins and M. Stojanovic, “Slotted FAMA: A
154 B 80 559.73 80 592.47 MAC Protocol for Underwater Acoustic Networks,” in
246 B 76 779.89 76 779.89 Proc. IEEE OCEANS, 2006.
338 B 80 322.41 80 300.01 [7] C.-C. Hsu, K.-F. Lai, C.-F. Chou, and K. C.-J. Lin,
430 B 87 303.17 87 666.13 “ST-MAC: Spatial-Temporal MAC Schedulging for
522 B 97 315.21 97 373.67 Underwater Sensor Networks,” in Proc. IEEE
614 B 109 619.79 109 857.24 INFOCOM, 2009, pp. 1827–1835.
706 B 124 570.68 124 666.21 [8] A. Syed, W. Ye, and J. Heidemann, “T-Lohi: a New
798 B 141 718.89 141 906.59 Class of MAC Protocols for Underwater Acoustic
890 B 163 056.92 162 460.06 Sensor Networks,” in Proc. INFOCOM, 2008, pp.
231–235.
[9] P. Xie and J.-H. Cui, “R-MAC: an Energy-Efficient
Table 8: Transmission length (in seconds) of differ- MAC Protocol for Underwater Sensor Networks,” in
ent approaches Proc. IEEE WASA, 2007, pp. 187–198.
BER vector MIN MAX OPT [10] J. Rice, B. Creber, C. Fletcher, P. Baxley, K. Rogers,
γ (1,9) 79 517.86 152 957.48 75 098.03 K. McDonald, D. Rees, M. Wolf, S. Merriam,
γ (2,8) 79 481.56 152 649.54 75 959.57 R. Mehio, J. Proakis, K. Scussel, D. Porta, J. Baker,
γ (3,7) 80 407.33 160 615.21 76 291.62 J. Hardiman, and D. Green, “Evolution of Seaweb
γ (4,6) 80 593.56 162 954.90 76 755.18 Underwater Acoustic Networking,” in Proc.
γ (5,5) 80 918.32 165 205.35 77 029.72 MTS/IEEE OCEANS, 2000.
γ (6,4) 81 062.06 166 750.69 77 304.81 [11] A. Caiti, V. Calabro, L. Fusini, A. Munafo,
K. Grythe, J. M. Hovem, and A. L. T. A. Reinen,
γ (7,3) 81 196.48 168 820.18 77 552.11
“Underwater Acoustic Network Performance: Results
γ (8,2) 81 399.95 170 285.96 77 758.23
from the UAN11 Sea Trial,” in Proc. MTS/IEEE
γ (9,1) 81 660.69 171 625.69 77 998.37 OCEANS, October 2012.
[12] C. Petrioli and R. Petroccia, “SUNSET: Simulation,
Emulation and Real-life Testing of Underwater
In this paper, we introduce the design, implementation Wireless Sensor Networks,” in Proc. IEEE UComms,
and experimentation of a scheduling-based MAC protocol 2012.
called PMAC. The real field test data show that PMAC’s [13] G. Toso, R. Masiero, P. Casari, O. Kebkal, M. Komar,
performance, although much better than two other protocols and M. Zorzi, “Field Experiments for Dynamic Source
in the same experiment, is far from the ideal case. There Routing: S2C EvoLogics Modems Run the SUN
are several causing factors such as varying environment con- Protocol Using the DESERT Underwater Libraries,”
dition and time drift, and we develop an algorithm which in Proc MTS/IEEE OCEANS, 2012.
determines the appropriate packet length to deal with these [14] Z. Peng, Z. Zhou, J.-H. Cui, and Z. J. Shi, “Aqua-Net:
two factors. Yet, the most influential factor is the modem An Underwater Sensor Network Architecture: Design,
processing delay, which is thought to be negligible before the Implementation, and Initial Testing,” in Proc. IEEE
test. This delay increases in packet length and magnifies the OCEANS, 2009.
impact of short packets if they are not scheduled carefully.
[15] Z. Peng, S. Le, M. Zuba, H. Mo, H. Zhou, J.-H. Cui,
This fact emphasizes the need for an efficient cross-layer de-
S. Zhou, Z. Jiang, and J. Schindall, “Field Test
sign in underwater networking.
Experience of an Underwater Wireless Network in the
Atlantic Ocean,” in Proc. MTS/IEEE OCEANS, 2013.
8. REFERENCES [16] S. Le, Y. Zhu, J.-H. Cui, and Z. Jiang, “Pipelined
[1] I. F. Akyildiz, D. Pompili, and T. Melodia, transmission mac for string underwater acoustic
“Underwater acoustic sensor networks: Research networks,” UCONN CSE, Tech. Rep.
challenges,” Ad Hoc Networks, vol. 3, no. 3, pp. UbiNet-TR13-01, 2013.
257–279, May 2005. [17] S. Basagni, C. Petrioli, R. Petroccia, and
[2] J. Cui, J. Kong, M. Gerla, and S. Zhou, “The M. Stojanovic, “Choosing the Packet Size in Multi-hop
challenges of building scalable mobile underwater Underwater Networks,” in Proc. OCEANS, 2010.
wireless sensor networks for aquatic applications,”
IEEE Network, vol. 20, no. 3, pp. 12–18, May 2006.
[3] J. Partan, J. Kurose, and B. N. Levine, “A survey of
practical issues in underwater networks,” in Proc.
ACM WUWNet, 2006, pp. 1–8.
[4] H. Mo and J.-H. Cui, “Selective ARQ and Slotted
Handshake Based Access (SASHA) for Underwater
Acoustic Networks,” UCONN CSE, Tech. Rep.
UbiNet-TR13-02, 2013.
[5] Z. Peng, Z. Zhou, J.-H. Cui, and Z. Shi, “Aqua-Net: