# Stochastic Scheduling for Underwater Sensor Networks

Dimitri Marinakis, Kui Wu, Sue Whitesides

► To cite this version:

Dimitri Marinakis, Kui Wu, Sue Whitesides. Stochastic Scheduling for Underwater Sensor Networks. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. pp.134-146, 10.1007/978-3-642-20757-0_11 . hal-01583414

HAL Id: hal-01583414

https://inria.hal.science/hal-01583414

Submitted on 7 Sep 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Stochastic Scheduling for Underwater Sensor
Networks

Dimitri Marinakis, Kui Wu, and Sue Whitesides

School of Computer Science
University of Victoria, Canada

dmarinak@kinsolresearch.com, wkui@ieee.org, sue@uvic.ca

**Abstract.** The context of underwater sensor networks (UWSNs) presents special challenges for data transmission. For that context, we examine the merit of using a simple, stochastic transmission strategy based on the ALOHA protocol. The strategy uses a stochastic scheduling approach in which time is slotted, and each network node broadcasts according to some probability during each time slot. We present a closed-form solution to an objective function that guides the assignment of the broadcast probabilities with respect to overall network reliability. We propose an easily distributed heuristic based on local network density and evaluate our approach using numerical simulations. The evaluation results show that even without using explicit control signalling, our simple stochastic scheduling method performs well for data transmission in UWSNs.

**Keywords:** underwater sensor networks, slotted ALOHA, network reliability, MAC protocols

# 1 Introduction

The monitoring and exploration of the ocean is of great importance to the sustainable and environmentally sound development of the Earth. Activities such as oceanographic data collection, offshore exploration, and ocean ecosystem monitoring are facilitated by the deployment of Unmanned or Autonomous Underwater Vehicles (UUVs, AUVs), equipped with underwater sensors, e.g., see Kennedy et al. [5]. There is a growing demand for UUVs/AUVs that cooperate to perform monitoring tasks; e.g., a fleet of small, inexpensive underwater AUVs for monitoring underwater waste sites was suggested by Nawaz et al. [15]. To cooperate effectively, the nodes must be able to exchange data and control messages with one other.

Underwater communication, however, is itself a challenging area of active research (e.g., [12], [6]). Radio waves propagate underwater only at very low frequencies (e.g., 30-300 HZ) and require high transmission power which generally cannot be afforded on board by UUVs/AUVs. Underwater, optical waves are affected by scattering effects and cannot be used to transmit over long distances. So far, acoustic communication has been the physical layer of choice for underwater communication. Underwater acoustic communication, however, is subject to large propagation latency, low bandwidth, high bit error rate (BER), and complex multipath fading. To make the situation worse, there can be large variations
in temperature, salinity, and pressure over short distances in the underwater environment, all of which can significantly impact acoustic propagation.

In existing RF communication systems, Medium Access Control (MAC) protocols are used to resolve contention issues in medium access. As a basic requirement, a MAC protocol should be able to find a transmission scheduling scheme that eliminates or minimizes conflicting transmissions. To achieve this, an implicit control mechanism (e.g., Time Division Multiple Access (TDMA)), or explicit control messages (e.g., Request-To-Send (RTS) and Clear-To-Send (CTS) messages in Carrier Sense Multiple Access (CSMA) based protocols), are adopted. Simulation studies have shown that the RTS/CTS based control, which alleviates hidden/exposed terminal problems and improves network throughput [4], actually degrades throughput when the propagation delay becomes large [21].

Interestingly, it has recently been shown that MAC protocols based on the relatively simple ALOHA protocol [1] perform well in an underwater, multi-hop environment in which there are significant propagation delays. Recently, Syed et al. [19] modified the slotted ALOHA protocol for underwater, acoustic communication so that ALOHA could achieve a throughput comparable to what it achieves in RF networks. In related work, Petrioli et al. [11] evaluated various MAC protocols for underwater sensor networks and found that in multi-hop, underwater acoustic networks, ALOHA variants out-performed protocols in which there were larger overhead costs. Additionally, simulations reported by Zhou et al. [21] demonstrated that random ALOHA schemes can provide stable performance in UWSNs.

