Architecture In Underwater Ad Hoc Networks Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In this section, the data link layer and the network layer protocols will be explained, as a part of integral communication architecture in underwater Ad-hoc networks. As we shall see below, many of protocols used for underwater Ad-hoc networks, are the same as those used in terrestrial ad-hoc communications.

Firstly, we analyze the protocols used to access to the media and then we describe the network protocols.

3.1 Data link layer protocols

The main solutions for data link layer protocols are mainly focused on Carrier Sensing Multiple Access (CSMA or CDMA), because Frequency Division Multiple Access (FDMA) is not suitable for underwater Ad-hoc networks, due to the narrow bandwidth in underwater channels and the vulnerability of limited band systems to fading and multipath. Moreover, Time Division Multiple Access (TDMA) shows limited bandwidth efficiency because of the long time guards required in the underwater channel. There are several protocols based on CSMA or CDMA, but the most interesting are: MACA/MACAW, FAMA and UW-MAC

3.1.1 MACA and MACAW

Multiple Access Collision Avoidance MACA [15] protocol makes use of RTS, CTS, DATA and ACK sequences to operate, which have shown to be effective for underwater use, and specially in the Seaweb project [16].

MACA proceeds as follows:

Before sending a message, the transmitter sends a RTS control message ("ready to send"), containing the length of the upcoming data message. The time taken to transmit a control message (~30 bytes) is called a slot.

If the receiver hears the RTS and is not currently "deferring," it replies with a CTS control message ("clear to send"), which includes a copy of the length field from the RTS.

Any station that hears a CTS defers any transmissions for long enough to allow someone to send a data message of the specified length. This avoids colliding with the CTS sender (the receiver of the upcoming data message).

Any station that hears an RTS defers any transmissions for a single slot (long enough for the reply CTS to be received, but not long enough for the actual data message to be sent, because contention is receiver-local).

Backoff: if no CTS response is received for an RTS, the sender must retransmit the RTS. It waits an integer number of slots before retransmitting, where that integer is chosen randomly between 1 and BO, the backoff counter. BO is doubled for every retransmit, and reduced to 1 for every successful RTS-CTS pair.

MACAW (MACA for Wireless) [17] is proposed as a series of improvements to the basic MACA algorithm. First, the authors suggest a less aggressive backoff algorithm: the exponential increase/reset to 1 policy of MACA leads to large oscillations in the retransmission interval. They propose increasing BO by 1.5 after a timeout, and decreasing it by 1 after a successful RTS-CTS pair. They also arrange for the value of the backoff counter to be communicated between clients: this avoids a client with a lower backoff counter starving other clients from accessing the media. Finally, they changed the backoff counter to be per-destination, rather than a single counter: the observation here is that the backoff counter should measure congestion, and there is not a single homogeneous level of congestion in a typical wireless deployment.

Second, they propose that receivers should send an ACK to the sender after successfully receiving a data message. This is suggested because the minimum TCP retransmission timeout is relatively long (0.5 seconds at the time), so it takes a long time to recover from lost or corrupted messages. A link layer timeout can be more aggressive, because it can take advantage of knowledge of the latency of the individual link (rather than the end-to-end timeout in TCP). This isn't inconsistent with the end-to-end argument: the link-layer timeout is not necessary for the correctness of TCP; it is just a performance optimization.

Third, they propose two related techniques for allowing transmitters to avoid contention more effectively:

A DS (Data Sending) packet should be sent after a successful RTS-CTS exchange, just before the data message itself. The idea here is to explicitly announce that the RTS-CTS succeeded, so that if a pad can hear an RTS but not the CTS response, it does not attempt to transmit a message during the subsequent data transfer period. The reasoning here is subtle: as noted before, contention is only at the receiver, so one wouldn't think that a node that can hear the RTS but not the CTS should avoid transmitting. However, sending a message requires that the sender hear the CTS response (as well as the eventual ACK); therefore, if another node within range is sending, it would be pointless to also try to transmit.

Suppose that two pads A and B in different cells/cluster both want to receive rapidly, but are close enough that they contend with one another. If pad A "wins" (completes the RTS-CTS pair), and it will effectively monopolize the channel: B will be unlikely to ever send a CTS response, because to do so it would need to receive the RTS at exactly the right time (just after A has finished receiving a data message). The authors propose a fix: if a receiver hears an RTS while it is deferring any transmissions, at the end of the deferral period it replies with an RRTS ("ready for RTS") packet, prompting the sender to resend the RTS. However, the authors note that this solution is imperfect: if A is receiving data constantly, it is unlikely that B will ever hear the RTS, so it won't know to send the RRTS.

Note that the best-case performance of MACAW is actually lower than that of MACA, because the additional ACK and DS messages sent by MACAW incur overhead. However, MACAW is much more resistant to interference, and ensures much fairer allocation of the medium among different transmitters.

