Managing the Mobility of a Mobile Sensor Network Using Network Dynamics

It has been discussed in the literature that the mobility of a mobile sensor network (MSN) can be used to improve its sensing coverage. How the mobility can efficiently be managed toward a better coverage, however, remains unanswered. In this paper, motivated by classical dynamics that study the movement of objects, we propose the concept of network dynamics and define the associated potential functions that capture the operational goals, as well as the environment of an MSN. We find that in managing the mobility of an MSN, Newton's laws of motion in classical dynamics are insufficient, for they introduce oscillations into the movement of sensor nodes. Instead, in network dynamics, the laws of motion are formulated using the steepest descent method in optimization. Based on the network dynamics model, we first devise a parallel and distributed algorithm (parallel and distributed network dynamics (PDND)) that runs on each sensor node to guide its movement. PDND then turns sensor nodes into autonomous entities that are capable of adjusting their locations according to the operational goals and environmental changes. After that, we formally prove the convergence of PDND. Finally, we apply PDND in three applications to demonstrate its effectiveness.

Related papers:

title: Real-Time Obstacle Avoidance for Manipulators and Mobile Robots
abstract: This paper presents a unique real-time obstacle avoidance approach for manipulators and mobile robots based on the artificial potential field concept. Collision avoidance, tradi tionally considered a high level planning problem, can be effectively distributed between different levels of control, al lowing real-time robot operations in a complex environment. This method has been extended to moving obstacles by using a time-varying artificial patential field. We have applied this obstacle avoidance scheme to robot arm mechanisms and have used a new approach to the general problem of real-time manipulator control. We reformulated the manipulator con trol problem as direct control of manipulator motion in oper ational space—the space in which the task is originally described—rather than as control of the task's corresponding joint space motion obtained only after geometric and kine matic transformation. Outside the obstacles' regions of influ ence, we caused the end effector to move in a straight line with an upper speed limit. The artificial potential field ap proach has been extended to collision avoidance for all ma nipulator links. In addition, a joint space artificial potential field is used to satisfy the manipulator internal joint con straints. This method has been implemented in the COSMOS system for a PUMA 560 robot. Real-time collision avoidance demonstrations on moving obstacles have been performed by using visual sensing.

title: Virtual attractive-repulsive potentials for cooperative control of second order dynamic vehicles on the Caltech MVWT
abstract: We consider a motion planning method based on cooperative biological swarming models with virtual attractive and repulsive potentials (VARP). We derive a map between the model and fan speeds for the Kelly, a second order vehicle on the Caltech multi vehicle wireless testbed. The motion planning map results leads to the development and implementation of a point to point controller which is subsequently used as part of a cooperative searching algorithm. The VARP control method is scalable and can be used to organize a swarm of robotic vehicles.

title: Sensor deployment and target localization based on virtual forces
abstract: The effectiveness of cluster-based distributed sensor networks depends to a large extent on the coverage provided by the sensor deployment. We propose a virtual force algorithm (VFA) as a sensor deployment strategy to enhance the coverage after an initial random placement of sensors. For a given number of sensors, the VFA algorithm attempts to maximize the sensor field coverage. A judicious combination of attractive and repulsive forces is used to determine virtual motion paths and the rate of movement for the randomly-placed sensors. Once the effective sensor positions are identified, a one-time movement with energy consideration incorporated is carried out, i.e., the sensors are redeployed to these positions. We also propose a novel probabilistic target localization algorithm that is executed by the cluster head. The localization results are used by the cluster head to query only a few sensors (out of those that report the presence of a target) for more detailed information. Simulation results are presented to demonstrate the effectiveness of the proposed approach.

title: Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem
abstract: This paper considers the problem of deploying a mobile sensor network in an unknown environment. A mobile sensor network is composed of a distributed collection of nodes, each of which has sensing, computation, communication and locomotion capabilities. Such networks are capable of self-deployment; i.e., starting from some compact initial configuration, the nodes in the network can spread out such that the area ‘covered’ by the network is maximized. In this paper, we present a potential-field-based approach to deployment. The fields are constructed such that each node is repelled by both obstacles and by other nodes, thereby forcing the network to spread itself throughout the environment. The approach is both distributed and scalable.

