Collaboration among drone swarms in various applications often requires dynamic data exchange to optimize their missions. When employing device-to-device (D2D) communications, drones must form connected topologies enabling multi-hop communication. Maintaining a connected topology during their movement to new locations is a major challenge that has not been tackled in the literature. In this paper, we first formalize this problem, proving the decision version is NP-Hard, and break it into sub-problems, detailing their complexity under certain constraints. We then propose polynomial time solutions to these subproblems. Our proposed approach first makes a location assignment for each drone to determine where to move as their next locations. Next, our approach relocates each drone to their designated target location without losing in-network connectivity of the drone topology. We achieve this by leveraging a two-step approach: contraction and re-expansion. In the contraction phase, drones converge towards a specific location, reducing network diameter and increasing connectivity. In the expansion phase, drones disperse to their new target positions. Mathematical proofs and extensive simulations validate our method’s effectiveness in maintaining connectivity during drone relocations.

This paper proposes an optimal deployment strategy for Unmanned Aerial Vehicles (UAVs) to create a wireless mesh network above ground users in an area without internet connectivity. The deployment strategy is aimed at maximizing user coverage and providing in-network connectivity, even with the added challenge of ground user mobility. The area is modeled as a grid, and ground user mobility is simulated using BonnMotion and represented as a list of temporal heatmaps. The problem is formulated as a mixed integer linear program with a network connectivity constraint based on network flows. The proposed approach’s performance is evaluated through simulation, and the results validate its effectiveness in terms of coverage. Overall, this study demonstrates the potential of UAVs to serve as a flying network backbone, providing temporary connectivity to users.

Advanced Metering Infrastructure (AMI) is an indispensable part of a Smart Grid (SG) initiative. AMI applications collect data measured by smart meters in the SG. This process may leak information about consumers. In this paper, we build an IEEE 802.11s-based SG AMI network testbed consisting of Beaglebone Black boards and investigate the performance of privacy-preserving protocols in real-life and compare it with the ns-3 simulations. We develop an application that collects data periodically. This mechanism runs in two modes: Hop-by-hop and end-to-end aggregation. The application is tested on TCP and UDP. We use Paillier cryptosystem for privacy, and ECDSA for authentication. The application is also simulated in ns-3. The testbed results are compared with the ns-3 results in terms of packet delivery ratio, throughput and data collection completion time. Comparison showed that the tested privacy-preserving protocol behavior may not accurately reflect that of ns-3, especially with data completion time metric.

Abstract Careful deployment of nodes in underwater acoustic sensor networks in a distributed manner with the goal of maximized coverage and guaranteed connectivity is a challenging problem because it is very difficult and costly to access the 3D underwater environment. This paper presents a novel algorithm for self‐deployment of nodes in underwater acoustic sensor networks assuming that the nodes are randomly dropped to the water surface and form a densely populated connected network at the water surface. The idea of the algorithm is based on calculating an optimized depth for each node in the network in such a way that the possible sensing coverage overlaps are minimized and the connectivity of final topology is guaranteed. The algorithm has three main phases. In the first phase, nodes are organized in a tree structure that is rooted at the surface station. In the second phase, the depths for all nodes are computed iteratively at surface station. In the final phase, the calculated depths are distributed to nodes so that the nodes start sinking. The performance of the proposed approach is validated through simulation. We observed that the proposed approach performs at least 10% better in terms of network coverage than contemporary schemes in the literature. Copyright © 2016 John Wiley & Sons, Ltd.

In most applications of Underwater Acoustic Sensor Networks, network connectivity is required for data exchange, data aggregation and relaying the data to a surface station. However, such connectivity can be lost due to failure of some sensor nodes which creates disruptions to the network operations. In this paper, we present two algorithms, namely BMR and DURA, which can detect network partitioning due to such node failures and re-establish network connectivity through controlled depth adjustment of nodes in a distributed manner. The idea is to first identify whether the failure of each node will cause partitioning or not based on localized information. If partitioning is to occur as a result of the possible failure of a particular node, both BMR and DURA designates backup nodes to handle the recovery in the future. While DURA aims to localize the recovery process and minimize the movement overhead on the nodes, BMR strives to reduce the recovery completion time at the expense of increased movement overhead by employing a two-phase block movement. The performance of the proposed approaches is validated through extensive simulations. The results indicated that DURA can provide energy savings as much as a centralized exhaustive approach while BMR provided the fastest recovery time.

