OVERVIEW

The performance of a sensor network may be best judged by the quality of application specific information return. Any given application would need a certain sensing performance, which must be guaranteed in the face of unpredictable event distributions and the presence of static and mobile environmental obstacles. Sensing media are typically not homogeneous as assumed in circular disk coverage models and it becomes essential to operate reliably in the presence of anisotropies. Such practical considerations are critical in the design of sensor networks due to the strong coupling of the system to its deployment environs. For instance, if a network of cameras is installed for security monitoring and certain regions of the scene are occluded by obstacles, the utility of the system to the user will immediately diminish. The system designer is challenged to not only provide the required performance within the resource constraints of embedded sensor nodes and a limited power budget but also ensure autonomous operation of the system in unknown environments. Environment specific customization is not desirable, as it hinders rapid deployment. In this research we are considering methods which allow the sensor network to control its sensing uncertainty by adaptively reconfiguring itself to the environment peculiarities and run time dynamics.

We use embedded motility to enable physical reconfiguration of the system. A test bed of network cameras with built-in motility primitives is being developed to evaluate our distributed algorithms for coordinated actuation.

Coordinated Actuation Testbed

APPROACHes

The performance problem outlined in the overview can be alleviated with the use of controlled mobility. We argue that the use of mobility to overcome sensing uncertainties is essential due to two reasons. The first reason is providing sensor diversity. A certain node density may be calculated for a specific sensor based on its nominal range in an isotropic medium or the required granularity at which the phenomenon is to be sensed. However, this density does not guarantee the quality of sensing in a real environment with anisotropic media and presence of obstacles. It is reasonable to accept that the deployment environment will be fairly arbitrary as mass produced systems will not be individually customized for each deployment. A prohibitively high density would be required to guarantee performance in an unknown and arbitrary environment. This high density is also associated with bandwidth problems and may cause intrusive interference with the sensed environment itself. Also, static high density sensors can give only probabilistic coverage. Actuated sensors, on the other hand, can adapt to the specific deployment scenario and give the exact coverage performance required. The second reason comes from the need for adapting to the run time dynamics of the environment. Obstacles may move in an unpredictable manner making it necessary for the system to adjust. Thus, the only feasible method to achieve performance guarantees is to endow the system with a capability to auto-configure and re-position in response to environmental peculiarities.

We first show that a small range of mobility relative to the mean obstacle size of the environment can lead to significant improvement in coverage performance. This finding is extremely important for sensor network design because of the specific nature of resource constraints in the system. Mobility in a general form has several disadvantages which make its use in sensor networks highly impractical. Most proposed systems which do use mobility restrict it to a small subset of the nodes in the network. Firstly, supporting mobility requires the nodes to be capable of accurately localizing their positions and navigating across the deployed terrain. This requires significant resources in terms of localization hardware, terrain sensing, motion feedback and the resultant complex data processing. Secondly, even if all the resources can be provided, the errors in the position of the node itself introduce further complications in the sensing and detection algorithms. Thirdly, large amounts of energy are required for physically moving the node on arbitrary terrain.

In contrast, node mobility operating over a limited range, often referred to as motility, can feasibly be provided to low cost sensor nodes deployed in large numbers. Several factors lead to this conclusion. First, a short linear displacement may be executed through addition of small infrastructure in the form of linear actuators, for example. This may include a track mechanism, permitting small motion around mean node position. Several sensors, such as network cameras are available with buil-in motility primitives such as pan, tilt, and zoom capabilities.

Preliminary analysis carried out to study the advantage due to small actuation, or more specifically, actuation that is limited to small multiples of the mean obstacle size in the environment, has shown to yield significant coverage advantage. Further, simulations and experiments have been carried out to validate the claims.

SYSTEMS / EXPERIMENTS

Simulations
To study the effect of obstacles on coverage and how small amounts of mobility help improve it, we carried out the following simulations. The simulations essentially model a surface deployment, where the sensors are mounted on objects lying on the ground, pillars or trees. The effect of height is not accounted for in the obstacle model. Three dimensional calculations would be needed when sensors are observing the environment from a UAV or very high altitude. Again, we consider sensors placed along edges of a square region, which as before models one tile of a large deployment. The mobile sensor is assumed to be able to move a short distance along the edge. To model realistic obstacles, we first note than most everyday objects have a small aspect ratio. Also, for the line of sight sensor, it is not the exact shape of the obstacle but the angle subtended by it at the sensor which determines the occlusion. With this reasoning, we simulate the obstacles as circular. Notable exceptions to small aspect ratio objects are walls and other forms of boundaries which will severely limit the coverage of a sensor and we do not expect low complexity actuation to overcome the effect of walls.

The obstacle diameter is assumed to be a random variable with uniform distribution. The density of obstacles is represented as number of obstacles per unit area. The obstacles are placed uniformly randomly over a square area. The random coordinates may lead to overlapping obstacles causing the formation of complex obstacle shapes. As discussed before, we are not concerned with the exact shape of obstacle but rather with the occlusion caused by it. The sensor is again assumed to be capable of moving a distance which is a small multiple of average obstacle size.

Coverage is measured by evaluating the area which is visible to the sensor compared to the free area left in the square after the area occupied by the obstacles themselves is subtracted. The line of sight from the sensor to every point in the free area is tested and if there is an obstacle blocking it, that point is assumed occluded. Coverage can be calculated by counting the occluded points and the visible points. To suppress the effect of peculiar chance placements, for each choice of parameter values we average our measurements over 20 runs of the simulation. Figure 1 shows the coverage advantage with varying obstacle size and with varying obstacle density. The figure shows two cases- one when mobility is limited to just the average length of the obstacles, and second when mobility is limited to twice the mean obstacle length. The figures demonstrate that significant coverage advantage is expected.

