Elsevier

Ad Hoc Networks

Volume 34, November 2015, Pages 170-183
Ad Hoc Networks

Self-deployment of mobile underwater acoustic sensor networks for maximized coverage and guaranteed connectivity

https://doi.org/10.1016/j.adhoc.2014.09.013Get rights and content

Abstract

Self-deployment of sensors with maximized coverage in Underwater Acoustic Sensor Networks (UWASNs) is challenging due to difficulty of access to 3-D underwater environments. The problem is further compounded if the connectivity of the final network is desired. One possible approach to this problem is to drop the sensors on the water surface and then move them to certain depths in the water to maximize the 3-D coverage while maintaining the initial connectivity. In this paper, we propose a fully distributed node deployment scheme for UWASNs which only requires random dropping of sensors on the water surface. The idea is based on determining the connected dominating set (CDS) of the initial network on the surface and then adjust the depths of all neighbors of a particular dominator node (i.e., the backbone of the network) for minimizing the coverage overlaps among them while still keeping the connectivity with the dominator. The process starts with a leader node and spans all the dominators in the network for repositioning them. In addition to depth adjustment, we studied the effects of possible topology alterations due to water mobility caused by several factors such as waves, winds, currents, vortices or random surface effects, on network coverage and connectivity performance. On the one hand the mobility of nodes may help the topology to get stretched in 2-D, which helps to maximize the coverage in 3-D. On the other hand the mobility may cause the network to get partitioned where some of the nodes are disconnected from the rest of the topology. We investigated the best node deployment time where 2-D coverage is maximized and the network is still connected. To simulate the mobility of the sensors, we implemented meandering current mobility model which is one of the existing mobility models for UWASNs that fits our needs. The performance of the proposed approach is validated through simulation. Simulations results indicate that connectivity can be guaranteed regardless of the transmission and sensing range ratio with a coverage very close to a coverage-aware deployment approach.

Introduction

Underwater Acoustic Sensor Networks (UWASNs) consist of a large number of sensors on and underwater which can communicate via acoustic links [1], [2]. Similar to terrestrial wireless sensor networks (WSNs), these networks provide numerous advantages in terms of coverage quality, labor, cost and deployment as opposed to traditional monitoring tools. Within the last decade, a lot of studies focused on the issues related to communication underwater given that radio frequency (RF) signals do not travel underwater. The design of an acoustic modem, modeling of the channel, medium access, routing and sensing issues had been the main focus of researchers [3], [4].

Node deployment and mobility modeling have been other issues studied in UWASNs given that underwater is not readily accessible and sensors can drift due to the characteristics of the environment. The main goals in these studies were to reduce the cost and time of deployment with desired objectives in terms of coverage, accuracy and communication quality [5], [6]. The deployment is a crucial issue especially for the applications which require rapid and remote deployment. For instance, deployment of a UWASN for measuring the water quality of a lake or river which is believed to be contaminated requires rapid deployment to measure the water quality and inform the public. Another example would be the deployment of a UWASN in a remote ocean location for environmental or habitat monitoring which is not easily accessible.

For such cases, there needs to be a mechanism to remotely deploy sensors at a reasonably short time. Since manual deployment is out of question due to accessibility and time constraints, one possibility would be to randomly drop sensors on the water surface from an aerial vehicle and then expand them to 3-D with depth adjustment. This requires the ability of the sensors to adjust their depths in the water via a mechanism which can change the weight of the sensor using air or water such as the one described in [7]. The vertical movement of acoustic sensors resembles self-spreading of sensors in 2-D environments when they have the ability of moving. While there has been studies leveraging this capability of acoustic sensors to expand their coverage [5], [6], none of them can guarantee connectivity of the stretched network with a surface station so that all the collected data can be relayed to an on-shore station. To the best of our knowledge, self depth adjustment of sensors subject to connectivity constraint is a novel problem that has not been studied in the past. Connectivity introduces new challenges since a path from every sensor to the surface station needs to be guaranteed. This requires a controlled strategy maintained by the surface sink so that network connectivity is maintained. In a distributed context, this requires messaging among the sensors. In addition, the coverage can still be extended within the limits of connectivity. For this issue, we assume a spherical sensing coverage that exists with the ultrasonic sensors.