title: Constrained coverage for mobile sensor networks
abstract: We consider the problem of self-deployment of a mobile sensor network. We are interested in a deployment strategy that maximizes the area coverage of the network with the constraint that each of the nodes has at least K neighbors, where K is a user-specified parameter. We propose an algorithm based on artificial potential fields which is distributed, scalable and does not require a prior map of the environment. Simulations establish that the resulting networks have the required degree with a high probability, are well connected and achieve good coverage. We present analytical results for the coverage achievable by uniform random and symmetrically tiled network configurations and use these to evaluate the performance of our algorithm.

title: Virtual leaders, artificial potentials and coordinated control of groups
abstract: We present a framework for coordinated and distributed control of multiple autonomous vehicles using artificial potentials and virtual leaders. Artificial potentials define interaction control forces between neighboring vehicles and are designed to enforce a desired inter-vehicle spacing. A virtual leader is a moving reference point that influences vehicles in its neighborhood by means of additional artificial potentials. Virtual leaders can be used to manipulate group geometry and direct the motion of the group. The approach provides a construction for a Lyapunov function to prove closed-loop stability using the system kinetic energy and the artificial potential energy. Dissipative control terms are included to achieve asymptotic stability. The framework allows for a homogeneous group with no ordering of vehicles; this adds robustness of the group to a single vehicle failure.

title: Peer-to-peer model for the area coverage and cooperative control of mobile sensor networks
abstract: This paper presents a novel model and distributed algorithms for the cooperation and redeployment of mobile sensor networks. A mobile sensor network composes of a collection of wireless connected mobile robots equipped with a variety of sensors. In such a sensor network, each mobile node has sensing, computation, communication, and locomotion capabilities. The locomotion ability enhances the autonomous deployment of the system. The system can be rapidly deployed to hostile environment, inaccessible terrains or disaster relief operations. The mobile sensor network is essentially a cooperative multiple robot system. This paper first presents a peer-to-peer model to define the relationship between neighboring communicating robots. Delaunay Triangulation and Voronoi diagrams are used to define the geometrical relationship between sensor nodes. This distributed model allows formal analysis for the fusion of spatio-temporal sensory information of the network. Based on the distributed model, this paper discusses a fault tolerant algorithm for autonomous self-deployment of the mobile robots. The algorithm considers the environment constraints, the presence of obstacles and the nonholonomic constraints of the robots. The distributed algorithm enables the system to reconfigure itself such that the area covered by the system can be enlarged. Simulation results have shown the effectiveness of the distributed model and deployment algorithms.

title: Energy-efficient deployment of Intelligent Mobile sensor networks
abstract: Many visions of the future include people immersed in an environment surrounded by sensors and intelligent devices, which use smart infrastructures to improve the quality of life and safety in emergency situations. Ubiquitous communication enables these sensors or intelligent devices to communicate with each other and the user or a decision maker by means of ad hoc wireless networking. Organization and optimization of network resources are essential to provide ubiquitous communication for a longer duration in large-scale networks and are helpful to migrate intelligence from higher and remote levels to lower and local levels. In this paper, distributed energy-efficient deployment algorithms for mobile sensors and intelligent devices that form an Ambient Intelligent network are proposed. These algorithms employ a synergistic combination of cluster structuring and a peer-to-peer deployment scheme. An energy-efficient deployment algorithm based on Voronoi diagrams is also proposed here. Performance of our algorithms is evaluated in terms of coverage, uniformity, and time and distance traveled until the algorithm converges. Our algorithms are shown to exhibit excellent performance.

title: Movement-assisted sensor deployment
abstract: Adequate coverage is very important for sensor networks to fulfill the issued sensing tasks. In many working environments, it is necessary to make use of mobile sensors, which can move to the correct places to provide the required coverage. In this paper, we study the problem of placing mobile sensors to get high coverage. Based on Voronoi diagrams, we design two sets of distributed protocols for controlling the movement of sensors, one favoring communication and one favoring movement. In each set of protocols, we use Voronoi diagrams to detect coverage holes and use one of three algorithms to calculate the target locations of sensors it holes exist. Simulation results show the effectiveness of our protocols and give insight on choosing protocols and calculation algorithms under different application requirements and working conditions.

title: Coverage control for mobile sensing networks
abstract: This paper describes decentralized control laws for the coordination of multiple vehicles performing spatially distributed tasks. The control laws are based on a gradient descent scheme applied to a class of decentralized utility functions that encode optimal coverage and sensing policies. These utility functions are studied in geographical optimization problems and they arise naturally in vector quantization and in sensor allocation tasks. The approach exploits the computational geometry of spatial structures such as Voronoi diagrams.