3.1.2 FAMA

The Floor Acquisition Multiple Access (FAMA) is another MACA based scheme that requires every transmitting station to acquire control of the floor (i.e., the wireless channel) before it actually sends any data packet [18]. Unlike MACA or MACAW, FAMA requires that collision avoidance should be performed both at the sender as well as the receiver.

In order to "acquire the floor", the sending node sends out an RTS using either non-persistent packet sensing (NPS) or non-persistent carrier sensing (NCS). The receiver responds with a CTS packet, which contains the address of the sending node. Any station overhearing this CTS packet knows about the station that has acquired the floor. The CTS packets are repeated long enough for the benefit of any hidden sender that did not register another sending node's RTS. The authors recommend the NCS variant for Ad hoc networks since it addresses the hidden terminal problem effectively.

3.1.3 UW-MAC

In [19], Pompili et al. propose a distributed Medium Access Control (MAC) protocol called UW-MAC for UW-ASNs. UW-MAC is a transmitter based on the CDMA scheme that incorporates a novel closed-loop distributed algorithm to set the optimal transmit power and code length to minimize the near-far effect. It compensates for the effect of multipath by exploiting the time diversity in the underwater channel, thus achieving high channel reuse and low number of packet retransmissions, which result in decreased battery consumption and increased network throughput.

It is shown that UW-MAC manages to simultaneously meet the three objectives in deep water communications, which are not severely affected by multipath, while in shallow water communications, which are heavily affected by multipath, UW-MAC dynamically finds the optimal trade-off among high throughput, and low access delay and energy consumption, according to the application requirements.

Main features of UW-MAC are: i) it provides a unique and flexible solution for different architectures such as static 2D deep water and 3D shallow water, and architectures with mobile AUVs; ii) it is fully distributed, since code and transmit power are distributive selected by each sender without relying on a centralized entity; iii) it is intrinsically secure, since it uses chaotic codes; iv) it efficiently supports multicast transmissions, since spreading codes are decided at the transmitter side; v) it is robust against inaccurate node position and interference information caused by mobility, traffic unpredictability, and packet loss due to channel impairment.

3.2 Network layer protocols

This subsection is divided into several subsections. This division has been made, because in this way the reader can distinguish the protocols according to their performance. In Ad-hoc environments there are many routing protocols, but some of them cannot be used in underwater situations because they require other elements that cannot be transmitted in this underwater environment. For example, in terrestrial ad-hoc networks there are protocols based on the situation of the nodes using the GPS signal. These routing protocols cannot be used in underwater communication because the GPS signal cannot be transmitted under water. For this reason, in this subsection we have included the most important protocols in underwater communications, but still there are many more that could be used.

3.2.1 Pro-active protocols

In networks utilizing a proactive routing protocol, every node maintains one or more tables representing the entire topology of the network. These tables are updated regularly in order to maintain up-to-date routing information from each node to every other node.

To maintain the up-to-date routing information, topology information needs to be exchanged between the nodes on a regular basis, leading to relatively high overhead on the network. One the other hand, routes will always be available on request. The main disadvantages of such algorithms are:

Respective amount of data for maintenance.

Slow reaction on restructuring and failures. DSDV

The DSDV [20] is a proactive routing protocol; it is based on the Distance Vector algorithms.

Each node in the network has a routing table for each destination indicating how many hops are needed and what the next node is. The process of updating routing tables are produced by the exchange of information between nearby nodes and reapplying the shortest path algorithms with lower costs. Each path is labeled with a sequence number, which gives a time indication on the validity of that path: higher sequence numbers imply more reliable paths. When two paths have the same sequence number, it is chosen which have the lowest cost (i.e. the least number of hops to arrive to destination).

If a node notices that a path to a destination does not work, it assigns a high value of jump number (meaning infinity) and to the sequence number an odd number. A sequence number identified with an odd number indicates that this path is unreachable while on the contrary, an even number indicates that the destination itself is achievable. OLSR

OLSR [21]is a proactive routing protocol for mobile Ad hoc networks. The protocol inherits the stability of a link state algorithm and has the advantage of having routes immediately available when needed due to its proactive nature. OLSR is an optimization over the classical link state protocol, tailored for mobile Ad hoc networks.

OLSR minimizes the overhead from flooding of control traffic by using only selected nodes, called MPRs, to retransmit control messages. This technique significantly reduces the number of retransmissions required to flood a message to all nodes in the network. Secondly, OLSR requires only partial link state to be flooded in order to provide shortest path routes. The minimal set of link state information required is, that all nodes, selected as MPRs, MUST declare the links to their MPR selectors. Additional topological information, if present, MAY be utilized e.g., for redundancy purposes.