In this paper, we propose a novel autonomous deployment scheme for underwater ultrasonic sensors which can maximize the coverage in 3-D while guaranteeing the connectivity among the sensors and a surface sink node to collect data. Our scheme assumes an initially randomly deployed and connected UWASN on the surface of the water in 2-D. This can be achieved by randomly dropping a certain number of sensors in a targeted area [8]. The scheme then determines the connected dominating set (CDS) (i.e., a network backbone) of the whole UWASN at 2-D plane. The main goal here is to determine a backbone of the network consisting of nodes called dominators and then maintain the network connectivity underwater by keeping the network backbone connected (i.e. keeping only CDS edges). Two connected dominators can still maintain their connectivity while being stretched along the z-axis as much as possible in order to provide minimal sensing coverage overlapping until they stay in each other’s communication range. This idea is then applied to every dominator along with its dominator and dominatee (i.e., non-dominator) neighbors one by one. The approach is named as CDS-based Depth Computation Approach (CDA). The CDA algorithm runs on the dominator nodes in a turn-based manner.

To improve the coverage of the final 3-D network, we also exploit the mobility of the sensors. It is well-known that free-floating sensors on the water surface are subject to mobility due to several factors such as waves, winds, sub-surface currents, vortices or random surface effects. Such mobility on the water surface causes that the nodes move away from each other and thus the network topology alters gradually. In this paper, we study the effects of dynamic topology alteration due to mobility on network coverage and connectivity. Our goal is to utilize the network expansion in 2-D to improve the 3-D coverage of the resultant topology produced by CDA. We simulated the displacement of the network topology under Meandering Current Mobility [9] (MCM) model and determined best deployment time where the 2-D coverage is maximized and the network in 2-D is still connected.

The proposed approach is validated through extensive simulations and has been shown to guarantee the connectivity while achieving a 3-D coverage that is very close a baseline approach targeted for maximized coverage. We also show that the resultant topology has desirable characteristics in terms of average node degree and expected path length which are crucial for fault-tolerance and data delay.

Our contributions in this paper can be summarized as follows:

  • We propose an autonomous and efficient deployment scheme which guarantees connectivity of the sensors to the surface station while maximizing the coverage of the nodes.

  • We adapt CDS idea from graph theory for maintaining connectivity among the nodes and the surface station.

  • We determine the optimal time for the deployment time based on meandering mobility model in order to maximize coverage.

This paper is organized as follows. Next section summarizes the related work. Section 3 explains the preliminaries of the proposed scheme. In Section 4, we present the details of the proposed approach. Section 5 is dedicated to the effects of mobility model on network coverage and connectivity. Section 6 provides evaluation of the proposed approach. Finally, Section 7 concludes the paper.

Section snippets

Optimal solutions for coverage and connectivity in UWASNs

Achieving full coverage and connectivity in UWASNs has been well studied in the past, assuming both random and manual node deployment [10], [11]. For instance, the main goal in [10] is to analyze the implications of the sensing and communication ranges on coverage, connectivity and network diameter in an UWASN. The author derived conditions for the node transmission range required for achieving a degree of connectivity and coverage. In [11], Alam and Haas have investigated the problem of

Assumptions

Since part of our goal is to have an autonomous deployment, we assume that a large number of sensors dropped from a helicopter or boat at the surface or bottom of water randomly. We also assume that there are ultrasonic sensors [23] which can sense moving objects. These sensors send sound signals and wait for echoes which are similar to a radar. We assume a distance of 45.7 m for these signals which travel in every direction and thus forming a sphere for the sensing range. There are of course

Overview of the approach