title: Autonomous underwater vehicles: future platforms for fisheries acoustics
abstract: Autonomous underwater vehicles (AUVs) are unmanned submersibles that can be pre-programmed to navigate in three dimensions under water. The technological advances required for reliable deployment, mission control, performance, and recovery of AUVs have developed considerably over the past 10 years. Currently, there are several vehicles operating successfully in the offshore industries as well as in the applied and academic oceanographic sciences. This article reviews the application of AUVs to fisheries- and plankton-acoustics research. Specifications of the main AUVs currently in operation are given. Compared to traditional platforms for acoustic instruments, AUVs can sample previously impenetrable environments such as the sea surface, the deep sea, and under-sea ice. Furthermore, AUVs are typically small, quiet, and have the potential to operate at low cost and be unconstrained by the vagaries of weather. Examples of how these traits may be utilized in fisheries-acoustics science are given with reference to previous work in the North Sea and Southern Ocean and to potential future applications. Concurrent advances in multi-beam sonar technology and species identification, using multi-frequency and broadband sonars, will further enhance the utility of AUVs for fisheries acoustics. However, before many of the more prospective applications can be accomplished, advances in power-source technology are required to increase the range of operation. The paper ends by considering developments that may turn AUVs from objects sometimes perceived as science fiction into instruments used routinely to gather scientific facts

title: Distributed localization in wireless sensor networks: a quantitative compariso
abstract: This paper studies the problem of determining the node locations in ad-hoc sensor networks. We compare three distributed localization algorithms (Ad-hoc positioning, Robust positioning, and N-hop multilateration) on a single simulation platform. The algorithms share a common, three-phase structure: (1) determine node-anchor distances, (2) compute node positions, and (3) optionally refine the positions through an iterative procedure. We present a detailed analysis comparing the various alternatives for each phase, as well as a head-to-head comparison of the complete algorithms. The main conclusion is that no single algorithm performs best; which algorithm is to be preferred depends on the conditions (range errors, connectivity, anchor fraction, etc.). In each case, however, there is significant room for improving accuracy and/or increasing coverage.

title: Estimating coverage holes and enhancing coverage in mixed sensor networks
abstract: Area coverage is one of the most fundamental problems in ad hoc wireless sensor networks because it directly relates to optimization of resources in a sensing field. Maximizing the coverage area while maintaining a lower cost of deployment has always been a challenge, especially when the monitoring region is unknown and possibly hazardous. In this paper, we present a method to deterministically estimate the exact amount of coverage holes under random deployment using Voronoi diagrams and use the static nodes to collaborate and estimate the number of additional mobile nodes needed to be deployed and relocated to optimal positions to maximize coverage. We follow a two-step deployment process in a mixed sensor network and we argue by simulation and analysis that our collaborative coverage enhancing algorithm (COVEN) can achieve a tradeoff between the cost of deployment and percentage of area covered.

title: Implementing software on resource-constrained mobile sensors: experiences with Impala and ZebraNet
abstract: ZebraNet is a mobile, wireless sensor network in which nodes move throughout an environment working to gather and process information about their surroundings[10]. As in many sensor or wireless systems, nodes have critical resource constraints such as processing speed, memory size, and energy supply; they also face special hardware issues such as sensing device sample time, data storage/access restrictions, and wireless transceiver capabilities. This paper discusses and evaluates ZebraNet's system design decisions in the face of a range of real-world constraints.Impala---ZebraNet's middleware layer---serves as a light-weight operating system, but also has been designed to encourage application modularity, simplicity, adaptivity, and repairability. Impala is now implemented on ZebraNet hardware nodes, which include a 16-bit microcontroller, a low-power GPS unit, a 900MHz radio, and 4Mbits of non-volatile FLASH memory. This paper discusses Impala's operation scheduling and event handling model, and explains how system constraints and goals led to the interface designs we chose between the application, middleware, and firmware layers. We also describe Impala's network interface which unifies media access control and transport control into an efficient network protocol. With the minimum overhead in communication, buffering, and processing, it supports a range of message models, all inspired by and tailored to ZebraNet's application needs. By discussing design tradeoffs in the context of a real hardware system and a real sensor network application, this paper's design choices and performance measurements offer some concrete experiences with software systems issues for the mobile sensor design space. More generally, we feel that these experiences can guide design choices in a range of related systems.