There is no 'one-size fits all' MAC layer appropriate for all underwater applications. To date, no MAC protocol has been commonly accepted as an industrial standard for UWSNs. For example Partan et al. [10] state that medium access is an unresolved problem in underwater acoustic networks. Thus, it is likely that, in specific application areas, lightweight, ALOHA-based MAC protocols will have a place in underwater networking.

Motivated by the role we believe ALOHA based MAC protocols will play in UWSNs, we have examined the merit of a simple, stochastic transmission strategy based on the ALOHA protocol: Time is slotted, and at the beginning of each time slot, each node in the network is assigned a probability for transmission. Such a simple link scheduling method is easy to implement and requires virtually no control overhead. Therefore, we propose that stochastic variants of slotted ALOHA such as the protocol we present here could be used for networking mobile underwater devices. In this context, the network topology may change dynamically, and any energy wasted in colliding transmissions is inconsequential relative to the power requirements of the actuators on the AUVs. Additionally, one key communication requirement is to deliver relatively continuous, but low bandwidth data among proximal nodes for navigation and coordination purposes.

**Main Contributions:** We lay the groundwork for exploring whether stochastic scheduling for lightweight, ALOHA based MAC variants might provide suitable
solutions for underwater network communication challenges. Specifically, for the
stochastic variant of slotted ALOHA we proposed above:

- we consider how the transmission probability of a node should be adjusted based on its local (at a given time) communication topology in order to obtain good overall network performance;

- we present a closed form solution to an objective function for assigning the transmission probabilities that is aimed at improving network performance in terms of reliability;

- we show that a heuristic based on the optimizing values of our objective function is easily distributed and shows good performance in simulations.

2 Related Work

2.1 Underwater MAC protocols

A number of MAC protocols have been proposed to handle the special condi-
tions encountered in underwater multi-hop sensor networks, e.g., [8], [17], [9],
[13]. Despite the disadvantages of the inherent propagation delays, a number
of modern MAC protocols proposed for underwater communication nevertheless
rely on the exchange of handshaking contol messages for medium access. For
example, Slotted FAMA, as presented by Molins and Stojanovic [8], is based
on carrier sensing. Each network node constantly listens to the channel, but
stays idle unless it has permission to transmit, which is granted via an RTS /
CTS handshaking mechanism. Collisions are handled through a random back off
scheme. Simulations demonstrate that this protocol has promise for underwa-
ter mobile networks, although the authors consider an application in which the
data packets exchanged are much larger than the control packets used for the
handshaking. In this situation, the disadvantage of significant propagation de-
lays when employing handshaking for collision avoidance is somewhat masked.
The suitability of this approach for an application in which many small data
packets are exchanged on a frequent basis is not clear.

The T-Lohi MAC introduced by Syed et al. [17] also employs a synchronized transmission frame with a handshaking scheme for collision avoidance. Unlike Slotted FAMA, however, the protocol allows network nodes to sleep for energy saving purposes. When a node using the T-Lohi protocol is ready to send data, it attempts to reserve the channel by sending a control message (a tone) during a reservation period. If the node does not hear one or more tones from other nodes during this reservation period then it is clear to send; otherwise it backs off and waits. Energy savings through sleeping are achieved by using custom acoustic hardware that triggers the node to wake up when the tone is detected.