Our proposed CDS-based Depth Computation Approach (CDA) for maximizing coverage is based on adjusting the depths of the sensor and sending them to 3-D locations within the water such that there will be minimal sensing overlap among the sensors. For instance, sensors which have sensing overlap in 2-D may eliminate this overlap by moving to different depths (i.e., z). Nevertheless, this may disconnect these two sensors if they move beyond their transmission range r. Therefore, we propose to

Effects of mobility model on network coverage and connectivity

The sensor nodes in UWSNs are subject to mobility due to several factors such as waves, currents, and wind. In our proposed deployment approach, such mobility can be utilized to improve the coverage given that the deployment of the sensors will not be manual and controlled. We consider situations where the water is not accessible due to environmental restrictions, cost and labor. In such cases, the sensor can be dropped from a helicopter or boat in a specific region. In this section, we analyze

Performance evaluation

The performance of the proposed CDA approach is validated through simulation. This section provides the simulation setup, baseline for comparison and performance results.

Conclusion

In this paper, we presented a purely distributed node deployment mechanism for UWASN with the idea of changing the depths of the sensors given that sensors can only move in vertical direction. The proposed approach is based on CDS of the sensors and runs in a turn-based manner. Once a turn come to a dominator (initially the leader node), the node computes the depths for its dominatees and neighbor dominators relative to itself while minimizing the coverage overlaps among its dominatees and

Acknowledgment

This work is supported in part by a research Grant from TUBITAK EEEAG (Grant No. 113E234).

Dr. Fatih Senel received his BS and MS degrees from in Computer Science from Bilkent University, Ankara, Turkey in 2005 and Southern Illinois University, Carbondale, IL in 2008 respectively. In between 2005 and 2007 he worked as a software engineer in Ankara. He received his PhD in Computer Science from University of Maryland Baltimore County in 2012. Currently he is an assistant professor in Computer Engineering Department at Antalya International University, Antalya, Turkey. He has served in

