Pr Pr Rami Langar

Ait Nadjib

Pr Saadi

Houda

Amira Mehaouech

Mariem Chadia Zayene

El Afrit

Mounira

Keywords: UnderWater Acoustic Sensor Networks (UW-ASNs), sink hole problem, collision avoidance, energy eciency, multichannel communication, grid virtual partition, slot assignment, channel allocation, quorum system

UnderWater Acoustic Sensor Networks (UW-ASNs) are the newest technological achievement in terms of communication. Composed of a set of communicating underwater sensors, UW-ASNs are intended to observe and explore lakes, rivers, seas and oceans. Recently, they have been subject to a special attention due to their great potential in terms of promising applications in various domains (military, environmental, scientic...) and to the new scientic issues they raise. A great challenging issue in UW-ASNs is the fast energy depletion since high power is needed for acoustic communication while sensors battery budget is limited. Hence, energy-ecient networking protocols are of a paramount importance to make judicious use of the available energy budget while considering the distinguishing underwater environment characteristics. In this context, this thesis aims at studying the main challenging underwater acoustic sensors characteristics to design energy-ecient communication protocols specically at the routing and MAC layers. 5 each pair of communicating nodes will have at their disposal a unique 2-hop conict free data channel. Compared with existing MAC protocol, MC-UWMAC reduces experienced collisions and improves network throughput while minimizing energy consumption.

First, we address the problem of energy holes in UW-ASNs. The sink-hole problem occurs when the closest nodes to sink drain their energy faster due to their heavier load. Indeed, those sensors especially the ones that are 1-hop away from the static sink act as relays to it on behalf of all other sensors, thus suering from severe energy depletion. In particular, at the routing layer, we propose to distribute the transmission load at each sensor among several potential neighbors, assuming that sensors can adjust their communication range among two levels when they send or forward data. Specically, we determine for each sensor the set of next hops with the associated load weights that lead to a fair energy depletion among all sensors in the network. Then, we extend our balanced routing strategy by assuming that each sensor node is not only able to adjust its transmission power to 2 levels but eventually up to n levels where n > 2. Consequently, at the routing layer, for each possible value of n, we determine for each sensor the set of possible next hops with the associated load weights that lead to a fair energy consumption among all sensors in the network. Moreover, we derive the optimal number of transmission powers n that balances the energy consumption among all sensors for each network conguration. In addition to that, it is worth pointing out that our extended routing protocol uses a more realistic time varying channel model that takes into account most of the fundamental characteristics of the underwater acoustic propagation. Analytical results show that further energy saving is achieved by our extended routing scheme.

Second, to mitigate the dramatic collision impacts, we design a collision avoidance energy ecient multichannel MAC protocol (MC-UWMAC) for UW-ASNs. MC-UWMAC operates on single slotted control and a set of equal-bandwidth data channels. Control channel slots are dedicated to RTS/CTS handshaking allowing a communicating node pair to agree on the start time of communication on a pre-allocated data channel.

In this thesis, we propose two novel coupled slot assignment and data channels allocation procedures without requiring any extra negotiation overhead. Accordingly, each node can initiate RTS/CTS exchange only at its assigned slot calculated using a slot allocation procedure based on a grid virtual partition of the deployment area. Moreover, for each communicating pair of nodes, one data channel is allocated using a channel allocation procedure based on our newly designed concept of singleton-intersecting quorum. Accordingly,

Introduction

The underwater world is a fascinating and mysterious area. Throughout history, men have posed many questions to better know and understand the underwater universe. However, some areas remain virtually inaccessible to men. Meanwhile, some companies as well as competent enterprises in the eld of automatic than in shipbuilding, have taken the idea of drone aircraft to accommodate the submarines. Thus, the underwater sensor and underwater vehicle are born. These devices, having the ability to do what other submarines could not do and go where they could not go, help men to explore and discover the underwater world [START_REF] Lurton | Acoustique sous-marine: Présentation et applications[END_REF]. Advocated initially for military applications, the use of underwater sensors is generalized to other applications such as environmental monitoring, disaster prevention, tactical surveillance, assisted navigation and scientic applications [START_REF] Akyildiz | Underwater acoustic sensor networks: Research challenges[END_REF]3]. Basically, a group of multiple underwater vehicle (unmanned or autonomous underwater vehicle) equipped with underwater sensor, are deployed within a two or three dimensional acoustic communication architecture allowing them collecting information from the targeted underwater area in a collaborative manner, forming thereby an underwater sensor network, which is interfaced with a surface station through a relaying underwater vehicle, called sink [START_REF] Akyildiz | Underwater acoustic sensor networks: Research challenges[END_REF]. Despite the severe limitations imposed by the nature of environment (attenuation, multipath, noise,. . . ) and the articial constraints (vessel noise), acoustic communication is widely used in underwater networks. Today, acoustic waves can be argued that they play in the ocean the same role that radio and optical waves play in the atmosphere and in space [START_REF] Lurton | Acoustique sous-marine: Présentation et applications[END_REF].

Similarly to the terrestrial wireless sensor networks (WSNs), increasing the network lifetime is highly required in UnderWater Acoustic Sensor Networks (UW-ASNs) so as to avoid failure of monitoring missions due to the faster energy depletion of sensors. Evidently, underwater sensors cannot use renewable energy like solar energy to recharge the batteries, and as sensors are habitually sparse and deployed in a harsh area, it is dicult and costly to replace the batteries or to replace sensor itself. The only way to improve network performance and to enhance its lifespan is by the use of energy ecient communication protocols for an ecient use of the initial battery energy budget [START_REF] Akyildiz | Underwater acoustic sensor networks: Research challenges[END_REF]. Although all the intensive work on energy eciency in WSNs, the fundamental dierences between the terrestrial and underwater environment impose the design of new protocols especially tailored for underwater networks that consider the harsh and distinguishing underwater environment characteristics [START_REF] Akyildiz | Underwater acoustic sensor networks: Research challenges[END_REF]. In this thesis, we rst aim at exploring the acoustic channel propagation properties and designing in a second stage energy-ecient networking (routing and MAC) protocols that make judicious use of the energy budget to avoid, mainly, the energy sink hole problem at the routing and to mitigate collisions impacts at the MAC layer. Thus, the network performance is enhanced, while taking into consideration the unique underwater acoustic characteristics. This Chapter introduces the fundamental key aspects of underwater acoustic sensor networks and acoustic communications, and presents the main challenges inherent to the underwater environment that face the development of 1 Introduction 12 ecient networking solutions. The problem statement is detailed in section 2. Then, in section 3, we discuss our research directions and contributions. Finally, we present the thesis organization.

Generalities on UW-ASNs

UnderWater Acoustic Sensor Networks (UW-ASNs) are typically a set of underwater vehicle, equipped with underwater sensor, which are deployed in the targeted area to collect scientic data as the quality of water, temperature, acidity and conductivity. Designed as an embedded system, an underwater sensor, in addition to its original sensing function, incorporates means for processing, communication and power supply (see internal architecture of an underwater sensor in Fig. 1.1). Unlike terrestrial sensor, an underwater sensor is more expensive due to its complicated hardware. Consequently, underwater sensors cannot be densely deployed and hence are usually sparse and distant. Moreover, the propagation speed for an acoustic link is 1500 meters/sec, 2 × 10 5 times lower than the speed of a radio link. This means that the propagation delay is 2 × 10 5 times longer for an acoustic link. In addition to that, the available bandwidth is highly limited. Indeed, inuenced by harsh environment such as transmission loss, noise, and high propagation delay, the available bandwidth is severely limited.

The most striking dierence between terrestrial and underwater sensor is the energy consumption. Indeed, an underwater sensor needs much more energy than terrestrial sensor because of the high energy expense in acoustic communication. In fact, in acoustic links, the transmit power is not only too high but also dominates the receive power. In fact, the transmit power is typically 100 times more than the receive power. For example, in WHOI Micro-Modem, the transmit power is 10 W which is 125 times of the receive power (80 mW). In addition to that, as mentioned earlier, batteries of underwater sensors are not only energy constrained but most importantly cannot be easily recharged, since for instance solar energy cannot be exploited.

Once an Underwater Acoustic Sensor Network is deployed, collected data are thereby processed, aggregated and communicated by collaborative multihop communication architecture to the collection node, called sink, which in turn reorganizes data and relays them to the surface station. UW-ASNs can interface with the external world through one or more sinks, in accordance with the deployment architecture. Deployment architectures for UW-ASNs can be of two or three dimensions [START_REF] Akyildiz | Underwater acoustic sensor networks: Research challenges[END_REF] where underwater sensors may be randomly scattered or attached either to docks, or to anchored buoys or simply moored to the seaoor. Note that by deploying attached underwater sensors, the topology in this case is considered static for long durations. That being said, it is worth pointing out that even by deploying attached sensors and depending on the target area location (shallow or deep

water), sensors positions may temporarily vary due to water dynamics (currents, surface waves or undersea species movements). Alternatively, underwater sensors may be enabled with the possibility to adjust their position. Indeed, underwater sensors may be attached to low-power gliders or unpowered drifters, or carried by an underwater vehicle that is an unmanned system with more or less complicated mechanism allowing its diving and free moving in water, dening therefore, a self-adjusted or mobile networks [4,[START_REF] Han | A survey on deployment algorithms in underwater acoustic sensor networks[END_REF][START_REF] Zeng | A survey on sensor deployment in underwater sensor networks[END_REF].

Applications

Employing networks in the water was recorded long ago, but their eective use is fairly recent, as the rst viable practical achievements have emerged in the early twentieth century, when changing technology has allowed. Since then, their applications went on expanding, and we can say that the underwater acoustic sensor networks can now provide in the ocean most of the role of terrestrial wireless sensor networks (but with less performance).

Applications of underwater networks may be categorized based on its domains [3] :

• Military applications: In such applications, UW-ASNs are mainly deployed to detect and locate obstacles or targets, which is the primary function of sonar systems, especially for military applications hunting submarines and mines, but also shing;

• Environmental applications: In this case, UW-ASNs measure either the characteristics of the various components of the marine environment (bottom topography, living organisms, currents and hydrological structures ...), or the position and the speed of an underwater mobile;

• Scientic applications: In such applications, UW-ASNs transmit signals that can be acquired by underwater scientic equipment, messages between submarines and surface ships, or commands to remotely operating systems.

• Underwater exploration: In this case, UW-ASNs are conceived to discover oil eld or reservoirs, determine routes for laying undersea cables, and assist in exploration for valuable minerals.

• Surveillance and disaster prevention: In such applications, underwater sensors can monitor areas for surveillance, reconnaissance, targeting and intrusion detection.

UW-ASNs is used to measure seismic activity to provide tsunami warnings or study the eects of submarine earthquakes.

Underwater Communications

For reliable communication, an underwater sensor should be eciently connected to a well established and deployed UW-ASN in order to deliver collected data by collaborative multihop communication architecture to the sink node. Hence, achieving a reliable and energy ecient communication is crucial since it also allows the successful reception of commands from sink or other submarines.

To achieve such objective, acoustic communication is the most suitable physical layer technology for underwater networks. Indeed, electromagnetic waves propagate through conductive salty water only at very short range due to the high attenuation and absorption eect in underwater environment. Optical waves do not suer from such high attenuation but are aected by scattering. Thus links in underwater networks are usually based on acoustic wireless communications, which are considered as the most suitable waves to wirelessly convey data in underwater environment due to their ease of propagation. However, the harsh and variable characteristics of the underwater environment are not without repercussion on the propagation of acoustic signals. Indeed, they are mainly inuenced

by path loss, ambient noise, multipath, propagation delay, and Doppler eect. Such harsh features will pose unique challenges [START_REF] Lurton | Acoustique sous-marine: Présentation et applications[END_REF][START_REF] Akyildiz | Underwater acoustic sensor networks: Research challenges[END_REF]3] such as

• The available bandwidth is extremely limited;

• The underwater channel is severely impaired, especially due to multi-path and fading;

• Propagation delay in underwater is ve orders of magnitude higher than in radio frequency (RF) terrestrial channels, and extremely variable;

• High bit error rates and temporary losses of connectivity (shadow zones) can be experienced, due to ths characteristics of the underwater channel.

In literature, numerous studies [START_REF] Jornet | Focused beam routing protocol for underwater acoustic networks[END_REF][START_REF] Stojanovic | On the relationship between capacity and distance in an underwater acoustic communication channel[END_REF][START_REF] Stojanovic | Underwater acoustic communication channels: Propagation models and statistical characterization[END_REF][START_REF] Qarabaqi | Statistical characterization and computationally efcient modeling of a class of underwater acoustic communication channels[END_REF] have been conducted to model the underwater acoustic channel features and characteristics. Despite the complexity of the physical reality of the acoustic channel, these models, using appropriate analytical tools, succeed to approach the real network behavior, helping the research community to predict the overall performance of networking protocols, to determine relevant guidelines for the selection of modulation as well as the validation of the newly designed solutions. Indeed, adopting a well dened acoustic channel, when conceiving networking protocols, can greatly increase its practical application in real world. Otherwise, without taking into consideration the unique characteristics of underwater channel, the designed protocols will fail to meet the application requirement and adapt the specic characteristics of the network and its deployment area. Consequently, networking protocols for wireless sensor networks (WSNs)

would not function well in UW-ASNs, unless wholly upgraded and supported by new capabilities that consider the underwater environment distinguishing characteristics.

Problem statement

Due to the peculiar underwater environment, acoustic communications consume larger amount of power compared to the terrestrial radio ones. However, battery budget of underwater sensors is not only limited but most importantly cannot be recharged, since solar energy cannot be exploited in underwater deployment area. This dissertation aims at designing energy ecient protocols which make judicious use of the available energy budget to prevent in rst place the main sources of energy waste such as the sink hole problem. In fact, in UW-ASNs typically as in WSNs, all collected data should be relayed to the sink, the central gathering point. They are routed from the source node to another node, hop by hop, till reaching the sink. Consequently, the closest sensors to the sink are extensively solicited since they act as relay on behalf of all other sensors, since all collected data are relayed through them. Thus, those nodes especially direct neighbors of the sink will deplete their limited energy much faster and die much earlier than the other nodes, creating a hole around the sink. Consequently, the sink will be isolated and the network will be split into disconnected subnets. It is worthless that sensors continue to collect data since they cannot deliver data to the gathering point; hence the entire network becomes useless. This phenomena is named sink hole problem and is hardly avoidable especially in static always on and energy constrained networks. In this thesis, we aim at proposing energy ecient routing protocols to avoid the sink hole problem which drastically aects the network performance.

Another important obstacle which consumes signicant energy in sensor networks is collisions. Indeed, collisions prevent packets from reaching their destination, which decreases dramatically the network throughput. In UW-ASNs, collisions are more serious and even have worse impact since retransmissions are time and energy consuming tasks.

In fact, in underwater UW-ASNs, transmission consumes much more energy compared

with terrestrial and it dominates the receive power. The transmit power is typically 100 times more than the receive power. In WHOI Micro-Modem, the transmit power is 10 W which is 125 times of the receive power (80 mW). Moreover, the propagation speed for an acoustic link is 1500 meters/sec, 2 × 10 5 times lower than the speed of a radio link. This means that the propagation delay is 2 × 10 5 times longer for an acoustic link.

In literature, several earlier solutions were proposed to avoid sink hole problem and mitigate collisions impacts in WSNs. However, due to the peculiar properties of the underwater environment, solutions need to be especially tailored for the underwater communication channel characteristics. Thus, when designing underwater protocols, it is essential to carefully take into consideration the main challenging characteristics of the underwater environment. [START_REF] Partan | A survey of practical issues in underwater networks[END_REF][START_REF] Heideman | Research challenges and applications for underwater sensor networking[END_REF]3] 1

.3 Research objectives and contributions

This thesis aims at studying the major challenging underwater acoustic sensor characteristics, analyzing its impact on networking solutions and conceiving energy ecient communication protocols especially tailored for UW-ASNs. Our main contributions revolve mainly around two axes: Data Link Layer and Network Layer and are as follows:

First, we tackle the sink hole problem and propose a balanced routing design for avoiding energy holes in UW-ASNs [START_REF] Zidi | Routing design avoiding energy holes in uw-asns[END_REF]. Our ultimate aim is to balance the energy consumption among all underwater sensors that are manually deployed according to a well dened deployment pattern. Our balanced routing solution dictates that each underwater sensor can tune its transmission range among two possible levels n = 2. Each transmission range allows the sensor to reach a specied next hop. We strive for deriving the optimal load weight for each possible range that leads to fair energy consumption among all sensors in the network and hence avoiding the sink-hole problem. Our proposed routing scheme is especially tailored for the underwater environment and takes into consideration the unique characteristics of the underwater channel such as attenuation, noise and the dependence of usable bandwidth and transmit power on distance.

Second, still dealing with the sink hole problem, we extend our previous work by conducting an in-depth analysis of the impact of a time-varying underwater acoustic environment on the proposed balanced routing strategy [START_REF] Bouabdallah | Joint routing and energy management in underwater acoustic sensor networks[END_REF]. We analytically reformulate the problem by introducing the link success probability to further take into consideration the network dynamism and the time variability of the underwater acoustic channel. Moreover, and as another main contribution of this extended work, we suppose that underwater sensor can adjust their transmission power not only up to 2 levels but mainly up to n levels where n is arbitrary and can be greater than 2. Accordingly, the trac load will be more distributed among more sensors toward the sink. We show that increasing the transmission power levels increases the energy consumption but at the same time leads to a more balanced trac load distribution which will lead to a uniform and smooth energy depletion among nodes in the whole networks. Thus we strive for determining the optimal number of transmission power levels that leads to a fair energy depletion through the networks and hence the sink hole problem is overcome to the most possible extent.

Finally, working on the MAC layer, we propose a collision avoidance energy ecient multichannel MAC protocol (MC-UWMAC) for UW-ASNs [START_REF] Zidi | Mc-uwmac: A multi-channel mac protocol for underwater sensor networks[END_REF]. MC-UWMAC operates on a single slotted control channel to avoid the missing receiver problem and multiple data channels to improve the network throughput. To guarantee to the most possible extent a collision free communication, MC-UWMAC uses two key newly designed procedures: i) a grid based slot assignment procedure on the common slotted control channel that approaches the 2-hop conict free slot assignment and ii) a quorum based data channel allocation procedure. More precisely, according to MC-UWMAC, a sender uses its own dedicated slot on the common control channel for handshaking with an intended neighbor receiver. However, data transmission takes place in a unique data channel especially reserved for this pair of neighbor nodes. In fact, MC-UWMAC reserves for each pair of neighbor nodes a unique data channel that aims at being 2-hop conict free. As such, the probability of collision is highly reduced and even completely mitigated in some scenarios.

In addition to that, by using multiple channels, MC-UWMAC allows multiple data communications along with handshaking on the common control channel to take place at the same time and hence the network throughput as well as the energy eciency is improved.

Simulation results show that MC-UWMAC can greatly improve the network performance especially in terms of energy consumption, throughput and end-to-end delay.

Organization of the thesis

The remainder of this thesis is organized as follows:

In Chapter 2, we investigate existing works dealing with sink hole problem and the design of multichannel MAC protocols in WSNs and then in UW-ASNs.

In Chapter 3, we present our balanced routing strategy to avoid the sink hole problem in UW-ASNs. We prove that, using two transmission power levels n = 2, we can greatly balance the nodes energy consumption. In particular, we present our analytical problem formulation to determine the load weight of each node to be sent to each possible next hop that lead to fair energy consumption among all underwater sensors. Then, we assess the performance of our balanced routing strategy.

In Chapter 4, we present our extended proposed balanced routing design for avoiding energy holes in UW-ASNs allowing underwater nodes to tune their transmission range among several possible levels n > 2. We show that increasing n increases the energy consumption since farther nodes could be reached. Thus, we propose to determine the optimal number of transmission range levels n which minimize the energy consumption while distributing the load trac to guarantee a fair energy depletion among all nodes. Then, we show the performance of our extended proposal while considering more challenging underwater environment characteristics.

In Chapter 5, we present our multichannel MAC protocol, MC-UWMAC. The main contributions of MC-UWMAC reside behind the use of two key newly designed procedures: a grid based slot assignment procedure and a quorum based data channel allocation procedure. Then, we analyze the simulation results of our MC-UWMAC.

Finally, chapter 6 concludes the thesis and presents our future perspectives.

Chapter 2

State of the art

Motivated by the wish to provide autonomous support for several underwater applications, Underwater Acoustic Sensor Networks (UW-ASNs) have gained a remarkable momentum within the research community in the last couple of years. While extensive work has been already proposed for Wireless Sensor Networks (WSNs), the unique characteristics of the underwater channel imposes the proposal of new dedicated networking protocols for UW-ASNs. However, conceiving protocols especially tailored for UW-ASNs faces severe challenges inherent to the harsh underwater characteristics such as the high attenuation, limited bandwidth, long propagation delay, high transmission power while sensors energy budget is not only limited but also cannot be easily recharged. Thus, UW-ASNs require novel energy ecient protocols that take into account the characteristics of the underwater deployment area to meet monitoring applications requirements. In literature, considerable number of works has been conducted at the physical layer to model to some extent the reality of the physical underwater environment and represent the fundamental underwater specications. Yet, less work has been done at higher layers of the protocol stack [START_REF] Pompili | Overview of networking protocols for underwater wireless communications[END_REF], [START_REF] Climent | Underwater acoustic wireless sensor networks: Advances and future trends in physical, mac and routing layers[END_REF], [START_REF] Salma | Underwater sensor network at physical, data link and network layer -a survey[END_REF].

In this chapter, we mainly focus on reviewing previous work related to the energy sink hole problem and multichannel MAC design in UW-ASNs. We also describe works related to the sink hole problem and multichannel MAC protocols in terrestrial WSNs as a way to highlight the similarities as well as the distinguishing features with respect to UW-ASNs solutions.

Energy sink-hole problem related work

