Source: https://jwcn-eurasipjournals.springeropen.com/articles/10.1186/1687-1499-2013-128
Timestamp: 2019-04-21 11:05:36+00:00

Document:
The performance of underwater sensor networks (UWSNs) is greatly limited by the low bandwidth and high propagation delay of acoustic communications. Deploying multiple surface-level radio-capable gateways can enhance UWSN performance metrics, reducing end-to-end delays and distributing traffic loads for energy reduction. In this paper, we study the problem of gateway placement for maximizing the cost-benefit of this UWSN architecture. We develop a mixed integer programming (MIP) gateway deployment optimization framework. We analyze the tradeoff between the number of surface gateways and the expected delay and energy consumption of the surface gateway architecture in the optimal case. We used an MIP solver to solve the developed optimization problem and integrated the optimal results to serve as an input for our simulations to evaluate the benefits of surface gateway optimization framework. We investigated the effect of acoustic channel capacity and the underwater sensor node deployment pattern on our solution. Our results show the significant advantages of surface gateway optimization and provide useful guidelines for real network deployment.
An important component of oceanographic studies is the collection of data from the aquatic environment. Remote sensing has long been employed as a tool to collect aquatic data in underwater monitoring and exploration activities. Recently, in the last decade to be more specific, underwater acoustic sensor networks (UWSNs) have emerged as a new alternative technology enabling underwater monitoring and exploration applications, including scientific, commercial, and military applications [1–5]. Compared to their remote-sensing counterparts, UWSNs have many advantages. UWSNs can provide localized and more precise data acquisition. They can also employ a wider variety of sensors including, but not limited to, chemical, temperature, photo, and motion sensors.
UWSN technology is also replacing traditional underwater instrumentation technology. Traditionally, bulky sensor nodes equipped with data-storage capability are manually deployed in the underwater target space. Each node operates independently for the duration of the mission to collect readings according to a preset program. At the end of the mission, sensor nodes are picked up, and the collected data are retrieved and processed. UWSN technology adds networking capabilities to underwater sensor nodes so that sensor nodes can relay real-time data to an off-shore or even an on-shore control station for immediate analysis. The communication channel can also be used to transmit control signals from the control station to the underwater sensor nodes, which enables interactive control of the underwater sensor network deployment. UWSNs offer many advantages over traditional instrumentation techniques. First off, UWSNs add a real-time reporting functionality that enables a host of new real-time monitoring and warning systems. Another advantage of UWSN is that the sensing mission can be dynamically reconfigured without the need to physically access all the underwater nodes in order to reprogram them. While this particular feature makes the reuse of a UWSN deployment much less costly, it also provides for fixing configuration errors that compensates for unforeseen circumstances and unexpected node failures. This improves the UWSN resilience compared to traditional instrumentation techniques. Therefore, sensor node failures can be detected soon after they occur, allowing early replacement or early abortion of the mission instead of having to wait until the end of the mission only to find that it has failed.
In addition to the usual design challenges faced by terrestrial wireless sensor networks, UWSN technology has to deal with some unique challenges. It cannot use electromagnetic waves for long-range communication due to their quick absorption in water. Acoustic waves are usually considered the practical solution for UWSN communication. The dependency of UWSNs on underwater acoustic communications is particularly challenging. Factors such as the high levels of noise and the channel variability due to temperature, pressure, salinity gradients, and current-induced turbulence add more constraints to the already small bandwidth available for acoustic communication. Moreover, when the Doppler effect (due to mobility) is added to those factors, channel encoding becomes a crucial component to the success of underwater acoustic sensor networks. However, the most limiting factor of underwater acoustic communications is the extremely low propagation speed of sound, which is roughly 1.5 km/s, subject to slight changes due to pressure, temperature, and salinity variations . This is five orders of magnitude slower than the propagation speed of electromagnetic waves. Such high propagation delay can cause high end-to-end delay, which could be greatly limiting for interactive applications and other monitoring applications where response time is critical.
One way to mitigate the high propagation delay in acoustic communications is to deploy multiple surface-level gateways. In sensor networks, each sensor node can monitor and detect environmental events locally and then transfer these measurements through the network to a surface gateway node (also referred to as a sink in UWSNs), which then relays data to the control station. Unlike single-sink networks that use long underwater paths to reach the unique surface sink, in a multiple-sink underwater sensor network, as illustrated in Figure 1, underwater sensor nodes can send data packets toward their nearest surface gateway. A surface gateway then uses electromagnetic waves to forward the packets to the control station. Considering that electromagnetic wave propagation is in orders of magnitude faster than acoustic wave propagation, it is safe to assume that surface gateways can send packets to the control station in negligible time and with relatively small energy consumption since acoustic communications consume much more energy than radio communications . In this way, all the surface gateways (or sinks) form a virtual sink. Although architectures employing multiple surface gateway nodes were mentioned in [5, 7], there is no formal study on surface gateway deployment. Neither an analysis on the effect of using multiple surface gateways on the network energy consumption or delay characteristics has been conducted nor a guideline on the deployment of such a multi-sink architecture has been provided.
In this paper, we study the problem of surface gateway deployment and present guidelines for deciding the number and locations of surface gateway nodes given an underwater sensor network deployment scenario. We focus on optimizing the cost of surface gateway deployment, by finding the minimum number and the locations of surface gateway nodes required to achieve a given design objective, which can be communication delay, energy consumption, fault tolerance, or a combination of them. The surface gateway deployment problem is formulated as an optimization problem modeling the routing of data packets from underwater sensor nodes to the virtual sink under link capacity and flow conservation constraints. A variety of objective functions are presented. Our framework provides an optimal gateway selection from given gateway candidate locations which are assumed to be a given. The rest of this paper is organized as follows. In Section 2, we provide a review of related work. In Section 3, the network model and assumptions regarding the surface gateway deployment problem are presented and justified, and the surface gateway deployment problem is formulated as an optimization problem. In Section 4, we evaluate our work, choosing sample problems to analyze the effect of various constraints on the deployment solution quality, problem complexity, and feasibility. Finally, in Section 5, conclusions are drawn, and a future work is presented.
The deployment problem for sensor nodes was studied extensively for terrestrial sensor networks . The closest to our work from the placement strategies in terrestrial networks are those for relay node and multi-tier sensor network architecture [9–11]. However, most terrestrial deployment problems assume a static two-dimensional (2D) architecture, and not much attention was received for multi-gateway deployment in UWSN. A triangular-grid deployment pattern for 2D UWSN was proposed in . The objective is to minimize the number of sensors needed to achieve the sensing and communication coverage of a target area. An interesting attempt to formulate the 3D UWSN point-coverage deployment problem as an integer linear program (ILP) is presented in . The solution of the ILP decides relay node deployment, routing, and link scheduling. Throughout this work, it is assumed that there is a single sink for the entire UWSN deployment and only the overall power consumption is used as an optimization objective. Neither of these two studies considers the multiple-sink network architecture. The only research study in the frame of multiple sinks we found is , in which Seah and Tan investigated the use of multi-sink architecture to enhance the underwater sensor network reliability. In this study, the same message is directed to more than one of the multiple sinks, with the assumption that if any of the sinks gets the message, then it is considered delivered successfully. The simulation results showed that high-reliability benefits can be achieved at the cost of reasonable increase in energy consumption. The surface gateway (i.e., sink) deployment problem was not considered in this work. In a parallel research effort,  studied the problem of placing multiple mobile data collectors in both delay-tolerant and delay-constrained underwater acoustic sensor networks. The authors defined candidate data collection stations as the maximal overlapping regions (MORs) of surface circles corresponding to underwater node communication ranges. They developed an O(n2 logn) algorithm for finding MORs. An earlier work in  was the first to address the underwater surface gateway deployment problem and formulate it as an optimization problem. The problem of surface-level gateway placement has been addressed by later research effort in. The authors used surface gateways deployment as a mean to guarantee connectivity and survivability (tolerance to single node failure). They proposed an approximation algorithm for choosing a minimal subset of candidate locations where SGs may be deployed. An effort by the authors in  addressed the deployment for a mobile multiple-sink architecture in UWSN. They used a prediction-based deployment strategy to cater for the mobility of underwater nodes. However, our work differs from all above by formulating the problem to find the best candidate locations that satisfies a set of flow conservation constraints, interference constraints, number of gateway constraints, and performance constraints in addition to a set of delay and energy-consumption objectives.
There are two approaches to handle the surface gateway deployment problem, (1) solving the underwater deployment and the surface-level deployment problems jointly or (2) solving each of them separately. It is understood that solving both underwater and surface deployment problems jointly will lead to optimal solutions that are better, or at least as good as, the outcome of the two-phase approach. However, since the objective of the research presented here is to analyze the effect of surface gateway deployment on the overall underwater sensor network performance, we fix the underwater deployment and therefore opt for the latter option. Thus, we assume that there is a pre-existing underwater deployment that has been reached by a way or another.
The surface gateway deployment problem is formulated as a combinatorial graph optimization problem. The nodes of the graph represent underwater sensors and candidate surface gateway positions, and the problem is to find the subset of the candidate surface locations that maximizes a certain performance metric, satisfying a set of flow conservation constraints, interference constraints, and a deployment cost constraint (on the number of surface gateways) or a performance constraint (such as maximum end-to-end delay or minimum reliability level).
The selection of the candidate positions is sophisticated enough to be considered as a separate problem to on its own and is discussed by our work in . For the purpose of producing a generalized formulation, the set of candidate surface points is considered a given and assumed to satisfy connectivity constraints as a precondition. This means that each underwater node has to have at least one connected path to one or more candidate surface locations, taking into account the communication ranges of the involved intermediate nodes.
Associated with each underwater sensor node is a packet generation rate. Surface gateway nodes have to collect all generated data packets. The surface gateway deployment problem is formulated as a combinatorial optimization problem. The formulation consists of a basic set of constraints that can be augmented with a variety of objective functions.
The functionality of the UWSN considered is assumed to be mainly collecting data from underwater sensor nodes and transmitting the collected data samples at regular time intervals to a central station through one of the surface-level gateways. We assume that most of the traffic, therefore, will be flowing from the underwater nodes to the surface gateways. Inter-node communication (for purposes such as synchronization, collaborative sensing, data fusion, etc.) is assumed to be small enough to ignore.
Together, the set of surface-level gateways forms a virtual sink for the underwater sensors because the propagation delay, the energy consumption, and the reliability of transmitting the received packet by a gateway to the central station over a direct or multi-hop radio path are far superior to underwater communication links. It is reasonable, therefore, to assume that a packet delivered to one of the surface gateways is delivered to the central station with high reliability and negligible delay and energy cost.
For simplicity, we assume that the data link protocol uses only fixed-length packets and that all links have the same bit rate. Consequently, the packet transmission time is consistent throughout the network, and if the transmission scheme is slotted, the packet transmission time is conventionally called the timeslot. Our deployment formulation can be adjusted to include a variable packet length and a variable bit rate at different links without compromising the quality of the solution. This will require a pre-existing knowledge of these parameters which will increase number of inputs and will result in a more complex formulation of the flow constraints. However, we are interested in providing a more generalized formulation of the gateway optimization problem to be adjusted and tuned for a more specified application that may require varying some of the inputs we assume is a fixed.
The network is modeled as a graph, in which nodes represent the underwater sensors and surface gateways, and edges represent pair-wise communication links.
Let U be the set of all underwater sensor nodes and T be the set of candidate surface node positions.
V = U ∪ T.
where d(v,w) denotes the Euclidean distance between the two nodes u and v, and R u denotes the maximum acoustic communication range of the underwater node u.
E = e ( u , v ) : u ∈ U , v ∈ C u .
E u O = e ( u , v ) : v ∈ C u , ∀ u ∈ U.
E v I = e ( u , v ) : e ( u , v ) ∈ E , ∀ v ∈ V.
G = ∑ u ∈ U g u .
Let f e be the average flow per packet time in edge e measured in packets per packet time.
f v I = ∑ e ∈ E v I f e , ∀ v ∈ V.
f u O = ∑ e ∈ E u O f e , ∀ u ∈ U.
f t O = 0 , ∀ t ∈ T.
x t = 1 if a node deployed at t , 0 otherwise , ∀ t ∈ T.
Let T be the schedule length, i.e., the number of time slots in a single period of the schedule.
Let he,t be a binary variable that indicates whether link e is scheduled for transmission during slot t of the schedule.
h e u , v , t = 1 u transmits to v at timeslot t 0 , otherwise , ∀ u ∈ U , e ∈ E , 0 ≤ t < T.
The most important performance aspects of any network are the delay and energy-consumption characteristics.
Let υ be the average propagation velocity of sound waves in water.
τ u , v P = d ( u , v ) υ , ∀ u ∈ U , v ∈ V.
Let τ u Q be the average transmission queuing time including the expected channel access delay at node u.
τ u , v = τ u Q + τ + τ u , v P , ∀ u ∈ U , e ∈ E u O .
Let π e S be the transmission energy required for transmitting one data packet over the underwater acoustic link e(u,v), π L be the listening/sleeping average energy consumption per packet time, and π v R be the reception energy per packet. For surface gateways, the reception power is taken to include the energy required to forward a packet to the central station over radio.
π v = π L + π v R f v I + ∑ e ∈ E v O π e S f e , ∀ v ∈ V.
π v = π L + π v R f v I + π S f v O , ∀ v ∈ V.
n e = 1 − ρ e ρ e , ∀ e ∈ E.
π v = π L + ∑ e ∈ E v I π v R + n e π v R ′ f e + ∑ e ∈ E v O π e S + n e π e S ′ f e , ∀ v ∈ V.
π e u , v = π L f e + π e S + π v R + n e π e S ′ + π v R ′ .
The constraints can be classified into deployment constraints, flow conservation constraints, and interference constraints.
∑ t ∈ T x t ≤ N.
x t ∈ 0 , 1 , ∀ t ∈ T.
The scenario considered in this work will be a monitoring network, where instrumentation data flow from underwater sensor nodes and through the network to a common sink station. Therefore, the analysis is limited to the (possibly multi-path) route from each underwater sensor to the virtual sink. Control traffic flowing from the central station down to the underwater sensor nodes or inter-node traffic for the purpose of synchronization or localization or other functions than sensing data transfer will be ignored.
f t I ≤ x t G , ∀ t ∈ T.
This means that the total flow f t I into candidate gateway location t has to be zero if x t =0; otherwise, f t I can grow as large as the maximum potential flow in any link in the network which is equal to the total data generation rate G in the network, thus rendering the constraint void.
Flow conservation implies that for underwater sensor nodes, the sum of the average flows leaving a node equals the sum of the flows entering that node plus the local data generation rate.
f u O − f u I = g u , ∀ u ∈ U.
Flow conservation also implies that the total data generation rate of all underwater nodes must equal the total data absorption rate by the virtual sink composed of all surface gateways since each packet, generated by any source, must eventually be received by a surface node (before being relayed to the sink).
∑ t ∈ T f t I = G.
T · f e ≤ ∑ t = 1 T h e , t , ∀ e ∈ E.
Note that since we assume the schedule is periodic, there is no need to add a constraint to enforce the reception of a packet before sending it out. If a packet is sent before being received, this means that it was stored from the previous period. It follows that the maximum per-hop queuing delay will not exceed T−1 timeslots.
B ≤ 0 . 18 b.
I v = u : u ∈ U , d u , v ≤ R u I , ∀ v ∈ V.
f v O + ∑ u ∈ I v f u O ≤ B , ∀ v ∈ V.
This formulation is called pessimistic because that assumes that transmissions that could interfere with the reception at node v are going to happen in distinct time intervals without any overlapping. This is the worst case because it leaves the minimum possible bandwidth for v to receive its own intended transmissions. In reality, however, some of these transmissions from interfering neighbors of node v can occur simultaneously and successfully. Consider, for instance, two interfering neighbors of v, called u1and u2, v cannot receive any signals as long as it can hear either u1or u2 is transmitting. Now, if u1 and u2 are sending to w1 and w2, respectively, it is possible that both transmissions can succeed simultaneously if u1 is not within w2’s interference range and u2 is not within w1’s interference range.
∑ u ∈ I t f u O ≤ B , ∀ t ∈ T.
∑ e ∈ E v O h e , t ≤ 1 , ∀ v ∈ U , t ∈ 1 , … , T .
This means that a node cannot transmit on more than one link during the same time slot.
T is the number of time slots a packet spends waiting in the transmission queuing at any node. Since the queuing delay can vary from 0 up to T−1 time slots, we estimate L = T − 1 2 . In order to for this estimate to be accurate and in order to insure the best possible performance, a search for the minimum feasible schedule length will be necessary. We do so following the method pointed out in . Namely, we formulate the problem starting from T=2 and attempt to solve the MIP problem. As long as the MIP is infeasible, we continue to increase the schedule length T until we find the minimum T for which the ILP formulation is feasible.
The objective function determines the goal of the deployment optimization. In general, the objective can be (1) a collective measure, such as minimizing the average end-to-end delay and minimizing the total energy-consumption rate or (2) an extreme measure, such as minimizing the worst case end-to-end delay or maximizing the worst case node lifetime.
τ k i E = ∑ e ∈ k i τ e , ∀ u ∈ U , t ∈ T , k i ∈ K u , t .
E τ u , t E = ∑ k i ∈ K u , t f k i τ k i E ∑ k i ∈ K u , t f k u , t i .
f e = ∑ u ∈ U ∑ t ∈ T ∑ k i ∈ K u , t : e ∈ k i f k i .
δ e , k i = 1 , e ∈ k i 0 , otherwise .
f e = ∑ u ∈ U ∑ t ∈ T ∑ k i ∈ K u , t δ e , k i f k i .
where g u = ∑ t ∈ T ∑ k i ∈ K u , t f k i .
E τ E = ∑ u ∈ U ∑ t ∈ T ∑ k i ∈ K u , t f k i ∑ e ∈ k i τ e G = 1 G ∑ e ∈ E f e . τ e .
Minimize 1 G ∑ e ∈ E f e . τ e .
π k i E = ∑ e ∈ k i π e , ∀ u ∈ U , t ∈ T , k i ∈ K u , t .
E [ π E ] = 1 G ∑ e ∈ E f e . π e .
Minimize 1 G ∑ e ∈ E f e . π e .
When the optimization objective is to minimize the overall average end-to-end delay, some sources maybe excessively penalized with a much longer delay. In monitoring applications where uniform response time is favored, the optimization objective has to be minimizing the worst case, per-source average delay. In other words, the objective is to minimize the average delay observed by packets from each source taken separately, to guarantee the best possible worst case scenario. In order to define this objective, we define a set of new flow variables, fe,u to denote the portion of the flow in link e that is generated originally by node u. If no path from u to the virtual sink uses link e, this implies that fe,u=0.
τ u E = 1 g u ∑ e ∈ E f e , u τ e , ∀ u ∈ U.
τ u E ≤ U τ .
We conducted extensive simulation to evaluate our gateway deployment optimization framework. We assumed that acoustic transceivers of all nodes, both underwater nodes and surface gateways, to be homogeneous and, therefore, the communication range is assumed to be constant for all nodes. We assume that sensor nodes are either stationary or that their motion is correlated strongly enough to assume that their relative locations are fixed. We adopt the pessimistic interference model. To reduce the problem complexity, we assume a lightly loaded, i.e., such that channel access delays and queuing delays can be safely ignored. Since both channel access delay and queuing delay are functions of network load (i.e., flow), keeping the network very lightly loaded justifies the assumption that the queuing delay is constant, hence allowing the linearization of the formulation and the use of LP solvers. When the load is increased, the non-linear formulation can be solved similarly by piece-wise linearization algorithms, such as the Frank-Wolfe algorithm. Although the problem can be solved for a choice of optimization goals, we limit our focus on the simplest optimization goals, namely minimizing the average delay and minimizing the average power consumption. The LP solver uses a brute-force search algorithm to find the optimal gateway deployment locations by numerating all possible candidate solutions and checking whether each satisfies the problem’s statement.
In order to evaluate the benefits and the performance of the gateway deployment optimization techniques, we used the following simulation setting.
Throughout the experiments, we fixed the packet length L = 400 bits, the underwater acoustic propagation velocity υ = 1.5 km/s, and the transmission power is set to a constant of 1 W/s per packet time. The communication range for the underwater modems for all nodes is fixed at R C = 150. We also fixed the area of deployment to a square area of 600 m × 600 m horizontal extent and fixed the candidate gateway deployment positions to a 5 × 5 square mesh of points spaced 150 m apart.
The depth of all underwater sensors is arbitrarily set to 100 m, such that each of the underwater sensors, regardless of its horizontal location, is within the communication range of at least one surface gateway candidate position, thus satisfying the connectivity requirement. This guarantees that an optimal solution can be found by setting a large-enough limit on the number of surface gateway nodes, N. Finally, the data generation rate at each underwater sensor is set to 1 packet per second. The acoustic channel effective bit rate B is varied among 5, 10, and 50 kbps. Accordingly, the packet transmission time τ=80, 40, and 8 ms, respectively, and the data generation rate g= 0.08, 0.04, and 0.008 packets per packet time, and the energy consumption per packet transfer π S = 80, 40, and 8 W, respectively.
When the number of allowed surface-level gateway nodes increase, the performance characteristics, average delay or average power consumption, is expected to improve. To verify that, we vary the number of allowed surface nodes from 1 to 25 nodes and solve the optimization problem to get the optimal average delay or energy. Results show that an increase in the number of surface gateways can dramatically enhance performance, especially when the network is lightly loaded.
Intuitively, when the ratio of total data generation rate to the per-node channel bandwidth increases, the minimum number of surface-level nodes required to make the problem feasible increases. This is due to the fact that surface gateways will saturate with incoming traffic and, therefore, more nodes will be needed to handle the additional traffic corresponding to the increased data generation rate. On the other hand, increasing channel capacity reduces the network load, and consequently, our assumptions about ignoring queuing delays become more realistic. To demonstrate the effect of channel capacity on the quality of the solution, we solve the deployment optimization problem for different link capacities, namely 5, 10, and 50 kbps.
If the set of candidate surface gateway positions is preset, the locations of underwater sensors and the distribution of data generation load among them are expected to affect the benefit of adding more surface gateways. If underwater sensors are clustered in groups, less surface gateways are expected to feasibly route all traffic to the surface, compared to the case when underwater sensors are spread evenly over the deployment area. On the other hand, clustering increases the odds of collision and, in the case of high traffic loads, can negatively affect delay and energy consumption. To study the effect of the deployment scheme of the given set of underwater sensors on the result of the surface gateway deployment optimization, we use two underwater deployment patterns.
The uniform underwater deployment was chosen because the uniformity of the solution simplifies the process of verifying the results. The chosen underwater deployment consists of a 7 × 7 planar mesh of sensor nodes. The distance between two adjacent nodes is 100 m, and therefore, the nodes cover the entire 600 × 600-m area. This problem setting is illustrated in Figure 2.
It was similar to the uniform underwater deployment, except that the 49 underwater sensor nodes are distributed at random within the 600 × 600-m underwater area. This problem setting is illustrated in Figure 3.
Results show that an increase in the number of surface gateways can dramatically enhance performance, especially when the network is lightly loaded. For example, Figure 4 shows that the expected delay corresponding to B = 50 kbps can be reduced from 0.26 to 0.16 s using four surface gateways instead of one. It is also worth noting that the improvement gained by adding a surface gateway diminishes as the number of surface gateways increase. After a certain number of surface gateways, depending on underwater deployment and other factors, any additional surface nodes have negligible effect on the performance of the network. This is due to the fact that at that point, all underwater nodes communicate with the a surface gateway at the candidate position nearest to each of them, and therefore, further addition of surface nodes becomes redundant.
Average delay, uniform underwater deployment.
Simulation results show that the performance improvement resulting from the addition of more surface gateway nodes diminishes when the network load increases, confirming our expectations as explained before. For example, Figure 5 shows that the heavily loaded network, corresponding to the channel capacity of 5 kbps has a smaller dynamic range of 0.2/0.08 = 2.5 than the lightly loaded network corresponding to B = 50 kbps, whose dynamic range is equal to 1.2/0.8 = 1.5. Figures 4 and 5 show the effect of varying the channel capacity, in the case of uniform underwater deployment, on the expected delay and expected energy consumption, respectively. Figures 6 and 7 show the effect of varying the channel capacity in the case of random underwater deployment, on the expected delay and expected energy consumption, respectively.
Average energy, uniform underwater deployment.
Average delay, random underwater deployment.
Average energy, random underwater deployment.
Figures 8 and 9 compare the results of the uniform underwater deployment case and the random underwater deployment case at a fixed channel capacity of 10 kbps. When the number of surface gateways is small, the randomly distributed underwater deployment suffers more congestion and therefore performs slightly poorer than the uniformly distributed counterpart in both delay and energy-consumption metrics. When the number of surface gateways increases, the effect of congestion diminishes, and the effect of clustering grows stronger. After a certain number of surface gateways, the energy consumption of the randomly distributed underwater deployments converges to that of the uniformly distributed case because, eventually, each underwater node becomes one hop away from a surface gateway. Although Figure 8 shows that the delay of the randomly distributed case eventually becomes lower than the uniformly distributed case is not necessarily always true. The problem instance shown in Figure 3 happened to have an average distance between underwater nodes and candidate surface positions, lower than that in the uniformly distributed case in Figure 2, and therefore, the randomly distributed underwater deployment case exhibits less average propagation delay. The experiments were repeated for several random underwater deployments to confirm that the results exhibit the same trends. Figures 10, 11, 12 and 13 illustrate two more samples for the random deployment results.
Average delay, uniform vs. random underwater deployment.
Average energy, uniform vs. random underwater deployment.
Average delay, random underwater deployment experiment 2.
Average energy, random underwater deployment experiment 2.
Average delay, random underwater deployment experiment 3.
Average energy, random underwater deployment experiment 3.
In this paper, we provided a generalized optimization framework for the surface gateway deployment problem. We demonstrated how to use the formulation to find the optimal placement of surface gateways with respect to a variety of optimization goals and a set of flow conservation constraints, interference constraints, and deployment constraints. We assisted our work by incorporating the optimal gateway optimization framework results in simulating the operation of the UWSN with multiple surface gateways. Our simulation results confirmed the potential for performance improvement using multiple surface gateways, such as reducing both average delay and energy consumption. It was also shown that the effect of the added surface gateways depends on the channel capacity or the network loading level, as well as the given underwater sensor deployment pattern. Our work presented here helps to pave the way for a wide variety of future research. One possible improvement is to optimize underwater and surface deployments jointly. Another is to consider mobility of surface gateways and a static UWSN with some level of location certainty models and integrate it as a new design parameter in our framework.
This work is supported in part by the US National Science Foundation under CAREER grant nos. 0644190, 1018422, 1127084, 115213, and 1205665.

References: V.

 V.

 V.

 V.

 V.

 V.

 V.

 V.