References (34)

  • I.F. Akyildiz et al.

    Underwater acoustic sensor networks: research challenges

    Ad Hoc Networks

    (2005)
  • K. Akkaya et al.

    Self-deployment of sensors for maximized coverage in underwater acoustic sensor networks

    Comput. Commun.

    (2009)
  • E. Cayirci et al.

    Wireless sensor networks for underwater surveillance systems

    Ad Hoc Networks

    (2006)
  • E. Sozer et al.

    Underwater acoustic networks

    IEEE J. Ocean. Eng.

    (2000)
  • J. Heidemann, W. Ye, J. Wills, A. Syed, Y. Li, Research challenges and applications for underwater sensor networking,...
  • J.-H. Cui, J. Kong, M. Gerla, S. Zhou, Challenges: building scalable and distributed underwater wireless sensor...
  • D. Pompili, T. Melodia, I.F. Akyildiz, Deployment analysis in underwater acoustic wireless sensor networks, in: Proc....
  • C. Detweiler, M. Doniec, I. Vasilescu, E. Basha, D. Rus, Autonomous depth adjustment for underwater sensor networks,...
  • C. Bettstetter

    On the connectivity of ad hoc networks

    Comput. J.

    (2004)
  • A. Caruso, F. Paparella, L. Vieira, M. Erol, G.M., The meandering current mobility model and its impact on underwater...
  • V. Ravelomanana

    Extremal properties of three-dimensional sensor networks with applications

    IEEE Trans. Mob. Comput.

    (2004)
  • S.N. Alam, Z. Haas, Coverage and connectivity in three-dimensional networks, in: Proc. of ACM Int’l Conf. on Mobile...
  • B. Liu et al.

    The redeployment issue in underwater sensor networks

  • F.X.L. Liu et al.

    Tfa: a scale-free network approach to topology formation in underwater acoustic sensor networks

    Adv. Wireless Sensor Networks

    (2013)
  • M.C. Domingo

    A topology reorganization scheme for reliable communication in underwater wireless sensor networks affected by shadow zones

    Sensors

    (2009)
  • G. Han et al.

    A survey on deployment algorithms in underwater acoustic sensor networks

    Int. J. Distrib. Sensor Networks

    (2013)
  • M. Erol, F. Vieira, M. Gerla, Auv-aided localization for underwater sensor networks, in: WASA 2007, International...
  • Cited by (0)

    Dr. Fatih Senel received his BS and MS degrees from in Computer Science from Bilkent University, Ankara, Turkey in 2005 and Southern Illinois University, Carbondale, IL in 2008 respectively. In between 2005 and 2007 he worked as a software engineer in Ankara. He received his PhD in Computer Science from University of Maryland Baltimore County in 2012. Currently he is an assistant professor in Computer Engineering Department at Antalya International University, Antalya, Turkey. He has served in TPC of many networking conferences such as Globecom and LCN. His research interests include topology management, fault-tolerance, node mobility, relay node placement in ad hoc wireless sensor, underwater networks and social networks. He is a member of IEEE.

    Dr. Kemal Akkaya is an associate professor in the Department of Electrical and Computer Engineering at Florida International University. He received his BS and MS in Computer Engineering from Bilkent University, Turkey and Middle-East Technical University, Turkey in 1997 and 1999 respectively. After working as a software developer in Ankara, Turkey, he moved to US in 2000 for pursuing a PhD degree in Computer Science. He received his PhD in Computer Science from University of Maryland Baltimore County in 2005 and joined the department of Computer Science at Southern Illinois University in 2005. Dr. Akkaya was a visiting professor at The George Washington University in Fall 2013. His current research interests include energy aware routing, topology control, security and quality of service issues in a variety of wireless networks such as sensor networks, social networks, multimedia sensor networks, smart-grid communication networks and vehicular networks. Dr. Akkaya is a member of IEEE. He is the area editor of Elsevier Ad Hoc Network Journal and serves on the editorial board of IEEE Communication Surveys and Tutorials. He has served as the guest editor for Journal of High Speed Networks, Computer Communications Journal, Elsevier Ad Hoc Networks Journal and in the TPC of many leading wireless networking conferences including IEEE ICC, Globecom, LCN and WCNC. He has published over 80 papers in peer reviewed journal and conferences. He has received Top Cited” article award from Elsevier in 2010.

    Melike Erol-Kantarci is an assistant professor in the Department of Electrical and Computer Engineering at Clarkson University. Previously, she was the coordinator of the Smart Grid Communications Lab and a postdoctoral fellow at the School of Electrical Engineering and Computer Science, University of Ottawa, Canada. She received the Ph.D. and M.Sc. degrees in Computer Engineering in 2009 and 2004, respectively. During her Ph.D. studies, she was a Fulbright visiting researcher at the Computer Science Department of the University of California Los Angeles (UCLA). She received the B.Sc. degree from the Department of Control and Computer Engineering of the Istanbul Technical University, in 2001. She has received a Fulbright PhD Research Scholarship (2006) and the Siemens Excellence Award (2004), and she has won two Outstanding/Best Paper Awards. She is an occasional reviewer of transactions and journals, and a TPC member for various conferences. Her main research interests are wireless sensor networks, smart grid, cyber-physical systems, electrification of transportation, underwater sensor networks, mobility modeling, localization and internet traffic analysis. She is an editor of the International Journal of Distributed Sensor Networks published by Hindawi. She is an IEEE member and the vice chair for Women in Engineering (WIE) at the IEEE Ottawa Section.

    Turgay Yilmaz received the BS degree in computer engineering from Bilkent University in 2004 and the MS degree in computer engineering from Middle East Technical University (METU) in 2008, where he is currently working towards the PhD degree at METU. He worked as a Computer Engineer in EES, HAVELSAN, and Rakuten Institute of Technology. In addition, he was affiliated with the Toyoda-Kitsuregawa Lab. in The University of Tokyo, as a visiting research associate for 1.5 years. Currently, he works as a system architect at TURKSAT for the e-Goverment Portal project. His research interests include multimedia databases, information fusion, multimedia retrieval, intelligent systems, fuzzy systems, machine learning and soft computing. He is a member of IEEE.

    View full text