title: JAM: a jammed-area mapping service for sensor networks
abstract: Preventing denial-of-service attacks in wireless sensor networks is difficult primarily because of the limited resources available to network nodes and the ease with which attacks are perpetrated. Rather than jeopardize design requirements which call for simple, inexpensive, mass-producible devices, we propose a coping strategy that detects and maps jammed regions. We describe a mapping protocol for nodes that surround a jammer which allows network applications to reason about the region as an entity, rather than as a collection of broken links and congested nodes. This solution is enabled by a set of design principles: loose group semantics, eager eavesdropping, supremacy of local information, robustness to packet loss and failure, and early use of results. Performance results show that regions can be mapped in 1-5 seconds, fast enough for real-time response. With a moderately connected network, the protocol is robust to failure rates as high as 25 percent.

title: Denial of Service in Sensor Networks
abstract: Sensor networks hold the promise of facilitating large-scale, real-time data processing in complex environments, helping to protect and monitor military, environmental, safety-critical, or domestic infrastructures and resources, Denial-of-service attacks against such networks, however, may permit real world damage to public health and safety. Without proper security mechanisms, networks will be confined to limited, controlled environments, negating much of the promise they hold. The limited ability of individual sensor nodes to thwart failure or attack makes ensuring network availability more difficult. To identify denial-of-service vulnerabilities, the authors analyzed two effective sensor network protocols that did not initially consider security. These examples demonstrate that consideration of security at design time is the best way to ensure successful network deployment.

title: Low-power DoS attacks in data wireless LANs and countermeasures
abstract: In this paper we investigate the resiliency to jamming of data protocols, such as IP, over WLAN. We show that, on existing WLAN, an adversary can successfully jam data packets at a very low energy cost. Such attacks allow a set of adversary nodes disseminated over an area to prevent communication, partition an ad hoc network, or force packets to be routed over adversary chosen paths. The ratio of the jamming pulses duration to the transmission duration can be as low as 10--4. We investigate and analyze the performance of using various coding schemes to improve the robustness of wireless LANs for IP packets transmission. A concatenated code that is simple to decode and can maintain a low Frame Error Rate (FER) under a jamming effort ratio of 15%. We argue that LDPC codes will be very suitable to prevent this type of jamming. We investigate the theoretical limits by analyzing the performance derived from upper bounds on binary error-control codes. We also propose an efficient anti-jamming technique for IEEE802.11b.

title: Channel surfing and spatial retreats: defenses against wireless denial of service
abstract: Wireless networks are built upon a shared medium that makes it easy for adversaries to launch denial of service (DoS) attacks. One form of denial of service is targeted at preventing sources from communicating. These attacks can be easily accomplished by an adversary by either bypassing MAC-layer protocols, or emitting a radio signal targeted at jamming a particular channel. In this paper we present two strategies that may be employed by wireless devices to evade a MAC/PHY-layer jamming-style wireless denial of service attack. The first strategy, channel surfing, is a form of spectral evasion that involves legitimate wireless devices changing the channel that they are operating on. The second strategy, spatial retreats, is a form of spatial evasion whereby legitimate mobile devices move away from the locality of the DoS emitter. We study both of these strategies for three broad wireless communication scenarios: two-party radio communication, an infrastructured wireless network, and an ad hoc wireless network. We evaluate several of our proposed strategies and protocols through ns-2 simulations and experiments on the Berkeley mote platform.

title: The feasibility of launching and detecting jamming attacks in wireless networks
abstract: Wireless networks are built upon a shared medium that makes it easy for adversaries to launch jamming-style attacks. These attacks can be easily accomplished by an adversary emitting radio frequency signals that do not follow an underlying MAC protocol. Jamming attacks can severely interfere with the normal operation of wireless networks and, consequently, mechanisms are needed that can cope with jamming attacks. In this paper, we examine radio interference attacks from both sides of the issue: first, we study the problem of conducting radio interference attacks on wireless networks, and second we examine the critical issue of diagnosing the presence of jamming attacks. Specifically, we propose four different jamming attack models that can be used by an adversary to disable the operation of a wireless network, and evaluate their effectiveness in terms of how each method affects the ability of a wireless node to send and receive packets. We then discuss different measurements that serve as the basis for detecting a jamming attack, and explore scenarios where each measurement by itself is not enough to reliably classify the presence of a jamming attack. In particular, we observe that signal strength and carrier sensing time are unable to conclusively detect the presence of a jammer. Further, we observe that although by using packet delivery ratio we may differentiate between congested and jammed scenarios, we are nonetheless unable to conclude whether poor link utility is due to jamming or the mobility of nodes. The fact that no single measurement is sufficient for reliably classifying the presence of a jammer is an important observation, and necessitates the development of enhanced detection schemes that can remove ambiguity when detecting a jammer. To address this need, we propose two enhanced detection protocols that employ consistency checking. The first scheme employs signal strength measurements as a reactive consistency check for poor packet delivery ratios, while the second scheme employs location information to serve as the consistency check. Throughout our discussions, we examine the feasibility and effectiveness of jamming attacks and detection schemes using the MICA2 Mote platform.