The energy sink hole problem was originally noticed in terrestrial Wireless Sensor Networks (WSNs) [START_REF] Lian | Modeling and enhancing data capacity in wireless sensor networks[END_REF], [START_REF] Wadaa | Training a sensor networks[END_REF], [START_REF] Lian | Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[END_REF], [START_REF] Olariu | Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[END_REF], [START_REF] Zhao | Analysis on strategies of alleviating energy hole problem in wireless sensor networks[END_REF], [START_REF] Jiang | Mitigation techniques for the energy hole problem in sensor networks using n-policy m/g/1 queuing models[END_REF]. Indeed, it was shown in [START_REF] Lian | Modeling and enhancing data capacity in wireless sensor networks[END_REF] that the closest sensors to the sink are prone to deplete their provided amount of energy faster than other sensors.

In fact, one of the characterizing functionality of sensor networks, is that all deployed sensors have to transmit the collected data toward the sink. Therefore, all forwarded data will imperatively pass through the sensors in the close vicinity of the sink. Thus, unlike distant sensors, the sensors in the vicinity of the sink especially the ones that are 1-hop away from the sink have signicant packet load to relay, in addition to their own collected data, which may rapidly exhaust their limited energy budget. In [START_REF] Wadaa | Training a sensor networks[END_REF], authors prove that by the time the nearest sensors drain their provided energy, distant nodes still have 93% of their initial energy. This unbalanced energy consumption is liable to drastically reduce the lifetime of the network since it causes energy holes which prevent reports from reaching the sink resulting in possible network disconnection. Due to its severe eect on the performance of the whole network, the energy sink hole problem is one of the major concern in WSNs as well as in UW-ASNs.

2 State of the art 18

Wireless Sensor Networks

In literature, many preventive researches have addressed this issue in WSNs. Their common goal is to avoid the energy hole around the sink in order to improve the network throughput and lifetime which depends on the lifetime of sink closest nodes. Accordingly, a common initial step of the analyzed solutions for the sink hole problem is the virtual partition of the network, mostly into regions or bands in order to distinguish the critical sensors (closest node to the sink) from the outer ones. However, they dier in how to deal with the problem taking into account the considered network topology and characteristics. In this thesis, we propose to classify the studied works into mainly three approaches.

According to the rst approach, protocols suggest to upgrade the network topology in order to mitigate the sink hole problem. It implicates the calculation of the number of the needed additional sensors around the sink, the adjustment of node density in dierent bands, the distribution of nodes (uniformly or non uniformly) ... For instance, authors of [START_REF] Lian | Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[END_REF] investigated how to distribute nodes in a way to increase the network throughput and balance the energy consumption of all sensors. Assuming that the monitored rectangular area was subdivided on sub areas and each area is divided on sub regions, authors calculated the number of nodes to be deployed in each sub region. Accordingly, the closer a subregion is to the sink, the higher the sensors density in the sub-region. Authors showed the eciency of the proposed model compared to the uniform distribution model since all sensors exhaust their energy almost at the same time which leads the unused energy ratio close to 0. However, the number of sub areas in their non uniform distribution of nodes is remaining not calculated arguing that the actual selection depends on the practical network environments.

In [START_REF] Wu | Avoiding energy holes in wireless sensor networks with nonuniform node distribution[END_REF], authors argued that in a circular multihop sensor network (modeled as concentric coronas) with nonuniform node distribution and constant data reporting, the unbalanced energy depletion among all the nodes in the network is unavoidable. Even if the nodes in the inner coronas of the network have used up their energy simultaneously, the ones in the outermost corona may still have unused energy. This is due to the intrinsic many-to-one trac pattern of WSNs. Thus, they proposed a novel nonuniform node distribution strategy to achieve nearly balanced energy depletion in the network. They regulated the number of nodes in each corona and derive the ratio between the node densities in the adjacent (i + 1)th and ith coronas.

Authors in [START_REF] Xu | Relay node deployment strategies in heterogeneous wireless sensor networks[END_REF] proposed two new random deployment strategies to balance the energy consumption rates of Relay Nodes (RNs) across the network, thus extending the network lifetime. However, this deployment scheme may not provide sucient connectivity to sensor nodes when the given number of RNs is relatively small. The latter reconciles the concerns of connectivity and lifetime extension. Both single-hop and multihop communication models are considered in [START_REF] Xu | Relay node deployment strategies in heterogeneous wireless sensor networks[END_REF].

In [START_REF] Mhatre | A minimum cost heterogeneous sensor network with a lifetime constraint[END_REF], authors proposed to organize the network into clusters and an aircraft visits the area to gather data from the cluster head tagged as type 1. Type 0 represents sensors that do sensing and communicate the sensed data to their cluster head. Nodes are supposed to be distributed over the area using two dimensional homogeneous Poisson point process.

Each type is characterized by its average number per unit area and its initial energy.

The cost of deployment is dened as a function of those parameters. For each type, the optimum parameters are calculated in order to guarantee the maximum lifetime of network, and minimize the cost of deployment. By doing so, authors ensure that all sensors run out of energy at about the same time. They compared the results for two kind of deployment: random and grid deployment. In both case, authors argued that the number of sensors should be about the square of the number of cluster head to mitigate the energy hole problem.

Hierarchical approach using clusters was considered as a promising method for e-ciently organizing the network and increasing the network lifetime. However, authors of [START_REF] Soro | Prolonging the lifetime of wireless sensor networks via unequal clustering[END_REF] proved that energy consumption remains unequal as clusters around static sink are more solicited especially when size of clusters are equal. So, they organize the network in accordance of an unequal clustering size model. Based on the fact that energy consumption (inter-cluster and intra-cluster) is proportional to the number of nodes within a cluster, the authors calculated the number of nodes in each cluster with respect to expected relay load, aimed at maintaining more uniform energy consumption. As the positions of the cluster heads aect the total energy consumption, clusters form Voronoi tessellations [START_REF] Okabe | Spatial Tessellations: Concepts and Applications of Voronoi Diagrams[END_REF] of the circular and layered sensor eld. Using the numbers of clusters and radius of each layer, authors formulated the number of sensors in each cluster and shows that nearest clusters to the sink should contains fewer nodes than the others.

To recapitulate, the main goal of this approach is to share the load of the 1-hop away relay sensors (in the inner band) over more nodes and provide multiple paths toward the sink. Consequently, the energy depletion is smoothly and uniformly distributed through the whole network. This approach can greatly improve the network lifetime and mitigate the sink-hole problem since the role of the sink closest nodes will be alleviated as the load will be shared by several nodes. However, by adopting such approach in UW-ASNs, there may be some problems. First, deploying additional nodes means additional expense due to the cost of underwater sensors. Second, increasing the number of nodes around the sink will probably engender the duplication of data as they monitor almost the same zone.

Finally, increasing nodes around the sink may increase the probability of simultaneous transmissions and so the collision probability, which increases the energy consumption and reduces the network throughput [28] [23].

According to the second approach, protocols employs additional nodes but mobile ones like mobile sink such that the set of closest node to the sink is constantly changing as in [START_REF] Mhatre | A minimum cost heterogeneous sensor network with a lifetime constraint[END_REF] using an aircraft. This approach includes also the use of mobile nodes to cover energy holes. For example, in [START_REF] Sahoo | Hora: A distributed coverage hole repair algorithm for wireless sensor networks[END_REF], authors addressed the sink-hole problem in mobile and dense sensor networks. They proposed a distributed coverage hole repair algorithm (HORA) that takes advantages of the nodes mobility to overcome the energy hole problem. To repair the coverage holes, mobile nodes with higher overlapping degree move towards the detected region of dead sensors without disturbing the network coverage and connectivity.

Accordingly, each node maintain a neighbors list to identify dead neighbors and to calculate the overlapping degree. Authors proved that the algorithm reduces considerably the energy holes and increases the network lifetime and throughput.

In [START_REF] Yadav | An agent-based solution to energy sink-hole problem in at wireless sensor networks[END_REF], authors proposed a mobile agent-based solution to overcome the energy sinkhole problem. Authors aim at reducing redundant data being passed to the nodes near to the sink thereby reducing the load and saving battery life. In [START_REF] Sharma | Data dissemination protocol for mobile sink in wireless sensor networks[END_REF], a distributed tree-based data dissemination (TEDD) protocol with mobile sink is proposed to enhance the network lifetime.

According to the third approach, the number of nodes is not changed and no additional nodes are required. In this case, studies strive for achieving a balanced energy consumption throughout the network either by adjusting the sensor's transmission powers or the sensor's initial energy... Authors in [START_REF] Guo | An energy-balanced transmission scheme for sensor networks[END_REF] proposed an energy balanced transmission scheme that balances the ratio between direct transmission to the sink and next hop transmission in order to optimize the energy consumption over the network. Nodes are deployed in a circular disk around the sink. Each node can send a percent of data directly to the sink and the rest to the next hop. Authors calculate the quantity of transmitted data in each case and showed that farthest nodes should send directly the big amount of data to the sink in order to reduce the charge of nearest nodes, avoiding therefore the formation of sink hole.

In [START_REF] Boukerche | A new energy ecient and fault-tolerant protocol for data propagation in smart dust networks using varying transmission range[END_REF], authors proposed a variable transmission range routing protocol (VTRP) to

2 State of the art 20 bypass the faulty and critical sensors problem around the sink by allowing nodes to increase their transmission range. To send data, nodes start rst by the search phase to discover a nearer sensor to the sink to be the forwarder. If no forwarder is selected, nodes enters the transmission range variation phase to modify the initial transmission range according to an increasing change-function. VTRP succeed to overcome the sink hole especially in dense sensor networks.

Authors of [START_REF] Lian | Modeling and enhancing data capacity in wireless sensor networks[END_REF] study the initial energy repartition among sensors. Since, nodes are usually deployed with the same initial energy; authors proved that 90 of energy is unused especially in farthest node. They proposed a non uniform energy repartition among nodes.

Nodes around the sink should have more energy as they relayed data from the rest of nodes. They also proposed the use of mobile sink as an alternative solution to the energy sink problem. Mobile sink collects data directly from all nodes, without any mediator.

UW-ASNs

In UW-ASNs, compared with the number of works in WSNs, few research work have targeted sink hole problem. In this section, we reviewed the most recent works that addressed mainly the sink-hole problem in UW-ASNs.

In [START_REF] Luo | Energy balanced strategies for maximizing the lifetime of sparsely deployed underwater acoustic sensor networks[END_REF], the authors. argued that linear sparsely sensor networks are the most aected by energy holes and proposed an energy balanced hybrid data propagation algorithm (EBH) based on the residual energy of nodes to mitigate the early energy depletion of sink closest nodes in sparse linear networks. Accordingly, each node uses rst multi-hop mode and transmit data to its next adjacent neighbor towards the sink. Then, node transmit data directly to the sink if its own residual energy is higher than the one of its next hop.

According to EBH, nodes should exchange control messages which contains their residual energy information. Authors proposed also a dierential initial battery assignment strategy (DIB) which employs super node to form cluster with basic nodes. Having higher battery power and longer transmit distance, super node collect data from basic nodes in its cluster and relay them to other super nodes or directly to the sink.

In [START_REF] Chen | Mobicast routing protocol for underwater sensor networks[END_REF], a power saving mobicast routing protocol for UWSNs is proposed to mitigate the energy hole problem resulting from the ocean current and non-uniform deployment of sensor nodes. The protocol relies on mobile autonomous underwater vehicle (AUV)

to collect data at dierent times from sensors within a series 3-D zone of reference (3-D ZOR) while traveling along a user-dened route. To save energy, sensors are usually in sleep mode only notied sensors by mobicast message from the AUV to deliver data. To ensure the continuity of delivery paths to the AUV and bypass the hole problem in each 3-D ZOR, the authors introduced an adaptive "apple-slicing" technique to build routing segments around the created coverage hole.

In [START_REF] Latif | On energy hole and coverage hole avoidance in underwater wireless sensor networks[END_REF], inspired by HORA [START_REF] Sahoo | Hora: A distributed coverage hole repair algorithm for wireless sensor networks[END_REF], the authors proposed a spherical hole repair technique (SHORT) to repair the coverage and energy holes problem in underwater wireless sensor networks (UWSNs). Similarly to HORA, in SHORT, higher overlapping nodes are responsible for hole reparation. Authors proposed also to use multiple transmission ranges jointly with the residual energy and depth consideration while forwarding data to sinks for further energy saving. well as in UW-ASNs. We also proposed a classication of the sink-hole problem solutions according to the basic features and the manipulated parameters. In fact, a part from solutions using mobile sink or mobile nodes, energy sink-hole solutions are either based on clusters or/and adjusting the nodes parameters such as the number, the position, the transmission power, the initial energy, ... In the same direction, but dierent from the described contributions, we present in our work a routing solution dedicated for a specic underwater acoustic network deployment where each node reports periodically its data to the sink node, which overcomes the energy holes problem by achieving a fair load distribution, balanced energy consumption, and better overall network management. In our study, we opt for adjusting the transmission power of nodes while transmitting data towards the sink. As such, each sensor node can reach multiple possible next hops in the direction of the sink using multiple transmission power levels. Such feature may greatly alter the total number of hops toward the sink and thus, moderate the end-to-end delay.

It can essentially bypass the sink closest nodes. However, in UW-ASNs, increasing the transmission power increases the energy consumption. Thus, jointly with adjusting the transmission power feature, we opt for managing the data load on individual sensor to balance the energy consumption. Accordingly, using an adjustable communication range based data forwarding, nodes are endowed with the possibility of tuning their transmission power and hence can distribute their load over the possible transmission power levels. The data load distribution among the possible transmission power levels will be proceeded in such way that balanced energy consumption is achieved among all the nodes. We strive analytically for deriving the appropriate load weight for each possible next hop such that the energy depletion is balanced among all sensors in the network. Our routing solution takes into account the unique fundamental features of the underwater environment such as frequency-dependant attenuation, bottom surface reections and Doppler eect, which highly aect energy consumption through both power and rate [START_REF] Stojanovic | On the relationship between capacity and distance in an underwater acoustic communication channel[END_REF]. We believe that the proposed balanced routing design is able to eciently overcome the energy holes problem and seems to be more eective to balance the energy consumption while still remaining practical enough for real implementation.

Multichannel MAC related work

A MAC layer protocol is of paramount importance in wireless networks since it arbitrates access to a common shared medium and thus highly impacts the overall network performance. The importance of MAC layer is even greater in UW-ASNs, due the new challenges design posed by the unique characteristics of the underwater environment [START_REF] Chen | A survey on mac protocols for underwater wireless sensor networks[END_REF]. In literature, several MAC protocols were proposed to enhance the overall network performance for WSNs as well as for UW-ASNs. In particular, it is proved [START_REF] Mo | Comparaison of multichannel mac protocols[END_REF] that parallel communication through multiple channels can eciently ameliorate network throughput and reduce end-to-end delay and energy consumption. In fact, multichannel communication scheme allows multiple simultaneous transmissions emanating from close senders, naturally contentious, to take place, thing that was impossible with the single channel scheme. Indeed, using multichannel MAC scheme, nodes within the neighborhood of each others can simultaneously and successfully transmit packets provided that they are on dierent data channels. As such, the average end-to-end delay is expected to be highly reduced which is extremely important in long delay underwater acoustic sensor networks [START_REF] Zhou | Analyzing multi-channel mac protocols for underwater acoustic sensor networks[END_REF], [START_REF] So | Multi-channel mac for ad hoc networks: Handling multi-channel hidden terminals using a single transceiver[END_REF]- [START_REF] Han | Analyzing multi-channel medium access control schemes with aloha reservation[END_REF].

That being said, several multichannel inherent issues should be addressed to design an ecient multichannel MAC protocol. In fact, equipped with one transceiver, nodes should agree on a specic channel for data communication. Traditionally, such agreement is established through a control packet exchange (handshaking) named negotiation. However, to enable such negotiation, nodes need to reside on the same channel to make a successful 2 State of the art 22 handshaking and avoid the missing receiver problem which occurs when a sender fails to get in touch with its intended receiver.

There has been a tremendous amount of research on the design of multichannel MAC protocols in Ad Hoc networks as well as in WSNs. Many surveys [START_REF] Mo | Comparaison of multichannel mac protocols[END_REF], [START_REF] Jovanovic | Multi-channel media access control for wireless sensor networks: A survey[END_REF], [START_REF] Huang | The evolution of mac protocols in wireless sensor networks: A survey[END_REF], [START_REF] Ali | A survey of mac protocols design strategies and techniques in wireless ad hoc networks[END_REF], [START_REF] Soua | Multichannel assignment protocols in wireless sensor networks: A comprehensive survey[END_REF] have been conducted to summarize and classify the varieties of multichannel MAC procedures while analyzing their advantages and disadvantages.

However, although the great number of existing multichannel MAC protocols for terrestrial networks, the dierent nature of underwater environment necessitates peculiar attention and requires the development of novel multichannel MAC protocols specially tailored for the UW-ASNs. In literature, most of the proposed MAC protocols uses single channel. Nevertheless, along with new technological advances in underwater devices, recent underwater modems [START_REF]Aquanetwork: Underwater wireless modem with networking capability[END_REF]

Single Rendezvous MultiChannel MAC protocols for UW-ASNs

In single rendezvous multichannel MAC protocols, there are one common control channel and multiple data channels. The node with outgoing packets will exchange control information over the single control channel to agree on the data channel. The major advantage of this approach is that it highly alleviate the missing receiver problem which is inherent to the multichannel communication scheme, where a potential sender may fail to get in touch with a target receiver since they reside on dierent channels.DC-MAC However, the common control channel can clearly become a bottleneck especially in dense high trac networks.

One of the rst work in single rendezvous multichannel MAC protocols for UW-ASNs is RCAMAC [START_REF] Tracy | A reservation mac for ad-hoc underwater acoustic sensor networks[END_REF]. RCAMAC is a Reservation Channel Acoustic Media Access Protocol based on RTS/CTS handshaking on a common control channel. Accordingly, the entire bandwidth is divided into two channels. One is a control channel with less bandwidth.

Another is the data channel with much more bandwidth. By doing so, the authors show that better network throughput as well as more energy eciency are achieved. CUMAC [START_REF] Zhou | Handling triple hidden terminal problems for multichannel mac in long-delay underwater sensor networks[END_REF] is a more recent example of single rendezvous approach especially conceived for underwater acoustic sensor networks. CUMAC mainly utilizes the common control channel for neighbors cooperation to rst select an available free data channel and second to detect collision with a simple tone device designed for the distributed collision notication. Although CUMAC aims at providing a collision free communication, the message exchanged to achieve such objective are energy and delay consuming in long delay high power underwater acoustic sensor networks. In [START_REF] Zhou | Analyzing multi-channel mac protocols for underwater acoustic sensor networks[END_REF], authors model and analyze two single rendezvous multichannel MAC protocols: a multichannel access with Aloha on a the dedicated channel and a multichannel access with RTS/CTS on the dedicated channel. The authors prove that RTS/CTS like channel reservation can signicantly increase the network performance even in long delay environments. Dierent from the all the proposed protocols, DC-MAC [START_REF] Yang | Dc-mac: A data-centric multi-hop mac protocol for underwater acoustic sensor networks[END_REF] is a data-centric multichannel multihop protocol based receiver-initiated mechanism to eliminate the hidden terminal problem. DC-MAC uses one control channel for receiverinitiated handshaking and one data channel for data transmissions. The control channel time is divided into periods assigned to nodes according to the number of hops counting from the sink. A node wishing to be receiver, it waits until its dedicated channel period to initiate a 4-way polling handshaking with its 1 hop neighbor. Each intended receiver sends rst an enquiry packet (ENQ) then it collects the replies (REQ) of all nodes wishing to be senders. After the selection of senders, the receiver broadcast a notication packet (NOTI) which can be followed by data packets of the receiver.

Multiple Rendezvous MultiChannel MAC protocols for UW-ASNs

As opposed to single rendezvous multichannel MAC protocols, multiple rendezvous can be achieved on distinct channels simultaneously to mitigate the control channel bottleneck.

However, since there are multiple rendezvous channels, special and careful coordination is required to guarantee that nodes switch to the same channel at the same time. However, with multiple rendezvous multichannel MAC protocols, the missing receiver problem is susceptible to get accentuated which may prevent regular spontaneous communication unless a special mechanism is provided to handle it.