Experiments
Experiments were also performed with actual sensors in a real sensing medium. This brings in several realistic concerns such as sensor noise, sensor’s quality of detection with distance and data compression into play. A camera test-bed has been built for this purpose which supported the present experiments and also enables future research on these issues. Figure 2 shows a picture of obstacles in our laboratory test-bed, seen from the camera location. The sensor used on the test-bed is an Axis 2100 camera system. The camera system is equipped with rotational articulation to enable imaging in the entire plane of rotation. Image processing algorithms required to detect the presence of a target have been implemented on the Linux server which processes the data generated by these cameras.

Figure 2. A sample view of the laboratory testbed for the test-bed camera.

The coordinates for obstacle placement are obtained from the actual location of trees in the Wind River forest. The size of tree stems is assumed equal for simplicity of construction. Actual tree coordinates do not follow a uniformly random distribution due to physiological phenomena and using actual forest tree coordinates is expected to provide a realistic obstacle scenario. The obstacles used here are cylinders with diameter of 1 foot. They are placed in a 12 foot by 12 foot grid. The tree coordinates are shown in Figure 3.

Figure 3. Coordinates of obstacle placement ion laboratory test-bed.

The target itself is a small cylinder of a different color than the obstacles. It can be seen as the  small black cylinder in Figure 2. The obstacles are colored brown to abstract tree stems. A simple image processing technique is used to detect the target in the captured image. As the lighting in the laboratory is controlled, we can take an image of the background with no target present and detect the target by subtracting an image taken when the target is present from the background image. If the target is completely occluded, it is assumed not detected. If it is partially occluded, we assume it as detected if the number of pixels visible is above a certain threshold. This threshold procedure reduces the contribution of noise associated with the camera system by ensuring that a minimum portion of the target is observed in order to declare a positive detection.

The experiment is performed as follows. First the camera is placed at the midpoint of one edge of the square area. With the camera stationary, the target is moved to uniformly spaced locations on
the $12' \times 12'$ grid. The number of locations at which the camera is able to detect the target divided by the total number of locations at which the target was placed gives the coverage achieved by the static sensor.

Next the camera is assumed to be able to move a distance of two feet. Coverage is again computed using the previous target placement procedure but now if the target can be detected by the camera by moving along its track, the target is assumed detected. Further, we vary the number of cameras available. One additional camera is successively added on each of the other edges. The mis-detection probabilities are plotted in Figure 4 for varying number of cameras, both for the stationary case and the mobile case. The mis-detection with mobility reduces significantly compared to the static case, reaching an order of magnitude improvement in some cases.

Experiments are also performed in an outdoor environment where the obstacles are not artificial objects but actual trees and foliage. The obstacles are no longer ideal cylinders and cameras do not operate in controlled lighting conditions. The cameras used as sensors are not designed for outdoor usage and the image quality is affected by exposure to sunshine for the long duration required for collecting data in our experiments. This leads to some errors in our simple image processing techniques for detecting the target. The experimental challenges include operating from batteries away from wall sockets and positioning the sensors on uneven terrain instead of the leveled laboratory floor. It may be noted that the foliage causes rather large occlusions and our mobility here is much less than the mean obstacle diameter, instead of being an integral multiple of it. A sample image of the deployment scene is shown in Figure 5.

Figure 5. An image of the outdoor deployment scenario.

The experiment performed consists of one camera placed along one edge. Coverage is measured over a $12' \times 12'$ grid in the forest. Detection probability is first measured when the camera is fixed at the midpoint of the edge. Then the camera is allowed to move two feet in one direction. Third the camera is allowed to move 2 feet in both directions. The mis-detection probabilities and gains are tabulated in Table 1. The measurements show that mobility even when lower than average obstacle length is able to provide significant advantage in reducing the uncertainty of sensing.

ACCOMPLISHMENTS

The project accomplishments include:

1. Extensive simulations and experiments have been performed to corroborate the intuition that limited mobility will help improve coverage.
2. A linux test-bed with camera sensors and an obstacle rich sensing medium has been developed to carry out realistic coverage experiments.
3. The image processing software required for actual detection in the test-bed has been prepared and can be used for further research.
4. Education Objectives:
   The research led to summer projects for undergraduate students and helped them get exposure to cutting edge research in sensor networks.
5. Research papers based on the current work:
   A Kansal, E Yuen, W Kaiser, G Pottie and MB Srivastava, “Sensing Uncertainty Reduction Using Low Complexity Actuation,” ACM Third International Symposium on Information Processing in Sensor Networks (IPSN) 2004.

FUTURE DIRECTIONS

This work is now being extended in two directions. One is building the obstacle detection modules which can be added to sensor nodes to learn the presence of obstacles in the scene. This  information can then be used by the sensor node to decide its position or to plan its motion. The second is the development of collaborative algorithms for sensor nodes to optimize their positions in view of the learnt propagation characteristics of the environment. These methods can enable a set of randomly placed nodes to customize their positions for the specific deployment and update it as required.

PEOPLE

Faculty:

Prof William J Kaiser
Prof. Mani B Srivastava
Prof Gregory J Pottie

Graduate Students:

Aman Kansal

Undergraduate Students:

Eric Yuen
Eric Lin
Michael Smith
Michael Stealey