In addition to sensors, cameras have started to be deployed in underwater acoustic sensor networks (UWASNs) for improved monitoring. However, since cameras already consume a lot of energy, they are kept in sleep mode most of the time and only activated when sensors detect a target. Due to random deployment and lack of cameras, there may not be any cameras within the vicinity of a detected target. A possible solution to this problem is to relocate remote cameras via vertical movements to certain locations to capture the target. In this paper, we propose a distributed camera selection and relocation scheme in UWASNs to maximize the coverage of the detected targets with the least vertical movement of cameras. The problem is modeled as a weighted set covering problem and solved using a greedy heuristic. The performance of the proposed approach is assessed through extensive simulations under a variety of conditions.

Disjoint Wireless Sensor Networks (WSNs) can be reconnected by placing additional relay nodes in the damaged areas. However, in some cases there may not be enough relays to reconnect all the partitions with the sink node. In such a case, some of the relays can exploit their motion capabilities and temporarily act as a mobile data collector (MDC) between partitions providing intermittent connectivity for the nodes sitting in those partitions. Nonetheless, due to increased data latency intermittent connectivity creates, the number of such MDCs need to be minimized. On the other hand, given that the energy resources for an MDC is limited, an upper bound on the travel distance overhead for an MDC needs to be imposed. This paper proposes a relay placement algorithm which guarantees connectivity by maximizing the number of stable connections while meeting the maximum tour constraint on the MDCs. The approach first determines the number and location of relays to restore connectivity by establishing stable links using a Steiner Minimum Tree (SMT) heuristic. Assuming that the number of available relays is less than the needed count, the algorithm determines how many of the available relays need to be stationary and how many of them should act as MDCs. By initially assuming all relays as MDCs, an iterative procedure is followed to reduce the MDC count while meeting the maximum tour length constraint. Specifically, groups of partitions are created and assigned to MDCs for touring. The proposed approach is validated with extensive simulations under a variety of conditions.

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 required. One possible approach is to drop the sensors on the surface and then move them to certain depths in the water to maximize the 3-D coverage while maintaining the connectivity. In this paper, we propose a purely distributed node deployment scheme for UWASNs which only requires random dropping of sensors on the water surface. The goal is to expand the initial network to 3-D with maximized coverage and guaranteed connectivity with a surface station. The idea is based on determining the connected dominating set of the initial network and then adjust the depths of all dominatee and dominator neighbors of a particular dominator node 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. 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.

Relay node placement in wireless sensor networks has gained importance due to its potential use in prolonging network life time, reducing data latency, and establishing connected topologies. In this paper we studied the relay node placement problem to establish multi-hop communication paths between every pair terminals (i.e., sensors) where each hop in the path is less than a common communication range. Such a problem is defined as Steiner Tree problem with minimum Steiner points and Bounded Edge-Length problem which is known to be NP-Hard. This paper presents a novel relay node placement heuristics called Incremental Optimization based on Delaunay Triangulation (IO-DT). The algorithm takes advantage of feasibility of finding optimal solution for the case of three terminals. IO-DT calculates the Delaunay triangulation (DT) of terminals and iterates over the formed triangles. In each iteration the algorithm steinerizes a triangle as part of the final topology if selecting such a triangle provides a reduction in total number of relay node required as compared to the minimum spanning tree (mst) based approach. The time complexity of IO-DT is quadratic in the number of terminals, which is superior to competing schemes. The performance of the algorithm is validated through simulation.

Due to inhospitable environments, the actors/sensors in Mobile Sensor/Actor Networks are subject to various damages which can disrupt the data delivery and cooperation. Typically, the damages affect the existing routes and may even cause network partitioning. In such a case, the set of actors/sensors disconnected from the rest of the network, namely a partition, can be re-connected with the network through topology adjustment by exploiting node mobility. However, movement of the nodes consumes significant energy which needs to be minimized. In this paper, we propose an effective yet scalable heuristic approach for restoring network connectivity while minimizing the total movement distance of the nodes. Given that the nodes can move to infinitely many locations in the damaged area, the basic motivation of the heuristic is to reduce the number of locations where the nodes can move. For this purpose, a minimum set of relay points is identified first by running a relay node placement heuristic that can ensure connectivity. Existing nodes in the partitions are then used to fill the relay points based on a greedy heuristic. When selecting nodes from the partitions, the nodes that do not cause further disconnectivity in the partition are picked. This is done by determining the connected dominating set of the partition and identifying the dominatee nodes. The experiment results show that the proposed approach not only performs very close to a near-optimal solution but also scales well when the number of nodes or partitions are increased.

Due to harsh environmental conditions a Wireless Sensor Network (WSN) may suffer from large scale damage where many nodes fail simultaneously and thus the network gets partitioned into several disjoint network segments. Restoring intersegment connectivity is essential to avoid negative effects on the application. Employing mobile data collectors (MDCs), which by repositioning-facilitate the establishment of communication links between segments, may provide flexible solution to this problem. However the problem of finding shortest tours for MDCs is NP-Hard. In this paper we study the problem under constrained number of MDCs which makes the problem more challenging. We present a polynomial time heuristic for Interconnecting Disjoint Segments with k MDCs (IDM-kMDC). IDM-kMDC opts to minimize the tour lengths and balance the load on the k available MDCs. We model each segment by a representative. The IDM-kMDC heuristic finds k-subsets of representatives, computes an optimized tour for each subset and assigns one MDC for each tour. The performance of the algorithm is validated through simulation.