One of the most recent MAC solution was proposed in [START_REF] Chao | Multiple-rendezvous multichannel mac protocol for underwater sensor networks[END_REF] and called MM-MAC protocol. MM-MAC aims at using a single modem to emulate multiple transceivers. Based on the cyclic quorum systems concept, nodes running MM-MAC can perform their channel negotiations on dierent channel simultaneously while avoiding to some extent the missing receiver problem. Accordingly, the time is divided into a series of superframes. Each superframe is further divided into control and data periods. For each control period, control slots are partitioned into default slots and switching slots such that every node will be allocated some defaults and switching slots. At default slots, a node stays on its default channel (each node is supposed to have its own default channel), waiting for transmission requests. At switching slots, a potential sender may switch to its intended receiver's default channel to initiate a transmission. To solve the missing receiver problem, the authors use the cyclic quorum concept to guarantee the overlapping between the default slots and the switching slot between any pair of nodes. That being said, the proposed procedure to compute the default and switching slots does not really guarantee the overlapping constraint which is mandatory for the proper functioning of the protocol. Moreover, MM-MAC relies on notication messages broadcast in order to inform neighboring nodes about any chosen data channel and hence avoid possible collisions on data channels. Indeed, once a sender and receiver succeed their handshaking process, both of them will repeatedly send a notication message at each of the remaining control mini-slots to declare that a given channel has been reserved. Such excessive sending of notication messages will highly consumes the network resources especially in terms of energy. Moreover, MM-MAC did not work in bursty network as the data period is xed. To deal with bursty networks, DMM-MAC, an extension of MM-MAC, was proposed in [START_REF] Chao | Energy-ecient multichannel mac protocol design for bursty data trac in underwater sensor networks[END_REF]. DMM-MAC is a dynamic duty-cycled multiple-rendezvous multichannel MAC protocol which applies the dynamic duty cycling mechanism to MM-MAC. As such, the time according to DMM-MAC is divided into series of cycles. Each cycle is composed of active and sleep sections. The time of each cycle is divided into frames mapped to MM-MAC superframes. The initial frame of each cycle is an active frame. The active section could be extended to multiple frames in order to accommodate the trac increase based on the overheard signals. However, instead to increase only the data period, the control period will be repeated also. Another example of multiple rendezvous multichannel MAC protocols for UW-ASNs is proposed in [START_REF] Hung | Rom-mac: A receiver oriented multichannel protocol for underwater acoustic sensor networks[END_REF]. The authors of [START_REF] Hung | Rom-mac: A receiver oriented multichannel protocol for underwater acoustic sensor networks[END_REF] propose a receiver oriented multichannel protocol named ROM-MAC to increase the bandwidth utilization and avoid the negotiation overhead and the hidden terminal problem. Accordingly, the channels time is composed of a set of cycles. Each cycle is divided into three phases. At the initial phase, neighbor nodes with the same default channel start to form a cluster using `Hello' and `Join' packets. Then, the cluster head organizes and broadcasts the control time slots schedule for members in the cluster. Based on the control slots schedule, each node announces its allocated negotiation duration and its data receiving time. At the control phase, each receiver node collects the requests of all possible senders, arranges the data reception from the possible senders and announces the data reception schedules. Finally, at the data phase, senders proceed to data transmission according to the schedule of the receiver. Using the received based communication, ROM-MAC mitigates the long propagation delay impacts and reduces the collision probability.

However, ROM-MAC relies on the broadcast of multiples control packets, at the initial and the control phases, which consume additional energy.

Conclusion

In this chapter, we presented the most potential works related to our context of investigation namely: sink hole problem and multichannel MAC protocols in UW-ASNs. Dierent from existing solutions, we conceived two novel protocols, a balanced routing design to avoid sink hole problem [START_REF] Zidi | Routing design avoiding energy holes in uw-asns[END_REF][START_REF] Bouabdallah | Joint routing and energy management in underwater acoustic sensor networks[END_REF] and a multichannel MAC protocol [START_REF] Zidi | Mc-uwmac: A multi-channel mac protocol for underwater sensor networks[END_REF], tailored for the underwater environment characteristics. In the next chapter, we present our proposed routing design to avoid the sink-hole problem. The objective of this protocol is to balance the energy consumption among all nodes in the network by distributing the individual trac load of each sensor node over multiple neighbors while forwarding data towards the sink.

Chapter 3

Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks

Introduction

In literature, it was shown, in terrestrial wireless sensor networks as well as in underwater sensor networks, that the closest sensors to the sink tend to deplete their provided amount of energy faster than other sensors [START_REF] Lian | Modeling and enhancing data capacity in wireless sensor networks[END_REF], [START_REF] Wadaa | Training a sensor networks[END_REF], [START_REF] Lian | Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[END_REF], [START_REF] Olariu | Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[END_REF], [START_REF] Zhao | Analysis on strategies of alleviating energy hole problem in wireless sensor networks[END_REF], [START_REF] Jiang | Mitigation techniques for the energy hole problem in sensor networks using n-policy m/g/1 queuing models[END_REF], [START_REF] Ammari | Investigating the energy sink-hole problem in connected k-covered wireless sensor networks[END_REF]. Indeed, sensors in the vicinity of a static sink act as the trac hot spots since they have signicant packet load to relay. As mentioned in the previous chapter, several solutions were proposed to avoid this unbalanced energy consumption which is liable to drastically reduce the lifetime of sensor networks. One of the crucial way to avoid sink hole problem that should be exploited is load balancing. In this chapter, we propose a balanced routing design for avoiding energy holes in UW-ASNs to balance the energy consumption among all underwater sensors. Our balanced routing solution dictates that each underwater sensor can tune its transmission power among two possible levels. Each transmission power level allows the sensor to reach a specied next hop. We strive for deriving the optimal load weight for each possible power level that leads to fair energy consumption among all sensors in the network and hence avoiding the sink-hole problem. Our proposed routing scheme is especially tailored for the underwater environment. Indeed, our routing solution takes into consideration the unique characteristics of the underwater channel such as attenuation, noise and the dependence of usable bandwidth and transmit power on distance. To do so, we consider one of the most popular and most adopted channel model in literature. In fact, once we determine the appropriate load weight for each possible transmission power level, the MAC layer then adapts specic parameters, such as bandwidth, according to the chosen transmission distance.

This chapter is organized as follows. In section 3.2, we introduce the energy sink-hole problem, we describe the considered network model. Then in section 3.3, we present a basic review of the underwater channel and the energy model. In section 3.4, we analytically formulate and solve the energy balancing problem that leads to an even energy depletion among all sensors. Results are provided in Section 3.5, where we compare the performance of our proposal to the nominal transmission range based data forwarding scheme. Finally, we conclude this chapter with a summary of our contributions.

3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 26

Energy sink-hole problem

In this study, we investigate the energy sink-hole problem in underwater acoustic sensor networks, where underwater sensors located close to the underwater sink are heavily used in forwarding sensed data to the sink. Indeed, those sensors especially the ones that are 1-hop away from the static sink act as relays to it on behalf of all other sensors, thus suering from severe energy depletion. Extensive research eorts have been devoted to analyzing the energy-sink hole problem especially in Wireless Sensor Networks (WSNs).

They all agree that the energy hole problem is unavoidable in static uniformly distributed always-on WSNs where the sensors periodically report their sensed data to a static sink using their nominal communication range [START_REF] Lian | Modeling and enhancing data capacity in wireless sensor networks[END_REF], [START_REF] Wadaa | Training a sensor networks[END_REF], [START_REF] Lian | Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[END_REF], [START_REF] Olariu | Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[END_REF], [START_REF] Powell | Energy optimal data propagation in wireless sensor networks[END_REF]. For this reason, most of the already undertaken research works on balancing the energy consumption focus mainly on using adjustable communication range. Indeed, by allowing each sensor to dynamically adjust its transmission power level, they aim at balancing the trac load distribution among sensors and thus the closest sensors to the sink are relieved of relaying task.

Our goal is to balance the energy depletion of all sensors in terms of trac forwarding (number of transmitted packets) in order to extend the network lifetime. To this end, our approach to deal with the energy sink hole problem is twofold: i) analyzing to what extent can perfect uniform energy depletion among all sensors in the network be assured such that the energy sink-hole problem in UW-ASNs is overcome and ii) studying how can the energy sink-hole problem in manually deployed UW-ASNs be addressed. By thoroughly investigating these two issues, we aim at closely approaching the perfect uniform energy depletion among all underwater sensors in the network. To address the rst issue, we conceive a data forwarding strategy for transmitting the periodically generated data from underwater source sensors to the sink. The goal of this forwarding scheme is to appropriately distribute the total data dissemination load on the individual underwater sensors such that the energy depletion is balanced among all sensors in the network. In our study, we target continuous monitoring applications, where each node reports periodically its own generated data to the sink. Consequently, we aim at distributing the total packet load (generated plus received) at each sensor among all possible next hops such that the energy consumption of each sensor is almost the same. To address the second issue, the set of 1-hop away neighbors of the sink should change over time, thus allowing dierent subsets of sensors to act as forwarders to the sink. In other words by varying the transmission power level of manually deployed sensors, the number of hops to reach the sink is continuously varying. For instance, let us assume that a sensor U is 2r away from the sink S. If the underwater sensor U uses a transmission power level to reach r then U is 2-hop away from S. However, if U adopts a transmission power to reach 2r then U is 1-hop away from S. Consequently, we propose that U sends a fraction of its total load using a transmission power level reaching r and the remaining portion is directly sent to the sink using a transmission power to reach 2r.

To recapitulate, in our work, each sensor is responsible of deriving the appropriate load weight with the associated transmission power level, namely potential next hop, that evenly distribute the energy consumption among underwater sensors. Similar objectives have been achieved in the literature by considering mobile sink [START_REF] Ammari | Promoting heterogeneity, mobility, and energy-aware voronoi diagram in wireless sensor networks[END_REF]. However, in our work, we tackle the energy sink-hole problem by considering a static underwater sensor deployment strategy. More details on the considered network model and acoustic channel features are given in the two next sections.

3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 27

Network model

In underwater environment, the deployment is generally sparser compared to terrestrial sensor networks due to the high cost of underwater sensors and the severe deployment challenges. Indeed, underwater sensors are manually anchored to the bottom of the ocean with deep ocean anchors. Note that, the manual and sparse deployment of UW-ASN reduces not only the number of deployed sensors but also allows the administrator to acquire a precise knowledge of their number in addition to their location which makes their precise deployment possible, which was extremely unrealistic with terrestrial sensor networks.

In our work, we exploit the sparse and manual deployment of UW-ASNs in order to propose a solution that approaches the perfect balanced energy depletion among underwater sensors. Accordingly, we consider a 2-dimensional shallow underwater sensor network where a set of sensors are anchored to the ocean bottom and endowed with a oating buoy. The buoy can be inated by a pump in order to bring the sensor towards the ocean surface. In addition, we assume that the sensors will be all the time attached to their anchors through the cable which will severely restrict their displacement. Consequently, in such scenario, these surface sensors that are bottom anchored have a complete knowledge of their geographical position at deployment time. It is worth pointing out that the considered deployment architecture targets especially shallow water which makes the deployment cost reasonable.

In order to approach the perfect uniform energy depletion, we assume that sensors are placed in a circular sensor eld of radius R centered at the sink. The sensor eld is virtually partitioned into disjoint concentric sets termed coronas of constant width r. The width of each corona is at most d tx-max , the maximum transmission range of an underwater acoustic sensor. Consider K to be the number of coronas around the sink. For example, in Fig. 4.1, K = 4, hence the sensor eld is partitioned into ve coronas B 1 , B 2 , B 3 and B 4 .

K = R r (3.1)
Recall that, we consider a continuous reporting sensor application where the average 3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 28 number of reports generated per unit of time by each sensor node is denoted by A.

According to the considered deployment pattern discussed above, routing is relatively straightforward. Each packet is forwarded from the source to the sink by crossing adjacent coronas through the immediately adjacent sensors. Figure 4.1 illustrates a possible path along which a packet from one sensor in the outermost corona is routed to the sink. Notice that, in this example, each hop involves the immediately adjacent neighbor from adjacent corona. More precisely, our sensor eld can be seen as a set of wedges. Each wedge W is virtually partitioned into K sectors, S 1 , S 2 , ..., S K by its intersection with K concentric circles, centered at the sink, and of monotonically increasing radius r, 2r, 3r, ..., Kr, as shown in Fig. 4.1. Each sector contains exactly one sensor which has to forward the cumulative trac coming from its predecessors to one of its possible successors in the direction of the sink. It is worth pointing out that in such deployment pattern, sink-hole problem would inevitably happen. This is because, using the nominal communication range based data forwarding, all the forwarded data would be obligatory passing through the closest neighbors of the sink. Forwarding all the accumulated data plus their own generated data, sink-closest-nodes especially 1-hop neighbors will exhaust faster their limited and nonchargeable energy budget, creating a hole around the sink, as explained above.

In our study, to avoid such problem, we assume that each sensor is capable of adjusting its transmission power among two levels in order to send the appropriate fractions of packet load to the adjacent successor and the one after in the same wedge W . In other words, we suppose that

d tx-max ∈ {r, 2r} (3.2)
More precisely, the lowest transmission power allows each sensor to reach the immediately adjacent corona, while the second highest transmission range allows it to reach the 2-hop away corona.

The goal of this work is to determine the associated load fraction to be sent using each transmission power level on the individual sensor node such that a uniform energy depletion is guaranteed among all sensors in the network and hence the energy hole problem is overcome. To do so, we aim at developing an analytical model that iteratively derives for each source sensor the appropriate load weight for each possible transmission power level while balancing the energy consumption among all sensors in the same wedge. Note that, in such network pattern, the energy consumption of sensors is most importantly due to data reception and transmission. The energy depletion due to overhearing can be neglected, since in underwater environment, the deployment is generally sparse. Nevertheless, in underwater networks, energy consumption depends strongly on the characteristics of the deployment environment such as the high-attenuation, the noise, ... In the section, we review the basic features of the underwater acoustic channel which inuences the data propagation and the consumed power.

3.4

Basic features of underwater propagation and energy model

Attenuation

The experienced attenuation in an underwater acoustic channel over a distance d in meters for a frequency f in kilohertz can be modeled in decibels by

10 log 10 A (d, f ) A 0 = k10 log 10 d + d 10 3 10 log 10 a (f ) (3.3)
where A 0 is a normalizing constant, k denotes the spreading factor, and a (f ) denotes the absorption coecient. a (f ) is empirically derived using Thorp's formula [START_REF] Brekhovskikh | Fundamentals of Ocean Acoustics[END_REF] in decibels 3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 29

per kilometer for f in kilohertz as 10 log 10 a (f ) = 0.11

f 2 1 + f 2 + 44 f 2 4100 + f 2 +2.75 × 10 -4 f 2 + 0.003 (3.4)
This formula is generally applied for frequencies above a few hundred hertz. For lower frequencies it is suggested to use the following formula: 10 log 10 a (f ) = 0.002 + 0.11

f 2 1 + f 2 + 0.011f 2 (3.5)

Noise

There are four dierent sources of noise in the ocean: turbulence, shipping, waves, and thermal noise. The overall power spectral density (p.s.d.) of the noise in dB re 1 µ P a 2 /Hz (i.e., the power per unit bandwidth associated with the reference sound pressure level of 1 µ P a) can be expressed as

10 log 10 N (f ) = η 0 -18 log 10 f (3.6)
where f is in kilohertz, and the constant level η 0 is adjusted in accordance with a specic deployment site.

The signal to noise ratio SNR

The narrowband signal-to-noise ratio (SNR) is given by [START_REF] Stojanovic | On the relationship between capacity and distance in an underwater acoustic communication channel[END_REF] SN R (d, f ) =

S(f )∆f A(d,f ) N (f ) ∆f = S (f ) A (d, f ) N (f ) (3.7)
where S (f ) is the p.s.d. of the transmitted signal and ∆f is a narrow frequency band around f .

Bandwidth and transmission power denitions

The bandwidth and the associated transmission power in the underwater environment are dened in [START_REF] Jornet | On joint frequency and power allocation in a cross-layer protocol for underwater acoustic networks[END_REF]. According to [START_REF] Jornet | On joint frequency and power allocation in a cross-layer protocol for underwater acoustic networks[END_REF], for each transmission distance d, there exists an optimal frequency f 0 (d) for which the narrowband SNR is maximized. Hence, a 3-dB bandwidth, B 3dB (d), was introduced and simply refers to the range of frequencies around f 0 (d

) for which A (d, f ) N (f ) < 2 A (d, f 0 (d)) N (f 0 (d))
. Using B 3dB (d) bandwidth denition, the associated transmission power in watts necessary to provide a target SN R 0 at a distance d in meters from the source is determined as

P tx (d) = SN R 0 B 3dB (d) × B 3dB (d) N (f ) df B 3dB (d) A -1 (d, f ) df (3.8)
Note that the target SN R 0 at a distance d can be expressed as function of a target packet error rate P ER tgt as introduced in [START_REF] Zorzi | Energy-ecient routing schemes for underwater acoustic networks[END_REF]. Accordingly, by assuming the use of BPSK, the target SN R 0 for a packet of length P l bits can be expressed as follows:

SN R 0 = 1 δ erfc -1 2 -2 (1 -P ER tgt ) 1 P l 2 (3.9)
3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 30 where δ is a penalty factor that accounts for signal processing ineciencies at the receiver. Consequently, the electrical power needed to cover a distance d is given by where 10 log 10 P tx (d) is the acoustic transmission power in dB re 1 µ P a 2 , 170.8 dB is the conversion factor between acoustic pressure in dB re 1 µ P a and acoustic power in watts (W ), and ξ is the transducer eciency. Fig. 3.2 shows the generated transmission power in Watt as function of distance where SN R 0 = 20 dB, η 0 = 50 dB re 1 µ P a 2 /Hz, A 0 = 30 dB, k = 1.5 and ξ = 0.8. It is worth pointing out that the transmission power is a non linearly increasing function of distance.

More precisely, the energy spent in transmitting one packet of length P l bits over a distance d is given by

E tx (d) = P T (d) × T tx (d) (3.11)
where T tx (d) is the transmission time given by

T tx (d) = P l C 3dB (d) (3.12)
where C 3dB (d) is the maximum allowed capacity over B 3dB (d) . According to [START_REF] Stojanovic | On the relationship between capacity and distance in an underwater acoustic communication channel[END_REF]

C 3dB (d) = B 3dB (d) log 2 1 + P tx (d) /B 3dB (d) A (d, f ) N (f ) df (3.13)
Likewise, the energy spent in receiving one P l bits packet is given by

E rx (d) = P 0 rx × T tx (d) (3.14)
where P 0 rx is the electronics power.

Balancing energy expenditure

In this work, we strive for eciently routing the reports to the sink node by balancing the energy consumption throughout the network. By doing so, we aim at improving the UW-ASNs lifetime. In our study, all the sensor nodes transmit periodically their reports to the sink node, denoted by S. We target here continuous-monitoring applications, one of the most important classes of UW-ASN applications. The average number of reports 3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 31 generated per unit of time by each sensor node is denoted by A. In this section we turn to the task of evaluating the energy expenditure per sensor in an arbitrary corona B i with i ≥ 1. Observe that, according to our routing strategy, every node in a given wedge W and a generic corona B i , (1 ≤ i ≤ K), is called upon to serve two kinds of paths:

• paths originating at an underwater sensor located in the same wedge W but in a dierent corona B j with i < j ≤ K, and

• paths emanating from the same sensor in B i .

It is easy to show that the total number of paths that may involve a specic node in a given wedge W and in corona B i includes all possible paths in W except those originating in one of the coronas B 1 , B 2 , ... and B i-1 .

In this work, we approach the ecient routing of reports to the sink node by appropriately distributing the total data dissemination load on the individual underwater sensors such that a fair energy depletion is assured among all sensors in the network and hence the UW-ASN lifetime is enhanced.

In this study, we suppose that for each sensor node located at corona B i in a specic wedge W , the next hop to send generated reports to the sink S can be the sensor located in B i-1 or in B i-2 in the same wedge W using respectively d tx-max = r or d tx-max = 2r.

Considering a wedge W , we associate to each possible next hop located in B i-

1 or B i-2 a respective weight β i 1 , β i 2 such that β i 1 + β i 2 = 1, ∀i, 1 ≤ i ≤ K.
Consequently, the total number of packets per unit of time, A i , handled by sensor in corona B i and wedge W, can simply be expressed as follows

A i = A + β i+1 1 A i+1 + β i+2 2 A i+2 (3.15)
where

β i+j j = 0 for j = 1, 2, if i + j > K.
Consequently, the average transmission energy, E i tx , consumed by a sensor in corona B i and wedge W can be derived as follows

E i T X = β i 1 A i E tx (r) + β i 2 A i E tx (2r) (3.16)
where β i j = 0 for j = 1, 2 if i -j < 0. Likewise, the average reception energy, E i rx , consumed by a sensor in corona B i and wedge W can be expressed as follows

E i RX = β i+1 1 A i+1 E rx (r) + β i+2 2 A i+2 E rx (2r) (3.17)
where β i+j j = 0 for j = 1, 2 if i + j > K. Finally, the total energy consumed by a sensor in corona B i and wedge W is

E i = E i T X + E i RX (3.18)
Recall that the goal of our work is to tailor the coronas in such way that the energy expenditure is balanced across all the coronas. Consequently, our problem can be stated as follows:

Given K, r, d tx-max Find β i 1 , β i 2 ∀i, 1 ≤ i ≤ K such that E 1 = E 2 = ... = E K subject to β i 1 + β i 2 = 1, ∀i, 1 ≤ i ≤ K (3.19)
In the next section, we strive for approaching the perfect uniform energy depletion by determining, for each sensor node, the next possible hops with the associated load weight that better approach the balanced energy expenditure among underwater sensors. Note that, in practical applications, a centralized computing center will be in charge of making the network planning by providing every sensor with the appropriate sending weights to every possible upstream sensor on the way to reach the sink. In what follows, we denote E rx (jr) as E j rx , E tx (jr) as E j tx and the vector

β i = β i l 1≤l≤2 .
3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 32

Iterative process

The rst analytical approach of the perfect uniform energy depletion is using an iterative process. As it turns out, the β i s can be determined iteratively in a natural way. In the rst iteration, we suppose that we only have the corona B 1 of width r. In this case, the total trac of each sensor in B 1 is exclusively composed of the locally generated trac A and clearly β 1 1 equal to 1. In the second iteration, we add corona B 2 and knowing β 1 1 we try to balance the energy expenditure between B 1 and B 2 by determining β 2 1 and β 2 2 . More precisely, by adding B 2 the total trac of B 1 increases since there is a newly received trac from B 2 . Consequently, our previously established balance is perturbed. To re-arrange such imbalance, we compute β 2 1 and β 2 2 . Note that β 2 2 denotes the trac weight that has to be sent directly from sensor in B 2 to the sink. Generally speaking, suppose that we reach iteration j and hence the energy consumption between j coronas is balanced. Adding corona B j+1 will disturb the previously established balance since the total trac in each corona will inevitably increase. Knowing β 1 , β 2 ,..., β j , we settle once again our balance by determining β j+1 . Note that for the newly added corona B j+1 , A j+1 = A and E j+1 RX = 0. As we shall see shortly, β 2 is obtained after adding corona B 2 and as a result of writing E 2 = E 1 . By the same way, after adding corona B 3 , β 3 is obtained from

E 3 = E 2 and E 3 = E 1 . More generally, at iteration j + 1, β j+1 is obtained from E j+1 = E j = ... = E 1 .
The iterative process is straightforward; the details are presented next.

Calculation of the cumulative trac

Let us start by iteratively expressing the cumulative trac. For this purpose, at each iteration j + 1, we newly derive A j-k ; ∀ 0 ≤ k ≤ j -1.

Theorem 1:

∀1 ≤ j + 1 ≤ K; A j+1 = A and ∀0 ≤ k ≤ j -1; A j-k = α 0k + α 1k β j+1 1 + α 2k β j+1 2 × A where                      β j+1 2 = 0 if k = j -1 α 00 = 1; α 0(-1) = 1 α 0k = 1 + α 0(k-1) β j-(k-1) 1 + α 0(k-2) β j-(k-2) 2 α 1(-1) = 0; α 2(-1) = 0; α 21 = 1; α 10 = 1; α 20 = 0; α 1k = α 1(k-1) β j-(k-1) 1 + α 1(k-2) β j-(k-2) 2 α 2k = α 2(k-1) β j-(k-1) 1 + α 2(k-2) β j-(k-2) 2
Proof. In order to prove Theorem 1, we use mathematical induction proof technique.

At the rst step, let we show that Theorem 1 holds for k = 0.

According to the iterative process, for the newly added outermost corona B j+1 , no data is received. Thus, the cumulative trac at corona B j+1 is simply the generated trac and it can be expressed as follows: A j+1 = A ∀1 ≤ j + 1 ≤ K. Moreover, adding corona B j+1 will increase the cumulative trac A j , at B j , which is equal to A + β j+1 1 A j+1 and can be also written as follows

A j-k = A × 1 + β j+1 1 = such that k = 0. Accordingly, A j-k = α 00 + α 10 β j+1 1 + α 20 β j+1 2
× A where α 00 = α 10 = 1 and α 20 = 0.

At the second step, let we suppose that Theorem 1 is true ∀0 ≤ k ≤ j -1 and let we prove it for A j-(k+1) . According to Eq. 3.15, we have can write A j-(k+1) as follows 3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 33

A j-(k+1) = A + β j-k 1 A j-k + β j-k+1 2 A j-(k-1)
After extending the equation of A j-(k+1) by replacing A j-k and A j-(k-1) based on Theorem 1, we get

A j-(k+1) = A + β j-k 1 [α 0k + α 1k β j+1 1 + α 2k β j+1 2 ] × A +β j-(k-1) 2 α 0(k-1) + α 1(k-1) β j+1 1 + α 2(k-1) β j+1 2 × A = A ×     (1 + α 0k β j-k 1 + α 0(k-1) β j-(k-1) 2 ) +(α 1k β j-k 1 + α 1(k-1) β j-(k-1) 2 )β j+1 1 +(α 2k β j-k 1 + α 2(k-1) β j-(k-1) 2 )β j+1 2     Note that, according to Theorem 1, 1 + α 0k β j-k 1 + α 0(k-1) β j-(k-1) 2 is simply α 0(k+1) , α 1k β j-k 1 + α 1(k-1) β j-(k-1) 2 is α 1(k+1) and α 2k β j-k 1 + α 2(k-1) β j-(k-1) 2 is α 2(k+1) . Accordingly, A j-(k+1) can be expressed as follows A j-(k+1) = α 0(k+1) + α 1(k+1) β j+1 1 + α 2(k+1) β j+1 2
Thus, Theorem 1 is true for A j-(k+1) .

Now, as we succeed to express the cumulative trac at each iteration as a function of β j+1 , we can calculate the energy consumption in transmission and reception to determine iteratively β j+1 .

Calculation of energy consumption in transmission and reception

Our objective is to determine β j+1 , for each iteration j + 1, which balance the energy consumption between B 1 , B 2 , ..., B j+1 . Thus, at each iteration j + 1, we strive for deriving the unknown vector β j+1 of size 2. For this purpose, we aim at expressing E j+1 T X , E i T X and E i RX (∀ 1 ≤ i < j + 1) as function of β j+1 . Consequently, by writing E j+1 T X = E j = ... = E 1 we get a system of j + 1 equations with 2 unknowns. Let's start by expressing the straightforward E j+1

RX and E j+1 T X .

∀1 ≤ j + 1 ≤ K E j+1 RX = 0 E j+1 T X = [AE 1 tx β j+1 1 + AE 2 tx β j+1 2 ] = T X j+1 1 β j+1 1 + T X j+1 2 β j+1 2 (3.20)
where T X j+1 l = AE l tx ; for l = 1, 2.

Note that our ultimate goal is to express our problem as a system of linear equations, at each iteration. We succeed to linearly express E j+1 T X as function of β j+1 . Now, let us derive E i T X and

E i RX (∀ 1 ≤ i < j + 1) as function of β j+1 . • E i T X derivation
According to Eq. 4.13, we have

E i T X = A i β i 1 E 1 tx + A i β i 2 E 2 tx ; if i = 1 then β i 2 = 0 = A i β i 1 E 1 tx + β i 2 E 2 tx
Now, A i can be replaced by its expression based on Theorem 1. Thus E i T X will be as follows 3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 34

E i T X = β i 1 E 1 tx + β i 2 E 2 tx A j-(j-i) = β i 1 E 1 tx + β i 2 E 2 tx × α 0(j-i) + α 1(j-i) β j+1 1 + α 2(j-i) β j+1 2 × A = A β i 1 E 1 tx + β i 2 E 2 tx α 0(j-i) + 2 l=1 A β i 1 E 1 tx + β i 2 E 2 tx α l(j-i) β j+1 l = T X i 0 + 2 l=1 T X j-i l β j+1 l ; if j + 1 = 1 then β j+1 2 = 0
Thus, E i T X can be simply expressed as follows

E i T X = T X i 0 + 2 l=1 T X j-i l β j+1 l (3.21)
where

     β j+1 2 = 0 if j + 1 = 1 and β i 2 = 0 if i = 1 TX i 0 = A β i 1 E 1 tx + β i 2 E 2 tx α 0(j-i) TX j-i l = A β i 1 E 1 tx + β i 2 E 2 tx α l(j-i) • E i RX derivation
According to Eq. 4.14, we have

E i RX = β i+1 1 A i+1 E 1 rx + β i+2 2 A i+2 E 2 rx ; if i = j then β i+2 2
= 0 At this step, A i+1 and A i+1 can be substituted by their expressions according to Theorem 1. Thus, E i RX becomes as follows

E i RX =    Aβ i+1 1 E 1 rx α 0(j-i-1) + α 1(j-i-1) β j+1 1 + α 2(j-i-1) β j+1 2 +Aβ i+2 2 E 2 rx α 0(j-i-2) + α 1(j-i-2) β j+1 1 + α 2(j-i-2) β j+1 2 =          A β i+1 1 E 1 rx α 0(j-i-1) + β i+2 2 E 2 rx α 0(j-i-2) +Aβ j+1 1 β i+1 1 E 1 rx α 1(j-i-1) + β i+2 2 E 2 rx α 1(j-i-2) +Aβ j+1 2 β i+1 1 E 1 rx α 2(j-i-1) + β i+2 2 E 2 rx α 2(j-i-2) = RX i 0 + RX j-i 1 β j+1 1 + RX j-i 2 β j+1 2 If i = j -1 then E i RX = RX i 0 + RX j-i 1 β j+1 1 + AE 2 rx β j+1 2
Consequently, E i RX can be written as follows

E i RX = RX i 0 + RX j-i 1 β j+1 1 + RX j-i 2 β j+1 2 ; ∀ 1 ≤ i < j + 1 RX i 0 + RX j-i 1 β j+1 1 + AE 2 rx β j+1 2 ; if i=j-1 (3.22)
where

             β i+2 2 = 0 if i = j RX i 0 = A β i+1 1 E 1 rx α 0(j-i-1) + β i+2 2 E 2 rx α 0(j-i-2) RX j-i 1 = A β i+1 1 E 1 rx α 1(j-i-1) + β i+2 2 E 2 rx α 1(j-i-2) RX j-i 2 = A β i+1 1 E 1 rx α 2(j-i-1) + β i+2 2 E 2 rx α 2(j-i-2)

Problem statement

Now that we succeed to express E i T X and E i RX as a function of β j+1 1 and β j+1 2 , we can express our problem as a system of linear equations, we nally get

∀ 1 ≤ j + 1 ≤ K ; ∀1 ≤ i < j + 1 E j+1 T X = E i T X + E i RX =    T X j+1 1 -T X j-i 1 -RX j-i 1 β j+1 1 + + T X j+1 2 -T X j-i 2 -RX j-i 2 β j+1 2 = T X i 0 + RX i 0 (3.23) such that β j+1 1 + β j+1 2 = 1.
3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 35

Let T X j+1 be a matrix of size (j + 1, 2) such that T X j+1 = (T X i,l ) 1≤i≤j+1 1≤l≤2

T X i,1 = T X j+1 1 -T X j-i 1 -RX j-i 1 ; ∀ 1 ≤ i < j + 1 T X i,2 = T X j+1 2 -T X j-i 2 -RX j-i 2 ; ∀ 1 ≤ i < j + 1 T X (j+1),1 = 1 T X (j+1),2 = 1 (3.24)
Recall that β j+1 is a column vector such that β j+1 = β j+1 l 1≤l≤2

and let us dene C

as C i 0 1≤i<j+1 such that C i 0 = T X i 0 + RX i 0 ; ∀ 1 ≤ i < j + 1 and C j+1 0 = 1.
In this case, our system can be written as T X j+1 β j+1 = C. Note that β j+1

1 + β j+1 2 = 1, ∀ 1 ≤ j + 1 ≤ K .
Note that, if j + 1 = 2, then we have a system of 2 equations with 2 unknown variables. Consequently, T X j+1 is a square matrix of size 2. Hence, we can easily solve T X j+1 β j+1 = C and thus the perfect uniform energy depletion is reached. However, if j + 1 > 2, then our system is actually composed of j+1 equations E j+1 = E j = ... = E 1 with only 2 unknown variables. Consequently, we have much more equations than needed and hence achieving perfect uniform energy depletion is impossible. For this reason, we slightly deviate our original goal to become that of minimizing the dierence in energy consumption among dierent coronas. We try to numerically solve our partial uniform energy depletion problem after reformulating it as follows

Given K, r, d tx-max Find β j+1 1 , β j+1 2 min β j+1 T X j+1 β j+1 -C subject to β j+1 1 + β j+1 2 = 1 β j+1 1 ≥ 0 and β j+1 2 ≥ 0 (3.25)
This constrained nonlinear optimization problem can be easily solved using fminconfunction in the Matlab optimization toolbox. Note that, fmincon is a powerful optimization tool that uses three well known methods namely; active set, trust region reective and interior point.

Performance evaluation

In this section, we present a comparison study between our balanced routing solution (d tx-max ∈ {r, 2r}) and the nominal communication range based data forwarding [START_REF] Ammari | Promoting heterogeneity, mobility, and energy-aware voronoi diagram in wireless sensor networks[END_REF] (i.e.

(d tx-max = r)). Results are derived analytically. Recall that in our model, the underwater sensor nodes perform continuous monitoring of the supervised circular area of radius R.

Our circular sensor eld centered at the sink is partitioned into disjoint concentric coronas of xed width r. Each underwater sensor periodically reports with rate A the locally generated data to the sink over several hops. At each hop, the trac emanating from the local sensor must be merged with route-through trac. Each packet is forwarded from the source to the sink by crossing coronas located in the same wedge. Power control was performed by determining the minimum power required to achieve a packet error probability of 0.04 at the receiver and a SNR penalty of δ = -10 dB providing thus a target SN R 0 of 20 dB. The parameters setting in our analysis are listed in Table 3.1.

We rst analyze the results regarding our balanced routing strategy for a circular sensor eld of radius R = 1000 m and corona width r = 100 m resulting in a total number of coronas equals 10. Each sensor in each corona is supposed to generate 10 packet/s. We 3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 36 First, let us discover β = β i 1≤i≤10 matrix of our balanced routing scheme with d tx-max ∈ {r, 2r}. We want to point out that the β matrix is derived with the purpose of evenly distributing the energy consumption among dierent coronas. Table 3.3 reports the β i vectors for each corona. Accordingly, in order to minimize the energy consumption gap between dierent coronas, much more packets should be sent to the 2-hop away corona.

In other words, in order to balance the energy consumption among dierent coronas, most of the accumulated trac should be forwarded using d tx-max = 2r = 200 m. Indeed, underwater sensors in the second corona should send 98% of their accumulated trac directly to the sink. In the same way, sensors in coronas 4, 6, 7, 8, 9 have to disseminate more than 80 % of their total packet load to the 2-hop away coronas. The least percentage is achieved in the third corona. In fact, sensor in corona 3 sends 65 % of its trac to the rst band against only 35 % to the second corona. As a result, it is clear enough that it is highly preferred to send packets load 2-hop away in order to balance the energy consumption.

According to Table 3.3, the packet load distribution is shown in Fig. 3 to a total trac of 100 packet/s at sensors in corona 1. This amount of accumulated trac at corona 1 is highly decreased (less than 40 packet/s) with our balanced routing solution (d tx-max ∈ {r, 2r}). This gain is more importantly highlighted in Fig. 3.4. In fact, Fig. 3.4 shows the energy consumption for each sensor in the corresponding corona.

Accordingly, a 74 % of energy saving is achieved at corona 1. It is worth noting that using our balanced routing strategy, leads to a maximum energy expenditure of 0.065 W at sensors in corona 2. However, according to the nominal communication range based data forwarding, a maximum energy consumption of 0.146 W is achieved as expected at corona 1. Consequently, an energy saving of 55.5 % is accomplished thanks to our balanced routing scheme. We would like to point out that the energy consumption per corona is not proportional to the packet load distribution as shown in Figs. time. From an energy depletion point of view, we consider the maximum consumed amount of energy among all coronas. When it comes to network lifespan, we dene the network lifetime simply as the time for the rst node in the network to drain its energy budget. In other words, the network lifetime is given by

T net_lif etime = E init max U ∈corona_nodes E(U ) (3.26)
where E init is the initial amount of energy provided to each sensor node and U refers to an arbitrary underwater sensor in our eld. Consequently and as depicted in Fig. 3.6 the network lifetime decreases with the increase of the eld radius. Note that, our balanced routing solution achieves up to 62% of energy saving for a eld radius of 500 m and a minimum energy saving of 46 % is guaranteed in each conguration. Now, let us assess the impact of varying the corona width on the system performance.

To achieve this, we consider a xed eld radius of 2000 m while varying the corona width 3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 39 Here again, we point out that a perfect balance of energy consumption as shown in Fig. 3. [START_REF] Pompili | Overview of networking protocols for underwater wireless communications[END_REF] 3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 40 3 Routing Design Avoiding Energy Holes in UnderWater Acoustic Sensor Networks 43

Figure 3.17: Energy Consumption per corona for various frequency band.

does not mean a perfect load distribution as depicted in Fig. 3.15 since the transmission power is a non linear function of transmission distance.

Finally, to justify the use of B 3dB bandwidth denition, let us evaluate its contribution to energy saving in our model. Recall that, according to [START_REF] Jornet | On joint frequency and power allocation in a cross-layer protocol for underwater acoustic networks[END_REF], there is an optimal bandwidth and its corresponding optimal transmission frequency for each transmission distance. Consequently, for each selected transmission distance, we use the B 3dB (d) bandwidth centered on a tone of frequency f c = f 0 (d).

Using our balanced routing scheme with d tx-max ∈ {r, 2r}, Fig. 3.17 illustrates the eect of independently changing the bandwidth and the center frequency while applying the same β = β i 1≤i≤10 matrix on trac load distribution. The system performance is analyzed for two dierent center frequencies f c = 20 kHz and f c = f 0 (d). With f 0 (d), we use the B 3dB (d) bandwidth denition. However, for f c = 20 kHz, the system performance is analyzed for two dierent bandwidths B = 1 kHz and B = 20kHz. When the center frequency remains xed and equal to 20 kHz, an important energy saving is achieved when increasing the bandwidth, for each corona. In fact, with a greater bandwidth the bit duration 1/B is highly reduced and thus the energy consumption. Most importantly, note that the optimal energy consumption is accomplished with f c = f 0 (d) and its corresponding B 3dB (d) bandwidth. As shown in Fig. 3.17, sensors in corona 2 consume the maximum amount of energy, for each frequency and bandwidth allocation scheme. However, the energy expenditure of sensors in corona 2 is reduced with f c = f 0 (d) and its corresponding B 3dB (d) bandwidth. We want to point out that our routing solution tries to optimize the energy consumption by looking most importantly for the best trac distribution among coronas and by applying the optimal frequency and bandwidth. As such a comprehensive solution is proposed.

Conclusion

In this chapter, we proposed a routing strategy that leads to an even energy depletion among all sensors in the underwater network. Accordingly, each underwater node can dynamically adjust its transmission power among two possible levels to send the associated predened load weight that lead to a fair energy consumption and hence the energy sink hole problem is overcome. To do so, we developed a comprehensive analytical model that iteratively derives for each source sensor the appropriate load weight for each possible transmission power level that lead to a fair energy depletion among all sensors in the network. Analytical results show that signicant improvement is achieved by our routing Introduction

Still dealing with the sink-hole problem, in this chapter, we present our extended balanced routing solution for avoiding energy holes in UW-ASNs. Unlike our previous solution, our extended solution dictates that each underwater sensor can tune its transmission power among multiple possible levels n>2 instead of only two levels. As stated in the previous chapter, each transmission power allows the sensor to reach possibly a specied next hop.

We strive for deriving the optimal load weight for each possible power level that leads to fair energy consumption among all sensors in the network and hence the sink-hole problem is overcome.

The main contribution of this work is that we derive the optimal number of transmission power levels, n, that maximizes the network lifetime by overcoming the energy holes problem. In fact, there exists a compromise between the number of transmission power levels (n) and the energy consumption [START_REF] Jornet | Focused beam routing protocol for underwater acoustic networks[END_REF][START_REF] Zorzi | Energy-ecient routing schemes for underwater acoustic networks[END_REF]. On one hand, as we increase n, we allow the trac load to be much more distributed among all the upstream coronas and hence a balanced trac load distribution is achieved resulting in a balanced energy consumption throughout the network. On the other hand, increasing n raises the energy consumption since the farthest coronas may be reached. Consequently, there clearly exists an optimal n value for which the network lifetime is maximized. Moreover, it is worth pointing out that our extended routing solution further takes into consideration the unique characteristics of the underwater channel through the use of the time-varying channel model derived in [START_REF] Qarabaqi | Statistical characterization and computationally ecient modeling of a class of underwater acoustic channels[END_REF].

Indeed, in the previous work as shown in chapter 3, we adopted the channel model presented in [START_REF] Jornet | Focused beam routing protocol for underwater acoustic networks[END_REF] where we consider some of underwater features which aect the acoustic channel propagation such as the attenuation, ... However, in addition to those features, the underwater channel can be aected by the movement of underwater nodes, the damages of some nodes (due to the rugged underwater environment), which make the strategy designing thought dier from other sensor networks. To solve this issue and in order to better approach the underwater environment peculiarities, in this chapter, we adopt a time varying channel model proposed by Stojanovic et al. in [START_REF]The simulator package[END_REF] which is considered in the literature review as one of the most recent and exhaustive mathematical analysis that meticulously describes the time varying channel gain in underwater environment by taking into account most of the physical features and impairments of the acoustic propagation.

This chapter is organized as follows. In section 4.2, we recall the considered network model denition to address the sink hole problem. The time-varying channel model is introduced in section 4.3. We present the analytical formula and we solve the energy balancing problem in section 4.4. Specically, we solve a linear optimization problem that

Network model

As stated in the previous chapter, the energy sink-hole problem occurs in underwater acoustic sensor networks when underwater sensors located close to the underwater sink deplete their limited energy budget because of their heavier load trac. To address such problem, we consider the same underwater sensor deployment topology of the previous chapter where underwater sensors are manually placed in a circular sensor eld of radius R centered at one static sink. The sensor eld is virtually partitioned into disjoint concentric sets termed coronas of constant width r. The width of each corona is at most d tx-max , the maximum transmission range of an underwater acoustic sensor. K denotes the number of coronas around the sink where

K = R r (4.1)
In such network, as mentioned in the previous chapter, packets are forwarded from the source to the sink by crossing adjacent coronas through the immediately adjacent sensors. Each sensor forwards the cumulative trac coming from its predecessors to its possible successors. More precisely, our sensor eld can be seen as a set of wedges where each wedge W represent one path. In our study, we assume that each sensor is capable of adjusting its transmission power in order to send the appropriate fractions of packet load to one of its possible successors within its maximum transmission range d tx-max .

To closer approach the uniform energy depletion, we enhance our previous data forwarding strategy in order to appropriately distribute the total data dissemination load on the individual underwater sensors among multiple neighbors such that the energy depletion is balanced among all sensors in the network. To do so, dierent from our previous solution, in this work, we assume that nodes are able to adjust its transmission power to To determine for each sensor the corresponded load weight for each possible transmission power level that lead to fair energy depletion among nodes in the network, we develop an analytical model that iteratively derives the appropriate load weight to be sent using each possible transmission power level while balancing the energy consumption of all nodes in the network.

Clearly, by increasing the transmission power levels, the trac load at each sensor will be much more distributed among all the possible neighbors and multiple sensors could be reached which alleviates the load of several nodes especially the 1-hop sink neighbors.

However, on the other hand, when the number of power levels raises the reached distance will raise also which increases mainly the energy consumption of the farthest sensors. Thus, in our work, we strive to nd the optimal number of transmission power levels for which the energy consumption is balanced, the network lifetime is maximized and most importantly the sink-hole problem is avoided.

Moreover, in order to further consider the peculiarities the underwater environment, we use a new channel model that takes into account the time variability of the acoustic channel notably the inevitable random local movement of underwater nodes and its induced Doppler eect. More precisely, we adopt the underwater channel model proposed by Qarabaqi and

Stojanovic in [START_REF] Akyildiz | Underwater acoustic sensor networks: Research challenges[END_REF] and implemented in [3] which is considered in the literature review as one of the most recent and exhaustive mathematical analysis that meticulously describes the time varying channel gain in underwater environment by taking into account most of the physical features and impairments of the acoustic propagation such as: frequencydependent attenuation, bottom surface reections as well as the eects of inevitable random local displacements and its induced Doppler eect.

Time-varying underwater channel

The channel gain

In [START_REF] Qarabaqi | Statistical characterization and computationally ecient modeling of a class of underwater acoustic channels[END_REF], an exhaustive mathematical analysis was conducted to describe the time-varying channel gain in underwater environment by taking into account most of the physical features of acoustic propagation such as frequency-dependent attenuation, the bottom surface reections as well as the eects of inevitable random local displacements and its induced Doppler eect. The proposed analytical model was validated using experimental data and hence an underwater acoustic simulator was developed [START_REF]The simulator package[END_REF] to provide the instantaneous channel gain between a transmitter and a receiver, given their nominal coordinates and their displacement ranges. According to [START_REF] Qarabaqi | Statistical characterization and computationally ecient modeling of a class of underwater acoustic channels[END_REF], underwater channel variations can be classied according to the size of the random displacement undergone by underwater sensors. Indeed, due to many phenomena (water current, transmitter/receiver drifting, surface waves...) underwater sensors may undergo displacement on the order of a few or many wavelengths. The former is referred to as small-scale variations and the latter as large-scale variations. Small-scale variations occur over short displacements and correspondingly short period of time during which the system geometry (especially in terms of nodes' locations) and environmental conditions do not go through remarkable change and hence are rather considered static. However, large-scale modeling takes into account variations caused by location shifting as well as varying environmental conditions. In other words, large-scale variations are modeled as a consequence of random system displacements spanning a given variation range leading thus to large-scale variation in the gains and delays of propagation paths. More precisely, in [START_REF] Qarabaqi | Statistical characterization and computationally ecient modeling of a class of underwater acoustic channels[END_REF], transmitter/receiver within a nominal channel geometry have multiple propagation paths with dierent lengths and dierent angles of arrival. Large-scale variations cause each propagation path length to deviate randomly and considerably from the nominal. In addition to that, small-scale variations cause every propagation path to be further scattered into a number of micro-paths. Hence, small-scale variations inuence the instantaneous channel response, and, consequently, the instantaneous signal-to-noise ratio (SNR). Therefore, small-scale channel variations are to be considered during a few consecutive packet transmissions. In contrast, large-scale variations impact the average SNR over longer periods of time. That's why, they are mostly signicant for the study of top-level system functions such as power allocation. Accordingly, the authors dene the instantaneous channel gain for a particular realization of the large-scale displacement and a particular realization of the small-scale variation for a system operating in the frequency range [f min , f min + B] as

G (t) = 1 B f min +B f min |H (f, t)| 2 df (4.3)
and the large-scale gain G which is the locally averaged instantaneous gain over small-scale realizations as

G = E G (t) (4.4)
where H (f, t) represents the time-varying channel transfer function that was derived in [START_REF] Qarabaqi | Statistical characterization and computationally ecient modeling of a class of underwater acoustic channels[END_REF]. Note that, in our work, we use the averaged instantaneous gain G to compute the needed transmission power to communicate a data packet between a pair of nodes in the network. While we rather use the instantaneous channel gain G (t) to determine if a data packet was successfully received by the intended receiver. More details are provided in the next section. For illustration purposes, we focus on an acoustic channel example whose parameters are depicted in Fig. 4.2. Let us assume that the transmitter and receiver are slightly displaced around their nominal locations by some heights ∆h T , ∆h R and a distance ∆d, and let us also assume that the surface height is displaced by some ∆h. Specically, let us suppose that all displacements are uniformly distributed, each on the interval ±5m. 4 Joint Routing and Energy Management in UW-ASNs 50 changes from 100 m to 3 km in steps of 200 m. For each value of the distance, there are 150 realizations of the acoustic channel. For every realization, the transmitter and the receiver are initially placed at the water surface within a depth of h = 100 m and using a bandwidth of 10 kHz to communicate. Once placed, the transmitter, the receiver, and the water surface randomly drift from their nominal locations by some heights ∆h T , ∆h R and ∆h, respectively. Besides, the distance separating the transmitter from the receiver randomly change by some ∆d. Specically, we suppose that all these displacements (∆h T , ∆h R , ∆h and ∆d) are uniformly distributed, each on the interval ±5m. As expected, as the distance separating the transmitter from the receiver increases, the channel quality will degrade resulting in a decreasing channel gain.

Power allocation

In a time-varying channel, the power allocation can be either adaptive or invariant. In the latter case, where no power control mechanism is applied a xed large margin is to be introduced to ensure that the SNR remains above a given threshold SN R 0 , regardless of the channel conditions. However, for energy eciency reasons, the transmit power consumption can be minimized if the transmitter has at its disposal some knowledge of the channel gain as stated in [START_REF] Qarabaqi | Adaptive power control for underwater acoustic channels[END_REF]. Ideally, if the exact fading gain G is known, the transmit power PT can be rigorously tuned accordingly such that the SNR is kept at the value SN R 0 . In this ideal case, and as introduced in [START_REF] Qarabaqi | Adaptive power control for underwater acoustic channels[END_REF], PT can be simply adjusted to

PT = P T 0 Ḡ/G (4.5)
where Ḡ is the mean of the actual exact channel gain G and P T 0 simply denotes the needed power to achieve a target SN R 0 in the absence of fading (G = Ḡ). P T 0 can be derived as follows:

P T 0 = P N × SN R 0 / Ḡ (4.6)
where P N is the noise power over B. Note that, in such ideal case, adopting such value for PT will always guarantee the successful reception of a data packet. However, as explained in [START_REF] Qarabaqi | Adaptive power control for underwater acoustic channels[END_REF], deriving PT using G can be challenging as the channel can not be fully known beforehand. Rather, an estimate Ĝ is to be used in place of the true actual gain G. In this case, a margin K has to be introduced to guarantee to some extent that the gap between the estimated and the true channel gain does not lead to an outage. The transmit power is then adjusted according to PT = KP T 0 Ḡ/ Ĝ. In our work, we suggest to consider Ĝ such that the probability that, the actual exact fading gain G is less than Ĝ, falls behind a given reliability level, R per . R per is to be decided by the network manager depending on the application requirements. In other words, we set Ĝ such that P (G < Ĝ) ≤ R per

(4.8)
It is worth noting that, in order to conceive a power allocation scheme, we rather consider G than Ĝ (t). Indeed, as previously explained, since large-scale variations inuence the average SNR over longer periods of time, it is rather more meaningful to consider the large-scale gain G to conceive a power allocation scheme. However, the instantaneous channel gain Ĝ (t) is more convenient for deriving the instantaneous signal-to-noise ratio (SNR) and hence to determine if a packet was successfully received or has encountered a failure. out that the transmission power is a non-linearly increasing function of distance. Note that by adjusting the transmission power according to PT the channel time-variability is now taken into consideration.

Recall that, once a communication is initiated using a given transmit power PT , the re- ceived signal power can then be determined according to the undergone instantaneous channel gain G (t). Let us consider a practical UWA communication between two nodes i and j separated by a nominal distance d and operating in a frequency bandwidth [f min , f max ] with a width B. Accordingly, the transmission from i to j will undergo an instantaneous channel gain of G(t) (i,j) . The received signal power can then be expressed as PR (t) (i,j) = PT (i,j) G(t) (i,j) (4.9)

Note that, the average received signal power during the reception period of time will help us decide if a data packet was successfully received, as explained in the next section.

Probability of successful packet reception

In our work, in order to further take into account the time-variability of the underwater acoustic channel, we introduce a success probability P i j over a link (i, j) which represents the probability of a successful reception by a node j for a transmission initiated by i using a transmission power PT (i,j) over a bandwidth B. In fact, a packet reception is considered successful by sensor j for a communication initiated by i during the time period [t 1 , t 2 ] if and only if

1 t 2-t 1 t 2 +D ij t 1 +D ij PR (t) (i,j) P N dt ≥ SN R 0 (4.10)
where D ij refers to the propagation time between i and j. It is worth noting that P i j is de- termined numerically for each link in the network using the underwater acoustic simulator developed in [START_REF]The simulator package[END_REF] and represents the fraction of successfully received packets. As expected, P i j will impact the total amount of trac received by every node in the network and thus the total energy consumption will be aected. Given that our objective is to balance the energy consumption throughout the network, P i j along with PT (i,j) will inevitably impact the load weights for every node in the network as detailed in section V.

4 Joint Routing and Energy Management in UW-ASNs 52

Energy management

Similar to the previous study, we assume that all the sensor nodes transmit periodically their reports to the sink node S where A denotes The average number of reports generated per unit of time by each sensor node. In this section, we start by evaluating the energy expenditure per sensor in an arbitrary corona B i with i ≥ 1. According to our routing strategy, each node in a given wedge W and a generic corona B i , (1 ≤ i ≤ K), can participate in two kinds of paths:

• paths originating at an underwater sensor located in the same wedge W but in a dierent corona B j with i < j ≤ K, in this case, the sensor in B i is only a forwarder;

• paths emanating from the same sensor in B i , in this case, the sensor in B i sends its own trac towards its predecessor.

Consequently, each sensor in a given wedge W and in corona B i is involved in all possible paths in W except those originating in one of the coronas B 1 , B 2 , ... and B i-1 .

In our routing strategy, each sensor node located at corona B i in a specic wedge W is able to send its generated reports to a possible next hop located in B i-1 or B i-2 , ... or B i-n , in the same wedge W where

n = d tx-max r (4.11)
For each possible next hop located in B i-1 or B i-2 , ..., or B i-n in a given wedge W , we associate a respective weight β i 1 , β i 2 , ..., β i n and a respective probability of a successful reception P i 1 , P i 2 , ..., P i n such that n p=1 β i p = 1, ∀i,1 ≤ i ≤ K. Thus, we can express the total number of packets per unit of time, A i , handled by a sensor in corona B i and wedge W as follows

A i = A + P i+1 1 β i+1 1 A i+1 +... + P i+j j β i+j j A i+j + ... + P i+n n β i+n n A i+n if i + j > K then β i+j j = 0 (4.12)
In this study, we introduced the success probability to take into account the timevariability of the underwater channel. Recall that, every pair of nodes have their own success probability which reects the probability of successful reception on their link, as introduced in section 4.3.3. By doing so along with the adjusted transmission power PT , the time-variability of the acoustic channel is now considered in our analytical model aiming at oine deriving the optimal load weights balancing the energy consumption throughout the network which makes the derived load weights more realistic.

Once the average load A i is expressed, the average transmission energy, E i T X , consumed by a sensor in corona B i and wedge W can be derived as follows:

E i T X = β i 1 A i E tx (r) + ... + β i j A i E tx (jr) + ...+ β i n A i E tx (nr) if i -j < 0 then β i j = 0 (4.13)
Likewise, the average reception energy, E i RX , consumed by a sensor in corona B i and wedge W can be expressed as follows

E i RX = P i+1 1 β i+1 1 A i+1 E rx (r) + ... + P i+j j β i+j j A i+j E rx (jr) +... + P i+n n β i+n n A i+n E rx (nr) if i + j > K then β i+j j = 0 (4.14)
Finally, the total energy consumed by a sensor in corona B i and wedge W is

E i = E i T X + E i RX (4.15)
4 Joint Routing and Energy Management in UW-ASNs 53

Recall that the goal of our work is to calculate the load weights for each possible next hop in such a way that the energy expenditure is balanced across all the coronas.

Consequently, our problem can be stated as follows:

Given K, r, d tx-max Find β i 1 , β i j , ..., β i n ∀i, 1 ≤ i ≤ K such that E 1 = E 2 = ... = E K subject to n j=1 β i j = 1, ∀i, 1 ≤ i ≤ K (4.16)
Note that for the derived optimization problem of Eq. (4.16), the number of unknowns is much greater than the number of equations. In fact, at each corona i we have to determine n unknown variables ( β i l 1≤l≤n ) resulting on a total number of unknowns equal to nK but with only 2K -2 equations (E 1 = E 2 = ... = E K and n j=1

β i j = 1, ∀i, 1 ≤ i ≤ K)
. Consequently, our optimization problem is impossible to solve and so is the energy balancing among coronas. Thus, it is impossible to achieve the perfect uniform energy depletion. For this reason, we deviate our goal to the one of approaching the optimal uniform energy depletion by determining, for each sensor node, the next possible hop with the associated load weight that better approaches the balanced energy expenditure among underwater sensors.

In what follows, we denote E rx (jr) as E j rx , E tx (jr) as E j tx and β i = β i l 1≤l≤n .

Iterative process

In this section, similar to our previous approach, we attempt to analytically approach the optimal uniform energy depletion iteratively. Accordingly, at the rst iteration, we suppose that we only have the corona B 1 . Thus, in this case, β 1

1 is equal to 1 since all the locally generated trac A of each sensor in B 1 is sent directly to the sink. In the second iteration, we suppose that a second corona B 2 is added. In this case, the previously established balance is perturbed since a new generated trac will be received from B 2 .

To re-arrange such imbalance, we compute β 2 1 and β 2 2 based on β 1 1 value. Note that β 2 2 denotes the trac weight that has to be sent directly from sensor in B 2 to the sink. Then, in general, we suppose that we achieved iteration j and hence the energy consumption between j coronas is balanced. Adding corona B j+1 will disturb the previously established balance since the total trac in each corona will inevitably increase. Knowing β 1 , β 2 ,..., β j , we settle once again our balance by determining β j+1 . Note that for the newly added corona B j+1 , A j+1 = A and E j+1 RX = 0. To recapitulate, β 2 is obtained after adding corona B 2 and as a result of writing E 2 = E 1 . By the same way, after adding corona B 3 , β 3 is obtained from E 3 = E 2 and E 3 = E 1 . More generally, at iteration j + 1, β j+1 is obtained from E j+1 = E j , E j+1 = E j-1 , ... and E j+1 = E 1 . Consequently, at each iteration j + 1, we strive for deriving the unknown vector β j+1 of size j + 1. To do so, we aim at expressing our problem as a system of linear equations, at each iteration.

Calculation of the cumulative trac

The cumulative trac emanating from downstream coronas is a key variable that directly inuences the energy consumption on every corona and hence the β i balancing vectors.

For this reason, let us start by iteratively expressing the cumulative trac at every corona.

For this purpose, at each iteration j + 1 (as explained above), corona B j+1 is newly added 4 Joint Routing and Energy Management in UW-ASNs 54 where A j+1 = A and thus A j-k ; ∀ 0 ≤ k ≤ j -1 should be newly derived since the amount of trac A j+1 will be forwarded to upstream coronas in order to reach the sink.

Theorem 1:

∀ 1 ≤ j+1 ≤ K ; A j+1 = A and ∀ 0 ≤ k ≤ j-1 ; A j-k = α 0k + k+1 l=1 α lk P j+1 l β j+1 l ×A where                    β j+1 l = 0, if l > min (n, k + 1) α 00 = 1; α 0(-1) = 1 α 0k = 1 + k m=1 α 0(k-m) P j-(k-m) m β j-(k-m) m ; α l(-1) = 0; α lk = 1, if l = k + 1 α lk = k+1-l m=1 α l(k-m) P j-(k-m) m β j-(k-m) m
Theorem 1 can be proven by mathematical induction. The proof is provided in Appendix A. Note that, as expected, in Theorem 1, A j-k ∀ 0 ≤ k ≤ j -1 linearly depends on β j+1 . Consequently, we aim at linearly expressing E i , ∀i, 1 ≤ i ≤ j + 1, as function of β j+1 and hence by writing E j+1 = E i , a system of linear equations can be established such that the balancing vector β j+1 can be determined.

Calculation of energy consumption in transmission and reception

Recall that our objective is to determine β j+1 for each iteration j + 1 that balance the energy consumption between B 1 , B 2 , ..., B j+1 . Consequently, at each iteration j + 1, we strive for deriving the unknown vector β j+1 of size j + 1. Recall that, as explained above, at iteration j + 1, all the β i , 1 ≤ i ≤ j are already computed. However, adding corona B j+1 will perturb the established balanced. To reinstate the previously established energy consumption balance, we aim at linearly expressing E j+1 and E i (∀ 1 ≤ i ≤ j) as function of β j+1 . By writing E j+1 = E j = ... = E 1 , we get a system of j + 1 equations with j + 1 unknowns. Recall that, for the newly added corona B j+1 , E j+1 RX = 0 hence E j+1 = E j+1 T X .

Therefore our system will be reduced to E j+1 T X = E j = ... = E 1 where

E i = E i T X + E i RX (∀ 1 ≤ i ≤ j). Let's start by expressing E j+1 T X . By denition, ∀ 1 ≤ j + 1 ≤ K, E j+1 T X = A j+1 l=1 β j+1 l E l tx
where β j+1 l = 0 if l > min (n, j + 1) .

(4.17)

Recall that our ultimate goal is to express our problem as a system of linear equations, at each iteration.

Consequently, E j+1 T X can be linearly expressed as as function of β j+1 as follows,

E j+1 T X = j+1 l=1 T X j+1 l β j+1 l where T X j+1 l = AE l tx . (4.18)
Now, let us derive E i T X and E i RX (∀ 1 ≤ i ≤ j) as function of β j+1 .

E i

T X can be expressed as follows

E i T X = T X i 0 + j-i+1 l=1 T X j-i l P j+1 l β j+1 l (4.19)
4 Joint Routing and Energy Management in UW-ASNs

55 where                β j+1 l = 0, if l > min (n, j -i + 1) T X i 0 = A i+1 q=1 β i q E q tx α 0(j-i) T X j-i l = A i+1 q=1 β i q E q tx α l(j-i) Similarly, ∀ 1 ≤ i ≤ j, E i
RX can be derived as follows

E i RX = RX i 0 + j-i l=1 RX j-i l P j+1 l β j+1 l + P j+1 j-i+1 β j+1 j-i+1 AE j+1-i rx (4.20)
where

             β i+p p = 0, if p > min (n, j + 1 -i) RX i 0 = j-i p=1 A × P i+p p β i+p p E p rx α 0(j-i-p) RX j-i l = j-i-l+1 p=1 A × P i+p p β i+p p α l(j-i-p) E p rx
The proofs for Eqs. 4.19 and 4.20 are provided in Appendices B and C respectively.

Problem statement

Now that we succeed to linearly express E j+1 T X , E i T X and E i RX , ∀ 1 ≤ i ≤ j, as function of β j+1 , we get our system of linear equations as expressed in Eq. 4.21.

∀ 1 ≤ j + 1 ≤ K ∀ 1 ≤ i < j + 1 E j+1 T X = E i T X + E i RX T X i 0 + RX i 0 = j+1 l=1 P j+1 l T X j+1 l β j+1 l - j-i l=1 T X j-i l + P j+1 l RX j-i l β j+1 l -A P j+1 j-i+1 E j+1-i rx + i+1 q=1 β i q E q tx β j+1 j-i+1 (4.21)
More concisely, our previously stated system can be written as follows

T X j+1 β j+1 = C (4.22)
where

C = C i 0 1≤i≤j such that C i 0 = T X i 0 + RX i 0 ; ∀ 1 ≤ i ≤ j and T X j+1 is a matrix of size (j, j + 1) such that T X j+1 = (T X i,l ) 1≤i≤j 1≤l≤j+1 , where T X i,l =                    P j+1 l T X j+1 l -T X j-i l -P j+1 l RX j-i l , if 1 ≤ l ≤ j -i P j+1 l T X j+1 l -A P j+1 j-i+1 E j+1-i rx + i+1 q=1 β i q E q tx , if l = j -i + 1 P j+1 l T X j+1 l , if j -i + 1 < l ≤ j + 1 (4.23)
Recall that β j+1 is a column vector such that β j+1 = β j+1 l 1≤l≤j+1

.

Note that, since j+1 l=1 β j+1 l = 1 , ∀ 1 ≤ j + 1 ≤ K then T X j+1 and β j+1 can be respectively reduced to a square matrix of size j and a vector of size j. Consequently, our system can be limited to only j equations with j unknown variables.

4 Joint Routing and Energy Management in UW-ASNs 56

It is worth pointing out that, if j + 1 ≤ n (n is the maximum number of coronas that can be reached by a sensor node), then we have a system of j equations with j unknown variables. Consequently, T X j+1 is a square matrix of size j. Hence, we can easily resolve T X j+1 β j+1 = C and thus the perfect uniform energy depletion is reached. However, once j + 1 strictly exceeds n, then our system is actually composed of j equations E j+1 = E j = ... = E 1 with only n unknown variables since β j+1 l = 0 for l > n. Consequently, we have much more equations than needed and hence achieving perfect uniform energy depletion is impossible. For this reason, we slightly deviate our goal to the one of minimizing the dierence in energy consumption among dierent coronas. Consequently, in this case, we reformulate our problem as follows Given K, r, d tx-max Find β j+1 min

β j+1 T X j+1 β j+1 -C subject to j+1 l=1 β j+1 l = 1 β j+1 l ≥ 0 , ∀1 ≤ l ≤ j + 1 (4.24)
Therefore, once the iteration number exceeds n, the previously stated optimization problem of Eq. 4.24 have to be solved instead of Eq. 4.22. This constrained nonlinear optimization problem can be easily solved using fminconfunction in the Matlab optimization toolbox [START_REF]Matlab help[END_REF].

Performance evaluation

In this section, we present a performance evaluation of our balanced routing solution along with a comparison study with the nominal communication range based data forwarding [START_REF] Ammari | Promoting heterogeneity, mobility, and energy-aware voronoi diagram in wireless sensor networks[END_REF] (d tx-max = r). The results are derived analytically. Indeed, in order to assess the performance of our proposal, we rst use the underwater acoustic simulator developed in [START_REF]The simulator package[END_REF] in order to compute the instantaneous gain, G(t) (i,j) , between any two nodes i and j. Note that, G(t) (i,j) will be derived by assuming that the transmitter and the receiver are initially placed at the water surface within a depth of 100m and using a bandwidth of 10Khz for communication. Moreover, we assume that the transmitter, the receiver, and the water surface randomly drift from their nominal locations by some heights ∆h T , ∆h R and ∆h, respectively. Besides, the distance separating the transmitter from the receiver randomly change by some ∆d. Specically, we suppose that all these displacements (∆h T , ∆h R , ∆h and ∆d) are uniformly distributed, each on the interval ±5m. Once derived, G(t) (i,j) will be used in our own developed Matlab simulator to determine numerically the average success probability P i j for each link in the network as well as the needed transmis- sion power PT (i,j) in order to derive the optimal load weight distribution that balances the energy expenditure among all underwater sensors in the network. The algorithm bellow provides a procedure that clearly states the dierent phases of our work. Note that, in our simulation scenario, any failed transmission will be subject to retransmissions until the successful reception.

Algorithm: Dierent simulation phases.

end for

According to our simulation model, the underwater sensor nodes perform continuous monitoring of the supervised circular area of radius R. Our circular sensor eld centered at the sink is partitioned into disjoint concentric coronas of constant xed width r. Recall that, we assume that underwater sensors are manually deployed according to the deployment pattern of Fig. 4.1. The proposed deployment strategy considers a 2-dimensional shallow underwater sensor network. A set of sparse sensors is anchored to the ocean bottom and endowed with a quite long rope along with a oating buoy to help the sensor reach the surface. Each underwater sensor periodically reports with rate A the locally generated data to the sink over several hops. At each hop, the trac emanating from the local sensor must be merged with route-through trac. Each packet is forwarded from the source to the sink by crossing coronas located in the same wedge. The parameters setting in our analysis are given in Table 4.1. We rst analyze the results regarding our balanced routing strategy for a circular sensor eld of radius R = 1500 m and corona width r = 100 m resulting in a total number of coronas equal to 15. Each sensor in each corona is supposed to generate 0.08 packet/s. We study the impact of using variable transmission powers with dierent values of n on both packet load and energy consumption for every corona. First, let us discover β n = β i l 1≤l≤n 1≤i≤15 matrix of our balanced routing scheme when n is set equal to 3, 5 and 7.

We want to point out that the β matrix is derived with the purpose of evenly distributing the energy consumption among dierent coronas. the main two components of energy consumption. On one hand, since the reception energy is almost constant, hence sending over longer distance will reduce the total number of hops to reach the sink and thus the total energy consumption is minimized. On the other hand, the transmission energy is increasing with distance. More than that, the increasing rate of the transmission energy as a function of distance is also raising as shown in Fig. 4.5.

Accordingly, it is highly preferred to send over short distances especially when the sensor is far from the sink. Reconciling these two opposites requirements leads to favoring the trac forwarding directly to the sink, if the sink is reachable otherwise the trac should be evenly distributed between upstream coronas as reported by Tables 4.2, 4.3 and 4.4. For instance, according to Table 4.2 when n is set equal to 3, much more packets should be sent to the 3-hop away corona when the sink can be directly reachable namely for coronas 1, 2 and 3. Indeed, underwater sensors in the second and third corona should send more than 90% of their accumulated trac directly to the sink. Whereas, sensors in other coronas have to evenly distribute their trac among all upstream coronas in order to balance the energy consumption. Similar results can be deduced for n = 5 and n = 7. Indeed, according to Tables 4.3 and 4.4, as long as the corona number is less or equal to n, most of the trac should be forwarded directly to the sink using the highest possible transmission power. While farther coronas have to evenly distribute their trac to all possible upstream coronas in order to achieve fair energy consumption among all the underwater sensors. 1. This amount of accumulated trac at corona 1 is highly decreased (less than 0.29 packet/s) with our balanced routing solution when n = 3, a further decrease is achieved with n = 5 and a further gain with n = 7 compared to nominal based data forwarding.

β matrix when n = 5. Corona i Corona (i -1) Corona (i -2) Corona (i -3) Corona (i -4) Corona (i -5)
This increasing gain is more importantly highlighted in Fig. 4.7. In fact, Fig. 4.7 shows the energy consumption for each sensor in the corresponding corona. Accordingly, a 92% of energy saving is achieved at corona 1 when n = 5. It is worth noting that our balanced routing strategy with n ∈ {3, 5, 7} leads to a maximum energy expenditure of 5 mW , 3 mW , 2.2 mW , respectively. However, according to the nominal communication range based data forwarding, a maximum energy consumption of 0.74W is achieved as expected at corona 1. Consequently, an energy saving of 50%, 70% and 78% are accomplished thanks to our balanced routing scheme when n ∈ {3, 5, 7}, respectively. We would like to point out that the energy consumption per corona is not proportional to the packet load distribution as shown in Figs. 4.6 and 4.7.

Indeed, as depicted in Fig. 4.5 the energy expenditure did not depend linearly on the transmission distance which justies the non-proportionality between packet load distribution and the energy consumption. Consequently, balancing the energy consumption does not really mean balancing the packet load distribution. Now, let us evaluate the gain that can be achieved by our balanced routing solution using variable transmission power over the nominal communication range based data for-Table 4.4: β matrix when n = 7. warding (d tx-max = r) for dierent eld radiuses as well as dierent corona width. Note that this comparison study is mainly conducted in terms of energy consumption and network lifetime. From the energy depletion point of view, we consider the maximum consumed amount of energy among all coronas. Regarding network lifespan, we dene the network lifetime T simply as the time for the rst node in the network to drain its energy budget. In other words, the network lifetime is given by

Corona i Corona (i -1) Corona (i -2) Corona (i -3) Corona (i -4) Corona (i -5) Corona (i -6) Corona (i -7)
T = E init max E(U ) (4.25)
where E init is the initial amount of energy provided to each sensor node and E(U ) is the consumed energy by U an arbitrary underwater sensor in our eld. nodes to adjust their transmission powers among n dierent levels, leads to packet load distribution among all the upstream coronas and hence we succeed to balance the energy consumption. Note that, for a eld radius of 2000 m our balanced routing solution achieves up to 51% of energy saving when n = 3. A further energy saving of 34% is achieved with n = 5 and a further saving of 66% with n = 20. Consequently, we recommend the use of n = 5 as a best compromise between increasing the energy savings and decreasing the number of variable transmission powers. Note that a smaller number of power levels is of interest for practical implementation.

A straightforward study showing the optimal value of n, in terms of energy consumption, as function of eld radius when the corona width remains xed and equal to 100 m was also conducted. As expected, the optimal number, n opt , is equal to R r . Indeed, by allowing each sensor to distribute its accumulated trac among all upstream coronas and especially to directly reach the sink will highly contribute in balancing the energy consumption and thus the network lifespan is improved. That being said, can we conclude that for any values of eld radius and corona width, as we extend the number of allowed transmission power levels (i.e. n) the energy savings is increased. To answer this question, we evaluate the energy consumption for various corona widths.

In order to gain more insight regarding the system performance, let us closely inspect the energy consumption as well as the network lifetime for various corona widths. To achieve this, we consider a xed eld radius of 5000 m while varying the corona width from 100 m to 1100 m. According to Figs. 4.12 and 4.13, for each value of n there is an optimal value of the corona width Cw opt which provides the minimum energy consumption and hence the maximum network lifetime. Indeed, when the corona width increases up to Cw opt the energy expenditure decreases. In fact, raising the corona width reduces the number of coronas and consequently the packet load is reduced. However when the corona width exceeds Cw opt the energy expenditure increases even though the packet load is reduced.

The reason behind this is the non linearity of transmission power as function of distance. Indeed, according to Fig. 4.5, for high value of transmission range, the transmission power is exponentially increasing leading consequently to high energy depletion.

Comparing our balanced routing schemes (n > 1) with the nominal range forwarding (n = 1) for dierent values of corona width, we observe that the schemes behave dierently. Indeed, for a corona width equal to 200 m, the minimum energy consumption is achieved by our balanced routing strategy when n = 7 while the maximum energy depletion is achieved by the nominal communication range based data forwarding. However, for a corona width equal to 900 m, the least energy consumption is achieved with the nominal communication range based data forwarding while the highest energy consumption is fullled with our balanced routing strategy when n = 5. Consequently, there clearly exists a compromise between the number of transmission power levels (n) and the energy consumption. Indeed, on one hand, as we increase n, we allow the trac load to be much more distributed among all the upstream coronas and hence a balanced energy consumption is achieved. On the other hand, increasing n raises the energy consumption since the farthest coronas can be reached. As a conclusion, we can state that for each corona width there is an optimal n value for which the energy consumption is minimized as depicted in Fig. 4.14. Moreover, for each n, there is an optimal corona width for which the network lifetime is optimized.

Combining both results, and according to Figs. 4.12 and 4.13, the maximum network lifetime is achieved by our balanced routing solution when n = 5 for a corona width equal to 300 m.

Conclusion

In this chapter, we presented our upgraded routing strategy that takes into account more challenging features of the underwater channel. Assuming that each underwater node is able to dynamically adjust its transmission power up to a predened number of levels, we determined for each source sensor the set of possible next hops with the associated transmission power and associated load weight that lead to fair energy consumption and 4 Joint Routing and Energy Management in UW-ASNs hence the energy sink-hole problem is overcome. To do so, we developed a comprehensive analytical model that iteratively derives for each source sensor the appropriate load weight along with the associated transmission power. Analytical results show that signicant lifespan improvement is achieved by our balanced routing scheme compared to the nominal communication range based data forwarding. In the next chapter, we will present MC-UW-MAC: a collision avoidance energy ecient multi-channel MAC protocol for UW-ASNs.

MC-UWMAC is a novel low power multi-channel MAC protocol which introduces two novel joint procedures to avoid collisions in UW-ASNs. Introduction

Due to the harsh and challenged environment characteristics which faces network protocols for UW-ASNs, acoustic underwater communications are expected to achieve lower throughput while consuming larger amount of power compared to their terrestrial radio counterparts. To overcome theses serious challenges and enhance the network performance, Medium Access Control (MAC) protocol for UW-ASNs is of paramount importance since the MAC layer protocol is responsible for coordinating nodes' access to the shared wireless medium. Indeed, the primary task of a MAC protocol is to prevent simultaneous transmissions and resolve transmission collisions of data packets while guaranteeing low channel access delays, fairness among the nodes in energy eciency way especially for energy constrained networks such as UW-ASNs. Thus, a MAC layer protocol in UW-ASNs has great importance on the network utilization as it has to overcome harsh underwater acoustic channel in addition to its fundamental role in network. Collisions are one of the most important obstacle that it has to be avoided to the most possible extent by MAC protocols, especially in underwater acoustic environment. Indeed, the collision problem is much more serious in UW-ASN since it dramatically decreases the network performance especially in terms of throughput and energy consumption [START_REF] Chao | Multiple-rendezvous multichannel mac protocol for underwater sensor networks[END_REF]. Note that, the impact of collision is even worse in heavily loaded UW-ASNs. Hence, collisions in UW-ASNs are so costly in terms of energy and throughput and hence can not be tolerated and they have to be avoided to the most possible extent. In this chapter, a multi-channel MAC protocol (MC-UWMAC) for UW-ASNs is proposed and evaluated. Our ultimate aim is to conceive a low power MAC protocol especially tailored for sparse heavily loaded underwater sensor networks that highly improve the network throughput by avoiding collisions to the most possible extent without requiring any extra control packet exchange.

To design a multichannel MAC protocol, general multichannel issues such as when and which node can use which channel must be addressed. Traditionally, channel negotiation is done through control message exchanges. Such mechanisms are however not ecient in UW-ASNs because of long propagation delay and considerably high transmission power.

Consequently, such negotiation based techniques are expected to highly increase the endto-end delay while introducing extra power consumption especially in UW-ASNs due to signicant signaling overhead. Therefore, in UW-ASNs, these channel assignment and transmission scheduling problems should be solved in an energy-ecient way, preferably without requiring extra control packets exchange. Moreover, the inherent missing receiver 5 MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 65 problem of multichannel communication scheme, which occurs when a sender fails to get in touch with its intended receiver because they do not reside on the same channel, has to be carefully addressed in underwater acoustic context.

To handle all of the aforementioned issues, we dene and adopt the concept of singletonintersecting quorum systems in a way such that the MC-UWMAC has several attractive features. First, equipped with one modem, each sender will have a dedicated data channel to communicate with a given neighbor such that potential collision among neighbors is at most avoided in any data channel. Indeed, according to MC-UWMAC, each underwater sensor will be assigned a subset of data channels such that a unique and dierent data channel is dedicated for possible communication with every neighbor. Note that, this unique data channel allocated for every pair of nodes is dierent from all the others data channel allocated to every possible pair of nodes in the neighborhood. As such, the hidden node problem is avoided during data communication. Second, thanks to the use of a common control channel along with an availability table, each sender is guaranteed to meet its receiver and hence, the missing receiver problem is solved. Moreover, even with the use of a unique control channel, MC-UWMAC succeed to guarantee to some extent a collision free handshaking on the common control channel. In fact, MC-UWMAC targets to allocate to each sensor node in a given neighborhood, a unique 2-hop conict free slot of time for possible handshaking on the single slotted common control channel which reduces the energy wastage due to possible damaging collision during handshaking. Third, credited to the separation of control and data channels, control and data packets transmissions in MC-UWMAC will not only ovoid collision among them but also may take place at the same time which will improves the network throughput. Simulation results conrm that the proposed MC-UWMAC signicantly improves the network throughput and energy eciency especially for heavy loaded trac pattern.

The remainder of this chapter is organized as follows. Section 5.2 presents a detailed description of our MC-UWMAC. Section 5.3 provides a collision study in MC-UWMAC.

The results are provided in Section 5.4, where we compare the performance of our proposal with a related existing multi-channel MAC protocol MM-MAC [START_REF] Chao | Multiple-rendezvous multichannel mac protocol for underwater sensor networks[END_REF]. This chapter concludes with a summary of our conclusions and contributions.

MC-UWMAC:

A multi-channel MAC protocol for UW-ASNs

Why single rendezvous multi-channel under-water MAC protocol

Using a multichannel media access control (MAC) protocol, dierent devices can transmit in parallel on distinct channels. This parallelism increases the throughput and can potentially reduce the end-to-end delay. One of the important issue with multichannel MAC protocol is the missing receiver problem. Indeed, operating on multichannel may expose the nodes to lose contact with their intended receiver and thus wasting time looking for it with the possibility of failing to get in contact with. Multi-channel protocols dier in how devices overcome the missing receiver problem and hence how do they agree on the data channel to be used for transmission and how they resolve potential contention for a channel. These choices aect the delay, energy consumption and throughput characteristics of the protocol. On one hand, using a dedicated common control channel completely avoids the missing receiver issue as well as gives the nodes a complete view about the data channels availabilities which is expected to reduce the probability of collision and hence more energy savings is achieved. However, this single control channel might become a bottleneck especially in dense overloaded networks. On the other hand, using multiple rendezvous multi-channel protocol will overcome the single control channel bottleneck 5 MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 66 but further expose the network to the missing receiver problem. Moreover using multiple rendezvous protocol will prevent any sensor node from acquiring a complete an accurate knowledge of data channels availabilities which may increase the probability of collision especially during data communication. That being said, we believe that adopting a single rendezvous multi-channel MAC protocol for UW-ASNs that are naturally sparse can be highly justied and benecial since it will avoid any unnecessary extra message exchange to nd the intended receiver and decrease collision probability in a given data channel since every node has a complete view of the data channels availabilities. Moreover, it is completely true that our proposed MAC protocols targets especially sparse heavy loaded UW-ASNs which may insinuate that the common control channel will be highly solicited and thus the collision problem may be worsen, thing that is not at all true. Indeed, once a handshaking is successfully achieved on the common control channel, MC-UWMAC allows every source node to send as much data packets as it has in its own buer for the intended receiver on the dedicated data channel. Thus, one RTS/CTS exchange on the common channel will be enough to handle multiple data packet transmissions to the same receiver on the same data channel and hence the collision problem will not be accentuated on the common control channel.

Why slotted control channel

In MC-UWMAC, the control channel is chosen to be slotted. Slots of constant duration are grouped into TDMA frame (or shortly the frame), of length n, and numbered. Nodes access the common channel according to the predetermined TDMA schedule that species in details which nodes are to send in each slot of the frame. In MC-UWMAC, we opt for TDMA access technique rather than carrier sensing one in order to ensure to some extent a collision free communication over the common control channel in addition to the guaranteed one over any data channel. Indeed, carrier sensing is not that ecient any more in underwater acoustic sensor networks.

Indeed, in simple contention-based single rendezvous multichannel MAC protocols, the data channel assignment is normally integrated into the RTS/CTS handshaking process on the control channel. However, for single-transceiver contention-based multichannel schemes in long-delay underwater networks, simple RTS/CTS negotiation approaches are not as ecient as they used to be in terrestrial wireless sensor networks. Indeed, in addition to the traditional multi-hop hidden terminal problem for the single channel network, they will more suer from two new hidden terminal problems that are intrinsic in the new underwater acoustic network context: multichannel and long-delay hidden terminal problems.

Multichannel hidden terminal problem

Multichannel hidden terminal problem was rst introduced in [START_REF] So | Multi-channel mac for ad hoc networks: Handling multi-channel hidden terminals using a single transceiver[END_REF] for nodes with single transceiver. Indeed, if the node has only one transceiver, it can listen either on the control channel or on a data channel, but not on both which may lead the node to lose control of the data channels availabilities and hence potential collisions on busy data channels may occur. For instance, as shown in Fig. 5.1, suppose that two nodes, say A and B, previously

Long-delay hidden terminal problem

The inherent long propagation delays of the underwater acoustic channel introduce another kind of hidden terminal problem where two pairs of neighbor nodes in the same vicinity may succeed to reserve the same data channel nearly at the same time because of long propagation delay, as shown in Fig. Our MC-UWMAC protocol is proposed to tackle eciently these new challenges. Opting for time division multiplexing technique was the rst step to cope with the triple hidden terminal problem in addition to our quorum and slot allocation procedures explained in section 5.2.4 Indeed, by assigning to each node its own slot, we avoid concurrent simultaneous reservation of the same data channel and hence the long delay hidden terminal problem is overcome. As for the multichannel hidden terminal problem, it will be eciently addressed by our quorum construction and allocation procedures.

According to MC-UWMAC, the control channel is temporally shared by all nodes in UW-WSN, and communication is halfduplex: node v cannot send one message and receive another simultaneously. All node clocks are synchronized to a common global time [START_REF] Chirdchoo | Mu-sync: A time synchronization protocol for underwater mobile networks[END_REF],

5 MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 68 We dene the slot time as

T SLOT = T RT S + T CT S + 2 × T P ROP (5.1)
where T RT S and T CT S refer to the RTS and CTS messages transmission times in the common channel, respectively. Note that here, the main objective of deploying RTS/CTS scheme is to establish a rendezvous with the intended receiver rather than avoiding collision like in CSMA scheme. For more details the reader is referred to section 5.2.5. T P ROP refers to the propagation time over the transmission distance R t .

T P ROP = R t V s (5.2)
where V s refers to the nominal speed of sound in the water V s = 1500m/s.

In large TDMA-based multihop wireless sensor networks, slots within a xed-length frame need to be spatially reused in order to increase the network throughput. In other words, the same slot number has to be shared among several nodes geographically quite separated from each other. Although the undeniable benets of the spatial reuse, it may cause the so called slot assignment conicts between nodes. A k-hop slot assignment conict is dened in [START_REF] Milica | Reduced-frame tdma protocols for wireless sensor networks[END_REF] as one in which a pair of nodes k hops away is assigned the same slot. The presence of k-hop slot assignment conicts, especially where k ≤ 2, causes collisions that should be properly handled. Contrarily, slot assignment is dened to be a 2hop conict-free if the slot S(v) used by a node v is not reused in the 2-hop neighborhood of v, N ≤2 (v) and hence collision is completely mitigated. In our work, we will propose our own slot assignment procedure aimed at being 2-hop conict free without any extra message exchange between the nodes. Our goal is to provide to the most possible extent a collision free communication while avoiding any extra message exchange among nodes as such the network throughput highly increases and so does the energy eciency.

By taking advantage of the underwater acoustic networks characteristics, namely low density, we aim at closely approaching the 2-hop conict-free slot assignment, while using a reduced frame length of size n, where n is the maximum neighborhood size and most importantly without imposing any message exchange among neighboring nodes which makes our protocol more energy ecient.

Overview

MC-UWMAC is a multi-channel medium access control protocol designed for multi-hop underwater acoustic wireless sensor networks using a single modem to emulate multiple transceiver solutions. MC-UWMAC operates on single control channel and multiple data 5 MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 69 channels of total number N = n(n-1)

2
where n is the maximum neighborhood size in the network. Specically, there is a common slotted control channel and N equal-bandwidth data channels. In the common control channel, which is the default active channel, time is divided into series of frames. Each frame is further divided into n slots such that every node in a neighborhood will be assigned a unique slot of duration T SLOT for possible handshaking. Indeed, to enable a data communication between a sender A and a receiver B, A and B must rst successfully exchange RTS and CTS packets during A's slot then they have to switch to the same appropriate data channel. Note that, once A and B are in the appropriate data channel, they may remain as long as A has packets for B provided that they announce the end time of communication to their respective neighbors during the handshaking. In other words, the time in MC-UWMAC is only slotted according to the control channel as opposed to MM-MAC [START_REF] Chao | Multiple-rendezvous multichannel mac protocol for underwater sensor networks[END_REF] where the frame is divided into control and data periods. Consequently, we may expect from MC-UWMAC to achieve better network throughput as the frame length is of reduced size.

According to MC-UWMAC, to appropriately select a data channel for possible communication, each node u will be assigned a subset of data channels S qu of length (n -1) that may be used by u for data communication with the (n -1) possible neighbors. Any node v , neighbor of u will be assigned another subset of data channel S qv dierent from S qu but they intersect exactly in one common data channel that will be used by u and v for their communication. Hence at maximum n dierent subsets will be assigned in any given neighborhood provided that the respective subsets of any two neighbors should satisfy the non empty intersection property for possible data communication. As explained in the next section, we will show how to build the subsets of data channels and how to allocate them such that n dierent subsets will be sucient enough to serve all the nodes in the network while achieving a collision free communication among them. Note that, in MC-UWMAC, we impose that the pairwise intersection between S qu and any S qv , v neighbor of u, is a singleton CH uv such that any two neighbors will have at their disposal a unique data channel to communicate on, for collision avoidance purposes. According to MC-UWMAC, the following property should be satised ∀uand∀ {v, w} ∈ N e (u) , w = v, => S qu ∩ S qv = S qu ∩ S qw (5.3) where N e (u) is the list of u's one-hop neighbors. In other words, data channel CH uv will be only allocated for data exchange between u and v, meaning that no other neighbor of u or v is using CH uv to communicate with u or v , respectively. Therefore, not only collisions among neighbors is mitigated but also collisions due to hidden node is completely avoided and hence a collision free communication is guaranteed on data channel. Note however that the same CH uv may be reused in a two hop far neighborhood which boosts the spatial reuse inside the network. To recapitulate, MC-UWMAC aims at achieving a 2-hop conict-free data channel subset assignment as shown in Fig. 5.4. By doing so, we aim at increasing the network throughput while being extremely energy ecient by completely mitigating collisions in any data channel. Moreover, MC-UWMAC proposes a data channel allocation scheme that allows each node to know in advance its own subset of data channels and which data channel to be used with every neighbor, for possible communication, without any extra packet exchange provided that every node knows its own geographical coordinates as well as the ones of its one hop neighbors. Given that the UW-ASNs are sparse, we expect that acquiring such information is easily manageable. Consequently, and more importantly we further decrease the energy consumption by avoiding any overhead that might be produced to appropriately select an available free data channel as in CUMAC [START_REF] Zhou | Handling triple hidden terminal problems for multichannel mac in long-delay underwater sensor networks[END_REF] , where the nodes have to cooperatively negotiate the list of available data channels using RTS/Beacon/CTS. Moreover, according to MC-UWMAC, during the data communication between u and v, we guarantee a collision free communication since CH uv is supposed to be only used by u and v and hence the multichannel hidden terminal is mitigated. Most importantly, as explained in the next section, our proposed data channels allocation scheme does not require any extra packet exchange to guarantee that almost all the neighbors in a given node neighborhood will select dierent data channel sets as represented in the example of Fig. 5.4 where for every node in the network, a unique and dierent data channel is associated to each one of its neighbors.

It is worth pointing out that, we will adopt the same procedure for the slot allocation on the control channel among neighboring nodes. Here again n slots will be sucient enough to highly decrease the collision probability during handshaking on the control channel,

where n is the maximum size of one hop neighborhood. That being said, MC-UWMAC does not fully guarantee the exclusive 2-hop conict free assignments of data channel sets as well as time slots, that's why MC-UWMAC will be supplied with a backo mechanism (as explained in 5.2.5) to deal with unlikely collision.

Data Channels subsets construction and allocation

In this section, we present the most important concepts in our protocol, namely 1) How to build the n subsets of data channels of length (n -1) each, such that the pairwise intersection between any 2 sets is a unique singleton and 2) How to allocate them to sensor nodes such that to maximize the probability of collision free communication. Note that, the same data channel subsets assignment procedure will be used for time slot allocation.

MC-UWMAC Quorum construction

The main idea behind MC-UWMAC is how to build our subsets of data channels of length (n -1) each, such that we guarantee the unique singleton intersection among pairwise neighboring nodes, and hence the multichannel hidden terminal problem is avoided without requiring any extra messages exchange among nodes. Thus, the collision free communication on any given data channel is insured. To do so, we utilize the concept of quorum systems that have been widely used for mutual exclusion in distributed systems [START_REF] Luk | Two new quorum based algorithms for distributed mutual exclusion[END_REF] and for MAC protocol design in wireless networks [START_REF] Camarda | Collision free mac protocol for wireless ad hoc networks based on bibd arthitecture[END_REF], [START_REF] Chao | An adaptive quorum-based energy conserving protocol for ieee 802.11 ad hoc networks[END_REF], [START_REF] Jiang | Quorum-based asynchronous power-saving protocols for ieee 802.11 ad hoc networks[END_REF], [START_REF] Chao | A quorum-based energy saving mac protocol design for wireless sensor networks[END_REF] and recently for UW-ASNs [51] [71]. A quorum system can be dened as follows.

Given a universal set U = {u 1 , ..., u N }, a quorum system Q under U is a collection of non-empty subsets of U , each called a quorum, which satises the intersection property: ∀{G, H} ∈ Q; G ∩ H = ∅.

Elements of a quorum system are simply called quorums. For example, Q={{1,2},{1,3},{2,3}} is a quorum system under U ={1,2,3}. There are many quorum systems, such as the cyclic quorum system, the grid quorum system, and the torus quorum system. We create our own quorum system that satises the functional requirements of our multichannel MAC 5 MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 71 protocol: MC-UWMAC. Accordingly, our quorum system will be mainly used for data channel selection between any two neighbor nodes as opposed to MM-MAC protocol [START_REF] Chao | Multiple-rendezvous multichannel mac protocol for underwater sensor networks[END_REF],

where the quorum system is used to select communication slots as explained in [START_REF] Chao | Multiple-rendezvous multichannel mac protocol for underwater sensor networks[END_REF]. In other words, every quorum in our system represents a subset of data channels to be allocated to an underwater sensor node. The rst main characteristic that should be satised by our target quorum system is that the pairwise intersection between any 2 quorums is a singleton. Therefore, any two neighbors will have at their disposal a single common data channel that will be used for possible data exchange between them. Consequently, our target quorum system can be now dened as follows.

A quorum system Q under U = {u 1 , ..., u N }, is said to be a singleton-intersecting quorum system if the pair-wise intersections among quorums is singleton. In other words,

∀G, H ∈ Q; G ∩ H = {u i }.
For instance, the quorum system Q ={{1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}} is a singleton-intersecting quorum system under U ={1,...,7}. Note that Q in this example is the nite projective plane quorum system used by Maekawa [START_REF] Maekawa | A n algorithm for mutual exclusion in decentralized systems[END_REF] in his mutual exclusion algorithm. Now, the second main characteristic that should be also fullled by our target quorum set is the unique singleton intersection between any two quorums. In other words, any pair of quorums should intersect in a unique dierent element from all the other possible pairwise intersections. Therefore, two pairs of nodes will never have the same common data channel to communicate on and hence simultaneous collision free communication emanating from neighbors can take place. Formally, our target quorum system can be nally dened as follows:

A singleton-intersecting quorum system Q under U = {u 1 , ..., u N }, is said to be a unique singleton-intersecting quorum system if the pair-wise intersections among quorums is a unique dierent singleton. In other words, ∀{G, H, I, J} ∈ Q; G = H = I = J; G∩H = I ∩ J and G ∩ H = G ∩ I.

For instance, the nite projective plane quorum system Q = { {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6} } is a non unique singleton-intersecting quorum system, while the quorum system Q ={{1,2,3},{1,4,5},{2,4,6},{3,5,6}} is indeed a unique singleton intersecting quorum system.

The MC-UWMAC protocol dictates that the data channel allocation scheme provides each underwater node with a set of data channel such that each node neighborhood of maximum size n has to be a unique singleton-intersecting quorum system. We devote the next section to show how to construct a unique singleton intersecting quorum system containing n quorums, where n is the maximum neighborhood size, each quorum is of size (n -1) , (n -1) is the maximum number of neighbors for each node, using the minimum number of distinct element {u 1 , ..., u N }.

Theorem

Given n, the system Q

= {S 1 , ..., S n } where              S 1 = {1, 2
, ..., n -1}, ∀1 < j ≤ n; card(S j ) = n -1 and S j = {(S 1 ) j-1 , ..., (S j-1 ) j-1 , (S j-1 ) n-1 + 1, ..., (S j-1 ) n-1 + (n -j)} (where(S p ) q refers to the q th element of S p ). is a unique singleton-intersecting quorum system under U ={1, ..., N } where N , the number of distinct element, is equal to

n(n-1) 2
. proof

• First, let us show that Q = {S 1 , ..., S n } is a quorum system where each quorum is of length (n -1).

According to Eq. 5.7, n denotes the maximum neighborhood size. Note that, once the p is computed, the n value has to be updated accordingly. For instance, if the maximum neighborhood size is 7 then p will be set equal to 3 and hence the total frame length as well as the number of quorum is n = 9. (x u , y u ) are the relative coordinates of a node u inside its own cell of side R C . Once our eld is virtually divided into a grid of cells of side R C , we further partition every cell into smaller ones of side R C p such that the total number of cells is p 2 = n. By doing so, we aim at locating every sensor inside a unique cell and hence it will be assigned a unique slot number. Note that, (i u , j u ) are the small cell indexes inside the corresponding large one of side R C and q u is the small cell number as shown in Fig. 5.5. q u will be the slot number assigned to node u. The proposed channel allocation scheme is expected to highly decreases the probability of collision while guaranteeing multiple simultaneous data communication which improves the overall network performance especially in terms of throughput and energy eciency.

Similarly, a node u will choose the slot s qu in the control frame. As such, we guarantee that the quorum and slot allocations are unique and most importantly without any extra message exchange among nodes. It should be noted that more than one node may select the same quorum number and thus the same slot number, if they reside in the same small cell.

Note however that, even in this case, collisions are not systematic as it can be expected.

For more details, the reader is referred to section 5.3, where a thorough collision study is provided. In the worst case, suppose that more than one node are sharing the same quorum, thus, they will have (n -1) common data channels to communicate on, as opposed to MM-MAC protocol where choosing the same quorum set will prohibit any communication between those nodes. Hence, in MC-UWMAC, depending on the announced data channel occupancy in their respective neighborhoods, these nodes may choose the smallest available data channel number during the handshaking process.

Protocol description

In this section, we provide a detailed description of our MC-UWMAC protocol by describing the sender and the behaviors.

Sender behavior

By default, every sensor node in the network listen on the common channel. A node m having a packet to transmit will send a RTS message on its scheduled slot s qm to a well dened receiver. Note that, the RTS packet basically includes the destination identier, the end time of data transmission depending on the number of packets in the queue destined to the receiver. In order to avoid triggering a communication with a busy node, every underwater sensor must maintain a table called hereafter meeting table. This table simply contains a list of in-progress communications with their associated members as well as corresponding end times. Before transmitting, a node m rst check its meeting table. If the potential receiver is busy, then m will defer its transmission till the mentioned end time of communication in its meeting table. Otherwise, the sender proceed sending its RTS on its scheduled slot s qm . If the RTS is successfully received then the receiver will send back a CTS and move to the appropriate data channel. After receiving the CTS, the sender may immediately move to the intended data channel. It is worth pointing out that if the sender does not receive the CTS then it will presume a collision and hence defer its access and go through the backo procedure as explained in section 5.2.5.

Receiver behavior

Having no packet to send or waiting for its own slot, each underwater sensor node has to listen on the common control channel. Once a RTS packet is correctly received, rst the sensor node veries if it is the actual target receiver of the RTS packet. If so, the receiver starts by sending a CTS conrming the data communication on the well known data channel as such any useless possible invitation from one of the receiver's neighbor is avoided. However, if the received RTS was intended to another node, the overhearer keeps track of the sender and receiver identiers along with the presumed data channel as well as the end time of communication in the meeting table. By doing so, the overhearer avoids triggering a communication with a busy node (the sender or the receiver). Similarly, the overhearer keeps track of all the previously mentioned information if it receives a CTS packet. Therefore, any underwater sensor node wishing to send a data packet to a well dened node, rst it has to check its meeting table. If the intended node is not busy, the node will proceed sending a RTS packet in its own slot. Otherwise, it has to defer its RTS transmission till the precised end time of communication in the meeting table.

Note that, since the underwater sensor networks are by nature sparse , each sensor node will have only a few neighbors. Consequently, the meeting table is manageable even with very limited memory resources.

The working process of MC-UWMAC from the sender and receiver sides are shown in the owcharts of Fig. 5.6 and Fig. 5.7.

5 MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 77

More bit

An important detail of the MC-UWMAC protocol, which is also found in a number of MAC protocols for sensor networks [START_REF] El-Hoiydi | Wisemac: an ultra low power mac protocol for multi-hop wireless sensor networks[END_REF] [74], is the presence of a more bit in the header of data packets. When this bit is set to 1, it indicates that more data packets destined to the same sensor node are waiting in the buer of the transmitting node. When a data packet is received with the more bit set, the receiving sensor node continues listening on the same data channel without sending the acknowledgment. Consequently, remaining on the same data channel, the sender will proceed transmitting the following data packet right after sending the previous one, especially without getting back to the common channel in order to take a new appointment (i.e; by sending a new RTS) with the same previous receiver.

Therefore, the end-to-end delay is decreased and the throughput owing through a given forwarder is increased.

Collisions processing in MC-UWMAC MC-UWMAC is conceived to provide collision free communication since the ultimate objective of MC-UWMAC is to maximize the throughput. Indeed, recall that thanks to our quorum set construction, the multichannel hidden terminal problem is avoided. Moreover, thanks to the TDMA-based communication on the common control channel, we avoid the long delay hidden terminal problem. Nevertheless, in some MC-UWMAC settings, collisions may occur since our slot and quorum assignment procedure is not completely 2-hop conict free. That being said, in MC-UWMAC, unlikely collisions may happen only in the control channel saving thus data channels from undesirable costly collision. Indeed, in a given data channel, the collision is completely avoided thanks to the handshaking process in the common control channel along with the meeting table management and the quorum system construction procedure. Consequently, in MC-UWMAC, data communication is guaranteed to be collision free.

Collisions in MC-UWMAC may happen only in the control channel if two or more nodes are sharing the same slot number. In other words, and according to our slot assignment procedure, if more than one node reside in the small cell then they will surely share the same slot in the TDMA frame, which may cause collision when sending the RTS packet to a common neighbor. According to MC-UWMAC, a collision is detected only after sending a RTS message for which no CTS is received. Once a collision is detected, a node waits a random number of frame periods (so called back-o delay) before trying to retransmit again the RTS message in the same slot. Retransmissions are scheduled according to the binary exponential back-o strategy. Accordingly, an integer variable BI (s) ≥ 1 is associated to each slot s. Whenever the sender node experiences a collision in slot s, it rst doubles BI (s) up to maximum value of BI max . Then, the sender chooses a random variable from interval [1, BI (s)]. Note that the selected random variable denotes the number of frames to wait before reattempting the RTS transmission. When a CTS packet is received in slot s, the sender resets the back-o interval to BI (s) = 1. In MC-UWMAC, BI max is set equal to the maximum number of nodes in the same small cell sharing the same slot number.

Finally, we brief that MC-UWMAC naturally avoids collision at the data channel without requiring any extra packet exchange among nodes and provides a recovery mechanism to deal with the unlikely collision in the common control channel. As opposed to MM-MAC and CUMAC, where messages has to be exchanged among neighbors in order to avoid collisions which is an energy consuming procedure.

5 MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 78

Collisions analysis in MC-UWMAC

In MC-UWMAC two nodes may experience a collision if and only if they exist in the same small cell of side R C p . In MC-UWMAC having nodes in the same small cell does not mean that they will systematically experience a collision. In order to gain more insights into the occurrence of collision in MC-UWMAC, let us closely inspect the MC-UWMAC behavior for dierent value of maximum neighborhood size n.

n ≤ 4

In this case, we deal with an extremely sparse network where every node has at maximum 6 neighbors. Hence, our p = 2 and thus the size of the small cell is

R C p = 2 × R t + ε.
Consequently, nodes in the same small cell may be 2-hop away, or even more since the diagonal line size is 2 √ 2R t > 2×R t , and thus traditional collisions may not occur. However, they may suer from hidden terminal collision if one of the 2 sending nodes is addressing a common neighbor. Looking at Fig. 5.8, reader may expect hidden terminal collision between nodes in dierent small cell but sharing the same slot number. Note however that since the size of the small cell is greater than 2 × R t then such collision is completely mitigated. Indeed, as depicted in Fig. 5.8, if node u and v initiate a communication simultaneously such that u is addressing node w then w will not suer from collision since w is not a neighbor of v. Indeed, because of the small cell size, w can be either a neighbor of u or a neighbor of v and hence hidden terminal collision between dierent small cell sharing the same slot number can never happen. n > 4

In this case, all the nodes in the same small cell are almost neighbors. Indeed, for p = 3

the size of the small cell is almost √ 2R t and for p = 4 the size of the small cell is 2 3 R t . Note that the size of the small cell decreases when p increases. Consequently, they may suer from traditional collision but never hidden terminal collisions. Note however that in this case, and according to MC-UWMAC, nodes in the same small cell will have complete and accurate knowledge of nodes availabilities as well as data channels availabilities since they are all neighbors of each others and hence collisions can be further reduced thanks to the meeting table management.

Performance evaluation

Inspired by the the discrete-event underwater acoustic network simulators developed in [START_REF] Chao | Multiple-rendezvous multichannel mac protocol for underwater sensor networks[END_REF], we have implemented our multi-channel underwater acoustic network simulator to assess the performance of MC-UWMAC. In our simulations, we consider a network of 49 nodes uniformly deployed over a square area of length 5Km supplied with constant bit rate trac. The transmission range is 1Km and the nominal speed of sound in water is 1500m/s. Data and control packets are of size 200 and 20 bytes, respectively. Control slot duration is 2s long. We employed the energy consumption model adopted in [START_REF] Chao | Multiple-rendezvous multichannel mac protocol for underwater sensor networks[END_REF], where the transmit power (10 W) is 125 times the receive power (80mW). In addition, we assume that nodes have a buer for each of its neighbors and perform a continuous monitoring of the target area where four sinks are placed at the corners. Each simulation runs for 3600s. Fig. 5.9 shows the probability of collision on the control channel as function of the trafc rate for both our MC-UWMAC protocol for dierent p values as well as for MM-MAC protocol for comparison purposes. First, note that MC-UWMAC succeed to achieve very low collision probability, especially for p = 3 and p = 4, that is even lower than the one achieved by MM-MAC. Indeed, Thanks to our quorum and slot assignment procedures, we aim at providing to the most possible extent a collision free communication. However as mentioned before, co-existing nodes in the same small cell will probably cause simultaneous RTS transmissions. In this case, nodes will defer their transmission according to a backo strategy to avoid repetitive collisions. The MM-MAC protocol was also conceived to provide a collision free communication but the proposed slot assignment procedure is not as ecient as our since it relies on node ID, which did not guarantee the overlapping of default and switching slots of communicating nodes. Moreover, MM-MAC didn't conceive any solution to deal with collision and hence repetitive collisions may happen. Moreover, observe that the collision probability is decreasing with p. In fact, by increasing p, the size of the small cell is further reduced and hence we guarantee that only a unique sensor is located in every small cell and thus every sensor will have its own unique quorum and slot that is 2-hop conict free and hence collision free communication is absolutely assured. well as MM-MAC will be able to send more than one data packets to the same neighbor in the same data channel. Recall that according to MC-UWMAC, once a pair of nodes succeed their handshaking they may remain on their dedicated data channel to send all the data packets on the sender buer to the intended receiver. Consequently, for one successful handshaking on the control channel, MC-UWMAC protocol as well as MM-MAC will be able to send more than one data packets which reduces the end-to-end delay of the data packets. Note that, this is not the case for low trac rate where for each data packet, a successful handshaking is required. Observe however that when the trac rate is very high the MM-MAC delays start to increase again. Recall that time in MM-MAC is rigidly slotted into control and data periods of xed sizes which imposes a limit on the number of sent data packets during the data period. Hence, a given sender will be obliged to start a new handshaking even if it still have data packets for the same receiver which is not the case for MC-UWMAC. Nevertheless, MM-MAC succeeds to achieve better end-to end delay for trac rates between [0.18, 0.25] while MC-UWMAC (for p = 3) clearly outperforms MM-MAC for trac rates between [0.01, 0.15]. In the latter range of trac rates, MM-MAC performance degradation is due to the rigid division of MM-MAC into control and data periods of xed length which not only imposes to postpone data transmission till the start of the data period which is time consuming but also the data period is not fully exploited since the trac rate is low and hence a new handshaking has to be re-conducted after uselessly waiting for the end of the data channel, and hence the average end-to-end delay is increased especially compared to MC-UWMAC which naturally avoids such harsh restrictions. In fact, according to MC-UWMAC, a pair of nodes can immediately start their data communication as soon as they succeed their handshaking. Moreover, once they move to the data channel, they can remain as long as they have data packets to exchange which will considerably reduce the end-to-end delay. Note however, the high end-to-end delays for p = 4 is mainly due to the reduced data channel bandwidth which will increase the transmission times. Recall that the total available bandwidth will be divided into N data channels where N = n(n-1)

2
and n is p 2 . this separation between control and data period will not only limit the data period and increase the end-to-end delay and hence badly impact the throughput as explained above but also it will prohibit simultaneous data transmissions and handshaking among dierent pair of nodes. However, with MC-UWMAC, not only simultaneous data communication can occur separately in dierent data channels but also the handshaking process in the common control channel naturally continues to take place at the same time which will further increases the number of successfully received packets by the sinks. who have succeeded their handshaking in order to avoid data collision which is an energy consuming procedure.

As a recap, we recommend to set p either equal to 2 or 3 in order to increase the throughput while being energy ecient. However, p = 4 highly decreases the collision probability but provides reduced throughput and energy eciency due to the reduced data channel bandwidth.

Conclusion

In this chapter, we proposed a novel multichannel MAC protocol, MC-UWMAC, especially designed for the underwater environment. MC-UWMAC operates on single slotted control channel for handshaking and multiple data channels. To guarantee a collision free communication, MC-UWMAC employs two key related procedures: i) a grid based slot assignment on the control channel and ii) a newly designed quorum based data channel allocation which aims at guaranteeing for each pair of neighbor nodes a unique and 2hop conict free data channel for their data transmission. The quorum construction and slot allocation procedures, not only highly decreases the probability of collision but most importantly do not require any extra packets exchange between nodes which increases the energy eciency of MC-UWMAC. Simulation results show that signicant throughput improvement is achieved by our MC-UWMAC protocol since it allows multiple simultaneous almost collision-free communications to take place on the control channel as well as all available data channels. Moreover, MC-UWMAC is energy ecient since it avoids collision without requiring any additional control packet exchange among nodes. We believe that the proposed MAC protocol is a promising Multichannel communication scheme since it achieves better performance over MM-MAC [START_REF] Chao | Multiple-rendezvous multichannel mac protocol for underwater sensor networks[END_REF], thanks to the careful design of MC-UWMAC.

Chapter 6

Conclusion and future perspectives

Conclusion

In this thesis, we introduced the UnderWater Acoustic Sensor Networks (UW-ASNs) and potential applications. We described the major challenging characteristics of the underwater environment that face the developing of networking protocols. One of the great challenging issue in UW-ASNs is the energy eciency as higher power is needed for acoustic communication while batteries are limited and not rechargeable due to inaccessible deployment zone. In this thesis, our work focus on the sink hole problem and the multichannel MAC design and made three main contributions.

First, we tackled the problem of energy holes in UW-ASNs. We proposed a balanced routing strategy based trac load distribution on each node among neighbors provided that sensors adjust their communication range among two levels when they send or forward the periodically generated data. In particular, at the routing layer, we determine the set of possible next hops with the associated load weight that lead to a fair energy consumption among all neighbors.

Second, we extended our balanced routing strategy design for avoiding energy holes in UW-ASNs allowing underwater nodes to tune their transmission range among several possible levels n > 2. We showed that increasing n increases the energy consumption since farther nodes could be reached. Thus, we proposed to determine the optimal number of transmission range levels n which minimize the energy consumption while distributing the load trac to guarantee a fair energy depletion among all nodes and considering more challenging channel characteristics. Hence energy holes can be avoided and consequently the network lifetime is highly increased.

Third, dealing with MAC layer, we conceived a novel multichannel-underwater MAC protocol (MC-UWMAC) based TDMA communication concept. MC-UWMAC operates on single slotted control channel dedicated to RTS/CTS handshaking and a set of equalbandwidth data channels. The originality of our MC-UWMAC is twofold: i) the slot assignment procedure and ii) the quorum based data channels allocation. Both procedures are distributed and did not need any extra negotiation overhead. Specically, the slot assignment procedure is only based on a combination of virtual coordinates derived from a virtual geographic area partition. Analytical results proves that our slot assignment procedure approaches the 2-hop conict free and the collision free communication. As to the data channels allocation procedure, we utilize the unique singleton quorum system which is composed of a predened number of data channel subsets. Each subset is associated to one node according to its slot number. The unique data channel intersection between two dierent subset will be allocated to the communication of the node couple owning the subsets. Thus, each neighbor of a node will be coupled with a dierent data channel, helping the node to distribute the load charge over all neighbors. Simulation results show 6 Conclusion and future perspectives 84 that MC-UWMAC can greatly improve the network performance especially in terms of energy consumption, throughput and end-to-end delay.

Future perspectives

Energy-eciency is one of the critical concerns in underwater acoustic sensor networks which attract an increased interest. Numerous challenges issues arise with such networks which have not been yet inspected. In this section, we present our future perspectives.

• Sparser networks are the most aected by the energy sink-hole problem. However, due to the random deployment and nodes mobility, dense networks can suer from energy holes. Thus, in future, we wish to design an enhanced load balancing routing protocol to mitigate energy holes in dense UW-ASNs considering the 2-D and 3-D topologies. Then, we plan to provide a performance comparisons with other protocols mentioned in the related work section.

• In MC-UWMAC, we considered a multiple sinks scenario when assessing the performance of our multi-channel MAC protocol. To enrich our performance evaluation, we plan as a rst step to extend our simulations to observe the performance of our protocol in a single sink scenario where all the packets are forwarded toward one sink placed at the center. Thus, in order to anticipate the occurrence of the energy sink-hole problem in the considered network, our second step consists of joining our proposed routing technique and our MAC protocol to conceive an energy-ecient cross layer protocol for UW-ASNs and implement it. By doing so, in addition to mitigate the energy sink-hole problem, we expect to achieve further energy savings and improve the network lifetime.

• Actually, many simulators are proposed for underwater networks. However, each available simulator has limitations and depends highly on what it is designed for. That is why, we designed our own simulator to assess the performance of our multichannel MAC protocol. In fact, due the unstable nature of the underwater environment and its variability from a zone to another, it is too dicult to nd a common standard propagation model which can be used in simulations to analyze and compare protocols for UW-ASNs.

To prove our nds, we plan to provide a comparative study between all the available simulators for underwater networks helping researchers to select the suitable simulator to implement and analyze their protocols. On a second stage, we wish to conceive an adaptable simulation platform which facilitate the higher layer protocols implementation and performance evaluation.

Figure 1 . 1 :

 11 Figure 1.1: Internal architecture of an UnderWater Sensor node.

Figure 3 . 1 :

 31 Figure 3.1: Underwater Acoustic sensor network model showing a wedge W and the associated sectors.

Figure 3 . 2 :

 32 Figure 3.2: Transmission power as function of distance.

  10 log 10 P T (d) = 10 log 10 P tx (d) -170.8 -10 log 10 ξ (3.10)

d

  tx-max = 100 m d tx-max = 200 m B 3dB 24.

Figure 3 . 3 :

 33 Figure 3.3: Packet load distribution per corona when R = 1000 m and r = 100 m.

Figure 3 . 4 :

 34 Figure 3.4: Energy consumption per corona when R = 1000 m and r = 100 m.

38 Figure 3 . 5 :

 3835 Figure 3.5: Energy consumption for dierent eld radius when r = 100 m.

Figure 3 . 6 :

 36 Figure 3.6: Network lifetime for dierent eld radius when r = 100 m.

Fig. 3 .

 3 Fig. 3.5 shows the energy expenditure as function of eld radius when the corona width remains xed and equal to r = 100 m. Recall that the energy value considered for each eld radius is the maximum consumed energy among all coronas. As expected, as the eld radius increases the energy consumption increases since the number of coronas grows.

Figure 3 . 7 :

 37 Figure 3.7: Energy consumption for various corona width when R = 2000 m.

Figure 3 . 8 :

 38 Figure 3.8: Network lifetime for various corona width when R = 2000 m.

Figure 3 . 9 :

 39 Figure 3.9: Packet load distribution per corona when R = 2000 m and r = 50 m.

Figure 3 . 10 : 41 Figure 3 . 11 :

 31041311 Figure 3.10: Energy consumption per corona when R = 2000 m and r = 50 m.

Figure 3 . 12 :

 312 Figure 3.12: Energy consumption per corona when R = 2000 m and r = 250 m.

Figure 3 . 13 : 42 Figure 3 . 14 :

 31342314 Figure 3.13: Packet load distribution per corona when R = 500 m and r = 50 m.

Figure 3 . 15 :

 315 Figure 3.15: Packet load distribution per corona when R = 500 m and r = 250 m.

Figure 3 . 16 :

 316 Figure 3.16: Energy consumption per corona when R = 500 m and r = 250 m.

Figure 4 . 1 :

 41 Figure 4.1: Underwater Acoustic sensor network model showing a wedge W and the associated sectors.

Figure 4 .

 4 Figure 4.1 illustrates a possible path along which a packet is routed from one sensor in the outermost corona to the sink. Each path involves only one sensor from adjacent coronas.

4 48 Figure 4 . 2 :

 4842 Figure 4.2: Nominal Channel Geometry: distance between the transmitter and receiver is d = 1km, water depth h = 100m , transmitter and receiver are at the water surface and the bandwidth B = 10Khz.

49 Figure 4 . 3 :

 4943 Figure 4.3: Instantaneous Channel Gain.

Figure 4 . 4 :

 44 Figure 4.4: The channel gain versus distance.

Fig. 4 . 51 Figure 4 . 5 :

 45145 Fig.4.5 shows the generated transmission power as a function of distance for the acoustic channel parameters listed in the previous section. Note that, we consider a noise power of 20 dB, R per is set equal to 85% and the margin K equals 1.1. Is is worth pointing

Figure 4 . 6 :

 46 Figure 4.6: Packet load distribution per corona when R = 1500 m and r = 100 m.

Figure 4 . 7 :

 47 Figure 4.7: Energy consumption per corona when R = 1500 m and r = 100 m.

Figure 4 . 8 :

 48 Figure 4.8: Energy consumption for dierent eld radius when r = 100 m.

Figure 4 . 9 :

 49 Figure 4.9: Energy consumption for dierent eld radius when r = 100 m.

Figs. 4 . 61 Figure 4 . 10 :

 461410 Figs. 4.8 and 4.9 show the energy expenditure as a function of eld radius when the corona width remains xed and equal to r = 100 m. Recall that the energy value considered for each eld radius is the maximum consumed energy among all coronas. As expected, as the eld radius increases the energy consumption increases since the number of coronas grows. Consequently and as depicted in Figs. 4.10 and 4.11 the network lifetime decreases with the increase of the eld radius. More importantly, our balanced routing strategy using variable transmission powers considerably reduces the energy expenditure compared to the nominal communication range data forwarding (n = 1). Indeed, allowing the sensor

Figure 4 . 11 :

 411 Figure 4.11: Network lifetime for dierent eld radius when r = 100 m.

Figure 4 . 12 :

 412 Figure 4.12: Energy Consumption for various corona width when R = 5000 m.

Figure 4 . 13 :

 413 Figure 4.13: Network lifetime for various corona width when R = 5000 m.

Figure 4 . 14 :

 414 Figure 4.14: Optimal n value for various corona width.

Figure 5 . 1 :

 51 Figure 5.1: MultiChannel Hidden Problem.

5 67 Figure 5 . 2 :

 6752 Figure 5.2: Long-Delay Hidden Terminal Problem.

Figure 5 . 3 :

 53 Figure 5.3: MC-UWMAC frame structure.

5 70 Figure 5 . 4 :

 7054 Figure 5.4: Example of channel assignment (n max = 5). The precised number on every link denotes the common dedicated data channel.

Figure 5 . 5 :

 55 Figure 5.5: Grid based virtual partition(n max = 9).

5

  MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 75

Figure 5 . 6 :

 56 Figure 5.6: Flowchart of the sender behavior.

5Figure 5 . 7 :

 57 Figure 5.7: Flowchart of the receiver behavior.

Figure 5 . 8 :

 58 Figure 5.8: Network virtual partition (p = 2).

5Figure 5 . 9 :

 59 Figure 5.9: Collision probability.

Now, regarding theFigure 5 . 10 :

 510 Figure 5.10: End-to-end Delay

Fig. 5 .Figure 5 .

 55 Fig.5.11 depicts the network throughput for both protocols as function of the trac rate. For both protocols, the throughput increases with the trac rate. Observe that, MC-UWMAC, especially with p = 3 and p = 2, outperforms MM-MAC in terms of throughput, regardless the generated trac rate. Indeed, MC-UWMAC achieves up to 74% improvement in network throughput over MM-MAC for a trac rate of 0.25pkts/s. Consequently, we can state that MC-UWMAC handles heavy loaded networks, as well as light loaded

Figure 5 . 12 :

 512 Figure 5.12: Energy consumption per bit

Now, to get

  more insight into the energy eciency of both protocols let us inspect the energy consumption per useful bit as function of the trac rate. As shown in Fig.5.12, MC-UWMAC (p = 3 and p = 2) is clearly more energy ecient than MM-MAC. The energy consumption for MM-MAC can be considered as closer to the case p = 4 where our protocol consumes more energy due to the reduced data channel bandwidth size which increases the transmission and reception time and hence the resulting energy consumption. p = 2 and p = 3 are clearly more energy ecient since they succeed to achieve much higher throughput while using a data channel of reasonable width. Moreover, it is worth noting that MC-UWMAC naturally avoids collisions and achieves high throughput without requiring any extra packet exchange among nodes. As opposed to MM-MAC, where notication messages has to be continuously sent during the remaining control period by any pair of nodes 5 MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 82

Table 3 .

 3 Transducer eciency ξ 0.8 study the impact of using variable transmission powers to reach (d tx-max ∈ {r, 2r}) on both packet load and energy consumption for every corona. The bandwidths and center frequencies adopted in our study conguration are reported in Table3.2.

	1: Parameters setting
	Packet length P l	1024bits
	SN R 0	20 dB
	Initial Energy	1 J
	Data Rate A	10 packet/s
	P 0 rx	0.75 W
	η 0	50 dB re 1 µ P a 2 /Hz
	A 0	30 dB
	Spreading factor k	1.5

Table 3 .

 3 2: Bandwidths and center frequencies.

Table 3 .

 3 .3. Note that, adopting a nominal communication range based data forwarding with d tx-max = r leads 3: β matrix when R = 1000 m and r = 100 m.

	Bi	β i 1	β i 2
	B1	1	0
	B2	0.02	0.98
	B3	0.35	0.65
	B4	0.14	0.86
	B5	0.25	0.75
	B6	0.17	0.83
	B7	0.18	0.82
	B8	0.15	0.85
	B9	0.13	0.87
	B10	0.1	0.9

Table 3 .

 3 4: Bandwidths and center frequencies.

4

  Joint Routing and Energy Management in UW-ASNs 47 up to n levels where n > 2. In other words, we suppose that d tx-max ∈ {r, 2r, . . . , nr}

	(4.2)

Table 4 .

 4

	1: Parameters setting
	Packet length P l 1024 bits
	SN R 0	25 dB
	Initial Energy	100 J
	Data Rate A	0.08 packet/s
	Noise Power	20 dB
	Bandwidth	10 Khz

Table 4 .

 4

2, 4.3 and 4.4 report the β i vectors for each corona when n equals to 3, 5 and 7, respectively. Accordingly, to minimize the energy consumption gap among dierent coronas, overall, the packets load should be evenly distributed among upstream coronas. Indeed, balancing the energy consumption among dierent coronas is a trade-o between 4 Joint Routing and Energy Management in UW-ASNs 58 two opposite requirements: the reception energy and the transmission energy which are

Table 4 .

 4 2: β matrix when n = 3. Corona i Corona (i -1) Corona (i -2) Corona (i -3)

	Corona 1	1	0	0
	Corona 2	0.033	0.97	0
	Corona 3	0.05	0.05	0.9
	Corona 4	3*0.33	3*0.33	3*0.34
	...
	Corona 15

Table 4 . 3 :

 43

  5.2. At the beginning, all nodes are listening to the control channel. Suppose that node A starts sending a RTS message to node B to communicate on data channel i. Shortly after, a node C neighbor of A and B starts sending a RTS to node D to communicate also on data channel i, since it didn't yet receive node A's RTS. Node B correctly receives node A's RTS and reply by the CTS. Shortly after, B receives the RTS from C. Node D being neither a neighbor of B nor a neighbor of A will normally sends its CTS. Consequently, both pairs of nodes will initiate data communication on channel i nearly at the same time. This problem is usually insignicant in terrestrial radio networks due to the extremely high propagation speed of radio signal. For longdelay underwater acoustic networks, however, this problem has to be considered and well addressed. In brief, new solutions are highly required in order to eectively solve the triple hidden terminal problems in single-transceiver multichannel long-delay underwater networks.

Joint Routing and Energy Management in UW-ASNs

Acknowledgements

Protocol for UW- ASNs 72 Clearly,

card(S 1 ) = n -1 and card(S j ) = j -1 + n -j = n -1; ∀1 < j ≤ n.

Moreover, by quorum construction, ∀{i, j}; 1 ≤ i, j ≤ n and i = j,

if i < j then(S i ) j-1 ⊂ {S i ∩ S j } else(S j ) i-1 ⊂ {S i ∩ S j }. Consequently, Q = {S 1 , ..., S n } is a quorum system.

• Now, let us demonstrate by recurrence that the pair-wise intersections among (S i ) 1≤i≤n quorums is a singleton.

-For a given n and according to S j denition      S 1 = {1, 2, ..., n -1} and S 2 = {1, n, ..., 2n -3} hence S 1 ∩ S 2 = {1} = (S 1 ) 1 . Note that, in S 2 , except the rst element 1, all the others are greater than n -1 and thus no one of them can be an element of S 1 .

-Suppose that up to k < n, ∀ {i, j} ≤ k, i = j and i < j then S i ∩ S j = {(S i ) j-1 }.

Let us now demonstrate by contra-position that for iteration k

Suppose that card (S k+1 ∩ S i ) ≥ 2, consequently there must be m, m = i and 1 ≤ m ≤ k such that (S m ) k ⊂ {S k+1 ∩ S i } since all the elements {(S k ) n-1 + 1, ..., (S k ) n-1 + (n -(k + 1))} of S k+1 are created only at step k + 1 and hence they do not exist in any other previous set S j , 1 < j ≤ k.

Since m > i, hence all the elements {(S m ) m , ..., (S m ) n-1 } are strictly greater than any element in S i . Hence, (S m ) k > (S i ) m-1 and thus S i ∩ S m is far from being a singleton which contradicts our hypothesis that up to k < n, ∀ {i, j} ≤ k , i = j and i < j then S i ∩ S j = (S i ) j-1 .

Consequently, Q = {S 1 , ..., S n } is a singleton-intersecting quorum system.

-In order to prove the pair-wise dierence among the intersections, we suppose that

Let us demonstrate by contra-position that (S i ) j-1 = (S k ) m-1 .

Suppose that (S i ) j-1 = (S k ) m-1 then S i ∩ S k = (S i ) k-1 , (S i ) j-1 which contradicts the pair-wise singleton intersection among S i .

Thus Q = {S 1 , ..., S n } is a unique singleton-intersecting quorum system.

-In order to nd the total number of distinct needed elements to construct Q, we point out that at each step k, when newly creating S k , there are (n -k) elements that are newly introduced compared to all previous sets {S 1 , ..., S k-1 }.

MC-UWMAC: A Collision Avoidance Energy Ecient Multi-Channel MAC Protocol for UW-ASNs 73

To get more insight into the set construction procedure, let us build the dierent sets for instance when n = 9. According to the proposed procedure, a unique singletonintersecting quorum system composed of 9 sets containing each 8 elements can be build as follows: Observe that the total number of distinct elements to construct the unique singleton intersecting quorum system is indeed

Quorum and slot allocation procedure

Once the singleton-intersecting quorum system Q = {S 1 , ..., S n } is built, the issue now is how to allocate the dierent S q (1 ≤ q ≤ n) to the sensor nodes such that each sensor node has a dierent set compared to all its neighbors. To do so, let us suppose that we have a sensor eld of length L and of width l , where N tot nodes with a transmission range R t each are manually and randomly deployed. We suppose that the geographical coordinates of a node u is (X u , Y u ). In order for our MC-UWMAC to work conveniently, we have to guarantee, to the most possible extent, for each node u to choose a set S qu of data channels dierent from all its neighbors. Moreover, in order to be energy ecient, we prefer that the quorum allocation procedure does not require any extra packet exchange among neighbors.

To do so, we propose that a node u's quorum set S qu (1 ≤ q u ≤ n) has to be selected as follows:

q u = (i u -1) + (j u -1) × p

(5.4)

where

(5.8)

As shown in Fig. 5.5 the main idea behind the proposed quorum allocation procedure is to virtually partition our eld into a grid of cells of side R C . The cell of size R C is built such that nodes in two adjacent cells are guaranteed to be non neighbors. As depicted in Fig. 5.5, R C should be chosen such that nodes located at the cell center will have all their neighbors only inside that cell. In other words, R C must satisfy the following

(5.12) We prove Theorem 1 by mathematical induction.

Initial

Step. At each iteration j + 1, corona B j+1 is newly added where A j+1 = A. Thus, the cumulative trac at corona B j will increase to

and hence it can be written as

. Consequently, α 00 equals 1 and α 10 too.

Inductive Step. Let us assume that

where β j+1 l = 0 if l > min (n, p + 1) .

(A.1) is true. Then, we need to prove that our assumption is also true for A j-(k+1) .

By denition, A j-(k+1) can be expressed as follows

Since we assume that our assumption is true up to corona B j-k , then A j-(k+1-m) can be substituted by Eq. A.1 and hence we can express A j-(k+1) as follows

Consequently, A j-(k+1) can be expressed as follows

Therefore, our assumption is also true for A j-(k+1) so that the proof completes.

A.2 Proof of Eq. 4.19

T X is the average transmission energy consumed by a sensor in corona B i . At iteration j +1, when we newly add corona B j+1 , linearly expressing

along with E i RX as function of β j+1 allows to have a system of linear equations where β j+1 can be easily derived. By denition E i T X can be written as follows

where β i q = 0 if q > min (n, i + 1) .

(A.5) At this step, the key idea is to observe that A i is simply A j-(j-i) . Therefore by substituting A j-(j-i) with the appropriate expression of Theorem 1, we get

Note that A i+1 q=1 β i q E q tx α 0(j-i) as well as A i+1 q=1 β i q E q tx α l(j-i) , that we call T X i 0 and T X j-i l respectively, are constants (not depending on β j+1 ). Hence we get

where β j+1 l = 0 if l > min (n, j -i + 1) which concludes the proof.

A. (A.8)

By substituting A i+p with the appropriate expression of theorem 1, we succeed to get a linear expression of E i RX as function of β j+1 as follows

Aβ i+p p α l(j-i-p) E p rx P j+1 l β j+1 l +P j+1 j-i+1 β j+1 j-i+1 AE j+1-i rx (A.9)

Observe that, by performing indices permutation,