OLSR MAY optimize the reactivity to topological changes by reducing the maximum time interval for periodic control message transmission. Furthermore, as OLSR continuously maintains routes to all destinations in the network, the protocol is beneficial for traffic patterns where a large subset of nodes are communicating with another large subset of nodes, and where the [source, destination] pairs are changing over time. The protocol is particularly suited for large and dense networks, as the optimization done using MPRs works well in this context. The larger and more dense a network, the more optimization can be achieved as compared to the classic link state algorithm. TBRPF

Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) is a proactive link-state routing protocol [22] designed for Mobile Ad-hoc Networks (MANETs), which provides hop-by-hop routing along shortest paths to each destination. Each node running TBRPF computes a source tree (providing shortest paths to all reachable nodes) based on partial topology information stored in its topology table, using a modification of Dijkstra's algorithm. To minimize overhead, each node reports only a part of its source tree to neighbors.

TBRPF uses a combination of periodic and differential updates to keep all neighbors informed of the reported part of its source tree. Each node also has the option to report addition topology information (up to the full topology), to provide improved robustness in highly mobile networks.

TBRPF performs neighbor discovery using "differential" HELLO messages which report only changes in the status of neighbors. This results in HELLO messages that are much smaller than those of other link-state routing protocols such as OSPF [6].

TBRPF consists of two modules: the neighbor discovery module and the routing module (which performs topology discovery and route computation).

The TBRPF Neighbor Discovery (TND) protocol allows each node i to quickly detect the neighbor nodes j such that a bidirectional link (I,J) exists between an interface I of node i and an interface J of node j. The protocol also quickly detects when a bidirectional link breaks or becomes unidirectional.

Each node running TBRPF maintains a source tree, denoted T, which provides shortest paths to all reachable nodes. Each node computes and updates its source tree based on partial topology information stored in its topology table, using a modification of Dijkstra's algorithm. To minimize overhead, each node reports only part of its source tree to neighbors. WRP

The Wireless Routing Protocol (WRP) [23] is a proactive unicast routing protocol for MANETs. WRP uses an enhanced version of the distance-vector routing protocol, which uses the Bellman-Ford algorithm to calculate paths.

WRP, similar to DSDV, inherits the properties of the distributed Bellman-Ford algorithm. In this protocol, each mobile host, this is a specialized router that periodically advertises its view of the interconnection topology with other mobile hosts within the network to maintain up to date information about the status of the network. Unfortunately, in DSDV a node has to wait until it receives the next update message originated by the destination in order to update its distance-table entry for that destination. This implicit destination-centered synchronization users from the same latency problems of DUAL and similar algorithms based on explicit synchronization. Also, DSDV uses both periodic and triggered updates for updating routing information, which could cause excessive communication overhead.

This protocol relies on the exchange of short control packets forming a query-reply process. It also has the ability to maintain multiple paths to a given destination. This is a destination-oriented protocol in which separate versions of the algorithm run independently for each destination. Routing is source-initiated, which means that routes are maintained by those sources which actually desire routes. Even though this algorithm provides multiple paths to the destination, because of the query-based synchronization approach to achieve loop-free paths, the communication complexity could be high.

It differs from DSDV in table maintenance and in the update procedures. While DSDV maintains only one topology table, WRP uses a set of tables to maintain more accurate information. The tables that are maintained by a node are the following: distance table (DT), routing table (RT), link cost table (LCT), and a message retransmission list (MRL).

3.2.2 Reactive protocols

Unlike proactive routing protocols, reactive routing protocols do not make the nodes initiate a route discovery process until a route to a destination is required. This leads to higher latency than with proactive protocols, but lower overhead. The main disadvantages of such algorithms are:

High latency time in route finding.

Excessive flooding can lead to network clogging. AODV

The Ad hoc On-Demand Distance Vector (AODV) [24] algorithm enables dynamic, self-starting, multihop routing between participating mobile nodes wishing to establish and maintain an ad hoc network. AODV allows mobile nodes to obtain routes quickly for new destinations, and does not require nodes to maintain routes to destinations that are not in active communication. AODV allows mobile nodes to respond to link breakages and changes in network topology in a timely manner. The operation of AODV is loop-free, and by avoiding the Bellman-Ford "counting to infinity" problem offers quick convergence when the Ad-hoc network topology changes (typically, when a node moves in the network). When links break, AODV causes the affected set of nodes to be notified so that they are able to invalidate the routes using the lost link.

One distinguishing feature of AODV is its use of a destination sequence number for each route entry. The destination sequence number is created by the destination to be included along with any route information it sends to requesting nodes. Using destination sequence numbers ensures loop freedom and is simple to program. Given the choice between two routes to a destination, a requesting node is required to select the one with the greatest sequence number.