Due to the harsh operation conditions a wireless sensor network (WSN) may suffer large scale damage where many nodes fail simultaneously causing the network to get partitioned into multiple disjoint segments. Restoring network connectivity in such a case is very crucial to avoid negative effects on the application. This paper investigates a relay node (RN) placement strategy to establish inter-segment connectivity and proposes CIST, an algorithm for forming a Connected Inter-Segment Topology. CIST uses segment representation as a means of optimization for minimizing the required number of RNs. The idea behind the algorithm is to find the best subsets of three segments and form a triangular Steiner Minimum Tree with minimum Steiner Points and federate the remaining segment through populating the RNs along mst edges. The performance of CIST is validated through simulation.

Mobility has been introduced to sensor networks through the deployment of movable nodes. In movable wireless networks, network connectivity among the nodes is a crucial factor in order to relay data to the sink node, exchange data for collaboration, and perform data aggregation. However, such connectivity can be lost due to a failure of one or more nodes. Even a single node failure may partition the network, and thus, eventually reduce the quality and efficiency of the network operation. To handle this connectivity problem, we present PADRA to detect possible partitions, and then, restore the network connectivity through controlled relocation of movable nodes. The idea is to identify whether or not the failure of a node will cause partitioning in advance in a distributed manner. If a partitioning is to occur, PADRA designates a failure handler to initiate the connectivity restoration process. The overall goal in this process is to localize the scope of the recovery and minimize the overhead imposed on the nodes. We further extend PADRA to handle multiple node failures. The approach, namely, MDAPRA strives to provide a mutual exclusion mechanism in repositioning the nodes to restore connectivity. The effectiveness of the proposed approaches is validated through simulation experiments.

Wireless sensor networks (WSN) can increase the efficiency of many real-life applications through the collaboration of thousands of miniaturized sensors which can be deployed unattended in inhospitable environments. Due to the harsh surroundings and violent nature of the applications, the network sometimes suffers a large scale damage that involves many nodes and would thus create multiple disjoint partitions. This paper investigates a strategy for recovering from such damage through the placement of relay nodes and promotes a novel approach. The proposed approach opts to re-establish connectivity using the least number of relays while ensuring certain quality in the formed topology. Unlike contemporary schemes that form a minimum spanning tree among the isolated segments, the proposed approach establishes a topology that resembles a spider web, for which the segments are situated at the perimeter. Such a topology not only exhibits stronger connectivity than a minimum spanning tree but also achieves better sensor coverage and enables balanced distribution of traffic load among the employed relays. The simulation results demonstrate the effectiveness of the proposed recovery algorithm.

Wireless sensor and actor networks (WSANs) additionally employ actor nodes within the wireless sensor network (WSN) which can process the sensed data and perform certain actions based on this collected data. In most applications, inter-actor coordination is required to provide the best response. This suggests that the employed actors should form and maintain a connected inter-actor network at all times. However, WSANs often operate unattended in harsh environments where actors can easily fail or get damaged. Such failures can partition the inter-actor network and thus eventually make the network useless. In order to handle such failures, we present a connected dominating set (CDS) based partition detection and recovery algorithm. The idea is to identify whether the failure of a node causes partitioning or not in advance. If a partitioning is to occur, the algorithm designates one of the neighboring nodes to initiate the connectivity restoration process. This process involves repositioning of a set of actors in order to restore the connectivity. The overall goal in this restoration process is to localize the scope of the recovery and minimize the movement overhead imposed on the involved actors. The effectiveness of the approach is validated through simulation experiments.

Wireless sensor and actor networks (WSANs) employ powerful and mobile actor nodes that can perform application specific actions based on the received data from the sensors. As most of these actions are performed collaboratively among the actors, inter-actor connectivity is one of the desirable features of WSANs. In this paper, we propose a novel distributed algorithm for establishing a connected inter-actor network topology. Considering an initially partitioned actor network with intra-connected sub-networks, our algorithm pursues a coordinated actor movement in order to connect the sub-networks. The goal of this movement is to both minimize the total and maximum travel distances of the individual actors. Our algorithm considers the minimum connected dominating set of each sub-network when picking the appropriate actor to move so that the connectivity of each sub-network is not violated. We analytically study the performance of our algorithm. Extensive simulation experiments validate the analytical results and confirm the effectiveness of our approach.