Locational optimization

Sensor placement dramatically affects the performance of a mobile sensor network. Locational optimization has been identified as a convenient framework to address this problem. In general, locational optimization minimizes a cost function that captures the quality of sensing with respect to the locations of the mobile sensors.

In other applications, such as urban planning, locational optimization is used to solve the resource allocation problem such as where to build waste collection stations that serve the area most efficiently.

Coverage control

For mobile sensor networks, sensor placement has been extensively studied. Coverage is one of the most important tasks. In coverage, each sensor node is responsible for sensing in its own region. In their seminal paper [1], the authors show that optimal sensor coverage can be formulated as a minimization problem, where an appropriate cost function is minimized with respect to the partition of the space and the locations of the sensor nodes. The formulation naturally led to the Lloyd-type gradient descent algorithm that achieves optimal sensor coverage.

Coverage control with information aggregation

Since data transfer is a main function of the sensor network, in [2] the authors propose a distributed coverage control law that maximizes the joint detection probability of an event happening in the area while minimizing the energy consumed by the sensors sending the information from their detection range to a fixed sink via a wireless antenna. In the optimal network configuration, the perception areas of neighboring sensors overlap with each other and the sink node receives redundant information. In most coverage applications, each sensor dominates its unique subregion and there is no sensing overlap. The latter is more natural for facility location problems, where each point in an area needs to be served by at least one network node but the service quality does not improve when it is served by multiple nodes. For example, two charging stations that are equally away from a robot do not improve the robot’s ability to recharge.

In our work, we consider a group of mobile sensors monitoring an area for events whose occurrence is governed by a probability density function. The nodes need to send the information they collect to an aggregation(sink) node. The space is partitioned into subregions, so every point in the area is monitored by one sensor. Within its subregion, each sensor node collects the information about the occurrence of an event and sends the information to a mobile sink node. We try to minimize the total cost of both coverage and information aggregation for the network. Motivated by the cost of wireless communication in [2], we model the cost of sending the information from a sensor node to the sink node as a product of the amount of information within the subregion and the distance between the sensor node and the sink node. Finding optimal sensing configuration for the coverage task has been studied in [1]. However, when both coverage and information aggregation are considered, the framework proposed in [1] needs to be extended. In our work, we minimize the combined cost of coverage and information aggregation with respect to both the partition of the space and the locations of all sensor nodes. We analytically determine the equilibrium configurations for all sensor nodes, including the mobile sink node. We also determine the optimal partition of the space given the locations of the sensor nodes. Using these results, we propose a gradient descent algorithm that drives all the nodes, including the mobile sink node, to an equilibrium configuration from an arbitrary initial configuration.

[1] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,” IEEE Transactions on Robotics and Automation, vol. 20, no. 2, pp. 243–255, 2004.

[2] W. Li and C. G. Cassandras, “Distributed cooperative coverage control of sensor networks,” in Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC’05. 44th IEEE Conference on. IEEE, 2005, pp. 2542–2547.