Route Requests (RREQs), Route Replies (RREPs), and Route Errors (RERRs) are the message types defined by AODV. These message types are received via UDP, and normal IP header processing applies. So, for instance, the requesting node is expected to use its IP address as the Originator IP address for the messages. For broadcast messages, the IP limited broadcast address ( is used.

As long as the endpoints of a communication connection have valid routes to each other, AODV does not play any role. When a route to a new destination is needed, the node broadcasts a RREQ to find a route to the destination. A route can be determined when the RREQ reaches either the destination itself, or an intermediate node with a 'fresh enough' route to the destination. A 'fresh enough' route is a valid route entry for the destination whose associated sequence number is at least as great as that contained in the RREQ. The route is made available by unicasting a RREP back to the origination of the RREQ. Each node receiving the request caches a route back to the originator of the request, so that the RREP can be unicast from the destination along a path to that originator, or likewise from any intermediate node that is able to satisfy the request. DSR

The Dynamic Source Routing protocol (DSR) [25] is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes. Using DSR, the network is completely self-organizing and self-configuring, requiring no existing network infrastructure or administration.

Network nodes cooperate to forward packets for each other to allow communication over multiple "hops" between nodes not directly within wireless transmission range of one another. As nodes in the network move about or join or leave the network, and as wireless transmission conditions such as sources of interference change, all routing is automatically determined and maintained by the DSR routing protocol. Since the number or sequence of intermediate hops needed to reach any destination may change at any time, the resulting network topology may be quite rich and rapidly changing.

In designing DSR, we sought to create a routing protocol that had very low overhead yet been able to react very quickly to changes in the network. The DSR protocol provides highly reactive service in order to help ensure successful delivery of data packets in spite of node movement or other changes in network conditions.

The DSR protocol is composed of two main mechanisms that work together to allow the discovery and maintenance of source routes in the ad hoc network:

Route Discovery is the mechanism by which a node S wishing to send a packet to a destination node D obtains a source route to D. Route Discovery is used only when S attempts to send a packet to D and does not already know a route to D.

Route Maintenance is the mechanism by which node S is able to detect, while using a source route to D, if the network topology has changed such that it can no longer use its route to D because a link along the route no longer works. When Route Maintenance indicates a source route is broken, S can attempt to use any other route it happens to know to D, or it can invoke Route Discovery again to find a new route for subsequent packets to D. Route Maintenance for this route is used only when S is actually sending packets to D.

In DSR, Route Discovery and Route Maintenance each operate entirely "on demand". In particular, unlike other protocols, DSR requires no periodic packets of any kind at any layer within the network. For example, DSR does not use any periodic routing advertisement, link status sensing, or neighbor detection packets and does not rely on these functions from any underlying protocols in the network. This entirely on-demand behavior and lack of periodic activity allows the number of overhead packets caused by DSR to scale all the way down to zero, when all nodes are approximately stationary with respect to each other and all routes needed for current communication have already been discovered. As nodes begin to move more or as communication patterns change, the routing packet overhead of DSR automatically scales to only what is needed to track the routes currently in use. Network topology changes not affecting routes currently in use are ignored and do not cause reaction from the protocol. DYMO

The Dynamic MANET On-demand (DYMO) [26] routing protocol enables reactive, multihop unicast routing among participating DYMO routers. The basic operations of the DYMO protocol are route discovery and route maintenance.

During route discovery, the originator's DYMO router initiates dissemination of a Route Request (RREQ) throughout the network to find a route to the target's DYMO router. During this hop-by-hop dissemination process, each intermediate DYMO router records a route to the originator. When the target's DYMO router receives the RREQ, it responds with a Route Reply (RREP) sent hop-by-hop toward the originator. Each intermediate DYMO router that receives the RREP creates a route to the target, and then the RREP is unicast hop by hop toward the originator. When the originator's DYMO router receives the RREP, routes have then been established between the originating DYMO router and the target DYMO router in both directions.

Route maintenance consists of two operations. In order to preserve routes in use, DYMO routers extend route lifetimes upon successfully forwarding a packet. In order to react to changes in the network topology, DYMO routers monitor routes over which traffic is flowing.

When a data packet is received for forwarding and a route for the destination is not known or the route is broken, then the DYMO router of the source of the packet is notified. A Route Error (RERR) is sent toward the packet source to indicate the route to that particular destination is invalid or missing. When the source's DYMO router receives the RERR, it deletes the route. If this source's DYMO router later receives a packet for forwarding to the same destination, it will need to perform route discovery again for that destination.

DYMO uses sequence numbers to ensure loop freedom. Sequence numbers enable DYMO routers to determine the temporal order of DYMO route discovery messages, thereby avoiding use of stale routing information.