Considerable research has demonstrated the promise of underwater MAC layers that incorporate CDMA; e.g. the work of Pompili et al. [13], the work of Page and Stojanovic [3], and the work of Tan and Seah [20]. The approach is particularly suited for some challenging application areas, such as shallow water operation where multi-path interference is a major factor. In other applications however, e.g. where congestion issues dominate, the operational simplicity of ALOHA schemes can be attractive.
In contrast to CDMA based approaches, Slotted FAMA and T-Lohi, the UWAN-MAC protocol presented by Park and Rodoplu [9] does not employ a handshaking mechanism using control messages to reserve channel access. When using UWAN-Mac, each node transmits infrequently but regularly, with a randomly selected offset. The schedule of a node's neighbour is learned via synchronization packets sent during an initialization period. The approach achieves energy savings by finding locally synchronized schedules such that network nodes can sleep during idle periods. Although there is no explicit method for avoiding collisions, the collisions are shown to be rare. The approach relies, however, on a static network in which the transmission delays between any pair of nodes remain roughly constant. The UWAN-MAC approach has some similarity in spirit to the stochastic scheduling we consider in this paper, and it should be possible to modify UWAN-MAC to benefit from our analysis, e.g., by adapting the duty cycle of each node based on local network density.

## 2.2 Stochastic Scheduling

The class of problems related to assigning a slot to each node in a wireless network for the purposes of collision avoidance is referred to as broadcast scheduling. Such problems were considered as early as the mid-eighties by Chlamtac and Kutten [2], for example. Later in that decade, Ramaswami and Parhi [14] showed that the problem of finding a minimum length schedule that allows each node to hear from each neighbour is NP-complete and presented effective heuristics.

In previous work [7], Marinakis and Whitesides presented a slotted stochastic transmission strategy which they compared to broadcast scheduling in the context of an alarm network. They addressed the question of how a network of nodes might signal the occurrence of an event capable of disabling the sensors. The approach called for the nodes to exchange messages regularly during normal operation, but to signal the occurrence of an alarm event by ceasing to transmit.

In the work we present in this paper, we consider in detail the merit of such stochastic scheduling approaches for underwater sensor network applications.

## 3 Network Model

We model the multi-hop communication links available between the network nodes at any instant in time as a directed graph $G = (V, E)$ in which each vertex $v \in V$ represents a network node and each edge $e_{ij} \in E$ denotes a potential communication link from node $i$ to node $j$, i.e., node $i$ can transmit data to node $j$ if and only if $e_{ij} \in E$ in a selected channel.

We make the following assumptions on data communication:

- A node that is transmitting may not receive at the same time. If a node is tuned to receive on a channel $m$, then a packet can be received if and only if exactly one of its neighbors is transmitting on that channel. This constraint provides a simple way to model collision issues such as the hidden terminal problem.

- Time is slotted, and at the beginning of each time slot, a node selects a channel $m$ at random (e.g., uniformly). It then transmits on channel $m$ with a given probability which is determined according to various performance goals. If the node does not transmit, then it tunes its acoustic transceiver to receive on channel $m$.
- All nodes maintain synchronized clocks and may select to time their communications to occur during a particular slot. Note that this assumption is common, and there are a number of techniques that could be used to accomplish this task; see Syed and Heidemann [18] for an example of a time synchronization method appropriate for acoustic networks, and see Sivrikaya and Yener [16] for a more general survey of time synchronization techniques in wireless sensor networks.

We will refer to this approach as *Stochastic Scheduling*.

# 4 Stochastic Scheduling on A Single Channel

In this section, we analyze the single channel case. Rather than handling the collision issue by an assignment of deterministic schedules, instead we propose to assign to each node in the network a time slot transmission probability. Thus we want to specify a set of appropriate values $P = \{p_i\}, \forall i \in V$. Since the goal of our analysis will be to obtain good heuristics that can be used to design simple and distributed scheduling, we ignore (at first) the propagation delay to ease the analysis; later, in our simulation study, we evaluate the impact of propagation delay.

## 4.1 Basic Constraints and General Guidelines

As a preliminary, we consider the impact of $P$ on the probability of one node communicating with another. To this end, we define a throughput graph corresponding to a given network.

**Definition 1** The throughput graph of a given network $G = (V, E)$ is a weighted, directed graph, denoted by $G' = (V, E, R)$, where $R$ denotes the set of weights $r_{ij}$ on the corresponding edges $e_{ij}$. The weight $r_{ij}$ of an edge $e_{ij}$ corresponds to the probability that node $j$ receives a message from a neighbouring node $i$ during a given time slot.