title: Mobility increases the capacity of ad hoc wireless networks
abstract: The capacity of ad hoc wireless networks is constrained by the mutual interference of concurrent transmissions between nodes. We study a model of an ad hoc network where n nodes communicate in random source-destination pairs. These nodes are assumed to be mobile. We examine the per-session throughput for applications with loose delay constraints, such that the topology changes over the time-scale of packet delivery. Under this assumption, the per-user throughput can increase dramatically when nodes are mobile rather than fixed. This improvement can be achieved by exploiting a form of multiuser diversity via packet relaying.

title: Towards mobility as a network control primitive
abstract: In the near future, the advent of large-scale networks of mobile agents autonomously performing long-term sensing and communication tasks will be upon us. However, using controlled node mobility to improve communication performance is a capability that the mobile networking community has not yet investigated. In this paper, we study mobility as a network control primitive. More specifically, we present the first mobility control scheme for improving communication performance in such networks. Our scheme is completely distributed, requiring each node to possess only local information. Our scheme is self-adaptive, being able to transparently encompass several modes of operation, each respectively improving power efficiency for one unicast flow, multiple unicast flows, and many-to-one concast flows. We provide extensive evaluations on the feasibility of mobility control, showing that controlled mobility can improve network performance in many scenarios. This work constitutes a novel application of distributed control to networking in which underlying network communication serves as input to local control rules that guide the system toward a global objective.

title: Sensor relocation in mobile sensor networks
abstract: Recently there has been a great deal of research on using mobility in sensor networks to assist in the initial deployment of nodes. Mobile sensors are useful in this environment because they can move to locations that meet sensing coverage requirements. This paper explores the motion capability to relocate sensors to deal with sensor failure or respond to new events. We define the problem of sensor relocation and propose a two-phase sensor relocation solution: redundant sensors are first identified and then relocated to the target location. We propose a Grid-Quorum solution to quickly locate the closest redundant sensor with low message complexity, and propose to use cascaded movement to relocate the redundant sensor in a timely, efficient and balanced way. Simulation results verify that the proposed solution outperforms others in terms of relocation time, total energy consumption, and minimum remaining energy.

title: Self aware actuation for fault repair in sensor networks
abstract: Actuation ability introduces a fundamentally new design dimension in wireless ad-hoc sensor networks, allowing the network to adaptively reconfigure and repair itself in response to unpredictable run-time dynamics. One of the key network resources in these systems is energy and several uncontrollable factors lead to situations where a certain segment of the network becomes energy constrained before the remaining network. The performance gets limited due to the constrained sections. We argue that in this scenario, instead of rendering the complete network useless, the remaining energy resources should be reorganized to form a new functional topology in the network. We present methods for the network to be aware of its own integrity and use actuation to improve performance when needed. This capability of the system is referred to as "self aware actuation". In this paper, we consider a network where nodes (or a subset of the nodes) have traction ability. The network uses mobility to repair the coverage loss in the area being monitored by it. We present a completely distributed energy aware algorithm (referred to as CO-Fi) for coordinated coverage fidelity maintenance in sensor networks. The energy overheads of mobility are incorporated in the algorithm, thus leaving no hidden costs. Our preliminary analysis shows that CO-Fi can significantly help improve the usable lifetime of these networks.

title: An incremental deployment algorithm for mobile robot teams
abstract: This paper describes an algorithm for deploying the members of a mobile robot team into an unknown environment. The algorithm deploys robots one-at-a-time, with each robot making use of information gathered by the previous robots to determine the next deployment location. The deployment pattern is designed to maximize the area covered by the robots' sensors, while simultaneously ensuring that the robots maintain line-of-sight contact with one another This paper describes the basic algorithm and presents results obtained from a series of experiments conducted using both real and simulated robots.