We call $G'$ the throughput graph because the weight assigned to the directed edge $e_{ij}$ is proportional to the amount of data across that link in a long run. Based on the second assumption in the network model in Section 3, it is easy to obtain:

$$r_{ij} = p_i(1 - p_j) \prod_{k \in N(j), k \neq i} (1 - p_k), e_{ij} \in E \quad (1)$$

where $N(x)$ denotes the neighbours of $x$ in $G$.

Equation (1) captures the basic constraint on the value assignment in $P$. The impact of this constraint is illustrated in Figure 1. In particular, if a node's time slot transmission probability is increased, the long-term throughput from this node to its neighboring nodes will be increased, which may lead to lower transmission opportunities at the neighbours.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Example graph showing the influence of $p_i$. If $p_i$ is adjusted upwards, then the throughput across links $(i, j_1)$ and $(i, j_2)$ will be increased, while that of the links $(j_1, i)$, $(j_2, i)$, $(k_1, j_2)$, $(k_2, j_2)$ and $(k_3, j_2)$ will be decreased.</figcaption></figure>

## 4.2 An Objective Function for the Assignment of P Values

We define a natural objective function, $Q_r$ and show how to use it to assign P values.

**Definition 2** We define the overall reliability $Q_r$ of network $G = (V, E)$ as a function evaluated over the corresponding throughput graph $G' = (V, E, R)$:

$$Q_r = \prod_{r_{ij} \in R} r_{ij}. \qquad (2)$$

We call $Q_r$ the overall network reliability, because in the long run $Q_r$ represents the chance that a data packet could be successfully routed along an arbitrary path $q$ in $|q|$ time slots, where $|q|$ is the length of the path.

## 4.3 Maximizing Overall Network Reliability

We will now show how to assign the values in $P = \{p_i\}, \forall i \in V$, to maximize the overall network reliability $Q_r$. Since $Q_r$ is a function of $P$, we rewrite it as: $Q_r(P) = \prod_{i,j \in R} r_{ij}$. By taking the log of both sides we get:

$$Q'_r(P) = \sum_{i,j \in R} \log r_{ji},$$

where $Q'_r(P) = \log Q_r(P)$.

Now we would like to find the values of $P$ that maximize $Q'_r$. We proceed by considering the partial derivatives of $Q'_r$ with respect to the value of $p_i \in P$:

$$\nabla Q'_r = \left( \frac{\partial Q'_r}{\partial p_1}, \frac{\partial Q'_r}{\partial p_2}, \dots, \frac{\partial Q'_r}{\partial p_n} \right)$$

where $n = |V|$. A single partial then becomes:

$$\frac{\partial Q'_r}{\partial p_i} = \sum_{e_{ij} \in E} \frac{1}{r_{ij}} \frac{\partial r_{ij}}{\partial p_i}. \qquad (3)$$

The partials for $p_i$ are only non-zero, however, for $r_{ij}, j \in N(i)$ and $r_{ji}, j \in N(i)$ and $r_{kj}, k \in N(j), k \neq i$, based on the basic constraint in Equation (1).
We can now consider the partial of a single weight value with respect to $p_i$. In particular, for the outbound links from $i$ to $j$:

$$ \frac{\partial r_{ij}}{\partial p_i} = \frac{\partial}{\partial p_i} p_i (1 - p_j) \prod_{k \in N(j), k \neq i} (1 - p_k) = \frac{r_{ij}}{p_i} . \quad (4) $$

For the inbound links from $j$ to $i$ where $j \in N(i)$ we have:

$$ \frac{\partial r_{ji}}{\partial p_i} = \frac{\partial}{\partial p_i} (1 - p_i) p_j \prod_{k \in N(j), k \neq i} (1 - p_k) = \frac{-r_{ji}}{1 - p_i}, \quad (5) $$

and similarly, for the links from $k$ to $j$ where $k \in N(j), k \neq i$ we have:

$$ \frac{\partial r_{kj}}{\partial p_i} = \frac{\partial}{\partial p_i} (1 - p_i)(1 - p_j) \prod_{k \in N(j), k \neq i} (1 - p_k) = \frac{-r_{kj}}{1 - p_i} . \quad (6) $$

Let us denote the set of links for which there exists a non-zero partial with respect to $p_i$ as $R_i$. This set can be described as all links that have their tail endpoints adjacent either to the vertex $i$ or to one of its neighbours: $R_i = \{r_{kl}\}, k \in \{N(i) \cup \{i\}\}$.

We can further categorize the directed links affected by $p_i$ into those with a positive partial derivative: $R_{i+} = \{r_{kl}\}, k \in N(i)$, and those with a negative partial derivative: $R_{i-} = R_i \setminus R_{i+}$. Let $\delta_i$ denote the degree of node $i \in V$ and let $\bar{\delta}_i$ denote the sum of the degrees of all the neighbours of $i$: $\bar{\delta}_i = \sum_{j \in N(i)} \delta_j$. It is easy to see that $|R_{i+}| = \delta_i$ and $|R_{i-}| = \bar{\delta}_i$.

Let us now return to Equation (3) and take the partial derivative of $Q'_r$ with respect to $p_i$:

$$ \begin{aligned} \frac{\partial Q'_r}{\partial p_i} &= \sum_{i,j \in R} \frac{\partial r_{ij}}{\partial p_i} \frac{1}{r_{ij}} = \sum_{i,j \in R_{i+}} \frac{\partial r_{ij}}{\partial p_i} \frac{1}{r_{ij}} + \sum_{i,j \in R_{i-}} \frac{\partial r_{ij}}{\partial p_i} \frac{1}{r_{ij}} \\ &= \sum_{i,j \in R_{i+}} \frac{r_{ij}}{p_i} \frac{1}{r_{ij}} + \sum_{i,j \in R_{i-}} \frac{-r_{ij}}{1-p_i} \frac{1}{r_{ij}} = \frac{\delta_i}{p_i} - \frac{\bar{\delta}_i}{1-p_i} . \end{aligned} \quad (7) $$

Since the partial derivative of our objective function $Q'_r$ with respect to a single $p_i$ does not depend on the other elements of $P$, we can set each partial to zero in order to find the value of each $p_i$ that will maximize $Q'_r$ and of course $Q_r$ as well: $p_i = \delta_i/(\delta_i + \bar{\delta}_i)$. If we now let $\Delta_i = \bar{\delta}_i/\delta_i$ be the *average degree of i's neighbours* we can express the above closed form result as:

$$ p_i = \frac{1}{1 + \Delta_i} . \quad (8) $$

# 5 Stochastic Scheduling on Multiple Channels

In the case where we have $M(M > 1)$ frequency channels, the value for $R$ in $G'$ will take on slightly different values. We can calculate the value of $r_{ij}$ as follows:

$$ r_{ij} = \frac{1}{M} p_i \frac{1}{M} (1 - p_j) \prod_{k \in N(j), k \neq i} (1 - \frac{1}{M} p_k), e_{ij} \in E \quad (9) $$
where $N(x)$ denotes the neighbours of $x$ in $G$. This calculation is analogous to Equation (1) for the single frequency variant.

Following the same analysis steps as in the single channel case, we arrive at the following values for $P$ that maximize overall network reliability:

$$p_i = \frac{2\delta_i M + \bar{\delta}_i - \sqrt{\bar{\delta}_i^2 + 4\delta_i M(M-1)}}{2(\delta_i + \bar{\delta}_i)} \quad (10)$$

Due to space limitations we omit the derivation.

# 6 A Distributed Algorithm for Stochastic Scheduling

The analytical results in the previous sections provide us with heuristics for for designing a simple, distributed algorithm for Stochastic Scheduling. In this section, we present a distributed algorithm that is aimed at maximizing overall network reliability. It is straightforward to assign $P$ values in a distributed manner in order to optimize overall network reliability. Equations (8) and (10) depend only on the knowledge of the local communication topology and the number of frequency channels employed. We will refer to this heuristic for assigning $p$ values as the Average Neighbourhood Degree Heuristic (ANDH).

For the single channel case we present the following distributed algorithm for selecting a suitable value of the transmission probability of an individual node:

1. During initial deployment, a default value for $p_i$ can be assigned to each node given a rough estimate of the typical network density.

2. Each node maintains a neighbour table with one entry for each of its neighbours. Each neighbour table entry includes the unique media access control (MAC) identification of the neighbour, along with the timestamp and the number of neighbours reported by that neighbour.

3. Each node exchanges neighbour count estimates with each of its neighbours, and then updates its transmission probability $p_i$ accordingly.

4. At each time slot, with probability $p_i$, on a channel selected uniformly at random, a node broadcasts its unique media access control (MAC) identification, the number of entries in its neighbour table, and any data payload.

5. If not transmitting, the node tunes its receiver to a channel selected uniformly at random, and if it receives a message, it adds the appropriate details to its neighbour table and updates its $p_i$ values according to Equation (8).

6. (Optional if the network topology changes, e.g., in a mobile environment) Entries older than a threshold $\omega$ may be discarded. In addition, the local $p_i$ value could be smoothed by using, for example, exponential averaging or a similar technique suitable for a low powered platform.

# 7 Performance Evaluation

We perform simulation studies to evaluate our Stochastic Scheduling approach. In the simulation, we build the network topology using disk graphs. The graphs are obtained by selecting points uniformly at random in a region of the plane bounded by a circle of diameter $D$ as the locations of the network nodes. An edge
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** (a) Average time from queuing a packet until its delivery (T-Lohi vs. Stochastic Scheduling using the ANDH); (b) Percentage of successful packet transmissions over all links as a function of traffic load; and (c) the same as (b) but under the condition of long propagation delay. Results were averaged over 100 trials of 100-node networks using a communication ratio $\alpha = 0.25$. Error bars depict one standard deviation.</figcaption></figure>

is then assigned between any two vertices if the pair-wise distance between their associated locations is less than a given fraction $\alpha$ of the deployment diameter $D$. Since the parameter $\alpha$ can be used to control the number of communication links of the network, we call it the *communication ratio*. We assign a delay to an edge proportional to the distance between the pairs (but rounded to a discrete value for ease of simulation). To save space, we only show performance results over a single channel.

## 7.1 Performance under Varying Load and Propagation Delay

As a general test of network performance we simulated an application in which each device, at random intervals, broadcasts a data packet to each of its neighbours. For this test, we controlled the traffic load by assigning each node a probability that a data packet is passed down to its MAC layer at the beginning of each time slot. We selected T-Lohi [17] for comparison because this protocol represents a typical example of using lightweight control packets (i.e. it uses a RTS control packet only). Our implementation of the T-Lohi algorithm is as described in ‘Algorithm 1’ of [17] using a single time slot as the duration of a contention round.

As shown in Figure 2(a), T-Lohi performs better than our Stochastic Scheduling under light traffic load, because T-Lohi employs control messages for media access. Nevertheless, our Stochastic Scheduling approach performs much better under heavy traffic load. This demonstrates that using control packets may not bring benefits for underwater acoustic communications, because the propagation delay is determined by the pair-wise distance of two communicating nodes, whose locations may be random. Such a randomness offsets the benefit of using control packets.

In Figure 2(a), in order to investigate the average transmission delay, we assumed a very large queue size to avoid buffer overflow. To further study how many packets could be delivered within a given time constraint, we changed the queue size to one so that a packet is considered undelivered, should it be passed
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** (a) Average link delay in units of time slots for networks of different node densities. Results were averaged over 100 trials of 100-node networks for each node density. (b) Mean flood time in dynamic networks for *successful floods only* and (c) fraction of broadcast floods that reached all nodes (i.e., succeeded) with broadcast scheduling. Note that all ANDH floods succeeded in all trials. Results are averaged over twenty 100-node networks generated with a communication ratio $\alpha = 0.25$. Error bars depict one standard deviation for all plots.</figcaption></figure>

down to the MAC layer when the queue is full. Figure 2(b) shows the average percentage of a node's neighbors that receive a packet sent by that node, under different traffic loads. We can also see that the performance of our Stochastic Scheduling with the ANDH outperforms T-Lohi when traffic load becomes heavy.

The results shown in Figures 2(a) and (b) were obtained by setting the propagation delay much smaller than the length of a time slot. We then increased the propagation delay considerably to further investigate its impact. In particular, we set the max propagation delay in the network to three times the length of a time slot. Figure 2(c) shows the results under this set of tests. Comparing Figure 2(b) and Figure 2(c), it can be seen that Stochastic Scheduling is almost unaffected, but the T-Lohi protocol suffers considerably. This is due to the fact that the RTS control packets used by the T-Lohi protocol may fail to reserve the channel due to propagation latency.

## 7.2 Performance under Dynamic Network Conditions

Although it can be seen that Stochastic Scheduling has some advantages over protocols that rely on handshaking under conditions such as heavy load, we also investigated how it compares to a TDMA based, deterministic scheduling approach.

For this test, we used *Hamming distance* as a metric to measure the dynamic change in the network topology. Assume that the adjacency matrix of graph $G_1 = (V_1, E_1)$ is $A_1 = [a_{ij}]$ and the adjacency matrix of graph $G_2 = (V_2, E_2)$ is $A_2 = [b_{ij}]$, where $V_1 = V_2$ and $|V_1| = |V_2| = n$. The *Hamming distance* of the two graphs is defined as $\sum_{i,j=1}^{n} (a_{ij} - b_{ij})^2$.

For the deterministic scheduling, we implemented the broadcast schedule obtained with the centralized heuristic described in [14]. Simulations suggest that Stochastic Scheduling results in a poorer average latency than a deterministic transmission schedule when static networks are considered, as shown in plots (a) and (b) of Figure 3.
To test the performance under dynamic networks, we generated networks of 100 nodes, using a communication ratio $\alpha = 0.25$. For each network, the ANDH *P* values in our Stochastic Scheduling and the deterministic broadcast schedules were determined. Then the edges of the network were changed to make it evolve to a new network, such that the Hamming distance of the two networks was larger than a given value. A global message broadcast was then simulated originating from a single node on this new network, but with transmission schedules based on the old network. We considered how long it would take for a particular piece of information from a single node to broadcast throughout the new network. Plots (b) and (c) of Figure 3 show the results of the flood simulation in which we tested the robustness of stochastic and deterministic approaches to changes in the communication network. It can be seen that although there is a lot of variability in flood times, the Stochastic Scheduling approach continues to function even if the network topology changes. The deterministic approach, on the other hand, depends on a specific topology and fails catastrophically once the underlying communication graph shifts.

To summarize, the stochastic nature of our approach makes it well suited for applications where propagation delay is long and random. For such applications, deterministic scheduling or protocols that rely on control packets to resolve medium contention may not perform well when traffic load becomes heavy.

## 8 Conclusions and Future Work

We have presented and evaluated the concept of using a lightweight variant of slotted ALOHA in conjunction with a Stochastic Scheduling approach in which network nodes transmit according to some time slot transmission probability. We have obtained a closed-form solution for the assignment of transmission probabilities that maximize overall network reliability and have presented an easily distributed algorithm for assigning these optimal values. Performance results demonstrate that even without using any control signaling, our simple Stochastic Scheduling works well for the context of UWSNs, where propagation delay is not negligible.

In future work we will extend our analysis to incorporate propagation delay (link lengths). This will involve adding a temporal aspect to our analysis beyond the scale of a single communication slot. Additionally, we plan to further investigate our approach through experiments using custom acoustic communication hardware.

*Acknowledgements:* This research was partially supported by Natural Sciences and Engineering Research Council of Canada (NSERC). We thank the anonymous reviewers for their comments. They have influenced the direction of our future work.

## References

1. Abramson, N.: Development of the alohanet. IEEE Transactions on Information Theory 31(2), 119-123 (March 1985)
2. Chlamtac, I., Kutten, S.: A spatial reuse TDMA/FDMA for mobile multi-hop radio networks. In: INFOCOM (March 1985)

3. E.C.Page, M.Stojanovic: Efficient channel-estimation-based multi-user detection for underwater acoustic CDMA systems. IEEE Journal of Oceanic Engineering 33(4), 502–512 (October 2008)

4. Fullmer, C.L., Garcia-Luna-Aceves, J.: Solutions to hidden terminal problems in wireless networks. In: SIGCOMM. pp. 39–49 (1997)

5. Kennedy, J., Gamroth, E., Bradley, C., Proctor, A.A., Heard, G.J.: Decoupled modelling and controller design for the hybrid autonomous underwater vehicle: Maco. Int. Journal of the Society for Underwater Technology 27(1), 11–21 (2007)

6. Liu, L., Zhou, S., Cui, J.: Prospects and problems of wireless communications for underwater sensor networks. Wireless Communications and Mobile Computing 8(8), 977–994 (Oct 2008)

7. Marinakis, D., Whitesides, S.: The sentinel problem for a multi-hop sensor network. In: Canadian Conference on Computer and Robot Vision. Ottawa, Canada (May 2010)

8. Molins, M., Stojanovic, M.: Slotted FAMA: A MAC protocol for underwater acoustic networks. In: IEEE Oceans'06 Conference. Singapore (2006)

9. Park, M.K., Rodoplu, V.: UWAN-MAC: An energy-efficient mac protocol for underwater acoustic wireless sensor networks. IEEE Journal of Oceanic Engineering 32(3), 710–721 (Jan 2007)

10. Partan, J., Kurose, J., Levine, B.N.: A survey of practical issues in underwater networks. ACM SIGMOBILE Mobile Computing and Communications Review 11(4), 23–33 (Oct 2007)

11. Petrioli, C., R.Petroccia, M.Stojanovic: A comparative performance evaluation of mac protocols for underwater sensor networks. In: IEEE Oceans’08 Conference. Quebec City, Canada (Sept 2008)

12. Pompili, D., Akyildiz, I.F.: Overview of networking protocols for underwater wireless communications. IEEE Communications Magazine (January 2009)

13. Pompili, D., Melodia, T., Akyildiz, I.: A distributed cdma medium access control for underwater acoustic sensor networks. In: (Med-Hoc-Net). Corfu, Greece (June 2007)

14. Ramaswami, R., Parhi, K.: Distributed scheduling of broadcasts in a radio network. In: INFOCOM. vol. 2, pp. 497–504 (April 1989)

15. Sarfraz Nawaz, Muzammil Hussain, S.W.N.T., Green, P.N.: An underwater robotic network for monitoring nuclear waste storage pools. In: 1st Int. ICST Conference on Sensor Systems and Software (SCUBE) (2009)

16. Sivrikaya, F., Yener, B.: Time synchronization in sensor networks: a survey. IEEE Network 18(4), 45–50 (July-Aug 2004)

17. Syed, A., Ye, W., Heidemann, J.: T-Lohi: A new class of MAC protocols for underwater acoustic sensor networks. In: INFOCOM. Phoenix, Arizona (April 2008)

18. Syed, A., Heidemann, J.: Time synchronization for high latency acoustic networks. In: INFOCOM. IEEE, Barcelona, Spain (April 2006)

19. Syed, A., Ye, W., Krishnamachari, B., Heidemann, J.: Understanding spatiotemporal uncertainty in medium access with ALOHA protocols. In: WUWNet. pp. 41–48. Montréal, Quebec, Canada (September 2007)

20. Tan, H.X., Seah, W.K.: Distributed cdma-based mac protocol for underwater sensor networks. In: IEEE Conf. on Local Computer Networks. pp. 26–36. Los Alamos, CA, USA (2007)

21. Zhou, Z., Peng, Z., Cui, J.: Multi-channel mac protocols for underwater acoustic sensor networks. In: (WUWNet) (Sept 2008)